（基础数学专业论文）两类线性分块纠错码的构造.pdf

摘要 2 0 0 6 年冯克勤教授等人在文献【1 2 】中提出了线性分块纠错码的概念线性分块纠错码可 用于实验设计、高维数值积分及密码学利用线性分块纠错码可以生成混合水甲正交设计【2 】， 进而可用于实验设计经典纠错码生成的正交阵，每个因子都是相同水甲的，而线性分块纠 错码能构造出更一般性的正交矩阵 本文构造了两类线性分块纠错码首先利用有限域f 口上分圆多项式的分解特性，我们 构造了如下线性分块纠错码c m 。 ，这类线性分块纠错码可以作为文献【1 3 】中经典线性码的推 广 定理3 1 1 如果s 为素数，a 为素数且a 8 ，或a = 1 ，0 t q ，1 m q 1 1 ，则晶 上的类型为”= 1 1 的线性分块纠错码。 具有参数b ，女，d l ，满足 n 曲“t = ( m + ：一) ， 伽譬群铲一孚m i 巾( m - 1 ) ，咄 这里r = e d l 口 。一1 ，d f q 一1t d 其次利用有限域日扩域中的元素及品上的对称多项式，我们构造了如下线性分块纠错 码g ( s ，a ，r ，m ，f ) ，这类线性分块纠错码可以作为文献【1 7 l 中经典线性码的推广 定理3 2 1 如果822 ，a 1 ，0 t q ，2 m q 1 ，l = ( f l ，1 2 ，一1 ) z 5 1 满足 0 k 一1 i s - 2 “蔓m 一1 ，且 1b 一1 ( s ) 2r ( ( m 一1 ) 口1 扣“+ l i q l 扣。一t ) ， i = 1 则马上的类型为”= 7 i t 的线性分块纠错码g ( s ，a ，t r m ，1 ) 具有参数融，k ，d l ，满足 n = a r + t , m = ( ”+ ；一2 ) 十a 。，m ，d ， 0 1 d r 一( 一1 ) 口砌_ 1 + l l q m 。一t ) ， 。 i = 1 关键词，有限域，对称多项式，线性分块纠错码，分圆多项式 a b s t r a c t t h ec o n c e p to fl i n e a re r r o r - b l o c kc o d e sw a sg i v e nb yp r o f e s s o rk c q i nf c n ga r i ds oo ni n2 0 0 6 i nf 1 2 1 l i n e a re r r o r - b l o c kc o d e sc a nb ea p p l i e dt oe x p e r i m e n t a ld e s i g n ，h i g h d i m e n s i o n a ln u m e r i c a l i n t e g r a t i o n ，a n de r y t o g r a p h y l i n e a re r r o r - b l o c kc o d e sc a ng e n e r a t em i x e d * l e v e lo r t h o g o n a la r r a y s f 2 】w h i c ha r eu s e df o re x p e r i m e n t a ld e s i g n c l a s s i c a le r r o r - c o r r e c t i n gc o d e s e a ng e n e r a t eo r t h o g o n a l a r r a y sw i t ht h es a m en u m b e ro fl e v e l sp e rf a c t o r ，w h i l el i n e a re r r o r - b l o c kc o d e sg e n e r a t em o r eg e n e r a l o r t h o g o n a la r r a y s t h e r ea r et w ok i n d so fl i n e a re r r o r - b l o c kc o d e sa r ec o n s t r u c t e di nt h i sa r t i c l e f i r s t b a s e do i l t h ef a c t o r i z a t i o np r o p e r t i e so fc y c l o t o m i cp o l y n o m i a l so v e rf i n i t ef i e l df q ，w ec o n s t r u c tt h ef o l l o w i n g l i n e a re r r o r b l o c kc o d e s w h i c ha r et h eg e n e r a l i z a t i o no ft h ec l a s s i c a ll i n e a rc o d e si n 【1 3 t h e o r e m3 1 1 i fs i sa p r i m e ，a i sa p r i m ea n da s ，o ra = 1 ，0 t q ，1 ms 口1 1 ， t h e nt h el i n e a re r r o r - b l o c kc o d e o v e rf qh a v ep a r a m e t e r s 协，k ，d 】w i t ht y p e r = 4 1 【1 l ，w h e r e n = h “* = ( m + ；_ 1 ) ， 嗡甓拦铲一孚酬s ( m 叫i t ) w h e r e r = d 一一l ，如一1t d s e c o n d ，u s i n ge l e m e n t sf r o me x t e n s i o n so ff i n i t ef i e l d 最a n ds y m m e t r i cp 0 1 3 ，n o m i a l so v e r 蜀， w ec o n s t r u c tt h ef o l l o w i n gl i n e a re r r o r - b l o c kc o d e sc ；( s ，a ，t ，r ，m ，f ) w h i c ha r et h eg e n e r a l i z a t i o no f t h ec l a s s i c a ll i n e a rc o d e si n 【1 7 t h e o r e m3 2 1i fs 2 ，a2l ，0 ts 口，2 m q 1 ，z = ( 1 l ，1 2 ，- ，2 。一1 ) z 8 1w i t h 0 一1s i s - 2 1 1 m 一1 ，a n d ( s ) r j ( ( m 一1 ) q ( 一1 ) + ：厶口 8 一一1 ) 一t ) ，t h e n t h el i n e a re r r o r - b l o c kc o d ec ；( s ，a ，t ，r m ，f ) o v e r 晶h a v ep a r a m e t e r sn ，d 1w i t ht y p e = 陋r 1 1 ， w h e r e n = a r + t , m = ( m + ；q ) 刈s ，m ，吼 d r 一；( ( m 一1 ) g 椰- 1 + l i q 州”。1 一t ) k e yw o r d s ：f i n i t ef i e l d ，s y m m e t r i cp o l y n o m i a l ，l i n e a re r r o r - b l o c kc o d e ，c y c l o t o m i cp o l y n o m i a l 一，学位论文独创性声明 东南大学学位论文 独创性声明及使用授权的说明 本人声明所呈交的学位论文是我个人在导师指导下进行的研究工作及取得的研究成果 尽我所知，除了文中特别加以标明和致谢的地方外，论文中不包含其他人已经发表或撰写过 的研究成果，也不包含为获得东南大学或其它教育机构的学位或证书而使用过的材料与我 一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表示了谢意 二，关于学位论文使用授权的说明 签名 苒仁咻巫珥 东南大学，中国科学技术信息研究所，国家图书馆有权保留本人所送交学位论文的复印 件和电子文档，可以采用影印缩印或其他复制手段保存论文本人电子文档的内容和纸质 论文的内容相一致除在保密期内的保密论文外，允许论文被查阅和借阅。可以公布( 包括刊 登) 论文的全部或部分内容论文的公布( 包括刊登) 授权东南大学研究生院办理 签名，址导师签名 靼喻蚪 第一章前言 1 1 问题背景 2 0 世纪5 0 年代以来，数字计算机和数字通信得到了极大发展在今天，人们从每个层 面上都能感受到计算机和通信的这种进步所产生的广泛而深刻的影响除了技术进步之外， 这种发展也得益于新的数学思想和工具的应用数字脉冲信号的数学描述方式，从连续性数 学( f o u r i e r 变换或l a p l a c e 变换) 扩展到离散数学( 组合学、数论代数) 同时，数字计算 机和数字通信中提出许多重要应用背景的数学问题，也促进离散数学自身的发展半个世纪 以来，由数字通信的可靠性要求建立并且发展了纠错码的数学理论 纠错码的数学理论体现了理论和应用之间相互联系和促进的过程通信的可靠性提出纠 错的要求，建立起明确的数学概念和问题，以反映工程上的需求，而后数学家用各种数学工 具构作性能愈来愈好的纠错码用到的数学工具主要涉及到组合学、初等数论、线性代数、 抽象代数代数几何，代数数论及群表示理论 1 9 4 8 年s h a n n o n 发表的通信的数学理论一文，奠定了通信的数学基础一信息论和通 信的可靠性理论具体的通信方式可以是多种多样的，它们的抽象的模型可以表示成如下基 本的形式， 发方互信道互收方 要发送的原始信息可以有不同形式把原始信息统一编成离散的脉冲电信号发出，假设脉冲 信号有g 个状态，当g 为素数幂时，可以取状态集为g 元有限域蜀，这时可以使用有限域理 论以砖表示日上的k 维向量空间，其中元素是长为k 的向量，可以表示q 个不同的信 息一般地，矿个信息可以用品上长为k 的向量来表示，但是用这种方式通信是不能纠错 的这是因为磅中每个向量都代表某种信息，都是有意义的 为使通信系统有纠错能力，需要将表示信息的向量长度加大，将矿个信息用比k 长的 向量来表示，对信息进行纠错编码取n k ，q 个信息用曰中的一部分向量( q o 个) 来表 示，而其余q “一q 个向量是没有意义的将通信系统加上纠错功能之后，其抽象的模型可表 示成t 发方三纠错编码三信道三纠错译码三收方互 发方将信息砖编成有纠错能力的码字c 曰，传给收方的过程中信道出现错误s 曰， 从而收方收到口= c + e 收方进行纠错，恢复成正确的码字c ，然后得到信息o 构作性能良好的纠错码就是要求效率k n 和反映纠错能力的d 愈大愈好这三个参数 是相互制约的它们的关系可以表示成一些不等式，给出参数的一些界，如h a m m i n g 界、 s i n g l e t o n 界和g v 渐近界接近或达到界的码便是理想的纠错码 1 东南大学硕士学位论文 线性码是一类重要的纠错码，这不仅是因为利用线性代数工具，能使纠错编码、纠错译 码和决定最小距离都比较方便，而且大多数纠错性能良好的纠错码都是线性码下面是几类 重要的线性码；h a m m i n g 码g o l a y 码、多项式码和r e e d m u l l e r 码前两种码是完全线性 码，多项式码是m d s 码 1 9 4 9 年g o r y 发现了两个完全线性码：二元线性码g 2 3 和三元线性码g 1 1 1 9 5 2 年，g i l b e r t 和v a r s h a m o v 独立地给出了纠错码的一个充分条件，并得到g v 渐近 界 1 9 7 3 年由t i e t t i v i i n e n - v a nl i n t 证明了：每个非平凡的q 元完全码( 线性或非线性，口为 素数幂) ，其参数n k ，d 必与h a m m i n g 码或g o l a y 码的参数一致 1 9 7 5 年d e l s a r t e 和g o e l h a l s 证明了：具有参数【2 3 ，1 2 ，7 】的二元线性码和参数【1 1 ，6 ，韪的 三元码( 线性或非线性) 必分别等价于g o l a y 码g 2 3 和g 1 1 此外还有一类重要的纠错码循环码r cb o s e 和d k r a y - c h a u d h u r i 于1 9 6 0 年以及 a h o c q u e n g h e l l 于1 9 5 9 年相互独立地得到了一类重要的循环码，b c h 码因为可以设计出 任意大的最小距离，并且有好的译码算法，b c h 码在工程中得到实际应用，但在理论上，它 并不是好的纠错码 2 0 世纪7 0 年代，翦苏联数学家g o p p a 提出一种构作线性码的新方法。是b c h 码的一 种推广，其性能已渐近达到g v 界不久他又以新的视野作了更大的推广，提出了代数几何 码的概念1 9 8 2 年，t s f a s m a n ，m a 等三位数学家构作出的代数几何码更突破了g - v 界， 这是编码理论的重大进展 前面所说的纠错码我们称为经典纠错码线性分块纠错码是经典纠错码的自然推广。可 用于实验设计、商维数值积分及密码学2 0 0 6 年冯克勤教授等人在文献【1 2 】中给出了线性分 块纠错码的定义，得到了线性分块纠错码的h a m m i n g 界和s i n g l e t o n 界，并给出了线性分块 纠错码的对偶码和权多项式，将经典纠错码的一些结论推广到了线性分块纠错码，而且将代 数几何码推广到了分块的情形在实际应用中，当码字长度n 很大，且发生的错误集中在某 几部分上时，我们就可以对码字划分，分块进行检错和纠错，这样就可以提高检错和纠错的 能力 半个世纪以来，人们构造出了许多性能良好的经典纠错码。由于线性分块纠错码是近两 年才提出来的，所以相关的研究还比较少构造性能良好的线性分块纠错码是编码理论的重 要课题在文献f 2 0 】中s a nl i n g 和f e r r u ho z b u d a k 得到了线性分块纠错码的参数的一些新的 界，给出了最优线性分块纠错码的定义，并且得到g i l b e r t - v a r s h a m o v 型的构造及尼上类型为 f = 胁1 1 1 1 2 的最优线性分块纠错码 2 东南大学硕士学位论文 1 2 本文的主要工作 经典纠错码的许多结论可以推广到线性分块纠错码一个自然的想法足将构造经典纠错 码的思想和方法用于构造线性分块纠错码如文献f 4 】中将有限域上的r e e d s o l o m o n 码推 广到f 口的扩域上，文献1 13 】中利用有限域f 口上分圆多项式的分解特性，及文献1 1 7 】中利用 有限域上的对称多项式，构造出性能很好的经典线性纠错码本文就是将这些方法用于构造 线性分块纠错码，并且举例给出一些参数比较好的码 在第二章中，我们介绍了经典纠错码和线性分块纠错码的有关概念和结论以及参数的几 个基本的界，给出经典纠错码与线性分块纠错码参数之间的联系和区别 在第三章中，首先我们利用有限域日上分圆多项式的分解特性，将文献【13 】中构造码 的方法用于构造线性分块纠错码，得到了一类线性分块纠错码其次我们将文献f 1 7 l 中构造 经典纠错码的方法用于构造线性分块纠错码，具体的是用有限域r 上的对称多项式及有限 域r 的扩域中的元素，构造出类型为”= 陋1 7 【l i 的线性分块纠错码，得到码长、信息位数以 及最小距离的下界根据这种构造方法，我们列举了一些的码，得到一些参数较好的码 3 第二章预备知识 本文中，r 是一个有限域，其中q 是素数幂下面我们来回顾一下纠错码的一些概念 和基本性质 2 1 纠错码 这里的纠错码指的是经典纠错码下面我们来回顾一下文献【o l 或【1 0 1 中纠错码的基本 概念和纠错码的界 定义2 , 1 1 j ? 表示有限域岛上的n 维向量空间曰的每个非空子集合c 都叫作一 个口元码，n 叫该码的码长，c 中向量叫作码字 一 用k 表示c 中码字个数，即k = f g i ，则1 k q ” k = l o g q k 叫作码c 的信息位数 ；叫作码c 的效率 当c 为曰的个晶上的线性子空间时，c 叫作q 元线性码此时信息位数k = d i m f 。c 定义2 1 2 设n = ( d l ，口 1 ) 和b = ( b l ，h ) 是日中两个向量。则向量8 的h a m m i n g 权定义为 w h ( a ) = | i l i i n ，啦o ) 而向量n 和b 之间的h a m m i n g 距离是指它们相异位的个数，表示成d t q ( a ，b ) ，即 d n ( a ，b ) = l i l ls i n ，啦嘞) = w n ( a 一 将它们分别简记为”( n ) 和d ( a ，6 ) 定义2 1 3 设c 是码长为n 的g 元码，k = 眵1 22 ，定义c 的最小距离为不同码字之 间h a m m i n g 距离的最小值，表示成d ( c ) ，即 d = d ( c ) = m i n d ( c ，c ，) i c ，c ，g c c ，) 当c 为线性码时，有 d = d ( c ) = m m ( c ) i o c c ) 对每个固定的有限域日，口元纠错码c ( 叼) 有三个基本参数 码长， 码字个数k ( 或信息位数k = l o g 。k ) ，0 k 曼n ， 最，j 、距离d = d ( g ) ，1 d s 4 东南大学硕士学位论文 我们把这个纠错码表示成【n k d l 。或( n k ，d ) q ，也可以称之为q 元码h k ，d l 或q 元码 ( n ，k d ) 定义2 1 4 设c 是参数为【n ，k 】的q 元线性码，即c 是叼的一个k 维线性子空 间。则称 c 1 = “f ? l 对v c e ( “，c ) = 0 ) 为线性码c 的对偶码这里( “，c ) 是指露中向量u 与c 的内积 t ，1 ) ，c = ( c 1 ，c 2 ，c n ) 曰) 易知c 上是参数为h n k 】的口元线性码 对于实数n ，以表示不超过n 的最大整数，q 作。的整数部分 下面的结果虽然简单，但却足整个纠错码理论的基础给出了最小距离具有的检错和纠 错的意义 命题2 1 1 ( 定理1 2 4 ，【10 】) 如果纠错码c 的最小距离为d ，则c 可以检查d 一1 位错， 也可以纠正【勺位错 证明见文献【10 1 下面我们来回顾一下纠错码的界 1 h a m m i n g 界： 如果存在纠错码( ，l ，k ，d ) 。，则 1 4 a 矿k 抽 这里( ：) 是组合数 c ) g ) = 坚# 菩掣 2 、s i n g l e t o n 界t 如果存在q 元纠错码( n ，k ，d ) ，1 d n 一1 ，则 k q n _ “1 即 n 2k + d 一1 定义2 1 5 如果日上的一个h ，t ，d 】纠错码c 达到h a m m i n g 界，则称c 为完全码如 果c 达到s i n g l e t o n 界，则称c 为最大距离可分( m d s ) 码 下面是纠错码的一个充分条件： 东南大学硕士学位论文 设1 d n ，2 k q “，q 为素数幂，如果 d 一1 ( 一】) ( ( 口一1 ) ( ? ) ) q ”， l = o 则必存在参数为( n ，k ，d ) 的q 元纠错码 由上述充分条件可以得到下面的g - v 渐近界 3 、g v 渐近界 对每个固定的素数幂g 和0 6 n b l + + 脚一l + 1 = = n a i + + 脚= m r 这里s = o l + 0 2 + + 却则此划分也可记为 w = 【r o l l “咖，p 令k = 叼。( 1 i ss ) ，v = h o o 毋k = 叼则v 中每个向量可唯一的写成 = ( 口1 ，u 2 ，) ，q k ( is i s ) 定义2 2 2 设u = ( u 1 ，) 和 = ( v l ，) 是y 中两个向量，则向量的”重量 ( t ) 为 t l 畸( ) = h i 1 1 s ，啦0 k ) 而向量u 和”之间的丌一距离( f 丌( “，v ) 为 d ；( u ，口) = l 【 i 1 1 i 8 ，蛳q ) = t 一口) 定义2 2 3 如果c 是y 的日- 线性子空间，码长t l 的划分为且m = d i m f q c ，则称c 是类型为”的h ，k ，胡。线性分块纠错码这里d = d ( c ) 是c 的最小”距离，其定义为 d = m i n d 。( c ，c ，) i c ，c ，g c 一 = l n i n 蜥( c ) i o c g ) 注2 2 1 由定义可以看出经典线性纠错码与相应的线性分块纠错码相比，码长和信息位 数都没有变，但最小距离有所不同当7 r = 【1 】n 时，线性分块纠错码就是经典线性纠错码对 于线性分块纠错码，与经典纠错码一样，构造出效率；和最小距离d 愈大的码愈好这是编 码理论中的重要问题 线性分块纠错码在实验设计、高维数值积分及密码学中有着重要作用利用线性分块纠 错码可以生成混合水平正交设计【2 】，进而可用于实验设计设c 是类型为”的hk ，乩线性 分块纠错码，m 是r 上的q ”k n 矩阵，它的矿“行是对偶码g 1 的码字将m 写成分 块矩阵【尬 幻 纠，每块畅是有m i 弛个元素的q n “n j 矩阵用矩阵m 可以构造矩阵 a = ( ) p 一 。其中a i j = m i j l q n ，- 1 + + m q ，n j 矩阵a 就是一个有s 因子的强度为d 一1 的 7 奎童奎兰堡圭兰堡垒塞 8 正交阵，并且每个因子j 是q 水甲的经典纠错码生成的正交阵，每个因子都, s $ i - 1 水甲 的。而线性分块纠错码能构造出更一般性的正交阵 对于线性分块纠错码，我们也有相应的h a m m i n g 界和s i n g l e t o n 界 1 h a m m i n g 界 设c 是疋上的一个h ，k ，d 1 线性分块纠错码，其类型为7 f = n i l n 2 1 t h 1 ，n l n 2 n f 则有h a m m i n g 界 q ”。k ( f ) ，d = 2 1 + 1 ， q “一薛( j ) ，d = 2 1 22 ， 其中 k ( ! ) = 1 + ( p - 一1 ) ( 矿- 一1 ) ， a = il 型l i x a l l 碍( f ) = q n ，1 1 + ( 矿1 ) ( 扩- 一1 ) 】 a = 1 2 i a ( i x 8 2 、s i n g l e t o n 界 设c 是日上的一个【 - 1 ，k ，d 】线性分块纠错码，其类型为 r = i m l n 2 】b s 】，n l n 2 n ，则有 竹一七2 竹1 + n 2 + + n d 一1 ( 甘k n d + n d + l + ，+ t l s ) 类似地，有如下定义 定义2 2 4 如果蜀上的一个p ；，田线性分块纠错码c 达到h a m m i n g 界，则称c 为完 全码如果c 达到s i n g l e t o n 界，则称g 为最大距离可分( m d s ) 码 类似的，在构造线性分块纠错码时，如果参数能够接近或达到上述两个界就是好的码 第三章构造线性分块纠错码 3 1 分圆多项式与线性分块纠错码 在本节中，我们利用分圆多项式的分解特性，将文献【1 3 1 中构造经典线性码的方法用于 构造线性分块纠错码 首先利用局上分圆多项式的分解特性给出，日= o l d n 譬品) 中元素的表 示方法 设s 1 ，a 1 ，q 为素数幂，日- 假定q 蛔一1 的全部相异正因子为： 1 = d 1 d 2 d = q 如一1 对每个酬扩一1 ，令蛳( z ) 为岛上d 次分圆多项式，即 d l p d ( x ) = l i 扫一) ， 这里n 是昂上d 次本原单位根，则由文献f 1 6 j ，我们有 引理3 1 1 ( 1 6 t ) ( 1 ) 妒d ( z ) 是日中次数为妒( d ) 的首1 多项式，这里妒为e u l e r 函数 ( 2 ) q o d ( x ) 在f q m 中可分解成t d = 罨兽个首1 的次数为m d 的不可约多项式的乘积，这 里m d 是使得g mil ( m o dd ) 成立的最小正整数 ( 3 ) 护“一1 = 兀d l q 。一1 伽( ) 对每个( 引g 知一1 ，记u p ( z ) ：u i x ) ，u 缨( z ) 为分圆多项式仇( z ) 的全部首1 不可约因 式，则d e g u d ) ( z ) = r o d ( 1 i s t d ) 我们记“垆( z ) 在局的扩域中的全部根为 n ，a ! 咖，田口1 ) ( 1 i t d ) ，则( z ) 在r 的扩域中的全部根的集合为 “ a d = u 妒，n ”，0 咖“) 由于d i 扩一1 故a d 野s ，并且t a d l = l p ( d ) ，用毛表示蜘( z ) 在岛的扩域中的全部根的代 表元集，即a d = o p ，a 妒，o 缨) ，则i 五d i = t d ，从而 一= 岛t 9 ( f 口 局) = 局t _ i ( u d l 口 l 一1 ，嘶口一l a d ) 对于给定的正整数s ，m ，a ，1 m q 1 ，记b = i l i 2 如i o i l ，1 2 ，蟊m 1 ) ，对任意 的，= n 2 如b ，令p ) 表示排列i l i a i 。中含元素k ( o k r n 一1 ) 的个数，在集合b 中定义如下关系： 对v i l i i i 8 , j l j 2 如b ，i l l 2 i 。j l j e 厶 辛，( ) = ，( 2 ) ( 0 南i n 一1 ) ，易得为 集合口中的等价关系 9 东南大学硕士学位论文 记a 。为排列i t i 2 z 。所在的等价类，则a 1 1 i ，。= 扎 2 ，i ，的排列) 则由文献 【1 3 】可知； 引理3 1 2 ( 引理2 ，【1 3 】) ( 1 ) 集合b 中不同等价类的个数为；i b 一i = ( ”。) ，这里 ( ”0 。) 为组合数 ( 2 ) 集合a i - 协“中不同排列个数为； i a i t 珏t - i2 霞! j 丽 对每个a i ，i ：，i 。b 一，不妨设i l 墨i 2 ! i 。，令 则有下列结论成立。 引理3 1 3 ( 1 ) 白，如“( z ) 晶，并且 d e g e i l i 2 l l ( 班等( m 1 ) ( 2 ) 对每个o t j _ ，均有e l 。 2 吨( a ) 局 ； ( 3 ) 如1 b i 。( z ) = e j l j 2 j o ( x ) 车= 争i i 2 i s 血如。矗 证明：( 1 ) 显然e 。幻“( z ) f q x l ，并且 d e g e i l 如；( z ) = t 1 幻“m a x ，1 。2 。 口1 ( 。一1 ) 。l + g x ( s - 2 ) t 2 + _ + k ) ( m 一1 ) ( 口 ( 。一1 + g 扣一2 ) - 4 - - + 矿+ 1 ) = 籍”1 ) ( 2 ) 对每个a 兄岫 ( i i 2 - i s ( n ) ) 一= ( 一“4 州”2 睇。+ “) 矿 “rr r t s e a i l 屯“ = 1 rd q l 。n + 口1 一1 t 2 + + 一b l 幻t - e a , 1 2 i ， = r 口矿- 1 如埘忙2 t a + + q l t - + t l t l t a t s e a = l 红b = e i 】如4 ，( 故e 1 2 i 。( q ) 昂 ( 3 ) 如果i t i 2 i 。一j l 五矗，则a 1 b 也= 勘1 力1 。，从而e i ，i 2 ，( z ) = e j ，血儡( z ) 另一方面，若e l 如，i s ( z ) = e j ，血嘻( z ) ，则 - 、z 口1 扣一1 t l + q 州。一2 k + 斗“= - _ $ 口m 。一”t ；+ 口m 。一砷呸+ 一+ t l t 2t s e a i l 也“ ；t 嵋e a n j r 如 1 0 +一+ 一 一 z 烈 圯 = zb 东南大学硕士学位论文 于是对v t l t 2 t 。a ，i ，存在j 分- r t ：a 。 使得 z 口1 一1 t l + q 1 5 2 t 2 + i = z q l “一1 t l + q 1 8 2 f ：+ + t ： 故 q x ( 。一1 i + 譬州s - 2 ) t 2 + 十t s = q x ( 5 1 ；+ 哿1 ( s - 2 ：+ + t ： 于是t 。i t ，( m o d 矿) ，又0 t 。，t ：m 一1s 矿一1 ，故t 。= t ：，从而 叮 ( s - 1 ) t l + g ( 8 - 2 ) t 2 + + q x t 卜1 = 口1 ( 卜1 巧+ g ( 6 - 2 t ；+ + g ：一1 于是“一1it p ( r o o d 矿) ，又0st s - i ，t ：一1 m 一1 矿一1 ，故t 8 - 1 = t ：- l 如此继续下去可得 t k = t k ( 11 t ss ) ，从而a i m i = a j 。j 2 矗，故i l i 2 i 。一j l 血 ( 证毕) 引理3 1 4 集合 e i 。虹“。( x ) l a i 。b 。b 一) 是日一线性无关的 证明；我们先证明：如果i 1 赴b 与j 1 五九不等价，则d e g e i 衙矗( z ) d e g e j ，j 2 矗( z ) 假设d e g e i ， 矿- 1 ( z ) = d e g e j l 矗( 茁) ，则存在t l t 2 t 一4 h 如i 。，t j 呸a j i 血j o ，使得 g 扣一1 1 + 口1 扣一2 t 2 + + t 5 = 口1 ( 8 1 t i + 口 扣一2 巧+ + t ： 于是t 。e ( m 耐口1 ) ，又0 “，m 一1 矿一1 ，故“= ，如此继续下去，由0 t k ， m 一1 q 1 1 可得t k = 圪( 1s 女s ) ，从而i l i 2 i ，一j 1 血矗矛盾! 由于 e 。i4 。( z ) i a 。小也b 一) 中多项式的次数两两不同，故它们是晶一线性无关的 ( 证毕) 对于给定的正整数s ，a ，m ( 1 m 矿) ，令 = s m n e l i 赴i 。( z ) l a ， ”。b 一) 则。 是r 【z 1 的吁线性子空间，并且d i m = i b 一i = ( m ? - 1 ) 令日= a l ，毗，口口) 对于a = a 1 ，砚，啦) 日，五d ； d p ，矽，n 缨) - 局， ，令，( a ) = ( ，( n 1 ) ，( 毗) ， ，( n t ) 日( 1 曼) ，( 田) 日- ( 1s i t d ) 的基，贝6 对每个1 s f 女，( 越田) 可表示成 令 记 ，( a t ) ) ，i ( a d ) = ( ，( a p ) ，( ) ，( a 铲) ) ，则 令 u 1 ，u 2 ，u ) 为在马上的一组固定 ，( 舻) = 卵u 1 + 谬屹+ + 鲫峨，谬晶( 1 j sa ) 9 ( a 垆) = ( 卵，舒，簖) 曰 9 ( 盈) = ( 鳢船，搿，舒，搿，磺，粥，卢t d 2 ，卢t d j 、l 东南大学硕士学位论文 则 c m , s ， = “o 卅矿一1 ，m 1 9 ( 山) ) ef ( a ) l f ，s ) 是上类型为7 r = 的线性分块纠错码，其码长n = 灯+ t ，这里r = d 护- l 曲。一l t d 定理3 1 1 如果s 为素数，a 为素数且 8 ，或a = 1 ，0 t q ，1sm q 1 1 ，则 ，是日上类型为”= 7 的h k ，d 】线性分块纠错码，其中参数满足： n = a r + t ，詹= ( ”+ ：一1 ) ， 协旺群铲一孚m i n s ( m - 1 ) ，) 这里r = d l q x , - l ，加一l 红 证明；由码。 的构造可知，l = 灯+ t 定义映射妒为 1 2 + j ； ，一( o 日q 一1 ，嘶口一l g ( a d ) ) ey ( a ) 任取，k e r 0 ，由于9 ( 而) = o ( a 维零向量) = = ，( 由) = 0 ，故对v q a u ( u 舶- 。- 1 加一l 五) ，( n ) = 0 ，从而对讹a u ( u a l q - j - 1 加一1 a a ) ，( o ) = 0 ，于是对届 o 件1 ，) ，( o ) = 0 由 此可知，( z ) 在e - 。中根的个数至少为q “一( q t ) = q “一q + t ，又由y ( x ) ， ，故 d e g l ( = ) 譬舻，而当m 茎矿一1 时， ( 一1 ) ( 籍扎2 ) ( 籍阳“一阳n q + t 于是f ( x ) = 0 ，故妒为单射，从而k = d i m c , n = d i m = ( ”? - 1 ) 下面考虑最小距离d 对v l ( x ) ，( z ) 0 ，令e l = ( o q 矿，一1 ，舶一1 9 ( a d ) ) o ，( a ) ，如果耐( 。，) = d ，则， 在a u ( u a h x 一- 1 ，舳一1 a d ) 中零点个数为r + t d ，记n 为，在a = a 1 ，眈，a t ) 中零点个 数，r d 为，在屯= a p ，a 妒，o 缨 中零点个数，则，在山中零点个数为m d r d ，而 巧u 是包含a d 的最小域，故，在山中零点个数不超过，在局m a 中零点个数，并且如果 d ，但m = m d ，则，在a 一u a d 中零点个数同样不超过，在巧w 中零点个数对每个 硎q 如一1 ，m a l a s ，故，在妒j - l , 舶一l a a 中零点个数不超过，在- ，f 口中零点个数 对每个d l q 如一1 ，m d l a s ，而s 为素数，a 为素数且 s ，或a = 1 ，故m d = 1 或m d s ，并 且当圳口如一1 ，但d tq 一1 时，m d s ，而，在u d l 口，u ，m 一1 山中零点个数不超过，在- - 日 中零点个数，于是 ( 5r d ) _ d e g y ( 圹呸( 碧) ( m _ 1 ) 1 ， = 查里奎量堡圭兰堡垒壅 1 3 从而 。点附s鸣竽产了rl，11 d 妒一曲q 一 11 ， 。 故 叶啪。蛐州r d 锵+ 半， 由于，在b = 。j ，啦，嘶) 中零点个数不超过s ( m 一1 ) ，故n m i n 。( m 1 ) ，t ) ，于是 ”舶。毫一，锵+ 掣啦( 一 ， f 而 d = r + t 一( r l + ) d i q l 1 , d t q1 一甓群铲一掣酬如叫，。， ( 证毕) 注3 1 1 ：当a = 1 时，7 r = 【1 l ” 1 = s p a n _ 1 n + 矿1 2 蚺忆j o 如s i 2 s 蟊s m 一1 t l t 2 t 1 此时。1 实际上为q 元经典线性码 我们有如下结论； 推论3 1 1 ( 定理1 ，【13 】) 当0s ts 口，lsm s q 一1 ，s 为素数时，。1 是岛上的f n ，国 线性码，其中参数满足： n ：r “：p 怕- 1 1 ， 5 锄一器产一孚叫咖_ 1 ) ，吐 这里r = q 矿一1 ，柳一1 t d 注3 , 1 2 ：当a = 1 ，s = 1 时，1 ，i = s p a n x 1 i o i m 1 ) ，如果m ，则1 1 即 为文献【8 】中的r e e d - s o l o m o n 码 当a = 1 ，s = 2 时。 ，2 ，1 = 印。咒 e 巧( z ) i o i j m 一1 ) = s p 。n x q t l + k i o i j m 一1 ) t , t 2 e a , j 东南大学硕士学位论文 则( 竹一2 1 即为文献1 4 】中的经典线性码此时2 1 的参数旧k d 】满足： n = t + a r = t + 幻= t + ；1 矿( d ) d l q 2 1d c q - ld l q 2 1d f q 一1 = t + ；( 妒( d ) 一妒( d ) ) d l q 2 1d q 一1 = t 十；( a 2 - 口) ， t = ( ”+ ；一1 ) = ( ”+ ；一1 ) = ( “1 ) = ；m c m + ， 协一譬拦q 铲1 一孚m i n 咖哪)s l4 一i s = n 一生群一j l m i n 2 ( m 一1 ) ，) = n 一；( ( 口+ 1 ) ( m 一1 ) + m i n 2 ( m 一1 ) ，) ) 与文献【4 】中的结论相一致 3 2 对称多项式与线性分块纠错码 这一节我们使用有限域凡的扩域中的元素及局上的对称多项式，将文献1 17 】中构造经 典线性码的方法用来构造类型为”= 7 1 1 线性分块纠错码 设q 是素数幂，a ：s 是两个正整数，考虑日【x ，y 】中的多项式 + ( 一1 ) 。一1 d j 一1 y + ( 一1 ) 。o * s ( 3 2 1 ) 对于所有的1 i 5 ，o i 是f 口i x 】中的多项式实际上，o i g 关：- 3 = x ，x q a , x q “，x q “- 1 ” 的第i 个初等对称多项式 引理3 2 1 对任意的d 岛x 及1 i s ，我们有a i ( a ) f 口- 证明；由( 3 2 1 ) 可知 根据有限域的有关理论可得 从而有 以( n ) = o i ( a q l ) = = t t ( c f q x ( s - 1 ) ) a i ( a )