（应用数学专业论文）关于环f2uf2上线性码的研究.pdf

关于环r + 峨上线性码的研究 捅要 本文重点研究了环e + 蛾上线性码、循环码及其( 1 + “) 一循环码的一些性 质，主要分为如下几个方面： 第一，利用环只+ “只上线性码c 的生成矩阵及其g r a y 映射，得到了该线 性码c 的对偶码c 1 及其g r a y 象西( c ) 的生成矩阵，并证明了该环上线性码的 g r a y 象m ( c ) 与其对偶码的g r a y 象巾( c 1 ) 仍是二元对偶码。 第二，定义了该环上线性码李重量分布的概念。并利用其g r a y 象及其对偶 码的重量分布的关系而得到了该环上线性码与其对偶码的各种重量分布之间 m a c w i l l i m a s 恒等式。 第三，定义了该环上( 1 + ) 一循环码的概念，并利用其与该环上循环码的关 系，而得到了( 1 + z ，) 一循环码的结构。 第四，证明了该环上( 1 + “) 一循环码的g r a y 象仍是二元循环码，并由( 1 + “) 一 循环码的生成多项式而得到了其g r a y 象码的生成多项式。 第五，通过n e c h a e v e 变换，定义了n e c h a e v e g r a y 映射，证明了该环上循 环码在n e c h a e v e g r a y 映射下的二元象是循环码，并由此讨论了该环上循环码 和其剩余码及挠码的关系。 第六，定义了该环上码字深度的概念；得到了计算码字深度的算法；讨论了 该环上线性码及其循环码的深度分鄱。 关键词：环+ “；m a c w i l l i a m s 恒等式； ( 1 + “) 一循环码：g r a y 映射 深度分布 o ns t u d yo fl i n e a rc o d e so v e r r j n g e + “r a b s t r a c t i nt 1 1 i st h e s i s ，p r o p e r t i e so fl i n e a rc o d e s ，( 1 + u ) 一c y c l i ca n dc y c l i cc o d e so v e rf 2 + u f 2a r e d i s c u s s e d t h em a i nc o n t e n t sa r ea sf o l l o 、搬： f i r s t l y b a s e do nt h eg e n e r a t o rm a t r i xo fl i i l e a rc o d e sco v e rf 2 + u f 2a n dg r a ym a p ，m e g e n e r a t o rm a t r i x e so ft h ed u a lc o d e sc 上a n dt h eg r a yi m a g e s 中( c ) o ft h el i n e a rc o d e sc a r ep r e s e n t e d b e s i d e s ，t l l ep r o p o s i t i o nt h a tl i n e a rc o d e s 由忙上ja r et h ed u a lc o d e so f 中归) i ss h o w e d s e c o n d l y ，t h ec o n c e p to fl e ew e i g h td i s t r i b u t i o no v e rt h ef b r e s a i dr i n gi sd e f i n e d t h e nt h er e l a t i o n s h i pb e t w e e ng r a yi m a g eo ft h el i n e a rc o d e sa n dd u a lc o d e si s e m p l o y e dt oa c h i e v et h em a c w i l l i m a si d e n t i t yo fa l lk i n d so fw e i g h td i s t r i b u t i o n a b o u tt h el i n e a rc o d e sa n dd u a lc o d e so v e rt h i sr i n g t h i r d l y ( 1 + u ) 一c y c l i cc o d e so v e rm i s 血唱a r ed e f i n e d b a s e do n 血er e l a t i o n s h i p b e t w e e n ( 1 + u ) 一c y c l i cc 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 m c t u r eo f ( 1 + u ) - c y c l i c c o c l e s f o h ly ，t h a tg r a yi m a g e so f ( 1 + u ) - c y c l i cc o d e so v e rf 2 + u f 2a r es t i l lc y c l i cc o d e s o v e rf 2i sp r o v e d f u r t h e n l l o r e ，w i t ht h eg e n e r a t o rp 0 1 y n o m i a lo f ( 1 + u ) 一c y c l i cc o d e s ，t h e g e n e r a t o rp o i y n o m i a lo fg r a yi m a g e so f ( 1 + u ) - c y c l i cc o d e si so b t a i n e d f i f t h ly ，w i t hn e c h a e v em a p ，t h en e c h a e v e g r a y m a pi sd e n n e d ，a n di ti sp r o v e d t h a tt h eb i n a r yi m a g eu n d e rt h en e c h a e v e g r a y m a po ft h ec y c l i cc o d e so v e rt h i sr i n g i sc y c l i cc o d e s i nd o i n gs o ，r e i a t i o n s h i p so fc y c i i cc o d e sw i t ht h e i rr e s i d u ec o d e sa n d t o r s i o nc o d e sa r ef u r t h e rd i s c u s s e d s i x t h l y ，t h ec o n c e p to ft h ed e p t ho ft h ec o d e w o r di sn r s t l yd e n n e da n dt h e nt h e a l g o r i t h mo ft h ed e p t ho fc o d e w o r di so b t a i n e d t h i sp a ne n d sw i l ht h ed i s c u s s i o no nt h e d e p t hd i s t r i b u t i o no f l i n e a rc o d e sa n dc y c l i co v e rf 2 + u f 2 k e y w o r d s ：r i n gf 2 + u f 2 ；m a c w i l l i a m si d e m i t y ；( 1 + u ) 一c y c l i cc o d e s ；g r a ym a p ；d e p t h d i s t r i b u t i o n 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的研究成果。据我所 知除了文中特别加以标志和致谢的地方外，论文中不包含其他人已经发表或撰写过的研究成果， 也不包含为获得金肥兰些友堂 或其他教育机构的学位或证二忙而使用过的材料。与我一同j _ = 作 的同志对本研究所徽的任何贡献均己在论文中作了明确的说明并表示谢意。 嫁烈确蝌舻彩车n ( 7 日 学位论文版权使用授权书 本学位论文作者完全了解金墼兰些盍堂有关保留、使用学位论文的规定，有权保留并向 国家有关部门或机构送交论文的复印件和磁盘，允许论文被查阅或借阅e 本人授权垒胆、业厶 ! 岜_ 可以将学位论文的全部或部分论文内容编入有关数据库进行检索，可以采用影印、缩印或扫 描等复制手段保存、忙编学位论文。 ( 保密的学位论文在解密后适用本授权书) 一名：彩匆新学位论文者签名：孑c 毋f 印 别币 签字日期秽邛口辟朋f j 日 签字 学位论文作者毕业后去向： 工作单位： 通讯地址： 电话 邮编 日 致谢 在即将过去的三年研究生学习阶段，我的导师朱士信教授不仅在学业上对 我进行耐心的指导，而且还在生活上给予我无微不至的关怀。朱老师严谨的治 学态度、宽广的胸怀和豁达的处世之道，都是我们学习的楷模。值此论文完成 之际，作者向导师致以最诚挚的敬意和衷心的感谢! 在本人学习期间，还得到了各任课老师的热心的关怀和无私的帮助，师兄 弟们的鼓励和帮助，在此，向他们表示深深的谢意。 感谢合肥学院数理系领导，特别是陈秀教授，在我读研期间给予的支持和 关照，使我有较充裕的时间来完成学业和论文。 感谢父母、岳父母以及夫人汪明多年的大力支持和照顾，在我研究生学习 阶段对我提供的物质帮助和精神鼓励。正是家人的无私的帮助和奉献，才使我 在研究生阶段全身心的投入到学习之中。 最后，再次向所有帮助和关心过我的师长、朋友们表示衷心的感谢! 作者：余海峰 2 0 0 5 年5 月 第一章绪论 1 1引言 1 9 4 8 年s h a n n o n 在他的开创性论文“am a t h e m a t i c a lt h e o r vo f c o m m u n i c a t i o n ”中，首次阐明了在有扰信道中实现可靠通信的方法，提出了著 名的有扰信道编码定理，奠定了纠错码的基石。自此以后，h a m m i n g ，s l e p i a n ， p r a n g e 等人在上世纪5 0 年代初，根据s h a n n o n 的思想，给出了一系列设计好 码和有效译码的方法。以后，纠错码受到了越来越多的通信和数学工作者，特 别是数学家的重视，使纠错码无论在理论上还是在实际中都得到飞速发展。 迄今，纠错码已有五十多年的历史，其发展过程大致分为以下几个阶段： 上世纪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 技术，已作为国际通信中标准技术而推广使用：纠 错码与密码结合，可以构造出类既能加密签名，又具有纠检错功能的密码系 统：纠错码与信源编码相结合的结果使得通信系统更为有效与可靠。不仅如 此，纠错码中的许多译码思想和方法，与神经元网络中的能量函数有密切关系， 可以用来解决神经元网络中的一些问题。因此，可以预料，随着科学的进步和 实际需要，纠错码理论必将进一步发展，它的应用范围必将进一步铲大。 1 2 本文的主要内容 近十几年来，随着有限域上编码理论发展日益成熟，人们逐渐将研究目光 转移到有限环上编码理论的研究上来。尤其是z 。环上线性码和循环码已经被广 泛研究。而最近，一种介于域与环z 。之间的四元素环尺= r + “e ，由于其特 殊的结构也被人们作为感兴趣的字母表而加以研究。本文首先简单介绍了编码 理论发展的过程，有限域及z 。环上与本文相关的一些码理论，然后重点研究了 环r 上线性码及其循环码的一些性质。主要分为如下几个方面： 第一，利用环e + “e 上线性码的生成矩阵及其g r a y 映射，得到了该线性 码的对偶码及其g r a y 象的生成矩阵，并证明了该环上线性码的g r a y 象与其对 偶码的g r a y 象仍是二元对偶码。 第二，定义了环e + 蜗上线性码的李重量分布的概念；并利用其g r a y 象及 其对偶码的关于汉明重量的m a c w i l l i m a s 恒等式而得到了该环上线性码与其对 偶码的各种重量分布之间m a c w i l l i m a s 恒等式。 第三，定义了环f ，+ “上( 1 + “) 一循环码的概念，并利用其与该环上循环 码的关系，而得到了( 1 + “) 一循环码的结构。 第四，证明了环只+ “r 上( 1 + 群) 一循环码的g r a y 象仍是二元循环码，并由 ( 1 + “) 一循环码的生成多项式而得到了其g r a y 象码的生成多项式。 第五。通过n e c h a e v e 变换，定义了n e c h a e v e g r a y 映射，证明了该环上循 环码在n e c h a e v e g r a y 映射下的二元象是循环码，并由此讨论了该环上循环码 和其剩余码及挠码的关系。 第六，定义了环一+ “只上码字深度的概念，得到了计算码字深度的算法， 讨论了该环上线性码及其循环码的深度分布。 此。纠错码中的许多译码思想和方法，与神经元网络中的能量函数有密切关系， 可以用来解决神经元网络中的一些问题。因此，叫以预料，随着科学的进步和 实际需要。纠错码理论必将进一步发展，它的应用范围必将进一步扩大。 1 2 本文的主要内容 近十几年来，随着有限域上编码理论发展日益成熟，人们逐渐将研究目光 转移到有限环上编码理论的研究上来，尤其是z 。环上线性码和循环码已经被广 泛研究。而最近，一种介于域一与环z 4 之间的四元素环胄= e + “e ，由于其特 殊的结构也被人们作为感兴趣的字母表而加以研究。本文首先简单介绍了编码 理论发展的过程，有限域及z 。环上与本文相关的一些码理论，然后重点研究了 环r 上线性码及其循环码的一些性质，主要分为如下几个方面： 第一，利用环e + 峨上线性码的生成矩阵及其g r a y 映射，得到了该线性 码的对偶码及其g r a y 象的生成矩阵，并证明了该环上线性码的g r a y 象与其对 偶码的g r a y 象仍是二元对偶码。 第二，定义了环e + 蜗上线性码的李熏量分布的概念；井利用其g r a y 象及 其对偶码的关于汉明重量的m a c w i l l i m a s 恒等式而得到了该环上线性码与其对 偶码的各种重量分布之间m a c w i l i i m a s 恒等式。 第三，定义了环+ “上( 1 + “) 一循环码的概念，并利用其与该环上循环 码的关系，而得到了r 1 + “卜循环码的结构。 第四，证明了环+ “只上( 1 + w ) 一循环码的g r a y 象仍是二元循环码，并由 ( 1 + ) 循环码的生成多项式而得到了其g r a y 象码的生成多项式。 第五。通过n e c h a e v e 变换，定义了n e c h a e v e g r a y 映射，证明了该环上循 环码在n e c h a e v e 0 r a y 映射下的二元象是循环码，并由此讨论了酸环上循环码 和其剩余码及挠码的关系。 第六，定义了环只+ “只上码字深度的概念，得到了计算码字深度的算法， 讨论了该环上线性码及其循环码的深度分布。 讨论了该环上线性码及其循环码的深度分布。 第二章域上的线性码 2 1 线性分组码 一、分组码的基本概念： 在数字通信中，经常利用纠错码来进行差错控制，其中一类重要的纠错码 就是分组码。 定义2 1 1 ：分组码是对每段k 位长的信息组，以一定规则增加，= 一七个 校验元，组成长为n 的序列：( c 。，。l i 一，c 。) ，称这个序列为码字( 码组，码矢) ， 在二进制情况下，信息组共有2 个，因此通过编码器后，相应的码字也有2 个， 称这2 个码字，集合为( ”，) 分组码。 n 长序列的可能排列总共有2 ”种( 每一 长序列称为厅重) ，而( n ，t ) 分组码 的码字集合只有2 种，所以分组码的编码问题就是定出一套规则，以便从2 ”个 重中选出2 个码字。不同的选取规则就得到不同的码。 称r = 七”为码率，表示( 打，t ) 分组码中信息位在码字中所占的比重，k 是衡 量分组码有效性的一个基本参数。 定义2 1 2 ：两个行重x ，y 之间对应位取值不同的个数，称为它们之间的汉 明距离，用d ( x ，y ) 表示。 定义2 1 3 ： 重x 中非零码元的个数，称为它的汉明重量，简称重量，用w ( x ) 表示。 定义2 1 4 ：( 肝，) 分组码中，任两个码字之间距离的最小值，称为该分组 码的最小汉明距离哦，简称最小距离或= 哂只、 d ( x ，y ) 。 巩是( n ，t ) 分组码的另一重要参数，它表明了分组码抗干扰能力的大小，为 方便起见，今后以简称为d 。 二、线性分组码： 一个h 女】线性码，是把信息划成七个码元为一段，通过编码器变成长为 个 码元的一组作为 ”，削线性分组码的一个码字。若每位码元的取值有g 种( g 为 素数幂) ，则共有g 个码字，若g 。个码字集合构成了g f ( g ) 上所有胛重构成的胛维 线性空间的一个七维线性子空阳j ，则称它是一个砷，明线性分组码，简称为m ，女】 线性码。 定义2 1 5 ：m ，】线性码是g f ( q ) 上 维线性空间k 中的一个七维子空间 k 。由于该线性子空间在加法运算下构成阿贝尔群，所以线性码又称为群码。 因线性分组码是分组码的一类，因此有关分组码的参数，如码率，码字的 距离与码的最小距离，码字的重量等定义，对线性分组码均适用，这罩不再赘 述。 显然，d 是分组码的两个最重要参数，因此今后我们用 ”，t ，d 】( 或 ，女 ) 表示线性分组码，而用( h ，m ，d ) 表示码字数目为m 的任何码。 胛，七，d 】分组码是一个群码，因此若码字q ，c ：m ，t ，棚，则由群的封闭性知 c 1 + c 2 【h ，_ j ，d ，即c l + c 2 也必是h ，羽分组码的一个码字，所以码字c l ，岛之间 距离d ( c 1 ，c ：) ，必等于第三个码字q 十c ：的汉明重量，因此，一个【疗，卅分组码 的最小距离必等于码中非零码字的最小重量，由此可得如下定理： 定理2 1 1 ：【 ，i ，卅线性分组码的最小距离等于非零码字的最小重量，即： d = m i n w ( c ，) ic 。限】 个 三、线性码的生成矩阵与一致校验矩阵 【h ，七，d 】分组码的编码问题就是在盯维线性空间圪中，如何找出满足一定要 求的，有2 。个矢量组成的t 维线性空间k 。或者说，在满足给定条件下，如何 从已知的七个信息元求得r = 一一个校验元。这相当于建立一线性方程组，已知 女个系数，要求”一女个未知数，使得到的码恰好有所要求的最小距离d 。 若定义一个一t ) n 阶矩阵h 满足： 日c 7 = 0 7 ( 2 1 1 ) 或：c h 7 = 0( 2 1 2 ) 其中c 为k i 的任码字：h 的每一行向量均线性无关 则称日为码【 ，t 】的一致检验矩阵。 显然日矩阵的每一行代表一个线性方程的参数，它表示求一个校验元的线 性方程，故若日确定了，则码【n ，女】也就确定了。 另一方面，【h ，女，d 】分组码的2 个码字组成了一个t 维子空间，因此这2 。个 码完全可由t 个线性无关向量所组成的基底而张成。 若将这t 个线性无关向量作为行向量写成矩阵形式，则称该矩阵为线性码 【竹，t ，棚的生成矩阵。若线性码 月，七，训生成矩阵为g ，个信息元组成的信息组 为m ，则有： c = 所g ( 2 1 3 ) 将( 2 1 3 ) 式代入( 2 1 1 ) 有：日- g2 = o 2 ( 2 1 4 ) 将( 21 3 ) 式代入( 2 1 2 ) 有：g - 日7 = o( 2 1 5 ) 即g 与日的行生成的空间互为零空间。 四、对偶码： ”，明码是”维线性空间的一个七维子空间由一组基底即g 的行张成， 由线性代数知识可知它的零空间必是一个”一维的线性子空间圪，。，并由 n 一个线性无关向量张成，由( 2 1 4 ) 、( 2 1 5 ) 式可知，这”一1 个向量就是h 矩 阵的行，因此，若把矩阵看成是 月，n t ，d 】码的生成矩阵g ，而把 n ，( ，】码的 g 看成是它的检验矩阵h ，则我们称由g 生成 n ，d 线性码c 与由h 生成的线 性码c 1 h ，h 一，d ，为对偶码，相应地，称吒i 与。互为对偶空间，由此可如 下定义对偶码。 定义2 1 6 ：设线性码c k ，d ，则它的对偶码定义为： c 1 垒& k ，。，对所有y c ，使x y = o ， 式中工y 表示x 与y 的内积。 若c = c 1 ，则称码c 为自对偶码。 显然，自对偶码必是 2 卅，m ，训形式的线性码。 2 2 线性码的重量分布 h ，卅线性码的不可检错误概率和译码错误概率的计算，是统计f e c 和 a r q 等差错控制系统性能的基础，但译码错误概率和不可检错误概率的计算， 又与码的重量分布密切相关。 一、 线性码的重量分布： 掰谓码的重量分布是指一个陬，明线髋分组弼或菲线性码的璃字重蓬的分 布情况，它不仅是计算各种译码错误概率的主要依据之一，而且也是探索码结 梅瓣蘩要塞瓣，逶逡它戆透彻蘧了解羁豹内部关蓉。 蹴义2 2 1 ：设爿，是七，训分组码中熏量为f 的码字数日，则集合 焉，焉，蠢。 赣为该线牲妈蛇重量分枣。 例如【7 ，4 ，3 汉明码的重爨分布为： 谴 = 名e ，蠢 ，名2 ，焉 = l ，o ，o ，7 ，7 ，o ，o ，l 蕻中，一个全o 码字( = 1 ) 是任何线性码必须有的，也可以把码的蘑量分 布写成如下形式的多项式： 旦 畋( x ，) = ：爿，x ”y 7 ( 2 ，2 1 ) 面 褡魏多颂式为线性弱c 阮晕，碉豹重量计数公式。 利用前莉汉明重量的意义，也可将之碍成： 甄瓴刃一x 州。y 昧 ( 2 ，2 2 ) c e ( 1 二、 线性碣与其对偶玛之闼救m a e w i l l i a m s 匿等式： 糟记爿j 表示线性码c 队明的对偶码c 1 阮”一】中的重凝为f 的码字数目，则 c 。熬霪量诗浆公式为： ( x ，y ) = 4 名y 。= x ”忡y 忡 ( 2 2 3 ) l 稀 雌( 1 奄理2 2 1 ：若c 是一帆女】的二元线性码，c l m ，”一纠为其对偶码，则有 瓴炉高喇h 肼刊 ( 2 2 1 4 ) 冀中陶= 2 。是攒e 中掰有码字豹个数a ( 9 ) 式也等价于： 静广。 南静( 州广b 训7 z s ， 或：f 叫砷y 吣k 南萎( 舢广忡k 训吣1 ( 2 2 6 ) ( 2 2 4 ) 、( 2 2 5 ) 、( 2 2 6 ) 式也称为m a c w i l l i a m s 恒等式 若引入如下形式的k r a w t c h o u k 多项式只( f ，h ) ： 只( i ， ) = ( 一1 ) 飞) ( 瑚 = o ，1 ，2 ， ( 2 2 7 ) 此处，是一未定元，显然最( f ，n ) 是关于f 的一次数为七的多项式 则由定理2 2 1 也可得到4 j 与4 ，之间的关系，即有： 定理2 2 2 ：设c 是一【n ，纠二元线性码，c 1 为其对偶码， 爿， 与 4 0f = o ，1 ，月分别为c 与c 1 的重量分布，则有： 1 上 以2 亩爿，b ( f ，h ) ( 2 2 8 ) 2 3 循环码 循环码是一类最重要的线性码，它具有严谨的代数结构，又具有循环的特 性，从而性能易于分析，且编译码电路尤其是编码电路简单且易于实现，现今 已发现的大部分线性码与循环码有密切联系，因此循环码特别引人注目，对它 的研究也比较深入和系统化。 一、 基本概念： 定义2 3 1 ：+ 个 重子空间小，若对任一v = ( ，q ，一。) 。，恒有 v 。= - 。，臼。：) e 。则称圪为循环空间或循环码。 二、 循环码的多项式描述： 显然卯0 ) 上所有n 的重构成一个线性空间k ，其中每个向量是分量取自g f ( p ) 上月重，若将每个盯重和系数取自g f ( p ) 上的多项式相对应： ”重：，口，一，)d g f 0 ) 多项式： 日o + a i x + + 口。一l x “= ，( x ) 则它们之间建立了一一对应关系，由有限域理论知，所有次数小于n 次的多项 式一定在模”次多项式f ( x ) f ，m 的不同剩余类中，即 b ) 甜o + d l f + + 。一1 x ”一1i ( m o d ，( 工) ) 因此，k 中每一个n 重都与g f ( p ) 上次数低于h 次的个多项式相对应，并必在 模f ( x ) 的某一剩余类中，而在模f ( x ) 的运算中，模f ( x ) 的剩余类构成一多项式 剩余类环l k 】护( z ) ) 若在该环中再定义一个数乘，即 c 口b ) = 扣日o + 阳i z + + c 。一l x ”叫c g j f 0 ) 则可以证明模f ( x ) 的剩余类构成一个 维线性空间，称为剩余类线性结合代数。 在k ，女j 循环码中，码字- 。，q ，a 。，) 的多项式表示为g ) = + q x + + 日。x ”1 ， 它循环移位一次后所得码字为0 ，a 。) ，相应的多项式表示为： 口i ( x ) = n 一2 x ”_ 1 + 口n 一3 x ”一2 + + d o x + 口n l ， 相当于d ( x ) 乘以x 后用f ( x ) = x “一1 取模，即： m o d b “一1 ) 】：口6 ) = 口n 一2 x “- 1 + + 口o x + 口h i 若在扛m x ”1 + + 口o x + a j 剩余类中，以最低次数，2 x ”1 + + x + 口多项式 作为该类代表元，则循环码就可用m o d ( x ”一1 ) 的多项式表示。 定理2 3 1 ：以多项式x “一l 为模的剩余类线性结合代数中，其一个子空间 k 。是一个循环子空间( 循环码) 的充要条件是。是一个理想。 由此定理可得： 一个循环码是模x “一l 多项式剩余类线性结合代数中的 中的一个理想必是一个循环码。 定义2 3 2 ：生成多项式g g ) 是模x ”一l 剩余类代数中， 低的非零首一多项式，它是理想或循环码的生成元。 个理想：反之，其 一个理想的次数最 定理2 3 2 ：g f ( g ) ( 口为整数或整数幂) 上的k ，女】循环码中，存在有唯一 的”一女次首一多项式g ( x ) = x ”+ g 一i x ”“。+ + g i x + 9 0 ，每一码多项式c ( x ) 都 是g b ) 的倍式，且每一个n 1 次的g g ) 倍式一定是码多项式。 由此定理可知： l ”，| | l 线性码是循环码的充要条件是：它是模z ”一l 多项式剩余类线性结合代 数中的一个理想，且理想中只有一个次数为n 一的生成元譬( x ) ，所以这是一个 主理想，理想的维数即循环码的信息元个数等于女。 下面讨论主理想生成元g ( x ) 应满足的条件： 定理2 3 3 ：g f b ) 上k ，t 循环码的生成多项式g ( x ) 一定是x ”一1 的因式： z ”一l = g ( x 如g ) ，反之，若g g ) 为”一女次多项式且g g 壮”一1 ，则该g g ) 一定生 成一个k t l 循环码。 三、循环码的生成矩阵、校验矩阵： 由前知x ”一l = 9 0 如g ) ，若设g b ) 为”一t 次多项式，则a ( x ) 为t 次多项式， 则以g ( x ) 为生成多项式所组成h ，】循环码中：g g ) ，昭b l ，x “1 9 ( x ) ，等个码多 项式必是线性无关的。 可以由这些码多项式所对应的码字构成循环码的生成多项式g ，即 口+x +矿 n 副以一所 + - 二 ，； 附- 况情 1 1一= 矿 模肌在为 因 g = g 一i g 。一i 一1 ，g l ，g o g i g ，g 。 g 肛 ，g 月一i i g ”g o 其中g g ) = g 。+ g i z + - - + g 。一i x ”一 若设 g ) = 魄x + + ，则可验证，循环码的一致检验矩阵为 目= 向o l o 办l 女 由该式可看出，h 矩阵的行完全由 0 ) 的系数决定。 故称 g ) = o ”一1 ) 居g ) 为该循环码的校验多项式。 另外，若记 + g ) = 矗。x + 魄一。x + 丸( 称 g ) 为 g ) 的互反多项式) 则有： 由校验多项式 g ) 的互反多项式 g ) 生成的胁，胛一女】循环码与由生成多项式为 g g ) 生成的k ，女】循环码互为对偶码。 2 4 线性码的深度分布 码字的深度是刻划码字复杂性的一个重要特征，也是研究移位寄序器序列 的线性复杂度的有力工具。 一、码字的深度概念及其算法： 记b ) 为g a l o i s 域g f 0 ) 上n 维向量空间，则蜥= g 一，k ) 0 ) ，称 ) 譬= ( x 2 一x i ，x 3 一x 2 ，x 。一x 。一1 ) 为码字x 的导数。 容易验证d 为线性算子，即，y ( 孽) ，a g f ( q ) 有： d 【x + y j = d x + p y ，d ( 缸) = 脓 为方便起见，用 表示分量全是旯的向量。 定义2 4 1 ：设工e 圪( g ) ，称使得d z = o ” 的最小非负整数i 为向量工的深 度，记为如p f 艋= f ；若没有这样的i 存在，则称比p ，橛= 月。 显然，对v x ，( q ) ，恒有o 却f 缸 且d e g p 慨= ，的充要条件是存在g f 0 ) 上非零元素a ，使得d ”= 爿”1 若设v = l v ，v 。) ，( g ) ，且，为满足9 7 ( 胛的最大正整数，记v = l v ，v ，) ， “= d “v = ( ”r + i v i ，+ 2 一”一，v 。一v 。q ，) ，则可以通过如下算法计算却r v ： 1 ) 如果v = 】，则( 耙p 曲p = 0 2 ) 如果v = 【刀 ，旯g f ( g ) 且非零，则却腩v = 1 3 ) 如果“= o ”一“】，贝0 锄矗v = 却肪( v ) 4 ) 女果“ o ”一“】，爨q 却珐v = 口+ 却捕 二、线性码及其循环码的深度分布： 定义2 ，4 2 ：给定g f ( q ) 线性码c ，蜘，令d ，表示c 中深度为f 的码字的个数， 则数d o ，d ，d 。称为码c 深度分布。 显然d 。= 1 。 定义2 4 3 ：设c 【月，明为g ，( g ) 上一线性码，d 。，d 一，d 。为其深度分布，则 下标集 f l l f h ，d j o 称为码c 的深度谱。 定理2 4 1 ：设c 印，明为g f ( q ) 上一线性码，则c 恰含有j 个非零深度值，并 且由任意个具有不同深度的码字均可构成c 的一个生成矩阵。进一步，若设七 个不同深度为f t ，2 以，则有b 。= ( g 一1 ) 口” ( 1 ，t ) 。 推论：设c 【胛，纠为g f ( 2 ) 上线性码，深度谱为p ，d 2 ，以 ，则其深度分布 为： d f = 1 0 2 0 f = o f 匹p ，d ：，一，d 。 f _ d ，j = l ，2 ，尼 定理2 4 2 ：设c 【n ，明是g f ( 2 ) 上循环码，其生成多项式为g ( x ) ，则 ( x - 1 ) 蚣“一1 ) g ) 曹c 有深度谱姐，2 ，s u 虹，n l ，推一是+ s + l 其中“1 | ，是指恰好整除”：即口( x ) 瞅工) 表示d ( x ) f6 ( x ) ，但口( x ) “不整除6 ( x ) 由此定理可得到循环码c h 1 的深度谱恰好为( 1 ，2 ， 以及如，h 一1 ，脬一女+ 1 两 种极端情况时应满足的充要条件，不再赘述。 第三章乙码 3 1 乙线性码 一、基本概念： 令z 。是一个整数模4 的环， 为一正整数，z ：是z 。的h 重集合，即 z ：= 妇i 一，h ) k z 4 ，扛1 ，2 ，一，n ( 3 1 1 ) z ：的任何非空子集c 称为z 。码，n 称为码c 的长度，码c 中的每个n 重称 为c 的一个码字。 对x = b ，x ：，x 。) 和y = l ， 一，_ y 。) z ：，定义分量和： 工+ y = ( x l ，工。) + ( y l ，一，y 。) = ( z l + j ，l ，- ，x ，+ y 。) ( 3 1 2 ) 则z 。可看成一阶为4 ”的加法阿贝尔群。 定义3 1 1 ：z ：的任一加法子群称为z 4 线性码。 对x = 0 ，x ：，x 。) ，y = 0 1 ) ，虬) z ：定义x 与y 的内积为： x y = x i y l + + z 。y 。 ( 3 1 3 ) 若x y = 0 ，则称x 与_ y 正交。 定义3 1 2 ：设c 是长为”的z 。线性码，定义： c 1 = 扛z ：卜y = o ，对任劫c j ， ( 3 1 4 ) 则易验证：c 1 也为乙线性码，称之为c 的对偶码。 如果c 1 = c ，则称c 为自对偶码。 定义3 1 3 ：设c l ，c ：均是长为月的z 。线性码，若c 通过坐标变换( 必要时 改变码元的符号) 可得到码c ：，则称c l 与c ：等价 定理3 1 1 ：任何包含非零码字的乙线性码c 都等价于一个生成矩阵为： 卜一b ( 3 1 5 ) l o2 l ：2 c j 的线性码，其中，护，“分别指女。、也阶的单位矩阵，a ，c 为最上矩阵，b 为 z 。上矩阵。此时也称码的类型为4 “2 “。 定理3 2 ：设c 为生成矩阵如( 3 5 ) 的线性码，则其对偶码c 1 的生成矩阵 为： f 一日丁一c r 爿r c 7 ，n 一岛一女2 ( 3 1 6 ) l 2 4 。 2 ，i ， o j 此处”指码c 的码长，c 1 的类型为4 ”- “2 2 虹 二、 线性码及其对偶码的m a c w i l l i a m s 恒等式： 设c 是z 。上长为h 的线性码，口z 。，觇= b 一，x 。) 础，定义x 的重量 睨( x ) = j f | 一= 口 j ( 3 1 7 ) 则可定义c 的完全重量计数公式为： 耽g 。，x i ，x 2 ，屯) = z 。州c z i ”小x 2 m 。1 彳3 昧c ( 3 1 8 ) c e c 以及c 的对称重量计数公式： s w e 。g 。，五，x 2 ，x 3 ) = 甄“。z l 州小吲。2 吲。 ( 3 1 9 ) c e f 类似地若定义z 。上元素0 ，1 ，2 ，3 的李重量分别为： 睨( o ) = 0睨( 1 ) = 睨( 3 ) = l ，睨( 2 ) = 2 延伸到z ? 上向量x = ( 一，z 。) 的李重量： 睨( x ) = 既( 一) f = i 李距离： d 。( x ，y ) = 阡i ( x 一_ y ) 则定义c 的李重量计数公式： ( 3 1 1 1 ) 三p e 。( x ，】，) = x 2 ”一”l f ( 1 y ”l 。) ( 3 1 1 3 ) 由z ：上离散的齑a m a r d 变换可得如下的m a c w i l l i m a s 恒等式： 定理3 1 1 3 ：设c 是z 4 线性码，c 1 是其对偶码，i c l 表示码c 中所含码元总 个数，则有： 小。焉，孙。，) 2 亩( ”b ”卟矿味矿”矿孙矿卧” 妣c 上 ”一1 2 ) = 商气( + 2 一2 j 。2 一。- 2 _ 2 胁( 、( x ，y ) 。亩胁( ( x x y ) 3 川4 三、g r a y 映射： 从互到z ，上可定义如下三个重要映射口，卢，： 其中： ooo0 l 101 2o1l 3l1o x z a v x z 。，有x = 口( x ) + 2 芦( x ) 则协乙，可定义g r a y 映射：中( x ) = ( 卢( x ) ，y ( x ) ) 显然m 为一从z 。到碍双射 可将之自然延伸至z ：上，即： 定义3 14 ：协= ( 一，x 。) z ：，若定义d ( x ) = 心( x i ) ，口( x 。) ) ，且 ( c ) = ( ( x 。) ，( x 。) ) 则称中( x ) = ( ( x ) ，d 0 ) + p ( x ) ) 为z ：到z 尹的g r a y 映射。 定理3 1 4 ：o 是一个从( 础，李重量) 到( z 尹，汉明重量) 的保重量映射， 且中也是一个从( 刃，李距离) 到( z ；”，汉明距离) 的保距离映射。 从g r a y 映射定义可明显看出z 。上线性码的g r a y 象不一定是线性码，因此，乙 上线性码与其对偶码在g r a y 映射下的象码不一定是对偶码。 任取两个n 维向量x = ( 而，x 。) ，y = ( m ，) 定义x 与y 的分量积为 x 唪y = ( x l y l ，x 。y 。)( 3 1 1 5 ) 则有： 定理3 1 5 ：z 4 线性码c 的二元象码o ( c ) 是二元线性码的充要条件是： 工+ y = ，2 口( x ) + 口( y ) c( 3 1 。1 6 ) 3 2 乙上循环码及其负循环码 一、h e n s e l 引理和h e n s e l 提升 上节我们定义了一个从z 4 到z ：的映射口，称此映射作用在乙上元素的象 为五上元素的二元约化，即巩z 。称口( x ) 为x 的二元约化，为方便起见，将 “口”简记为“一”，即有：石：互：o ，t ：i ：1 该映射能自然延伸至z 。嘲到z ：纠的映射“一”： 即v ，( x ) = 盘。+ 口。x + + 口。一x ”1 z 。卜】，称7 石五= i + 瓦l + + 五= x “1 为，( x ) 的二元约化多项式。 引理3 2 1 ：h e n s e i 引理： 令，( x ) 是z 。b 】上首一多项式，假设页习= 万固- 万弼，其中万固，万q 为z ：中 互索的多项式，则一定存在首一多项式g 。g l g ：o ) sz 。m ，具有下列性质： ( 1 ) ，g ) = g ，g k ：o ) ( 2 ) 羽= 确硐= 五g ) ( 3 ) d e g g 0 ) = d e g 确d e g g ：g ) = d e g 确 ( 4 ) 在z 4 卜j 中，( g ( x ) ，9 2 ( x ) ) = 1 说明：此引理也可推广到多个多项式的情形。 定义3 2 1 ：令，( x ) e z 。k 是一个次数为m 的首一一多项式，如果确在z ：m 上是不可约的，则称厂b ) 是z 。i 】中一次数为研的基本不可约多项式，如果7 i 习 在z ：h 上是本原的，则厂g ) 称为z 。m 上一次数为m 的基本本原多项式。 定理3 2 2 ：对任意正整数聊，一定存在一个z ，i x i 上次数为的首一多项 式