（通信与信息系统专业论文）rs码及turbo码应用与硬件实现的研究.pdf

摘要 r s 码是一种经典的代数编码方式，由于它是一种极大可分距离码，在纠随机错 误与突发错误方面都具有非常优秀的眭能，所以在工程中应用非常广泛。t u r b o 码 具有近s h a n n o n 限的性能它的出现被看作是信道编码理论发展史上的一个晕程碑， 它使人们设计信道编码的方法不仅仅力求增加码的最小汉明距离而且要努力减少低 重量码字的个数( 错误系数) 。在第三代移动通信系统中，具有代表性的3 g p p 的 w c d m a 、c d m 舵0 0 0 和我国的t d s c d m a 三个标准中的信道编码方案都使用了 t u r b o 码，用于高速率、高质量的通信业务。本文主要是从工程应用的角度，研究 设计了r s 编译码器和t u r b o 码编译码器在f p g a 电路上的硬件实现。主要的工作成 果是： 1 采用e u c l i d 算法实现可根据信道状况优劣采用不同编码方案配置参数的通 用化r s 编译码器。 2 根据不同工程应用对性能需求的不同，采用两种实现策略去设计r s 编译码 器，使得器件在工作吞吐能力与硬件实现成本两方面得到最优化的折中。 3 完成固定参数编码方式下的t u r b o 码编码器，交织器，删余模块，m a p 译码 器的硬件设计实现。 关键词：r s 码e u c l i d 译码算法t u r b o 码软输出迭代译码 m a p 算法v h i ) l a b s t r a c t r e e d - s o l o m o nc o d ei sac l a s so fa l g e b r a i ce r r o r - c o r r e c t i n gc o d e s ，w h i c hh a sm a x i m u m d i s t a n c es e p a r a b l e i nt h ed e c a d e ss i n c et h e i rd i s c o v e r y , i th a se n j o y e dc o u n t l e s sa p p l i c a t i o n s b e c a u s ei th a st h es t r o n gp o w e ro fc o r r e c t i n gr a n d o me r r o ra n db u r s te r r o r t u r b oc o d e si sa n e wc l a s so fe r r o r - c o r r e c t i n gc o d e st h a tc a na p p r o a c ht h es h a n n o nb o u n db yad e c i b e lo rl e s s w i t l li t e r a t i v e l yp r o c e s s e dm a x i m u m - a - p o s t e f i o r id e c o d e r s n o w , t u r b oc o d e si sc o n s i d e r e da s o n eo ft h em o s te x c i t i n ga n dp o t e n t i a l l yi m p o r t a n td e v e l o p m e n t si nc o d i n gt h e o r yi nm a n y y e a r s i t si n v e n t i o nh a sc h a n g e dt h ec o n v e n t i o n a ld e s i g np f i n c i p l e o ft h ec o d i n gs c h e m e f r o mt h ea t t e m p tt oi n c r e a s i n gt h em i n i m u mh a m m i n gd i s t a n c eo ft h ec o d et ot h eg o a lo f r e d u c i n gt h em u l t i p l i c i t yo fc o d e w o r dw i t hl o wh a m m i n gw e i g h t s f r o mt h ev i e wo f e n g i n e e r i n g ，t h i sp a p e rr e s e a r c ha n dd e s i g nr se n c o d e r d e c o d e r ，t u r b oc o d e r d e c o d e ru s i n g f p g a t h em a i nr e s u l t sa r ea sf o l l o w ： 1 a d o p t i n g e u c l i d a l g o r i t h md e s i g nh i g h - p e r f o r m a n c e r e e d - s o l o m o n e n c o d e r d e c o d e r , w h i c h h a v eh i g h t h r o u g h p u t a n dc a l l r e c o n f i g u r ec o d e c - p a r a m e t e r a c c o r d i n gt ot h ec h a n n e lc h a n g e si nu s e 2 a c c o r d i n gt ot h er e q u i r eo fp e r f o r m a n c ei nd i f f e r e n te n g i n e e r i n ga p p l i c a t i o n ，u s i n gt w o k i n d so fs t r a t e g yi m p l e m e n tr se n c o d e r d e c o d e r , i no r d e rt oo p t i m i z ec o m p r o m i s eb e t w e e n d e c o d i n gd e l a ya n dr e s o u r c ec o m p l e x i t y 3 a c c o m p l i s ht h e t u r b o c o m p o n e n t e n c o d e ri nf i xp a r a m e t e r su s i n gr e c u r s i v e c o n v o l u t i o nc o d e ，i n t e d e a v e lp u n c t u r i n gm o d e l ，a n dm a p ( m a x i m u map o s t e r i o r i ) d e c o d e r k e y w o r d s ： r e e d s o l o m o nc o d e e u c l i da l g o r i t h mt u r b oc o d e s o f t - o u t p u ti t e r a f i v ed e c o d i n g m a p a l g o r i t h m v h d l 创新性声明 本人声明所呈交的论文是我个人在导师指导下进行的研究工作及取得的研究成果。 尽我所知，除了文中特别加以标注和致谢中所罗列的内容以外，论文中不包含其他人已 经发表或撰写过的研究成果；也不包含为获得西安电子科技大学或其它教育机构的学位 或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作 了明确的说明并表示了谢意。 申请学 本人签名 有不实之处，本人承担一切相关责任。 只期如o ；，7 关于论文使用授权的说明 本人完全了解西安电子科技大学有关保留和使用学位论文的规定，即：研究( e 在校 攻读学位期间论文工作的知识产权单位属西安电子科技大学。本人保证毕业离校后，致 表论文或使用论文工作成果时署名单位仍然为西安电子科技大学。学校有权保留送交沦 文的复印件，允许查阅和借阅论文；学校可以公布论文的全部或部分内容，呵以允许采 用影印、缩印或其它复制手段保存论文。( 保密的论文在解密后遵守此规定) 本人签名：圣兰丝 导师签名 互丞拯 ， 嘲型! 丛2 i 期坦；! ：f i 第一章绪论 第一章绪论 本章介绍了通信系统的组成与信道编码发展历程。阐述了r s 码和t u r b o 码的 提出和研究现状，应用和有待研究的问题，给出了本文的主要内容和取得的结果。 1 1s h a n n o n 信道编码定理与纠错码的发展 通信的目的是要把对方不知道的消息及时可靠地( 有时还需秘密地) 传送给对 方2 1 ，因此要求一个通信系统传输消息必须可靠且尽可能高的速率传输：在数字 通信系统中可靠性与有效性往往是一对矛盾。若要求很高的有效性，则必然使得每 个数据码元所占的时间缩短、波形变窄、能量减少，从而在受到干扰后产生错误的 可能性增加，传送消息的可靠性减低。若要求可靠，则使得传送消息的速率变慢。 因此，如何较合理地解决可靠性与速度这一对矛盾，是正确设计一个通信系统关键 问题之一。通信理论本身也正是在解决这一对矛盾中不断发展起来的。 1 9 4 8 年s h a n n o n 在他的开创性论文“通信的数学理论”中，首次阐明了在有 扰信道中实现可靠通信的方法，提出了著名的有扰信道编码定理，奠定了纠错码的 基石。 s h a n n o n 信道编码定理： 1 r c ，不存在有编码方法实现满足尸b 要求的速率为r 的传信。 s h a n n o n 证明码长n 足够大时，随机选择的码以很高概率为好码。 其中c 是信道容量，r 是码率，高斯白噪声信道的信道容量c 的计算方法如式： d c - 纠o g ，( 9 21 + 蒜x 加“d 式中，矽是信道所提供的带宽，b = e s t 是信号功率，b 是信号能量，r 是分 组信号的持续时问即信号宽度，只是单位频带的信号功率，m 是单位频带的噪声 功率，只( w n o ) 是信噪比。 s h a n n o n 对于通信理论的贡献具体表现在m 】：把任何一个数字通信系统抽象为 图1 l 的基本框图：成功地定义了信息量的概念；启发式地证明了几个编码定理。 图1 1 中的信源( i n f o r m a t i o ns o u r c e ) 随机地产生消息( m e s s a g e ) 一般用消息的统 r s 码及t u r b o 码应用与硬件实现的研究 计特性来刻画信源；发射机( t r a n s m i t t e r ) 完成由消息变换为信号( s i g n a l ) 的功能， 是一个广义的编码器；由于有噪声源( n o i s es o u s e ) 的存在，接收信号( r e c e i v e d 葫鳓1 ) 会有不同程度上的畸变，这种畸变是由信道的物理特性和噪声源的统计特性 确定的，一般用条件概率转移矩阵或条件概率密度来刻画；接收机( r e c e i v e r ) 试图 从接收信号恢复正确的消息，是一个广义的译码器；这个估计的消息最终送给了信 宿( d e s t i n a t i o n ) 。s h a n n o n 同时指出了任意给定信道都有一个固有的量，称之为信 道容量。只要信息的传输速率低于信道容量，总可以找到一种编码方法，使得差错 概率任意的小：反之，如果信息的传输速率超过信道容量，则不存在这样的编码方 法。这就是著名的信道编码定理。信道编码定理表明，信道容量正好等于信息传输 速率的上确界。 信源发射机接收机信宿 噪声源 图i i 通信系统的组成 我们以加性白高斯噪声( a w g n ，a d d i t i v ew h i t eg a u s s i a nn o i s e ) 信道为例来说 明信道编码定理。 设信息传输速率为r 比特信道符号，则单位比特所用能量为瓯= p r 。记高 斯噪声的单边功率谱密度为0 ，则0 = 2 0 2 ，贝) | s n r = 2 r 急- 容量曲线如图1 2 。 嚣一章绪论 c 珀u s a i a n n o t n s b p s kf u 担 。 y 一。一一一 ! 驴 ， 图1 2 理想a w g n 信逆的容晕曲线 从图1 2 可以看出，e h n 。0 0 d b 时，信道容量c 0 5 。s h a n n o n 信道编码 定理指出存在速率r = o 5 的编码方案，只要毛，0 = 0 0 就可以达到“可靠”通 信。所谓“可靠”，一般是用误比特率( b i t e r r o r - r a t e ) b e r 来度量的。尽管实际的 通信系统对b e r 的要求有差别，理论的“可靠”通信一般以b e r 1 0 。1 0 。来 衡量。从图1 2 还可以看出，与不编码( r = 1 0 ) 的b p s k 调制相比较，s h a n n o n 信道编码定理指出了编码可以节省能量达9 6 d b 。如果采用1 2 的编码，利用b p s k 信号在理论上可以达到0 2 d b 。由于b p s k 在工程实现上简单，因而当信息速率较 低，例如( r 0 5 比特信道符号) ，采用b p s k 调制足够了。 s h a n n o n 编码定理以后h a m m i n g 、s l e p i a n 、p r a n g e 等人在5 0 年代初，根据 s h a n n o n 的思想，给出了一系歹设计好码和有效译码的方法。纠错码越来越受到大 家的重视，同时无论在理论还是实际中都得到了飞速发展。 纠错码的主要发展过程大致分以下几个阶段 4 。 5 0 年代至6 0 年代初，主要研究各种有效的编、译码方法，奠定了线性分组码 的理论基础；提出了b c h 编码、译码方法以及卷积码的序列译码；给出了纠错码 的基本码限；还出版了纠错码的第一本专著。 6 0 年代至7 0 年代初，这是纠错码发展过程中最为活跃的时期。提出了如门限 译码、迭代译码、软判决译码和卷积码的v i t e r b i 译码等有效的编译码方法：同时 注意到了纠错码实用化的问题讨论了如码重量分布、译码错误概率和不可检错 误概率的计算、信道的模型化等与实用化有关的各种问题。 7 0 年代以来，纠错码在实际应用中得到了更大的发展。大规模集成电路和微 4 r s 码及t u r b o 码应用与硬件实现的研究 的迅速发展，为纠错码的实用打下了坚实的物质基础。7 0 年代末、8 0 年代初( 2 0 世纪) ，g u n g e r b o e e k 把编码与调制相结合提出了网格编码调制( t c m t r e l l i s - c o d e d m o d u l a t i o n ) 技术【4 】是编码理论的又一重要里程碑。继t c m 之后，1 9 9 3 年c 。b e r r o u ， a g l a v i e u x 和p t h i t i m a j s h i m a 发现的t u r b o 码【1 8 1 是又一重大突破。 1 。2r s 码和t u r b o 码背景知识 r s 码是一种分组码【i6 j ，是i s r e e d 和g s o l o m o n 在1 9 6 0 年发现的。同年， r c b o s e 和d k r a y - c h a u d h u r i 独立于a h o c q u e n g h e m ( 1 9 5 9 年) 发现了b c h 码。1 9 7 0 年，v d g o p p a 发现了o o p p a 码。1 9 8 2 年，m a i s f a s m a n ，s g v l 6 d u t 和t z i n k 发现了代数几何码。从b c h 码，r s 码，g o p p a 码到代数几何码的 发展过程中，g v 限( o i l b e r t - v a r s h a m o v eb o u n d ) 起着不可忽略的作用。g v 限是由 e n g i l b e r t ( 1 9 5 2 ) 和r r v a r s h a m o v ( 1 9 5 7 ) 独立发现的。假定我们在有限 域上考虑问题，给定一组非负整数n k ，d ，只要g ”+ r ；1i ( g 一1 ) 。，就可 以构造一个码长为订，维数为七、最小h a m m i n g 距离至少为召的g 无线性分组码。 这就是g v 限，其证明以及有关线性分组码的基本术语、概念可以在编码理论的基 础教材中找到。记归一化的最小h a m m i n g 距离为占= d n ，编码速率( 对于线性分 组码而言) r = k n 。渐近的g v 限表明订斗0 0 时，存在线性分组码，使得占和矗 均严格大于0 。渐近的g v 限是衡量某类分组码“好坏”的一个标准。已经证明 h a m m i n g 码、r m 码、b c h 码等大部分已知的码都是渐近坏码。在分组码的理论研 究中，i 毽码扮演着重要的角色。r s 码是有限域c 上的极大距离可分( m d s ， m a x i m u md i s t a n c es e p a r a b l e ) 码，具有参数 h ，k ，疗一七l ，达到了s i n g l e t o n 限 d s n k 十l ，从这个意义上讲，r s 码是最佳的。r s 码的一个码字可以看作是某个 多项式( 取自一个特定的多项式集合) 在一个特定的点集( 含于冗) 上的值。1 9 6 1 年，d c g r e e n s t e i n 和n z i e g l e r 4 注意到r s 码是一类特殊的b c h 码，其位置域 和符号域是同一个域。另一方面，一个给定的b c h 码总可以看成某个r s 码的子域 子码。 r s 码是迄今为止所发现的一类很好的线性纠错码类【2 】，它的纠错能力强，特别 在短的和中等码长下，其性能很接近于理论值，并且构造方便，编码简单，编译码 设备也不太复杂。正是由于该码的超强纠错能力及各种成熟、可用、有效的译码算 法，因此在工程中在移动通信、卫星通信、微波传输、d v b ，以及计算机存储系统 等中都有着非常广泛的应用。特别是r s 码和卷积码构成的级联码，已经被用在深空 通信的下行链路中。另外r s 码也应用在保密通信中。 s h a n n o n 理论证明，随机码是好码，但是它的译码却太复杂。因此，多少年来 随机编码理论一直是作为分析与证明编码定理的主要方法，而如何在构造码上发挥 第一章绪论 作用却并未引起人们的足够重视。直到1 9 9 3 年，t u r b o 码的发现，才较好地解决了 这一问题，为s h a n n o n 随机码理论的应用研究奠定了基础。 t u r b o 码【1 8 1 ，又称并行级连卷积码( p c c c ) ，是由c b c r r o u 等在i c c 9 3 会议上 提出的。它巧妙地将卷积码和随机交织器结合在一起实现了随机编码的思想，同 时，采用软输出迭代译码来逼近最大似然译码。文【2 5 】中的模拟结果表明，如果采 用大小为6 5 5 3 5 的随机交织器并且进行1 8 次迭代，则在e 虬o 7 d b 时，码率 为1 2 的t u r b o 码在a w g n 信道上的误比特率( b e r ) 1 0 ，逼近s h a n n o n 限的 性能( i 2 码率的s h a n n o n 限是0 d b ) 。因此，这一超乎寻常的优异性能，立即引起 信息与编码理论界的轰动。 由于上述的良好的性能并不是理论的结果，而是计算机的仿真结果，因此t u r b o 码的理论基础还不完善。人们通过大量的模拟、仿真表明，t u r b o 码的确具有相当 优异的性能。因此，t u r b o 码的发现，标志着信道编码理论与技术的研究进入了一 个崭新的阶段。 关于t u r b o 码的发现和发展历程，c b e r r o u 等在文 1 9 】中给出了详细的说明。 因为c b e r r o u 主要从事的是通信集成电路的研究，所以他们将s o v a 译码器看作 是“信噪比放大器”，从而将电子放大器中的负反馈技术应用于串行级联的软输出译 码器，并且为了使两个译码器工作于相同的时钟，以简化时钟电路设计，就提出了 并行级联方式，这导致了t u r b o 码的发明。 尽管目前对t u r b o 码的作用机制尚不十分清楚，对迭代译码算法的性能还缺乏 有效的理论解释，但它无疑为最终达到s h a n n o n 信道容量开辟了一条新的途径，其 原理思想在相关研究领域中具有广阔的应用前景。目前，t u r b o 码被看作是1 9 8 2 年 t c m 技术问世以来，信道编码理论与技术研究上所取得的最伟大的技术成就，具有 里程碑的意义。 t u r b o 码就目前而言，从出现到发展已经有了9 年多的历程。许多科学家都在 研究t u r b o 码的理论依据取得了许多成果1 2 2 1 1 2 3 2 4 1 1 2 s 。t u r b o 码已经有了很大的发 展。在各方面也都走向了实际应用阶段。在t u r b o 码的应用研究中，t u r b o 码已被 美国空间数据系统顾问委员会作为深空通信的标准同时它也被确定为第三代移动 通信系统( i m t - 2 0 0 0 ) 的信道编码方案之一，其中，具有代表性的3 g p p 的w c d m a 、 c d m a 2 0 0 0 和我国的t d s c d m a 三个标准中的信道编码方案都使用了t u r b o 码， 用于高速率、高质量的通信业务，第三代移动通信标准的实施为t u r b o 码的研究提 供了重要的应用背景；与t u r b o 码相结合的t c m 技术也在实际中有了很大的应用。 同时，迭代译码的思想已作为“t u r b o 原理”而广泛用于编码、调制、信号检测等 领域。 1 3 本文的主要工作及内容安排 6 r s 码及t u r b o 码应用与硬件实现的研究 本文主要结合国家自然基金项目“迭代软译码中几个关键理论问题的研究”和 一个与军方合作的横向项目，对r s 码和t u r b o 码实际应用中的不同译码算法的如 何在i c 电路硬件上实现进行了研究，分析了不同译码算法和不同的实现羡略对硬件 实现成本，性能产生了哪些影响。主要内容安排如下： l 。第二章详细论述了r s 码的编译码原理及算法，重点讨论了代数译码算法的 流程及一些关键问题并且比较了各种算法的复杂度。 2 在第三章中给出r s 码编译码器在f p g a 上具体的实现描述，同时讨论了采 用不同实现策略对硬件成本与性能的影响。 3 第四章中给出t u r b o 码的编译码原理、t u r b o 码的迭代m a p 译码算法及其纠 错性能与实现复杂性的分析。 4 第五章主要对t u r b o 码的编码器，交织器迭代m a p 译码算法硬件实现过程 中所遇的关键问题做出详细的讨论。 5 最后是对本文的总结。 第二章r s 码的编译码原理与算法 第二章r s 码的编译码原理与算法 了 r s 码是一类具有非常良好性质的最大距离可分码。在工程中被广泛应用。本 章讨论了关于r s 码的一些基本概念，编译码原理，详细论述了r s 码的各种代数译 码算法，并对几种译码算法的复杂度做了分析比较。 2 1 概述 r s 码全称r e e d s o l o m o n 码1 1 6 | ，是i s r e e d 和g s o l o m o n 在1 9 6 0 年发现的。 同年，博斯( r c b o s e ) 和雷一查得胡里( d k r a y - c h a u d h u r i ) 独立于霍昆格姆 ( a h o c q u e n g h e m ) ( 1 9 5 9 年) 提出了纠正多个随机错误的循环码一b c h 码的构造 方法。1 9 6 1 年d c g o r e n s t c i n 和n z i e r l e r 注意到r s 码是一类特殊的n 2 t t 码， 其位置域和符号域是同个域。另一方面，一个给定的b c h 码总可以看成某个r s 码 的子域子码。因此，本章所讨论的内容同样适用于b c h 码。 r s 码是理解o o p p a 码、代数几何码的非常好的例子，而且r s 码的纠错能力， 尤其是纠突发错误的能力强，被广泛应用在工程实践中。所以，研究r s 码的译码 问题无论对于编码理论还是对于工程应用都具有深刻的意义。1 9 6 0 年彼得逊 ( p e t e r s o n ) 从理论上解决了二进制b c h 码的译码算法 2 】。奠定了i c h 码译码的理论 基础。稍后，格林斯坦( c o r e n s t e n ) 和齐勒尔( z i e r l e r ) 把它推广到多进制，该算 法需要求矩阵的逆，译码比较复杂，但理论很直观，易理解。1 9 6 6 年。伯利坎普 ( b e r l e k a m p ) 利用迭代译码算法译b c h ，由于它不需要求解矩阵的逆，从而大大加快 了译码速度，从实际上解决了b c h 码e 4 译码问题。随后。，l m a s s e y ( 1 9 6 9 ) 从序 列综合的角度重新推导了b c r l c k a m p 算法，因而，人们称该方法为b e r l e k a m p - m a s s e y 算法( 蹦算法) 。1 9 7 5 年，y ，s u g i y a m a ，m k a s a h a r a 等指出了译码的关键方程n - i n 欧 几里得( e u c l i d ) 算法求解。这些算法的一个共同特征是，首先利用接收矢量( 可 以称之为时域向量) 计算出变换域矢量( 相应地，称为频域向量) 或者其某些分量 ( 这些特定的分量又称伴随式序列) ，然后建立错误位置多项式满足的关键方程并求 解。因此我们称这类算法为伴随式译码算法。伴随式译码算法由于理解比较直观， 译码复杂度满足实用化，所以在远方面的研究成果也最为详尽，分析的也最为透彻。 除了这几种译码算法以外，还有象w e l c h - b e r l e k a m p 译码算法等的其它一些算法。 这里就不再举例了。 2 2r s 码的基本概念【2 】 由于r s 码可以看作是b c h 码的一种特例，所以我们首先给出b c h 码的有关 r s 码及t u r 8 0 码应用与硬件实现的研究 概念。 定义2 2 1 给定任一有限域o r ( c d 及其扩域g f ( q “) ，其中q 是素数或素数的幂， m 为某一正整数。若码元取自g f ( c ok 的一循环码，它的生成多项式g ( x ) 的根集合r 中含有以下6 1 个连续根：r ： 口“，口m u + l ，2 “”) 时，则由g ( x ) 生成的循 环码称为q 进制b c h 码。 设m i ( x ) 和e i ( x ) 分别为t “( i = o ，l ，2 ，6 2 ) 元素的最小多项式和级，根 据循环码的生成多项式的性质，可知b c h 码的生成多项式和码长分别为： g ( x ) = l c m ( m o ( x ) ，l n i ，一2 ) ( 2 1 ) n = l c m ( e o e 1 ，e 5 2 ) ( 2 2 ) 如果生成多项式g ( x ) 的根中，有一个g f ( q m ) 的本原域元素，则n = q m _ 1 ，称这 种码长为n _ q 1 的b c h 码为本原b c h 码。否则称非本原b c h 码。 下面我们从b c h 码的角度定义r s 码的概念。 定义2 2 2 ：g h q ) ( q 2 ) 上，码长n = q - 1 的本原b c h 码称为r s 码。 由定义可知，r s 码最主要特点之一是码元取自g f ( q ) 上，而它的生成多项式的 根也在g f ( q ) 上，所以r s 码是码元的符号域和根域一致的b c h 码。 设a 是有限域g f 的一个n 阶元素，其中q = p m , p 是该域的特征。因为： 算一一1 = 丌o 一口) ，o r , 的最小多项式m f ( x ) = x - d ，所以长为n = q 1 ，设计距离 为6 的r s 鹳：摸生成多项式为： g = 0 一矿) 0 一驴“) e 一矿一)( 2 3 ) 通常情况下取m o = l ，此时 2 _ g ( x ) = ( x - a x x 一口2 ) ( x - a2 ) = g j ( 2 4 ) ，t 0 但取不同的m o 值，可以有不同的生成多项式，可以形成不同的结构的编码器，其复 杂度也不一样。详细讨论可以参照下节的编码器实现。 由该生成多项式可以构造出一个q 进制的 q - 1 ，q - 6 r s 码，有最d 、雁离为6 。 由于线性码的最大可能的最小距离是校验元的个数加1 ，而r s 码恰好做到了这一点， 因此，称r s 码为极大最小距离可分码，简称m d s 码。显然，r s 码的设计距离6 与 实际距离d 是致的 一个码的纠错能力，完全由它的最小汉明距离d 决定，而r s 码的d 则完全由 生成多项式的根所决定的。根据b c h 限可知，r s 码的最小距离矽。就是6 。对于参 数为i n , k ，d 的本原r s 码，其符号域为g f ( p ) ，p = 2 。在该域上，码长n = g - i ，即每 个码字有i 1 个符号，每个符号用m 个比特表示。信息位为k 个符号校验位是n k 个符号。该码最多可以纠正【n k ) t 21 个符号错误，或可以纠正( n k ) 个符号删除。 由于现在计算机的字长均为8 的整数倍，因此在实际工程中应用的r s 码大部分是在 g f ( 2 8 ) 或g f ( 2 。) 上，这样容易被计算机处理。如在深空通信中c c s d s 所采用的标准 第二章r s 码的编译码原理与算法 9 级联码中外码r s ( 2 5 5 ，2 2 3 ) 即为g f ( 2 8 ) 上：在计算机存储系统中，其经常采用 的纠错码，如s e c d e d s b e d ，或s b e c d b e d ，其符号域为g f ( 2 1 ) 和g f ( 2 8 ) 两种符号域。 同时，关于r s 码编译码器的产品也绝大多数在g f ( 2 8 ) 域上的。 2 3r s 码的编码原理 r s 码的编码原理及编码器的实现比较简单，而译码则相对复杂一些。以下分 别讨论三种编码方式。 1 r s 码的时域编码 1 ) 定义：g f ( 0 3 ( q - 2 ”) 上，码长n ；q l 的本原b c h 码称为r s 码。它的码元和生 成多项式的根都在o f ( q ) 上，即它是符号域和根域一致的b c h 码。若a 是g f ( q ) 上 的本原元素，因为： ，- l = 兀( x - - g f 。) 口。 6 f ( q ) ( 2 - 5 ) 旺的最小多项式m ，( x ) = x - d ，所以长为n = q - 1 ，设计距离为6 的r s 码，由b c h 码的 定义可知，其生成多项式为： g ( z ) = ( 工一口肌) ( x 一口“) ( x 一口 。+ 6 2 )( 2 - 6 ) 其中m 。是整常数，肌。不同时可构成不同的生成多项式，合理地选择刖。的值，可以 降低编译码电路的复杂度。通常情况下，我们选m o ；l 。此时 a g ( 曲= ( x - a ) ( x 一口2 ) ( x 一口“) = 岳x j = 0 ( 2 - 7 ) 设g f ( 2 ) 上的k 个数据符号为d = d o ，刃露表示威多项式为： 俐= d 0 + d t x + + 矗b “( 2 8 ) 最简单的编码是利用乘法电路，直接与生成多项式相乘，得到码多项式 c 倒= d 倒g 俐，但这样编出的码是非系统码，因此在解码时，要先将信息码从接收码 中选出。非系统码的编译码效率明显低于系统码，实际的应用中都是采用系统码。 r s 码还可以用一个比特作为删除指示( e r a s u r ei n d i c a t o r ) ，指明接收符号时错误 的，r s ( n ，k ) 码可以纠正( n i k ) 个删除。若它纠正个错误即个删除，则有：合理的加以 分配可以获得不同的纠错能力。 2 ) 基于多项式除法的编码器 同样对于g f ( 2 ) 上的k 个数据符号( 矢量表示) ：d = ，砺，d l ，靠设校验位 矢量p = 加o , p t 。p 2 , - f f ，则码矢量( 系统码) c = c o ，e l ，c n i m f p o ，p o , p l 一p 2 t - id o ，d l 靠 ( 2 - 9 ) 表示威多项式： 1 0 r s 码及t u r b o 码应用与硬件实现的研究 c 叩甜+ ，嘏j( 2 1 0 ) 其中p 甜= 俐嘶w ，即g ( x ) 除x “。kd ( x ) 后的余式，记为： p ( 工) = ：1 p l x 。 ( 2 - 1 1 ) 它是o f ( 2 ”) 上的多项式阶数 = 2 t - i ，可知p 。就是校验位。 这样编码过程分为三步： 1 ) 预乘：删 2 j 由除法电路求p 似 3 ) 得到c 叩似+ 刑 其中步骤2 ) 需要km - k ) 个o f ( 2 ) 上的乘法运算。 编码结构的复杂性取决于所用的乘法器，对于并行乘法器，电路复杂度为0 ( m 2 t ) ，若 采用b e r l e k a m p s 比特串行对偶基乘法器，电路复杂度可降为0 ( m t ) ，利用三角基得到 的电路复杂度与此相当。 2 r s 码的频域编码 设a 是g f ( q ) 上的本原域元素m k q ，m k - 2 ，m i ，m o 是信息元，m i o f ( q ) ， 0 - - i l 嘶，吁，而盼都是g f “) 上的元素。 定义：算。= i 掣7 一 d = f = k - 1 = a t 4 寸o = j = n - k - 1 驴币谚击而o i k - 1 v ，= 兀 ”。“。一a ”。) 0 s _ ，n - k - 1 0 掣s 一i ( 2 一1 6 ) ( 2 - 1 7 ) 对于系统r s 码，校验矢量p = 0 o , p l 概毒j 有：p = da ，其中d 是信息位矢量，而 历为：n = 乏= 一4 ，= v ，：= ：j 毛 ( 2 i s ) t ，i 因为需要求逆，所以此方法用到更多的域运算。但是它可以采用s y s t o l i c 阵列结构 实现。s y s t o l i c 阵列是由相对简单的处理单元互连两成的处理阵列，所有的处理单元 同步执行相对简单的操作输入数据在单元间按节拍流过，处理结果从输出单元输 出。s y s t o l i c 这个词我们也译为脉动阵。 c a u c h y 编码器的另一个特性就是采用不同的冗余( r 个校验位) 时，很容易重 新配置，对于任意的r i - - - - t ，只需令最后的f ，个单元的开关置于a 即可，再按照要求 的冗余值初始化常数c 和y ，。 2 4r s 码的译码原理 r s 码的译码与其它的线性分组码的译码步骤相同，基本上分为三步：第一步是 由接收到的r ( x ) 计算出伴随式s ；第二步由伴随式找出错误图样童( ，) ：第三步由 月( x ) 一应o ) 得到最可能发送的码字6 扛) 完成译码。而根据r s 码的特点，有几种译码 效率更高的专门译r s 码的译码算法出现。下面就简要介绍这几种算法。 1 p e t e r s o n - g o r e n s t e i n z i e r l e r 算法 1 2 r s 码及t u r b o 码应用与硬件实现的研究 i e s , = e + i = 1 ，d - i ，称为伴随式序列。换言之，伴随式序列是错误谱向 ， 量的d 一1 个连续分量。由e ，= r , x l ，b ，b + d 一2 可以得到 ，- f x ? x ： i “x y 峪r 1x r l x ? p 卜 摊h 引 纠 f “2 j 【ij 【以一。j 我们希望从这d 一1 个方程求出2 r ( f 时，m ( v ) 的行列式的值d e t ( m ( v ) ) = 0 。 当v = f 时，d e t ( m ( v ) ) 0 ，即m ( 可逆。 2 b e r l e k a m p - m a s s e y 算法 1 1 由式( 2 2 ) 。假如我们已知错误位簧多项式的系数，我们可以得到如下的递推关 系 s ，= 一人1 s ，一i a2 s ，一2 一一人。s j - ，j = f + l ，2 t ( 2 - 2 5 ) 因而现在的问题是，已知d 一1 个伴随式s ，- ，= 1 ，d 一1 ，即错误谱序列的连续的 d 一1 个分量e ，j = b ，b + d 一2 ，设计一个如图2 - 2 所示的线性反馈移位寄存器 要求连接多项式a ( x ) = 1 + 人。x + a ：x 2 + + a ，一的次数尽可能的低，或者要求寄存 器长度最短。 一个线性反馈移位寄存器由寄存器长度工与连接多项式人( x ) 唯一确定。我们可 以把一个线性移位寄存器表示为( 厶a ( x ) ) 。b e r l e k a m p - m a s s e y 算法是迭代算法，具 体描述如下：设s ，s ：，s 。是任意域上的d 一1 个元素，线性反馈移位寄存器 ( 工，a c 一0 ) ) 是生成s ，是，s ，的一个最短线性反馈移位寄存器。假定我们已经构造 了( 厶，a ( 1 ( 功) ，( 2 ，a ( 2 ( x ) ) ，( h ，人( ( x ) ) 。b e ( 1 e k a m p - m a s s e y 算法给 出了利用已有的最短线性反馈移位寄存器构造新的最短线性反馈移位寄存器 ( 工，人 叶 ) ) 的方法，即有下面的定理 定理2 2 5 】( b e r l e k a m p m a s s e 算法) ：设s i ，s 2 ，咒一l 是给定的域元素。利用 初始条件人( 。( 算) = 1 ，b o ( x ) = 1 ，l 。= 0 以及如下的递推关系，可以求出a “( x ) ： a ，= 衅”s ， 上，= t ( ，一l ，一1 ) + ( 1 一t ) 上，一1 ( 2 - 2 6 ) 瞄翻= 去( 1 “- 8 , 订箸翱，浏一k 4时矿叫啊) j r = l , - - , d - 1 , 其中= 冀孟r 。且2 工，_ 1 r 一1 则a ( “1 ( 工) 是具有性质a 护1 = 1 及吖“s 。= o ，r = l 一+ 1 ，d 一1 的次数最低 的多项式。 3 ，欧几里得算法 从上面的讨论可以看出，r s 码的译码问题可以表述为： 已知伴随式多项式s x ) ，求多项式q x ) ，a ( x ) ，使得 f l ( x ) = s ) a ( 曲( m o d x “1 ) ， 1 4 r s 码及t u r b 0 码应用与硬件实现的研究 d e g q ( x ) d e g a ( x ) l 【d s ) 2 j ( 2 2 7 ) 这就是伴随式译码的关键方程。把b e r l e k a m p m a s s e y 算法稍加修改，可以同时求出 多项式q ( x ) ，a ( x ) 。这个方程也可以用欧几里得算法求解 5 】【3 1 。 定理2 t 4 【5 】( 欧几里得算法) ：设，( x ) = x d - i , t c o ) ( 工) = s ( x ) ，a 旧( z ) = j ：? ， 按下面的公式递推， 叭加j 嘏f 濠莉刚b ) 脯) ， a ( r “( x ) = i ? 一g j ，( 工) 】a p ( 工) - ；：高 = 0 一q ：，。x ) ；：= 蓦 占- 2 s ， - - i jd e g t ”( x ) 一 图3 5时序关系图 3 3r s 编码器的设计实现 在第二章中我们介绍了除法器结构的编码器，频域编码器和s y s t o l i c 结构的编 码器已经知道，s y s t o l i c 阵列结构的编码器避免了全局信号嘲，每个处理单元仅和 与之相邻的单元相连，数据在处理单元之间脉动地流过，事实上包括时钟信号也是 脉动地传递的，但是每个处理单元的运算非常复杂，要进行变系数的有限域乘法和 除法，而有限域的乘法和除法比加法和常系数乘法复杂得多用f p g a 实现是要占 用较多得硬件资源，同时也降低了吞吐率。而除法器结构的编码器只用到了常系数 乘法器。而常系数乘法器的硬件实现非常简单，占用的硬件资源也较少。除法器结 构的编码器的缺点是存在全局信号，而f p g a 器件中有专门设置得时钟网络和长线 资源，信号在时钟网络和长线上传播时发生的畸变和抖动最小，从而使得全局信号 的问题并不突出，另外，除法器结构可以方便地实现带交织的r s 编码器，而采用 s y