（应用数学专业论文）环fpmufpm上循环码和常循环码的若干问题的研究.pdf

环c 脚+ 以易上循环码和常循环码的若干问题的研究 摘要 经典的编码理论是以有限域上的向量空间为背景。二十世纪九十年代，人 们发现一些高效的二元非线性码可以看作是z 。上的线性码在g r a y 映射下的二 元象，有限环上的编码理论获得重要突破。自此，有限环上的编码理论成为研 究的热点。本文主要研究了环r = t 。+ 幔。上长为p 的循环码和循环自对偶码 的结构和计数，探讨了常循环码的置换等价性及其结构和计数；还研究了当 ( 玎，p ) = 1 时环尺上常循环码的置换等价性和g r a y 像的结构。具体内容如下： 1 利用等价代换给出了环r 上长为p 的循环码的唯一表示方法，并在此基 础上得到了循环码的码字个数及对偶码的唯一表示； 2 讨论了环r 上长为p 2 的循环自对偶码的充要条件，给出了其计数，并列 出了当p = 3 ，k = 1 和k = 2 时的所有循环自对偶码： 3 探讨了当( n ，p ) = l 时环尺上( 1 + 口材) 一常循环码、( 善+ a u ) - 常循环码的置换 等价性，并给出了其g r a y 像的结构； 4 研究了环r 上长为p 。的口一常循环码、 一口) 一常循环码的置换等价性 及其计数，并给出了口一常循环自对偶码的计数。 关键词：循环码：准循环码；自对偶码；g r a y 映射：有限链环；零化子 r e s e a r c ho ns o m ep r o b l e m so fc y c l i cc o d e sa n dc o n s t a c y c l i c c o d e so v e rt h er i n g f 一+ h f a b s t r a c t c l a s s i c a lc o d i n gt h e o r yt a k e sp l a c ei nt h es e t t i n go fv e c t o rs p a c e so v e rf i n i t e f i e l d s i nt h e19 0 0 s ，t h et h e o r yo fe r r o r c o r r e c t i n gc o d e so v e rf i n i t er i n g sh a s e x p e r i e n c e dt r e m e n d o u sg r o w t h s i n c et h e s i g n i f i c a n td i s c o v e r yt h a ts e v e r a l w e l l k n o w np r o m i n e n tf a m i l i e so fg o o dn o n l i n e a rb i n a r yc o d e sc a nb ei d e n t i f i e da s i m a g e so fl i n e a rc o d e so v e r 乙u n d e r t h eg r a ym a p s i n c et h e n ，c o d e so v e rf i n i t e r i n g sh a v eb e e ng i v e nm o r ea t t e n t i o n i nt h i sp a p e r ，w es t u d yt h es t r u c t u r e sa n d m a s sf o r m u l a so fc y c l i cc o d e sa n dc o n s t a c y c l i cc o d e so fl e n g t h p 2o v e rt h er i n g r = o + u f 。，w h i l et h ep e r m u t a t i o n - e q u i v a l e n c e so fc o n s t a c y c l i cc o d e sa r ea l s o i n v e s t i g a t e d f o r t h e c o n s t a c y c l i c c o d e sw i t h ( 胛，p ) = 1 ，t h e i rp e r m u t a t i o n e q u i v a l e n c e sa n ds t r u c t u r e so fg r a yi m a g e sa r ed i s c u s s e d t h ed e t a i l sa r eg i v e na s f o l l o w s ： 1 u s i n ge q u i v a l e n tp e r m u t a t i o n ，w eg i v e au n i q u em e t h o do fr e p r e s e n t i n g c y c l i cc o d e so fl e n g t hp 2 o v e rt h er i n gr b a s e do nt h a t ，t h en u m b e ro f c o d e w o r d so fc y c l i cc o d e sa n dt h eu n i q u em e t h o do fr e p r e s e n t i n gd u a lc o d e sa r e p r o v i d e d ； 2 w ed i s c u s st h ee q u i v a l e n tc o n d i t i o n so fc y c l i cs e l f - d u a lc o d e so fl e n g t hp 2 ， a n dg i v et h e i rm a s sf o r m u l a s b e s i d e st h i s ，a l lc y c l i cs e l f - d u a lc o d e sa r eg i v e n w h e np = 3 ，k = 1a n dk = 2 ； 3 t h ep e r m u t a t i o n - e q u i v a l e n c e so f ( 1 + 口材) 一c y c l i cc o d e sa n d( 善+ 口z ，) - c y c l i c c o d e sw i t h ( 疗，p ) = 1o v e rt h er i n gra r ed i s c u s s e da n dt h es t r u c t u r e so ft h e i r g r a yi m a g e sa r eg i v e n 4 w es t u d yt h ep e r m u t a t i o n e q u i v a l e n c e sa n dm a s sf o r m u l a so f 口一c y c l i c c o d e sa n d ( u p - - 6 t ) 一c y c l i cc o d e so fl e n g t h p 2o v e rt h er i n gr ，t h em a s sf o r m u l a s o f 口- c y c l i cs e l f - d u a lc o d e so fl e n g t hp a r ea l s og i v e n k e y w o r d s ：c y c l i cc o d e ；q u a s i c y c l i cc o d e ；s e l f - d u a lc o d e ；g r a ym a p ；f i n i t er i n g ； a n n i h i l a t o r 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的研究 成果。据我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已 经发表或撰写过的研究成果，也不包含为获得 盒墅工些友堂 或其他教育机 构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均 已在论文中作了明确的说明并表示谢意。 学位论文作者签名：j 签字日期：上吖6 年牟月fg 日 学位论文版权使用授权书 本学位论文作者完全了解金目墨王些塞堂有关保留、使用学位论文的规定，有 权保留并向国家有关部门或机构送交论文的复印件和磁盘，允许论文被查阅和借阅。 本人授权金壁王些太堂可以将学位论文的全部或部分内容编入有关数据库进行检 索，可以采用影印、缩印或扫描等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后适用本授权书) 学位论文作者躲了彳爱 签字日期少厂口年争月f 洳 学位论文作者毕业后去向： 工作单位： 通讯地址： 导师签 签字日期：c ，年午月f 庐 电话： 邮编： 致谢 光阴似箭，蓦然回首，三年的硕士学习生涯即将结束。值此论文完成之际， 首先要感谢我的导师朱士信教授，朱老师严谨的治学态度，渊博的专业知识， 精益求精的工作作风，诲人不倦的高尚师德，严以律己、宽以待人的崇高风范， 朴实无华、平易近人的人格魅力对我影响深远，使我明白了许多待人接物与为 人处世的道理。在此谨向朱老师表示最衷心的感谢和最崇高的敬意! 在本人读研三年期间，还得到了刘丽老师等很多老师的热心的关怀和无私 的帮助，在此，向各位老师表示深深的谢意。同时，感谢学校为我提供了良好 的学习环境和优越的学习条件! 我还要感谢李平师兄、开晓山师兄、唐永生师兄、王玉师兄、李富林师兄 等在三年共同生活学习的过程中给予我的鼓励和帮助，我会永远铭记在心! 感谢评审硕士论文和出席硕士论文答辩会的各位专家学者，感谢他们在百 忙之中给予的批评指正和宝贵意见! 感谢我的家人多年来在物质及精神上给予我莫大的支持，这为我完成学业 和论文奠定了重要的基础，在此祝愿他们永远健康，快乐! 最后，向所有关心和帮助过我的人们致以衷心的感谢! 作者：丁健 2 0 1 0 年4 月 第一章绪论 1 1 纠错编码理论 美国数学家香农( s h a n n o n ) 在1 9 4 8 年发表的著名开创性论文“a m a t h e m a t i c a lt h e o r yo fc o m m u n i c a t i o n ( 即通讯的数学理论) 中提 出了著名的受干扰信道编码定理，从而宣告了一门现代科技中具有重大意义的 崭新学科一一信息论( i n f o r m a t i o nt h e o r y ) 的诞生。纠错编码理论( 也即编码 理论) 是信息理论的一个专门分支，它的发展源于实际应用中现代通信技术与 电子计算机技术中差错控制研究的需要，因此这一领域既是通信工作者们也是 数学工作者们研究的热点。在信息技术飞速发展的同时，编码理论也得到了迅 速的发展。现在我们利用计算机进行复杂运算时，不再担心结果是否可靠，但 是在计算机概念刚提出时，有人提出如下反驳：在计算机进行复杂运算时，外 界噪声的干扰是不可避免的，而计算机的系统如此复杂，只要噪声使得计算机 中任一部件发生一次错误，最后的运算结果都会变得面目全非，因此可以断言 利用计算机进行复杂运算是不可能的。这个困难后来是如何克服的呢? 编码在 这个过程中起了关键性的作用。什么是编码? 编码，更准确地说，信道编码， 指的是通过引入冗余信息，使得在一部分比特( b i t ) 发生错误的情况下，仍有 可能按照一定的规则纠正这些错误，以实现无失真地传送和处理信息。举一个 最简单的重复码为例，我们可以将信号0 编码为0 0 0 ，信号1 编码为1 11 ，如果 至多只有一个比特发生错误，譬如，0 0 0 变成0 1 0 ，我们仍然可以按照少数服从 多数的原则，找出错误的比特就是第二个比特并纠正该错误。纠错编码理论是 上世纪四十年代末由s h a n n o n ，h a m m i n g ，g o l a y l l - 7 1 等人创立。h a m m i n g 和g o l a y 在六十多年前分别发表的论文“e r r o rd e t e c t i n ga n de r r o rc o r r e c t i n g c o d e s ” 6 1 和“n o t e so nd i g i t a lc o d i n g 1 7 1 中，提出了从充分利用检验元的 角度来看，纠正二元序列中一位错和三位错的完备码( p e r f e c tc o d e s ) 是最佳 的，从而开创了与应用相结合的编码理论方法的研究，可以说，信息理论的发 展和编码方法的成长始终是相互依赖、相互促进的。h a m m i n g 曾经说过：“从 逻辑上来说，编码理论导致了信息理论的产生，而信息理论则为适当的信息编 码提供所能达到的限度 8 - - 1 。事实上，信息理论的应用从底层的通信到电子 的损耗都涉及到编码理论，所以说“a l g e b r a i cc o d i n gt h e o r yi sab r a n c ho f e n g i n e e r i n gw i t h r o o t si nm a t h e m a t i c sa n da p p l i c a t i o n st o c o m p u t e r s c i e n c e ” 1 2 1 。 编码理论的研究主要包括以下三个方面：以提高数字信息传输、存储处理 的有效性为宗旨的信源编码( s o u r c ec o d i n g ) 。以增加数字信息传输、存储的 安全性为目标的数据加密编码( d a t ae n c r y p t i o nc o d i n g ) ；以保证数字信 息传输和处理的可靠性为目的的差错控制编码( e r r o r c o n t r o lc o d i n g ) ，又称 信道编码( c h a n n e lc o d i n g ) 。差错控制编码技术应用面广、类别繁多，通常所 使用的编码理论中的“编码”指的就是差错控制编码译码技术。每一个通信系 统都依赖有效的编码技术，差错控制编码技术也是伴随着数字通信业务的发展 而发展起来的，因此在相当长的一段时间内，编码的要求和编码译码器的结构 特点，都体现了数字通信技术的特征，这就是要求冗余度小、码率高，以便在 串行信道中保证尽可能高的通过能力，编码译码器的速度只要能跟上信号在串 行信道上传送的节拍就可以。在这种工程技术背景下，以有限域和代数为基础， 以循环码为代表，以线性反馈移位寄存器为主要编码译码器件的代数编码技术 得到迅速发展并且日臻完善，其中像r s 码、b c h 码、g o l a y 码以及h a m m i n g 码等都 是应用非常广泛的代数码。从结构上来看，差错控制编码主要有两种，即分组 码( b l o c kc o d e s ) 和卷积码( c o n v o l u t i o nc o d e s ) 。所谓分组码是一组固定 长度的码组，在编码时，k 个信息位被编为玎位 七) 码组长度，( 珂一k ) 个监督 位被加到信息位之后，形成新的码，监督位的作用就是实现检错与纠错。与分 组码不同，在卷积码中编码后的刀个码元不仅与当前段的k 个信息有关，而且 也与前面( m 一1 ) 段的信息有关，编码过程中相互关联的码元为n m 个，其中m 是 数据帧移位寄存器的存储深度。卷积码的纠错能力随着聊的增加而增大，在编 码器复杂程度相同的情况下，卷积码的性能优于分组码。由于卷积码类在工程 技术中的实用性，使得通信工程工作者们更倾向于卷积码类的研究，近年来通 信工程工作者们在t u r b o 码上的研究热潮反映了这一特点。分组码则以其较完美 的数学特点吸引了更多编码理论和理论数学的研究者。 1 2 纠错码的发展史【”】 迄今，纠错码已有五十多年的历史，其发展过程大致分为以下几个阶段： 2 0 纪5 0 年代至6 0 年代初，主要研究各种有效的编、译码方法，奠定了线 性分组码的理论基础；提出了著名的b c h 码编、译码方法以及卷积码的序列译 码；给出了纠错码的基本码限；还出版了纠错码的第一本专著。这是纠错码从 无到有得到迅速发展的年代。 自2 0 纪6 0 年代至7 0 年代初，这是纠错码发展过程中最为活跃的时期。不 仅提出了许多有效的编译码方法，如门限译码、迭代译码、软判决译码和卷积 码的维特比( v i t e r b i ) 译码等，而且注意到了纠错码的实用化问题，讨论了与实 用有关的各种问题，如码的重量分布、译码错误概率和不可检错误概率的计算、 信道的模型化等，所有这些问题的研究为纠错码的实用打下了坚实基础。在此 期间，以代数方法特别以有限域理论为基础的线性分组码理论已趋成熟。 2 0 世纪7 0 年代初至8 0 年代，这是纠错码发展史中具有极其重要意义的时 期。在理论上以o o p p a 为首的一批学者，构造了一类g o p p a 码，其中一类子码 能达到香农在信道编码定理中所提出的码一一香农码，所能达到的性能，这在 纠错码历史上具有划时代意义。在这期间大规模集成电路和微机的迅速进展， 为纠错码的实用打下了坚实的物质基础，因而与实用相关的各种技术及有关问 题得到了极大关注，并在实用中取得了巨大成功。如美国在7 0 年代初发射的 “旅行者”号宇宙飞船中，成功地应用了纠错码技术，使宇宙飞船在极其遥远 的距离( 3 0 亿公里) ，向地面传回了天王星、海王星等星体的天文图片，发现了 天王星的9 个卫星和光环以及海王星的6 个卫星和光环等许多极其宝贵的资料。 若不应用纠错码，这些成就的取得是不可想象的。应当指出，在此期间利用f f t 技术，从频谱观点研究纠错码，受到了特别重视，使得很多熟悉信号处理技术 但不熟悉有限域理论的工程师们，能够较快地掌握纠错码理论，并能熟练地应 用于实际中，从而为纠错码在各类通信系统中的广泛使用，起到了极好的推动 作用。 自8 0 年代初以来，g o p p a 等从几何观点讨论分析码，利用代数曲线构造了 一类代数几何码。在这些码中，某些码的性能达到了香农码所能达到的性能。 由于代数几何码是一类范围非常广的码，在理论上已证明它具有优越的性能， 因而一开始就受到了编码理论工作者，特别是代数几何学家的重视，使代数几 何码的研究得到了非常迅速的进展，取得了许多成果。现在，代数几何码的研 究方兴未艾。 1 3 目前研究的现状 近年来，在信道编码定理的指引下，人们一直致力于寻找能满足现代通信 业务要求、结构简单、性能优越的好码，并在分组码、卷积码等基本编码方法 和最大似然译码算法的基础上提出了许多构造好码及简化译码复杂性的方法， 提出了乘积码、代数几何码、低密度校验码( l d p c ，l o wd e n s i t yp a r i t yc h e c k ) 、分组一卷积级联码等编码方法和逐组最佳译码、软判决译码等译码方法以及 编码与调制相结合的网格编码调制( t c m ，t r e l l i sc o d e dm o d u l a t i o n ) 技术。虽 然软判决译码、级联码和编码调制技术都对信道码的设计和发展产生了重大影 响，但是其增益与s h a n n o n 理论极限始终都存在2 d b 至3 d b 的差距。 在1 9 9 3 年于瑞士日内瓦召开的国际通信会议上，两位任教于法国不列颠通 信大学的教授b e r r o u 、g l a v i e u x 和他们的缅甸籍博士生t h i t i m a j s h i m a 首次提 出了一种新型信道编码方案一一t u r b o 码，由于它很好地应用了s h a n n o n 信道 编码定理中的随机性编、译码条件，从而获得了几乎接近s h a n n o n 理论极限的 译码性能。1 9 9 7 年，h o s t 、j o h a n n e s s o n 、a b l o v 提出了编织卷积码( w o v e n c o n v o l u t i o n a lc o d e ，w c c ) 的概念，随后编织码( w o v e nc o d e ) 便发展起来了。 它是一种组合码，其系统结构可完全包容传统分组码、卷积码以及各类t u r b o 码，开创了编码领域的一个新天地。 编织码的结构综合了并行级联卷积码( t u r b o 码) 和串行级联卷积码的结 构特点，当外编码器个数足够多时，该码型完全拥有了s h a n n o n 编码定理中随 机长码的特性，因此，其纠错性能理论上比t u r b o 码要优异。但编织码的编码 结构复杂性较高，编码效率也不高，目前研究最多的是1 3 的编织卷积码，译 码采用b c j r 算法的迭代译码。 此外h a m m o n s 等人在1 9 9 4 年通过适当的定义发现几种著名的非线性码可表 示为z 4 多项式环上的理想，其实质是环z 4 上的线性码，从而使得环上的线性码 的研究成为近二十年来编码界的热点之一。二十世纪九十年代，n e c h e v 、 h a m m o n s1 1 4 1 等人发现了二元k e r d o c k 码和其他的一些二元非线性码如 p r e p a r a t a 、d e l s a r t e g o e t h a l s 和g o e t h a l s 码等可以看作是环乙上线 性码在g r a y 映射下的二元象，有限环上的编码理论获得了重要突破。这 也使得有限环上的编码理论受到了广泛的关注，尤其是环乙上循环码 1 5 - i s 和自对偶码【l9 】等各项编码理论被广泛研究。1 9 9 7 年，万哲先1 2 0 院士 将此前关于环乙上编码理论的一些论文文献整理汇编成q u a t e r n a r y c o d e s 一书。近年来，环z 4 上的各项理论已被逐渐推广到模剩余类环z 。， c 阻】( “1 ) 。c a r l e t 2 1 l 、l i n g 2 2 】分别研究了环乙，z 。上的线性码的结构和 性质。b o n n e c a z e 和u d a y a t 2 3 l 深入研究了环e + 以上循环码及自对偶码，d i n h 【2 4 l 给出了环e + 识的g a l o i s 扩环上长为2 8 的常循环码，a b u a l r u b 2 5 1 ，q i a n t 2 6 1 还 分别进一步讨论了环五+ 幔+ 甜2 e ，只匝】( 甜) 上循环码的结构理论，此外朱士 信、李平、吴波、开晓山【2 7 _ 3 1 】研究了环e + 蛾+ + 甜卜1 e 上一类重根常循环码， 环c + 以上任意长度的循环码，环e + 幔上重根( 1 + 甜) 一常循环码的结构和性 质等。 1 4 本文的主要内容 就目前信息科学中纠错码研究的几个热点来说，t u r b o 码等涉及更多的是 有关通信工程方面的技术问题研究，而数学工作者们讨论更多的则是代数几何 码与环上码的理论研究。作者在纠错编码理论部分主要对环r = f 。+ u f 。上的 码做了部分研究，具体内容如下： 1 利用等价代换得到了环r 上长为p 的循环码的唯一表示方法，并在此基 础上给出了循环码的码字个数及对偶码的唯一表示； 2 讨论了环r 上长为p 的循环自对偶码的充要条件，给出了其计数，并分 别列出了当p = 3 ，j j = 1 和k = 2 时的所有循环自对偶码； 3 探讨了当( ，z ，p ) = 1 时环r 上( 1 + 口甜) 一常循环码、( 孝+ 口甜) 一常循环码的置换 等价性，并给出了其g r a y 像的结构； 4 研究了环r 上口一常循环码、 一口) 一常循环码的置换等价性及其计数， 并给出了口一常循环自对偶码的计数。 以上这些内容的研究，对进一步丰富纠错码在有限环上的理论及构造一些 性能好的码有一定的指导和实际意义，特别是对进一步研究环，+ “f 。上码的 距离和解码具有一定的指导意义。 4 第二章基础知识和基本定理 2 1 有限域的基本理论 2 1 1 有限域的特征 设p 为素数，整数集模p 形成阶为p 的域，记为c 或z 。，即 z 。= o ，l ，p 1 ) ，它按模p 的四则运算来计算。整数模一个素数得到的域是一 种最常见的域，它的许多主要性质可以推广到任意有限域上。有限域的特征显 示每一个有限域的阶是一个素数的幂且反过来对于每个素数幂都存在一个有限 域使得其元素个数恰好就是这个素数幂，具有相同数目元素的有限域之间是同 构的。 命题2 1 1 口2 】若k 是，的子域且fkf - q ，则lf | _ q ”，其中m = 【f ：k 】 证明f 是k 上的向量空间，由f 是有限域知f 是k 上的有限维向量空间， 称岛，b 2 ，是f 的一组基，从而f 的每个元素都可以唯一的表示为： q6 l + a 2 b 2 + + ，其中a i k ，扛1 ，2 ，扰。因为i k i = q ，故每个q 可以取到q 个 值，所以i f i = q ”。 命题2 1 2 3 2 】若，是有限域，则l f i = p ”，其中素数p 是f 的特征， 刀= 【f ：k 】o 证明因为f 是有限域，所以f 有素数特征p 。若k 是f 的素子域，则 k 兰只即k 中包含p 个元素，由命题2 1 1 知i f i = p ”。 从素域只开始，我们可以通过根的添加过程来构造其它的有限域。如果 厂c 【x 是上次数为，z 的不可约多项式，然后把f 的一个根和c 联合在一起 我们得到一个元素个数是p ”的有限域。然而，对于每个正整数玎是否都存在一 个c 【x 】中的甩次不可约多项式这一点我们不清楚。为了确定对于每个素数p 和 1 1 n 都有一个阶为p ”的有限域，我们利用下面结论中提供的方法。 命题2 1 3 3 2 1 如果f 是一个鸟阶有限域，那么v a f ，都有a q = 口。 证明( 1 ) 当a 0 时，显然a 9 = a ( 2 ) 当a 0 ，a f 时，的非零元关于乘法做成一个阶为( q 一1 ) 的 群，从而a q 一= a ，所以v a f ，a 0 也有a q = a 成立。 综上，v a f ，满足矿= a 。 命题2 1 4 3 2 】如果f 是一个q 阶有限域，x 是f 的一个子域，那么g x 】中 的多项式妒一x 在r x 】中可以分解为护一x = 兀( x 一口) ，且，是多项式x q x 在k _ 仨声 上的分裂域。 证明因为妒一x 在f 中至多有q 个根，而v a f 都有口e = a 。所以x q x 的 根也就是，的所有元素，故x q x 在f 上可分解为丌( x 一口) 而且它不能在f 的任 i 声 何真子域中分解，所以，是多项式矿一x 在k 上的分裂域。 我们现在可以证明有限域特征的主要定理，主要观点来源于命题2 1 4 。 命题2 1 4 【3 2 j( 有限域的存在唯一性定理) 对于任意的素数p ，栉z ，存 在一个阶为p ”的有限域；任何阶为q = p ”的有限域都同构于x q x 在e 上的分裂 域。 证明( 存在性) 由于q = p ”，假设，一x c 【x 】，令f 是x 9 一x 在c 上的分 裂域。因为( 矿一x ，q x q 一1 ) = 1 ，所以矿一x 没有重根即含有口个单根。取定 a = 以f ：a 9 = 口) ，因为 ( 1 ) 0 ，1 a ( 2 ) v a ，b a ，( 以一6 ) 9 = a 9 - b 9 = 口一b ，所以a b a 。 ( 3 ) v a ，b a ，b 0 ，( a b - 1 ) 4 = a q b 一9 = a b ，所以a b - 1 a 从而彳是f 的子域，另一方面x 。一x 必可在彳上分解( 这是因为彳包含了它的所 有根) ，所以a = f ，而ia | _ q ，所以f 是一个g 阶有限域。 ( 唯一性) 设f 是一个阶为q = p ”的有限域，由有限域阶数是其子域阶数 的方幂知f 的特征为p ，且凡是f 的子域，所以f 是多项式妒一x 在只上的一 个分裂域，而任意两个分裂域之间是同构的并且保持e 中的元素和妒一x 的根 是一一对应的，所以这样的f 是唯一的。 命题2 1 4 的唯一性部分说明了g 阶有限域( 或者6 a l o is 域) 这种说法的正 确性。我们可以记为疋，显然g 是e 的素数特征的一个方幂。 命题2 1 5 3 2 】( 子域判断准则) 设e 是阶为q = p ”的有限域，则e 的每个 子域的阶为p ”，其中mn ；反过来，如果mi 聆，则e 存在一个阶为p ”的子域。 证明当0 聊疗时，显然有e 的子域k 的阶为p ”，故q = p ”= ( p ”) 7 ，其 中，= 【r ： ，所以此时i；o kmn 反之，若mi 疗，记刀= 朋，则 p ”一1 = ( p 肿一1 ) ( p h 枷+ p 7 2 ”+ + p 2 ”+ p ”+ 1 ) ， 所以在e 【x 】中x 矿一一1lx 矿一一1 ，即x ，一xix ，一x ，从而x | 口_ 一x 的根是x 矿一x 的 根，即妒一x 的根属于e ，所以e 必有子域是x 一x 在e 上的分裂域。且此分 裂域的阶为p 辨：如果存在e 中两个阶为p ”的不同子域，那么它们综合起来所 含的元素个数超过e 中x 矿一x 的根的个数p ”，矛盾! 故唯一。 命题2 1 6p 2 l任一有限域e 的非零元作成的乘群c 是循环群。 证明因域至少要有两个元素，若域只有两个元素0 和1 ，非零元关于乘法 ( g ，) 组成单元素循环群g = e 。故考虑q 3 。令h = p 1 1 p 2 眨p m 是阶为h = q 一1 的乘群f+内的一个素因子分解，对任意lf所，多项式xm易一1在c上至多有。 办b 个根，因( h p ，) - 1 h ，即存在e 中的非零元不是多项式x m - 1 的根。令q 是这样的一个元素， 岛= a j 刖7 ，6 f 印= a i “= 1 ，故6 f 的阶是b 的因子，不妨设6 f 的 阶的形式为只毋，0 。又因为6 i 舟一= 7 研l ，所以包的阶为只。因此元素 b = 扛6 k 的阶为h ，事实上假设6 的阶是h 的因子，则存在f 使得b 的阶整除 办b ，不妨设f = 1 ，则有b 刖a = 1 = b l h l h 6 2 射n 6 卅射n 。当2 f5m 时b 整除办a ，所 6 以b t h i 崩= l 。所以b l h i n = 1 ，因此易1 整除| l z p l 即岛1 + 1h ，这与h 时素分解相矛盾。 所以f 是以b 为生成元的循环群。 定义2 1 1 3 2 1 循环群e + 的一个生成元又称为有限域e 的一个本原元。 命题2 1 71 3 2 】设c 是一个有限域，只是一个有限扩域，那么c 是e 的单代 数扩域且f 的每个本原元可以看作是e 在e 上的一个定义元。 证明令孝是c 的一个本原元。( f ) c 。另一方面，( 善) 包含0 与孝的 所有方幂，所以包含c 的所有元素，因此c ( 孝) = f r 。 命题2 1 81 3 2 1 对任意的有限域e 与正整数珂，存在一个c 【x 】上次数为门的 不可约多项式。 证明设只是c 的一个阶为9 ”的有限扩域，即【c ：】= ”，所以对某个 孝c ，有( 孝) = c ，那么善在上的极小多项式是一个次数为n 的【x 】上的 不可约多项式。 2 1 2 不司。约多项式的根 命题2 1 9 3 2 1 设f f , x l 是有限域上的一个不可约多项式，口是在的 一个扩域上的根，那么对于h 只k 】，h ( a ) = 0 营fh 。 证明设口是厂的首项系数，令g ( x ) = a - f ( x ) 。那z , g ( x ) 是c 【x 】上一个首项 系数为1 的不可约多项式，且g ( c t ) = 0 ，所以它是口在c 上的极小多项式，所 以h 硝x 】，h ( a ) = 0 gh fih 。 命题2 1 1 01 3 2 1 设f 【x 】是有限域上的一个聊次不可约多项式， ( x ) l x q ”一x c ，肌l 刀。 证明( i ) 设f ( x ) i 工一x ，令口是在c 上的分裂域中一根，那么口矿= 口， 所以口g 。 又因为。，所以【口】是g 。的一个子域， 口】：】= r n ，t f ：】- 疗，所以m i 珂。 ( ii ) 若r a in ，则乞。g 。，如果口是f 的一个根，因为【陋】：】= 聊， 故陋】- g ，所以口乃，进一步有口矿= 口，因此口是x 矿- - xe 【叫的一个根， 所以f ( x ) lx 矿一x 。 2 1 3 有限域上的多项式 除了次数以外，与有限域上的一个非零多项式相联系的还有另外一个重要的 整数即阶。一个多项式的阶的定义基于下面的结论之上。 命题2 1 1 11 3 2 1 设f f q x 是使得f ( o ) 0 的次所1 的多项式，则存在一个正 整数e q ”一l 使得厂( x ) l 一l 。 证明 因为剩余类环c x 】( f ) 包含q ”一1 个非零的剩余类，而g 脚个剩余类 x + ( 厂) ，j = o ，1 ，q 埘一l 全是非零的，所以存在整数，j ，0 r j q ”一1 使 7 得r 兰z 7m o d ( f ( x ) ) ，因为( 石，厂( z ) ) = 1 ，所以x ”董lm o d f ( x ) ，即( z ) lz 卜7 1 且 0 e 2 e r ，我们称此群的类型为 ( p q ) 帕( p 耳m r 。显然有m = m l e i + m r e ，并规定c = o ) 的类型为p o 。 例如加法群刃的类型为( 2 2 ) ”，因为它是n 个阶为2 2 的循环群的直和。我们 有： 刃= + ( 0 ，o ，x ，o ，o ) ix z 4 ) 其中每个 ( 0 ，0 ，x ，0 ，0 ) ix z 4 ) 是阶为2 2 的循环子群。 z 4 一线性码是召的一个子群，阶为2 的幂，所以可以讨论z 4 一线性码的类 型。很明显，等价的乙一线性码具有相同的类型。 z 4 一线性码的类型具有如下4 种形式：( 2 2 ) 肌，2 2 ) m 12 卅2 ，2 ”或2 0 。在接下来 的分析中，我们将( 2 2 ) ”简写为4 肘。 z 4 仅仅有三个子群，分别是4 1 ，2 1 或2 0 型，因此有三个长度为一的z 4 一线性 码，它们是： ( 0 ) ，( 1 ) ，( 2 ) ，( 3 ) ， ( 0 ) ，( 2 ) ) 和 ( 0 ) ) 现在让我们计算一下长度为2 的z 4 一线性码。很明显，乏的子群是 4 2 ，4 1 2 1 ，2 2 ，4 1 ，2 1 ，2 0 型。长度为2 且是4 2 型的z 4 一线性码仅仅只有一个，那就是看 且由z 4 上的2 2 矩阵生成： 此矩阵称为z 4 一线性码盈的一个生成矩阵。乏存在四个子群，是4 2 1 型， 且它们由下面的2 x 2 矩阵中的某一个生成： ， 1 0 很明显：( 三三 和( 三主 产生了相同的子群，所以第二个矩阵未被列入。 分别由第一个和第二个矩阵产生的乙一线性码是置换等价的，第三个和第四个 矩阵产生的z 4 一线性码也是如此，因此仅仅存在两个长度为2 且是4 1 2 1 型的不 等价的z 4 一线性码。 长度为2 且是2 2 型的z 4 一线性码仅仅只有一个，其有如下形式的生成矩阵： 它是一个自对偶码。 长度为2 且为4 1 型的乙一线性码的生成矩阵如下： ( 1o ) ，( 01 ) ，( 1 1 ) ，( 12 ) ，( 21 ) ，( 13 ) ，( 31 ) 很明显，前面两个矩阵产生了置换等价的z 4 一线性码，第四个和第五个及 第六个和第七个也是如此。另外，由第三个和第六个产生的z 4 一线性码是等价 的，因此存在三个长度为2 且是4 1 型的不等价的z 4 一线性码。 长度为2 且为2 1 型的z 4 一线性码的生成矩阵如下： ( 2o ) ，( o2 ) ，( 22 ) 很明显，前面两个矩阵产生了等价的乙一线性码，因此存在两个长度为2 且2 型的不等价的z 4 一线性码，且它们两个均是自正交的。 最后，长度为2 且是2 0 型的z 4 一线性码仅仅只有一个，即为 ( o ，0 ) ) 。 因此，总共存在1 0 个长度为2 的不等价的z 4 一线性码。 2 2 2 乙码的生成矩阵 定义2 2 1 啪1 设c 是码长为n 的z 4 一线性码，如果z 4 上的k x n 矩阵g 的行向 量生成c 且g 的行向量的任一真子集都不能生成c ，则称矩阵g 为c 的生成矩 阵。 命题2 2 1 【2 0 1 任一非零z 4 一线性码和以如下形式的矩阵g 为生成矩阵的 z 4 一线性码置换等价 ( it ab 、 i 了2 ci 1 ) 其中气，厶：分别是毛毛，岛如单位阵，a ，c 是z 2 上的矩阵，b 是z 4 上的矩阵， 则c 是类型为4 h 2 如的加法可换群，且c 共包含2 2 向+ 如个码字，当且仅当k = o 时， c 是自由z 。一模。 证明对码长n 作数学归纳法，分两种情况考虑： ( i ) c 中包含一个阶为4 的码字，则通过坐标变换( 必要时将码字乘以- 1 ) ， 可设该4 阶码字的形式为( 1 ，乞，巳) ，令c k ( o ，恐o to 吒) c ，显然c 是z 4 一 线性码，且通过删除第一个坐标可将其看作是码长为一1 ) 的线性码。 由归纳假设， 4且、 2 i k ：2 c1 其中4 ，c l 为z 2 矩阵，蜀为z 4 矩阵，则c 有生成矩阵 气+ i 气+ 七2 4 2 厶： c 屯+ 1 2 + l 厶 最 2 c 该矩阵的后( k 。+ k ：一1 ) 行的适当线性组合加到第一行，可得到形如( 2 1 ) 的生 成矩阵。 ( ii ) c 中不含4 阶码字，则c 中所有非零码字的阶是2 。 因为c 0 ”) ，则c 中含有一个阶为2 的码字。与( i ) 相似可设该码字为 ( 2 ，2 巳，2 c ) ，类似( i ) 定义c 是不含4 阶码字的z 。线性码，c 可看作是码 长为。一1 ) 的码，由归纳假设，c 的生成矩阵形如( 02 厶：一。2 c 1 ) ，其中c 是z ： 矩阵， 则c 有