（通信与信息系统专业论文）线性分组码中的交叠编码迭代译码技术研究.pdf

摘要 摘要 线性分组码是信道纠错编码中极其重要得一类码；它的基本理论是建立在代 数群论基础上的，这使得线性分组码有严格的代数结构。对比卷积码，线性分组 码的校验元只与本组的信息元相关，并且信息元与校验元之间满足线性叠加关系， 这种线性关系可以通过一致校验矩阵和生成矩阵来获得。一致校验矩阵以及生成 矩阵，是线性分组码的核心概念；线性分组码的码结构，纠错能力，译码算法的 实施都与其有密切联系。 本文提出了一种应用于线性分组码的交叠编码迭代译码技术；该方法可看作 一种复杂的级联码技术，在编码时，我们使两码字的信息位部分有完全相同的一 段公共信息序列；而在译码时，我们把这段公共信息序列作为译码突破口，两码 字在各自的译码过程中，以公共信息部分作为桥梁，把正确译码信息进行互相传 递，从而进一步进化所有信息数据，提高系统整体译码成功率。 r s ( r e e d s o l o m o n ) 码是一种具有很强纠正突发错误和随机错误能力的线性分 组码。i r v i n gr e e d 和g u ss o l o m o n 在19 6 0 年构造出此种码型至今的几十年里，r s 码已经在磁盘阵列，无线通信，数字视频广播( d v b ) ，深空通信等领域得到了广泛 应用。本文在第三章简要介绍了有限域基本运算规则和常用的r s 码编译码算法， 详细分析了r s 码的b m ( b e r l e k a m p m a s s e y ) 硬判决译码算法以及c h a s e 软判决译码 算法；在第五章，进一步把交叠编码迭代译码技术应用于r s 码，对b m 硬判决译 码以及c h a s e 软判决译码都进行了全面的仿真分析，仿真结果证明交叠编码迭代 译码技术能够提高r s 码编译码系统性能。 l d p c ( l o wd e n s i t yp a r i t yc h e c k ) 码，是另一种引人注目的线性分组码；它具有 和t u r b o 一样的近香农限的性能，并且其译码器的复杂度和码长成线性关系，能 获得1 0 倍于t u r b o 码的性能。本文在第四章重点介绍了仿真中用到的基于w i m a x 标准的l d p c 码构造编码方式，以及现今应用最广泛的b p 和积译码算法；然后在 第六章，把交叠编码迭代译码技术用于l d p c 码进行了一系列的仿真分析，仿真 结果再次证明交叠编码迭代译码技术能提高线性分组码的纠错性能。 关键词：线性分组码，交叠编码，迭代译码，r s 码，l d p c 码 a b s t r a c t a b s t r a c t l i n e a rb l o c kc o d ei so n eo ft h em o s ti m p o r t a n tc l a s so fc o d e sf o rc h a n n e le r r o r c o n t r o lc o d i n ga n dt h eb a s i cp r i n c i p l ei sb a s e do nt h ef o u n d a t i o no fa l g e b r ag r o u pw h i c h m a k e sl i n e a rb l o c kc o d eh a v es t r i c ta l g e b r as t r u c t u r e c o m p a r i n gt oc o n v o l u t i o nc o d e ， t h ep a r i t y - c h e c kb i t so fa1 i n e a rb l o c kc o d ea r eo n l yr e l a t e dt ot h ei n f o r m a t i o nb i t so f c o n t a i n e di nt h es a m eb l o c k ，a n dt h er e l a t i o nb e t w e e ni n f o r m a t i o nb i t sa n dp a r i t y - c h e c k b i t si sd e s c r i b e db yl i n e a rs u p e r p o s i t i o n s ，o rb yt h et h ep a r i t y - c h e c km a t r i xa n dt h e g e n e r a t i o nm a t r i x b o t ht h et w o m a t r i c e sd r o pi n t ot h ec r i t i c a lp r o p e r t i e so fl i n e a rb l o c k c o d e ，s u c h aa st h es t r u c t u r e ，t h ee r r o rc o n t r o la b i l i t ya n dt h ed e c o d i n ga r c h i t e c t u r e t h i st h e s i sp r e s e n t san e wc o d i n g d e c o d i n gs c h e m ec a l l e dt h eo v e r l a pc o d i n ga n d i t e r a t i v ed e c o d i n gf o rh a r dd e c i s i o nd e c o d i n go fl i n e a rb l o c kc o d e t h en e wr e s u l t e d c o d ec a nb er e g a r da sac o m p l e xc o n c a t e n a t e dc o d e t w oc o m p o n e n tc o d e w o r d sh a v ea f r a c t i o no fs a m ei n f o r m a t i o nb i t sa so v e r l a p p i n g d e c o d i n gu s e st h es a m ei n f o r m a t i o n b i t sa si t e r a t i o nm e d i at op a s st h ec o r r e c td e c o d i n gm a s s a g et ot h ei n d i v i d u a ld e c o d e r f o r t h et w or e c e i v e ds e q u e n c e s a n dt h i sp r o c e d u r e sw o u l di n c r e a s et h eo v e r a l l d e c o d i n gp e r f o r m a n c e r s ( r e e d - s o l o m o n ) c o d ei sas t r o n gk i n do fm a r yl i n e a rb l o c kc o d ef o rc o r r e c t i n g b o t hb u r s ta n dr a n d o me r r o r sa n dh a sb e e nw i d e l ya p p l i e di nd i s ka r r a y 、w i r e l e s s c o m m u n i c a t i o n 、d v ba n dd e e p s p a c ec o m m u n i c a t i o nf i e l d sa f t e ri r v i n gr e e da n dg u s s o l o m o n p r o p o s e dt h ec o d ei n19 6 0 i n t h et h i r dc h a p t e ro ft h i st h e s i s ，w ea tf i r s tb r i e f l y i n t r o d u c et h eb a s i co p e r a t i o nr u l e si nf i n i t ef i e l da n dt h et y p i c a ld e c o d i n ga l g o r i t h mt h e n w ei nd e t a i l e da n a l y s et h eb md e c o d i n ga l g o r i t h ma n dt h ec h a s ed e c o d i n ga l g o r i t h m f o rs o f t d e c i s i o n i nc h a p t e rf o u r , w ea p p l yt h eo v e r l a pc o d i n ga n di t e r a t i v ed e c o d i n g m e t h o dt ot h ec o d i n ga n dd e c o d i n go fr sc o d ea n dp r e s e n tc o m p r e h e n s i v e l yo u r s i m u l a t i o nr e s u l t sf o rt h eb mh a r d d e c i s i o nd e c o d i n ga n dt h ec h a s es o f t d e c i s i o n d e c o d i n g t h es i m u l a t i o nr e s u l t ss h o wt h a tt h eo v e r l a pc o d i n ga n di t e r a t i v ed e c o d i n g m e t h o di n c r e a s et h ep e r f o r m a n c eo fr sc o d e l d p c ( l o wd e n s i t yp a r i t yc h e c k ) c o d ei sa n o t h e rn o t a b l el i n e a rb l o c kc o d e i t h a st h es a m ep e r f o r m a n c eo fc l o s i n gt ot h es h a n n o nl i m i ta st u r b oc o d e t h e r ei sa i i a b s t r a c t l i n e a rr e l a t i o n s h i pb e t w e e nt h el d p cd e c o d e r sc o m p l e x i t ya n dt h ec o d el e n g t h ，a n d l d p cc o d ec a ng e tt e nt i m e st h ep e r f o r m a n c eo ft u r b oc o d e i nt h ef o u r t hc h a p t e ro f t h i st h e s i s ，w ea tf i r s ti n t r o d u c et h ec o d i n gm o d eo fl d p cc o d eb a s e do nt h ew i m a x s t a n d a r d ，w h i c hi su s e di ns i m u l a t i o n ，t h e nw ei nd e t a i l e di n t r o d u c et h eb p ( b e l i e f p r o p a g a t i o n ) d e c o d i n ga l g o r i t h m ，w h i c hi st h em o s tw i d e l yu s e dn o w a d a y s ；i nt h es i x t h c h a p t e r , w ea p p l yt h eo v e r l a pc o d i n ga n di t e r a t i v ed e c o d i n gm e t h o dt ot h ec o d i n ga n d d e c o d i n go fl d p cc o d e ，t h es i m u l a t i o n r e s u l t ss h o wt h a tt h eo v e r l a pc o d i n ga n d i t e r a t i v ed e c o d i n gm e t h e dc a na l s oi n h e r et h ep e r f o r m a n c eo fl d p cc o d e k e y w o r d s ：l i n e a rb l o c kc o d e ，o v e r l a pc o d i n g ，i t e r a t i v ed e c o d i n g , r sc o d e ，l d p c c o d e i i i 图表目录 图表目录 图1 1 信道传输基本模型3 图1 2 二维串行分组级联码编码器5 图1 3 二维并行分组级联码编码器5 图l 。4 二维并行卷积级联码编码器6 图1 5 三维并行分组级联码编码器6 图1 6 乘积码的分块8 图2 1 纠错码分类12 图2 2 分组码的编码器模型1 3 图2 3 交叠迭代编译码方案编码过程示意图17 图2 - 4 交叠迭代编译码方案译码过程示意图18 图2 5 交叠缩短编码方案1 9 图2 - 6 万= 8 且，= 1 2 时r s 交叠缩短码编码码字结构示意图2 0 图2 7 交叠编码迭代译码方案译码流程示意图2 2 图3 1 线性反馈移位寄存器电路2 8 图3 2 多项式加法器的串行数字电路实现3 l 图3 3 多项式触发器的数字电路实现31 图3 4 自回归滤波器数字电路图3 9 图3 5b e r l e k a m p m a s s e y 算法流程图4 1 图4 1e b n 0 = 7 d b 时，不同交叠长度万下的r s 码硬判决性能对比5 5 图4 2e b n 0 = 7 5 d b 时，不同交叠长度万下的r s 码硬判决性能对比5 5 图4 3 不同迭代次数，r s 码b m 硬判决译码下，方案性能比较5 6 图4 4r s 码b m 硬判决译码下，方案性能5 7 图4 5e b n 0 = 6 5 d b 时，不同交叠长度万下的r s 码软判决性能对比5 9 图4 6e b n 0 = 7 0 d b 时，不同交叠长度万下的r s 码软判决性能对比5 9 图4 7 不同迭代次数，r s 码c h a s e 软判决译码下，方案性能比较6 0 图4 8r s 码c h a s e 软判决译码下，方案性能6 1 图4 9 交叠迭代方案与原缩短码仿真对比图6 2 图5 1 编码信道上的符号说明7 2 v i i 图表目录 图6 1 方案基于w i m a x 标准l d p c 码下的性能8 0 表3 1 部分本原多项式2 8 v i 缩略语 叁翮g r b e r b f b p b p s k b s c c b p b m r s e g g l d p c l d p c l f s r l l r m p a s n r s p a 、船f 缩略语 a d d i t i v ew 1 1 i t eg a u s s i a nn o i s e b i te r r o rr a t e b i tf l i p p i n g b e l i e fp r o p a g a t i o n b i n a r yp h a s es h i f tk e y i n g b i n a r ys y m m e t r i cc h a n n e l c y c l i cc o d e sb e l i e f p r o p a g a t i o n b e r l e k a m p - m a s s e y r e e d s o l o m o n e u d l i d e a ng e o m e t r i e s g e n e r a l i x e dl o wd e n s i t yp a r i t yc h e c kc o d e s l o w d e n s i t yp a r i t yc h e c k l i n e a rf e e d b a c ks h i f tr e g i s t e r l o g a r i t h ml i k e l i h o o dr a t i o m e s s a g ep a s s i n ga 1 9 0 r i t h m s i g n a l t o - n o i s er a t i o s u mp r o d u c ta l g o r i t h m w e i g h t e db i tf l i p p i n g i x 加性高斯白噪声 误码率 比特翻转 置信传播 二进制相移键控 二进制对称信道 循环码的置信传播 伯利坎普一梅森 里德一索罗门 欧式有限几何 广义低密度奇偶校验码 低密度奇偶校验 线性反馈移位寄存器 对数似然比 消息传递算法 信噪比 和积算法 加权比特翻转 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工 作及取得的研究成果。据我所知，除了文中特别加以标注和致谢的地 方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含 为获得电子科技大学或其它教育机构的学位或证书而使用过的材料。 与我一同工作的同志对本研究所做的任何贡献均己在论文中作了明 确的说明并表示谢意。 签名：酗厂阜日期：嵫g 月8 日 关于论文使用授权的说明 本学位论文作者完全了解电子科技大学有关保留、使用学位论文 的规定，有权保留并向国家有关部门或机构送交论文的复印件和磁 盘，允许论文被查阅和借阅。本人授权电子科技大学可以将学位论文 的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或 扫描等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后应遵守此规定) 日期：po 子年6 月膏厂9 日 第一章引 言 1 1 信道纠错编码的发展 第一章引言 1 9 4 8 年香农f c e s h a n n o n ) 在他的论文通信的数学理论【l 】中首次提出著名的 有噪信道编码定理，该定理指出，对于任何一个通信信道，总有一个确定的信道 容量c ，如果通信系统的传信率r c ，则存在一种编码方式，使该信道以任意小 的差错概率进行信息传输；若r c 则不可能存在某种编码方式使传输差错概率任 意小。虽然这只是一个数学上的存在性定理，但却开创了信道编码理论这一富有 活力的研究领域。有噪信道编码定理从理论上给出了纠错码的理论极限，它给以 后纠错码的研究指明了方向。 从纠错码的发展历程来看，主要分成两类：分组码和卷积码【2 】【3 1 。第一个分组 码出现于1 9 5 0 年，汉明( h a m m i n g ) ( 4 】找到了一类纠单个差错的分组码。汉明码比 香农定理指出的码要弱得多。尽管人们进行了努力探索，但一直到5 0 年代末，尚 未找到更好的码类。在这一期间的主要进展在于b o s e ，r a y - c h a u d h u r i ( 1 9 6 0 年) 和 h o c q u e n h e m ( 1 9 5 9 年) 找到一大类多个差错纠错码( b c h 码) ，以及r e e d 与 s o l o m o n ( 1 9 6 0 年) 为非二进信道找到一大类有关的码( r s 码) 【5 】。这些码至今仍然留 在重要的码类之中。卷积码是由伊莱亚斯( e l i a s ) 于1 9 5 4 年首先提出来的。最初从 概率的观点来进行卷积码译码器的设计，这些尝试导致了序贯译码的概念。在5 0 年代后期卷积码已经用序贯译码算法成功地译码。一种简单得多的卷积码的译码 算法维特比( v i t e r b i ) 算法【6 】，一直到1 9 6 7 年才出现。特别是对中等复杂度的卷积码， v i t e r b i 算法得到广泛的应用。 无论是从信息论还是从编码理论看，要想尽量提高编码的性能，就必须要加大 编码中具有约束关系的序列长度。但是直接提高分组码编码长度或卷积码约束长 度都使得系统的复杂性急剧上升。在这种情况下，1 9 6 6 年f o r n e y 提出了级联码【_ 7 】 的概念，即以多个短码来构造长码的方法，这样既可以减少译码的复杂性，同时 又能够得到等效长码的性能。一种广泛应用的级联结构就是以r s 码作为外码，以 卷积码作为内码的串联结构。 级联码方面的大量研究最终结出了t u r b o 码【8 】【9 】这样一个硕果。c b e r r o u 等人 电子科技人学硕七学位论文 在1 9 9 3 年首次提出了t u r b o 码的概念。t u r b o 码又称并行级联卷积码( p c c c ) 【1 0 1 ， 它巧妙地将卷积码和随机交织器】【1 2 】结合在一起，在实现随机编码思想的同时， 通过交织器实现了由短码构造长码的方法，并采用软输出迭代译码来逼近最大似 然译码。从而获得了几乎接近香农极限的纠错性能，同时复杂度较低可以实现， 为信道编码领域带来了一场革命。t u r b o 码的出现引发了对迭代译码算法研究的热 潮，1 9 9 5 年m a c k a y 和n e a l 1 3 】重新发现早在1 9 6 2 年由g a l l a g e r 提出的低密度校验 i - 马( l d p c ) 1 4 】也是一种性能接近香农限，而且可以实现的编码方案。 在过去的5 0 多年里，有关纠错编码技术的研究已经取得了许多可喜的成果【i5 1 。 伴随着通信技术的飞速发展，纠错编码技术已经成为现代通信领域不可或缺的一 项标准技术。 1 2 信道纠错编码在通信系统中的作用 提高信息传输的可靠性和有效性，始终是通信工作所追求的目标。纠错码是提 高信息传输可靠性的一种重要手段。1 9 4 8 年香农( s h a n n o n ) 在他的开创性论文“通 信的数学理论 中，首次阐明了在有扰信道中实现可靠通信的方法，提出了著名 的有扰信道编码定理，奠定了纠错码的基石。自此以后汉明( h a m m i n 蓟、斯列宾 ( s l e p i a n ) 、普兰奇( p r a n g e ) 等人在5 0 年代初，根据香农的思想，给出了一系列设计 好码和有效译码的方法。以后，纠错码受到了越来越多的通信和数学工作者，特 别是代数学家的重视，使纠错码无论是在理论上还是在实际中都得到了飞速发展。 近年来，随着t u r b o 码的出现和低密度校验检测码( l d p c ) 的重新发现，再次掀起 了寻找好的纠错编码方法的热潮。 目前，利用纠错码降低各类数字通信系统以及计算机存贮和运算系统中的误码 率，提高通信质量，延长计算机无故障运行时间等，在美国等西方国家中已作为 - - f - 标准技术而广采用。在移动通信中，纠错码被广泛用于模拟体制的信令传输 及数字体制的整个传输，以高传输的可靠性和节约珍贵的频谱资源；在卫星通信中， 纠错码技术已成为用来降低对高放的要求和减少地球站天线孔径的尺寸的经济可 靠的方法，v s a t ( 甚小口径天线地球站) u s a t ( 超小1 ：1 径天线地球站) 的兴起，都是 和纠错技术的应用有关的；在宽带综合业务字网( b i s d n ) 通信中，纠错码也是保证 多种业务的服务质量，降低规模、功耗代价，高系统性能的关键技术。此外，纠 错码技术还应用于超大规模集成电路设计中，以提高集电路芯片的成品率，降低 2 第一章引言 芯片的成本。利用纠错码中的许多编、译码原理和方法，与通信统中的其它有关 技术相结合，得到了令人惊喜的结果。 通信的目的是要把对方不知道的消息及时可靠地( 有时还须秘密地) 传送给对 方，因此，要求一个通信系统传输消息必须可靠与快速，在数字通信系统中可靠 与快速往往是一对矛盾。若要求快速，则必然使得每个数据码元所占得时间缩短、 波形变窄、能量减少，从而在受到干扰后产生错误得可能性增加，传送消息得可 靠性减低。若要求可靠，则使得传送消息的速率变慢。因此，如何较合理地解决 可靠性与速度这一对矛盾，是正确设计一个通信系统的关键问题之一。通信理论 本身( 包括纠错码) 也正是在解决这对矛盾中不断发展起来的。所有数字通信系统 如通信、雷达、遥控遥测、数字计算机的存贮系统和内部运算及数字计算机之间 的数据传输等，都可以归结成如图卜1 示的模型。 信源编码器 信源译码器 信道编码器 l壁兰塑 璺! 嵩 c ) e 宾) 图1 - 1 信道传输基本模型 图1 - 1 ，信源编码器是把信源发出的消息如语言、图像、文字等转换成为二进 制( 也可转换成为多进制) 形式的信息序列，并且为了使传输有效，还去掉了一些 与传输信息无关的多余度( 有时为了保密，信源编码器后还可接上加密器) 。为了 抗击传输过程中的各种干扰，往往要对信源编码器送出的信息序列，人为地增加 一些多余度，使其具有自动检错或纠错能力，这种功能由图中的信道编码器即纠 错编码器完成。发射机( 调制器) 的功用是把纠错码送出的信息序列通过调制器变 换成适合于信道传输的信号。数字信号在信道传输过程中，总会遇到各种干扰而 使信号失真，这种失真传输到接收端的接收机，进行解调，变成二进制( 或多进制) 信息序列。由于信道干扰的影响，该信息序列中可能已有错误，经过信道译码器 即纠错码译码器，对其中的错误进行纠正，再通过信源译码器( 及解密器) 恢复成 原来的消息送给用户。 3 囊至 电子科技人学硕十学位论文 信道译码器是编码器的逆变换，它根据解调器输出的数据序列进行译码运算。 由于从解调器输出的数据序列可能还有错误，因此译码器要完成比编码器更为复 杂的运算，以纠正这些错误。译码器性能的好坏、速度的快慢往往决定了整个差 错控制系统的性能和成本。信源译码器是信源编码器的反变换。它把信道译码器 输出的已经过纠错的信息序列，恢复成信源原始发送的消息送给用户。 1 3 构造好码，提高纠错码性能的方式 1 3 1 级联码 一般的线性分组码和卷积码只适用于差错概率要求不太高的系统中，这时系统 所能达到的性能无论从理论上或实际上距离s h a n n o n 极限( 传输l 比特信息所需要 的信噪比为1 6 d b ) 还l l 较远。当系统的可靠性要求很高，信道干扰又较强时，需 要进一步提高编码增益，为此要用级联码。 级联码是f o m e y 引入的，它是用两次或更多次编码的方法组合成很长的分组 码，以期实现s h a n n o n 编码定理所要求的增大码长实现有效而可靠的通信的目的。 码长过大时，一次编码和译码所需的设备很复杂，因而难以实现。用多级编码和 译码就可以大大降低编译码的复杂性，而成为实际中可以实现的技术。级联码自 从诞生以来得到了很大的发展，已经在需要很高的编码增益的应用中作为标准， 例如深空通信等。 香农信息理论指出，长码和编码随机化是寻找渐进好码的有效途径，人们沿着 这一思路进行了很多探索并取得了丰硕成果，1 9 6 6 年f o m y e 首次提出级联码的概 念，它以并不复杂的方式实现了长码和编码随机化。按级联方式级联码主要分为 串行级联码和并行级联码，按级数可以分二维和多维级联码，按分量码的种类不 同可分为线性分组级联码和卷积级联码【l 酬。 串行级联分组码( s c b c ：s e r i a l l yc o n c a t e n a t e db l o c kc o d e s ) f i l l 通常意义的乘积 码，图1 2 为它的编码器框图。s c b c 的分量码可以是任意类型的分组码，但一般 选择码率较高、纠错能力较强的二进制b c h 码或经过多进制向二进制映射的r s 码【1 7 】【1 8 】【1 9 】。而卷积码由于具有记忆性，且编码时不像b c h 码那样每行都是独立编 码，经过串行级联编码后并不能保证整个码字仍然是这种类型的卷积码，因此卷 积码并不适用于串行级联方式。 4 第一章引言 不： 图卜2 二维串行分组级联码编码器 并行级联分组码( p c b c ：p a r a l l e lc o n c a t e n a t e db l o c kc o d e s ) 编码器如图1 3 所 毛k 2力lx 屯+ k i 玎2 一向x 屯 位信息序列 屯个。只输出校验 如个 。复 位编码输出信息序列l 位的编码器 啊一向比特组 用 岛比特组 毛k s屯个 。只输出校验 k 1 个 。 交织器位的编码器 一如比特组k 比特组 图卜3 二维并行分组级联码编码器 其分量码的选择和串行级联分组码类似。当毛x 红位信息码元输入到二维并行 级联码的编码器后，编码器的第一个子编码器将输出忽x ( 刀，一屯) 位检验位码元， 第二个子译码器输出红( n 一毛) 位校验位码元，它们和毛x 岛位未编码的信息码元 进行复用后可得到n x 屯+ 毛n 2 一毛x 毛位比特的编码输出；并行级联卷积码 ( p c c c ：p a r a l l e lc o n c a t e n a t e dc o n v o l u t i o nc o d e s ) 编码器如图1 4 所示，文献 19 1 的 t u r b o 迭代译码算法就是在此基础上实现的，其分量码是一种特殊类型的卷积码一 递归卷积系统码( r s c ) ，本文仿真研究采用的是( 1 3 3 ，1 7 1 ) 和( 2 3 ，3 5 ) 这两种码率为1 2 的递归卷积系统码作为p c c c 的分量码，p c c c 需对校验比特做删余处理，采用的 删余矩阵为 1 0 ，0 1 ，即删去来自r s c i 的检验序列的偶数位置比特与来自第二个子 译码器输出的检验序列的奇数位置比特，如果p c c c 采用上述编码规则，可以计 算出最后的码率仍然为抛。并行级联码编码器在进行复用时，如果是高斯白噪声 信道，则对三个输入端所输入的码元的顺序不作严格要求，只要能够在译码的时 候顺利提取就行，关键在于怎么样安排它们最有利于算法的实现。 电子科技人学硕+ 学位论文 k l k 2，l k 2 + k l 门2 一k 2 位信息序列 七。 只输出校验删 七2 个 复 位编码输f j ；信息序列 位的编码器 余用 毛比特组 n 。一向比特组 k l k 2 k z 个 只输出校验删 k 1 个 ， 交织器位的编码器 余 n 2 - k 2 比特组 k 比特组 图l _ 4 二维并行卷积级联码编码器 多级串行级联码的编码器框图可在二级串行级联码基础上进行改进，比如三级 串行级联码可在图1 3 的后面接上一个交织器和【n 3 ，岛，最】的编码器，此时输入的 信息比特数为乞缸位毛比特组，经过第一个编码器后输出致织位n ，比特组，再 经过交织器长度为n = 屯( ，l 。缸) 的第一个交织器得到n i 致位恕比特组，输入到第 二个编码器，类似第二个交织器长度为n = 故( 强惕) 把从第二个编码器输出的 n 缸位n ，比特组变换为n 。xn 2 位缸比特组以提供给第三个编码器，最后得到 1 1 2 位比特组的编码输出；三级并行级联码可在图1 4 的下面分别增加一个交 织器和分量码编码器，如图1 5 所示，其中第一个长度为n = 缸x ( 毛红) 的交织器提 供毛豇位吃比特组给第二个编码器，第二个长度为n = 缸( 毛如) 的交织器提供 毛位织比特组给第三个编码器，编码器最后输出 ，z i 如缸+ 毛 1 2x 效+ 毛恕一2 k i 屯缸位码元比特的编码输出。由于级联码 的编码很好地体现了长码和对噪声的随机化，能纠正大量随机和突发错误图样， 因此比一般线性分组码具有更强的纠错能力。 只输出校验 毛也岛 位的编码器 一x 岛屯+ 岛x 以2x 乜一2 t ：1 也x k 3 位信息序列 复 位编码输出信息序列 l 毛x 也 只输出校验如个 用 + 交织器 位的编码器 i i i 一七比特组 毛k 2 只输出校验k 1 个 、 ， 交织器 位的编码器 吃一也比特组 图1 5 三维并行分组级联码编码器 6 第一章引言 1 3 2 交织器 在级联码的实现方案中，长码的伪随机性是决定码字性能的关键，交织技术正 是实现伪随机性的一个重要手段，在级联码的构造中扮演了一个不可或缺的重要 角色。在信号发送端，其伪随机性是通过编码器中的交织器结合并行或者串行级 联方式来实现的；在接收端的译码器中，伪随机性是交织器和反馈迭代译码共同作 用的结果。就本质而言，交织其实是通信系统中进行数据处理而采用的一种技术， 是一种实现最大限度的改变信息结构而不改变信息内容的方法，从传统上来讲就 是使信道传输过程中所突发产生集中的错误最大限度的分散化、不规则化。因此， 因此交织器实际上更贴切的称谓应该叫数据置乱器。 从交织技术开始应用于信道编码中直至现在为止，总体上来讲可以分为三大 类：规则交织器、不规则交织器、随机交织器。规则交织器被最早应用于信道编 码中，其实就是通常我们所说的分组交织器，或称作行进列出交织器，一个典型 的分组交织器是一个按着n m 矩阵描述的周期为t = n m 的交织器，这种交织器 最典型的特征就是在数据的读写过程中是按着行进列出或列进行出的形式进行 的。我们可以通过二维串行级联分组码的构造过程进一步加深对行进列出交织方 式的理解，具体步骤如下： 1 对毛如比特长度的信息码元，按顺序排列成一个毛x 屯码阵f c l ； 2 按某个线性分组码c 2 【吃，如，4 】的编码规则对【c 】逐行进行编码，得到一个 新的毛x ，z ，码阵 c 7 】； 3 按某个线性分组码g 1 7 1 , 曩，匹】的编码规则对 c 逐列进行编码，最后得到 _ 他的乘积码【e 】。 、 ，1 2 ，r 卜也一 伞 奉 l i i f 信息块行校验块 一 1 上 列校验块 校验之校 验块 图i - 6 乘积码的分块 7 电子科技大学硕士学位论文 可以看出从第一步的逐行编码到第三步的逐列编码可以实现对l c l 的行进列出 交织，乘积码码阵f e l 可分割成4 块：信息块、行校验块、列校验块、校验之校验 块，如图1 6 所示。可以证明f e l 的最小重量为点破，所以乘积码实质上是一种码 长为聆，1 1 2 ，码率为( k 。乞) ( n 。xn ：) ，最小汉明距为磊最的线性分组码，由于乘积 码的编码很好地体现了长码和编码随机化，因此具有一般线性分组码所不能达到 的纠错能力，它除了能纠正所有重量不大于( 4 最一1 ) 2 的随机错误图样外，还能纠 正其它大量的随机和突发错误图样。 不规则交织器大部分是由分组交织器演变而来的，目前主要有对角交织器、螺 旋交织器等种类。对角交织器和螺旋交织器都是采用行写而对角读出的方式，两 者不同是在于对角交织器是行写然后从第一行的第一个元素开始以对角方式读 出，而b t c 基于计算l l r 的迭代译码螺旋交织器则是从最后一行的第一个元素开 始以对角的方式读出。总体来说这两种交织器都是由分组交织器演变而来的，其 性能要比一般的分组交织器稍好。 随着t u r b o 码理论的日趋成熟，随机交织器已经被日益广泛的应用起来，但现 在真正能用于实践的都是伪随机交织器，这是因为译码器中的交织器与编码器中 的交织器具有明确的对应关系。分组交织器、对角交织器和螺旋交织器是以规则 的顺序进行交织，所以在收发两端能够很容易地获得这种对应关系。但是在采用 了随机交织器的级联码系统中，由于每一组信息序列交织后的结果都是随机性的， 要想得到这种对应关系，必须要求在在信道上既要传输编码序列，还要传输交织 器的信息，这不仅会加大译码器的复杂度，而且也加大了信道负载，如果在中途 交织信息出现错误，还会使译码的误码增多，所以现在所采用的随机交织器都是 伪随机的，是事先经过随机选择而生成的一种性能较好的交织方式，然后将其做 成表的形式存储起来进行读取，目前公认性能较好的是伪随机s 交织器【2 们。 b n e d e e t o t s 和m o n o t s r i g 引入的均匀交织器的概念【2 1 1 ，给出了t u r b o 码的一个b e r 联合上限，并指出了好的交织器是存在的，这些研究结果对于选择交织器有一定 的指导意义。由于本文偏重于s i s o 算法的研究，又是基于b p s k 高斯白噪声信道， 码的帧长度也不是很大，所以只选用了行进列出交织方式，不对其他类型的交织 器做深入探讨。 1 4 论文结构及主要成果 第一章引言 论文的结构如下： 第一章引言。首先介绍信道纠错编码的发展现状，并指出其在通信系统中的 重要作用；然后介绍了构造好码，提高纠错性能的方式。 第二章交叠编码迭代译码方案的基本原理。首先介绍了线性分组码的基本概 念以及分类；然后介绍本文提出的交叠编码迭代译码方案进行了基本的原理，并 阐述了交叠编码迭代译码方案的编码过程和译码过程；最后，对影响交叠编码迭 代译码方案性能的参数进行了分析。 第三章r s 码编译码原理。此章介绍了r s 码涉及的一些基本知识，并介绍了 交叠编码迭代译码方案仿真时涉及的r s 码的编译码方法。首先，介绍了r s 码的 相关代数理论，主要是关于有限域的一些基本常识；然后介绍了r s 码基本的编译 码方法，r s 码的编码具体介绍了伽罗华域的构造方法，以及从时域和频域上分别 阐述编码原理，r s 码的译码具体介绍了b e r l e k a m p m a s s e y 硬判决译码算法和 c h a s e 软判决译码算法。 第四章l d p c 码的编译码原理。首先介绍了l d p c 码的基本概念；然后具体 介绍了文中仿真用到的w i m a x 标准下的l d p c 码的构造方法和编码方法；最后， 介绍了通用的b p 和积算法，其中对概率域上的b p 算法，对数域上的b p 算法以 及一些改进型b p 译码进行具体介绍。 第五章r s 码下的交叠编码迭代译码方案仿真。此章具体介绍分析了交叠编 码迭代译码方案在r s 码情况下的具体仿真性能。首先，对r s 码下的仿真的背景： 以太网无源接入网( e p o n ) 进行介绍；然后，对应用r s 码的交叠编码迭代译码方 案的参数进行分析设计；最后，在不同的参数条件下，统计分析了r s 码 b e r l e k a m p m a s s e y 硬判决译码和c h a s e 软判决译码下的性能。 第六章l d p c 码下的交叠编码迭代译码方案仿真。此章具体介绍分析了交叠 编码迭代译码方案在l d p c 码条件的具体仿真分析。首先，对仿真背景w i m a x 标准做了具体介绍；最后，对应用l d p c 码的交叠编码迭代译码方案进行了具体 仿真分析。 第七章对全文进行了概括总结，并指出了继续进行的相关研究工作和未来可 能的研究方向。 本文主要取得如下研究结果： 9 电子科技人学硕士学位论文 1 提出了一种新的交叠编码迭代译码方案。 2 对现有的分组码，主要是r s 码和l d p c 码的性能进行分析研究。 3 把交叠编码迭代译码方案应用于r s 码，对r s 码b e r l e k a m p m a s s e y 硬判 决译码算法以及c h a s e 软判决译码算法下的方案的性能进行仿真对比研 究。 4 把交叠编码迭代译码方案应用于l d p c 码，对应用w i m a x 标准结构的 l d p c 码的方案的性能进行仿真对比研究。 1 0 第一二章交叠编码迭代译码方案的基本原理 第二章交叠编码迭代译码方案的基本原理 2 1 线性分组码的基本概念 2 1 1 信道纠错编码的分类 信道纠错编码的各种差错控制系统中所用到码，不外乎是能在译码器自动发现 错误的检错码，或者不仅能发现错误而且能自动纠正错误的纠错码，或者能纠正 删除错误的纠删码。但这三类码之间没有明显的区分，所以，任何一类码，按照 译码方法不同，均可作为检错码、纠错码或纠删码来使用。除了上述的划分方法 以外，通常还按以下方式对纠错码进行分类： 1 按照对信息元处理方法的不同，分为分组码与卷积码两大类。 分组码是把信源输出的信息序列，以后个码元划分为一段，通过编码器把这段 k 个信息元按一定规则产生，个校验( 监督) 元，输出长为n = k + ，的一个码组。因此 每一码组的校验元仅与本组的信息元有关，而与别组无关。分组码用( ，z ，k ) 表示， n 表示码长，