（基础数学专业论文）关于准循环码的结构及其一些性质.pdf

学位论文独创性声明 本人所呈交的学位论文是我在导师的指导下进行的研究工作及取 得的研究成果据我所知，除文中已经注明引用的内容外，本论文不包 含其他个人已经发表或撰写过的研究成果对本文的研究做出重要贡献 的个人和集体，均已在文中作了明确说明并表示谢意 作者签名： 学位论文授权使用声明 本人完全了解华东师范大学有关保留、使用学位论文的规定，学校 有权保留学位论文并向国家主管部门或其指定机构送交论文的电子版 和纸质版有权将学位论文用于非赢利目的的少量复制并允许论文进入 学校图书馆被查阅有权将学位论文的内容编入有关数据库进行检索 有权将学位论文的标题和摘要汇编出版保密的学位论文在解密后适用 本规定 学位论文作者签名：有罗f 冕 导师签名：p 吾乏互 摘要 本文首先介绍了纠错码、循环码的基本知识和些结果，讨论了准循环码的结构， 即可以把准循环码看作r 旧 模f k l 的子模，然后我们给出了 文【2 】两个结果的具体证明，并且计算了四个准循环码接下来我们讨论了准循环码的一些 性质，包括一个生成元生成的准循环码和多个生成元生成的准循环码的关系，即在一定 的条件下多个生成元生成的准循环码实际上等价于一个生成元生成的准循环码，之后我 们讨论了某些两个生成元生成的准循环码的维数接着我们对某些准循环码的最小距离 傲了估计最后我们计算了两个生成元生成准循环码的维数和最小距离 关键词：循环码，准循环码，维数，最小距离 a b s t r a c t i nt h i st h e s i s ，w ef i r s ti n t r o d u c et h eb a s i ck n o w l e d g ea n ds o m er e s u l t 3o fe r r o r - c o r r e c t i n gc o d e sa n dc y c l i cc o d e s w ed i s c u s st h es t r u c t u r eo fq u a s i c y c l i cc o d e s r e g a r d i n g t h e ma s f q i x 一s u b m o d u l e s o f f k 】 n e x t w e g i v e t h e d e t a i l e d p r o o fo ft w or e s u l t si nr e f e r e n c ef 2 】 a n dc a l c u l a t ef o u rq u a s i e y c l i cc o d e s a h e rt h a tw e d i s c u s ss o m ep r o p e r t i e so fq u a s i c y c l i cc o d e s ，i n c l u d i n gt h er e l a t i o nb e t w e e n1 - g e n e r a t o r q u a s i c y c l i ec o d e sa n dm u l t i - g e n e r a t o rq u a a i c y e l i cc o d e s ，i e ，s e v e r a lm u l t i - g e n e r a t o rq u a s i - c y c l i cc o d e sa r ee q u i v a l e n tt oc e r t a i n1 - g e n e r a t o rq u a s i c y c l i ec o d e su n d e rs o m ec o n d i t i o n s w ec a l c u l a t et h ed i m e n s i o no f2 - g e n e r a t o r sq u a s i c y c l i cc o d e sa f t e r w a r d s a f t e rt h a tw e e s t i m a t et h em i n i m u md i s t a n c eo fq u a s i c y e l i cc o d e s f i n a l l y , w eg i v es o m ee x a m p l 髑o f t w oq u a s i c y c l i cc o d e so f2 - g e n e r a t o m k e y w o r d s ：c y c l i cc o d e s ，q u a s i c y c l i ec o d e s ，d i m e n s i o n ，m i n i m u md i s t a n c e 2 第一章引言和以前的结果 第一节引言及主要工作 1 1 引言 1 9 4 8 年s h a n n o n 发表通信的数学理论一文，奠定了通信的数学基础信息论 和通信的可靠性理论【9 1 通信系统的最简单模型可以表示成： 发方( x ) - - l 收方( y ) 发送方把信息x 传给接收方，但是在信道传输过程中出现错误( 或干扰) e ，从而收方收到的 是y = x + e 我们希望有一种办法，使收方在得到y 之卮有能力检查是否有错并且在 有错( 即e o ) 的情况下，决定出错误e ，从而得到所传送的正确信息x = y e ( 纠错) ，这 需要纠错编码 1 2 编码及译码 分组编码的第一步是把这些信息分成长度为的组【1 5 】：( n l ，o 2 ，口) ，( n k + 1 ，8 k + 2 ， ，2 ) ，然后对每组k 个符号a = ( a l ，0 2 ，o k ) 进行处理( 编码) ，得到一个向 量( 码字) c = ( c l ，q ，靠) ，n 七，为了纠错，我们添加了n 一七个冗余位信息向 量a = ( d l ，a 2 ，n k ) 按下列方法得到一个向量( 码字) c = ( c l ，c 2 ，c ，i ) = ( a t ，o 2 ，a k ) g 这里 g = f f l l9 1 2 9 l n 9 2 19 2 2 肋 9 k l 鲰2 一吼n 是一个秩为k 的矩阵( 生成矩阵) 现在通过有干扰的信道，用向量c 代替a 传送到接收 3 方，如果接收方接收到没有差错的向量c = ( c 1 ，c 2 ，岛) ，那么他可以通过解下列线性方 程组 g n a l + 9 2 1 0 a + + g k l a k = c l 夕1 2 n 1 + 虫2 眈+ + 鲰2 2q ( 2 ) g l n i 1 + 啦n n 2 + + 钆= 得到信息向量( o l ，0 , 2 ，钒) 因为g 的秩是七，上面的线性方程组有惟一的解，可是这个 信道有干扰，接收到的向量y = ( y l ，抛，) 可能不等于发送的向量c ，那么接收方必须 从接收向量y 决定发送向量( 码字) c 是什么，然后还原成信息向量a ，这个过程就是译码 他可以按这样的准则从y 决定c ：在由g 生成的向量空间( 线性码) 中选择这样的c ， 使得y 和c 之间的相异位的个数最j , ( 1 1 0 y c 的h a m m i n g 重量最小) ，这个译码准则称为极 大似然译码准则假定在信道中，对任何发送的向量b z ( b 1 ，b 2 ，k ) ，最多有t 个符号可 能发生差错，则y 和c 的相异位的个数小于t ( 即y c 的h a m m i n g 重；l t ) 如果在由g 生 成的向量空间( 线性码) 中，任意两个向量的相异位的个数不小于孔+ 1 ( 即线性码的最小 距离d 2 t + 1 ) ，那么在由g 生成的向量空问中，存在且仅存在一个向量c ，使得y 和c 的 相异位的个数小于t 这是因为，对任意接收向量y ，如果有c l c 2 ，使得y 和c l 的相异位 的个数小于t ，且y 和。2 的相异位的个位数小于t ，因为c 1 ，。2 的相异位的个数不大于 。l ，y 相异位的个数与c 2 ，y 相异位的个数之和2 t ，所以。l 和c 2 帽异位的个数不大于盘这 与我们的假设向量空间( 线性码) 中任意两个向量的相异位的个数不小于2 t + 1 矛盾这 样接收方就把y 译成c ，然后通过解线性方程组( 2 ) 惟一地确定被传送的信息向量a 1 3 准循环码当前的研究现状的概述 准循环码是循环码的自然推广【1 1 利用g r 砌l e r 基理论( 【1 6 d 作为工具讨论了准循环 码的代数结构【2 】把准循环码看成f q m 模f p l 的子模，研究了 一个生成元和多个生成元的准循环码的维数和最小距离1 3 1 引入了线性空间的准循环子 4 空间的概念，进而研究了准循环码与准循环子空问的关系，给出了准循环码的准循环子空 间的表示定理【4 】得到七个新的二元线性码s l i n g 和p 8 0 1 4 把域上的准循环码看成是 环f m ，然后通过中国剩余定理( 【19 】) 等把环f n 分解，从而把 域上的准循环码看成是码长较短的码的直和，刻画和列举了自对偶的一个生成元生成的 准循环码，并且推广到对多个生成元生成的准循环码的刻画( 【5 】，【6 】，【7 】，【8 】) 这些工作大部 分对一个生成元生成的准循环码做了深入的研究，但对多个生成元生成的准循环码的研 究涉及较少 1 4 本文的主要工作 本文在第一章介绍了纠错码、循环码的基本知识和一些结果( 【9 | 一【1 5 】，【1 8 j ) ，然后讨论 了准循环码的结构及已有的一些结论( 【1 卜i s ) 在第二章第一节中，我们给出了【2 】的两个结 果的具体证明，并且计算了四个准循环码，在第二章第二节中，我们讨论了准循环码的一 些性质：其中性质2 2 1 是循环码的结果的推广：在性质2 2 2 中讨论了一个生成元生成的 准循环码和多个生成元生成的准循环码的关系，即当 ( 。) ，厶( z ) e f 。i x 时，由这些生 成元生成的准循环码是一个生成元生成的准循环码：在性质2 2 3 中讨论了某些两个生成 元生成的准循环码的维数；在性质2 2 4 ，性质2 2 5 和性质2 2 6 ，我们对某些准循环码的最 小距离作了估计最后我们计算了两个都是两个生成元生成准循环码的维数和最小距 离，验证了我们在性质2 2 6 中对准循环码的最小距离估计的结果 第二节纠错码的定义和以前的结果 在本节，我们给出纠错码、h a m m i n g ：重：m 、最小距离和生成矩阵等概念及其一些定 理，主要参考文献是【9 卜p 3 ，【1 5 j ，【17 】，1 1 8 1 定义1 2 1 设f 口是具有q 个元素的有限域，其中g 是一个素数的幂e 表示有限 域f 。上的n 维线性空间，f ；的每个非空子集c 都叫做一个口元码，n 叫做码的码长，e 中的 5 向量叫做码字，k = l e l 为码字的个数，k = l q 岛叫做码字的信息位数，七加叫做码的信 息率 定义1 2 2 设a = ( n 1 ，n 2 ，) 和b = ( b l ，b 2 ，k ) 是f ；中的两个向量，则向 量a 的h 彻姗妇g 重量定义为非零分量a i 的个数，表示成“橱( a ) ，即 u 日( a ) = 4 0 1 1 i n ，a i o 而向量a 和b 之间的h 锄m i n g 距离是指它们相异位的个数，表示成妇b ) ，即 d 日( a ，b ) = 1 1 1 i n ，n 以) = 阳( a b ) 以后“憎( a ) 和d h ( a ，b ) 简记为u ( a ) 和d ( a ，b ) 容易证明：h a n l m i n g 距离满足数学上“距离”所应具备的以下三条性质：对任给 的a ，b ，c e ， ( 1 ) d ( a ，b ) 0 ，g d ( a , b ) = 0 骨a = b ， ( 2 ) d ( a ，b ) = a ( b ，a ) ， ( 3 ) d ( a ，c ) d ( a ，b ) + d ( b ，c ) 定义1 2 3 设e 是一个g 元码，则码c 的最小距离为g 中不同码字之间h a m m i n g 距离的最小值，表示为d ( c ) ，即 d ( c ) = m i n d ( a ，b ) l a ，b c ，a b ) 显然，0 d ( c ) n 定义1 2 4 f q 上的线性码e 是线性空问f ；中的一个子空间，如果这个线性子空问 的维数是七，最小距离是d ，则称e 是一个i n ，d 】码 以后用h ，k ，d 】表示一个码长为礼，维数为屉，最小距离为d 的线性码， 对于一个h ，后，司线性码c ，可以利用线性代数作为工具，取c 的一组基 v l ，v 2 ， v k ，v t = ( 吼1 ，甄2 ，9 机) ，( 1 i 七) ，其中e f q ( 1si k ，1 j ，1 ) 则每个码字可 惟一表示成 c = 6 1 v 1 + b 2 v 2 + + b k v k = ( 6 1 ，6 2 ，一 6 k ) g 6 其中6 l ，b 2 ，k f 日，g 是b 上秩为抛q 是n 矩阵， g = v l v 2 ： v k g a l9 1 2 g i n 9 2 19 9 2 f i g k lg 轮9 h g 叫做线性码c 的一个生成矩阵，我们再考虑g 的解空间湿然解空问的维数为n k 。 设恤l ，h 2 ，h 。- k ，h i = ( m 1 ，h i 2 ，k ) ，e f 口，1 i n k ，1 j n 是解空间 的一组基，则对c = ( c l ，c 2 ，岛) e 有 ( c l ，也，岛) c 乍= h 1 1 h i 2 h h 2 1h 2 2 k k 一1k k , 2 k k m c l c 2 ： 岛 = 0 一个一詹) n 矩阵日称为线性码c 的奇偶校验矩阵，如果 c e 车号日c r = 0 对于线性码，我们有以下基本性质： 定理1 2 1 设c 是f 口上码长为扎，维数为k 的线性码，日是它的奇偶校验矩阵，如 果日的任何( d 1 ) 列都线性无关，那么码c 的最小距离至少是d 进一步，如果存在d 列线 性相关，那么码e 的最小距离等于d 通过下面的定理，我们知道线性码的最小距离，它反映了码的纠错能力 定理1 2 2 设e 是一州n ，d 】线性码，则此码可检查f i t d 一1 位错误，也可纠 正【等】位错误对于实数n ，【j 表示不超过n 的最大整数 纠错码数学理论的最基本研究对象有如下两个：一是拇造性能良好的纠错码，即要求 效率k n 和反映纠错能力的d n 愈大愈好一是寻求好的译码算法但是线性码c 的三个 7 参数：码长7 l ，维数k ，最小距离d 是相互约制的，即一个h 尼，司线性码c 的参数之间满足 某些不等式，叫做纠错码的界 定理1 2 3 ( s i n g l e t o n 界) 对于i 扎，七，司线性码c ，有n d + 1 我们把达到s i n 甜e t o n 上界的h ，七，d l 线性码c 称为最大距离可分码( 简称m d s 码) 定理1 2 4 ( h a m m i n g 界，或叫球填充界)如果存在q 元码( n ，k ，d ) ，则 矿k 塾叫t ( 黟 c 5 ， 矿( g 一1 ) ( ) 扛= 0 、。， h a m m i n g 界反映y 口元码的码长，码字的个数，最小距离之间的制约关系 定理1 2 5 ( g i l b e r t , - v a r s h a m o v)设kd 是正整数，q 是素数的幂，如果 ( 一) d - 1 k 1(口_1)qi-o” ( 一) ( g 一1 ) 17 ” 、。 ( 6 ) 则必存在参数为，托d ) 的q 元码 h a 删血n g 界和s i n 西e t o n 界是纠错码存在的必要条件，而g n b e m l r s h a 唧界则是 纠错码存在的充分条件 第三节循环码的定义和以前的结果 循环码是一类重要的线性码不仅可用线性代数，而且还可用近世代数作为研究工 具在本节，我们主要参考文献是 1 0 】一【1 4 】，f 1 9 】 定义1 3 1 码长为n 的g 元线性码g 叫做循环码，如果c = ( c o ，e l ，c n 1 ) c ，那 么c 的一次右循环变换( 一1 ，勺，一2 ) d 把码字c ：，c l ，c n 1 ) 表示成多项式形式c ( z ) = c o + c , x + + 一l 矿。6 f q m ， 则z c ( z ) = c o x + c 1 妒+ + 一2 矿一1 + c n l 矿i 一, + c o x + c , x 2 + + 一2 z “一1 ( r o o d 矿一 1 ) 所以码字c 可以看成商环风= k m 中的元素，。c ( z ) 即为码字c 一 次右循环得到的向量因此，我们把集合f n 等同于r ，1 它们均为f q _ h n 维线性空 8 间， 1 ，z ，孑，扩一1 是r r i 的一组基f n 中的口元线性码等同于r ，l 的一个f 口一线性子 空间( 仍记为c ) 如果a 是循环码，这相当于c 满足如下条件：c ( z ) c = = 争x c ( x ) d 因此，e 是循环码当且仅当e 是环忍中的一个理想 定理1 3 1 设c 是兄l = k x l 的一个理想，即c 是码长为的循环码 码则 ( 1 ) 存在唯一的次数最低的多项式g ( x ) c ，使得c ； ，g ( z ) 称为g 的生成 多项式； ( 2 ) g ( x ) l x 一1 ； ( 3 ) 如果d e g ( g ( x ) ) = r ，那么c 的维数是竹一r ，且 g = = r ( z ) g ( z ) i d e g ( r ( z ) ) ，l r ) ( 4 ) 如果9 ( z ) = g o + g l x + + g r x r , 那么g o 0 ，_ t i c 的一个生成矩阵是 g = g ( z ) z g ( x ) j c n - r - 1 9 ( x ) g bg l g r0 00 0 g og l 肼0 0 0o 。 0 000 g o9 i 吼 证明：( 1 ) 因为风中的每个理想都是主理想 ( 2 ) 由带余除法可得 ( 3 ) 由( 2 ) 可设矿一1 = h ( x ) g ( x ) ， 对任给的( x ) 冠。， 设f ( x ) = q ( x ) h ( x ) + r ( z ) ，d e g ( r ( x ) ) n r ， 贝l j f ( x ) g ( x ) er ( x ) g ( x ) ( r o o d , t n 一1 ) 因为9 ( z ) ，z 9 ) ，扩- r - 1 9 ( z ) 是e 的一组基 所以e 的维数是n r - ( 4 ) 若g o = o ，则g ( x ) = 。9 1 0 ) ，d e g ( g l ( x ) ) r ， 9 ( n - r 1 ” 且g l ( x ) ix g d x ) = 矿- 1 9 ( z ) ( r o o d 矿一1 ) ， 所以g l ( z ) c ，这与g ( z ) 的取法矛盾 定理1 3 2 设口= 和q = 是日。中的理想，即a ，c 2 都是循环 码，设f ( z ) = l c m ( g l ( x ) ，9 2 ( z ) ) ，g ( x ) = g c d ( m ) ，9 2 ( z ) ) ，则 ( 1 ) a q 车号虫( 圳m ( z ) ， ( 2 ) a n c 2 = ， ( 3 ) g + q = 证明：由定义可得到 第四节准循环码的定义和结构 在本节，我们主要参考文献是【1 卜i s 首先，我们规定如下的记号： i - - - - - f m ； 1 1 = f q m ； 若，( z ) e f 一，7 两= f ( x ) + i ，( z ) 为次数小于m 的多项式； 若o ( 。) e f q ，二两= a ( x ) + i t ，n ( z ) 为次数小于m 的多项式； 定义1 4 1 设e 是一个f 。上的【n ，k ，司线性码，如果对c 中的每个码字经连续f 次右 循环变换后仍是c 中的一个码字，则g 称为准循环码这样最小的 称为c 的指标，在这 种情况下，由带余除法，n = m 1 准循环码是循环码的自然推广，当f = 1 时，准循环码即为循环码 对于准循环码的结构，我们有以下的刻画( 【2 】) ： 设e 是一个f q 上长度为n = m l ，指标为f 的准循环码设t 是对叼中的向量v 的一 次右循环变换，定义为p v = t ( p 一1 v ) ，i = 1 ，2 ，规定t o = 1 是恒等变换，则准循环 码c , - i p a 看作是r 上的，在一下保持不变的瑶的一个子空间 1 0 如果n ( z ) 6 f q 纠，那么f 可被看作为一个f 。纠一模定义是： f 。嘲f + f a ( x 1 f ha ( t t ) f 对任给的a ( x ) $ f q 纠，f f ，在这个定义下，f q h 乘以一个长为m z ，指标为z 的r 上的 准循环码是一个l m 模f 的子模因为( z ”一1 ) f = ( p “一1 ) f = o ，所以理想i l = c f g 扛】是掣的零化子因此，我们也能把f 看作是f q 旧i l 一模，定义是： f q x 1 1x f q m f 丽f a ( t t ) f 对任给的五两e f 。 x 1 1 ，f f 类似地，准循环码c 是f 。纠i 模叼的子模 设c 是准循环码，作为l m i 模f 的子模，由f 1 ，如，f 生成，则 e = = 瓦i 弧+ 夏不弧+ + 蕊f 夏两f q 纠i 1 ，i = 1 ，2 ，一，t ，f 在f 中，一个准循环码c 有一组循环基c ，一c ，t a c ，t ( 一1 ) c ，c f ，七sm ，对 应于一个生成元生成的k m i t 模l 掣的子模，即 c ； = o ( z ) cia ( x ) e f 口 z 1 1 设向量v = ( 钉( o 0 ) ，v ( o j 1 ) ，口( m l o ) ，口( m 一1 ，l - 1 ) ) f ，令v j = ( v u , o ) ，1 ) ， o ，l - 1 ) ) f ：，j = 0 ，l ，m 一1 贝l j v = ( v 0 ，v 1 ，v m 1 ) ，元素吩= o ，o ) + v o , n a + ”) 舻+ + v o - , t 1 ) 一1 f d ，这里 1 ，o ，口2 ，o t l - i 是向量空间f q t f q 固定的一组 基定义f 。i l 模f 和f 口1 1 模f 一吲i 之间的映射： ：f _ + f 一纠i v h 毋( v ) = v ( x ) = v ( x ) + i = v o + u 1 2 + + v m 一1 z m 一1 + i 则f 町m i - 模f 与f 。川i 模玎纠i 模同构，这里f 。 z i i 模f q , m i 的定义是： f 。 x i ix f 一 x i + k m i a ( x ) x ，( z ) 一o ( z ) ，( z ) ” 对任给的石两e f 。 x i l ，7 两f i x i 在上述的模同构意义下，循环变换f 的作用相当于在f i x i 中乘以z 再模( 矿。一1 ) 因 此，在f 一f 口的一组固定的基下，f q x l l l l 模f d m i 的子模和f q 上长度为m f ，指标为f 的准 循环码之间建立了一一对应的关系 对于准循环码，我们有以下一些已有的结果( 【2 】) ： 定理1 4 1 设c 是f 。上长度为竹= m l ，指标为z ，一个生成元7 两f 口l m i 生成的 准循环码，则码g 的维数k = m d e g ( 9 ( z ) ) ，夕( z ) = g c d q ( f ( x ) ，矿一1 ) e f 口i x 定理1 4 1 给出了一个生成元生成的准循环码维数的计算方法 定理1 4 2 设g 是f 口上长度为n = m ，指标为f ，一个生成元7 两f 矿睁l i 生成的 准循环码，则d ( g ) d ( 0 ) 这里0 是f 一上长度为m ，由9 ( z ) = g c d ( f ( x ) ，矿一1 ) f m 生 成的循环码 定理1 4 2 给出了一个生成元生成的准循环码的最小距离的一个下界这个下界是由 生成元和z m 一1 的最大公因子生成的循环码的最小距离 定理1 4 3 设e 是f q 上长度为n = 硼，指标为f ，由8 个生成元生成的准循环码，设生 成元集为 丽= 鬲五丽，i = 1 ，2 ，s c _ f q , m i ，这里反( z ) = g c d q ( f i ( x ) ，一 1 ) f g m ，且五( z ) 反( z ) = m i ( 茹) = m l , 0 + 佻。l z + + m f ，女：一l z 一1 f i 爿，= m d e g ( 反( z ) ) ，i 一1 ，2 ，s , b 琏e f q , f 。的一组固定的基 1 ，n ，n 2 ，n l - 1 下砚j 对应的f ：中 的向量# j m u ，如果集合 m m m i l ，m i ，一1 ，i = i ，2 ，- r m i j 0 f ：在f q 上是 线性无关的，那么码c 的维数k ；名1 = 。( m d e g ( 反0 ) ) ) 定理1 4 4 设c 是k 上长度为n = m l ，指标为f ，一个生成元7 两f 矿【叫i 生成的 准循环码，f ( x ) = ，0 + z + + ，m 一1 $ 一1 f 一纠，则 d ( c ) d ( 白d ( b ) 这里0 是f d 上长度为m ，由9 ( z ) = g c d ( f ( x ) ，。”一1 ) 6 f q * 生成的循环码b 是长度为f ， 由 f 0 ，f 1 ，f m l c _ f ：生成的线性码，这里如u = 0 ，1 ，m 一1 ) 是在f 一f q 的一组固 定的基 1 ，a ，q 2 ，0 ，- 1 t f j 对应的聪中的向量 定理1 4 5 设e 是f 町上长度为n = m l ，指标为f ，由8 个生成元生成的准循环码，设生 成元集为 而= a o + 五，l + + m 一1 扩一1 + i ，i = l ，2 ，- 一，s ) c _ f 矿 x i ，则 d ( c ) d ( c ) d ( b ) 这里c 是f 一上长度为m ，由9 ( z ) = g c d ( f l ( x ) ，2 ( z ) ，五( z ) ，z ”一1 ) f m 生成的循 环码b 是长度为z ，由 f j ，i = 1 ，2 ，s ，j = 0 ，1 ，m 一1 量砖生成的线性码，这 里f i j ( i = 1 ，2 ，s ，j = 0 ，1 ，m - 1 ) 是在f 一f q 的一组固定的基 1 ，n ，o t 2 ，c l t l - 1 ) 下 五j 对应的f ：中的向量 定理1 4 3 给出了在一定条件下多个生成元生成的准循环码的维数的公式定 理1 4 4 和定理1 4 5 对准循环码的最小距离做了估计，这取决于循环码0 和线性码b 的 最小距离在第二章第一节，我们将给出定理1 4 4 的不同于1 2 】的一个证明但是1 2 】2 没有给 出定理1 4 5 的证明，我们将在第二章第一节给出具体的证明 第二章引理及准循环码的一些性质 第一节引理 定义2 1 1 符号g c d 口( ( z ) ，2 ( ) ，工( z ) ) 表示，1 ( z ) ，丘( z ) ，。0 ) 在f 。中的 最大公因子 首先，设c 是f 。上长度为n = m ，指标为z ，一个生成元而生成的准循环码，即c = = 硒而：丽r x i - ) ，而f m i 以下我们给出定理1 4 1 的一个证明 证明：因为码c 中任意一个码字三两可以表示成7 两，；7 研，芬j 而的f 。一线 性组合，并且7 两，；7 两，= 叮研在k 上线性无关 因此码e 的维数k = m d e g ( g ( x ) ) ，g ( x ) = g c d q ( f ( x ) ，矿一1 ) e f q x 1 设码c 是由s 个生成元雨，丽，丽，丽e f q l r i ，t = 1 ，2 ，s ，生成 的准循环码，即e = 石石丽+ 五巧丽+ + 五万丽：i 两f 。 x l - ，i = 1 ，2 ，s c _ f q z m i 每个生成元雨= 五，o + ，1 z + + 五，。一l x m 一1 + i e f 一 x i ，i = 1 ，2 ，- 一，8 以下我们给出定理1 4 2 的一个证明 证明：因为码c 中任意一个码字；两可以表示成丽，；丽，矿：一1 ( z ) ， 丽，x l ( z ) ，z e 一- 厶0 ) 的f q - 线性组合， 又因为集合 m 撕m i ，l ，一，m i , k ：一l ，i = l ，2 ，s i m i j o f ：在f g 上是 线性无关的， 所以丽，丽，z ：一- ，1 ( z ) ，丽，厕，“一- 厶( z ) 在f 。上线性 无关 因此，码e 的维数k = = = l = 冬l ( m d e g ( 反( z ) ) ) 对于准循环码的最小距离，我们给出定理1 4 3 的一个证明 1 4 证明：因为c 中每个码字雨可以看成0 中的一个码字，因此d ( e ) d ( 0 ) 下面我们给出定理1 4 4 的不同于【2 l 的另一种证明方法 证明：因为0 羽= c ( z ) + i = e o + c l x + e a x 2 + + c ，一i x m - 1 + i c 是由g ( x ) 生 成的循环码0 中的一个码字，触ld ( c ) d ( 0 ) 由于 可可，虿7 两，；函而) 是c 的一组f 。一基，= m d e g ( ，( z ) ) ， g ，0 ) = g e d 。( ， ) ，扩一1 ) ， 所以存在a o ，a l ，叼一1e f 口，使得 c ( x ) in o ，( z ) + 口l x f ( x ) + o 圯f f ( x ) + + a k _ i 扩一1 f ( x ) = ( a o8 l n 一1 ) 兰( a o a l a 一1 ) i ( c oc 1 一1 ) ，( z ) z ，( z ) 寸一l f ( x ) h 氛| 。一1 i 。一1f o | m 4 l 。一o h | m 一札| m o ( m o d 扩一1 ) z m 一1 所以对c ( z ) 的每个非零系数qe f 。一，有 勺= n o 乃+ a ：t f 一1 + 。_ + n 一l 一( k ，一1 ) 设毛= ( 厶o ，办t 1 ，厶，l - 1 ) 0 = 0 ，1 ，m 一1 ) 是在f q 一f 口的一组固定的 基 1 ，n ，舻，o 一1 下方对应的f ：中的向量， 则c j 对应的向量 c j = a o ( f j 。0 ，办1 ，一，厶，l 一1 ) + n l ( 办一1 , 0 ，万一1 l ，办一l ，l 1 ) + - ba k , 一l ( 厶一( 一1 ) o ，乃一( k j - 1 ) ，l ，一，乃一一1 ) l 1 ) b ， 即w h ( c j ) d ( 口) 因此，d ( c ) d ( c ) d ( 口) 。 对多个生成元生成的准循环码，有类似的结果以下我们给出定理1 4 5 的具体证明 证明：设0 c = ，c l ，一1 ) g q = b ，o ，l ，) ， 对每个j ，令q = 勺，0 + c j , l c t + + c j 一1 0 1 he f 4 ，j = 0 ，1 ，m 一1 f 酗g ( x ) = g c d ( ，1 ( z ) ，2 ( z ) ，厶( 霉) ，z ”一1 ) f 叮i 翻， 所以可以设 扛) = p ) g ( z ) ，l = 1 ，2 ，s ， 又因为g 是由 丽，i = 1 ，2 ，s ) f 矿i 叫i 生成的准循环码， 所以存在5 丽，爵瓯，瓦两e f 。i x i - ，使得 习万；瓦i 万五百西+ 瓦i 丽+ + 瓦i 瓣 ；瓦i 西元疋羽+ 瓦i 西瓦i 丽+ + 瓦i 万瓦忑丽 ：( 瓦石习i 两+ 瓦石丽+ + 瓦石丽) 虱巧0 即d ( c ) d ( 0 ) 对每个；两c ，存在机忙) = 圾，o + 玩，l z + + 6 t ，矿+ ie f q 陆】i ， 0 m l ，t = l ，s ，使得 可可= 瓦i 丽+ 瓦再丽+ + 瓦i 瓣， 因此 1 6 c 和) 兰b l ( z ) 1 ( x ) + 6 2 ( z ) 五( z ) + + 以( z ) 工( z ) = ( 以仁) 6 2 ( z )“( z ) ) = ( 1z ，) = ( 1 矿) b l ，0b 2 ，0 b l ，1b 2 ，1 h 。6 2 ， ( z ) ，2 ( o ) ! 厶( z ) c o , 0c o , z 。c b m 一1 e l , 0 c 1 1 。一 c 1 m 一1 岛0 岛。1 一 岛m 一1 1 1 ，0a 1 f l , m - i ，2 。0 ，2 ，1 ，2 m l l s n s 。1 s , m - - 1 z m 一1 0 ( 其中c i j = b k ， j ，i = 0 ，1 ，一，；j = 0 ，1 ，m 一1 ) k = l = ( c i q ，1 x * 。 = 0t = 0 q t m 一1 x i ) i = 0 1 z ： 卫m 一1 = c i ，0 x + q ，i x i + 1 + + g ，m l z ”“一1 i = 0i = 0i - - - - 0 兰c o + c l x + + 锄一1 x m 一1( m o d 扩一1 ) 因为每个c ；j ( i = 0 ，1 ，e ；j = 0 ，1 ，m 一1 ) 是 k j ( k = 1 ，一，s ； 】7 x r n 一1 啪 阶 j = 0 ，1 ，m 一1 ) 的f 。线性组合， 而每个q 0 = 0 ，1 ，f f t , 一1 ) 是c i a ( i = 0 ，l ，一，e ；j = 0 ，1 ，m 一1 ) 的 f 口线性组合，因此，q 是 j 的k 线性组合， 又因为在f 一f 。的一组固定的基 l ，o t ，n 2 ，- 1 ) 下， c ( z ) 的系数如对应的的向量是c t ， 因为f i j b ，所以e t z ( t = 0 ，m 一1 ) ， 因此对每个非零系数c t 对应e t ，w n ( c t ) d ( b ) 所以，d ( c ) d ( c ) d ( b ) 下面我们具体计算了四个准循环码的维数和最小距离 例1 ：取f = 3 ，口= 2 ，m = 3 ，佗= m l = 9 ，f d = f s ，a ( z ) = z 3 - - i - z + 1 ，设a 是a ( z ) 的一 个根，q 3 = n - t - 1 , f 8 = o ，1 ，n ，a + 1 ，a 2 ，0 2 + n ，o , 2 + 1 ，a 2 + 口+ 1 ，f 8 中的每个元素在 基 l ，q ，舻) 下有唯一的表示i = f s m ，i i = f 2 x 设确= z + 1 - i - i ，a = 面忑西丽：五两f z k 】i 。 ，则 0 扛+ 1 ) = 0 一( 0 0 0 0 0 0 0 0 0 ) 1 扛+ 1 ) = z + 1 一( 1 0 0 1 0 0 0 0 0 ) z ( z + 1 ) = x 2 + z 一( 0 0 0 1 0 0 1 0 0 ) 扛+ 1 ) 扛+ 1 ) = 护- t - 1 一( 1 0 0 0 0 0 1 0 0 ) z 2 0 + 1 ) i 护+ 1 一( 1 0 0 0 0 0 1 0 0 ) ( z 2 + 1 ) 0 - t - 1 ) 三x 2 + z - + ( 0 0 0 1 0 0 1 0 0 ) ( 。2 + z ) 扛+ 1 ) i 。+ 1 ，( 1 0 0 1 0 0 0 0 0 ) ( z 2 + z + 1 ) + 1 ) e 0 一( 0 0 0 0 0 0 0 0 0 ) 即a = ( o o o o o o o o o ) ，( 1 0 0 1 0 0 0 0 0 ) ，( 0 0 0 1 0 0 1 0 0 ) ，( 1 0 0 0 0 0 1 0 0 ) ，a 是f 9 ，2 ，2 j 准循环码石 = ( 0 0 0 ) ，( 1 1 0 ) ，( 0 1 1 ) ，( 1 0 1 ) 是【3 ，2 ，2 】循环码，b 1 = ( 0 0 0 ) ，( 1 0 0 ) 是【3 ，l ，1 】线性码 因此，d ( c 。) d ( 西) d ( 玩) 设丽= z 2 + z + 1 + i ，0 2 = 瓦巧i 丽：石玎巧f 2 i t ) ，则由类似的计 算方法，我们得到：0 2 = ( o o o o o o o o o ) ，( 1 0 0 1 0 0 1 0 0 ) ，q 是【9 ，1 ，3 】准循环码0 2 = ( 0 0 0 ) ，( 1 1 1 ) 是【3 ，l ，3 】循环码，b 2 = ( 0 0 0 ) ，( 1 0 0 ) ) 矧3 ，1 ，l 】线性码 因此，d ( q ) d ( q ) d ( b 2 ) 例2 ：取f = 4 ，q = 2 ，m = 3 ，n = m z = 1 2 ，f q f = f 1 6 ，a ( x ) = f i 9 4 + z + l ，设口是a 0 ) 的 一个根，0 1 4 = 口+ i , f 1 6 = 0 ，1 ，q ，q + 1 ，口2 ，n 2 十n ，n 2 + 1 ，a 2 + d + 1 ，0 3 ，o l 3 + 1 ，q 3 + 口，a 3 + a 2 ，舻+ a + 1 ，n 3 + 舻+ a ，矿+ a 2 + 1 ，舻+ a 2 + n + 1 ，f 1 6 中的每个元素在 基 1 ，n ，q 2 ，舻) 下有唯一的表示i = f 1 6 m ，1 1 - - f 2 m 设丽= 。+ o t + 1 + i ，0 3 = 磊巧y 丽：石虱万f z 忙】i ， ，则由类似的计算方 法，我们得到：g = ( 0 0 0 0 0 0 0 0 0 0 0 0 ) ，( 1 1 0 0 1 0 0 0 0 0 0 0 ) ，( o 0 0 0 1 1 0 0 1 0 0 0 ) ，( 1 1 0 0 0 1 0 0 1 0 0 0 ) ， ( 1 0 0 0 0 0 0 0 1 1 0 0 ) ，( o ：o o ：o 0 0 1 ：o o ) ，( 1 0 0 0 1 1 0 0 0 1 0 0 ) ，( 0 1 0 0 0 1 0 0 0 1 0 0 ) ，q 是【1 2 ，3 ，3 】准循环码 a j = ( o o o ) ，( a + 1 1 0 ) ，( o 口+ 1 1 ) ，( 1 0 q + 1 ) ，( q + 1 0 1 ) ，( q 1 a + d ，( 1 a + l q ) ，( n n d ) ) 是循 环码，d ( 石) = 2 ，b 3 = (