（应用数学专业论文）线性码的若干问题研究.pdf

线性码的若干问题研究 摘要 目前，随着有限域上纠错码理论的不断深入和完善，一些纠错性能好的码 不断涌现，如此同时，构建新码和好参数的码，已经吸引了大批从事纠错码研 究的工作者。女w x i n gc h a o p i n g 、l i n gs a n 、a y d i nn u h 等编码研究专家，都给出 了构造好码的方法和具体的好码。另一方面，随着文献 1 】的发表，人们发现有 限域上些好参数的非线性码，可以将有限环上的线性码通过g r a y 映射而得到， 因此，对于有限环上码的研究，成为近十几年纠错码研究的另一热门。鉴如此， 本文的主要内容如下： 1 、介绍了有限域咒上一种特殊的m d s 码一多项式码，将x i n gc h a o p i n g 和 l i n gs a n 在文献【2 ，3 】中的构造好码的方法，从新的角度进行推广：定义 了一类新的多项式函数，再由这类新的函数构造了一类新码，并且通过 验证，可以得到一些具有较好性能参数的线性码。 2 、以有限域取上二次剩余码的理论为基础，定义了f 上特殊长度的三次 剩余码，研究了六种三次剩余码之间的关系，同时，给出了三次剩余码 的对偶码和一些生成幂等多项式。 3 、定义了有限域配上的广义准循环码，并构造了一类贬上的线性码，给 出了此类码的极小汉明距离范围和码的维数。 4 、将有限域屹上的常循环码的概念推广到有限环z 矿上，证明了z ，。的某 个g a l o i s 扩环上常循环码和循环码的等价关系，在此基础上，构造出z ， 上一类新的常循环码，它与有限域上设计距离为d 的b c h 码有相似的性 质：具有b c h 界。 关键字：多项式码b c h 码s i n g l e t o n 界汉明距离 新迹函数 4 r e s e a r c ho i ls o m ep r o b l e m so fl i n e a rc o d e s a b s t r a c t a tp r e s e n t ，w i t ht h er a p i dd e v e l o p m e n ta n dp e r f e c t i o no fe r r o r c o r r e c t i n g c o d i n gt h e o r yo v e rt h ef i n i t ef i e l d ，m a n yg o o dc o d e sh a v ee m e r g e di nl a r g en u m b e r s a tt h es a m et i m e ，m a n yr e s e a r c h e so ne r r o r - c o r r e c t i n gc o d i n gt h e o r yh a v ed r a w n i n t e n s i v ea t t e n t i o no nt h em e t h o d so fc o n s t r u c t i n gn e wc o d e sa n dg o o dc o d e s ， e s p e c i a l l yt h el i n e a rc o d e s f o re x a m p l e ，x i n gc h a o p i n g ，l i n gs a n ，a y d i nn u h ，e t c ， h a v ep u tf o r w a r dt h em e t h o d so fc o n s t r u c t i n gg o o dc o d e sa n dg i v e nm a n yg o o d c o d e s o nt h eo t h e rh a n d ，晰mt h ep u b l i c a t i o no fp a p e r 1 】，r e s e a r c h e sf r e ds o m e g o o dp a r a m e t e rn o n l i n e a rc o d e so v e rt h ef i n i t ef i e l db ea b l et ob eo b t a i n e db yt h e g r a ym a pa n dl i n e a rc o d e so nt h ef i n i t er i n g s o ，i nr e c e n td e c a d e ，t h er e s e a c ho n c o d e so nt h ef i n i t er i n gh a v eb e e np o p u l a r h e n c e ，t h i sd i s s e r t a t i o na r ea r r a n g e d 嬲 f o l l o w s ： w ei n t r o d u c et h en o t i o no fn e wt r a c ef u n c t i o n so v e r f q ，a n du s i n gt h e n e wt r a c ef u n c t i o na n de l e m e n t so fs o m ee x t e n s i o n so f ，w ed e v e l o p l i n ga n dx i n g si d e ao f 【2 , 3 】t oc o n s t r u c tn e wq - a r yl i n e a rc o d e s o u r r e s u l t ss h o wt h a ts o m ec o d e sf r o mt h i sc o n s t r u c t i o nh a v eg o o d p a r a m e t e r sb a s e do nb r o u w e r st a b l e 4 】 2 o nt h eb a s eo fq u a d r a t i cr e s i d u ec o d e so nf 2 ，w ei n t r o d u c et h en o t i o n 4 o fs i xc u b i c r e s i d u ec o d e so v e rf 2 t h er e l a t i o n sb e t w e e nc o d e sa l e d i s c u s s e d ，a n dt h eg e n e r a t i n gi d e m p o t e n t sa n dt h ed u a lc o d e sa r ea l s o s t u d i e d w ed e f i n et h eg e n e r a l i z e dq u a s ic y c l i cc o d e so v e rt h ef i n i t ef i e l d 屹， c o n s t r u c tak i n d o fl i n e a rc o d e so v e r ，a n dg i v et h eh m n m i n g d i s t a n c ea n dd i m e n s i o no ft h e m t h ed e f i n i t i o no fc o n s t a c y c l i cc o d e so v e rf i n i t ef i e l d s 咋i se x t e n d e dt o t h ef i n i t er i n g z ，f i r s t l y t h e s t r u c t u r eo fc o n s t a c y c l i cc o d e so v e r r i n gz ，i si n t r o d u c e d i ns h o r t t h ee q u i v a l e n tr e l a t i o nb e t w e e n c o n s t a c y c l i cc o d e sa n dc y c l i cc o d e so ns o m eg a l o i sr i n go f z ，i s p r o v e n a tl a s t ，s o m es p e c i a lc o n s t a c y c l i cc o d e sa r eg i v e n ，w h i c hh a v e s i m i l a rp r o p e r t i e st ob c hc o d e so fd e s i g n e dd i s t a n c edo v e rf i n i t ef i e l d ： t h eh a m m i n gd i s t a n c e _ d k e yw o r d s ：p o l y n o m i a lc o d e s ，b c hc o d e s ，s i n g l e t o nc o d e s ，h a m m i n gd i s t a n c e ， n e wt r a c ef u n c t i o n 6 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的研究成果。 据我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经发表或撰写 过的研究成果，也不包含为获得 盒胆工些太堂 或其他教育机构的学位或证书而使 用过的材料。与我一同工作的同志对本研究所做的任何贡献均己在论文中作了明确的说明 并表示谢意。 学位论文作者签名： 签字吼炒苫年z 月f 7 日 学位论文版权使用授权书 本学位论文作者完全了解金目巴王些太堂有关保留、使用学位论文的规定，有权保留 并向国家有关部门或机构送交论文的复印件和磁盘，允许论文被查阅和借阅。本人授权尘 目巴：e 些太堂可以将学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、 缩印或扫描等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后适用本授权书) 学位论文作者签名： 签字嗍舻占月。7 日 学位论文作者毕业后去向： 工作单位： 通讯地址： 2 导师签 解醐砌酬刖7 日 电话： 邮编： 致谢 本人在三年的硕士研究生课程学习和撰写学位论文的过程中，自始至终得 到了我的导师朱士信教授的悉心指导，无论从课程学习、论文选题，还是到收 集资料、论文成稿，都倾注了朱老师的心血，由衷感谢朱老师在学业指导和生 活方面所给予我的关心，以及从言传身教中学到的为人品质和道德情操，老师 广博的学识、严谨的治学作风、诲人不倦的教育情怀和对事业的忠诚，必将使 我终身受益，并激励我勇往直前。在此论文即将完成之际，作者向朱老师致以 最诚挚的敬意和衷心的感谢! 同时，还衷心的感谢师兄李平、吴波、开小山、施敏加、唐淼和师姐王冬 银、王敏秋，以及张道福、许和乾、宛金龙、孙琳、姜光峰等同学给我的帮助， 在此一一表示感谢。 最后，感谢我的父母、大哥、姐姐、二哥、弟弟、妻子，在我三年的研究 生生活中给我无私的帮助。 作者：陈安顺 20 08 年4 月 第一章绪论 1 1 引言 s h a n n o n 于1 9 4 8 年发表了题为“am a t h e m a t i c a lt h e o r yo f c o m m u n i c a t i o n ”【5 】的 论文，在文中s h a n n o n 首次提出了著名的有扰信道编码定理，这篇论文的发表， 开创了纠错码理论的研究方向，标志着纠错码理论开始形成。由s h a n n o n 的思想， h a m m i n g 【6 1 、m a s s e y 7 9 1 、m a c w i l l i a m s b o - 1 2 、g o p p a l l 3 q 4 】、x i n gc h a o p i n 9 1 2 3 】、l i n g s a n 2 。3 】、s l o a n e 1 5 1 6 】等纠错码理论研究的专家先后给出了一系列好码构造和译码 方法。随后，纠错码受到越来越多的通信和数学工作者的青睐，纠错码理论在 实际通信中的应用也越来越广泛。 迄今，纠错码已有五十多年的发展史了，其发展过程主要分为以下几个阶 段： 2 0 世纪5 0 年代至6 0 年代初，主要研究各种有效的编码、译码方法，奠定了 线性码的理论基础，提出了著名的b c h 码【1 7 1 9 1 ，同时，给出了纠错码的基本码 限，对卷积码的研究也进入了初步阶段。这一时期，可以说是纠错码的研究从 无到有的发展过程。 6 0 年代至7 0 年代初，许多有效的新的编码、译码方法不断涌现，与此同时， 随着微机技术的迅猛发展，纠错码理论已开始应用于实际生活，而以代数方法 研究纠错码成为主流。这一阶段，是纠错码理论研究的活跃期。 7 0 年代至8 0 年代初，这是纠错码发展史中最重要的时期。g o p p a 码 1 3 - 1 4 】的提 出，具有划时代的意义，同时，纠错码理论与实际应用的联系更加紧密，在信 息通信、图像处理等领域，纠错码理论已得到应用。 8 0 年代以后，特别在1 9 8 2 年，t s f a s m a n 等人证明了一个惊人的结果：存在 渐近好的代数几何码，超过t g i l b e r t v a r s h a m o v 界【2 0 】。这一结果的出现，使代 数几何码很快成为了编码理论中的一个热门。8 0 年代人们主要研究了各种曲线 上的代数几何码的性质和参数，其中对h e r m i t e 曲线和k l e i n 曲线上的代数几何 码，结果最为丰富。到8 0 年代后期，译代数几何码的问题受到关注，直至u 1 9 9 1 年，g l 。f e n g 和t r 。n r a 0 才找到一种译码方法。现在，人们关注更多的是：构 造好的代数几何码，这就需要简化或改进代数几何码，另一方面，代数几何码 要走向应用，也需要简化和改进。在实践应用中，纠错码技术已经渗透到很多 领域。利用纠错码中的编码、译码方法和原理，与通信系统中的其他相关技术 相结合，得到了令人惊喜的结果。例如，纠错码与调制技术相结合所产生的t c m 技术，已经作为国际通信中标准技术而推广使用。又如，纠错码与密码相结合， 可以构造出一类既能加密又具有纠检错功能的密码系统。不仅如此，纠错码中 的许多译码思想和方法，与神经元网络中的能量函数有密切关系，纠错码的许 多译码技术，可以用来解决神经元网络中的一些问题。因此，可以断言：随着 科学技术的不断发展和实际应用的源源需求，纠错码理论必将进一步发展，它 的应用范围必将进一步拓宽，对纠错码理论研究的重视度必将进一步提高。 1 2 本文的主要内容 目前，随着有限域上纠错码理论的不断深入和完善，一些纠错性能好的码 不断涌现，如此同时，构建新码和好参数的码，已经吸引了大批从事纠错码研 究的工作者。如x i n gc h a o p i n g 、l i n g s a n 、a y d i nn u h 等编码研究专家，都给出 了构造好码的方法和具体的好码。另一方面，随着文献 1 】的发表，人们发现有 限域上一些好参数的非线性码，可以看成是有限环上线性码的g a r y 映射的像， 因此，对于有限环上码的研究，成为近十几年纠错码研究的另一热门。鉴如此， 本文的主要内容如下： 1 、介绍了域兄上一种特殊的m d s 码【1 2 2 1 】一多项式码【2 1 1 ，将x i n gc h a o p i n g 和l i n gs a n 在文献【2 ，3 】中的构造好码的方法，从新的角度进行推广：定义了一类 新的多项式函数，再由这类新的函数构造了一类新码，并且通过验证，可以得 到一些具有较好性能参数的线性码。 2 、以有限域f 上二次剩余码【1 2 盈】的理论为基础，定义了r 上特殊长度的 三次剩余码，研究了六种三次剩余码之间的关系，同时，给出了三次剩余码的 对偶码和一些生成幂等多项式。 3 、定义了有限域疋上的广义准循环码，并构造了一类圮上的线性码，给 出了此类码的极小汉明距离范围和码的维数。 4 、将有限域疋上的常循环码的概念推广到有限环z ，上，证明了z 矿的某 个g a l o i s t 2 3 1 扩环上常循环码和循环码的等价关系，在此基础上，构造出z 一上一 类新的常循环码，它与有限域上设计距离为d 的b c h 码有相似的性质：具有b c h 界。 这些内容从多方面研究了线性码的若干问题，主要涉及到新线性码的构造。 这些理论进一步丰富了纠错码的理论，在某一些方面，具有一定的指导意义。 2 第二章构造好码的两种方法 自从s h a n n o n 于1 9 4 8 开创了纠错码理论以后，纠错码理论研究已经经历了五 十多年的发展，而构造好码，即纠错性能优越的码( j t i m d s 码) ，一直是纠错码 研究的热门，如编码专家x i n gc h a o p i n g 、l i n gs a n 、a y d i nn u h 在文献【2 ，3 】中给 出的好码。本章主要以有限域上一种m d s 码一多项式码的构造思想为基础，分 析t x i n gc h a o p i n g 、l i n gs a n 在文献 2 ，3 】中构造好码的方法，再从另一个角度， 给出了另一种构造码的方法，对应此种构造方法，产生了一些参数比较好的线 性码。 2 1 多项式码【2 l 】 本节主要围绕有限域上多项式码，先介绍了一些关于纠错码的初步知识， 给出了多项式码的定义和性质，以及相关证明。 2 1 1 有限域上的m d s 码 在介绍m d s 码之前，我们先来规定整个论文中的几个记号：圮表示包含q 个 元素的有限域，其中q 是某个素数p 的方幂；砸：表示有限域e 的乘群，即集合 酵= e 一 0 关于乘法运算构成的循环群；n 表示正整数，酵表示有限域晚上的 玎维向量空间。 定义2 1 叼的一个线性子空间c 称为有限域圮上长为，z 的线性码，若c 的 维数为k ，则称c 是一个i 刀，k l 的线性码，c 中的每一个向量称为c 中的码字。 显然，c 中含有g 。个码字。关于c 的生成矩阵和校验矩阵等概念可以参照文献 1 2 】。 定义2 2 对于向量空间砸：，中的向量c = ( c o ，c l ，巳一，) ，我们称c 的分量 q ( 0 f n 一1 ) 中非零元素的数目为码字c 的汉明重量，记为w t ( c ) ：对于酵中 的任意两码字x = ( x o ，一，矗一) 和y = ( y o ，咒，一。) ，我们称对应同一位置分 量不同的位置个数为码字x 和y 的汉明距离，记为d i s t ( x ，y 1 ，即 d i s t ( x ，j ，) = w t ( x o y o ，五一m ，矗一l - y ) ；对于町的任意子空间c ，我们称 m i l l d i s t ( x ，y ) l x ，y c 为码c 的极小汉明距离，简称c 的汉明距离。 例如：w t ( 1 0 l ll o ) = 4 ，w t ( 1 4 3 0 2 0 3 1 = 5 ，d i s t ( 3 0 2 1 ，1 0 0 1 ) = 2 。 如果c 是兄上长为n 的线性码，则c 中的向量对于加法是封闭的，因为 d i g t ( x ，y ) = w t ( x o - y o ，五一m ，吒1 一一1 ) ，所以线性码c 的汉明距离就是c 中 码字的汉明重量最小值，虽1 ：f i r a i n d i s t ( x ，y ) x ，y c = m i n w t ( c ) c c ) 成立。 - 若m i n u ，f ( c ) l c c - d ，线性码c 的维数为k ，我们称c 是参数为【玎，k ，d 】的码 对于酡上的线性码c 有一个重要的s i n g l e t o n 界： 定理2 1 若吒上的线性码c ：【，2 ，k ，d 1 ，则d 玎一k + l 。 口 定义2 3 设c 是屹上参数为【玎，k ，d 】的线性码，如果d = n - k + 1 ，我们称c 为最大距离可分码，简称m d s 码。 例如：设b = o ，1 ，口，口2 ) ，其中口是本原的2 次单位根，由矩阵： 1 0 ：) 纠l 1口 口2 j 在e 上生成的线性码，容易验证此码的参数为：【4 ，2 ，3 】，则它是m d s 码。 关于m d s 码的更多介绍，可以参照文献【1 2 】。 2 1 2 多项式码 下面我们来介绍m d s 码的一个特例一多项式码： 定义2 4 设正整数刀和k 分别满足条件：1 以q 、1 k 拧，集合 q ，吃，) 表示巧的子集，最表示由环哆【x 】中次数 七的所有多项式构成的 集合，称码c = 厂( ) ，( 口：) ，( ) l 厂( x ) 最 为上的多项式码。 关于多项式码的更多性质，可以参照文献【2 1 】。下面我们给出它的一个重要 性质： 定理2 2 多项式码c 是上的线性码，且参数为【玎，k ，n - k + 1 】，i 撇m d s 码。 证明：设集合 m = f 【x l d e g k - 1 是屹上的k 维向量空间， 1 ，并，z 2 ，以 是m 的一组一基。考虑映射 缈：m 一叼，伊( 厂) = ( 厂( q ) ，( ) ，厂( ) ) 易知这是一线性映射，并且c = i m f o = 缈( m ) 。所以c 为砸：；l 的向量子空间，即 c 是q 元线性码，码长为聍。为了证明d i m c = k = d i m m ，我们只需证明缈是单 射，即要证k e r ( 伊) = 0 ，这里 k e r ( o ) = 厂m i 妒( 厂) = ( o ，u ，0 “，o ) = f m i 厂( 岱。) = 厂( 口：) = = 厂( ) = 0 由于d e g f 七一1 刀一l ，当0 时，厂至多有n - 1 个零点。所以当q ，均 为f ( x ) 的零点时，必然厂= 0 。这表明k e r ( t p ) = 0 ，于是d i m e = k = d i m m 。对 于c 中非零码字c 厂= ( ( q ) ，厂( ) ，厂( ) ) ，厂( 石) 【x l ，d e g f ( x ) _ k 一1 。 如果w f ( 勺) n - k ，则，当中至少有n - ( n k ) = k 为厂( x ) 的零点，即 s ( x ) 至少有七个不同的零点。由于d e g 厂( 工) k - 1 ，可知厂( x ) 恒等于零，则c ，为 零向量。这表明c 中的非零码字的h a m m i n g 重量均1 1 - - k + l 。于是d 刀一k + l ， 再眭i s i n g l e t o n 界可知d = 刀- k + l 。从而c 时m d s 码。 口 4 2 2 由特殊多项式函数构造好参数的线性码 本节运用多项式码的构造原理，介绍t x i n gc h a o p i n g 和l i n gs a n 在文献【2 】 中一种构造好码的方法。本节中规定q 是奇数。 在介绍构造码的方法之前，我们先看文献 1 2 1 中的一个重要定理： 定理2 3 距离为d 的码可以纠正巴( d 1 ) 个错误( 其中“ ”表示取整符 号) 。若d 是偶数，则可以纠正当( d 一2 ) 个错误，并且可以观察到兰个错误。口 由定理2 3 我们可以知道：对于等长等维数的线性码，距离越大，其能纠正 错误的个数就越多，纠错性能就越好。也就是说，对于某些有限域上的线性码， 码长和维数一定时，距离大的码相对而言是好码。显然，由定理2 1 和定义2 3 ， m d s 码是好码。更多的好码，我们可以在网站【4 】上查询。 下面我们来介绍一类好码的构造方法： 设有限域屹= q ，口：，) ，艺：表示的2 次扩域，设届巴：一屹，其中 z ：1 z ， 显然局- 局。我们同样可以列出e ：中的元素： 吃：= 吼，届，群，屏，群 ，易知，= ( 9 2q ) 2 。 引理2 1 设f ( x ) 是多项式环砸：【_ ) c 】中的任意多项式，局艺：一码，则对于 任意，：1 ，厂( 届) = 0 当且仅当厂( 局9 ) = 0 。 证明：由等式厂( ) = 厂( 届) 9 立即就证明了引理。 口 对于整数f ，j 0 ，令多项式( x ) = x 卅7 + 石州，则我们可以得到下面的 引理2 2 任意吃：，则q ，( ) 是吒中的元素；对于整数m ：1 所q ， 若令集合e = q 。，( x ) l o j j m - 1 ，则e 中的元素是码一线性无关的。 证明：通过验证易知：l 巳( ) l 。= ( ) ，所以证明了q ( ) 吗。又因 为f ，所以多项式岛，x ) 撇d e g ( e “( x ) ) = 影+ f 。而对于集合e 中的所有 多项式，可知它们的次数是两两互不相同的。即证引理。 口 对于整数m ：ism q ，我们定义由集合e 生成的咒一线性空间，即 圪= ( e “( 戈) l o i _ ，m - i ) ，其中“ ”表示生成的意思。由引理2 2 易知： 对于任意多项式( x ) 和屹：中任一元素，有f ( f 1 ) 屹成立；且圪的维数 d i m ( v m ) = i q ，( x ) l o _ i - j - m 一1 l = 寺肌( m + 1 ) 。下面我们定义一种新码： 定义2 5 设整数f 和m 分别满足：0stsq 、l m q ，定义码c 。( f ，m ) ： c 。( f ，m ) = 厂( ) ，厂( 口：) ，厂( q ) ，f ( f 1 1 ) ，f ( f 1 2 ) ，( 屏) i 厂( x ) 圪 。 定理2 4 码c ，( f ，朋) 是吒上参数为i 门= r + ( 9 2 一g ) 2 ，k = 吉朋( 脚+ 1 ) l 的线性 码。 证明：由码c 。( f ，m ) 定义，易知它是线性码，且码长行为f + ( q 2 一q ) 2 。设 对于中任意多项式i ( x ) ，对应码c 。( f ，m ) 中的码字可以为 c m l = ( 厂( q ) ，厂( 口：) ，厂( ) ，厂( 届) ，厂( 屈) ，厂( 屏) ) 。由定义可知： j a o , o 口0 ，1 ，- 】州屹，使得c ，( ，) 2a o , o 气。( ，) + a o 1 c e o ，( ，) + + 一l 朋一l c e 一州( ，j ，假设 c r ( ，1 0 ，则口。，口2 ，届，屏是- f ( x ) 的根，由引理2 1 可知局9 ( 1 f ( g + 1 ) ( q 一2 ) ( g + 1 ) ( 小一1 ) ，但由于s ( x ) 的最大次数为 ( g + 1 ) ( 朋一1 ) ，f f f 以f ( x ) = 0 。即证得当c f ( ，) = 0 时，口0 ，。= a o ，。= = 一。朋一。= o ， 所以，( ，) ，气，( ，) ，气如d ( ，) 是线性无关的。即七= d i m ( 圪) 一i ，m ( m + 1 ) 。 口 关于线性码c 。( f ，m ) 的距离，我们有下面的 定理2 5 对于整数r 和m ：0 t q 、1 m q ，码c g ( f ，m ) 的距离d 满足不 等式：d f + q 2 _ q ) 2 一告 ( q + 1 ) ( m 一1 ) + m i n 2 ( m 一1 ) ，f ) 。 2 f 胛一n 证明：设任意多项式厂( x ) 圪且( x ) 0 ，厂( x ) = e 口，q ，x ) ， s = u ，+ = s 0 ，j r a - i 其中口，厂( z ) 对应码c 。( f ，m ) 中的码字为，) ，要证明d 的范围，只要证 明w f ( c ，( ，) ) 的范围。我们分两种情况： 1 ) 对于j ：o j 2 ( 优一1 ) ，当q = o 时，我们有： l + ，= j 0 s ，si m - 1 2 ( 肼一1 ) s ( x ) = 口u e u ( x ) j = u，+ ，= j o s ，s j m 一1 2 ( m 一1 )2 ( m 一1 ) ii = 。( x ) 一。l q ，lx s + x q s ) 9 0 茹j m 一，9 0 苟j m - ij o s ，sl 0 s f s = 口，( x 卅+ 7 + x 倒“一x 。一x 伊) s = o ，+ = s 0 s 信l m - i = 。a i , jx 训一x ) ( x 7 一石) s = o ，+ = s 0 s ，s j m - 1 龇，x q - - x ) 1 2 酬枷瞅臌咖) 2 e 咻鼬肛例 则屈( 1 f 厂) 是( x ) 的根当且仅当屈是g ( x ) 的根。又因为g ( f l , ) = o 当且仅当 6 g ( 屈。) ：o ，所以厂( x ) 在集合 层，岛，屏) 中至多有d e g ( g ( z 个根，在集 合 ，屈，腹，屏) 中至多有f + d e g ( g ( x 个根。因此码字，) 的重 量 w 心) 狲( 产g ) 2 一卜如g ( g ( 工 ，+ ( q 2 一g ) 2 一 f + 专( ( g + 1 ) ( ，”一1 ) 一2 q ) 1 = r + ( e - q ) p - 一圭( g + 1 ) ( 聊一1 ) + ( g r ) f + ( 9 2 一q ) 2 一凯( g + 1 ) ( 聊一1 ) + m i n 2 ( 掰一1 ) ，r 2 ) 当a i 0 时，x c 3 ：某+ u ：o “ 2 ( m - 1 ) ，存在s ：甜 s _ 2 ( m - 1 ) ， 0 i + 芏j f = u ，蔓卅一1 设口码，若厂( 口) = o ， 等价 2 a 5 a i ，- 0 。所以，口是厂( 工) 的根当且仅当口是q ，r 的 s ut + j = s s = ol + i = s 0 s ，! ，堋一i o j o s j g - n l 根。又因为甜2 ( m - 1 ) ，所以f ( x ) 在集合 ，q ) 中至多有 m i n 2 ( m 一1 ) ，t 个根。设厂( 工) 在集合 喁，q 和 屈，尾，屏) 中分别有吒、 r 2 个根，所以_ m i n 2 ( m 一1 ) ，t ，i + 2 r z d e g ( 厂( 石) ) - ( q + 1 ) ( m - 1 ) 。最后可 以得到 ，i + 吃= 去( ，i + 2 吒+ ，i ) 寺( ( g + 1 ) ( 聊一1 ) + m i n 2 ( 研一1 ) ，r ) 。 口 对比网站 4 】上提供的关于线性码的参数，利用定义2 5 ，我们可以得到一些 好码，例如：当q = 7 时，用玎，k ，d 分别表示线性码的长、维数、距离， mf力 k d 312 261 4 3 32 461 5 3 72 861 8 47 2 8 91 4 7 0 = 口 q 2 一 赫 旧 枷 = 口 形 q 赫 - 、噼 鲫 即 2 3 由新迹函数构造新的线性码 x i n gc h a o p i n g $ 1 1 l i n gs a n 又在文献【3 】中将上一节的结果进行了推广，本节 主要是从另一个角度将文献【2 】中的构造码的方法进行推广。首先，定义了有限 域上的一类特殊多项式，再利用此类多项式和。中的元素构造了一些线性码。 经检验，它们是参数较好的码。 设彳是由m ( 掰2 ) 个整数l ，_ 2 ，j 肌的全排列构成的集合，为了便于说 明，当m 个数相同时，如：j l = j 2 = = 厶= 1 时，我们忽略集合的互异性，认 为a 中仍然含肌! 个( 1 ，1 ，1 ) 。 定义2 6 ( 新迹函数) 设g 是某个奇素数p 的m 次幂，m ( 2 m p 1 ) 个整 数 ，如，l 满足：0 j l 办厶t - 1 g - 1 ， 令 乃。：以( x ) =x 叮”止广2 + “斗厶，对于有限域f 口中的任意一个元素口有 ( 1 儿，l ) e a t j ! 2 讥q 以) =口止广 ，饥9 ， 因为( l ，2 ，l ) a ， 易知 ( ，j 2 ，l ) e ( ，2 ，_ 3 ，- ，。，j 1 ) a ，即y j ! , j 2 , , j m q 缸) = t j l 如。几 ) 所以毛如，厶 ) 码，我们称 乃一：，厶( x ) 是有限域上的新迹函数。 显然，当y i t ( j ，j 2 ：，j r ) = ( 0 ，0 ，1 ) 时，乃m ，几( x ) 就是 2 4 】中定义的一般 迹函数的m ! 倍。一般地，毛如，厶不是从兄。到码的同态映射，但l 如_ 也 有一些与迹函数相似的性质： 定理2 6 乃m _ ) = 0 当且仅当0 f m 时有：毛如_ 一) = 0 。 证明：因为毛如，l 一) =口 ，脚“2 + 呻l 一 = y 口 + i g ”1 + + 2 9 ”2 + + m q + q “+ 2 一- 2 + + ， c j , 2 ：z 。) e a 显然，( f + l ，m ，j m ，j l ，2 ，工) a 。所以毛缸_ 矿) = 乃m ，。以 ) 。 口 因为取不同m 个整数 ，：，j 。时，得到不同的哆上多项式毛如。l ( x ) ， 我们有下面的定理： 定理 2 7 在0 到f 一1 间取m 个整数_ ，i ，j 2 ，厶： r a - 1 0 j 1 j 2 j 棚 t - 1 g - i ，得到的c ，一c ：一l ( 其中c ，是组合数) 个 i = o 多项式t 一：，山( z ) 在屹上是线性无关的。 证明：对整数加进行归纳，可以得到c ，一c j ：| 一。组不同的整数 ，- ，：，册， 易知多项式l 儿。厶( x ) 次数：d e g t j ：，以( x ) = _ ，。g 剃+ _ ，。一l q ”一2 + + j l ，而 0 j l j 2 j 。t 一1 g - 1 ，则取不同的整数组_ ，l ，2 ，。得到的多项式 l 2 厶( z ) 的次数不同，即c ，一c 剃1 个多项式l 。如，l ( z ) 是互不相同的，所 以它们在是线性无关的。 口 令匕，。表示由集合留 如，l ( x ) i o l 2 _ ， 1 ) 1 0 所以，定理得证。 a i m 州) 一罢筹i t“2y 一 口 设、d 、k 分别表示屹上线性码的长度、汉明距离、维数。结合上面的 构造码的方法，可以得到一些参数较好的线性码，例如： g mfnk d 5221 5 37 52 。 3 1 5 64 5 324 54 3 0 5 334 5 1 02 0 72 22 831 7 7 232 861 3 7321 1 94 9 3 7 331 1 91 07 4 显然，随着g 的增大，利用这种方法我们能得到更多的哆上的码，此外， 我们还可以如 2 ，3 q u j i g 样引入新的变量，来得到更多的码。经验证，有些码与 b r o u w e r 表格( 见 4 】) 中的码参数相近甚至更好。 第三章有限域蝗上的三次剩余码 n j a s l o a n e 和f j m a c w i l l i a m s 编写的“t h et h e o r yo fe r r o r - c o r r e c t i n g c o d e s 1 2 】”，是一部关于纠错码理论的科学著作，这部文献非常系统、详细的介 绍了纠错码的发展，并提出了许多问题至今还十分有研究价值。本章正是以文 献 1 2 】中的第1 6 章所讲的内容。二次剩余码为蓝本，定义了醍上的三次剩余 码，并从相似的角度，对f 2 上的三次剩余码进行了研究。 3 i 二次剩余码1 1 2 】 3 i 1 循环码 循环俏从一开始，就以兵独特的性质，在编码钡域占有。十分重要的地位。 作为需要，我们先介绍一些关于循环码的基础知识： 定义3 1 对于一个长为玎线性码c ，若v c = ( c o ，c 1 ，q 一。) c 都有 ( c n ，c o ，c n 一：) c 成立，则c 称为循环码。 我们可以用甩一1 次多项式来表示c 中的码字，即码字c 可表示为： c o + q x + + 厶一l 工”1 。在文献【1 2 中，关于有限域吒上的循环码已经说得很详细， 对于本章，我们列出一些在后面要用的结果：设c 是有限域f g 上长为n 的循环 码，c 可以看成是环【x 】( ，一1 ) 的一个理想，因为环【z 】( x ”一1 ) 是主理想 环，则存在厂( 石) 嚷 工1 ( ，一1 ) 使得c = ( 厂( 工) ) ，即厂( x ) 称为c 的生成多项式； 对于c 的生成多项式，存在唯一的首项系数为1 的多项式g ( x ) 码 z j ( x n 一1 ) 且 g ( x ) l ( 一1 ) ，使得c = ( g ( x ) ) ，易知c 的维数七= 玎一d e g ( g ( z ) ) ，多项式 五( x = ( x n - - 1 ) g ( x ) 称为c 的校验多项式：多项式g ( x ) 【x l ( x ”- i ) ，若 p ( x ) 2 = e ( x ) ，则称e ( 工) 是c 的幂等多项式，对于吒【x j ( x ”一1 ) 的任意理想( 即 循环码) c ，存在唯一的幂等多项式p ( x ) 使得c = ( e ( x ) ) ，则p ( x ) 称为c 的生成 幂等多项式。 定义3 2 对于任意码字口= ( ，口l ，a 州) 、b = ( ，轨，k 一。) 町，我们称 1 2 t - - l n b = q 包为口和b 的e u c l i d e a n 内积；对于任意长为玎的码c ，称码 l f f i o c 上= 口j 口b = 0 ，v b m c ：- - 是 i 2 q c 的对偶码。 同样，从文献 1 2 中得知：若码c 是哆上参数为【刀，七】的线性码，则c 上是参 数为【疗，z k 】的线性码：关于循环码的