（应用数学专业论文）具有确定极小距离的循环码的构造.pdf

学位论文独创性声明 本人承诺：所呈交的学位论文是本人在导师指导下所取得的研究成果。论文中除特别加以标注和 致谢的地方外，不包含他人和其他机构已经撰写或发表过的研究成果，其他同志的研究成果对本人的 启示和所提供的帮助，均已在论文中做了明确的声明并表示谢意。 学位论文作者签名： 学位论文版权的使用授权书 本学位论文作者完全了解辽宁师范大学有关保留、使用学位论文的规定，及学校有 权保留并向国家有关部门或机构送交复印件或磁盘，允许论文被查阅和借阅。本文授权 辽宁师范大学，可以将学位论文的全部或部分内容编入有关数据库并进行检索，可以采 用影印、缩印或扫描等复制手段保存、汇编学位论文，并且本人电子文档的内容和纸质 论文的内容相一致。 保密的学位论文在解密后使用本授权书。 学位论文作者签名：社指导教师签名： 签名日期： 亳觏 捌。年和班 r 辽宁师范大学硕士学位论文 摘要 本硕士论文分三部分： 第一部分：介绍剩余码的研究概述以及本文的主要工作 第二部分：给出本论文的一些预备知识，包括：循环码和原根的一些基本概念以及剩 余码的构造方法和基本特征。 第三部分：我们通过深入分析剩余码的特点，将剩余码的长度扩大，并利用z p t 及 z 2 口上原根的性质，构造了一类具有确定的码长，维数和极小距离的循环码。除此之 外，我们还利用码长的特殊性质构造了另一类具有确定的码长，维数和极小距离的循环 码。主要结果如下： 定理3 1 1 设p 是奇素数，q 是素数，且( p ，g ) = 1 ，口是c 的某个扩域中本原p 次单位根，又设卢是模p 的一个原根，令g ( x ) = n 竺；p 。 一口) ，则有 ( 1 ) g ( x ) ( 2 ) g ( x ) 一1 ，并且g ( x ) = x ，州一+ x p 锄，一+ + x + l ； ( 3 ) 在域上，由g ) 生成的循环码c = 的参数为 矿，p , - i , p 定理3 2 1 设p ，q 都是奇素数，g ( p ，q ) = 1 ，y 是的某个扩域中本原2 p 次单位 根，令口= y 2 ，则口是c 的某个扩域中本原p 次单位根，又设卢是模2 p 。的一个原根， 令g ( 工) = n ：p o 一( 一口) ) ，则有：( 1 ) g ( x ) = 兀：。o + 口) 乞【x ； ( 2 ) g ( x ) l 石+ 1 ，9 y f - i 了g ( x ) = x ，“( ，一一x p t - i ( ，一2 + x 。( ，一3 1 一一x ，。+ l ； ( 3 ) 在域上，由g ( x ) 生成的循环码c = ( g ( x ) ) 的参数为 2 ，p 卜1 0 一1 ) ，d p 定理3 3 1 设q 是一个素数幂，_ r q 3 ，e 是g f ( q ) i - _ - 长为刀= g 。+ 1 的循环码，其 生成多项式是g ( x ) = ( x ) ，则乞的参数为 g + 1 ，q + 1 2 t ，d ，- 其- d = 2 ，3 或4 定理3 3 4 设g 是一个素数幂，r q 4 ，e 是g f ( q ) 上长为刀= q 7 + 1 的循环码， 其生成多项式是g ( x ) = 聊。( x ) ，z l ( x ) ，则q 的参数为 q 7 + 1 ，9 7 2 t , 4 关键词：循环码：原根：最小距离 具有确定极小距离的循环码的构造 t h ec o n s t r u c t i o n so f c y c l i cc o d e sw i t hd e f i n i t em i n i m u m d i s t a n c e s a b s tr a c t w eh a v et h r e ep a r t smt h i sp a p e r ： t h ef i r s tp a r t ：w ei n t r o d u c es o m ek n o w nr e s u l t sa b o u tr e s i d u ec o d e sa n db c h c o d e s ，a n ds t a t et h em a i nc o n t r i b u t i o n si nt h i st h e s i s t h es e c o n dp a r t ：w eg i v es o m ep r e l i m i n a r i e s ；m a i n l yi n c l u d i n gs o m ec o n c e p t sa b o u t c y c l i cc o d e s ，p r i m i t i v er o o t sa n dt h em e t h o do fc o n s t r u c t i o nf o rr e s i d u ec o d e s t h et h i r dp a r t ：f i r s t l yw ee x t e n dt h el e n 【g t ho fr e s i d u ec o d e s ，a n dt h e nc o n s t r u c ta f a m i l y o fc y c l i cc o d e sw i t hd e f i n i t ep a r a m e t e r sb ya n a l y z i n gt h ec h a r a c t e r so fr e s i d u ec o d e sa n d u s i n gt h ep r i m i n t i v er o o t so fm o d u l op a n dm o d u l o2 p , w h e r epi s a l lo d dp r i m e s e c o n d l y , u n d e rt h ei n s p i r a t i o no fl i t e r a t u r e 2 3 ，w ec o n s t r u c ta n o t h e rf a m i l yo fc y c l i cc o d e s w i t hd e f i n i t e l e n g t h s ，d e f i n i t ed i m e n s i o n , a n dd e f i n i t e m i n i n l t m ld i s t a n c e s b yu s i n gt h e c h a r a c t e ro f t h ec o d e s sl e n g t l l t h ef o l l o w i n gs t a t e m e n t sa r et h em a i nr e s u l t s ： t h e o r e m3 1 1 ：l e t pb ea no d dp r i m e ，qb eap r i m en u m b e r , ( p ，q ) = 1 ，口b ea p r i m i t i v e ( p k ) ? r o o to fu n i t yo v e ra e x t e n d e df i e l do f ，l e t b eap r i m i t i v ef o o tm o d u l e p 。，s u p p o s eg ( z ) = 兀掣) ( z 一口卢i t h e n ( 1 ) g ( x ) 乞【x 】； ( 2 ) g ( x ) p 一1 , a n dg ( x ) = x ( ，卅) 十z ( 坤) ，h + + x d 一十1 ； ( 3 ) t h ep a r a m e t e r so f t h ec y c l i cc o d e sg e n e r a t e db yg ( 工) i s p ，p - i , p o v e r t h e o r e m3 2 1 ：l e t q , pb eo d dp r i m e s ，( p ，留) = 1 ，b eap r i m i t i v e ( 2 p ) 髓r o o to f u n i t yo v e rae x t e n d e df i e l do f ，l e t 口= y 2 ，t h e n 口i sap r i m i t i v e ( p ) 肪r o o to fu n i t y , s u p p o s e i sap r i m i t i v er 0 。tm o d u l e2 p ，g ( x ) = n 纠( x 一( 一口) ) ，t h e n ( 1 ) g ( x ) = 兀掣( 工+ 口卢) x 】： ( 2 ) g ( x ) l x p + 1 ，a n d g ( x ) = x p 叫9 一z p “1 ( p 。1 ) + x ，“1 【p 一引一一工p “1 + 1 ； 辽宁师范大学硕士学位论文 ( 3 ) t h ep a r a m e t e r s o ft h e c y c l i c c o d e s g e n e r a t e d b yg ( x ) 2 p k , p 扣1 ( p - 1 ) ，d p o v e l t h e o r e m3 3 1 ：l e tqb eap r i m ep o w e r , a n dq 3 ，cb eac y c l i cc o d ew i t ht h el e n g t h 刀= g + l ，w h o s eg e n e r a t o rp o l y n o m i a li sg ( x ) = 强( x ) ，t h e nt h ep a r a m e t e r s o fci s 阿+ w q + l - 2 t ，d ，w h e r e d = 2 ，3o r 4 t h e o r e m3 3 4 ：l e t qb eap r i m ep o w e r , a n dq24 ，cb eac y c l i cc o d ew i t ht h el c n g t h 疗= g + la n dg e n e r a t o rp o l y n o m i a lg ( x ) = ( x ) ，z l ( x ) ，t h e nt h ep a r a m e t e r so fci s g f + 1 ，q - 2 t ，4 1 k e yw o r d s ：c y c l i cc o d e s ；p r i m i t i v er o o t ；m i n i m u md i s t a n c e i i i 3 3 一类长度为g ，+ l 的循环码的极小距离的确定1 4 结j 沦2 0 参考文献21 攻读硕士学位期间发表学术论文情况2 3 致 射2 3 i v 辽宁师范大学硕士学位论文 1 引言 1 1 剩余码和b c h 码的研究概述 随着数字化通讯的广泛应用，信息传输方式的深入变革，人们对如何在传输中减少 差错、纠正传输中的错误的需求越来越迫切，这就令编码理论的研究有了非常重要的意 义。而循环码作为编码理论的基础部分也引起了诸学者的兴趣，循环码是一类重要的纠 错码目前各类数字通信系统以及计算机存贮和运算系统广泛利用纠错码来降低他们的 误码率，提高通信质量，延长计算机无故障运行时间等，所以循环码在编码理论的发展 中发挥着不可替代的作用循环码是由普朗格( e p r a n g e ) 于1 9 5 7 年首先在域g f ( q ) 上研 究的，后来，人们对循环码的研究在理论和实践方面都取得了很大进展，详见文献 1 7 】。 众所周知，码的长度、维数以及码的极小距离是线性码的最主要的参数。其中码的维数 确定了码的大小，极小距离确定了码的纠错能力进而，人们越发的关注如何构造好码这 一基本问题。域只上的二次剩余码是一类非常古老的循环码，人们对它的研究已经有三 十多年了，它是一类好码，并且在实际中得到了广泛应用。在文献 8 1 3 q 丁定义了域e 上 的二次剩余码，并讨论了二次剩余码的相关性质，文献 1 4 】还给出了一类二次剩余码的 解码方法，后来文献 1 5 】研究了域最上的三次剩余码的相应性质，文献 1 6 】又将域五推 广到环z 上，讨论了z i 上二次剩余码的性质，后来文献【1 7 1 8 】又将域e 扩充到域 ( g 为素数) 上，得到了二次剩余码和k ( k 3 ) 次剩余码，并研究了它们的相关性质。这类 码有确定的码长，维数和极小距离的下界本文是在此基础上，在域e 上，通过深入分 析剩余码的构造方法和基本特征，将剩余码的长度扩大，并利用z 。及z 。上原根的性质， ro p 构造了一类新的循环码这类码与剩余码相比有确定的码长，维数和极小距离。 b c h 循环码也是一类重要的纠错码。它的构造方法是由d k r a y - c h a u d h u r i 于1 9 6 0 年给出的，见文献 1 9 2 0 。近二十年来，随着有限域上编码理论发展日益成熟，人们逐 渐将研究目光转移到纠错码的检错和纠错能力的研究上来，特别是具有重大实用意义的 特殊纠错码即线性码和循环码的检错和纠错能力。当前应用广泛的纠错码是汉明码和 b c h 循环码，汉明码效率高，但仅能纠正一个差错。但是b c h 循环码却可以纠正任意多 个事先给定的差错，所以b c h 循环码具有更大的使用意义。而码的长度、维数以及码 的极小距离是线性码的最主要的参数。其中码的维数确定了码的大小，极小距离确定了 具有确定极小距离的循环码的构造 码的纠错能力，所以对循环码的极小距离的研究成了许多学者的一个重要课题。然而计 算循环码的极小距离却是一件比较困难的工作，通常只能用b c h 界或者一些较好的界 去刻画它的下界。如何提高极小距离的下界使之更接近真实值，一直是人们感兴趣的问 题。文献 2 1 1 对前人的工作做了比较系统的引用和发挥，通过研究生成多项式的零点与 极小距离的关系，用矩阵积的方法和“移位”法对几乎所有的n 6 3 ( 以为码长) 的二元 循环码的极小距离做了界定，文献 2 2 1 用另外的方法解决了文献 2 1 d p 没有完成的两个 特例；1 9 7 0 年，c h c h e n 在计算机上对一些以6 5 的二元循环码做了处理，算出了它们 的极小距离，详见文献 2 3 】同年，文献 2 4 】讨论了一类自反循环码，在理论上为确定它们 的极小距离找到了一些可利用的条件，并得到了一些结果。后来文献 2 5 】将研究对象投向 了另一种循环码，围绕生成多项式的零点、码长、极小距离和b c h 界进行讨论，得到 了使循环码的极小距离等于其b c h 界的两个充要条件。接着文献 2 6 】又研究了码长是 刀= 9 2 一g + 1 的g 元循环码的极小距离( 其中g 4 ) 。本文是在文献 2 6 】的启发下，将研究对 象投向另一类循环码，利用码长的特殊性质，构造了一类具有确定极小距离的循环码。 1 2 本文的主要工作 本硕士论文分三部分： 第一部分：介绍两类循环码( 剩余码和b c h 码) 的研究概述以及本文的主要工作。 第二部分：给出本论文的一些预备知识，主要包括：循环码和原根的一些基本概念以 及剩余码的构造方法和基本特征。 第三部分：首先我们通过深入分析剩余码的特点，将剩余码的长度扩大，并利用z p i 及z 2 ，上原根的性质，构造了一类具有确定的的码长，维数和极小距离的循环码。除此 之外，我们还利用码长的特殊性质，构造了另一类具有确定的码长，维数和极小距离的 循环码。主要结果如下： 定理3 1 1 设p 是奇素数，g 是素数，且( p ，g ) = l ，口是的某个扩域中本原p 次 单位根，又设夕是模p 的一个原根，令g ( z ) = n g ( x 一口) ，则有 ( 1 ) g ( x ) 【司； ( 2 ) g ( z ) i x 广1 ，并且g ( z ) = x ( ，。1 ) + o p 缈+ + + 1 ； ( 3 ) 在域上，由g ( x ) 生成的循环码c = ( g ( x ) ) 的参数为 p ，p h ，p 定理3 2 1 设p ，g 都是奇素数，且( p ，g ) = 1 ，是的某个扩域中本原2 p 次单位 2 辽宁师范大学硕士学位论文 定理3 2 1 设p ，g 都是奇素数，j l ( p ，g ) = l ，y 是乞的某个扩域中本原2 p 次单位 根，令口= ) ，2 ，则口是c 的某个扩域中本原p 次单位根，又设卢是模2 p 的一个原根， 令g ( x ) = n 纠( x - ( - a ) ) ，则有 ( 1 ) g ( x ) = 兀掣( 石+ 口) x ； ( 2 ) g ( x ) + 1 ，并且g ( x = _ x p - i ( p - 1 ) - - x ，h 坤+ x p - ( p - 3 ) 一x ，扣1 + 1 ； ( 3 ) 在域上，由g ( x ) 生成的循环码c = ( g ( x ) ) 的参数为 2 p ，p ( p - 1 ) ，d p 定理3 3 1 设g 是一个素数幂，且g 3 ，e 是g f ( q ) 上长为刀= g r + 1 的循环码， 其生成多项式是g ( x ) = ，z l ( x ) ，则q 的参数为 g + 1 ，q + 1 2 t ，d ，其中d = 2 ，3 或4 定理3 3 2i r q 是一个素数幂，如果g 3 是偶数，则由g ( x ) = m a ( x ) 生成的长度为 栉= 矿+ 1 的循环码的参数为i 矿+ 1 ，q 7 - 2 t ，di ，其中d = 3 或4 定理3 3 3 定理3 3 1 中的c 上长度为刀，生成多项式为g ( x ) = 历。( x ) 的码c 的对偶 码c 上的参数为q 。+ l ，2 t ，d ，其中d 9 7 2 q h + 1 定理3 3 4 设q 是一个素数幂，且g 4 ，e 是g f ( q ) 上长为刀= 矿+ 1 的循环码， 其生成多项式是g ( x ) = ，z 。( 工) 惕( x ) ，则乞的参数为 矿+ 1 ，矿一2 t ，4 定理3 3 5 定理3 3 4 中的c 上长度为万，生成多项式为g ( x ) = m 。( 工) ( 工) 的码c 的对偶码c 上的参数为9 7 + 1 ，2 t ，d ，其中d g 。一2 q h + 1 具有确定极小距离的循环码的构造 2 预备知识 2 1 循环码及原根的基本 = i c 忿性质 定义2 1 7 1 巧表示有限域上的甩维向量空间。碍的每个非空子集合c 都叫做一 个g 元码，l 叫做该码的码长，c 中向量叫做码字。用k 表示c 中码字的个数，即k = l c i 。 k = l o g 。k 叫做码c 的维数。 定义2 2 【7 1 设三= a 。，a ：，吒) ，苫= ( 6 l ，吃，瓯) 是巧中的两个向量，则向量艺的 h a n n i n g 权定义为非零分量的个数，表示成( 三) ，即 ) = 撑 f 1 1 f ，z ，。 。 而向量口和b之间的hamming距离是指它们相异位的个数，表示成di口，b-i,i ，即 _，- + _ + 、 d ( 三，苫) = 撑 z i z 栉，口，岛) = 国( 三一苫) 定义2 3 纠设c 是码长为刀的g 元码( 即c 是巧的非空子集合) ，k = l c l - 2 ，定义 c 的最小距离为不同码字之间h a m m i n g 距离的最小值，表示成d ( c ) ，即 捌( c ) = 凼”c 。1 ) 降c - 0c 4 i ) 定理2 4 【7 】如果存在g 元码( 咒，k ，d ) ，1 d 甩一1 ，则k g 州“，即d 6 ，只需证明日的任意6 1 列都是乞。线性无关的，取日中任意艿一1 ，给出 6 1 歹4 方阵m = 岛7 卢咖1 ) ( 1 + a - 2 ) p 如( “6 2 )讪( “占一2 ) ( o i 2 珐一l n - 1 ) 我们要证它的行列式d e t m 必不等于零，由于d e t m = ( 坞“嘞y ，而，珞一- 彼此 不同且均不为零，上式右边的行列式是v a n d e r m o n d e 行列式，从而也不为零，因此 d e t m 0 ，这就证明了d 艿 定义2 1 2 t 冽设r 是有单位元的环，则r 的可逆元的全体作成的群称为r 的乘群或 单位群，用u ( r ) 表示 定义2 1 3 2 7 设聊1 ，a ，m ) = 1 ，使得口4 = l ( m o d m ) 成立的最小正整数d 称为口对 模m 的指数( 或阶) ，记为屯( a ) 定义2 1 4 【2 7 】当民( 口) = 驴( ，z ) 时，称口是模朋的原根 定理2 1 5 ”】模所有原根的充要条件是研= 1 , 2 ，4 ，p k2 p ，其中p 是奇素数，k 1 由上述定理可知当p 为素数时，p 2 有原根；当p 为奇素数时，p 。有原根，k 1 定理2 1 6 m 在环z ，。中，l u ( z p 。) l = 驴( p ) = p 扣1 ( p 一1 ) ，其中p 为素数 定理2 1 7 2 7 1 ( 欧拉定理) 若( p ，g ) = 1 ，则可，- - - l ( m o d p ) d 埘 哪 卅 抄肌 肌 ， + ， 舻胁；胁 “ 舡 胪 辽宁师范大学硕士学位论文 2 2 剩余码的构造及王要性质 定义2 18 2 7 】若对某一素数p ，存在有一个整数x ，使下式成立工2 - i ( m o dp 1 则称f 是模p 的二次剩余；否则称为模p 的非二次剩余 定理2 1 9 2 7 若p 是奇素数，则在l 5 5 p - 1 的所有整数中，有( 字) 2 个是模p 的二 次剩余，有( 字卜是模p 的非二次剩余 证明：这只要证明满足1 2 ，2 2 ，( 孚 2 的模p 二次剩余的每一个均不相同即可用 反证法若对一个f ，f 1 ，f ，p ，、- 1 有相同的二次剩余：即 i 2 - j 2 ( m o d p ) ，i 2 - j 2 = ( f + j f ) ( f 一) 基o ( m o d p ) ，由于p 是素数，模p 的剩余类是 一个域，域中无零因子，所以，由上式可得f + 兰。或f 一_ ，暑o ( m 。d p ) 由t i 1 ，芝 ， 故f + o ，所以只有f 一歹兰o ( m o d p ) 即浯( m o d p ) ，又因为f ，芝：，所以这意味着 f = 歹，与假设i ，相矛盾。因此，满足1 2 ，2 2 ，( 孚) 2 的模p 二次剩余中的每个均不同， 这说明在l ，2 ，p 一1 中只有三个不同的二次剩余，其余的暑个为非二次剩余 模p 的二次剩余有以下性质： ( 1 ) 两个二次剩余的积，或两个非二次剩余的积仍是二次剩余。一个二次剩余与另一 个非二次剩余之积是非二次剩余 ( 2 ) 若p = 8 m + l ，则2 是模p 的二次剩余。若p = 4 历+ 1 ，贝l j - 1 = - ( p - 1 ) ( m o d p ) 是g - ：a p 的二次剩余；若p = 4 m - 1 ，则- 1 是模p 的非二次剩余 g f ( q ) 上码长为素数p 的二次剩余码，其中q 是模p 的二次剩余，且为素数。x 寸7 ：- - 进制鲫码来说9 2 2 ，因而由性质( 2 ) 可知，码长为p = 8 m + l 的形式 令q 表示模p 的二次剩余集合，n 表示模p 的非二次剩余集合 具有确定极小距离的循环码的构造 x p - - 1 在扩域g f ( p ”) 的p 阶根为口，a ，口2 ，o l p - io p = 1 都是x p 一1 的方程的根所以 我们有 x p 一1 = ( x 一1 ) ( 工一口) ( j 一口2 ) ( x 一扩1 ) = ( x 一1 ) g ( z ) 甩( z ) 式中 g ( x ) = 兀( x a ) 刀( x ) = 兀x - - a ) 是系数在g f ( g ) 上的多项式 定义2 2 0 2 7 l 由下列多项式g ( x ) ，( x 一1 ) g ( x ) ，胛( x ) ，( x - o n ( x ) 生成的码，称为g f ( q 1 上的二次剩余码 定义2 2 1 18 】如果在有限域疋中，方程三g ( m o d p ) 有解，则称g 是模p 的一个七次 剩余 定理2 2 2 1 8 1g 是模p 的一个七次剩余的充要条件是曰t - - l ( m o d p ) 定理2 2 3 1 8 】设p ，g 是两个不同素数，_ k q 是模p 的足次剩余，卢是中的一个本原 元素， 口是乞的某个扩域中的一个本原p 次单位根， 令 吩= p ( m 咖) p 竿) ，咖) = n 小卅) ，倒凡2 ，矗一。则 g j ( z ) h ，且x p l = ( x - 1 ) g 。( _ x ) g 。( x ) g h ( x ) 定义2 2 4 1 8 1 c 上长度为p 的由g o ( x ) ，g ，( x ) ，g ：( x ) 。一。( x ) 生成的循环码称为七次 剩余码 定理2 2 5 1 明c 上由g o ( x ) ，g 。( x ) ，繇一。( x ) 生成的循环码相互等价如果c ( x ) 是j i 次剩余码 中的一个码字且c ( 1 ) 0 ，( c ) = d ，则d ：p 辽宁师范大学硕士学位论文 3 具有确定极小距离的循环码的构造 3 1 参数为 p k , p k - i ) p j 的循环码的构造 以下设是乙。的一个原根，u ( 乙。) = i _ ，万2 ，万矿弋p 9 ，因为( p ，g ) = 1 ，所以 ( p ，g ) = l ，由欧拉定理知g 烈p ) 暑l ( m o d p ) ，所以0 。，中存在p 次本原单位根，设a 是 的某个扩域( 例如乞，) 中本原p 次单位根，令g ( 工) = n 墨：，( z 一位卢) 定理3 1 1 设p 是奇素数，g 是素数，且( p ，g ) = 1 ，口是的某个扩域中本原p 。次 单位根，又设卢是模p 。的一个原根，令g ( 工) = 兀兰：，( 工一口) ，则有 ( 1 ) g ( x ) e f q x 】； ( 2 ) g ( 工) 矿一1 ，并且g ( x ) = x ，卅+ 少2 + + x p k - i r - ， ( 3 ) 在域上，r ag ( x ) 生成的循环码c = 的参数为 ，p k - i , p 证明 ( 1 ) 因( p ，g ) = 1 ，所以( p ，g ) = l ，q e u ( z 。) ，故存在正整数，l - ，( p ) ，使 得卢- q ( m o d p ) ，设q = f 1 7 + p ，l e z ，则对任意l f 驴( p ) ，因为口的阶为p ，有 ( a ) 9 = ( a ) 外一= a ( 口p ) 肌= a 所以( 口) 9 = a 当z + 歹妒( p ) 时，( 口) 9 是 g ( x ) 的根；f + 驴( p ) 时，令f + _ ，= 妒( p ) s 卜，o f ( p ) ，则 州：“，p ：卢“矿卜p r ，但是p “，) 三l ( m 。d p ) ，所以卢峨) 5 三1 ( m o d p ) ，设 卢“川s ：1 + a ，口z ，则口：( 倪州，p 丫：( o l l + p t a ) ：( a 叔p 口) ：( a 1p = t x p 综上 所述，当口是g ( x ) 的一个根时，( 口卢丁也是g ( x ) 的一个根，因此g ( x ) 【x 】。 ( 2 ) 首先说明g ( x ) 无重根，倘若p ki 7 一卢7 = 卢。( 卢一一1 ) ， 不妨设 l i j ( 矿) ，则矿l 卢7 一卢= 卢( 声一一1 ) ，所以p 。i 卢一一1 ，即卢一- l ( m o d p ) ，则 9 具有确定极小距离的循环码的构造 ( ) 陟一f ，因此_ ，= f ，与f 矛盾，所以g ( x ) 无重根 其次，又因为对g ( x ) 的每个根口，1 f ( p ) ，都有( 口卢7 ) = ( a 矿) = 1 ，所以 口也是x 一1 的根，则有g ( z ) k 一1 因为p k = p k - - i p ，所以x 一1 = ( x 一1 ) ( x p _ l + o p 2 旷1 + + 石p k - i + 1 ) 而 a l ，口2 ，口p ，口，a ，”，口幻，口2 p + i ，a ( p t q _ 1 ) p ，a p ，a p 是x 一1 的全部零点，显然 口p ，口幻，口( ，。1 - 1 p ，口p 是x p “一1 的p k - 1 个零点，即全部零点，那么其余p t p “：( p t ) 个p 次单位根则是| ，一1 ) p 卜1 + x ( ，一2 ) p “+ + z p 扣1 + 1 的全部零点， 所以 g ( x ) = x t p 一1 ) p “+ x ( p 一2 ) 矿一+ + z p 扣1 + 1 ( 3 ) 首先证明d p 令c - ，显然c 的长度为p ， 维数为 p 一驴( p ) = p 一p k - 1 ( p 一1 ) = p 扣1 因为p 为奇素数，所以对任意l i 是长度为p 2 ，维数为p ，极小距离d = p 的循环码 例3 1 2 若p = 2 ，q = 3 ，k = 2 ，则z 2 ：= 石，i ，芝，) ，u ( z 2 ：) = i ，) ，n s b3 = 2 ，所 u ( z 2 ：) = j ，5 2 = 1 ) ，设口是e 的扩域乞：的一个4 次本原单位根，根据定理3 1 1 有 g ( x ) = ( x a ) ( x a 3 ) = x 2 + 1 只【x ；g ( x ) i x 4 一l ，且c = 是参数为 2 2 ，2 ，2 的 循环码，实际上显然c 的长度为4 ，维数为4 2 = 2 ，又校验多项式为 办( x ) = x 4 一l x 2 + 1 = x 2 一l ，校验矩阵为且= ( 三：苫。1 ，所以d 等于2 ，即c 是 l o 辽宁师范大学硕士学位论文 4 ，2 ，2 】码 例3 1 3 若p = 3 ，q = 2 ，k = 2 ，则z 3 ：= 石，i ，吞) ，u ( z 3 ：) = i ，芝，互，；，可，吞) ， 因为周= 6 ，所以u ( z 3 ：) = 芝，乏2 ，乏3 ，芝4 ，歹，芝6 ，设口是互的扩域e 。的一个9 次本原 单位根，根据定理3 1 1 有 g ( x ) = ( x 一口) ( j 一口2 ( x - - 0 1 4 ) ( 工一口5 ) ( x 一口7 ( x - a 8 - - - - x 6 + x 3 + 1 互h ， g ( x ) i x 9 1 ，c = 是参数为 3 2 ，3 ，3 的循环码。事实上，显然c 的长度为9 ，维数 为9 - 6 = 3 ，又校验多项式为五( z ) = ( x 一口。) ( x 一口3 ) ( x 一口6 - - x , - 1 所以校验矩阵为日= = ( u j u 2 u 3 u 4 u 5 u 6 u 7 蚝u 9 ) h 中任何两列线性无关， 且一3 - - - - - - 一6 一- - - t ，根据定理2 7 得d = 3 1 l j c 是 9 ，3 ，3 】码 3 2 参数为 2 p ，p 卜1 ( p - 1 ) ，d p 的循环码的构造 定理3 2 1 设p ，g 是奇素数，且( p ，g ) = 1 ，y 是的某个扩域中本原2 次单位根， 令口2 y 2 ，则口是乞的某个扩域中本原p 次单位根，又设卢是模2 p 的一个原根，令 g ( x ) = 兀纠( x 一( 一口) 雕) ，则有 ( 1 ) g ( 石) x 】j | - g ( x ) = 兀掣( x + 口) ； ( 2 ) g ( x ) p + 1 ，并且g ( x ) = 4 ( 川) 一x p h ( 坤) + x p ( p 圳一一x + l ； ( 3 ) 在域上，由g ( x ) 生成的循环码c = 的参数为 2 p ，p 卜1 ( p 一1 ) ，d ，j p 证明 0 o 0 0 o o o o 0 o o 0 o 0 o o 0 o o 0 0 0 o 1 o o o 0 l 0 o 0 0 o o o o l o o o 0 1 o 0 0 o 1 n u d d d d 具有确定极小距离的循环码的构造 ( 1 ) 因为p 9 ( 2 矿) 暑1 ( m o d p 。) p 叫，) 三l ( m 。d p ) 且卢是奇素数，所以 卢( 1 f 矽( 2 p ) ) 是奇数，x 刚( 2 p ) = 驴( p 。) ，则有g ( x ) = n 墨：，( x + 口) 接下来证明g ( x ) x 】。因为( p ，g ) = 1 ，( 2 ，g ) = 1 ，所以( 2 p ，g ) = 1 ，即 q e u ( z 2 ，) ，故存在正整数，1 妒( 2 p 。) ，使得7 暑q ( m o d 2 p ) 设 g = 夕+ 2 p ，l z ，则对任意1 f 驴( 2 p ) ，由l - a l = l l - l l ，l 口口= 2 ，p = 2 p k , 且卢是奇 素数得 - - t z # ) 9 = ( 一口f f q = ( 一a ) ( 删f ) _ ( 川) ( ( 一口) 2 p ) f i l l = ( 一口p t + j = 川 当f + j 驴( p ) 时，令f + 歹= ( p ) s + f ，其中o f 矽( p ) ，则卢州= 卢9 ( 矿) 州= 妒( p p p 7 ， 但是卢( 矿) = l ( m o d p ) ，所以卢9 ( 矿p - - l ( m o d p ) ，设p 9 ( 矿p = l + p 口，口z ， 则一口卢卅：一口矿，：一( a ，n ) ：一( a l + p a ) f l ：一( 口口，a ) ：一( 口1 ) ：一a 这说明，当一口是g ( x ) 的一个根时，( - a ) e 也是g ( x ) 的一个根，因此 g ( x ) e f j x ( 2 ) 首先证明g ( x ) 无重根若卢卢。( m o d 2 p 。) ，不妨设1 f ( 2 p ) ，则 2 p i 7 一声，即2 p i 卢( 卢7 一一1 ) ，所以2 p 。l ( 卢7 一一1 ) ，即p 7 一三l ( m o d 2 p ) ，则 ( 2 矿) i j - i ，因此江，与f 0 ) 例3 2 2 若p = 3 , q = 5 ，k = 2 ，x 埔一1 = ( x 9 1 x x 3 + 1 ) ( x 6 一x 3 + 1 ) ，g ( 工) = x 6 一x 3 + l ， 由定理3 2 知由g ( x ) 生成的循环码参数为 1 8 ，1 2 ，d 3 】，事实上，校验多项式 h ( x ) = ( x 9 一1 ) ( x 3 + 1 ) = x 1 2 + x 9 一x 3 1 ，校验矩阵为 h = 显然第1 列与第1 0 列线性相关，所以d = 2 _ 3 ，q 是上长为咒= 矿+ 1 的循环码，其生成 多项式是g ( 工) = ，1 1 ( x ) ，则q 的参数为 矿+ 1 ，q + 1 - 2 t ，d ，其中d = 2 ，3 或4 证明首先我们考虑g ( x ) 的所有零点，因为疗i q 2 卜1 ，所以口0 ，且 ，= 口，口g ，口，= 口- 1 , t z 一，a _ q l _ 1 ) ， 为1 1 1 = 2 t ，则c 的维数k = g + 1 2 t 接下来我们考虑码的极小距离，由定理2 4 我们可知d 拧一k + l = 2 t + 1 更进一步，我们能够证明d 4 假设d 5 ，由定理2 5 可知 g 一。1 + 珂( g 一1 ) + 竺尘芸二尘( g 一1 ) z g 一一l + ( g r + 1 ) ( g 一1 ) + 掣( g 一1 ) 2 了q n - k 一1 ( g r + 1 ) + 皇名二旦( g 一1 ) 口一1 z _ q 2 tm 1 ( g r + 1 ) + 煎掣( q - 1 ) c l 1 2 整理得9 2 “+ 9 2 ，_ 2 + + g + 1 m q t - - 1 掣( g 一1 ) 一 两边同时除以g