（应用数学专业论文）一些bch码的极小距离.pdf

摘要 内容摘要：循环码是一类非常重要的线性分组码，它们建立在严格的 代数理论基础上。由于它们编译码迅速，具有较强的纠错和检错能 力，从而在实践中具有重要作用。迄今为止，己有大量的文献对有 限域上的循环码的编码理论进行了研究。线性码的主要参数有码的 长度，维数以及码的极小距离，其中码的维数决定了码的大小，极 小距离确定了码的纠错能力。一般来说，不容易确定码的维数以及 极小距离。本文主要研究了有限域日上特定码长的一类循环码的极 小距离。 本文首先讨论了有限域b 上的码长为佗= q 。+ q 扣1 + + 口+ 1 的b c h 码的极小距离。 其次确定了有限域e 上码长为佗= q 2 + 1 的b c h 码的极小距离。 最后确定了有限域f q 上g n = q 4 + 1 的b c h 码的极小距离。 关键词：循环码，h a m m i n g 界，生成多项式，极小距离 a b s t r a c t c o n t e n t ：c y c l i cc o d e sa r ev e r yi m p o r t a n tl i n e a rb l o c kc o d e s ，w h i c h s e tu ps t r i c t l yo nb a s i ca l g e b r at h e o r y s i n c ec y c l i cc o d e sa r ee n c o d e d a n dd e c o d e dr a p i d l ya n dt h e ya r ew i t hs t r o n ge r r o rc o r r e c t i o na n d e r r o rd e t e c t i o nc a p a b i l i t y , t h e yp l a ya ni m p o r t a n tr o l e i np r a c t i c e s of a r ，t h e r ea r eal o to fr e f e r e n c e sa b o u tc y c l i cc o d e so v e rf i n i t ef i e l d s 日f o rl i n e a rc o d e s ，t h e r ea r et h r e em a j o rp a r a m e t e r s ，t h e ya r el e n g t h s o fc o d e s ，d i m e n s i o n so fc o d e sa n dm i n i m u md i s t a n c e so fc o d e s d i m e n - s i o n so fc o d e sd e t e r m i n et h en u m b e r so fc o d e sa n dm i n i m u md i s t a n c e s o fc o d e sd e t e r m i n ee r r o rc o r r e c t i o na b i l i t y g e n e r a l l ys p e a k i n g ，i ti sn o t e a s yt od e t e r m i n ed i m e n s i o n sa n dm i n i m u md i s t a n c e so fc o d e s i nt h i s p a p e r ，w es t u d ym i n i m u md i s t a n c e so fs o m ec y c l i cc o d e sw i t hs p e c i a l l e n g t h s f i r s t l y , w ed e t e r m i n et h em i n i m u md i s t a n c eo ft h ec y c l i cc o d ew i t h l e n g t hn = q + q 。一1 + + q + 1 s e c o n d l y , w ed e t e r m i n et h em i n i m u md i s t a n c eo ft h ec y c l i cc o d e w i t hl e n g t hn = q 2 + 1 f i n a l l y , w ed e t e r m i n et h em i n i m u md i s t a n c eo ft h ec y c l i cc o d ew i t h l e n g t h 佗= q 4 + 1 k e yw o r d s ：c y c l i cc o d e s ，h a m m i n gs e c t o r ，g e n e r a t i n gp o l y n o m i a l ，t h e m i n i m u md i s t a n c e 学位论文独创性声明 本人承诺：所呈交的学位论文是本人在导师指导下所取得的研究成果。论文中除特 别加以标注和致谢的地方外，不包含他人和其他机构已经撰写或发表过的研究成果，其 他同志的研究成果对本人的启示和所提供的帮助，均已在论文中做了明确的声明并表示 谢意。 学位论文作者签名： 学位论文版权的使用授权书 本学位论文作者完全了解辽宁师范大学有关保留、使用学位论文的规定，及学校有 权保留并向国家有关部门或机构送交复印件或磁盘，允许论文被查阅和借阅。本文授权 辽宁师范大学，可以将学位论文的全部或部分内容编入有关数据库并进行检索，可以采 用影印、缩印或扫描等复制手段保存、汇编学位论文，并且本人电子文档的内容和纸质 论文的内容相一致。 保密的学位论文在解密后使用本授权书。 学位论文作者签名：指导教师签名： 签名日期： 2 d o 年月7 日 一些b c h 码的极小距离 1引言 一些b c h 码的极小距离 代数编码是电子时代抽象的数学理论得到巧妙应用的范例。代数编码产生 于五十年代初，由于数字通信和数字储存的需要，在其后的几年间得到了迅速的 发展。电子时代，任何高速度数据传输系统和计算机的数据储存系统都会由于种 种原因而发生差错。如何控制这些差错是一个重要的课题，纠错码就是为了解决 这个课题而产生和发展的起来的。s h a n n o n 1 】在1 9 4 8 年首次提出了著名的有扰 信道编码定理，开创了纠错码理论的研究方向，奠定了纠错码理论的基石根 据s h a n n o n 的思想，h a m m i n g 2 l ，兄c b o s e ，d k r a y c h a u d h u r i ，a h o c q u e n g h e m ( b c h ) 3 1 - 【5 1 ，m a s s e y 6 一【8 】，m a c w i u i a m s 9 1 - 【1 1 1 ，g o p p a 1 2 ，n e c h a e v 1 3 ，冯 贵副1 4 卜【1 5 】等纠错码理论专家先后给出了一系列设计好码和有效译码的方 法而后，纠错码受到了越来越多的通信和数学工作者，特别是数学家的重 视，使纠错码无论在理论上还是在实际中都得到飞速发展迄今，纠错码已有 五十多年的历史，其发展过程大致分为以下几个阶段： 2 0 世纪5 0 年代至6 0 年代初主要研究各种有效的编、码方法，奠定了线性分 组码的理论基础，提出了著名的b c h 码，同时也给出了纠错码的基本码限。这 是纠错码从无到有得到迅速发展的年代，也是纠错码发展过程中最为活跃的时 期。不仅提出了许多有效的编译码方法，而且注意到了纠错码的实用化问题， 讨论了与实用有关的各种问题，所有这些问题的研究为纠错码的应用打下了坚 实的理论基础。在此期间，以代数方法特别是以有限域理论为基础的线性分组 码理论已趋成熟。 2 0 世纪7 0 年代至8 0 年代初，这是纠错码发展史中具有极其重要意义 的时期。在理论上g o p p a 等学者，构造了一类g o p p a 码，其中一类子码能 达s h a n n o n 在信道编码定理中所提出的s h a n n o n 码所能达到的性能，这在纠错码 历史上具有划时代意义。在这期间大规模集成电路和计算机技术迅速发展，为 纠错码的应用打下了坚实的物质基础，因而与实用相关的各种技术及有关问题 得到了极大关注，并在实践中取得了巨大的成功。 自2 0 世纪8 0 年代初至今，g o p p a 等从几何观点讨论分析码，利用代数曲线 构造了一类代数几何码。在这些码中，某些码的性能达到了s h a n n o n 码码所能 达到的性能。由于代数几何码是一类范围非常广的码，在理论上已证明它具有 优越性能，因而受到了编码理论研究者，尤其是代数几何学家的重视，使代数 几何码的研究得到迅速发展，取得了许多成果。 一些b c h 码的极小距离 近二十年来，随着有限域上编码理论发展日益成熟，人们逐渐将研究目光 转移到纠错码的检错和纠错能力的研究上来，特别是具有重大实用意义的特殊 纠错码即线性码和循环码的检错和纠错能力。当前应用广泛的纠错码是汉明码 和b c h 循环码。汉明码效率高，但仅能纠正一个差错。但是b c h 循环码却可以 纠正任意多个事先给定的差错，所以b c h 循环码具有更大的使用意义。众所周 知，码的长度、维数以及码的极小距离是线性码的最主要的参数。其中码的维 数确定了码的大小，极小距离确定了码的纠错能力。所以对循环码的极小距离 的研究成了许多学者的一个重要课题。然而计算循环码的极小距离却是一件异 常困难的工作，通常只能用b c h 界或者一些较好的界去刻画它的下界。如何提 高极小距离的下界使之更接近真实值，一直是人们感兴趣的问题。文献【1 6 】对前 人的工作做了比较系统的引用和发挥，通过研究生成多项式的零点与极小距离 的关系，对几乎所有的n 6 3 ( n 为码长) 的二元循环码的极小距离做了界定， 文献【1 7 1 将研究对象投向了另一种循环码，围绕生成多项式的零点、码长、极 小距离和b c h 界进行讨论，得到了使循环码的极小距离等于其b c h 界的两个充 要条件。文献【1 8 】则主要研究了码长是亿= q 2 一q + 1 的q 元循环码的极小距离( 其 中q 4 ) 。受文献【1 8 l 的启发，本文主要在前人已有的工作基础之上，进一步研 究了b c h 码的极小距离问题，具体内容如下： ( 1 ) 确定了有限域r 上码长为n = q t + q t _ 1 + + 口+ 1 的b c h 循环码的极小距 离。 ( 2 ) 确定了有限域e 上码长为佗= q 2 + 1 的b c h 循环码的极小距离。 ( 3 ) 确定了有限域r 上码长为n = q 4 + 1 的b c h 循环码的极小距离。 2 些b c h 码的极小距离 2预备知识 定义2 1 i 1 1 】 如果z = ( x 0 ，x l ，z 竹一1 ) 鬈，y = ( y o ，y l ，蜘一1 ) 曰。则z ，可的h a m m i n g 距离为d ( x ，y ) = i i 1 0 i 死一1 ，x i 玑) i 。z 的重量定 义为w ( x ) = d ( x ，0 ) 。 定义2 2 非平凡码的极小距离定义为m i n d ( x ，y ) l xe c ，ye c ，z 可) 。 极小重量定义为m i n w ( c ) l xe c ，c o ) 。 一个码的极小距离在纠错检错的时候有着重要的作用。如果一个码的极小 距离是2 e + 1 ，一个码字c 在传输的过程中有七( e ) 个位置发生了错误，接收方 接受的码字为c ，当检测出c ，不是c 中的码字后，可以将其纠正，得到正确的码 字c 。 定义2 3 【1 1 】 已知线性码c 的一组叼一基v l ，v 2 ，仇) ，其中v i = ( a i l ，o 幽 ，a l n ) ( 1 i ) ，a i j 叼，则每个码字c c 可以唯一的表示成c = b i v i = ( b l ，6 2 ，b a ) g ，( ( b l ，b 2 ，b k ) 日) 其中 g = ( ：) = ( 三：二薹：j ：三二) 矩阵g 称为线性码c 的一个生成阵。我们可以先把k = q 惫个信息编成露中 的向量( b l ，b 2 ，b k ) ( 共q 个) ，为了纠错，再把它们变成c 中的码字c = ( b l ，b 2 ，b k ) g ，所以纠错码编码即是日一线性的单射 兰三耋詈三：三主兰三毫 一些b c h 码的极小距离 定义2 4 【1 9 1r 中任意元素p 的极小多项式是指系数取自r ，使m ( p ) = o 成立的方程中次数最小的首一多项式m ( x ) 。 定义2 5 1 1 1 】 r 中参数为hk ，d l 的g 元线性码c ( 即曰中的线性子空 间) 称为循环码( c y c l i cc o d e ) ，若对g 中任意码字进行循环移位以后仍 然是c 的码字，即c r i 一1 c o c l c ，i 一2 c ，v c o c l c ，i 一2 c n l c 很多循环码与 多项式环r m 密切相关。将码字c = ( c o ，c 1 ，c n 一1 ) 写成多项式：c ( x ) = c i x ，d e g c ( x ) 】佗一1 则 1 - - 1 z c ( z ) = c i z 件1 = c n 一1 + c o x + + c n 一2 z n 一1m d d x n 一1 ) i = 0 如果把c ( z ) 看成是商环兄= 日( 扩一1 ) 中的元素，( c n 一1 ，c o ，c i ，c n - - 2 ) 恰好 对应于尺中的元素z c ( z ) ，则线性码c 可以看做是冗的日一线性子空间。若c 又 是循环码，这相当于c 满足如下条件： c ( x ) c 号x c ( x ) c 由此可知c 是循环码当且仅当c 是环兄中的一个理想( 由抽象代数知识进一步可 知，c 是兄的一个主理想) 。 定义2 6 【1 l 】如果c 是一个 n ，k 的q y 5 线性码，我们定义它的对偶码c 上为 c 上= 【y 曰l ( z ，秒) = 0 ，v x c 显然h 七1 码的对偶码是一个线性码。 引理2 1 【l l 】设c 是参数为h ，纠的g 元线性码，h = ( u l ，u 竹) 是c 的一 个校验矩阵。如果当中任意d 一1 个均为凡一线性无关，并且存在d 个列向量 是r 一线性相关的，则c 的最小距离为d 。 证明设c = ( c 1 ，c 2 ，c n ) 是碍 h a m m i n g ；校为f 的向量，即c 有 个分 量c f l ，c 2 ，c 卉不为零，而其余分量为零，则 c c 净。= 日c t = c u h u 幻，“。( 三j 2 勺t 嘶，+ 勺z 吻。+ + 勺，呦 这表明：c 中每个权为f 的非零码字对应给出日中f 个r 一线性相关的列 j r 。从 而c 的最小距离( 即非零码字的最小权) 就等于仳，u 2 ，u n 中线性相关列向量的 最少个数由此定理得证。 4 一些b c h 码的极小距离 引理2 2 【1 1 】 如果存在纠错码( n ，k ，d ) g 则 【孚】 矿k ( 口一1 ) 繇 面 这里晓是组合数( n 个物体中取i 个的方向数) 门i n ( n 一1 ) ( 礼一i + 1 ) n ! i ( i 一1 ) 1( n i ) ! i ! 证明 对每个整数r 0 和向量u = ( v l ，v n ) 叼，我们用& ( 移，r ) 表示 与v 的h a m m i n g 距离r 的所有向量组成的集合 岛( u ，7 ) = u j ? i d ( u ，u ) r 叫做以v 为中心半径为r 的( 闭) 球，不难算出这个球中向量的个数：对每个i 0 ，若u 与u 的h a m m i n g 距离为i ，n u 和v 恰有i 个分量不同。由于u = ( v l ，) 是固定的，n 个分量中选i 个的方法数为磷。在这i 个分量上u 的元素与v 不一 致，从而每个分量均有q 一1 种取法，其余分量上与秽一致，因此d ( u ，v ) = z 的钆共 有( 口一1 ) 碟个。于是球岛( 口，r ) 中元素个数为 r i s q ( v ，r ) i = ( g 一1 ) 砩 i = 0 现在设存在参数为( 佗，k ，d ) 的q 元码c ，令z = 譬】，考虑以c 中每个码字为 中心的所有半径均为f 的球岛( c ，f ) ( c c ) 。这样的球共k 个，对于其中两个不 同的球& ( c 1 ，z ) 和岛( c 2 ，0 ( c l ，c 2 c ，c l c 2 ) ，由d ( c l ，c 2 ) d 可知这两个球不相 交，因若有向量u 同时在这两个球中，贝u d ( u ，c 1 ) z ，d ( u ，c 2 ) z 。由三角形不 等式， d ( c 1 ，c 2 ) d ( u ，c 1 ) + d ( u ，c 2 ) 2 l ：2 竺；! 】d 一1 这与d ( c 1 ，c 2 ) d 相矛盾，于是，上述k 个球两两不相交，这些球所有元素之和 为k e ( 口一1 ) 嚷，它应不超过整个空间曰的元素个数矿，就给出了定理。 引理2 3 1 1 1 】设c 是一长度为n 的循环码，那么 ( 1 ) 设g ( x ) 是c 中次数最低的首一多项式，则c = 白( z ) ) ，并称g ( x ) 为c 的生成 多项式。 ( 2 ) c 的生成多项式夕( z ) 整除x n 一1 。 ( 3 ) 如果d e g g ( x ) = r ，那么c 的维数为d i m c = n r 。 证明 ( 1 ) 由于c 是一个理想，g ( x ) c ，所以( 9 ( z ) ) c 。v p ( z ) c 设 在f q i x 】中p ( z ) = q ( x ) g ( x ) + r ( z ) ，其中d e g g x d e g g ( x ) ，n & r ( x ) = p ( x ) 一 q ( x ) g ( x ) c ，由( 9 ( z ) 的取法可知r ( z ) = 0 。所以 p ( z ) = q ( x ) g ( x ) ( 夕( z ) ) 5 一些b c h 码的极小距离 从而c ( 夕( z ) ) 。于是我们有c = ( 夕( z ) ) 。 ( 2 ) 设在b 陋】中，x n - i = 口( z ) 9 ( z ) + r ( z ) 其中d e g g x d e g g ( x ) ，又在r 中妒一 1 = 0 c 所p a r ( x ) c ，又由夕( z ) 的取法e 失n r ( x ) = 0 所p a g ( x ) 整除扩一1 。 ( 3 ) 显然9 ( z ) ，z 9 ( z ) ，x n - r - l g ( x ) 在心中线性无关，下面只需证明他们生 成c 即可。由( 2 ) 知在日【z 】中有扩一l = ( z ) 9 ( z ) ，其中 d e g ( h ( x ) = 礼一r ， 于是在日i x 】中z 加r = q ( x ) h ( x ) + r ( z ) ，其中d e g ( r ( x ) = 佗一r 。所以我们有 x n - r g ( x ) = q ( x ) h ( x ) g ( x ) + r ( z ) g ( z ) ， 则 x - r g ( x ) 兰r ( x ) g ( x ) ( m o d x n 一1 ) 又因为d e 夕( r ( z ) = 礼一r ，所以z 舻r 9 ( z ) 可以m g ( x ) ，x a ( x ) ，x n - - r - - 1 9 ( x ) 线性表 出，于是它们是c 的基，所以c 的维数是n r 。 引理2 4 【1 1 】如果c = ( ， ) ) ，令k = 0 ，0 i 死一1 ：，( q ) = o ) ，则 有c = ( 夕( z ) ) ，其q j g ( x ) 一1 c m m ：i k ) 6 一些b c h 码的极小距离 3关于b c h 码的一些结果 引理3 1 【1 1 1 ( b c h 界)设c 是循环码，其生成多项式为9 ( z ) ，对一些整 数d 0 ，5 1 ，满足 9 ( q 6 ) = 夕( 口1 ) = = 夕( 口6 + 6 2 ) = 0 也就是说码c 有5 一l + a 的相邻幂作为零点。则码c 的极小距离d 5 。 证明 由b c h 码的定义可知， 其中， 如兮日f 亨1 ：。 其中0 i 1 i 2 ( 矿+ l 一1 ) ( q t 一1 ) 得 2 q ( q + 1 1 ) ( 矿一1 + + q + 1 ) 即 ( q + 1 1 ) ( 矿一1 + + q + 1 ) 一2 q 2 0 因此 鲨业主# 刿o 口一i 但是，不等式左边 ( q h 。1 1 ) ( 矿一1 ) 一2 q 。( 口一1 ) 一些b c h 码的极小距离 = q 2 件l q 。+ l q 2 + 1 2 q 件1 + 2 q = q 2 件1 + 1 + q 。一3 q 件1 = q t + l ( g t 一3 ) + 1 + q o ( t 2 ，q 2 ) 这与上面的结论相矛盾，所以当d 5 时h a m m i n g 界不成立，所以极小距 离d 4 。又根据引理3 1 【1 9 】，5 = 3 得d 3 。所以有3 d 4 ，故d = 3 - s j 4 。 推论4 1 1有限域而上，长度为礼= 2 + 2 扣1 + + 2 + 1 = 2 t “一1 ，生 成多项式为g ( x ) = m o ( x ) m l ( x ) 的b c h 码的参数为h ，n t 一2 ，4 】。 证明由定理4 1 1 知，码的极小距离d = 3 或4 。设c ( z ) 是一个码字c = ( c o ，e l ，一1 ) 所对应的多项式，虽p c ( z ) = c o + o x + + c n l x 俨1 ，则9 ( z ) i c ( z ) ， 于是c ( 1 ) = 0 ，即c 0 + c 1 + + c n 一1 = 0 。所以叫( c ) 是个偶数，即每个码字的重 量都是偶数。从而d = 4 。 定理4 1 2 岛上长度为n ，生成多项式为g ( x ) = m l ( x ) 的b c h 码的参数 为h ，n t 一1 ，胡，其中d = 2 ，3 或4 。 证明当生成多项式g ( x ) = m - ( z ) 时 其定义集 i = o l ，q 口，q r ，q 旷) ，i i i = t + 1 故d i m c = 礼一d e g g ( x ) = 死一t 一1 = k 。 t 一1 ，翻。同理，我们设极小距离d 5 ， 码c 的参数为 口。+ q 。一1 + + 口+ 1 ，佗一 假设它满足h a m m i n g 界。即有 q n 1 + 砩( g 一1 ) + 锈( g 一1 ) 2 】k q n - k 1 + 礼( 口一1 ) + 掣( 口一1 ) 2 有 q t + z q t + l + 掣( 口一1 ) 2 即 掣( g 一1 ) 2 o 这是矛盾的，所以极小距离d 4 ，又由于极小距离d l ，得d = 2 ，3 或4 。 定理4 1 3 当( t + 1 ，q 一1 ) = l e 6 ，由9 ( z ) = m 1 ( z ) 生成的长为佗= q + q 一1 + + q + 1 的b c h 码等价于h a m m i n g 码。 证明 码的生成多项式g ( x ) = m l ( x ) ，故码的校验矩阵是h = ( 1 ，a ，o l 2 ， o l 肛1 ) 。假设中有两列在日上线性相关，则存在a 0 日，使得n = ， 其中0 i j n 一1 ，于是a = 。因为a 0 e ，有a q 。= 1 ，所 以1 = a q 一1 = q ( j 一) ( g 一1 ) 又由口n = 1 ，得n l ( j i ) ( q 一1 ) 已知条件( t + 1 ，q 一1 ) = 1 2 一些b c h 码的极小距离 1 ，礼= 矿+ q 。一1 + + q + 1 = ( q 一1 ) + ( q 。一1 1 ) + + ( 口一1 ) + t + 1 ，从 而( 礼，口一1 ) = ( t + 1 ，q 一1 ) = 1 ，所p a n l j i ，但是0 2 ) 上长度为n = q 2 + 1 ，生成多项式为g ( x ) = m 1 ( z ) 的b c h 码的参数为i n ，他一4 ，明，其中d = 2 ，3 - ：或4 。 证明 b c h 码c 的码长为n = q 2 + 1 ，显然有n l q 4 1 我们先通过码c 的生 成多项式确定它的维数。由于它的生成多项式为g ( x ) = m 1 ( z ) 故其定义集为 i = 0 1 1 0 f f ，o t q 2 = o z ，a - q i i l = 4 ，所以d e g g ( x ) = 4 ，故d i m c = 礼一d e g g ( x ) = n 一4 = k 。码c ，的参数 为 q 2 + l ，q 2 3 ，司，假设d 5 ，i 扫h a m m i n g 界 q n 1 + c 甓( 口一1 ) - 4 - c 尝( g 一1 ) 2 】k 1 3 一些b c h 码的极小距离 即 得 从而 因此 得 口n - 七1 州q - - 1 ) + 掣( q - - 1 ) 2 9 4 1 + ( q 2 + 1 ) ( g 一1 ) + 垒兰二二堕掣 q 4 _ _ 1 ( 9 2 + 1 ) ( 口一1 ) + 鱼二j 皇掣 口3 + 口2 + g + 1 口2 + 1 + 垒掣 9 3 + g 坐掣, q 2 + l 盟掣 2 q ( q 一1 ) 当且仅当q = 2 时= 成立，所以，当q 2 时，极小距离d 4 ，r p d = 2 ，3 或4 。故 码c 的参数为h 佗一4 ，棚，其中d = 2 ，3 或4 。 推论4 2 1 如果口 2 是偶数，则由夕( z ) = m l ( x ) 生成的长度为n = q 2 + 1 的b c h 码的参数为h 扎一4 ，d 】，其中d = 3 或4 。 证明码的生成多项式g ( x ) = m l ( x ) ，故码的校验矩阵是h = ( 1 ，q ，q 2 ， o l 肛1 ) 。假设日中有两列在日上线性相关，则存在a 0 日，使得a o l = ，其 中0 i j n 一1 。于是a = 一。因为a 0 日，有a q _ 1 = 1 ，所 以1 = a q 一1 = q ( j 一 ) ( 口一1 ) ，又由o l 竹= 1 ，得n i ( j i ) ( g 一1 ) 。由于 ( n ，q 一1 ) = ( q 2 + 1 ，q 一1 ) = ( q 2 + 1 ，q 2 + 1 + q 一1 ) = ( q 2 + 1 ，q 2 + q ) = ( q 2 + 1 ，q + 1 ) = ( q 2 十1 ，q + 1 ) = ( ( 口+ 1 ) 22 q ，q + 1 ) = ( 2 q ，q + 1 ) = ( 2 ，q + 1 ) = 1 所以n l j i ，但是0 j - i 2 是偶数，则由夕( z ) = m l ( x ) v 成的长度为i t = 口4 + 1 的b c h 码的参数为h ，佗一8 ，司，其中d = 3 或4 。 证明码的生成多项式g ( x ) = m l ( x ) ，故码的校验矩阵是h = ( 1 ，q ，q 2 ， o l n - - 1 ) 。假设日中有两列在b 上线性相关，则存在a 0 局，使得o q = ， 其中o i j n 一1 。于是a = o g 一。因为a 0 日，有a q 。= 1 ，所 p a l = a q 一1 = a o 一) ( 口一1 ) 又由q n = 1 ，得nj ( j 1 ) ( 口一1 ) 。由于 ( n ，g 一1 ) = ( q 4 4 - 1 ，g 一1 ) = ( q 2 ( q 2 - 1 ) + q 2 + 1 ，g 一1 ) = ( q 2 ( g + 1 ) ( q 一1 ) + 口2 + 1 ，q - 1 ) = ( 口2 + 1 ，口一1 ) = ( q 2 1 + 2 ，口一1 ) = ( ( g + 1 ) ( 口一1 ) + 2 ，口一1 ) = ( 2 ，q 一1 ) = 1 所以训歹一i ，但是0 歹一i 翌鬯! ! 二! 巡1 2 3 q 一1 2 垫血些祟2 ( q 訾1 塑。 一) 一。 口3 ( 2 + q 5 + q q 4 1 ) ( 口一1 ) 一2 q 8 + 2 0 ( q 8 一q 7 + q 4 + q 3 ) ( g 一1 ) 一2 q 8 + 2 0 q 9 4 q 8 + q 7 + q 5 一q 3 + 2 0 口3 ( 9 6 4 9 5 + q 4 + q 2 1 ) + 2 0 ， q 3 9 2 ( 9 4 4 q 3 + q 2 + 1 ) 一1 】+ 2 0 一些b c h 码的极小距离 口3 口2 q 2 ( 口2 4 9 + 1 ) + 1 】一1 ) + 2 0 当q 2 时，不等式左边 9 3 口2 口2 ( 9 2 4 q + 1 ) + 1 】一1 ) + 2 0 所以当q 2 ，d 5 时，该码的参数不满足h a m m i n g 界，故d 4 。又因为码 有3 个连续的根，所以根据引理3 1 得d 4 ，得d = 4 。 定理4 3 3 定理定理4 3 2 中的r 上长度为n ，生成多项式为夕( z ) = 低( z ) 仇1 ( z ) 的b c h 码c 的对偶码c 上的参数为 n ，9 ，d ，】，其中d ，q 4 2 q 3 + 1 。 证明 因为码c 的生成多项式为9 ( z ) = 伽( z ) m 1 ( z ) ，所以对偶码c 上的定 义集为 j = q 2 ，q 3 ，o f f - 1o f f + 1 ，q 口2 1 ，q 口4 一9 3 + 2 ，o f f 4 一q - ，q 口4 一口2 + 2 ， o f f 4 一，q 矿一q + n ，o f f 4 1 ) 定义集中有连续的6 = q 4 2 q 3 个根。根据引理3 1 得，q 4 2 q 3 + 1 。 定理4 3 4 定理4 3 1 中的日上长度为佗，生成多项式为9 ( z ) = m 1 ) 的 b c h 碉j c 的对偶码c 上的参数为 死，8 ，刎，其中d ，q 4 2 q 3 + 1 。 1 9 些b c h 码的极小距离 5应用 1 码长) g n = q 2 + q + 1 的b c h 码 ( i ) q = 2 此时b c h 码的长为n = 2 2 + 2 + 1 = 7 ，取为如上的本原元，且在如s 上满 足的本原多项式为3 + + 1 ：0 ，q 为本原单位根，有q ：牟：牟：。 所以q 也满足0 1 3 + o t + l = 0 。设生成多项式g ( z ) = m l ( x ) ，则 i = o l ，q 2 ，o l 4 ) 故d e g g ( x ) = 3 ，由于q 满足q 3 + q + 1 = 0 ，由极小多项式的定义得 m 1 ( z ) = ( z q ) ( z q 2 ) ( z q 4 ) = i x 2 一( q + q 2 ) z + q 3 】( z q 4 ) = z 3 一( a + q 2 + q 4 ) z 2 + ( q 3 + o 5 + q 6 ) z q 7 因为q 3 + n + 1 = 0 ，得o l 3 = q + 1 ，所以上式 g=c(三1三1三0三1季0三0三0) 肚1 01110 0 ) 2 0 一些b c h 码的极小距离 ( i i ) q = 3 码长佗= q 2 + 口+ 1 = 1 3 ，取g ( x ) = z 3 + 2 x - t - 2 f 3 i x ，显然9 ( z ) 不可约， 并且 g ( x ) = z 1 3 1 x l o + z 8 + z 7 + z 6 + 2 x 5 + 2 x 4 + z 2 - t - 2 x 夕( z ) 的周期o ( 9 ( z ) ) 1 3 3 1 = 2 6 ，所以o ( 夕( z ) ) = 1 3 。故9 ( z ) 的根q 是1 3 阶本原单 位根，从而9 ( z ) = m 1 ( z ) ，所以在玛 z 】中取码c 的生成多项式g ( x ) = z 3 + 2 x + 2 给出三元b c h 码c = ( 9 ( z ) ) 的参数h ，k ，d 】，其中礼= 1 3 ，k = 1 0 ，生成矩阵为 g = 由于校验多项式 2 2 0100o 000 0 0o 0 2 2 010000 0 00 0 0 02 2010 0 0 o 00 0 o 002 2 0 10 0 oo0 0 00 0 0 2 2010 0 o o0 o 0 000 2 2010 0 00 o 00 00 02 2 0 10 00 0 0 000 002 20100 0 0 000 00 02 2010 0 0 o 0 0 00 o0 2 2 01 h ( x ) = ( z ”一1 ) g ( x ) = z l o + z 8 + z 7 + z 6 - i - 2 x 5 + 2 x 4 - + - z 2 + 2 x 肚1 01112 2 012 0 0 0 ) 2 1 一些b c h 码的极小距离 z 2 一z + 1 ，给出三元b c h 码c = ( 夕( z ) ) 的参数 t ，k ，司，其中n = 1 0 ，k = 6 ，生成 矩阵为 g = l 212100 0o0 01212100 o0 00121210 00 0o0121210 0 0000121210 00 0 0 012121 日=lf三1三1三0 0 三车0 三2 蚕2 薹0 0兰兰0) 2 2 一些b c h 码的极小距离 6 结论 本文主要讨论有限域r 上一些特定码长特殊的循环码的极小距离，通 过h a m m i n g 界来提高极小距离的下界，从而使之更接近真实值。首先证明了， 码长为n = 矿+ 口t - 1 + + q + 1 的循环码的极小距离为d = 3 或d = 4 。同时证 明了码长为死= q 2 + 1 的循环码的极小距离为d = 3 或d = 4 。码长为n = q 4 + 1 的 循环码的极小距离为d = 3 或d = 4 。因为在码的三个重要参数中，极小距离决 定了该码的检错和纠错能力。因而确定了循环码的极小距离，这将在译码过程 中发挥作用。特别地，当