（计算数学专业论文）环上码的研究.pdf

环上码的研究 摘要 近年米，j 艮从事编码密码理论的研究者将研冗的兴趣从有限域上的编码密 码理论转移到有限环上，尤其是z 。码的研究，通过g r a y 映射，将z 上的码与 域上二元码联系起来。 本论文主要有以下几点： 第一，作者定义了环z 。 u ( u 一1 ) 上一个g r a y 映射，使得该映射是 z 。 u ( u 。1 ) 到z 。的距离保持映射，并且通过该映射，由z 。 u ( u 1 一1 ) 上的码生 成矩阵可得到g r a y 映射下码的生成矩阵最后，我们得到，如果码c 是环 z 。 u ( u 1 ) 上一个循环码当且仅当它的g r a y 映射像是一个准循环码 第二，作者将码的问题的研究推广的有限环上，得到在z 4 环上循环码的迹表 不。 第三，l i n g s a n 等人 3 4 j 研究了z 。环上的( i p k ) 一线性循环码，定义了一 种g r a y 映射，研究了z p “环上的( 1 一p k ) 一线性循环码在z 。环上g r a y 映射的像。 作者在 3 4 的基础上给出了z 一环上的( 1 - t p 。) 一线性循环码的概念，构造一个 同构映射，使z t 环上的( 1 一p k ) 一线性循环码和z - 环上的( 1 - t p 。) 一线性循环码 之间建立一个环同构映射关系，研究了z 矿，上( 1 一) 一线性循环码的一些性质， 给出了z 。“上( 1 一护。) 一线性循环码的生成多项式及码的个数。 第四，作者在g a l o i s 环g r ( q 。) 上定义了f r o b e n i t l s 映射，并在该环上定 义了迹码和子环子码的概念，得到了g a l o i s 环上的一个码的对偶码的迹码是 该码的子环子码的对偶码 这些内容的研究对进一步丰富纠错码在环上的理论及构造一些性能较好的 码都有一定的指导意义。 关键词： 线性码循环码准循环码g r a y 映射z 码 t h e s t u d y o fc o d e so v e rr i n g a b s t r a c t i nr e s e n ty e a r s t h et h e o r yo fr i n go fc o d i n ga n dc r y p t o g r a p h yi s t h ek e yf o r r e s e a r c h e ri nc o d i n ga n dc r y p t o g r a p h y i np a r t i c u l a r ，t h es t u d y o fc o d eo v e rz 4 i nt h i sp a p e r ，t h em a i nr e s u l t sa r et h ef o l l o w i n g ： 1 w ed e f i n eag r a ym a p o v e rz p u ( u m - 1 ) ，a n d t h e g r a ym a pi s a n i s o m e t r yf r o m ( z 口【u 】( u m 1 ) ，d o ) t o ( z p ”，d h ) m o r e o v e r ，i fg i sag e n e r a t o rm a t r i x o fac o d eco v e rz 。 n ( u m - 1 ) ，t h e nag e n e r a t o rm a t r i xo f ( c ) c a nb eo b t a i n e d a n e c e s s a r y a n ds u f f i c i e n tc o n d i t i o n f o r t h e g r a yi m a g e o f c y c l i c c o d et ob e q u a s i - c y c l i ci sg i v e n 2 l e tz 4b et h ei n t e g e r sm o d u l o4 ，t h en o t i o no fc y c l i c c o d e so v e rz 4i s i n t r o d u c e d w ep r o v i d eat r a c ed e s c r i p t i o no f s u c h ac o d e 3 a r i n gi s o m o r p h i s m b e t w e e nl i n e a r ( 1 一p ) 一c y c l i c c o d e sa n dl i n e a r ( t - 啦) c y c l i c c o d e so v e r z 一，、i s c o n s t r u c t e di n t h i s p a p e r w es t u d y t h e ( 1 一t p 。) c y c l i cc o d e sa n dp r o d u c t t h eg e n e r a t o ro f ( 1 一t p ) 。c y c l i cc o d e so v e r z 一一 4 w ed e f i n eaf r o b e n i u sm a po v e rg a l o i s ，t r a c ec o d e sa n ds u b r i n gs u b c o d e w e p r o v et h et r a c eo f d u a lc o d e so v e rg a l o i si st h ed u a lc o d e so fs u b r i n gs u b c o d e a l lt h er e s u l t sa r ev e r yi m p o r t a n tf o rt h es t u d yo ft h ee r r o rc o r r e c t i n gc o d e s o v e rr i n g s k e y w o r d s ：l i n e a rc o d e s ，c y c l i cc o d e s ，q u a s i c y c l i cc o d e s ，g r a ym a p ，z 4 c o d e s 独创性声明 研究成果，也不包含为获得盒目b 王k 杰堂 或其他教育机构的学位或证书而使用过的材 擀瓤柳期：中如防 学位论文版权使用授权书 本学位论文作者完全了解金胆工些杰堂有关保留、使用学位论文的规定，有权保留 并向匡】家有关部门或机构送交论文的复印件和磁盘。允许论文被查阅或借阅。本人授权盒 磐：e 些厶堂可以将学位论文的全部或部分论文内容编入有关数据库进行检索，可以采用影 印、缩印或扫描等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后适用本授权书) 学位论文者签名 签字日期 卅f 月 学位论文作者毕业后去向： 工作单位： 通讯地址： 导师 签字 邮编 致谢 在这三年的研究生学习阶段，我的导师朱士信教授不仅在学业上对我进行 耐心的指导，而且还在生活上给予我很大的帮助。朱老师严谨的治学态度、宽 广的胸怀和豁达的处世之道，都是学生学习的楷模。在此，作者向导师致以最 诚挚的敬意和衷心的感谢! 在本人学习期间，还得到了苏化明教授、程f 杰老师、刘丽老师、钱开燕 等很多老师的热心的关怀和无私的帮助，在此，向各位老师表示深深的谢意。 最后，感谢父母和兄弟多年来的大力支持和照顾，感谢我的爱人张莉娜， 在我研究生学习阶段对我提供的物质帮助和精神鼓励。正是家人多年来默默的 奉献和周到的照顾，才使我解除了后顾之忧，从而全身心的投入到学业中去。 作者：钱建发 2 0 0 4 年4 月 第一章绪论 1 9 4 8 年s h a n n o n 在他的开创性论文“im a t h e m a t i c a lt h e o r y o f c o m m o n i c a t i o n ”中，首次阐明了在有扰信道中实现可靠通信的方法，提出了 著名的有扰信道编码定理，奠定了纠错码的基石。自此以后h a m m i n g ，s 1 e p i a n ， p r a n g e 等人在5 0 年代初，根据s h a n n o n 的思想，给出了一系列设计好码和有 效译码的方法。以后，纠错码受到了越来越多的通信和数学工作者，特别是数 学家的重视，使纠错码无论在理论还是在实际中都得到飞速发展。 迄今，纠错码已有4 0 年的历史，其发展过程大致分为以下几个阶段。 5 0 年代至6 0 年代初，主要研究各种有效的编，译码方法，奠定了线性分组 码的理论基础：提出了著名的b c h 码。译码方法以及卷积码的序列译码：给出 了纠错码的基本码限。这是纠错码从无到有得到迅速发展的年代。 自6 0 年代至7 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 码，所能达到的性能，这是 纠错码历史上具有划时代意义。在这期间大规模集成电路和微机的迅速进展， 为纠错码的实用打下了坚实的物质基础，因而与实用相关的各种技术及有关 问题得到了极大关注，并在实用中取得了巨大的成功。 自8 0 年代初以来，g o p p a 等从几何观点讨论分析码，利用代数曲线构造了 一类代数几何码，在这些码中，某些码的性能达到了s h a n n o n 码所能达到的性 能。由于代数几何码是一类范围非常广的码，在理论上己证明它具有优越性能， 因而一开始就受到了编码理论工作者，特别是代数几何学家的重视，使代数 几何码的研究得到了非常迅速的进展，取得了许多成果。现在，代数几何码的 研究方兴未艾。自7 0 年代末以来，纠错码技术已开始渗透到很多领域。利用 纠错码中的许多编，译码原理和方法，与通信系统中的其它有关技术相结合， 得到了令人惊喜的结果。例如，纠错码与调制技术相结合所产生的t c m 技术， 已作为国际通信中标准技术而推广使用。又如纠错码与密码相结合，可以构造 出一类既能加密。签名，又具有纠检错功能的密码系统：纠错码与信源编码相 结合的结果，使得通信系统更为有效与可靠。不仅如此，纠错码中的许多译码 思想和方法，与神经元网络中的能量函数有密切关系，纠错码的许多译码技 术，可以用来解决神经元网络中的一些问题。因此，可以预料，随着科学的进步 和实际的需要，纠错码理论必将进一步发展，它的应用范围必将进一步扩大a 1 2 本文主要工作及意义 本论文是在朱士信教授的悉心指导下及部分课题在安徽省自然科学基金 ( 0 3 0 4 2 2 0 1 ) 的资助下完成的。 作者主要做了以下几个方面的工作。 第一，作者定义了环z 。 u ( u 一1 ) 上一个g r a y 映射，使得该映射是 z 。 u ( u “一1 ) 到z 。的距离保持映射，并且通过该映射，由z “u ( u 。1 ) 上的码生 成矩阵可得到g r a y 映射下码的生成矩阵。最后，我们得到，如果码c 是环 z 。 u ( u 。一1 ) 上一个循环码当且仅当它的g r a y 映射像是一个准循环码。 第二，作者将码的问题的研究推广的有限环上，得到在z t 环上循环码的迹 表示。 第三，l i n g s a n ”研究了z 。环上的( 1 一p ) 一线性循环码，定义了一种g r a y 映射，研究了乙。环上的( 1 一p ) 一线性循环码在z ，环上g r a y 映射的像。作者 在 3 4 的基础上给出了乙。环上的( 1 - f p ) 一线性循环码的概念，构造一个同构 映射，使z ，环上的( 1 - p ) 一线性循环码和z ，“环上的( 1 - t p 。) 一线性循环码之间 建立一个环同构映射关系，研究了z 一。上( 1 - t p + ) 一线性循环码的一些性质，给 出了z 一- 上( 1 一t p 2 ) 一线性循环码的生成多项式及码的个数。 第四，作者在g a l o i s 环g r ( q ”) 上定义了f r o b e n i u s 映射，并在该环上定 义了迹码和子环子码的概念，得到了g a l o i s 环上的一个码的对偶码的迹码是 浚码的子环子码的对偶码。 这些内容的研究对进一步丰富纠错码在环上的理论及构造一些性能较好的 码都有一定的指导意义。 2 1 线性分组码 2 1 1 分组码的基本概念 第二章纠错码简介 分组码是把信源输出的信息序列，以k 个码元划分为一段，通过编码器把 这段k 个信息元按一定规则产生r 个检验元，输出长为n = k + r 的一个码组。因 此每一码组的校验元仅与本组的信息元有关，而与别组无关。分组码用( n ，k ) 表示，r l 表示码长，k 表示信息位。 定义2 1 1 1 分组码是对每段k 位长的信息组，以一定规则增加r = n k 个 校验元，组成长为n 的序列：( c 。一c ：，c ，c 。) ，称这个序列为码字。 n 长序列的可能排列总共有2 “种，而( n ，k ) 分组码的码字集合只有2 “种。 所以，分组码的编码问题就是定出一套规则，以便从2 “个n 重中选出个2 。码字 不同的选取规则就得到不同的码。我们称被选取的2 。个n 重为许用码组，其余 的2 ”一2 “个为禁用码组。 称r = k n 为码率，表示( n ，k ) 分组码中，信息位在码字中所占的比重。r 是 衡量分组码有效性的一个基本参数。 定义2 1 1 2两个n 重码x ，y 之间，对应位取值不同的个数，称为它们之 间的汉明距离，用d ( x ，y ) 表示。 定义2 1 1 3n 重码字x 中非零码元的个数，称为它的汉明重量，简称 重量，用w ( x ) 表示。 例如，若x ：( 1 0 1 0 1 ) ，则w ( x ) = 3 。若y ：( 0 1 1 1 1 ) ，则w ( y ) = 4 ，等等。 定义2 ，1 1 4( n ，k ) 分组码中，任两个码字之间距离的最小值，称为 该分组码的最小汉明距离d 。，简称最小距离 d 。= m i n d ( x ，y ) lx ，y ( n ，k ) j d 。是( f i ，k ) 分组码的另一个重要的参数。它表明了分组码抗干扰能力的大 小。 下面的定理说明了( n ，k ) 分组码中的最小汉明距离d 。( 今后简称d ) 与纠错 能力的关系。 定理2 1 1 1 【3 ”任一( n ，k ) 分组码，若要在码字内： ( 1 ) 检测e 个随机错误，则要求码的最小距离d e + l ， ( 2 ) 纠正t 个随机错误，则要求码的最小距离d 2 t + l ， ( 3 ) 纠正t 个随机错误，同时检测e ( t ) 个错误，则要求d t + e + l ， ( 4 ) 纠正t 个错误和p 个删除，则要求d 2 t + p + 1 。 2 1 2 线性分组码 一个 n ，k 线性分组码，是把信息划成k 个码元为一段，通过编码器变成 长为n 个码元的一组，作为 n ，k 线性分组码的一个码字。若每个码元的取 值有q 种( q 为素数幂) ，则共有q “个码字。n 长的数组共有q “组，显然。q “个 n 维数组组成一个g f ( q ) 上的n 维线性空间。如果q “个码字集合构成了一个k 维线性子空间，则称它是一个 n ，k 线性分组码。 定义2 1 2 1 1 1 ，k 线性分组码是g f ( q ) 上的n 维线性空间v 。中的一个 k 维线性子空间v 。 由于该线性子空间在加法运算下构成阿贝尔群，所以线性分组码又称为 群码。 为简单起见，今后若没有特别说明，所说的分组码均指线性分组而言，且 用( c 。c ：，c ，c 。) 表示 n ，k 码的一个码字，其中每一个分量c ：g f ( q ) 。 由于线性分组码是分组码的一类，因此有关分组码的参数，如码率，码 字的距离与码的最小距离，码字的重量等定义，以及说明最小距离与纠错能 力之间的定理2 1 1 1 ，对线性分组码均适用，这里不再重复。 显然，r 和d 是分组码的两个最重要的参数，因此今后我们用 r l ，k ，d ( 或 n ，k ) 表示线性分组码。而用( n ，m ，d ) 表示数目为m 的任何码。 n ，k ，d 分组码是一个群码，因此若码字c n ，k ，d ，c 。 n ，k ，d ， 则由群的封闭性可知，码字c 。与c 。之和c 。+ c ： n ，k ，d ，即c 。+ c 。也必是 n ，k ， d 分组码的一个码字。所以，两码字c 。和c ：之间的距离d ( c ，c 。) 必等于第三个 码字c + c ：的汉明重量。 因此，一个 n ，k ，d 分组码的最小距离必等于码中的最小重量，由此可 得知下定理。 定理2 1 2 p ” n ，k ，d 线性分组码的最小距离等于非零码字的最小重 量。 d = m i n ( w ( c ，) lc 。 n ，k 2 2 码的一致校验矩阵与生成矩阵 2 2 1 码的一致校验矩阵与生成矩阵 n ，k ，d 分组码的编码问题就是在n 维线性空间v 。中，如何找出满足一 定要求的，有2 。个矢量组成的k 维线性子空间v 。或者说，在满足给定条件 下，如何从已知的k 个信息元求得f = l q k 个校验元。这相当与建立一线性方程组 已知k 个系数，要求n k 个未知数，使得到的码恰好有所要求的最小距离d 。 一般情况下，任何一个i n ，k ，d 码的一致检验矩阵h 可表示为 h = h i ，i h 2 一i h 】 2 h 2n 一2 h 1 。 h 2 o h 。t ，】曩h 一2 也。 它是一个( n k ) r l 阶矩阵。由此h 矩阵可以很快地建立码的线性方程组： 简写为 旦圮 n i , n - 1 n 2 , n - i m p i 一2 矗2 。一2 曩，_ 。一2 h c 7 = 0 7 c h - - 0 h 】o h 2 ，o h h io c ”一l p 2 ： 0 7 可知h 矩阵的每一行代表一个线性方程组的系数，它表示求一个校验元线性方 程。因此任何一个 f l ，k ，d 码的h 矩阵必须有n k 行，且每行必须线性独立。 若把h 的每一行看成一个矢量，则这n k 个矢量必然张成了维线性空间中的一 个n k 维子空间v 。 由于 n ，k ，d 码的每一个码字必须满足( 1 ) 式。即它的每一个码字必然在 由h 矩阵的行所张成的v 。一。空间中的零空间中。显然v 。一t 的零空间必然是一个 k 维子空间v 。，面这正是 n ，k ，d 码的码字集合全体。所以，v 。一与 1 2 ，k ， d 码的每一个码字均正交，也就是h 矩阵的每一行与它的每一个码字的内积 均为零。 n ，k ，d 分组码的个码字组成一个维子空间，因此这个码字完全可以由 个独立矢量所组成的基底而张成。设基底为 若把这组基底写成矩阵形式 c 1 = ( g l , n - i , g i ”2 ， c 2 = ( 9 2 。一1 ，9 2 。一2 ， q = ( g 十g 女肿，。 则有 蹦 甜 ， ， ， g g t ，p i g 2 ，。一1 g k ，n 一1g k ， 一2一g k 0 n ，k ，d 码中的任何码字，都可由这些基底的线性组合生成，即 gj 一 9 2 肛 9 1 ，2 g z ”一2 g l ，0 9 2 ，0 g k 。一ig k ，。2一g k ，o f 1001110 f g = j0 10 0111 i l 0 01 1101 1 i 1o o1t10 i 1 0 o11lol l 2 2 2 对偶码 n ，k ，d 码是n 维线性空间中的一个k 维子空间v 。，由一组基底即g 的 行张成。由前可知，它的零空间必是一个n - k 维的线性子空间v 。并由n k 6 个独立矢量张成。由( 3 ) 和( 4 ) 可知，这n k 个矢量就是h 矩阵的行。因此，若 把h 矩阵看成是 n ，n k ，d 码的生成矩阵g ，而把 n ，k ，d 码的g 看成 是它的校验矩阵h ，则我们称由g 生成的 n ，k ，d 码c 与由h 生成的 n ，n k ， d 码c 上互为对偶码。相应地，称v 。与v 。一。空间互为对偶空间。由此可以定 义对偶码。 定义2 2 2 1 设c 是 n ，k ，d 码，则它的对偶码c 。l 是 cj 。= x v 。i 对所有y c ，有x y = 0 ) 式中，x y 为x 与y 的内积。 例如，h a m m i n g 7 ，4 ，3 码，它的对偶码必是 7 ，4 ，3 码，其生成矩阵g - 一 就 是 7 ，3 ，4 码的校验矩阵h 。】 10110 o o 11l010 o l1o 0 0l0 0l100 01 若一个码的对偶码就是它自己，即c j - = c 则称c 码为自对偶码。显然，自对 偶码必是 2 m ，m ，d 形式的分组码。 2 3 线性码的纠错能力 研究码的纠错能力，也就是分析码的n ，k ，d 之间的关系，不仅能从理论 上指出哪些码可以构造出，哪些码不能构造出，而且也为工程实验提供了各种 码性能估计的理论依据。因此，研究码的纠错能力始终是编码理论中一个重要 的课题。在s h a n n o n 的信道编码定理中指出，仅当分组码的n 趋向于* 时，译 码错误才能任意地接近于零。因此，研究n - - - o 。时的渐进性能，具有特别重大 的理论意义。 本节将介绍某些基本的分组码距离的上，下限，其结果比较简单。 定理2 3 1 ”1p l o t k i n 限g f ( q ) 上( n ，m ，d ) 分组码的最小距离d 为 d n m ( q - 1 ) ( m 一1 ) q 定理2 3 2 “3h a m m i n g 限长为n 纠t 个错误的q 迸制分组码的码字数m 为 m o o 时，比较这3 个限所表示的之间的关系( 只限于二进制码) ： ( 1 ) 当n - - o o 时有p l o t k i n 限可推出 k n l - 2 d n ( 2 ) 由h a m m i n g 限可得到 k n 1 一h 2 ( d 2 n ) ( 3 ) 由v - g 限可导出 k n 卜h ：( d n ) 式中 h 2 ( x ) = 一x l o gz x 一( 1 一x ) l 0 9 2 ( 1 一x ) 由上面的关系式可以看出，当n ，d 给定时，p l o t k i n 限和h a m m i n g 限给 出了传信率r 的上限，而v g 限提供了r 的下限。当n ，k 给定时，p l o t k i n 限 和h a m m i n g 限给出了最小距离d 的上限，而v g 限给出了最小距离d 的下限。 在相同条件下，最小距离越接近于上限的码越好。 8 0 年代初g o p p a 把分组码看成是射影平面上的曲线，从而把代数几何引入 了分组码的构造。1 9 8 2 年，t s f a s m a n 等人利用模曲线构造了类代数几何码， 当q 4 9 时，其性能超过了v g 限，这具有重大的理论意义，说明从理论上讲， 利用代数几何方法可以构造出s h a n n o n 码。但是，正如同g o p p a 码所遇到的困 难一样，当n _ o o 时，如何构造这类码已及如何译码，都没有完全解决。这说明 如何具体地构造s h a n n o n 码仍然是一个没有解决的问题，也是当前编码理论研 究的热门课题之一。 2 4 循环码与理想 2 4 1 基本概念 循环码是一类最重要的线性码，它具有严谨的代数结构，其性能易于分析。 特别是目前已发现的大部分线性码与循环码有密切关系，它们之中的大部分码 都可以归结于循环码。另外，循环码具有循环的特性，编译码电路，特别是编码电 路简单易于实现。 因此循环码特别引人注目，对它的研究也比较深入和系统。 定义2 4 1 1 一个n 重子空间v ，若对任何一个v = ( a 。，a 。，a 。) v ， 恒有v l = ( a 。a 。，a 。，a ) v ，则称vn k 为循环子空间或循环码。 2 4 2 码的多项式描述 显然，g f ( p ) 上的所有n 重构成一个线性空间v 。，其中每个矢量是分量取自 g f ( p ) 上n 重，若将每个n 重和系数取自g f ( p ) 上的多项式相对应： r l 重：( a 川，a 。喝，a 。)a j g f ( p ) 多项式：( a x 几- 1 + a x r 2 + + al x + a # ) = f ( x ) 则它们之间建立了一一对应关系。由f i n i t ef i e l d 知，所有次数小于n 次的多 项式一定在模n 次多项式f ( x ) f 。 x 的不同剩余类中，即 f ( x ) e l n - t x “叫+ a 。一2 x “叫+ + a i x + a o )( m o df ( x ) 因此，v 。中每一个n 重都与g f ( p ) 上的次数低于n 次的一个多项式相对应，并必 在模f ( x ) 的某一剩余类中。有f i n i t ef i e l d 知，在模f ( x ) 运算下，模f ( x ) 的 剩余类构成一多项式剩余类环f 。( x ) f ( x ) ，若在该环中再定义一个数乘，即 c a ( x ) =c a x n _ 1 + c a 删xn _ 2 + + c a i x + c a o )c g f ( p ) 则可以证明模f ( x ) 的剩余类构成一个n 维线性空间，称为剩余类线性结合代 数。 在 n ，k 循环码中，码字( a 。a “，a 。) 的多项式表示为a ( x ) = a 。x ”1 + a x ”2 + + a 。x + a 。它的循环移位一次后所得码字为( a 。a 。，a 。，a 。) ， 相应的码多项式表示为 a 】( x ) = a n - 2 x ”1 + + a o x + a n 1 相当于a ( x ) 乘以x 后，用f ( x ) = x 。- i 取模： x a ( x ) = a 铲l x “+ a 。一= x “叫+ + a o x 兰a - 2 x r l + + a o x + a 。，i( m o dx “一1 ) 因为在模x “一1 情况下，x “s l 。 定理2 4 2 1 ”1 以多项式x ”1 为模的剩余类线性结合代数中，其一个子空间 v m 是个循环子空间( 循环码) 的充要条件是：v 。是一个理想。 由上面定理可得到如下结论：一个循环码是模x - 1 多项式剩余类线性结合 代数中的一个理想。反之，其中的一个理想必是一个循环码。 定义2 4 2 1 生成多项式是模剩余类代数中，一个理想的次数最低的非零 首一多项式，它是理想或循环码的生成元。 9 定理2 4 2 2 “1 g f ( p ) 上的 n ，k 循环码中，存在有唯一的n k 次首一多项 式g ( x ) - - - - x ”。+ g n - k - i x ”1 + + g 。x + g 。，每一个码多项式c ( x ) 都是g ( x ) 的倍式，且每 一个( n 1 ) 次的g ( x ) 倍式一定是码多项式。 下面讨论主理想生成元应满足的条件。 定理2 4 2 3 ”3g f ( q ) 上 n ，k 循环码的生成多项式g ( x ) 一定是x “l 的因 式：x 。1 = g ( x ) h ( x ) 。反之，若g ( x ) 为n k 次，且g ( x ) l ( x “一1 ) ，则该g ( x ) 一定生 成一个 n ，k 循环码。 2 4 3 循环码的生成矩阵和校验矩阵 由前面知，x “一l = g ( x ) h ( x ) 。若g ( x ) 为n k 次，则h ( x ) 为k 次多项式。以g ( x ) 作为生成多项式所组成的 n ，k 循环码中g ( x ) ，x g ( x ) ，x g ( x ) 等k 个码多 项式必是线性无关的，设可以由这些码多项式所对应的码字，构成循环码的生成 矩阵g 。则 g 。一g 。一一l 9 1g o 0 t 0 0 g 。一i 9 2g lg o 0 - 0 0 0 0 g ，tg 。一一l - g l g o 如果h ( x ) = h - x “+ + h ，x + h 。，则 n ，k 循环码的一致校验矩阵 h oh i h k 0 0 0 h oh l 0 0 00 0h o h 1 玩 容易验证 g h 7 = o 所以，我们称h ( x ) = ( xn - - 1 ) g ( x ) 为码的校验多项式。 2 4 4 循环码的深度分布 令v 。( q ) 为域g f ( q ) 上n 维线性空间，有映射 d ：v 。( q ) _ v 。( q ) 称作微分，定义如下： d ( x i ，x 2 ，x 。) = ( x z - x l ，x 3 - x2 ，x n - x 。一1 ) 容易验证d 是一个线性映射，即对x ，y v 。( q ) 和2 g f ( q ) ，有 d ( x + y ) = d ( x ) + d ( y ) ，d ( 五x ) = 五d ( x ) 对五g f ( q ) ，我们记 ” = ( 五，五，五，2 ) 为长度为m 的一排五向量 定义2 4 4 1 向量x 的深度d e p t h ( x ) 是最小的整数i ，使得d 1 x = 0 】o 如果没有这样的i ，则x 的深度就定义为n 显然向量x g f ( q ) 的深度为i ，当且仅当对某一非零元素五g f ( q ) ，有 d i - , x = 咒”1 。 定义2 4 4 2 对g f ( q ) 域上 n ，k 线性码c ，令d 为深度为i 的码字的数 量，数d 。，d ，d 称为码c 的深度分布。 定义24 4 3 对g f ( q ) 域上 n ，k 线性码c ，指数集合 i l i n ，d 0 称为码c 的深度谱 一序列( 有限或无限) 微分被许多作者讨论过 1 2 - 1 3 ，而且同序列的复杂度建 立联系。深度分布作为线性码的个新的特征被e t z i o n 研究过。e t z i o n 1 2 q b 得 到 n ，k 线性码的一个非零码字的深度分布正好是k 的非零的值组成。码的生成 矩阵能够从有k 个不同的深度的码字生成，并讨论了一些著名的线性码的深度 分布，例如汉明码，扩展的汉明码和一阶r e e d m u l l 码。 c h r i s 5 m i t e h e l l 在 1 3 中线性循环码的深度分布。 引理2 4 4 p 3 1 假设c = ( c 。，c “，c 。) 是一个长度为n 的二元码字，对应 的多项式为c ( x ) = c 。x ”+ c ，x ”。十+ c 。，那么d c 的n - i 个元素等于多项式 c ( x ) ( x - 1 ) 1m o d ( x “- 1 ) 的前n - i 项。 引理2 4 4 2 假设c 是一个长度为n 的二元线性循环码，l 不是它的码字， 假设一个非零码字的0 游程最大长度是l ，那么所有非零码字有至少是n l l 的深度。 证明：假设x 是c 中一个非零码字，令s = n - l l ，由于c 是一个线性循环 码，x 1 jd x 0 ，d x 等于一个码字n 一1 的比特，那么通过归纳法可知d 5 x 等于一 个非零码字的n s 个连续比特。 而且d8 x 的n s 连续比特不能全为零，由于n s = l + 1 l 。因此x 的深度大 于s = n l l 。故引理得证。 定理2 4 4 3 如果i ( x ) 是一个 n ，k 线性循环码c 的生成多项式，( x 一1 ) 不能整除( x - 1 ) g ( x ) ，那么c 的深度谱为f n ，f l - 1 ，n k + 1 ) 证明：由条件知，该循环码的一个码字如果包含一个长度为k 的o 一游程， 那么它必须是非零码字由于( x 一1 ) 不能整除( x - 1 ) g ( x ) ，那么1 不是c 的一个 码字，由引理可知，c 的深度谱为 r l ，n l ，n k + 1 ) y u a n l u o ：同样研究了线性码的深度分布，而且给出了r e e d m u l l e r 码的深 度分布，得到了3 元 1 1 ，6 ，5 g o l a y 码的9 个深度等价类。 2 4 5 退化循环码的深度分布 定义2 4 5 1 域f 。上长度为n ：m l 的线性码c 称为是退化循环码，如果它 的生成多项式为g ( x ) = ( g ( x ) ，g ( x ) ，g ( x ) ) ，这里g ( x ) 是循环码的生成多项 式。 对于一个码的深度分布，我们有下面的算法 a lg or i t h m a ：令v = ( v - ，v 2 ，“，v 。) 是一个长度为n 的二元字，令r 为使 2 n 成立的最大整数，令v + = ( v - ，v 。，v 2 ，) ，u = ( v t + v2 ，+ 】，v v2 ，+ 2 ，v 。+ v “) 、 我们如下计算函数d ( v ) ： 如果v = 0 “ ，那么d ( v ) = 0 如果v = 1 “ ，那么d ( v ) ：1 如果u = 0 ”27 ，那么d ( v ) = d ( v + ) 如果u 0 ”2 7 ，那么d ( v ) = 2 + d ( u ) 引理2 4 5 p 2 1 如果v = ( v 。，v 矿”，v 。) 是一个长度为n 的二元字，那么在 a l g o r i t h ma 中，我们有d ( v ) = d e p t h ( v ) 定理2 4 5 2 如果v = ( v ，v ：，v 。) = ( v ，v 。，v ，v 。，v ：，v 。， v l ，v z ，v m ) ，n 2 m l ，m = 2 ，r 0 ，是一个二元字，w = ( v 。，v ：，v 。) ，那么 d e p t h ( v ) ：d e p t h ( w ) 证明：由于 m 2 2 7 ，那么v + = ( v 】，v 。，v2 。) ，而且u = ( v - + v2 。“，v ：十 v 2 一+ 2 ，v n + vm “) 5 ( v + v t ，v z + v z ，v 。+ v 。) = o “7 因此我们有 d e p t h ( v ) = d e p t h ( v ) 由归纳法可知d e p t h ( v ) = d e p t h ( w ) 引理2 4 5 3 m 假设( x 一1 ) 5j ( x “一1 ) ，令c 是一个i n ，s 线性循环码。那么 c 的生成多项式为( x ”一1 ) ( x 1 ) 。当且仅当c 的深度谱为( 1 ，2 ，s 在下面的引理中，我们用j 记为正好整除，即a ( x ) 。| jb ( x ) 当且仅当a ( x ) r b ( x ) 而a ( x ) 1 不能b ( x ) 引理2 4 5 4 假设c 是一个 n ，k 线性循环码，g ( x ) 为c 的生成多项 式，d e g ( g ( x ) ) = n k ，那么( x 一1 ) 8 | | ( x - 1 ) g ( x ) 当且仅当c 的深度谱为 1 ，2 ，s ) u n ，n 一1 ，n k 十s + 1 ) 下面我们有以下结论 定理24 5 5 令c 为长度为n = m l 的退化循环码，如果生成多项式为 g ( x ) 5 ( g ( x ) ，g ( x ) ，g ( x ) ) ，这里g ( x ) 是长度为】的循环码c 。的生成多项式， 且m = 2 。，则c 的深度谱与c 相同。 证明：由定理2 。4 。5 。2 及退化循环码的定义可知，该结论是成立的。 2 4 6 系统码的生成 用式( 2 4 3 1 ) 矩阵生成的循环码，并不是系统码，系统码的g 矩阵为 g = i 。p 左边是k 阶单位方阵。这相当于码字多项式的第n 一1 次至n k 的系数是信息位， 而其余的为校验位，这相当于 c ( x ) = i l l ( x ) x n - k + r ( x ) i 0( m o dg ( x ) ) 式中 i l l ( x ) = m k 一1 x 卜1 + m h x 卜。+ + m i x + m o 是信息多项式，( i j l 。，m 。m 。) 是信息位，而 r ( x ) = r n - k - i x n - k - i + r n - k - 2 x “一一2 + + r i x + r o 是校验多项式，相应的系数是码元的校验位。由上式可得 一r ( x ) = c ( x ) + i l l ( x ) x n - k - i - - 1 1 1 ( x ) x “一“( m o dg ( x ) ) 所以要构造用g ( x ) 生成的系统码，首先必须将信息组乘以x ”“变成x n - k 【( x ) ：然 后，用g ( x ) 除，得到余式r ( x ) ；再将其各项系数取加法逆元，就得到了所要求 的校验位。因此，循环码系统码的编码问题就是以g ( x ) 为模的除法问题。 由g = i - p 可知，信息组的基底矢量是：( 1 0 0 0 ) ，( 0 1 0 0 ) ，( o o 0 1 ) ， 相应的信息多项式分别是：m ( x ) = x ”1 ，m 。( x ) = x “2 ，n l 。( x ) = 1 。与这些信息多 项式相应的校验多项式分别为：r 。( x ) 2 x 。k x ”( m o dg ( x ) ) ，r ：( x ) 一x ”。x ”2 ( m o d g ( x ) ) ，r 。( x ) s x ”1 ( m o dg ( x ) ) 。一般写成 r i 5 x 。 k x “1 = x ”1 ( g ( x ) )i = l ，2 ，k 与此相应的码多项式为 g ( x ) q ( x ) = c i ( x ) = x ”1 一r ，( x )i = 1 ，2 ，k 共k 个，它们的系数就组成了系统码g 矩阵的行。 1o 01 0 一k ( x ) 0 一k 2 ( x ) 式中，k ( x ) 表示r ( x ) 系数。因而，校验矩阵h 可由上式立即得到 h = 一p i = k ( x ) 1k ：( x ) k 。( x ) 7 i 。 这说明h 矩阵的前k 列是r 。( x ) 一x ( m o dg ( x ) ) ( i = l ，2 ，k ) 的系数。而 后n - k 列是x ”，x ”2 ，xo 的系数，由于它们的次数均小于g ( x ) 的次数，所 以它们被g ( x ) 取模以后仍不变。因此可把上式写成 h = 一p i 。 = k 。( x ) k 。( x ) 1 k 。( x ) 7i 。( 2 4 4 2 ) ( 2 4 4 1 ) 式和( 2 4 4 2 ) 式就是循环码的系统码形成的g 矩阵和h 矩阵的一般 表示式。 例2 4 1 二进制 7 ，4 码的g ( x ) = x 3 + x 2 + 1 ，求系统码g 和h 矩阵。 r l ( x ) 5 x 8 i x 2 + x( m o dg ( x ) ) r z ( x ) 2 x 。5 x + 1( m o dg ( x ) ) b ( x ) ；x4 5 x2 十x 十l ( m o dg ( x ) ) r4 ( x ) i x a 5 x2 + 1( m o d g ( x ) ) 在g f ( 2 ) 上，元素的逆元就是它自己，所以 g l0 oo110 oloool1 001o111 0o ol10l r 101i h = i1110 l0 0 01 2 5 由生成多项式的根定义循环码 = i , p 循环码是模x “一1 剩余代数中的一个以g ( x ) 作生成元的理想，每一个码多 项式都是g ( x ) 的倍式。因此g ( x ) 的根亦必是所有码的多项式的根，基于这一点， 我们可以从根定义循环码。 设码的生成多项式 g (