（基础数学专业论文）关于环上的循环码.pdf

摘要 高鼍日 捅要 1 9 9 4 年，h a m m o n s 等人证明了一些十分重要的二元非线性码是环z 4 上的线 性码在g r a y 映射下的像。之后针对四元码的研究逐步开展起来，并获得了很多 重要结果。1 9 9 6 年和1 9 9 7 年，p l e s s ，q i a n 和s o l e 证明了在z 4 环上的线性循 环码的结构特征，并给出了自对偶码的充分必要条件。受到这些人研究工作的 启发，本文以环z 4 上码的理论为基础对环r + z 以( ”2 = 0 ) 上的线性循环码进行 研究探讨。 本文首先介绍了有限域上与本文相关的一些码的基本知识。其次研究了环 e + u f 2 上循环码的结构特征，给出了环e + s t f 2 上码长为奇数的循环码的结构， 其对偶码的结构以及( 1 + u ) - 循环码的结构，同时给出环e + 以上的线性码和循 环码的深度分布。最后综述了环e + 埚上码长为2 的方幂的循环码的结构。 关键词： e + z 幔环； 循环码；深度分布 1 a b s t r a c t a b s t r a c t i n19 9 4 ，h a m m o n se t ch a d p r o v e dt h a ts o m ei m p o r t a n tb i n a r yn o n l i n e a rc o d e s a r eg r a yi m a g e so fl i n e a ro v e rz 4 - r i n g n o tl o n ga f t e rt h a tt h er e s e a r c ha i m e d a t f o u r - u n i tc o d e sh a sb e e nd e v e l o p e ds t e pb ys t e pa n dm a n ys i g n i f i c a n to u tc o m eh a v e b e e nd e r i v e ds i n c et h e n i n19 9 6a n d19 9 7 ，p l e s s ，q i a na n ds o l ep r o v e dt h es t r u c t u r e c h a r a c t e r i s t i c so fl i n e a rc y c l i cc o d e so v e rz i - r i n ga n dp r o v i d e dt h ef u l lr e q u i r e m e n t s f o rs e l f - d u a lc o d e s e n l i g h t e n e db yt h er e s e a r c hw o r kd o n eb yt h e s ep e o p l e ，t h i sp a p e r h a sm a d ea na n a l y s i st o w a r dt h el i n e a rc y c l i cc o d e so v e rr i n ge + 峨w h e r e u 2 = 0b a s e do nc o d et h e o r yo v e rz 4 一r i n g i nt h ef i r s tp l a c et h i se s s a yh a si n t r o d u c e dt h er u d i m e n t so fi n f i n i t ef i e l dr e l a t e d s e c o n d l ya n a l y z e dt h es t r u c t u r ec h a r a c t e r i s t i c so fc y c l i cc o d e so v e rr i n g 疋+ 幔a n d p r o v i d e dt h ec y c l i cc o d e sl e n g t h e n e di no d dn u m b e ro v e rr i n g 最+ 蜗，t h es t r u c t u r e o ft h e i rd u a lc o d e sa n d ( 1 + 甜) - c y c l i cc o d e sa n dt h ed e p t hd i s t r i b u t i o no fl i n e a rc o d e s a n dc y c l i cc o d e sa r ed i s c u s s e d f i n a l l ys u m m a r i z e dt h es t r u c t u r eo f c y c l i cc o d e s l e n g t h e n e di n p o w e r 2o v e r r i n g 最+ 蜗 k e yw o r d s ：e + z 幔一r i n g ；c y c l i cc o d e s ；d e p t hd i s t r i b u t i o n i i 南开大学学位论文版权使用授权书 本人完全了解南开大学关于收集、保存、使用学位论文的规定， 同意如下各项内容：按照学校要求提交学位论文的印刷本和电子版 本；学校有权保存学位论文的印刷本和电子版，并采用影印、缩印、 扫描、数字化或其它手段保存论文；学校有权提供目录检索以及提供 本学位论文全文或者部分的阅览服务；学校有权按有关规定向国家有 关部门或者机构送交论文的复印件和电子版；在不以赢利为目的的前 提下，学校可以适当复制论文的部分或全部内容用于学术活动。 学位论文作者签名：伽) 经指导教师同意，本学位论文属于保密，在 纠年z 月7 日 年解密后适用本授权书。 指导教师签名：学位论文作者签名： 解密时间：年月日 各密级的最长保密年限及书写格式规定如下： 南开大学学位论文原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师指导下，进行 研究工作所取得的成果。除文中已经注明引用的内容外，本学位论文 的研究成果不包含任何他人创作的、已公开发表或者没有公开发表的 作品的内容。对本论文所涉及的研究工作做出贡献的其他个人和集 体，均己在文中以明确方式标明。本学位论文原创性声明的法律责任 由本人承担。 学位论文作者签名：彬1 砂1 年，v 月f 日 第一章引言 第一章引言弟一早jl看 1 9 7 4 年，m c o d n a l d 研究了有限环上的编码理论。1 9 9 4 年，h a m m o n s 等人证 明了一些十分重要的二元非线性码是环乙上的线性码在g r a y 映射下的像，即关 于k e r d e c k ，p r e p a r t a 和g o e t h a l s 码的问题。1 9 9 6 年和1 9 9 7 年，p l e s s ，q i a n 和s o l e 讨论了在z 4 环上的线性循环码的结构特征，给出了环z 。上的线性循环 码的生成多项式和幂等生成元，并给出了自对偶码的充分必要条件。受到这些 人研究工作的启发，本文研究环疋+ 幔上的循环码。环r + u f 2 = o ，l ，材，l + 孔) ， 其中甜是符号并且“2 = 0 。环中的加法法则，乘法法则在下面表格中给出： 加法 oi u1 + 甜 00iu1 + u 110l + 甜 ”“1 + u 0i 1 + 材l + 甜” 10 乘法 0l 甜l + “ ooooo l0i ”l + u ” 0甜0 甜 l + z ， o 1 + 甜 z ，1 由环的定义可知环疋+ u f 2 的特征是2 ，同时易证环r 十掰疋是一个局部环 存在唯一极大理想 o ，z ， ，最可视为其子环。因此，探讨环e + u f 2 上循环码就 具有重要的理论意义和一定的实际意义。本文旨在解决环只+ 埚上循环码的问 题。 本文第二章介绍了有限域上与本文相关的一些码的基本知识。在第三章中 研究了环e + 蜗上循环码的结构特征，给出了环e + z 以上码长为奇数的循环 码的结构，其对偶码的结构以及( 1 + z ，) 一循环码的结构，同时给出了环最+ z 以上 线性码和循环码的深度分布。第四章综述了环只+ z 正上长为2 的循环码的结 构。 第二章域上的线性码 第二章域上的线性码 第一节线性分组码 在数字通信中，经常利用纠错码来进行差错控制，其中一类重要的纠错码 就是分组码。 分组码是对每段k 位长的信息组，以一定规则增加，= 刀一k 个校验元，组成 长为孵的序列( c o ，c l ，q 一。) ，称这个序列为码字。在二进制情况下，信息组共 有2 个，因此通过编码器后，相应的码字也有2 七个，称这2 七个码字集合为( 仇k ) 分组码。 若每位码元的取值有g 种，则共有9 2 个码字，若g 个码字集合构成了g f ( q ) 上所有n 维向量构成的n 维线性空间的一个k 维线性子空间，则称它是一个g 元 以，k 】线性分组码，简称为q 元 疗，k 】线性码。 g 元【刀，k 】线性码的编码问题就是在刀维线性空间圪= g f ( q ) ”中，如何找出 满足一定要求的，有g 量个向量组成的k 维线性子空间圪j 。或者说，在满足给定 条件下，如何从已知的| | 个信息元求得，= 刀一k 个校验元，这相当于建立一线性 方程组，已知露个系数，求满足要求的刀一k 个未知数。 若定义一个一七) 刀阶矩阵日满足 h c - , r = 0 r( 2 1 1 ) 或 c h r = 0( 2 1 2 ) 其中c 为g 元胁，k 】线性码的任一码字，日的每一行向量均线性无关，则称日 为g 元砷，k 】线性码的一致检验矩阵。 显然矩阵的每一行代表一个线性方程的参数，它表示求一个校验元的线 性方程，故若日确定了，则g 元帆k 】线性码也就确定了。 另一方面，g 元f 彪，k 】线性码的g 个码字组成了一个k 维子空间，因此这g 个码字完全可以由k 个线性无关向量所组成的基底而张成。 若将这k 个线性无关向量作为行向量写成矩阵形式，则称该矩阵为g 元 【，l ，k 】线性码的生成矩阵。若g 元研，k 】线性码的生成矩阵为g ，k 个信息元组成 的信息组为所，则有 c = 所g( 2 1 3 ) 2 第二章域上的线性码 将( 2 1 3 ) 式代入( 2 1 1 ) 有 日g r ：0 r( 2 1 4 ) 将( 2 1 3 ) 式代入( 2 1 2 ) 有 g ：日7 = 0( 2 1 5 ) 即g 与日的行生成的空间互为零空间。 q 元 ，z ，k 】线性码是刀维线性空间圪的一个k 维子空间圪j ，由一组基底即g 的行张成，由线性代数知识可知，它的零空间必是一个疗一k 维的线性子空间 圪，靠，并由刀一k 个线性无关的向量张成，由( 2 1 4 ) ，( 2 1 5 ) 式可知，这刀一k 个向量就是日矩阵的行，因此，若把日矩阵看成是g 元i n ，z k 】线性码的生成矩 阵，而把g 看成是它的检验矩阵，则我们称由g 生成的g 元 ，z ，k 】线性码c 与由 日生成的q 元 聆，z k 】线性码c 上互为对偶码，相应地，称圪j 与圪一一七互为对偶 空间。 若c = c 上，则称码c 为自对偶码。显然，自对偶码必是g 元 2 n ，n 】形式的线 性码。 第二节循环码 循环码是一类重要的线性码，它具有严谨的代数结构，又具有循环的特性， 从而性能易于分析，且编译码电路尤其是编码电路简单且易于实现，现己发现 的大部分线性码与循环码有密切联系，因此循环码特别引人注目，对它的研究 也比较深入和系统化。 圪j 为n 维线性空间圪的一个k 维线性子空间，若对于任意 p o ，c l ，一，c 。- 1 ) 圪 ，恒有( c 。- 1 ，c o ，c 柚) 圪j ，则称k 为循环空间或循环码。 显然g f ( p ) 上所有的r l 维向量构成一个线性空间圪，其中每个向量是分量 取自g f ( p ) 上的向量，若将圪中每个聆维向量和系数取自g f ( p ) 上的多项式相 对应： ( c o ，c l ，c n 1 ) 寸c o + c l x + 4 - c n - i x ”= 厂( x )c i g f ( p ) 则它们之间建立了一一对应关系，由有限域理论知，所有次数小于n 次的多项式 一定在模n 次多项式f ( x ) 耳i x 】的剩余类中，即 厂( x ) c o + c l x + + c 。一l x ”一1 ) ( m o d f ( x ) ) 3 第二章域上的线性码 因此，圪中每一个，l 维向量都与g f ( p ) 上次数低于r 1 次的一个多项式相对 应，并必在模f ( x ) 的剩余类中： 在q 元陬k 】循环码中，码字( c 。，c l 一，c 。) 的多项式表示为 c ( z ) = c o + q x + + c n l x ”一， 它的循环移位一次后所得码字为( c n - i ，c 脚) ，相应的多项式表示为 c l ( x ) = c n _ 2 x 4 - 1 + o n _ 3 x ”一2 + + c o x + c n 一1 ， 相当于c ( x ) 乘以x 后用f ( x ) = x ”一1 取模，即 x c ( x ) = c n _ 1 x ”+ c n - 2 x “一1 + + c l x 2 + c o x 善o n _ 2 x “_ + + c i x 2 + c o x + c 月一lm o d ( x ”一1 ) 因为在模矿一l 情况下x “兰l ，所以 x c ( x ) = c n 一2 x ”一1 + + c o x + c h l 若在 o n - 2 x 肛1 + + 铴x + c ) 剩余类中，以最低次数c 。一2 x 肛1 + t c o x + c 多项式作为该类代表元，则循环码就可以用m o d ( x 一一1 ) 的多项式表示。 定理2 2 1 g f ( q ) ( g 为整数或整数幂) 上的g 元 疗，k 】循环码中，存在有 唯一的刀一k 次首一多项式g ( x ) = 石”七+ g n - k - 1 x ”扣1 + + g l x + g o ，每一码多项式 c ( 功都是g ( x ) 的倍式，且每一个刀一1 次的g ) 倍式一定是码多项式。 定理2 2 2 g f ( q ) 上g 元【玎，k 】循环码的生成多项式g ( x ) 一定是石”一1 的 因式，即x 一- 1 = g ( x ) 办( 石) 。反之，若g ( x ) 是力一七次多项式，且g ( x ) ix ”一1 ，则 该g ( x ) 一定生成个g 元 ，z ，k 】循环码。 若设g ( x ) 为疗一k 次多项式，则办( x ) 为k 次多项式，从而以g ) 为生成多项 式所组成的g 元 力，k 】循环码中，g ( x ) ，x g ( x ) ，x h g ( x ) 等k 个码多项式必是线性 无关的。可以由这些码多项式所对应的码字构成循环码的生成多项式g ，即 g = g n kgn k 一1 g n 一七 g o g ig o g ，一七g n 一七一lg l 其中g ( z ) = g o + g l x + + g 。“x ”一。 若设向( x ) = h , x + + ，则可验证，循环码的一致检验矩阵为 4 第二章域上的线性码 ( h o 、i 日- i 竺i l 魂j 由该式可看出，h 矩阵的行完全由h ( x ) 的系数决定。故称办( x ) = x ”一l g ( x ) 为该循环码的校验多项式。 另外，若记矗+ 0 ) = h o x + + 仅一l x + h k ( 称h ( x ) 为办( x ) 的互反多项式) ， 则有由校验多项式厅( x ) 的互反多项式乃+ ( x ) 生成的q 元 ，z ，聆一k 】循环码与由多项 式g ( x ) 生成的q 元 ，2 ，k 】循环码为对偶码。 5 第三章环e + u f 2 上的循环码 第三章环最+ 幔上的循环码 第一节环疋+ 幔上的线性码 3 1 1 环e + z 以上的线性码及其对偶码的生成矩阵 下文中设e + z 以= r 若栅= ( x l ，z 2 ，x 。) ，y = ( y l ，y 2 ，y 。) r 疗，定义x 与y 的内积为 彳y = i y l + 恐奶+ + 乩 ( 3 1 1 ) 如果x y = 0 ，则称x 与】，正交。 设c 是r 上长为刀的线性码，令 c 上= x r ”ix y = 0 ，对vy c ( 3 1 2 ) 则容易证明c 上也是环r 上长为n 的线性码，称之为线性码c 的对偶码。若环r 上 线性码与其对偶码相等，即c = c 上，则称c 为环足上的自对偶码。 设q ，c ：均是环r 上长为n 的线性码，若q 通过坐标置换，必要时将码元1 与l + u 互换，能得到码c ：，则称c 。与c ：为环r 上等价的线性码。 命题3 1 1r 上非零线性码c 等价于一个由 f 彳 b 1 ( 3 1 3 ) 1 0 u i 如u dj 所生成的线性码，其中么，d 为域e 上的矩阵，b 为犬上的矩阵，此时也称码c 的 生成矩阵为( 3 1 3 ) 式，显然码c 中共包含4 k - 2 k 2 个码字。 证明对码长，l 用数学归纳法。分两种不同情形： ( 1 ) c 中有一个含码元1 或码元1 + 甜码字c ，则经过坐标变换( 必要时将 1 或l + u 互换) 可设该码字为c = ( 1 ，c 2 ，c 。) ，令c = ( o ，x 2 ，矗) c ，显然c 7 也是一线性码，且通过删除第1 个坐标可将之看成一长为，一l 的线性码，由归 纳假设知c 的生成矩阵为 f o k i 4 l 且1 【0 0 讥，u dj 其中4 ，d 为域疋上的矩阵，蜀为环尺上的矩阵。则c 的生成矩阵为 f 1 c 2 c k !c k i + l c 毛+ 七2 c 毛+ 屯+ l c 月j l 0 ，”l 彳l 最 i 10 0 u i k 2 u d j 6 第三章环e + u f 2 上的循环码 将该矩阵的后k 。+ k 2 一l 行的一个适当线性组合加到第1 行可得 f 气 彳 曰1 1 0 u 6 , u dj 其中彳，d 为域只上的矩阵，b 为r 上的矩阵，即此时c 有形如式( 3 1 3 ) 的生 成矩阵。 ( 2 ) c 中所有码字均不含码元l 与码元i + 材，因为c 0 疗 ，所以c 中一 定有一个含码元甜的码字c ，经过坐标变换可设该码字为c = ( z f ，u c ：，u c n ) 。 类似地，定义c = ( o ，瓣：，y x 。) c ) ，则通过删除第一个坐标也可将之看 成一长为n - i 的线性码，由归纳假设知c 的生成矩阵为( o u i h 。u d ，) ，其中 d 1 为域最上的矩阵。则c 的生成矩阵为 f “ u c 2 材c bu c k 2 + l 材c n1 【o儿，一z 峨j 将该矩阵的后k ，一1 行的一个适当线性组合加到第一行可得 婶ik 。u d ) 其中d 为域最上的矩阵，此式即为式( 3 1 3 ) 中当k 。= 0 时的情形。综上所述， 无论何情况，c 的生成矩阵均为式( 3 1 3 ) 。 定理3 1 2 若c 为命题3 i 1 所设的线性码，则其对偶码c 上的生成矩阵 为 r 爱k - k , 0 也) ) l 谢7讥j 7 且c 上共包含4 柚- 啦2 z 个码字。 证明 设c 。为r 上的由( 3 1 4 ) 式所生成的线性码，则显然有c l 互c 上。 v c = ( c 1 ) c 2 ，c 。) c 上，将( 3 1 4 ) 式中前n - k l 一如行的一个适当线性组合加 到c 上，则可得到c 上中的一个码字c 7 = ( c l ，一，c k i ) + l ，c 毛+ i ：，0 ，0 ) 。因为c 7 与 ( 3 1 3 ) 式中后如行正交，所以气+ l ，气+ 如只能取0 或“，将( 3 1 4 ) 式中 后k ，行的一个适当线性组合加到c 上，则得到c 上中的码字 c = ( c l ，一，气，0 ，0 ) 。又因为c 。与( 3 1 3 ) 式中前毛行正交，所以 q = = c 岛= 0 。因此，c c i ，即c 上c l 。 综上即有c 上= c l 。 由命题3 1 1 与定理3 1 2 可得到 推论3 1 3 任一长度为力的r 上的自对偶码恰好包含2 ”个码字。 7 第三章环e + z 幔上的循环码 3 1 2 环r + z 厉上线性码的深度分布 3 1 2 1 环只+ z 厉上深度的基本概念及其基本性质 定义3 1 1 v x = ( x l ，一，x 。) r ”称 d x = ( x 2 一而，x 。一x 。一1 ) 为码字z 的导数。 容易验证 d ( x + 少) = d x + d yd ( 3 x ) = 2 d x 允r 即d 是r 的线性算子。 为了方便，记【】是长为m ，分量全是见的向量。 定义3 1 2 设x r ”，称使得 d x = 0 肛】 成立的最小非负整数f 为向量x 的深度，记为d e p t h x = f 。如果没有这样的f 存在， 则规定d e p t h x = 刀。 显然，对v x r ”，将有0 d e p t h x 疗，且d e p t h x = f 的充要条件是存在 五r = 1 ，甜，14 - 甜) ，使得d 卜1 x = 刀叫+ 1 】。 定义3 1 3 设c 为r 上长为，2 的线性码，令d ，表示深度为f 的码字的数量， 则称仇，d x ，o n 为线性码c 的深度分布。 定义3 1 4 设c 为r 上长为，2 的线性码，d 。，d 1 ，圾是它的深度分布， 则下标集 f f1 f 胛，口0 ) 称为线性码c 的深度谱。 性质1 设c l 是r 上深度为f 的码字，c 2 是r 上深度为歹的码字，且j f ， 则c = c ，4 - c ，是r 上深度为f 的码字。 证明 因为c 。的深度为f ，所以存在名r + = 1 ，z ，1 + 材 ，使得 d 卜1 ( c i ) = 【2 n 一“】。又因为c 2 深度为，并且f ，所以 d 卜1 ( c 2 ) = d l - j - ! ( d 7 ( f 2 ) ) = d i - j - i ( 0 n - j 】) = 【0 ”“1 】 而d 是线性算子 d 卜1 ( c l4 - c 2 ) = d 卜1 ( c 1 ) 4 - d 卜1 p 2 ) = 【2 n 叫“】 因此，q4 - c ，的深度为f 。 性质2 设c = ，( c ) + u s ( c ) 为r 上一码字，则有 d e p t hc = m a x d e p t hr ( c ) ，d e p t hs ( e ) 证明因为d 是线性算子，所以d ( c ) = d ( 尸( c ) ) + 徊。( s ( c ) ) ，又因为 c = 0 皇，( c ) = s ( c ) = 0 8 第三章环疋+ 幔上的循环码 所以由深度定义知，d e p t h c = m a x d e p t h r ( c ) ，d e p t hs ( c ) 。 显然，由此性质知，要算c 的深度，只须先计算，( c ) ，s ( c ) 的深度，再选较大 者即可。 3 1 2 2 环e + z 以上线性码的深度分布 定理3 1 4 设c 为r 上生成矩阵为 ( i 。k iz ：b 2 ) ) 的线性码，其中彳，蜀，岛，d 均为域疋上的矩阵，若定义r ( c ) = r ( c ) lc 彤， s ( c ) = s ( c ) ic c ) ，则c 与s ( c ) 具有相同的深度谱，即c 中所有非零码字共有 k l + k 2 + 秩( 岛) 个不同的深度。 证明 先证明c 与s ( c ) 有相同的深度谱，由，s 的定义知，s 均是r ”到霹 的加法群同态映射，故，( c ) ，s ( c ) 均为e 上线性码，v r ( c ) r ( c ) ，其中c c ， 则“c c ，故有r ( c ) = s ( u c ) s ( c ) ，即有厂( c ) s ( c ) ，也就是说，( c ) 是线性码 s ( c ) 的线性子码，再由性质2 知c 与s ( c ) 具有相同的深度谱。 其次，证明c 的所有非零码字含有k l + k 2 + 秩( 岛) 个不同的深度，也即证明 s ( c ) 的所有非零码字含有k l + k ：+ 秩( 岛) 个不同的深度。 事实上，因c 的生成矩阵为( 3 1 5 ) 式，故，( c ) ，s q c ) 分别可看作矩阵 f 氏 a 骂+ 幔 1 lz “ u a 蛾 l i ( 1 + u ) i k , ( 1 + u ) ab + u ( b n + b 2 ) l 【0红， u d j 的行向量在映射，s 下的象所生成的。 因为彳，e ，b ，d 均为域最上的矩阵，所以 ，( 么垦+ 徊2 ) = ( 彳墨) ，( z t k u a u b t ) = ( o 0 o ) ，( ( 1 + “) 气 ( 1 + u ) ae + 甜( b l + b 2 ) ) = ( 气 a局) r ( oz 心u d ) = ( o 0 o ) 即r ( c ) 是由( 厶 ab i ) 生成，又因为该矩阵的秩为毛，所以r ( c ) 的生成 矩阵为( k 彳曰) ，即r ( c ) 是i n ，毛】线性码。 类似地，因s ( i k , ab i + u b 2 ) = ( 0 0 b 2 ) s ( 叱。u au b i ) = ( 1 k 。ab i ) 9 第三章环五+ z 以上的循环码 5 ( ( 1 + “) i k , ( 1 + u ) ab l + u ( b l + 岛) ) = ( 气 4 蜀+ 召2 ) s ( o u l t , ：u d ) = ( o 厶：d ) 而( oo 岛) + ( 气 彳最) = ( i k ,a 反+ 反) 故s ( c ) 可看作由 ha b 11 1 0 i k ：dl 10 0 岛 的行向量生成。若记e 为b ，的行向量的最大无关组所生成的矩阵，则s ( c ) 可由 f a 骂1 i o 厶： d i ( 3 1 6 ) l0 0e j 生成，并且该矩阵各行向量线性无关，故( 3 1 6 ) 式为s ( c ) 的生成矩阵，即s ( c ) 是 刀，k l + 如+ 秩( 岛) 线性码，s ( c ) 的非零码字共含有白+ 屯+ 秩( 岛) 个不同的 深度，故原命题得证。 推论1设c 是生成矩阵为( 3 1 5 ) 式的线性码，则其非零码字的不同深 度的个数最小值是白+ k 2 ，最大值是m i n 2 k ! + k 2 行 。 证明由定理3 1 4 知，c 中非零码字含有k l + 后2 + 秩( 岛) 个不同的深度， 而0 秩 ( 垦)m 洫毛，刀一白一岛， ，故有 k l + 也k l + 如+ 秩 ( b 2 ) m i n 2 k i + k 2 , 刀) 。 推论2 设c 为r 上一长为甩的线性码，其生成矩阵为 fi k , a b 1 ( 3 1 7 ) l0z 叱d 、“2， 其中a ，b ，d 均为疋上的矩阵，则c 中所有非零码字恰含有k + 也个不同的 深度分布。 若c 的生成矩阵为( 0 u l k 2 u d ) ，其中d 为疋上矩阵，则c 的所有非零码 字恰含有毛个不同的深度分布。 下面讨论一下推论2 中线性码c 的深度分布。 引理3 1 5 设c l c 2 均为e 上线性码，且c l 生成矩阵为 ( 厶 彳 b ) ( 3 1 8 ) g 的生成矩阵为 1 0 第三章环只+ u g 上的循环码 一 _ 一 h 么b1 ( 3 1 9 ) lokd 其中a ，b ，d 均为r 上的矩阵，则c 。+ u c 2 为环r 上的线性码，且其生成矩 阵为( 3 1 7 ) 式。 。 证明 v x l + 戤2 ，y 1 + 砂2 c l + “c 2 ，则有 ( x l + 城2 ) + ( y l + 缈2 ) = ( x l + x 2 ) + “( y l + y 2 ) 1 因为c 1 ，c ，为环r 上线性码，所以( x l + x 2 ) + 甜( y l + y 2 ) c t + u c 2 ，即c l + u c 2 为环尺上的线性码。 设c 为r 上生成矩阵为( 3 1 7 ) 式的线性码，则v c = r ( c ) + u s ( c ) c ，均 有，( c ) c l ，s ( c ) c 2 ，故c = ，( c ) + z 锯( c ) c l + u c 2 ，即c c i + u c 2 。 因为lcl ：4 h 2 “，lc l + u c 2l 爿c l1 1c 2i = 2 屯2 毛忆，即lc i 刊c l + u c 2l ，所以 c = c l + u c 2 。 引理3 1 6 设c 是凹( 口) 上 甩，七】线性码，则c 的所有非零码字恰含有后个 不同的深度d l d 2 ，且其相应的深度分布为 d j = 1 f = 0 ， i ，一1 2 1 + 2 厶q + z 2 j , + p - 2 + 2 r + $ - 2 ，f 叱，叱，九) 且f = 叱，= 1 ，二，2 一，毛 ，= i 摹= l 2 卜1 + 2 t + r - 2i e d l ，吒+ 如 d ，九 且f = z ，f l ，2 ，向+ 也) ( i ， ) ，( 时，4 = o 。 第二节环疋+ 幔上的循环码 3 2 1 环最+ u f 2 上的循环码 一个线性码是循环的，如果对v c = ( c oc i ，一，c 川) c ，其循环移动 ( c 开一l ，c o ，c l ，c 月一2 ) 也在c 中。 若c = ( ，c l ，一，c n 1 ) c ，称p ( c ) = c ( x ) = c o + c , l x + + c n _ 1 x 川为码字的多项 式表示，p 可视为r 。到r x 】的一个同构映射。 用r 。表示环r x 】模x ”一1 生成的理想所得商环，即 r 。= r x ( x ”一1 ) 引理3 2 1环r 上长为n 的线性码c 是循环码的充要条件是p ( c ) ( 有时也 称c ) 是震。的一个理想。 证明 如果码c 是心= r m 似刀一1 ) 的一个理想， c ( x ) = + c l x + + 巳一l x 肛1 是任一码字，则x c ( x ) 也是c 中的一个码字，即 ( o n - l 气，c i ，c 帕) c ，所以c 是循环码。 反之，若码c 是循环码，则对每个码字c ( x ) ，都有x c ( x ) 在码c 中，因而， 对一切f ，x c ( x ) 在c 中。因为码c 是线性的，所以对于切多项式a ( x ) 都有 口( x ) c ( 石) c ，因此，码c 是一个理想。 引理3 2 2 如果x ”- 1 = 石办，其中z 是基本不可约多项式，并且两 两互素，则多项式的分解式唯一。 引理3 2 3 设x ”一1 = 石正，其中刀为奇数，z 是基本不可约多项式， 并且两两互素，定义f ，= 石a z 一z + 。f r ，那么在r 。上的理想是( 厂，) 和( u f 。) 的部分和。 引理3 。2 4 设c 是一个长度为奇数n 的循环码，则存在唯一的首项系数为 1 的多项式，g ，| l i 满足c = ( f h ，u f g ) ，其中f g h = x 一一l ，并且ici - 4 蜊g 2 哟。 证明 设x ”- 1 = z ，其中n 为奇数，z 是基本不可约多项式，并且 两两互素，由引理3 2 3 知，码c 是( 厂，) 及( u f ，) 的部分和，通过置换z 的下标， 1 3 第三章环疋+ u v 2 上的循环码 我们假设c 是以下式子的和 ) ，( m ) ，( 厂川) ，( u f 川+ 。) ，( u f + ：) ，( u f ，) 那么 c = ( 石f 2 f k f k + ，+ 。f k + ，+ ：，研 以+ ，以+ ： + ，) = ( 乃，u f g ) 其中 f = z f 2 以，g = f k + 。以+ ：以+ ，h = f k m 。f k 小：，。 定理3 2 5 设c 是足上长为奇数n 的循环码，则c 是尺。的主理想，且存在 唯一一组两两互素的多项式厂，g ，h ，使c = ( f ( h + 甜) ) ，其中x ”一l = f g h ，且 lci _ 4 出8 ( g ) 2 出g ( m 。 证明 由定理3 2 4 知，存在唯一一组两两互素的多项式厂，g ，h ，使得 c = ( 乃，u f g ) ，其中x ”- 1 = f h g ，ici - 4 如g ( s ) 2 出甙们。令厶= ( 乃，u f g ) ，1 2 = ( f i t ，u f ) ， 厶= ( ( 办+ 甜) ) ，由定理3 2 4 知，只要证明1 1 = 1 3 即可。 首先证明x l = 厶。显然厶互1 2 。反之，对v a 1 2 = ( 乃，u f ) ，则存在后，1 ，r x 】 使得 a = 坳+ v u f ( 3 2 1 ) 又因为g ，h 互素，则存在c ，d r x 】，使得曙+ d h = 1 ，则 f = c g 厂+ d h f ( 3 2 2 ) 将( 3 2 2 ) 代入( 3 2 1 ) 得 a = y h + v u ( c g t + a h f ) = ( 七+ u v a ) f l 哩+ v c u f g 即a 厶= ( 乃，u f g ) ，即1 2 i i 。故厶= 1 2 。 下证1 2 = 1 3 。显然，3 厶，只须证厶厶。令6 = f ( h + u ) ，即1 3 = ( 6 ) ， 由于在r 。中x ”- 1 = 0 ，则b g = f ( h + u ) g = x ”- 1 + 堙= f u g ， u b = f ( h + 甜) 甜= 乃甜+ f u 2 = 乃甜，又因为g ，h 互素，所以存在c ，d r x 】，使 砌+ 内= l ， 则u f = c h 矿+ d g u f ， 故u f = ( c u + 幽) 6 ( 6 ) ，又 乃= 6 一u f = ( 1 一c u 一如) 6 ( b ) ，即( 矿，乃) s ( 6 ) ，即1 2c ：z1 3 。故1 2 = 1 3 。 综上得i l = 1 3 ，即c = ( 厂( 厅+ 甜) ) 。 3 2 2 环只+ z 以上循环码的对偶码 定理3 2 6 设码c = ( 乃，垤) 是一个长度为奇数行的循环码，其中，g ，h 为 首项系数为1 的多项式，满足傀= x ”一1 ，icl = 4 4 e g ( g ) 2 , e g ( m ，那么 c 上= ( g 办，u g + f + ) 且ic 上l - 4 d e 掣( y 2 出g ( 们。 其中，g 木和h 。是多项式，g 和h 的互反多项式 证明 由( g h ) ( i l l ，u f g ) 上，( u g f 。) ( f h ，u f g ) 上 1 4 第三章环r + z 幔上的循环码 知( g 而，u g f ) ( f h ，u f g ) 上 又因为 i ( g 办+ ，u g + f ) 1 4 n - , t e g ( g ) - a e g ( h ) 2 ”一蜊伊出反引- - 2 ( j h ，u f g ) 上l 所以 ， c 上= ( 办。厂，咯厂) 推论3 2 7 设c = ( 乃，u f g ) 是一个长度为奇数甩的循环码，其中厂，g ，h 为 首项系数为l 的多项式且满足f g h = x ”一1 ，如果c 是自对偶，当且仅当f = g 和 h ：h 。 3 2 3 环只+ u 6 上的( 1 + ”) 一循环码 定义3 2 1 设c 为r 上长为n 的线性码，若v c = ( c oc l ，一c ) c 均有 ( ( 1 + “弦n - i ，c o ，c 盹) c ，则称c 为r 上的( 1 + “) 一循环码 定理3 2 8足上线性码c 是( 1 + 甜) 一循环码当且仅当p ( c ) 是环 b 。= r x l ( x 厅一( 1 + 甜) ) 的理想，有时也称c 为吃的理想。 证明 设p ( c ) = c f x p ( c ) ，则( ，c l 一，c 川) c ，又由于c 是( 1 + z f ) 一 j = o 循环码，故( ( 1 + u ) c n - ! 铴，c 柚) c ，有 x p ( c ) = ( 1 + “) c ”一i + c o x + c i x 2 + + c h 一2 x 一一1 p ( c ) 所以e ( c ) 为环或的理想。 反之，设尸( c ) 是统的理想，对v c = ( c o ，c l ，一，c 州) c ， 有 p ( c ) ；q x 尸( c ) ，故 i = 0 印( c ) = ( 1 + u ) c n l + c o x + c l x 2 + + c n - 2 x ”_ 1 e ( c ) 从而( ( 1 + 甜) c 川，c o ，c 神) c ，所以c 为( 1 + 材) 一循环码。 定理3 。2 9( 1 ) 对v c ( x ) r 。，n 为奇数，令仃0 ( x ) ) = c ( o + “) x ) ，则仃是 环r 。到环或的同构。 ( 2 ) 若对v c = ( c o ，c l 一，c 川) r ”，令 f ( c ) = ( c o ，( 1 + 材) q ，( 1 + “) 。c j ，( 1 + “) ”_ 1 c 。一1 ) 则r p = p 。1 仃 证明( 1 ) 由于刀是奇数，则有 口( x ) 兰b ( x ) m o d ( x 斗- 1 ) 亡a ( o + “) x ) 三b ( o + u ) x ) m o d ( x ”一( 1 + ”) ) 关于盯对多项式的加法和乘法保持性是自然的，故仃是r 。到最上环同构。 1 5 第三章环e + 峨上的循环码 ( 2 ) v c ( x ) = c o + c i x + + c 。一l x ”1 r 。，则 矽叫( c ( z ) ) = r ( c o ，c i ，c n 1 ) = ( c o ，( 1 + “) c l ，( 1 + ”) q ，( 1 + 甜) ”一c 。一1 ) 又p - 1 仃( c ( x ) ) = p - i l ( c o + c 1 ( 1 + u ) x + + q ( 1 + “) x 。，c 。一l ( 1 + 甜) ”- 1 x 4 - 1 ) = ( c o ( 1 + “) q ，( 1 + 甜) c i ，( 1 + “) ”1 巳一1 ) 故矽一= p - i 盯 定理3 2 10 设c 是r ”的子集，则c 是循环码当且仅当彳( c ) 是( 1 + 甜) 一循 环码 证明由定理3 2 9 ( 2 ) 知，f = p - 1 印是r ”到r ”的环同构，故c 是r 一的 理想当且仅当f ( c ) 是尺”的理想，即c 是循环码当且仅当f ( c ) 是( 1 + 甜) 一循环码。 定理3 2 1 1 设c 是长为奇数刀的( 1 + 甜) 一循环码，则c 是统中由 口( x ) ( c ( x ) + 材) 所生成的主理想，其中x ”一( 1 + 甜) = a ( x ) b ( x ) c ( x ) ， 且 ic | _ 4 d e g b ( x ) 2 她。引。 证明 由于c 是长为疗的( 1 + 甜) 一循环码，则o r 。1 ( c ) 是长为刀的循环码，由 定理3 2 5知， 仃以( c ) = ( f ( h + “) ) ，其中x 厅一1 = f g h ，并且 i 盯1 ( c