（通信与信息系统专业论文）基于卫星通信的高速纠错码研究及其fpga实现.pdf

摘要 卫星通信经过半个多世纪的发展，已逐渐成为远距离通信、军事通信乃至个 人通信等的重要手段。纠错码技术作为其中保证信息正确传输的有效手段，经历 了从卷积码到r s 码、t u r b o 码和l d p c 码，逐渐发展，联合应用的过程。 传统的r s 码由于其纠错能力强，构造方便，编码简单，是卫星通信中常用纠 错码之一，c c s d s 标准的r s ( 2 5 5 ，2 2 3 ) 码应用尤为广泛。随着卫星通信对数据 速率越来越高的要求，本文结合采用全局反向时钟，并且通过对乘法器的改进， 在不增加硬件资源消耗的情况下，设计了一种高速的r s 编译码器，编码数据吞吐 量可达4 4 8 g b p s ，译码数据吞吐量可达2 9 6 g b p s 。 另一方面，可逼近香农限性能的低密度奇偶校验码( l d p c ) 是已成为卫星通 信中的热点研究问题，最新的c c s d s 、d v b s 2 等相关卫星标准都采用l d p c ， 其中d v b - s 2l d p c 码由于其码字长、码率多，不易于硬件实现。本文针对d v b s 2 l d p c 码庞大的资源消耗和较低的数据吞吐量进行分析，在尽量不影响其性能的前 提下，设计了一种基于最小和算法的高速译码器的f p g a 实现方案。该方案采用 1 8 0 路并行，6 b i t 位宽，2 0 次迭代，在降低资源消耗量的同时，最高可支持2 0 8 9 m h z 的时钟，数据吞吐量可达3 4 0 m b p s 。论文基于x i l i n xs c s v s x 9 5 t 芯片，通过开发 板下载测试，验证了其优越性。另外，该译码器方案还可以兼容其它第二代d v b 标准。 关键字：卫星通信d v b s 2 纠错码r s 码l d p c 码f p g a a b s 仃a c t a f t e rt h ed e v e l o p m e n to fm o r et h a nh a l fac e n t u r y , s a t e l l i t ec o m m u n i c a t i o nh a s g r a d u a l l yb e c o m ea ni m p o r t a n ts c h e m ef o rm a n ya p p l i c a t i o n s ，i n c l u d i n gl o n gd i s t a n c e c o m m u n i c a t i o n s ，m i l i t a r yc o m m u n i c a t i o n s a n dp e r s o n a lc o m m u n i c a t i o n s a sa n e f f e c t i v et e c h n o l o g yw h i c hg u a r a n t e e st h er e l i a b l et r a n s m i s s i o n , e c co 三r r o rc o r r e c t c o d e ) h a sb e e nd e v e l o p e df r o mt h ec o n v o l u t i o nc o d et or sc o d e ，t u r b oc o d ea n d u ) p cc o d e ，a n dt o w a r dc o d ec o m b i n a t i o n f o ri t ss t r o n ge r r o rc o r r e c t i o na b i l i t y , c o n v e n i e n tc o n s t r u c t i o na n ds i m p l ee n c o d i n g ， c o n v e n t i o n a lr s ( r e e ds o l o m o n ) c o d ei so n eo fe c c sc o m m o n l yu s e di ns a t e l l i t e c o m m u n i c a t i o n a m o n gv a r i o u sr sc o d e s ，r s ( 2 5 5 ，2 2 3 ) r e c o m m e n db yc c s d si s e s p e c i a l l yw i d e l yu s e d i nv i e wo ft h ed e m a n do fg r o w i n gd a t ar a t eo ft h es a t e l l i t e c o m m u n i c a t i o n s ，t h i st h e s i sd e s i g n e dah i g h - s p e e dr se n c o d e ra n dd e c o d e rb yu s i n gt h e g l o b a ll v e r s cc l o c ka n da l lm o d i f i e dm u l t i p l i e rw i t h o u tm o r eh a r d w a r er e s o u r c e s c o n s m n p t i o n r e s u l t ss h o wt h a tt h et h r o u g h p u to ft h ee n c o d e ri s4 4 8 g b p s ，a n dt h e t h r o u g h p u to ft h ed e c o d e rc a l lb eu pt o2 9 6 g b p s o nt h eo t h e rh a n d ，t h el o wd e n s i t yp a r i t yc o d e s ( l d p c ) ，w h i c hc a na p p r o x i m a t e l y r e a c ht h es h a n n o nl i m i t , h a v eb e c o m et h eh o ts p o ti ns a t e l l i t ec o m m u n i c a t i o n s ，a n dw a s w i d e l yu s e di nt h el a t e s ts a t e l l i t es t a n d a r d s ，s u c ha sc c s d s ，d v b - s 2 ，e t a 1 f o rn 砖 l d p cu s e di nd v b - s 2 i ti sd i f f i c u l tt ob er e a l i z e dd u et oi t sl o n gc o d ew o r da n dv a r i o u sc o d er a t e si n v i e wo ft h eh u g er e s o u r c ec o n s u m p t i o na n dl o wt h r o u g h p u to fd a t a , ah i g h - s p e e ap a r a l l e l l d p cd e c o d e ri sp r o p o s e df o ri t sf p g ar e a l i z a t i o nb yu s i n gt h en o r m a l i z e ds u m - r 疵a l g o r i l t m a w i t h18 0 p a r a l l e l s , 6b i tw i d t h sa n d2 0i t e r a t i o n s , f i l ed e c o d e rc 锄s u p p o r taf r e q u e n c ya st l i g h 部2 0 8 9m h za n da t h r o u g h p u to f3 4 0 m b p sa e e o r d i i l gt oo u rt e s t i n gr e s u l t si nx i l i n xs c 5 v s x 9 5 t i na d d i t i o n , t h e n e w l y - d e s i g n e dd e c o d e ri sc o m p a t i b l ew i t ho t h e rd v bs t a n d a r d s k e y w o r d s ：s a t e l l i t ec o m m u n i c a t i o n d v b - s 2e c cr sc o d el d p cf p g a 第一章绪论 第一章绪论 1 1卫星通信简介 卫星通信自2 0 世纪4 0 年代提出以来，经过长达半个多世纪的发展，已逐渐 发展成为区域通信与跨洋通信、国家基础干线通信、国际军事通信、行业及企业 专网通信乃至个人通信的重要手段，其主导思想是利用人造地球卫星作为中继站， 转发或反射空间电磁波( 称之为无线传输信道或无线接收信道) 来实现信息传输。然 而近几年来，伴随着地面高密度、。大容量光纤通信的不断发展与普及，卫星通信 一直处于低潮期。但是地面网络的覆盖范围始终是有限，且主要集中在城市地区。 时至今日，通信个体化、机动性及无缝覆盖的需求不断增加，信息全球化、互联 网、数字多媒体通信等业务不断增长，为了使通信不受地点、时间以及业务种类 的影响，卫星通信无疑是地面通信的重要延伸和补充。此外，卫星通信在应急通 信上的地位也是无可取代的。 卫星通信主要有以下几个特点：1 ) 频带宽，容量大；2 ) 兼容多种业务；3 ) 覆盖范围广，全球区域无缝隙覆盖的能力是其他任何通信方式所不具备的；4 ) 机 动性好，几乎可满足无地域，无距离，无时间限制的要求；5 ) 稳定性，可靠性好， 通信质量好；6 ) 由于卫星通信主要是利用卫星进行传输进而提供远距离、广域覆 盖的信息传输服务，解决地面通信网络覆盖不到的或稀路由业务地区的通信服务 问题，所以在卫星通信方式下可以同时实现区域通信和全球通信。 当前卫星通信的业务主要有：卫星固定通信、卫星移动通信、卫星宽带通信、 卫星电视直播数字多媒体直播四大类别。其中，高速数字卫星广播是卫星通信一 个非常重要的应用，它具有频带利用率高，传输信号质量高的优点。其标准的发 展起源于上世纪九十年代初，应用较多的制式主要有两种，即欧洲的d v b s 标准 和美国g i 公司开发的d i g i c i p h e r 标准。由于这两大标准采用了不同的数字信号传 输方式即信道编码，所以这两种方式彼此互不兼容。 d v b s 标准提供了一整套由卫星传输方式实现的数字电视系统规范。首先按 照i s o i e cm p e g 2 标准对音频及视频进行编码压缩，随后将m p e g 2 码流打包 形成传输流( t s ) ，接着进行信道编码以及数字调制，最后通过卫星进行传输，其 最高t s 流传输速率约为4 5 m b i t s 。其中，内码编码选用收缩卷积编码；调制方式 采用q p s k 。d v b s 标准在亚洲、澳洲、美国都得到了响应，我国于1 9 9 6 年采用 符合d v b s 标准的数字电视卫星广播系统，建立了广播电视数字传输技术体制。 d v b s 作为当今广播电视领域的主流卫星传输标准已有十年之久，这意味着 d v b s 的核心技术已经远远落后于当今的前沿技术，因此，基于当前的硬件水平 2基于卫星通信的高速纠错码技术研究及其f p g a 实现 技术成果，人们急需开发出更适应当前乃至未来中长期业务的标准。本着这样的 目的d v b s 2 标准出现了，它是应用于卫星宽带传输的第二代标准，其目标是在 合理的接收机复杂度条件下，实现更好的信号播送性能以及更完整的系统灵活性， 在支持更高t s 流速率的同时( 最高约为9 0 m b i t s ) ，提供比现存服务更灵活、性 能更好的服务，主要体现在以下五个方面：1 ) 自适应编码调制技术( a c m ) ；2 ) 灵 活的输入接v 1 匹配；3 ) 多选择频谱滚降系数；4 ) 高性能前向纠错系统；5 ) 灵活 高效的多码率多调制方式。 由此可见，当前卫星通信研究发展的首要目标是更强的纠错能力，更高的数 据吞吐量，更好的适应性。 1 2卫星通信中信道编码简介 众所周知，在卫星通信中需要不断地从卫星上往下传输信息数据。这一信息 传输路径称为卫星信道，它具有多径衰落、功率受限、时延大、非线性、易受环 境干扰等不良因素。这是由于为了满足的通信系统各种基本要求，卫星通信都必 须通过地球以外空间的在轨卫星来实现，通信距离非常长，因而很容易受到卫星 本身、通信路径及宇宙其它星体等因素的影响。 卫星通信具有带宽充足而功率受限的特性，那么其纠错码也应具有超强的纠 错能力，所以，为了达到节省发射机功率、提高频谱利用效率的目的，卫星通信 系统采用信道编码技术，在有限带宽和低信噪比条件下，实现信息的低误码率传 送。以未编码的q p s k 系统为例，忽略所有措施带来的富裕值，需要信噪比e b n o 值至少为1 0 6d b ，才能获得1 0 击的b e r 性能。但是，通过某种特定的级联编码、 交织、译码过程，在达到相同的误码性能的前提下，信噪比仅需2 6d b ，通过信道 编码获得了8d b 的编码增益。这也正是为什么信道纠错码技术的研究能一直成国 际关注热点的原因。 纵观纠错码理论的发展历史，大致可分为卷积码、r s 码、t u r b o 码和l d p c 码，同时还伴随着码之间的组合级联码等发展演进过程。另外在技术层面上，则 以高增益、高效率、低复杂度、低延迟为发展方向。 卷积码由e l i a s 于1 9 5 5 年提出，是继分组码之后提出的简单高效的编码方式。 上世纪七十年代，伴随着v i t e r b i 软判决译码算法迅速发展，卫星通信系统以及深 空探测装置普遍采用卷积码技术。与未编码的情况做对比，v i t e r b i 算法可以得到7 d b 的编码增益，与采用硬判决译码方式的情况做对比，v i t e r b i 软译码仍有2d b 的 额外增益。除此以外，译码性能的好坏还与选取的编码速率、编码器的整体约束 长度和截短长度等因素有关。2 0 世纪8 0 年代v s a t 卫星系统兴起之初，采用码率 为1 2 ，约束长度为7 的卷积编码，通过q p s k 调制和v i t e r b i 软判决译码，在误码 第一章绪论 率为1 0 5 时具有5d b 的编码增益。卷积码在很大程度上改变了卫星通信系统的性 能。卷积码及其译码算法为t u r b o 码、串行级联编码等优秀编码方案的提出奠定了 基础。然而卷积码并不完美，随着编码器存储长度不断增加，v i t e r b i 译码的复杂 度将呈指数上升，因而编码性能无法得到进一步的提高。 r e e 扣s o l o m o n 码( 简称r s 码) 是由里德( r e e d ) 和索洛蒙( s o l o m o n ) 应用m s 多项式于1 9 6 0 年构造出来的。它不仅是一类具有很强纠错能力的多进制b c h 码， 同时，也是一类典型的代数几何码。由于早期电路的复杂性以及集成度都较低， r s 译码难以实现以致被认为其只有学术价值；但随着大规模集成电路微处理器技 术的发展，电路复杂性和设计费用都大大降低，可供选择实现这些复杂算法的手 段也越来越多。设计者分别针对r s 码设计结构的简单高速应用【l h l l 】以及i 塔码复 杂的译码算法 1 1 - 1 3 】做了大量研究，使得r s 码可以在译码复杂度不增加的情况下， 得到更高的纠错能力和编码增益，同时不仅仅局限于纠正突发错误和随机错误， 因而被广泛地应用于各种数字通信系统和数据存储系统中，特别是在d v b 系统、 h d t v 系统、星通信等方面，已经成为一项标准的技术被采用。例如：在c c s d s ( 空间数据系统咨询委员会) 的遥测信道编码标准中，采用( 2 ，1 ，7 ) 卷积码和 r s ( 2 5 5 ，2 2 3 ) 的级联码，当误码率小于l o 击时信噪比e b n o 为2 5 3c l b ，与相同 情况下的6 4 态卷积码比较有2c l b 的增益；e t s i 的d v b s 标准及美国d b s t v 系 统均采用码率为3 4 、约束长度k = 7 的卷积码与( 2 0 4 ，1 8 8 ) 的r s 码，采用q p s k 调制方式，信噪比e b n o 为4d b 时误码性能介于1 0 d o - - 1 0 1 1 ；n a s a ( 美国航天 局) 于1 9 9 3 年发射的a c t s 卫星采用1 2 卷积码与r s 码级联编码方案，最佳误 比特性能达1 0 。1 2 ：欧洲的m e t o p 、美国e o s 、n p p n p o e s s 以及我国的遥感卫 星风云三号f y 0 3 也都采用c c s d s 标准推荐的r s 与卷积码级联的数据传输方案。 也正因为其应用如此广泛，r s 码的编译码算法一直是国际通信领域研究的热点问 题之一。 但是，当r s 码非常长时，很难实现软判决译码，编码增益的改善也因此受到 限制，且随着信息分组长度的增加，译码复杂度成指数上升。1 9 9 3 年c b e r r o u 和 i l p y n d i a n 提出“并行级联”形式的t u r b o 码。近几年对t u r b o 码的深入研究表明， t u r b o 码即使在极低信噪比下依旧可获得很高编码增益，性能接近香农极限，远优 于串行级联编码性能，这一点特别适合中等误码率需求的卫星系统。目前，t u r b o 码技术已相当成熟，被多个国际组织和机构确定为差错控制标准规范，例如， i n m a r s a t ( 国际海事卫星组织) 、i n t e l s a t ( 国际卫星通信系统组织) 、c c s d s 等。伴随着研究的进一步深入，t u r b o 码已经成为下一代卫星通信系统的核心技术 之一。美国航空航天公司在卫星通信领域，对t u r b o 码的应用方面也获得了很大成 就，t u r b o 码被直接应用于高级宽带系统、先进极高频通信卫星( a e h e l 、g p s 及 地球同步环境卫星系统( g o e s ) 。 4 基于卫星通信的高速纠错码技术研究及其f p g a 实现 由g a l l a g e r 于1 9 世纪6 0 年代首次提出的l d p c ( l o wd e n s i t yp a r i t yc h e c k ) 码是一种能够逼近香农容量限的线性分组码，并给出了高效的迭代译码算法s p a ， 但由于该算法计算复杂度高等原因，一直到2 0 世纪9 0 年代后期才逐步受到编码 界的重视。这一切的转折点正是1 9 9 5 年，m a c k a y 和n e a l 等人重新发现了l d p c 码及其译码算法，证明了就实际系统接近信道容量而言，迭代译码算法的重要性， 并且发现l d p c 码具有比t u r b o 码更优良的误码性能。以1 0 7 分组长度、二进制 输入的a w g n 信道下使用迭代译码为例，为达到1 0 。6 误码性能，需要的信噪比距 离香农极限仅o 0 4d b 。此后进行的大量研究1 2 0 m 2 6 更是从构造基础码字到译码算 法上奠定了l d p c 码的位置；同时针对特殊的i r a l d p c 码，由于其优良的性能， 研究的重剧2 8 】1 4 6 便转向如何减少其译码的实现复杂度上。正因为不断有高效的 l d p c 编译码算法出现，对于l d p c 码的研究也逐步趋于实用性层面。l d p c 码是 一种线性分组码，当分组长度很大的情况下性能接近香农极限，而且编解码简单、 时延小等特点非常适合高速信息传输系统，是未来卫星通信系统的首选信道编码 7 方案。e t s i 的第二代卫星数字广播标准d v b s 2 以及d v b c 2 、d v b t 2 就以b c h 码和l d p c 码的串行级联取代了d v b s 以往的信道编码方案。美国c o m t e c h 公司 的c d m 6 0 0 平台卫星调制解调设备采用了l d p c 码，相同调制方式和误码要求下， l d p c 码相对于t u r b o 码就有0 3 - 0 5d b 不等的编码增益。 1 3课题的主要研究内容 基于前面的描述，可见r s 码由于其优异的性能还广泛应用于现代各种数字通 信系统和数据存储系统中，同时可知，一种r s 码是否能在实际中得到应用，很大 程度上取决于其译码算法是否简单、快速、经济。此前，x i l i n x 公司和法国m a t r a m a r c o n i 公司生产过满足c c s d s 标准的r s ( 2 5 5 ，2 2 3 ) 码的译码芯片，其中， x i l i n x 公司的译码芯片的两个输入码组之间的时间间隔不小于4 0 5 个时钟周期。法 国m a t r am a r c o n 公司生产的译码芯片的最大数据通过率也不超过1 0 0 m b p s 。 另外，专利 6 2 1 中提出一种符合c c s d s 标准的高速r s 译码芯片，采用x i l i n x 公 司的x c v 6 0 0 e 6 h q 2 4 0 c 作为实现芯片，其数据通过率约为4 0 0 m b p s ，资源使用 约为1 8 万系统门。 同样，l d p c 码的适用性也大部分取决于其译码部分，针对于其算法硬件实现 的复杂度，当前的目标均重点在于性能与复杂度的均衡，及其硬件实现的可行性。 此前，g a b r i e lf a l c t op a i v af e m a n d e s 于2 010 年研究的d v b s 2l d p c 码【5 引，采用 1 8 0 的部分并行，仅取5 比特的有效信息位，在x c 2 v p l 0 0 芯片上所支持的最大时 钟频率为7 3 2 m h z ，其资源使用率为8 8 。而文献 4 5 】中提出的d v b s 2l d p c 码 的编码器，在x c 2 v p l 0 0 芯片上所支持的最大时钟频率为1 3 1 7 m h z 。 第一章绪论5 所以，减少输入码组之间的间隔时钟周期和提高译码器部分的数据通过率是 近期工程实现的迫切要求。本课题基于可配置的f p g a ，针对r s 码和l d p c 码的 广泛应用，以及各项业务对高速数字通信的广泛需求，实现了一个具有高计算密 度、高数据密度、高加吞吐量的高速r s 编译码器和高速d v b s 2l d p c 译码器， 适合卫星通信、深空通信等多方面的要求。本课题结合实际需要，从研制高速r s 编译码器和d v b s 2l d p c 码译码器的角度出发，研究r s 码和l d p c 码的编码原 理和译码算法，并在其实现结构上进行改进，从而达到高速f p g a 实现的目的。 做为课题的两方面工作，本课题的研究内容主要包括以下几个方面。 ( 1 ) 研究r s 码的编码原理和译码算法、l d p c 码的编码原理和译码算法； ( 2 ) 以高速i 峪编译码为目的，研究r s 码的编译码方式及特点； ( 3 ) 以高速和低复杂度度为目的，研究d v b s 2l d p c 码的译码方式及特点； ( 4 ) 基于f p g a 设计实现高速r s ( 2 4 4 ，2 1 2 ) 码的编译码器； ( 5 ) 基于f p g a 设计实现高速适用于d v b s 2 标准的l d p c 译码器； ( 6 ) 基于x i l i n x 芯片，对提出的方案进行下载测试。 c 1 4 本文结构安排 综合考虑r s 码和l d p c 码的特点和其现有的分析方法，本文在讨论r s 码和 l d p c 码的基本概念、校验矩阵构造方法及编译码算法的基础上，重点对r s ( 2 4 4 ， 2 1 2 ) 码及d v b - s 2l d p c 码的编译码算法及其性能分析进行了深入研究，分析对 比了不同译码算法及参数对编译码的影响，以及不同译码分析方法各自的优缺点， 并在其f p g a 实现的基础上提出了改进，在保证系统性能的基础上，不但降低了 资源利用量，还大大提高了数据吞吐量。另外，通过测试板进行下载测试，验证 了其优越性。 具体章节安排如下： 第一章绪论，介绍课题的研究背景、意义和卫星通信中纠错码技术的发展， 其中主要描述了r s 码和l d p c 码的研究现状和研究目标，最后给出了本论文的主 要研究内容和结构安排； 第二章介绍了r s 码的研究现状、研究意义以及近期的主要研究成果，并详细 描述了r s 码的编译码算法原理和现今主流的设计方法。同时针对其硬件实现中乘 法单元的重要性，介绍了有限域内乘法单元的设计。另外，分析比较了r s ( 2 5 5 ， 2 2 3 ) 码和r s ( 2 4 4 ，2 1 2 ) 码的性能； 第三章介绍了l d p c 码的历史发展、研究现状以及近期的主要研究成果，并 详细描述了l d p c 码编译码算法原理以及d v b s 2 标准中的i r a l d p c 码的构造 和编码方案。此外，还针对d v b s 2l d p c 码的软判决方法和与其它标准的兼容性 6 基于卫星通信的高速纠错码技术研究及其f p g a 实现 进行了说明； 一 第四章基于现今编译码系统的主要问题，在前文描述的算法的基础上，提出 高速的r s ( 2 4 4 ，2 1 2 ) 码和d v b s 2l d p c 码的f p g a 实现方案，并针对编译码 实现方案中比较典型的模块，进行简化，较大的减少了硬件资源消耗，提高了数 据处理速度。 第五章则针对第四章中所设计的高速的r s 编译码器和d v b s 2l d p c 译码器 方案，首先，基于m o d e l s i m 进行逻辑测试，验证编译码系统的逻辑正确性。然后 针对i s e 综合仿真以及静态时序分析，总结编译码器最小时钟周期和资源占用情 况。最后基于x i l i n x 芯片，通过v c 测试平台进行下载测试，验证所提出编译码 f p g a 实现方案的优越性。 第六章整篇论文的工作总结与展望，在回顾论文工作的基础上，总结了工作 取得的研究成果并提出了以后工作中还需深入研究的一些地方，指出了后续工作 的改进方向。 第二章r s 编译码的算法原理 7 第二章r s 编译码的算法原理 2 1r s 码的研究现状 由r e e d 和s o l o m o n 于1 9 6 0 年应用m s 多项式构造出来的r s 码是一类具有强 纠错能力的多进制b c h 码，能同时纠正随机错误和突发错误，是迄今为止所发现 的性能最好的线性纠错码之一。它构造方便，编码简单，在码长较短的情况下， 纠错能力能够接近理论值，并且具有严谨的代数结构。这些良好的特性使它的应 用非常广泛，。对于信道干扰非常复杂的通信系统更是如此。比如：r s ( 3 1 ，1 5 ) 是军事通信中的首选码；r s ( 2 5 5 ，2 2 3 ) 是深空通信中的标准码；在c d r o m 等 存储系统中也大多采用r s 码作为其纠错码；高清晰度电视( h d t v ) 系统中通常用 r s 码作为其级联码的外码。 目前，在编码器方面，文献 1 】中利用了二倍改进的流水线编码器结构，采用 了a l t e r a 公司的c y c l o n ei i i ( e p 3 c 2 5 q 2 4 0 c 8 ) ，其最大编码时钟频率为2 6 2 2 6 m h z ， 在仿真过程中，若时钟频率达到1 0 0 m h z 时，数据速率为7 3 0 m b p s 。而对于r s 的 译码器而言，则基于欧氏算法和b m 算法，出现了许多改进，比如i b m 算法，m e 算法，g a o 氏算法等，以及基于这些改进算法继续改进的p r m e 算法，r d i b m 算 法，f d c m e 算法，p r i b m 等。这些算法或在结构上，或在算法上进行了一些小的 修改，以实现在某些特定环境提高其性能的目的，如表2 1 所示。 表2 1 近几年国外r s 译码算法研究情况 同时，通过对近几年关于r s 码的专利的调查分析，对其做了相关的总结，如 表2 2 所示，详细说明了不同专利的特点。 表2 2 近几年国内外r s 专利的特点 专利特点 【5 9 】 求解关键方程后进行判断，避免错码个数超出最大纠错能力时，“越纠越错”。 8 基于卫星通信的高速纠错码技术研究及其f p g a 实现 元素的加减法采用查表法，元素直接用其指数表示。 c c s d s 标准的r s 码译码芯片，加入元素的二元域表示到复合域表示的域变换。 判断序列发生错误的类型，根据其对应关系，确定其纠错方式。 译码器直接计算信息多项式而无需计算错误图样。 采用存储器寻址方式，避免了流水线结构的冗余运算。 用一个加速的钱搜索来更快的估计一个或多个错误位置多项式。 错误值能直接计算，不需要错误值多项式的生成。 当产生错误位置多项式时，只需用到两组寄存器，节省资源。 产生多个时钟信号，钱搜索模块用一个更快的时钟信号控制。 改进的欧氏算法，t 步迭代译码过程解关键方程，不减少译码速度。 2 2 r s 编码算法 令口为伽罗华域g f ( 2 ”) 中的本原元。符号取自g f ( 2 ”) ，纠t 个错误的i 峪码 的生成多项式的形式为： b + 2 t - i3 2 g ( x ) = 兀( x - - a 可) - - e g , x 。 ( 2 1 ) j = 6 i 幂0 其中b 称为偏移量，s 称为步进因子。 注：由于缩短循环码的生成多项式与原码是相同的， 的形式。 以系统码为例，其码字的k + 1 到1 1 位是检验位，且 c ( x ) = m ( x ) x ”以+ ，( x ) 首先，令需要编码的序列为： m = ( - l 一2 ，码，m o ，) 所以不影响生成多项式 ( 2 _ 2 ) ( 2 - 3 ) 可得编码多项式为： m ( x ) = m k l x 。+ m k 一2 x 一2 + + ，x + ，( 2 - 4 ) 其中k = n 2 t 。 在系统码形式下，信息多项式x 2 m ( x ) 除以生成多项式g ( x ) 后得到的余式 厂( x ) = r 2 “x 2 卜1 + r 2 f - 2 x 2 t - 2 + r l x + r o 的系数恰好是2 t 个奇偶校验符号。即： m ( x ) x 甜= q ( x ) g ( x ) + r ( x ) ( 2 5 ) 此时，编码器输出的码字多项式为： c ( x ) = l ( x ) x 2 + r ( x ) = q ( x ) g ( x ) ( 2 6 ) 因此，r s 码的编码问题其实就是模g ( x ) 的除法问题。 注：输出的码字是信息位在前校验位在后。本章中所有的图中用到的加法器 =刁习习q刀叼u刁 陋p p p 第二章r s 编译码的算法原理 9 和乘法器均为g f 有限域加法器和乘法器，下文不再赘述。 x ) 图2 1 典型的r s 编码器结构 典型的r s 码编码器结构如图2 1 所示，每个数据进入编码器之后，都要经历 加、乘、加三步，即需要三个时钟完成，下一个数据才能输入。若考虑当输入编 码器时，每个数据不执行加法操作，直接进入n 个相乘器，同时执行与系数的相 乘操作，对来自寄存器r ( n k ) 的数据，也执行与系数的相乘操作，然后再加上之前 的数据，通过这样的改进，则每个数据进入之后，只需经历乘、加两步，只需要 两个时钟，如图2 2 所示。文献【1 】中提出，由于对偶基中加法和乘法的本质是比特 的异或计算，则乘加两步可以在一个时钟周期中完成。 图2 2 r s 编码器结构( 二) 文献【1 0 】中提出了八倍并行编码器，可将编码时间缩短为原来的1 8 。由经典 编码结构可知，由于电路中具有反馈环路结构，因此不能简单的对其进行并行八 倍处理，且通过分析可知，此方法虽然在算法上具有很大的优化性，但在具体实 现中，却需要庞大的计算量来得到更新后的多项式系数矩阵，因而并不适合硬件 实现。 而针对文献【1 0 】中的超前运算，即对应多项式系数来设计常系数乘法器，可缩 短关键路径，提高工作速度，同时减少乘法器加法器数量，减少资源消耗。另外， 乘法器是消耗面积的主要单元，若设计具有对称系数性质的r s 编码，需要的乘法 器的个数将减半，从而大大节省了硬件资源。但此两种方法只针对某一特定的r s 编码器有效，对通用的r s 编码器并不适用。 l o 基于卫星通信的高速纠错码技术研究及其f p g a 实现 2 3r s 译码算法 r s 码的译码问题，一直以来都是码理论研究者最感兴趣的课题之一。一种码 是否能在实际中得到应用，很大程度上取决于译码算法是否可以达到简单、快速、 经济和译码错误概率小的要求。因此研究r s 码的理论与实现，无论是在理论上还 是在实践上都有重要意义。 ， 首先，令发送端传输的码字多项式为： c ( x ) = c ；一l x ”1 + c 一一2 x h + q x + c o ( 2 7 ) 令接收端的接收序列多项式为： r ( x ) = ，：i i x ”- 1 + ，：，一2 x n - 2 + r l x + r o ( 2 8 ) 令差错图样多项式为： e ( x ) = e v x + p ，l x 钿+ e 2 x ，2 + q x ( 2 9 ) 其中为错误位置数，该位置的错误值为e l 。那么： 取x ) = c ( x ) + e ( 工) ( 2 - 1 0 ) r s 码的传统译码方法与一般的线性码是相同的，主要分为以下三步： 1 ) 由接收到的码字r g ) 计算伴随式s 。 2 ) 由伴随式s ( 劝确定错误图样e ( 曲。 3 ) 计算) - e = c ) ，得到译码器输出码字c ；若译码器不能得到e o ) ， 则译码失败，此时译码器指出r 中有错误，但不能纠正。 其中第2 ) 步又可以分为求错误位置多项式o ( x ) 和错误值多项式c o ( x ) 两步。伴 随式s 0 ) 和仃( x ) 以及c o ( x ) 之间应满足关键方程： s ( x ) 仃( x ) = c o ( x ) m o d x 可( 2 1 1 ) 如果不考虑纠删的问题，我们可知译码器结构具体包括伴随多项式的计算、 错误位置多项式的计算、钱搜索和错误值计算四个模块，如图2 3 所示。其中伴随 多项式计算模块生成多项式s ，它可用于关键方程求解模块用于求解关键多项式 s ( x p ( x ) = t o ( x ) m o d x 知。一般可以用m e 算法或b m 算法来解关键方程，得到错 误位置多项式仃( x ) 和错误值多项式c o ( x ) ，这两个多项式可用来得到错误位置和对 应的错误值。然后，通过钱搜索模块得到错误位置多项式的根鼍。最后，利用f o r n e y 算法，根据钱搜索模块得到的相应值，采用f o m e y 算法计算出错误值，并在译码 器的输出端进行纠错。其中，决定译码器复杂度的主要因素在求o ( x ) 。另外，f i f o 存贮器是根据这些模块的时延来缓存接收信号的。 第二章r s 编译码的算法原理 2 3 1伴随多项式计算 已知接受的数据码流为： 图2 3r s 码译码结构 r ( x ) 2 。l x ”。1 + - i - r l x l + ( 2 1 2 ) 伴随多项式计算公式如f ： 墨2 附) - 丢。扩( 2 - 1 3 ) = ( “一l 口+ ，；，一2 + ，；，- 3 + + ，i + 且已知s ( x ) = l + s l x + s 2 x 2 + + 岛2 x 3 2 ，则伴随多项式的求解可采用迭代算法来实 现，可以构造出伴随式生成电路基本单元如图2 4 所示。 2 3 2 求解关键方程 r ，墨， 图2 4 伴随式生成电路基本单元 r s 译码器设计中，错误位置多项式和错误值多项式的运算模块是其核心模块， 经查阅大量资料，现在的r s 码译码器设计主要分为两种算法，b m 算法和m e 算 法。b m 算法采取了带有反馈的迭代结构，虽然具有较广泛的应用，但是由于其电 路中具有反馈，故实现时无法插入流水线来提升工作效率，比较适于软件实现。 m e 算法【2 1 【1 0 心是基于计算多项式的最大公约式实现算法的，具有脉动结构的实现 1 2基于卫星通信的高速纠错码技术研究及其f p g a 实现 算法。其特点在于为前向脉动结构，易于添加流水线，工作速度块，适于v l s i 实 现，且资源消耗与b m 算法相同。 而改进的b m 算法即i b m l 8 胴避免了求逆运算，通过修正减少了传统b m 算法 中多余的计算量，从而大大提高了译码器处理速度及其硬件可实现性。因此，此 处主要介绍常见的b m 算法和改进后的i b m 算法。 1 b m 算法 通过前面我们已知，s 、仃( x ) 、c o ( x ) 满足求解错误位置多项式的关键方程， s ( x ) c r ( x ) = w ( x ) m o d ( x 玎)( 2 - 1 4 ) 根据牛顿迭代算法的原理，可得迭代方法如下：首先，选取一组合理的初始 值仃( o o ) ，o o ) 然后第一次求得仃1 ( x ) ，1 ( x ) ，其中仃1 ( x ) ，1 ( x ) 用仃o o ) ， ( o ) 表示，如此进行下去，每一步都可由g ( o ( x ) ，( x ) 表示出仃“1 o ) ， “1 ( x ) ，也就是从仃( x ) ，t o ( x ) 的低次项表示出仃( x ) ，w ( x ) ，直至最后求解所有 的2 t 项。 在求解过程中，若墨= s 2 = = s j l = 0 ，s ，0 ，则当i o 开始循环迭代； 珂断，当d ，“= o l l 2 d ( j ) j 成立时， d ( ，+ 1 ) = d ( 歹) l - ( + 1 ) ( x ) = x l o )( 2 2 3 ) j j ( j + do ) = x j ( ) ( x ) 不成立时， d ( + 1 ) = j + l 一9 0 3 。z o p + 。i ) 曷三勰 ( x ) = 气x ) 卜一7 6 = d j + 1 当j = 2 t - 1 时，迭代结束，a ( x ) = 仃气x ) ，c o ( x ) = c o 7 ( x ) 。 2 3 3 钱搜索算法 在得n o ( x ) 后，钱搜索模块采用钱闻天于1 9 6 4 年提出的搜索算法进行求根运 算，对仃( x ) 求解，确定错误位置。该算法根据有限域的元素数目有限的特点，逐 一检验口”1 是否是仃( x ) 的根，即检验是否满足 仃( 口一。一1 ) = 仃( 口) = l + 仃l 口+ 仃2 a 2 + + q 口= o( 2 2 5 ) 1 4 基于卫星通信的高速纠错码技术研究及其f p g a 实现 其具体电路图如下所示。 图2 5 钱搜累电路图 注：当生成多项式的根为不连续的时候，令它们之间的间隔为s ，则当 o - ( ( x 一1 ) 5 ) = 0 时，对应的错误位置为x 一。同样，后面用到的错误值多项式等中的x - 1 也要相应地变成( x 卅) 5 。 文献【1 1 】中以消耗硬件资源为代价，通过适当的并行展开，可使其速度加快。 首先，以r s ( 2 5 5 ，2 2 3 ) 为例，我们可把o - ( x ) 表达奇数项和偶数项之和： 仃( x ) = 吼( x ) + 仃。( x ) ( 2 - 2 6 ) 其中，仃。( x ) 表示偶数项之和，仃。( x ) 表示奇数项之和。即 仃( x ) = l + c r l x + 仃2 x 2 + + o r l 6 x 1 6 ( 2 2 7 ) 1 3 。( x ) - o - i x + o 3 x 3 + + 仃1 5 ( 2 2 8 ) 仃。( x ) = l + c r 2 x 2 + 仃4 x 4 + + q 6 x 1 6 ( 2 - 2 9 ) 其结构图如图2 6 所示 其中， 图2 6 钱搜索o ( a ) 计算电路结构 第二章r s 编译码的算法原理 2 3 4 f o m e y 法计算错误值 图2 7 s a n ) 结构图 r s 译码的就最后一步就是求错误值y s 。设实际产生的错误码个数是，f ，则 可知，错误位置多项式可表示为 。 仃( x ) ：卉( 1 一誓x ) ：圭仃，x ，( 2 - 3 0 ) i = li - o 式中定义，o r o = l ，采用f o m e y 算法可知 鬈= 了- x , 万( x f l ) ( 2 3 1 ) 仃l 工。， 注：当s ( x ) = s + 最x + 墨x 2 + 时，则 鬈= 书 当生成多项式的第一个根的初始位置1 时，则式( 2 3 1 ) 和式( 2 3 2 ) 的右边 必须乘以( 百1 ) 嘞一。同时，与求解a ( a 。) 的过程类似，它需要求解 。) ，其电路结 构图也与其类似。 2 4 基本运算单元 r s 编译码器中主要的基本运算单元为加法和乘法。由于g f 有限域内加法运 算即为多项式加法运算，且多项式系数为二进制，故有限域加法即为简单的八个 并行的异或。相对而言，乘法运算则相对复杂的多，故r s 编译码器中乘法器的设 计在很大程度上影响着整个r s 编译码器的性能，下面主要描