（微电子学与固体电子学专业论文）rs码的研究及modified+euclid算法的实现.pdf

摘要 摘要 随着信息传输、可靠性和有效性的要求不断的提高，纠错码在众多领域也得 到了迅速的发展和广泛的使用。在移动通信中，纠错码被广泛用于模拟体制的信 令传输及数字体制的整个传输，以提高传输的可靠性和节省频谱资源；另外，在 计算机存储、光存储、超大规模集成电路等领域使用也很广泛。 r s 纠错码是一类有很强纠错能力的多进制b c h 码，也是一种典型的代数几 何码，它的代数结构决定了它具有很好的纠突发错误和随机错误的能力。是经过 证明的高性能码。 目前，对r s 纠错码的译码，使用较多的有两种方法：代数译码和变换译码。 变换译码是一种纠错多个错误的快速译码方法。本文研究和讨论的是代数译码方 法，如b e l e k a m em a s s e y 算法和e u c l i d e a n 算法多属于代数译码方法码。本文将从 介绍信道编码理论入手，分析各种b c h 码字，并且详细研究r s 码，重点研究 e u c l i d e a n 译码方法，并在传统的e u c l i d e a n 方法基础上提出一种较为先进的改进型 e u c l i d e a n ( 欧几里德) 译码方法，其先进性在硬件结构和算术迭代等方面都有体现。 另外，对出现删除时候的纠删译码方法进行了介绍，并且将m o d i f i d ee u e l i d s 算法 应用于r s 码的纠错纠删上。在论文的最后介绍了两种近期提出的纠错码：卷积码 和t u 曲o 码。 关键词：r s 码e u c l i d e a n 译码突发错误纠删 a b s t r a c t3 a b s t r a c t w i t ht h er e l i a b i l i t yo fi n f o r m a t i o n r e q u i r e m e n t so fc o n t i n u o u si m p r o v e m e n t ， t r a n s m i s s i o na n dt h ee f f e c t i v e n e s so ft h e e r r o r - c o r r e c t i n gc o d e si nm a n yf i e l d sh a s a l s ob e e nar a p i dd e v e l o p m e n ta n de x t e n s i v eu s ei nm o b i l ec o m m u n i c a t i o n ， e r r o r - c o r r e c t i n gc o d e sa r ew i d e l yu s e dt os i m u l a t et h es i g n a l i n gs y s t e mt r a n s m i s s i o n a n dd i g i h a lt r a n s m i s s i o ns y s t e m 弱aw h o l et oi m p r o v et h er e l i a b n i t yo ft r a n s m i s s i o na n d s a v es p e c t r u mr e s o u r c e s ；a n o t h e ri nt h ec o m p u t e rs t o r a g e ， o p t i c a ls t o r a g e ， u l t r a - l a r g e - s c a l ei n t e g r a t e dc i r c u i t s ， a n do t h e rf i e l d sh a v ea l s ob e e nw i d e l yu s e d r sc o d ei sak i n do fe r r o rc o r r e c t i o na b i l i t yo f as t r o n gm u l t i - b a n db c hc o d e ，i sa t y p i c a le x a m p l eo fa l g e b r a i cg e o m e t r yy a r d s ， a n di t sa l g e b r a i cs t r u c t u r ed e t e r m i n e s t h a ti th a sag o o dg a n gb u r s te r r o r sa n dr a n d o ma r r o r s c a p a c i t y i sap r o v e n , h i g h - p e r f o r m a n c ec o d e d e c o d i n gt h ec u r r e n tr sm e t h o d ，t h eu s eo fm o r eo fat w om e t h o d s ：a l g e b r a i c d e c o d i n ga n dt r a n s f o r md e c o d i n g t r a n s f o r mi sad e c o d i n ge r r o r - c o r r e c t i o no v e rt h e r a p i dd e c o d i n gm e t h o d s t h i sp a p e ri s s t u d i e da n dd i s c u s s e da l g e b r a i cd e c o d i n g m e t h o d s b e l e k a m p _ m a s s e ye u c l i d e a na l g o r i t h ma n dd e c o d i n ga l g o r i t h r n sa r em o s t l y a l g e b r a i cm e t h o d s t b i sp a p e rw i l ls t a r tw i t hl e t t e ro fc o d i n gt h e o r y ，t h ea n a l y s i so f b c hc o d ew o r d ，a n dd e t a i l e ds t u d yo fr sc o d e ，f o c u so ne u c l i d e a nd e c o d i n g m e t h o d s ， i nt h et r a d i t i o n a le u c l i d e a nm e t h o db a s e do nam o r ea d v a n c e dm e t h o do f i m p r o v i n gt h ee u c l i d e a nd e c o d i n g ， a d v a n c e dh a r d w a r es t r u c t u r e ，a n da r i t h m e t i c ， a n do t h e ra s p e c t so fi t e r a t i v ea tt h es a m et i m e ，at i m et od e l e t et h ee r a s u r ed e c o d i n g m e t h o d sw e r ei n t r o d u c e d ，a n dw i l lm o d i f i d ee u c l i d sa l g o r i t h mi sa p p l i e dt ot h er s e r r o rc o r r e c t i o nc o d eo ne r a s u r e p a p e r si nt h ef i n a lc o m p a r i s o no ft h et w oo u t s t a n d i n g c o d e ：t u r b oc o n v o l u t i o n a lc o d e sa n dc o d et oac e r t a i np r e s e n t a t i o n k e y w o r d s ：r sw o r d e u c f i d e a nc o d m g c o r r u p te r r o r e r a s u r e s 西安电子科技大学 学位论文独创性( 或创新性) 声明 秉承学校严谨的学风和优良的科学道德，本人声明所呈交的论文是我个人在 导师指导下进行的研究工作及取得的研究成果。尽我所知，除了文中特别加以标 注和致谢中所罗列的内容以外，论文中不包含其他人已经发表或撰写过的研究成 果；也不包含为获得西安电子科技大学或其它教育机构的学位或证书而使用过的 材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中做了明确的说 明并表示了谢意。 申请学位论文与资料若有不实之处，本人承担一切的法律责任。 本人签名： 年 西安电子科技大学 关于论文使用授权的说明 本人完全了解西安电子科技大学有关保留和使用学位论文的规定，即：研究 生在校攻读学位期间论文工作的知识产权单位属西安电子科技大学。学校有权保 留送交论文的复印件，允许查阅和借阅论文；学校可以公布论文的全部或部分内 容，可以允许采用影印、缩印或其它复制手段保存论文。同时本人保证，毕业后 结合学位论文研究课题再攥写的文章一律署名单位为西安电子科技大学。 ( 保密的论文在解密后遵守此规定) 本学位论文属于保密，在一年解密后适用本授权书。 本人签名： 导师签名： 日期堡兰：! ：堕 第一章绪论 第一章绪论 1 1 研究背景 在数字信息化发展日新月异的当今时代，信息对经济、科技、文化、及人们 日常生活都起着不可替代的作用。信息的交换、处理和传输是属于现代通信领域 的范畴。通信的目的是把对方不知道的消息及时可靠的传送给对方。因此，要求 一个通信系统传输消息必须可靠与快速。在数字系统中，可靠与快速往往是一对 矛盾，如何合理地解决可靠性也速度这一对矛盾，是正确设计一个通信系统的关 键问题之一。 目前r s 码也广泛应用也深空通信、扩频通信以及数字多媒体应用等领域。因 为它是一种循环码，有严谨的代数结构，在码率固定的情况下它具有较大的纠错 能力，从而提高了通信系统的可靠性，但提高可靠性的同时，又增加了译码器设 计的复杂度，并且随着码长的增加，译码器的复杂性也不断增加，这又不可避免 的以牺牲通信的速度为代价。因此提高r s 码的译码速度，简化译码器的结构具有 重要作用，这也是本文的研究任务。 本课题是在大连东软公司认事业部实习时，依公司所承担的日本p a n a s o n i c 公司的有关d v d c de c c 模块验证项目而定。 1 2 信道编码理论和纠错码的分类 一个信息源的输出在噪声信道中的传输问题是信道论和编码理论中最重要的 部分，所有的数字通信系统如通信、雷达、遥控遥测、数字计算机存储系统和内 部运算以及数字计算机之间的数据传输等。 构造一个信息源序列u = ( u ，u ：，u 。) ，序列的各个分量由独立、同分布的 随机变量组成，具有相同的概率分布函数p = u = 0i = pu = 1 = 1 2 。我们的目 的是在信道中传输这“k ”比特信息，共利用新到1 1 次平均每次的代价。设x = ( x 。，置以) 是相应的信道输入，y = ( ，艺艺) 是信道的输出，而u u ， u ：，u 。) 表示接收者对u 的估计，我们假设它只依赖于y 。这个假设如图 1 1 所示： 图1 1 设想的通信系统 2 r s 码的研究及m o d i f i e de u c l i d 算法的实现 图中1 2 中信源编码器是把发出的消息如语言、图像、文字等转换成二进制( 或 多进制) 形式的信息序列。为了抗击传输过程中的各种噪声干扰，往往要人为的 加一些多余度，使其具有自动检错和纠错能力，这种功能由图中的信道编码器完 成。调制器的功用是把纠错码送出的信息序列通过调制器变换成适合于信道传输 的信号。 图1 2 数字通信系统模型 s h a n n o n 信道编码定理【3 】：每个信道具有确定的信道容量c ，对于任何小于c 的 码率尺，存在有速率为r 码长为万分组码及( 以。，k 。，m ) 卷积码，若用最大使然译码， 则随着码长的增加其译码错误率p 可任意小，即： p a e n e 6 ( 川 - ( 1 1 ) 纠错码的分类，各种差错控制系统中所用到的码，不外乎是能在译码器自动发现 错误的检错码，或者不仅能发现错误而且能自动纠正错误的纠错码，或者能够纠 正删除错误的纠删码。图1 3 表示了对纠错码的分类【l j 。 图1 3 纠错码的分类 第一章绪论 1 3r s 的实际应用领域 r s 码是由r e e d 和s o l o m o n 在19 6 0 年通过论文“p o l y n o m i a lc o d eo v e rc e r t a i n f i n i t ef i e l d s ”所提出的。在提出的初期，即在1 9 6 5 年以前很长的一段时间里，当 时的数字电子技术未能够根据r s 码的有关内容作出相应的实际应用，而同样的 r s 码纠错理论却在当今的数字电子技术领域发挥着非常重要的作用，其原因在于 把r s 码有效的推向实际应用的关键技术有效的r s 码译码算法，在当时未能有 实际性的突破。尽管很早之前就有人在研究r s 码的译码算法，并且在1 9 6 1 年就 有了可行的p g zr s 码译码算法，但是该算法过于复杂，以至于无法将其用于数字 电子技术的实现，而1 9 6 5 年后b e r l e k a n a p 和 算法的提出最终m e s s s a y e u c l i d e a n 解决了r s 码实际应用的最后障碍。 从提出信道到现在，r s 码已在许多不同的领域应用：如数字电视传输、硬磁 盘驱动( h a r dd i s kd r i v e r s ) 、c dr o m 、数字图像处理系统、大容量存储系统、远 距离通信和数据广播协议、单信息包数字数据( c e l l u l a rd i g i t a lp a c k e td a t a ) 、无线 个人数据处理、可容错r a i d 控制器、深空探测、移动系统的地面同步对接( m o b i l e s y s t e m sg c o s y n c h r o n o u ss a t e l l i t ec o m m u n i c a t i o n sl i n k s ) 等。 同时，r s 码在许多不同的国际标准中得到了相应的规定，如：c c s d s ，i e e e 8 0 2 1 4 ai e e e8 0 2 1 4 b ，w 二c d m a ， v s b ，i m t 2 0 0 0 ，d v b ，d v d 等，而 在国内外的航天工作中，r s 同样在许多的任务中发挥着重要的作用，例如国内的 神州3 号、神州4 号、神州5 号以及探测一号等任务；国外的m a r i n e r 9 、v o y a g e r l 、 m a r sl a n d e r 和m a r se x p l o r a t i o nr o v e r 等任务。 1 4 本文工作 对于r s 码，目前较为通用的译码迭代算法主要有：b m 算法和e u c l i d e a n ( 欧 几里德) 算法。其中e u c l i d e a n 算法结构较为简单，电路实现容易，因此被广泛的应 用。本文提出一种改进的e u c l i d e a n 迭代方法，使得迭代中消除了除法运算，从而 提高了迭代速度，减少了译码占用的时间。 本文共五章，内容如下： 第一章：简要介绍了信道编码的基本理论及其发展过程，信道编码的应用， 纠错码的分类，重点阐述了r s 码的一些应用领域。 第二章：讨论了目前使用较多的几种线性码及编码方式，给出了线性分组码 的重要参数、r s 码的性质、编码原理，重点推导了生成矩阵、校验矩阵生成码字 的编码过程。 4 r s 码的研究及m o d i f i e de u c l i d 算法的实现 第三章：详细论述了r s 码编译码原理及算法，重点讨论了代数译码流程及一 些译码的关键问题，对运用解关键方程寻找错误位置和错误值的方法进行了系统 的分析和推导。在本章的后半部分提出了m o d i f e i de u c l i d e a n ( 改进型欧几里德) 译码方法，并且给出硬件电路的实现和各模块的硬件描述语言的实现( 见附录) 。 第四章：是对当前的纠错码理论范围的进一步展望和拓展，随着纠错码应用 领域的日益增加，提出了目前研究最多的两种码字：卷积码和t u r b o 码。本章介绍 了这两种的码字的优良特性及编码方式，并且对它们与r s 码作了一定的比较，提 出了今后纠错码的研究方向。 第五章：是全文的结束语部分，在本章对全文最了总结，提出了研究的不足 与缺陷以及今后还需要进行努力的方面。 第二章几种纠错码的编码技术 第二章几种纠错码的编码技术 2 1 线性分组码 线性分组码是分组码中的一类最重要的纠错码，它是讨论各种码的基础。虽然 这类码的概念比较简单，但却非常重要，特别是有关码的生成矩阵g 和校验矩阵h 的表示，以及它们的关系。 i 2 1 1 线性分组码的基本概念 一个 n ，k 线性分组码，是把信息划分成k 个码元为一段( 称为信息位) ，通过编 码器变成长为1 3 个码元的一组，作为 1 3 ，k 线性分组码的一个码字，若每位码元的 取值由q 种( q 为素数幂) ，则共有q 个1 3 个码字。n 长的数组共有g 组，在二进制 情况下，由2 “个数组显然，q “个n 维数组( n 重) 组成一个g f ( q ) 上的n 维线性空间。 如果q ( 或2 8 ) 个码字集合构成了一个k 维线性空间，则称它是一个 n ，k 3 线性分组 码。 从另一方面讲就是，长为n 有2 个码字的分组码c ，当且仅当c 构成域g f ( 2 ) 上r l 维矢量空间的v 。的一个k 维子空间时，称c 为线性分组码，v 。是一个矢量空间， 线性分组码是它的一个子空间，对于加法运算它是一个交换群，所以线性分组码也 成为群码。 线性分组码有三个重要的参数：r 、w 和d 。 r = k n 表示在码字中信息位所占的比重，称为编码效率或者编码速率，简称码 率。它表明了信道利用的效率，所以也称为传信率。r 越大，表明码的效率越高或者 传信率越高。 w 是码字的h a m m i n g 重量，简称重量或h 重，表示码字中非零码元符号的个数。 在线性分组码中c 中，非零码字重量的最小值，叫做c 的最小重量w 曲，表示为： w 血= m i n w ( c ) ，c c ，c 0 ) ( 2 - 1 ) 在【n ，k 线性分组码中，两个码字u ，v 之间对应码元位上取值不同的符号个数， 成为码字u ，v 之间的h a m m i n g 距离，简称距离或者h 距，用d ( u ，表示。距离 具有对称性( d ( c 1 ，c2 ) = d ( c ：，c 。) ) 、非负性( d ( c ，c2 ) 0 ) 和满足距离三角不等 式d ( c l ，c ，) s( d ( c 。，c2 ) + d ( c2 ，c3 ) ) 这三个性质。任意两个码字之间距离 的最小值，称为码的最小距离d 曲若c o 和c 力是任意两个码字，则码的最小距离 6 r s 码的研究及m o d i f i e de u c l i d 算法的实现 司以表不成： d m = m i n d ( c i ，c2 ) ) ，i ，j = 0 ，1 ，2 ，2 一1 ( 2 - 2 ) 码的最小距离d 曲是衡量码抗干扰能力的重要参数，码的d 幽越大，码的抗干 扰能力越强。如果一个线性码能检出长度，个码元的任意错误图样，则称码的检错 能力为，；如果线性码能纠正长度t 个码元的的任意错误图样，则称码的纠错能力为 t 。 码的最小距离d 曲和纠错能力有密切的关系，可以归纳为以下几条： ( 1 ) n ，k 】线性码能纠正t 个错误的充要条件是码的最小距离d 硫= 2 t + 1 。 ( 2 ) n ，k 】线性码能检出，个错误的充要条件是码的最小距离d 曲= ，+ 1 。 ( 3 ) 1 1 ，k 】线性码能纠正t 个错误的并发现z 个错误的( ， t ) 的充要条件是码的最小 距离d i n j i l = ，+ t + 1 3 0 1 。 在线性分组码中有几个重要的概念：生成矩阵、校验矩阵、伴随式等分别会在 下一节中叙述。 2 1 2 线性分组码的几个重要概念 生成矩阵： 由线性分组码的定义可以得出， n ，k ，d ( d 称为汉明距离，今后用作系统码的 最小距离) 分组码的q 个码字组成了一个k 维子空间，因此这q 个码字完全可以由 k 个独立矢量的基而张成，可写成下面的矩阵形式， =降j寥gl,0go l = i9 2 扩l 乳扩2 9 2 0l l ： ： ：i l g 铀一lg 咖一2 g k ，0 - j 其中，g f = ( g f o ，g f 1 ，g 抽一i ) ，0 i 七。 设k 个数字信息组组成的消息由u - “。，“ 表示，则相应得码字v 为 g o = 雌，垆 ( 2 3 ) ( 2 - 4 ) ( 2 5 ) = “o g o + “1 9 l + + “正一l g 七一l ( 2 - 6 ) g 的行张成了k 维线性子空间，或者说g 的行生成了线性分组码c ，矩阵g 成为c 的生成矩阵，所以一个线性分组码完全有生成矩阵确定，因此线性分组码只要存储g 第二章几种纠错码的编码技术 7 矩阵的k 行，并根据输入消息u 构成这k 行的一个线性组合，即码字。 一致校验矩阵： n ，k ，d 编码问题就是在n 维线性空间中，如何找出满足有q 个矢量组成的k 维线性子空间v 磁。即在满足给定条件下( 码的最小距离d 或码率r ) 下，从已知 的k 个信息元中求得r = n k 个校验元。相当于己知k 个系数，要求1 1 一k 个未知数， 使得到的码正好有所要求的最小距离d 。根据矢量空间中零化空间的知识，对任意有 k 个线性独立行的k 1 1 1 阶矩阵g ，存在一个具有1 1 一k 个线性独立( n k ) 1 1 阶 矩阵h ，g 的行空间的矢量与h 的行正交，并且与h 的行正交的矢量都在g 的行 空间中，这说明由g 和h 的行生成的空间互为零空间。即有 g 1 h = 0 或g h1 = 0 ( 2 7 ) 矩阵h 叫做码的一致校验矩阵( 简称校验矩阵) 。 伴随式： 伴随式是有关译码的内容，但是后面要引出伴随矩阵的知识，所以伴随式在编 码部分就给出 设发送的码字c = ( c n - i ，c 啦，c 1 ，co ) ，通过有扰信道传输，信道产生的 错误图样e = ( ea - i ，en - 2 ，e l ，c o ) 。接收端译码器收到的n 重为r = ( r n - 1 ，r 一- 2 ， ，r l ，r o ) ，i 净c + e 。【n ，k ，d 】码的每一个码字c ，都必须满足式( 2 5 ) 和式( 2 6 ) ， 因此收到r 后用在两式之中的任式进行检验： r o l l t =( c + e ) h t ；c oh t + e h t = e h t ( 2 8 ) 若e = 0 ，则r h1 = 0 ，e 0 则r h1 0 。说明r - h1 仅与错误图样有关， 而与发送什么码字无关。令： s = r o l l t = e eh t 或s t = h - r t = h e t ( 2 - 9 ) 称为接收矢量r 的伴随式( 或校正子) 。 系统码： 若信息组以不变的形式码组的任意k 位( 通常在最前面：cn 4 ，cn 之，c ， co ) 中出现的码称为系统码，否则称为非系统码。由于系统码的码字前k 位是原来 的信息组，故由式( 2 - 3 ) 知，g 矩阵左边k 列必然组成一个方阵i 因此系统码的生 成矩阵通常为 g = i 。p ( 2 一1 0 ) 表2 1 系统码的一种结构形式 彰7，k 位信息位1 1 一k 位校验位。i 式中，p 是k ( n k ) 阶矩阵。如果信息组不在码字的前k 位，而在码字的后 r s 码的研究及m o d i f i e de u c l i d 算法的实现 k 位，则g 矩阵中的i 方阵在p 矩阵的右边。因为g 与h 矩阵互为零空间，所以式 ( 2 - 7 ) 相应的h 矩阵为 h = 一p i 。 ( 2 1 1 ) 式中，一p1 是一个( n k ) x k 阶矩阵，它是p 矩阵的转置，“一号表示一p 阵中的 每一元素是p 阵中对应元素的逆元，在二进制情况下，仍使该元素自己。显然，由 此得到得h 满足 ，厂一p 叫i k 明k j q 。1 2 ) 通常称式( 2 一1 0 ) 和式( 2 1 1 ) 中的g 和h 矩阵为码的典型( 标准) 生成矩阵和典型 校验矩阵。系统码的编码相对较简单，且由g 可以方便地得到h ( 反之亦然) ，容易 检查编出的码字是否正确。同时，对分组码而言，系统码与非系统码的纠错能力完 全等价。因此，若无特别声明，仅讨论系统码的形式。 2 2 循环码 循环码是一类最重要的线性码，它具有以下的性质： ( 1 ) 循环码具有严谨的代数结构，其性能容易分析。特别是目前已经发现的大部 分线性码与循环码有密切关系，它们中的大部分码都可归结为循环码。 ( 2 ) 循环码具有循环特性，编译码电路特别是编码电路简单易于实现。 因此它是研究r s 码的基础，对它的研究也表较深入和系统。 2 2 1 循环码的基本概念 一个n 重子空间v 础ev 一，若对任何一个v = ( a n _ la 脚，a o ) v 址， 恒有v 1 = ( a n - 2a 脚，a o ，a 川) v 础，则称v 础为循环子空间或循环码。也就 具有这种特性的 n ，k 分组码称为循环码。由于 n ，k 线性分组码是n 维线性空间v 一 中的一个子空间，因此 n ，k 循环码是n 维线性空间中的一个k 维循环子空间。 l1 o1110 0i g = lo1o111ol l00101 11l 第二章几种纠错码的编码技术 9 这个码有8 个码字。如果以c - ，c ：，cs 表示g 的行，那么非零码字为： c 1 = 1 0 1 1 1 0 0 c2 = 0 1 0 1 1 1 0 c3 = 0 0 1 0 1 1 1 c1+c2 = 1 1 1 0 0 1 0 c 1 c = 1 0 0 1 0 1 1 c2+c3 = 0 1 1 1 0 0 1 c1+c2 + c3 = 1 1 0 0 1 0 1 这个码实际就是一个循环码。 2 2 2 码的生成函数 循环码的定义表面上看起来很随意，但实际上这样有充分的理由，尤其是在我 们引入码字的生成函数以后。如果c = ( c0 ，c - ，c n - i ) 是一个码字，那么它的 生成函数定义为多项式： c 伍) = c 0 + c ix+ + c ”一1 x ( 2 1 2 ) 一_ x 是一个未知数，通过利用循环位，可以给出码字右循环移位的一个简单代数描述， 为了给出这一描述，需要定义整数和多项式的一个重要的“m o d 运算。 定义2 2 2 1 如果p 和m 是整数，且m 0 ，小则“pm o dm 表示p 除以m 得到 的余数，因此p m o d m 等一个能使p r 被m 整除且o r m 一1 的整数r 。同样， 如果p ( x ) 和m ( x ) 是多项式，则p ( x ) m o dm ( x ) 表示p ( x ) 除以m ( x ) 的余式因 此p ( x ) m o d m ( x ) 等于唯一能使p ( x ) - r ( x ) 被m ( x ) 整除，且d e g r ( x ) - 3 ，m 是任意整数) 有限域上，且r s 码是m d s 码，具有极大最小距离特性，它具有卓越的纠错能力，无论是纠突发错误还是纠随 机错误的能力，以及它的快速译码速度，均是其它码类无法比拟的。用m s 多项式 产生的是非系统码，而用b c h 构造方法能产生系统码。我们用的是后一种。 r s 码的定义： 定义：g f ( q ) t 的( q 2 ) ，码长n = q 一1 的本原b c h 码成为r s 码。 可知r s 码最主要的特点之一是码元取自g f ( q ) 上，而它的生成多项式也在g f ( q ) 上，所以r s 码是码元的符号域与根域一致的b c h 码。 因为x 叮1 - 1 = n ( x a 1 ) ，a 。的最小多项式m t = ( x a ) 。所以，长为n = q l ， a e g f ( q ) 设计距离为万的r s 码，由b c h 码的定义可知，它的生成多项式 g ( x ) = ( x a 嘞) ( x a 肼0 + 1 ) ( x - a 柳0 w 2 ) ( 3 1 ) 通常情况下取m o = 0 ，此时 g ( x ) = ( x a 嘞) ( x a 嘞+ 1 ) ( x - a 万一2 ) ( 3 2 ) 码的描述是：码长n = q - 1 信息位数k = n d + 1 最小距离d 血= 艿= 2 t + 1 ，此时生 成多项式可以写成： g ( x ) = ( x 1 ) ( x a ) ( x a 2 卜1 ) ( 3 3 ) 由此生成一个q 进制的【q 1 ，q 一艿】r s 码，有最小距离万。由于线性码的最大可能的 1 6 r s 码的研究及m o d i f i e de u c l i d 算法的实现 最小距离是校验元的个数加l ，而r s 码恰好做到了这一点。因此，称r s 码为极大 最小距离可分码，简称m d s 码。显然r s 码的设计距离万与实际距离d 是一致的。 如果我们要设计一个万= 9 的r s 码，显然r s 码的冗余位为万1 = 8 = 2 t 它的生成 多项式为： g ( x ) = ( x 一1 ) ( x a ) ( x a 7 )( 3 4 ) 3 2r s 码的时域编码 对于r s 码的编码问题，时域和频域都比较简单，时域编码只需要一次多项式除 法，频域编码需要一次i f f t ，不同的是，用频域编码的码字是系统码，可用于截短 编码，而频域编码编出的码字是非系统码。我们讨论和采用的主要是系统码，所以 这里只介绍时域编码的方法。 r s 码的编码主要是围绕码的生成多项式g ( x ) 进行的，其编码器基本上分成两类： k 级编码器和n k 级编码器。 系统码的g 矩阵为：g = i 。p 】 左边是k x k 阶单位方正。这相当于码字多项式的第1 1 1 次至第n k 次是信息位， 其余为校验位，即 c ( x ) = m ( x ) x ”。十“x ) 三0 ( m o d g ( x ) )( 3 - 5 ) 式中 m ( x ) = m k 一1x “地心xk - 2 + 慨1x 协o ( 3 6 ) 是信息多项式，( m k - 1x “，mm x 扣2 ，m l ，m o ) 是信息位，而 “x ) = r n - x 柑一1 竹柑一2 x 础一2 + 斗t l x + f o( 3 7 ) 是校验位多项式，相应的系数就是码元的校验位。由上可得 - r ( x ) = c ( x ) + m ( x ) x ”暑m ( x ) x ”。( m o d g ( x ) ) ( 3 8 ) 所以要构造用g ( x ) 生成的系统码，首先必须将信息组乘以x ”变成xn - k m ( x ) ；然后 用g ( x ) 除，得到余式“x ) ；再将其各项系数取加法逆元，就得到了所要的校验位了。 因此循环系统码的编码问题就以g ( x ) 为模的除法问题。 下面给出一个1 1 k 级r s 码的编码电路： 第三章r s 码的编码及e u c l i d e a n 译码方法 殳岛r 蜀一r g y 、ryyy l 一，一、一、，、7 一、 一 一、 b + ，爷岛州+ 也步i + ，魄，一榭+ 十+ 一 一7 l 一一 、二j 、一1 _ _ 卜一 图3 1 模块e n c o d e r 逻辑图 从图上可以看出，有一个单元时重复的，即一个乘法器，一个加法器和一个 移位寄存器，这样我们把它独立出来做成底层模块。本电路的工作原理： 2 t 级移存器的初始状态全清为零，开关先转向2 ，然后进行移位，送入信息组 m ( x ) 的系数，高次为系数首先进入电路，它一方面直接经或门输出，另一方面自动 乘以x 一次后进入除法电路，从而完成了x m a ( x ) 的作用。 k 次移位后，m ( x ) 全部送入电路，完成了除法作用，此时移存器内保留了余式 r ( x ) 的系数，在二进制的情况下就是校验元，此时把开关打向1 ，经过1 1 k 次移位后， 就把移存器的校验元全部输出，与原先的k 为信息元组成了一个1 1 长的码子。 g f ( 2 ”1 上的r s 码是2 “进制码，它的编码电路可用k 或n k 级多进制移位寄存 器实现，例如能纠两个错的 3 2 ，2 8 r s 码就是用4 级除法电路实现。采用n k 级 编码器，随机产生1 0 0 0 个2 8 位的信息位然后编码生成1 0 0 0 个( 3 2 ，2 8 ) 码字，与图 3 1 对应的v e r i l o g 硬件描述语言代码见附录：5 所示，图3 2 是采用m o d e l s i m 的仿 真结果。 图3 2 编码器波形图 k 级编码器是利用校验多项式h ( x ) = h 女x + h 女- 1x + + h 】x + hoh f g f ( 2 ”) r s 码的研究及m o d i f i e de u c l i d 算法的实现 来构成的，因为用的较少，所以这里就不再讨论了。 3 3r s 码的一般译码算法 r s 的译码算法问题，一直是编码理论研究中的最感兴趣的课题之一。一个码能 否在实际中应用，往往取决于译码器的是否简单、经济和译码错误概率小。自7 0 年代中以后，很多作者研究了超b c h 限的设计距离的译码问题，如能到达h t 限和 r o o s 限的译码问题。但目前用的最普遍，实用上最重要的还是时域中的迭代译码法。 3 3 1r s 码的时域译码算法 r s 码的译码步骤分为三步：第一步是由接收到的r ( x ) 计算出伴随式s ；第二 步由伴随式式找出错误图样豆( x ) ；第三步由r ( x ) 云( x ) 得到最可能发送的码字 6 ( x ) ，完成译码。 g f ( q ) 上的 n ，k ，d r s 码以1 ，a ，a 2 ，a 2 卜1 为根，则它的生成多项式为： g ( x ) = ( x 一1 ) ( x - a ) ( x a 2 卜1 ) d = 2 t + 1 ，a e g f ( q ”) 为n 级域元素。发送的码字c ( q ) = q ( x ) g ( x ) ，接收的1 1 重为r ( x ) = c ( x ) + e ( x ) 。设错误图样 e ( x ) = e n - i x ”1 + e 柚x n - 2 + + e l x + e o( 3 - 9 ) 若信道产生t 个错误，则 e ( x ) = y ，x + y f - l x + y l x = 】，；工 ( 3 1 0 ) 式中，y ，o f ( q ) ，x 称为错误位置数，说明错误发生在r ( x ) 中的第n 1 ，中的第n 一1 r 位，错误值是y ，。如果r ( x ) 中有y 个错误，则e ( x ) 共有y 项y ，x ，i = 1 ，2 ， ，a 由伴随式定义可知：s r = h e r r = h o e r 。 第三章r s 码的编码及e u c l i d e a n 译码方法 1 9 式中 1 口 - l ( a 2 t - i ) 纠 1 口4 - 2 ( a2 t - i ) ”2 ( 口o ) + y 2 ( 口o ) ：+ + y ，( 口o ) y i ( 口1 ) + l ( 口1 ) 厶：+ + y r ( a1 ) 屯 ； y i ( 口2 。1 ) + y 2 ( 口2 一) 2 + + y f ( 口2 。1 ) k so = r ( 4 o ) = e ( ao ) s i = r ( a1 ) = e ( 口1 ) s2 川= r ( 口2 t - - i ) = e ( 口2 h ) ( 3 1 1 ) f s = z ( 口哕j = n l 。，mo + 1 ，mo + 2 t + lm 。= 0 ( 3 1 2 ) i = 1 - 3 ) - ( a + ) = 五嘞州，则有 f s o = z + 砭+ + e = k 七= l f 足，一，= 】，；石? 。q + 艺工；卜1 + + r x 尸一_ - z 砭d ( 3 1 3 ) k - - i 称式中的s ，为x 的加权幂和对称函数。当接收到一个接收码字r 以后，可以用校验 矩阵h 来检验r 是否满足校验方程，即，h r = 0 是否成立，则认为r 是一个码 字；否则，判断码字在传输中出现了错误。因此h r 是否为0 是检验码是否出错的 依据。把s = h r 或s = h r 称为接收码字r 的伴随式( 校验子或者监督予) 。它有 下述几个特点【”】： ( 1 ) 伴随式与错误图样有关，而与发送的具体码字无关，即，伴随式仅由错误 图样决定。 0；l；0 0；巧0 o ；0 2 0 r s 码的研究及m o d i f i e de u c l i d 算法的实现 ( 2 ) 伴随式是错误的判别式：若s = 0 则判为无错，接收到的是一个码字；若s 0 ，则判为有错。 ( 3 ) 不同的错误图样具有不同的伴随式，它们是一一对应的。 译码的目的就是由式( 3 1 1 ) 解出2 t 个方程解出2 t 个未知数工，l ( i = 1 ，2 ，t ) 。分 两步进行，先解出错误位置数x ，再求出错误位置值e 。为此引入错位位置多项式。 仃( 石) = ( 1 一x l x ) ( 1 一x 2 x ) ( 1 一_ 工) f 3 1 4 ) 若第k 个错误位置x = x ：，则口( x ：1 ) = 0 。因此，求错误位置就是求解错误位置多 项式a ( x ) 的根。将a ( x ) 展开： f 仃( 工) = ( 1 - 而x ) ( 1 - x 2 x ) ( 1 - x ，x ) = 兀( 1 - x f 工) i = 1 = 1 - ( x 1 + x 2 + + 工，) x + ( 工l 石2 + x 2 工3 + + x i - l x f ) x 2 一+ ( 一1 ) 工1 2 2 x f( 3 1 5 ) 令 仃1 = 一( x l + x 2 + + x ，) 仃22 ( x l z 2 + x l x 3 + + x l _ 1 x t ) 仃f = ( 一1 ) 7 x i x 2 t ( 3 1 6 ) 则式( 3 1 4 ) 成为 t 仃( x ) = 1 + o r l x + c r 2 工2 + + o t x 。= 兀( 1 - x f x ) ( 3 一1 7 ) i f f i l 称式( 3 - 1 6 ) 是x ，的初等幂和对称函数。若z i l 为错误位置，则 c r ( x i l ) = l + e r l x ；1 + 仃2 工+ + 仃f x 7 = 0 两边乘以x ：则 x ：+ q 工 t - 1 + 仃2 工女t - 2 + + 盯f = o k ：1 ，2 ，t 上式两边再乘以v x ：，j = m o ，m o + 1 9 o 9 + f - 1 则 ft k x ：州+ 盯。k 工，一+ + 仃。z r , 4 = 0 k = lk = l k = 1 ，2 ，t 对k 求和得 印 p l，、ii = ko = 、i x k ，腻 1 3+ + 一+ k ，心 阢+ 村 玩 ，脚 第三章r s 码的编码及e u c l i d e a n 译码方法 2 l f 由式( 3 - 1 2 ) 若令( 口朋。“) = x 贝o ，s ，= z x ? j = m o ，聊。+ 1 ，m o + 2 t 一1 t f f i l 可知式( 3 - 1 8 ) 成为 i s i ，+ f + q 多，+ f - l + + 仃f s j = 0 j f = 朋o ，m o + 1 ，m o + f 一1 ( 3 - 1 9 ) 取n l o = 0 把上式展开，则 墨+ 吼s - 1 + 1 7 2 s 一2 + + o t s o = 0 s 1 “+ 仃1 墨十仃2 只1 + + o ts l = 0 s 2 r 1 + 吼趴2 + 口2 s 2 l - 3 + + q 钆= 0 ( 3 2 0 ) 或用矩阵的形式表示出来 s l - l s f ： s 卜2 s f 1 ： s 2 f 一2s 2 f 3 s o s l ： s f - l 盯l 0 2 ： 盯l s f s f + l ： s 2 f - l ( 3 - 2 1 )