（应用数学专业论文）一类特殊码的有效错误控制.pdf

一类特殊码的有效错误控制 摘要 内容摘要：自1 9 9 3 年t u r b o 码出现以来，信道编码技术进入了一个崭新的时代。自那 时起信道编码技术就引起了通信与编码界广泛的关注与研究，其相关理论在实际中也得 到了广泛的应用。本文的贡献在于给出了一种与信道编码紧密相连的信道错误容量以及 发生一定数目错误时的纠错改正方法。 本文首先给出了模的定义，这样可以把一个多项式通过一组模编成一个剩余向量。 反之利用中国剩余定理得到解空间c ，即由c 中向量能够解出它所对应的多项式；并进 一步在c 中介绍了重数的概念，讨论了它与h a m m i n g 距离之间的关系；简述了利用这种 模的定义进行编码和译码的过程，从而找到一种新的编码算法。 其次我们讨论了在信息传输的过程中如果有错误产生，那么我们能控制，检测并改 正错误的数目的限制，并介绍了具体的检测和改正的方法。 最后本文给出了一种更为有效的错误改正方法。并给出了一类特殊的码，对这类码 中最重要的几种情况进行研究和讨论，利用所给出的新的改正方法来解决具体问题，从 而得到这种新的方法与原来的改正方法所比较的优势在于它可以改正比原来更多的错 误。 关键词：模，剩余向量，h a m m i n g 距离，重数，错误检测，错误改正，特殊码。 一类特殊码的有效错误控制 a b s t r a c t c o n t e n t ：s i n c e1 9 9 3 ，t u r b oy a r d sc h a n n e le n c o d i n gt e c h n o l o g yh a se n t e r e dan e we r a s i n c et h e n ，c h a n n e l c o d i n gt e c h n o l o g y h a sb e e n p a i d m u c hm o r ea t t e n t i o ni nt h e c o m m u n i c a t i o na n dc o d i n gw o r l d i t sr e l a t e dt h e o r yh a d w i d e l ya p p l i c a t i o ni np r a c t i c e t h e m a j o rc o n t r i b u t i o n so ft h i sp a p e rg i v et h en u m b e ro fc e r t a i nc a p a c i t yo fe r r o rc o r r e c t i o n r e t a t e dt oc h a n n e lc o d i n ga n de r r o rc o r r e c t i o nm e t h o d f i r s t l y ，i ti ss h o w nt h a tap o l y n o m i a lc a nb ee n c o d e dar e s i d u a lv e c t o rt h r o u g hag r o u po f m o d u l i c o n v e r s e l y ，i nt h es o l u t i o ns p a c ec ，ar e s i d u a lv e c t o rc a nb er e c o v e r e dap o l y n o m i a l b yc h i n e s er e m a i n d e rt h e o r e m f u r t h e r m o r e ，t h ec o n c e p to fm u l t i p l i c i t yi si n t r o d u c e d t h e r e l a t i o n s h i pb e t w e e nm u l t i p l i c i t ya n dh a m m i n gd i s t a n c ei sd i s c u s s e d w ea l s oi l l u s t r a t eh o w t oe n c o d ea n dd e c o d eb ym o d u l i an e w c o d i n ga l g o r i t h mi sa l s og i v e n s e c o n d l y ，s u p p o s et h a tt h e r ea r ee r r o r si nt h ep r o c e s so fi n f o r m a t i o nt r a n s m i s s i o n ，w es h o w t h em e t h o do fd e t e c t i o na n dc o r r e c t i o n f o rs e v e r a lc a s e so ft h es p e c i a lc o d e sw eg i v e a t h o r o u g hr e s e a s c ha n dd i s c u s s i o n w ea l s ou s et h en e wc o r r e c t i o nm e t h o dt os o l v es p e c i f i c p r o b l e m s c o m p a r e dw i t ht h eo l dc o r r e c t i o nm e t h o d ，t h en e wm e t h o di sa b l et oc o r r e c tm o r e e n 0 r s f i n a l l y ，t h i sp a p e rg i v e sam o r ee f f e c t i v ee r r o rc o r r e c t i o nm e t h o da n dg i v e sac l a s so f s p e c i a lc o d e s k e y w o r d s ：m o d u l u s ，r e s i d u a lv e c t o r ，h a m m i n gd i s t a n c e ，m u l t i p l i c i t y ，e r r o rd e t e c t i o n ， e r r o rc o r r e c t i o n ，s p e c i a lc o d e 学位论文独创性声明 本人承诺：所呈交的学位论文是本人在导师指导下所取得的研究成果论文中除特别加 以标注和致谢的地方外，不包含其他人和其他机构已经撰写或发表过的研究成果，其 他同志的研究成果对本人的启示和所提供的帮助，均已在论文中做出了明确的声明并 表示谢意 学位论文作者签名盈缉趁 学位论文版权使用授权书 本学位论文作者完全了解辽宁师范大学有关保留、使用学位论文的规定，及学校有权保 留并向国家有关部门或机构送交复印件和磁盘，允许论文被查阅和借阅本人授权辽 宁师范大学，可以将学位论文的全部或部分内容编入有关数据库进行检索，可以采用 影印、缩印或其他复制手段保存、汇编学位论文保密的论文在解密后使用本授权书 学位论文作者签名：三啦指导教师签名：捌 签名日期：年月日 一类特殊码的有效错误控制 一类特殊码的有效错误控制 1 引言 1 9 4 8 年香农( s h a n n o n ) 在他的开创性论文通信中的数学理论 1 中，首次阐明了 在有扰信道中实现可靠通信的方法，提出了著名的有扰信道编码定理，是纠错码的奠基 石。至今接近6 0 年的发展，人们一直在追求达到香农限的好码。随着信息时代的到来 及飞速发展，今天的纠错编码不单是一个理论问题，它已成为现代通信领域不可缺少的 一项标准技术。通信系统要求实现对话音、数据以及图像等大量数据信息量实现高速实 时传输，都离不开高效的纠错编码。 1 9 9 6 年，英国的m a c k a y 教授“再发现 了1 9 6 2 年由美国的g a l l a g e r 2 教授提出 的低密度校验( l d p c ) 码，在高斯信道下，引入因子图的概率和基于置信传播的和积算 法，1 2 码率的二元l d p c 码与香农限只差0 0 0 4 5 d b 。t u r b o 码及l d p c 码的发展，极大 地刺激了信道编码研究工作地兴趣，使人们开始从新的思路与数学工具去寻找和解释接 近香农好码。经过最近1 0 多年的发展，一些新的编译码理论与方法日渐成熟。现代编 码理论是麻省理工学院( m i t ) 的g d a v i df o r n e y j r 教授 3 在2 0 0 4 年首次提出的概 念，试图以概率论与因子图为工具来统一编码理论，提出了现代编码理论的三大特征， 即基于信息传递的和积算法，因子图和信道输出软信息的利用，而将以前基于代数方法 的编译码称之为经典的编码。 尽管计算体系结构采用剩余数系( r n s ) 所做的工作，对于普通计算来进行较困难的 符号识别，测量，对比和区分是没有明显的优点，但是他们对于要求计算大规模的加法， 减法，或乘法的特殊的计算设备是很适合的。特别的，研究的一个重要的部分是关注r n s 在信号处理的各个领域中，包括数字滤波、数位关联与快速傅里叶变换( f f t ) 加工中的 应用。剩余代数系统起源于中国剩余定理( c r t ) ，它的特点包括执行平面上基本的算术 运算，不携带计算，并缺乏在剩余位置的顺序性。后两种性质形成r n s 在控制测量误差， 以及由于传输时产生的噪音或执行算术运算产生的错误应用中的基础。剩余数系所固有 的灵活性被开发为研究误差检测的综合理论 4 、5 、6 和7 。同余的控制错误的必要性 是通过增加额外的剩余位数或模得到的，因此得到了名为同余的剩余数系( r r n s ) 。大量 的在这一领域的工作是关注于r r n s 在剩余位置错误处理器的设计的应用，特别关注于数 字滤波器 8 。关于r r n s 误差控制的重要工作由k r i s h n a ，l i n 4 和s u n h ek r i s h n a 9 完成。上面所涉及到的所有的研究是基于r r n s ，它的模认为是两两互素的。虽然r r n s 提供全面的误差控制理论及许多有用的性质，但是也有缺点。虽然通过基本的扩展误差 检测和改正已基本完成，通常是通过混合的基数转换实现，但是它需要大量的计算。这 是误差控制理论中最大的问题从算术计算及需要独立运作误差检查( 参见 1 0 的一个框 一类特殊码的有效错误控制 图有一个单一的二元运算的一致性检查的过程) 。本文的主要贡献在于给出了一种与信 道编码紧密相连的信道错误容量以及发生一定数目错误时的纠错改正方法。 本论文结构如下：第二部分给出了模的定义，进而得到相对应的剩余向量并由中国 剩余定理得到码空间，并进一步给出此码空间的基本定义和相关结论，从而找到一种新 的编译码的方法；第三部分讨论了在信息传输的过程中发生错误时，能检测识别并改正 错误的数目的容量，并介绍了具体的检测和改正的方法；第四部分，给出了一种更为有 效的错误改正方法，并给出了一类特殊的码，对这类码中最重要的几种情况进行研究和 讨论，利用所给出的新的改正方法来解决具体问题。 本文所用的符号与术语可参考文献 1 1 一 1 5 。 2 预备知识 2 1 剩余数系中的相关定义 定义2 1 ：取定卜 中的6 个多项式 ( x ) ，厶( 工) ，厶( z ) ，把它们称为一组模。 任给多项式i ( x ) - - a 。+ a l x + a 2 x 2 + + 口。一i x ”1 卜 它对应于一个剩余向量 ) ，= ( ( z ) ，r 2 ( 工) ，吃( x ) ) ，这个剩余向量是由下列同余方程组所确定的： ，( x ) - ( x ) ( m o d ( z ) ) ，( 工) _ 厂2 ( z ) ( m o d ，2 ( 石) ) s ( x ) = r b ( x ) ( m o d f b ( 石) ) 其中osd e g r 。( z ) d e g f i ( x ) 。 每个剩余向量 歹：( 吒( z ) ，吃( z ) ，( z ) ) 都对应于善唧 中一个向量 二= ( 吒。，小，2 ，：，。，一。) ，其中吩一d e gf ( x ) ， ( x ) ；。+ 一+ + 一，f ：1 ，2 ，6 ，因此以下我们把剩余向量和它所对应善 中 的向量等同起来。 码c 是善嘶的一个子集，它是由使得同余方程组( 1 ) 有解的那些向量组成的，即 v ：- = ( c l o , c 1 1 ，c 。 。，c ，c ：1 ，c ：妒，c 6 。，1 一c b n 。一，) c 均可由同余方程组 一类特殊码的有效错误控制 c ( z ) = c 。+ c 1 t x + + 气一1 x ”1 ( m o df 。( x ) ) c ( x ) = c 加+ c ：声+ + c ：。：一1 x “2 。1 ( m o d 。疋( x ) ) c ( z ) = c 。+ c 。一+ + c 虮一1 x 一1 ( m o d f b ( x ) ) 解出c ( z ) 来。 反之能由同余方程组解出c ( z ) 的那些向量也都在c 中。 显然c 是向中的一个长为他的线性码。 定义2 2 ：对于c 中任意两个剩余向量y 和y ，y 和y 的h a m m i n g 距离定义为向量) ，和y 中分量不同的数目，记为d ( 歹，罗) ，明显的我们知道d ( 歹，歹) 2w ( 歹一歹) 。 定义2 门：码c 的极小距离定义为d ( c ) = 而n d ( ：，j ) ：x ，i c ，：i ，即不同的向量 间的最小距离。 以下文章中我们用( x ) 来表示模五( x ) ，厂2 ( z ) ，五( x ) 的最小公倍式，把( z ) 唯一 的分解为不同的不可约多项式因子的乘积，记l ( x ) 一吼( 茗) 口：( z ) q v ( x ) ，其中 d e g 吼( 工) s d e g q ：( 工) s s d e g q , , ( x ) 。 定义2 4 ：模五( z ) ，厂2 ( x ) ，无( z ) ，五( z ) 乞卜 的重数，定义为最大的正整数满足最小 公倍式l ( z ) 的每个不可约因子呸( x ) 整除至少，个( x ) ，其中1 s fsv ，1s j s6 。 例 ( x ) = ( 工+ 1 ) 2 ( z 2 + 1 ) ( x 2 + 及+ 2 ) ( x 3 + x 2 + 1 ) ，厂2 ( x ) ；( z 2 + 1 ) ( z 2 + 及+ 2 ) ， f 3 ( x ) - - ( x + 1 ) 2 ( z 2 + 1 ) ( x 3 + 工2 + 1 ) ，厂4 ( z ) = ( 工2 + 1 ) ( x 2 + h + 2 ) ( z 3 + x 2 + 1 ) 解：其中( x + 1 ) 2 整除五( 工) ，厶( 石) ，( z 2 + 1 ) 整除 ( 工) ，2 ( x ) ，厂3 ( x ) ，厂4 ( 石) ，( z 2 + 2 x + 2 ) 一类特殊码的有效错误控制 整除五( x ) ，厂2 ( z ) ，厂4 ( z ) ，( x 3 + z 2 + 1 ) 整除 ( 工) ，厂3 ( z ) ，4 ( x ) ，因此这个模集合的重数为 ，- 一2 。 定理2 1 ：d ( c ) = 厂 证明：由厂的定义知由6 一，+ 1 个模组成的集合包含至少一个模厂j ，( 工) 被( z ) 的某个不 可约因子哂( z ) 整除，其中1s ls y 。因此l ( 戈) iz r 埘 ( z ) ，f i 2 ( x ) ，厶，( z ) ，对于 任意 f 2 。，对任意多项式，( z ) ，0 d e g f ( x ) d e g l ( x ) ，如果厂( z ) 有6 一厂+ 1 个剩余，；( z ) = 0 ，那么它就被最小公倍式的相对应的6 一，+ 1 个模整除，这与前面的观 察矛盾。因此：有至少6 一( 6 一，) 一，个对应的非零分量，所以w ( ；) 芑厂。也就是说对c 中任意的i 和乏，i 乒x 一2 ，d ( i ，乏) = w ( i 一乏) 厂，所以d ( c ) 之，- 因为模五( 石) ，厂2 ( z ) ，兀( z ) ，五( x ) 1 的重数为，那么有( z ) 的某个不可约 因子g 仁) 就是正好整除，个模。设 ( x ) ，丘( z ) ，九( x ) ，其中 屯 一，表示 不被留，( 工) 整除的b 一，个模，如果厂( 石) = z c 朋 ( x ) ，厶( 石) ， ，( z ) 】那么 0 d e gf ( x ) d e g l ( x ) 并且对任意的1 墨zs 6 一，( 石) 一f ( x ) ( m o df i , ( x ) ) = o ，对任 意被q ( x ) 整除的，- 个模i ( z ) = f ( x ) ( m o d 五( x ) ) 0 。因此相容的剩余向量x 对应于 ，( x ) 有重量，。这样d ( c ) s d ( ：，石) 2 w ( z ) 一，其中石是零剩余向量。 2 2 中国剩余定理 定理2 2 ：在多项式集合五( x ) ，厂2 ( x ) ，无( z ) ，六( x ) b 所构成的模中，如果它们是 两两互素的，那么线性同余式( 1 ) 总存在一个解厂( z ) ，并且这个解是唯一满足这个同 余式且osd e gf ( x ) d e g m ( x ) ，其中m ( x ) a 正( x ) 厂2 ( 工) 无( x ) 。 定理2 3 ： 对余式( x ) ，厂2 ( x ) ，( x ) e f q x 的任意集合， 0sd e g r ，( 工) d e g 正( x ) ，i ；1 , 2 ，6 ，线性方程( 1 ) 有解当且仅当 一类特殊码的有效错误控制 g c 彳( 五( z ) ，乃( z ) ) i ( ( 工) 一o ( z ) ) ，i ，j = l 2 9 o*o9 b ( 2 ) 当( 1 ) 有解存在，那么就有一个唯一的解，( 工) 满足o s d e gf ( x ) d e g l ( x ) ，其中l ( x ) 表示模 ( x ) ，厂2 ( x ) ，兀( x ) ，z ( x ) 卜 的最小公倍式，( 2 ) 中的缩写g c 彳表示最大 公因式。 2 3 编码及译码 由2 1 部分的定义我们知道，给出一个信息( 口。，口1 ，一，吼) 譬，它对应一个多项式 ，( z ) - - a 。+ a l x + a ：x 2 + + 吼矿e f 口 x ， 由模的定义，它对应一个剩余向量 t ( ( z ) ，r 2 ( z ) ，r b ( x ) ) ，它等同于向量 ( 。，巾，吃，：书，。，一。) c ，这样我们就把一个长为( 七+ 1 ) 的信息 7 m b 编码为智中的一个长为他的向量。 反之任给c 中的一个向量，由c 的定义我们知道均可解出唯一的多项式i ( x ) ，这样 我们就找到了所传递的信息。 3 错误的控制，检测及识别 3 1 错误控制 定义3 1 ：c 中的向量称为与c 相容，不在c 中的向量称为与c 不相容。 当d ( c ) 苫2 时，改变口c 中任意f 个分量，当“1 s d ( c ) 时，则产生一个不相容的 剩余向量y ，当勿+ 1sd ( c ) 时，h a m m i n g 距离函数指出y 是唯一的最接近a 的向量。这 样我们利用最接近剩余向量的方法来改正发生i ( d ( c ) 一1 个错误的相容的剩余分 lj 量，其中i 1 代表最大的整函数。然而这种方法在理论上很简单，但是在实际计算中却 很少把这个剩余向量与c 中的所有剩余向量比较来译码。 这部分发展了在剩余位置上的错误检测和改正的有效的计算技术。前面部分引用的符 号在这部分继续使用，另外对于一对模五( x ) 和( x ) 的最大公因子记为g ，( x ) 。输出向 一类特殊码的有效错误控制 量歹通过一系列的测量，传输或计算可能在一些剩余位置上与码向量：有所不同。这样 咒( z ) 量( 石) + q ( x ) ( m o d 五( x ) ) ，0sd e g e ；( z ) d e gf 。( z ) ，巴( x ) 是第f 个剩余位的错误多 项式。校验矩阵e 是通过定义第f ，j 位置向量略( z ) 一( 咒( z ) 一y ，( x ) ) m o d g 玎( z ) 所得到的， 这个结论是由d ( z ) - ( e ( z ) 一e ，( x ) ) m o d g 可( 石) 事实得到的。 由于 ( 办( z ) 一y ，( x ) ) m o d 岛( x ) = ( ( z ) 一。( z ) ) + ( 白( z - e i ( z ) ) 】( m 。d g 玎( x ) ) ，但是：是一个 码向量因此相容所以( z ) 一o ( z ) = o ( m o d g 玎( z ) ) 。 回想，表示模集合五( x ) ，厶( x ) ，五( z ) ，五( x ) e e , x 的重数或者等价的由定理2 1 知，是相容的剩余向量的码空间c 的最小的h a m m i n g 距离。下面的引理对于获得这部分 的主要结论起到了重要的作用。 引理3 1 ：设- b 一，+ 1 ，对任意的1sis6 及1s 五 j z l ，丘乒i ， 五( 石) l1 c m g 坑( z ) ，g 牙：( z ) ，g 礼( 石) 】 证明：整除五( 工) 的任意不可约因子g ( z ) ，必整除l ( x ) 中某一个不可约因式吼( z ) ， 1 1 s 1 ，而重数为，因此除了最多b r 个( z ) 外其余都被g ( x ) 整除，这样集合 鼠( x ) ，g f 2 ( x ) 9o 9 9 如( x ) 的任意缈；6 一，+ 1 的最大公因子一定包含至少一个被g ( z ) 整 除的模。 引理3 2 - 设一6 一，+ 1 ，对任意的1s fs 6 及任意整式p ( 工) ，o d e g e ( x ) d e g 五( x ) ，至 少有一个剩余分量e ( x ) ( m o d g f ：，( 工) ) 是非零的，对于任意矗 厶 l ，丘f 证明：如果不是这样即所有剩余分量e ( x ) = o ( m o d g 坑( x ) ) ，那么既( z ) i px ) ，由前面的 引理知道z c 朋 鼠( x ) ，g 2 ( x ) ，g 礼( z ) 】i p ( z ) ，即z ( x ) l p ( x ) ，这是不可能的。 定理3 1 ：如果剩余向量歹与相容向量；在f 个位置上不同，其中o tj 呈t + ls ，那么 与多相关的校验矩阵至少有一个非零分量。 证明：不失一般性的，我们假设两个剩余向量在前b - t 个位置是相同的，在后t 个位置 不同，这并不影响证明，只是为了符号标记的简单些。这样巳( x ) = e ：( x ) = 一吃一，( x ) 一0 ， 一类特殊码的有效错误控制 那么校验矩阵e 的前b - t 个分量在b - t + l 行是以小。，( z ) ；巳小。( x ) ( m o d9 6 。+ l ，( 工) ) ，其 中1sj s6 一t ，因为0 d e g ( e b 小。( z ) ) o ，t + 1s ，那么校验矩阵e 一0 。当 校验矩阵e ；o 时，那么没有发生错误或者由于错误t + l r 而没有检测到错误。 下面一个阶段是来确定发生错误的位置及发生错误的数量。此阶段最关键的是当t o 且办+ 1s ，时，定理3 2 保证了对任意的o i t ，校验矩阵中有大于i 行包含有i + l 或更 多的非零分量。这样我们就找到了寻找t 的方法：从t = l 开始，逐渐的对照指标i 和e 中包含i + 1 个或者更多的非零分量的数目。当t 的值和i 的值相等时，我们就找到了t 的确切值和发生错误的位置。对于任意的t 和r ，上面的过程都可以使用，但是我们很 少对于大于2 个错误的情况进行控制，因此上面的描述过程当执行次数大于2 时我们就 不往下进行了，我们需要的是不多于l ( ，+ 1 1 个错误。 【 二j 3 3 错误改正 如果在相容的剩余向量中有t 个错误发生，其中o 1 ，计算有2 个分量不为零的行的数目，并从，中减去这个数得到a ：。 如果， 2 ，计算有3 个分量不为零的行的数目，并从：中减去这个数得到。 如果， 3 ，假设不满足，发生错误的数目和位置都不能确定。 如果a ，；3 , t 。3 ，那么有4 个或者4 个以上的非零分量的那三行就是发生错误的位 置。 依次计算下去 发生错误的数目和位置一旦被确定，那么错误就可以被改正。为了简化符号，我们 把模重新标号，这样前b - t 个剩余位置是没有发生错误的，后面t 个位置发生错误。下 面的改正错误的过程由校验矩阵的定义及定理2 2 及定理3 1 一并引出。 如果在一个相容的剩余向量中的t 个位置发生错误，其中0 t 且力+ 1 s 厂，在第i 个位置发生错误的q ( x ) 是唯一的次数小于五( x ) 且满足线性同余式 e , ( x ) - d 玎( x ) ( m o d g ( z ) ) ，1s j s6 一t 的解。 备注：为了实施这部分所说的确定错误数目和识别错误剩余位置的过程，不必记住 校验矩阵的每一行，我们所要做的就是确定每一行中的非零分量的总数目。编译一个剩 余向量的前奏就是把错误识别出来，我们不需要去改正被识别出来的任何错误。不等式 ，苫2 t + 1 保证了没有错误发生的对应位置的模的最小公倍式就是l ( x ) 。定理2 3 保证了 被编成相容的剩余向量x 的多项式厂( 石) 可以由没有发生错误的剩余位置唯一地被译出 来。 一类特殊码的有效错误控制 4 特殊码的错误控制 4 1 有效的错误改正 4 1 1 二维重数的引入及相关定理 此部分我们扩展了一种更有效的方法来增强模系统对于错误控制的能力，从应用的 角度，如果用剩余位置来测量物理量，很自然的去限制在基本的实际讨论中发生错误的 大小。回忆前面我们用( z ) 来表示模矗( z ) ，2 ( z ) ，无( 工) ，的最小公倍式，它可以由不 同的不可约因式的乘积来表示，其中d e g q 。( x ) 墨d e g q ：( x ) s sd e g q , , ( 石) 。 定义4 1 1 ：假设模五( x ) 被两个或者多个不同的q ( 工) 整除，内在错误毒( x ) 定义为岛( x ) 与正( 工) 一岛( z ) 次数较小的多项式，它是由口。( z ) 来限定，o jd e g 毒( x ) d e g q 。( x ) 。 定义4 1 2 ：二维重数，2 定义为满足l ( z ) 中每一对不可约因式口j ( x ) 或吼( 工) 整除的 五( x ) 的总数的最大值的最小者。 下面有类似于引理3 2 1 和3 2 2 的引理。 引理4 1 1 ：设- - b - r 2 + 1 ，对任意的1s fs6 及1 s 厶 l ，丘乒f ，那么 1 c m 鼠( x ) ，g 玎：( x ) ，- ，g 如( 工) 】被l ( z ) 中整除五( x ) 的至少一个不可约因式整除。 证明：由假设知五( z ) 被( x ) 的两个或者两个以上的不可约因式整除，那么最多有6 一r 2 个整除某些( x ) 的不可约因式研( z ) 不整除z ( z ) ，那么既( 工) ，鼠( z ) ，鼠( z ) 的任意 集合，其中= b - r 2 + 1 ，的最大公因子一定包含至少一个整除五( z ) 的不可约因式中的 一个。 引理4 1 2 - 设缈= 6 一r 2 + 1 ，对任意的1s fs 6 ，如果剩余向量的第i 个位置包含有一个 非零错误值e f ( 工) o ，那么至少有一个剩余错误q ( 石) ( m o d 鼠( z ) ) 是非零的，对于任意 j i j 2 j 。，js i 证明：假设所有的乞( x ) ( m o d 岛，( x ) ) 均为0 ，那么将存在( 石) 的一个不可约因式整除 q ( 工) 和z ( x ) ，这与前提假设d e g q ( x ) d e g q ，( x ) z ( x ) 矛盾，因此一定有至少一个不 为零的。 一类特殊码的有效错误控制 定理4 1 1 ：如果剩余向量包含t 个错误，其中o tr t + 1 s r 2 ，那么伴随这个向量的校 验矩阵至少有一个非零分量。 证明：不失一般性的，我们假设两个剩余向量在前b - t 个位置是相同的，在后t 个位置 不同，这并不影响证明，只是为了符号标记的简单些。这样巳( z ) = e ：( z ) ；= 气- ，( x ) = 0 ， 那么校验矩阵e 的前b - t 个分量在b - t + l 行是以小。，j ( 工) ；气小。( x ) ( m o d g + 1 ，( z ) ) ，其 中1s ，s 6 一t ，因为0 d e g e b - ，+ 1 ( x ) o ，而2 t + 1 = 3 s ， = 2 r - 1 = 3 ，因 此定理可用。由向量y 。和y 。给出的校验矩阵为臣一 02 10 0 0 0o o o 0 o o 0 o 0 ，毛= o o o 0 0 o o o 0 o 0 0 o1 2o 它们没有非零分量大于2 的行，所以无法改正。下面看向量y ：是否可以改正。向量y ：的 y l ( x ) 一y ( x ) ( m o d g 。( 工) ) y ：( 工) 一y l ( x ) ( m o d g ：。( z ) ) y ，( x ) 一y ，( x ) ( m o d g ，。( z ) ) y 4 ( x ) 一y 。( x ) ( m o d g 。( z ) ) o ( m o d x ( x + 1 ) ) 2 x 2 一x - 1 ( r o o d ( x + 1 ) ) - x ( m o d x ) z 2 一z l ( m o d l ) 矩 d 。( z ) 、i d ：。( z ) l 站( x ) l d 4 4 ( x ) j y l ( x ) - y ：( x ) ( m o d g 。：( x ) ) y ：( 工) 一y ：( x ) ( m o d g 趁( x ) ) y 3x ) - y ：( x ) ( m o d g ，：( z ) ) y 。( x ) 一y ：( x ) ( m o d g 。：( z ) ) 一氖2 + x + l ( m o d ( x + 1 ) ) o ( m 。d ( z + 1 ) ( 工2 + 1 ) ) - 2 x 2 + l ( m o d l ) 吣2m 。d ( 石2 + 1 ) ) 阵 y l ( 工) 一y 。( x ) ( m o d g 。( z ) ) 夕：( z ) 一y 。( x ) ( m o d g 孔( x ) ) y 。( x ) 一y 。( x ) ( m o d g 弘( z ) ) y 。( x ) 一y 。( x ) ( m o d g “( x ) ) x ( m o d x ) 2 x 2 一l ( m o d l ) o ( m o d x ( x 一1 ) ) z 2 一l ( m o d ( x 一1 ) ) 哨2 + x + l ( m o d l ) x 2m 。d ( x 2 + 1 ) ) 一z 2 + l ( m o d ( x 一1 ) ) o ( m 。d ( x 一1 ) ( 石2 + 1 ) ) 因为1 一b 一错误行数= 4 3 = 1 ，因此错误识别的计算只循环一次即可，它可以正确的 改正单一错误发生的情况。由于只有第二行是唯一包含1 + 1 = 2 个非零分量的行，因此这 个错误的位置在第二个分量上。最后通过计算下列线性同余式 e 2 ( x ) 量2 ( m o d ( x + 1 ) ) ，乞( x ) 暑2 ( m o d ( z 2 + 1 ) ) ，e 2 ( x ) - - o ( m o d l ) ，得到e ：( x ) 一2 ，最后得到 正确的剩余分量 乞( x ) = y ：x ) - e ：( z ) ( m o d ，2 ( 石) ) 一h 2 + 1 2 ( m o d ( 戈+ 1 ) ( 石2 + 1 ) ) = 及2 1 ( m o d ( z + 1 ) ( x 2 + 1 ) ) 。2 x 2 + 2 ( 在e 卜1 中) 因此可得正确的剩余向量。 第二种情况： 当r = 3 时，即码的解空间的h a m m i n g 距离为3 ，那么由前面3 2 部分定理，我们知道 当t + 1s ，时，可以检测到错误，当丑+ 1s ，时，我们可以改正检测到的错误。由r = 3 ， 我们可以检测到检测到ts2 时，即发生一个或两个错误的情况，而我们能改正 x z x z ，i_、，-i、，j_、，j、 b 弘 钉 验d d d d 、l，、l，、l，、i， 工 石 石 x ，j，f，i、， 心 勉 强 心 d d d d 、-，、i，、-，、-， x 工 z x ，i_、，l、，j_、，-_、 r 2 3 4 口d a 口 ，jj-_-。_-。_-。-。-_ = 校 易 一类特殊码的有效错误控制 2 f + 1 墨3 ，2 ts2 , ts1 ，即发生一个错误的情况。而利用前面4 1 部分的定义的内在错误 及需要添加的新的条件知，我们能检测f + 1 s ，即最多发生两个错误，而能改正2 t + 1s r 2 的情况，而在r = 3 ，k