（通信与信息系统专业论文）tpc编译码算法研究与实现.pdf

硕士论文 t p c 编译码算法研究与实现 摘要 无线通信信道中存在着干扰和衰落，使通信系统的可靠性降低，而对信号进行预处 理可以提高信噪比，减少误码率。往往采用差错控制编码技术来检测和纠正因为信道失 真引起的信息传输错误，提高信号传递的可靠性。差错控制编码的研究主要是希望在低 译码复杂度的前提下，寻找一种逼近香农极限的编译码方法。t u r b o 乘积码不仅译码复 杂度低，译码延时小，而且它继承了t u r b o 码在低信噪比下仍然有低误码率的优点。因 此，t u r b o 乘积码已经成为纠错编码领域的研究热点。 本文首先指出纠错编码的应用领域和它的发展历史，比较了t u r b o 乘积码和其他纠 错编码的性能。然后依据t p c 的编译码原理，对t u r b o 乘积码的迭代译码算法进行了 探讨，译码算法采用典型的c h a s e 迭代译码算法，在m a t l a b 7 0 下进行了仿真。本文 还提出了f p g a 可实现的t p c 编译码结构设计，叙述了部分模块设计思想，并且在a l t e r a 公司的q u a r t u si i 一6 0 环境下进行了仿真。子码码型选用加了一位奇偶校验位的截短循 环码( 2 2 ，1 6 ) 。在实际应用中，编译码器均采用了美国a h a 公司生产的针对分组t u r b o 码的第一代t p c 编译码专用芯片a h a 4 5 0 1 ，通过对芯片内部寄存器的控制实现t p c 码 的编译码，根据芯片给出的时序说明完成的芯片的初始化工作。最后总结了研究成果， 指出有待改进的地方，阐述作者对该领域的一些看法。 关键词：t p c 编码，迭代译码算法，f p g a 实现，a h a 4 5 0 1 ，信道编码 a b s t r a c t 硕十论文 h a b s t r a c t t h ei n t e r f e r e n c ea n df a d i n gi naw i r e l e s sc o m m u n i c a t i o nc h a n n e lr e d u c et h e r e l i a b i l i t yo ft h ec o m m u n i c a t i o ns y s t e m s a n dt h ep r e - p r o c e s s i n gc a ni m p r o v et h es i g n a l t on o i s er a t i o ，a n dr e d u c et h ee r r o rr a t e e r r o rc o n t r o lc o d i n gt e c h n o l o g yi so f e nu s e dt o d e t e c ta n dc o r r e c tt h ei n f o r m a t i o nt r a n s m i s s i o ne r r o rd u et oc h a n n e le r r o r s a n dt o i m p r o v et h er e l i a b i l i t yo ft h es i g n a lt r a n s m i s s i o n t h em a i np o i n to ft h es t u d yo fe r r o r c o n t r o lc o d i n gi st of i n dan e a rs h a n n o nl i m i tc o d i n ga n dd e c o d i n gm e t h o du n d e rt h e p r e m i s eo fl o wd e c o d i n go fc o m p l e x i t y t u r b op r o d u c tc o d ei sn o to n l yh a sl o wd e c o d i n g c o m p l e x i t ya n ds m a l ld e c o d i n gd e l a y , b u ta l s oi n h e r i t e dt h et u r b oc o d e s sa d v a n t a g eo f c l o s i n gt ot h es h a n n o nl i m i t i no t h e rw o r d s ，i ts t i l lh a sl o we r r o rr a t ea tl o ws i g n a lt o n o i s er a t i o t h e r e f o r e ，t u r b op r o d u c tc o d eh a sb e c o m eah o tr e s e a r c h i n ga r e ao fe r r o r c o n t r o lc o d i n g f i r s to fa l l ，t h i sp a p e rp o i n t e do u tt h ea p p l i c a t i o na e r ao ft h ee r r o r - c o r r e c t i n g c o d i n ga n di t sd e v e l o p m e n th i s t o r y t h e ni tc o m p a r e dt h ep e r f o r m a n c eo ft h et u r b o p r o d u c tc o d e sa n do t h e re r r o r - c o r r e c t i n gc o d i n g b a s e do nt h ep r i n c i p l eo ft h et p c ，t h e i t e r a t i v ed e c o d i n gf o ri th a sb e e nd i s c u s s e d ，w i t hat y p i c a lc h a s ei t e r a t i v ed e c o d i n g a l g o r i t h mf o rt h er e p r e s e n t a t i v e ，a n ds i m u l a t e di nm a t l a b7 0e n v i r o n m e n t t h e n f p g ac h i pw a sp u tf o r w a r dt oa c h i e v et h es t r u c t u r ed e s i g no ft h et p cc o d e s t h i sp a p e r d e s c r i b e dt h et h i n k i n gp a r to fs o m em o d u l e s ，a n du s e dt h ea l t e r a sq u a r t u s - i i6 0t o s i m u l a t e t h es u b c o d ec o d e t y p ea d o p t e dt h et r u n c a t e dc y c l i cc o d e ( 2 2 ，16 ) t h a tp l u sa p a r i t yb i t i nr e a ls y s t e m ，b o t ht h ee n c o d i n ga n dd e c o d i n gu s et h ea h a 4 5 0 1c h i p ，w h i c h i st h ef i r s tt p ce n c o d i n g d e c o d i n gc h i po fa h a c o r p o r a t i o n a c c o r d i n gt ot h et i m i n g s p e c i f i c a t i o n sg i v e nb yt h ec h i pg u i d e ，t h i sp a p e rc o m p l e t e dt h ei n i t i a l i z a t i o no ft h ec h i p a tl a s t ，t h ep a p e rc o n c l u d e dt h er e s u l t so ft h es t u d y , a n dc o n c l u d e dt h ea r e a st ob e i m p r o v e d s o m ea s p e c t so fc o d i n ga n di t sd e v e l o p i n gt r e n da r ea l s oc o n s i d e r e d k e yw o r d ：t p cc o d e ，i t e r a t i v ed e c o d i n ga l g o r i t h m ，f p g ar e a l i z a t i o n ，a h a 4 5 01 ， c h a n n e lc o d e 声明 本学位论文是我在导师的指导下取得的研究成果，尽我所知，在 本学位论文中，除了加以标注和致谢的部分外，不包含其他人已经发 表或公布过的研究成果，也不包含我为获得任何教育机构的学位或学 历而使用过的材料。与我一同工作的同事对本学位论文做出的贡献均 已在论文中作了明确的说明。 研究生签名： 酶纬加 ! 年月江日 o ii 学位论文使用授权声明 南京理工大学有权保存本学位论文的电子和纸质文档，可以借阅 或上网公布本学位论文的部分或全部内容，可以向有关部门或机构送 交并授权其保存、借阅或上网公布本学位论文的部分或全部内容。对 于保密论文，按保密的有关规定和程序处理。 研究生签名：皇屿牡呷年月乜日 硕+ 论文 t p c 编译码算法研究与实现 1 绪论 1 1 课题研究背景 1 1 1 纠错编码的应用 在深空和卫星通信领域、数据传输领域、数据存储领域、数字音频视频传输领域、 移动通信领域和文件传输领域中，纠错编码有着广泛的应用。 深空通信因为其信息传输距离远、传输延时大、信号能量衰减严重等特点，必须采 用各种措施来保证信息传输准确。这些措施就包括采用高性能的信道编译码技术来得到 高的编码增益。高的编码增益就意味着探测器可以探测更远的距离，发射设备的发射功 率可以做得更小。深空通信的信道和无记忆高斯白噪声信道相似，而且香农编码理论采 用的信道模型正是无记忆高斯白噪声信道，因此将信道编码理论应用于深空通信信道得 到的理论和仿真结果将会与实践相差无几。深空通信的信道带宽相对较宽，使得低频谱 利用率的编码和二进制调制方案都能够使用。正是由于深空通信的上述特点，使得编码 技术在其中得到了很好的应用，而且发展迅速【l j 。 要实现在a w g n 带限信道上高效可靠地传输数据就必须克服噪声的影响。而编码 和调整正是抑制噪声的两种有力手段。传统的做法是分开讨论和设计编解码与调制解 调。m a s s e y 在2 0 世纪7 0 年代中期根据信息论，证明了将编码与调制作为一个整体考 虑的最佳设计，可以明显的改善系统的性能。1 9 8 2 年，昂格尔博克( u n g e r b o e c k ) 提 出了卷积码与调制相结合的网格编码调制( t c m ) ，它的显著优点便是不需要增加传 输带宽或者降低信息传输速率便可以获得可观的编码增益。因此t c m 是高速数据传输 抗噪声的最佳手段，很快就得到了应用【2 】【3 】。 纠错编码可以克服存储设备中存在着的大量随机错误和突发错误，目前比较通常的 做法是将r s 码、阵列码用于全息数据存储【4 】。另外在卫星数据存储特别是微小卫星的 数据存储设备中，必须尽可能避免空间辐射造成的单粒子翻转。而纠错编码对克服单粒 子翻转引起的错误有效。目前主要采用汉明码和三倍冗余判决( t m r ) 方案【5 j i 6 。 纠错编码技术也广泛应用于数字音频广播和数字视频广播以增强传输的可靠性【7 j 。 移动通信在为人们提供灵活、机动、高效的通信方式的同时，也使得移动通信的研 究、开发和实现比有线通信更复杂困难。移动通信信道中存在着多径效应、多普勒频移 和阴影效应等影响，而使信号衰落迅速、码间干扰和信号失真严重。因此，各种数字信 号处理技术，例如多址技术、纠错编码、分集技术、软件无线电等被应用于移动通信系 统来改善它的性能。移动通信信道的恶劣性迫使译码器在非常低的信噪比下工作，而且 移动通信信道频率资源稀少。这就意味着对编译码器的设计提出了较高要求。英国的模 1 i 绪论硕。 ：论文 拟蜂窝移动通信中采用了b c h 编码【8 1 。目前最广泛使用的g s m 系统使用多种f e c 编 码，包括b c h 编码、f i r e 编码、c r c 编码。目前，3 g p p 协议中已经确定t u r b o 码为 其纠错编码方案，在3 g 的3 种主流标准中都采用t u r b o 码技术作为高速率信道的编码 技术。另外在4 g 移动通信中，更高级的信道编码方案如l d p c 等将得到应用【9 】。 1 1 2 纠错编码的历史与发展介绍 纠错编码是以最小差错概率实现信源到信宿传输数字信息的一种方法，是解决传输 可靠性的一种重要手段。 香农( c e s h a n n o n ) 分别于1 9 4 8 年在贝尔系统技术杂志上发表了关于“通信的数 学理论 【1 0 】和1 9 5 7 年发表了“适用于有扰信道的编码理论的某些成果【l l 】两篇文章。 在这两篇文章中，他用概率测度和数理统计理论的方法系统地讨论了通信的基本问题， 得出了重要结论：在通信系统中采用适当的编码后能够实现高效率和高可靠性的信息传 输，并且得出了信源编码定理和信道编码定理，由此奠定了现代信息论的基础。但是， 香农定理仅证明了最优编码是存在的，并未给出如何去寻找好的纠错编码。从此，很多 科学工作者和工程技术人员在香农所指的方向上进行了极有意义的探索。 这以后，戈莱( g o l a y ) 于1 9 4 8 年发表了“评论数字编码”，并且于1 9 5 4 年发明了 g o l a y 码。汉明( h a m m i n g ) 在1 9 5 0 年发表了“检错与纠错码 ，奠定了线性分组码的理 论基础。1 9 5 4 年马勒( m u l l e r ) 从现行空间角度构造，同年里德( r e e d ) 用大数逻辑译 码方法解决了它的译码而得到t r m 码l l 2 。同h a m m i n g 码和g o l a y 码相比，r m 码的编码 方式和纠错能力更灵活。1 9 5 9 年由霍昆格姆( h o c q u e n g h e m ) ，1 9 6 0 年由博斯( b o s e ) 和雷查德胡旱提出了b c h 码。它是能纠正多个随机错误的循环码，具有严格的代数结 构、纠错能力强、构造简单、编码较其他码简单的特点。同年，r e e d 和s o l o m o n 发现的 多进制r s 码，它是一类非二进制的b c h 码，特别适合于纠正突发错误。与线性分组码 同时期提出的是卷积码，它是由p e l i a s 于1 9 5 5 年提出来的一种非分组码。与分组码不同， 卷积码编码器把七比特信息段编成n l g 特码组，但所编的n 长码组不仅同当前的尼比特信息 段有关联，而且还同前面的( - 1 ) 个( 1 ，整数) 有关联。自此，卷积码的的主要 问题是译码。1 9 6 1 年，乌曾格来夫( w o z e n c r a f t ) 提出了序列译码算法，它的计算量是随 信道干扰大小而变化的，但是平均计算量小，译码速度快，在约束长度较大的长度使用 序列译码能使译码性能接近最佳【l 引。 这以后，代数编码理论日趋完善。r e e d 最先提出了大数逻辑译码算法的思想。1 9 6 0 年，彼得森( p e t e r s o n ) 提出了第一个b c h 译码算法，它适用于纠错数较少的译码。之后， 钱( c h i e n ) # l l 福尼( f o m e y ) 提出了更高效的b c h 译码算法。1 9 6 6 年b e r l e k a m p 提出了迭代译 码算法，梅西( m a s s e y ) 从线性反馈移位寄存器的角度对该算法进行了描述，形成了b m 算法。b m 迭代算法的硬件实现简单。对于卷积码的译码，1 9 6 3 年费诺( f a n o ) 完善了 2 硕士论文t p c 编译码算法研究与实现 w o z e n c r a f i 提出的序列迭代译码算法，称为f a n o 算法。之后，扎纲奇诺夫( z i g a n g i r o v ) 和 杰里内科( j e l i n e k ) 分别于1 9 6 6 年和1 9 6 9 年设计出堆栈算法，译码速度比f a n o 算法更快。 对于卷积码的另一种概率译码技术，维特h ：( v i t e r b i ) 译码算法由19 6 7 年v i t e r b i 提出。它 具有译码速度快、效率高、译码器简单等优点，而且其本质上是无记忆噪声中的离散有 限状态马尔可夫过程的输入序列进行估计，因此适用各种通信估计问题，是目前卷积码 译码最常用的算法。 1 9 7 0 年，以g o p p a 为首的一批学者，构造了一类g o p p a 码，g o p p a 码类中含有好码， 甚至一类子码能达至l j s h a n n o n 信道编码定理中所指出的性能。b c h 码是g o p p a 码的一个 子类。一般而言，g o p p a 码是非循环码( b c h 码除外) ，而它的译码方法非常相似于b c h 的译码。8 0 年代初，t s f a s m a n 、v l f i d u t 和z i n k 将g o p p a 的思想与代数几何中的深刻结果 相结合，构造了一类代数几何码。代数几何码的信息率超过了g i l b e r t v a r s h a m o v 界，具 有非常优越的性能【川。另外，对于线性分组码的译码，人们提出软判决译码的概念。在 分组码中使用软判决译码，使得工程人员在设计通信系统时有更大的灵活性。在许多情 况中，软判决使用的附加信息能够得到2 d b 的编码增益。软判决译码对于中等长度的码 特别有效，并能在很宽的信噪比范围内得到很大的性能改善【1 5 1 。1 9 6 3 年，梅西( m a s s y ) 提出了基于码元错误概率最小的a p p 译码( 后验概率译码) 。它实质上是将门限译码算法 推广至软判决，是一种近最优的译码方法。在此基础上，韦尔登( w e l d o n ) 于1 9 7 1 年又提 出了重量删除译码算法( w e d 算法) 以及鲁道夫( r u d o p h ) 于1 9 7 6 年提出了逐位译码算法 ( h r 算法) 。后来，f o r n e y 提出了广义最小距离译码( g m d 译码) ，它是一种近似a p p 译码。 1 9 6 6 年，f o r n e y 将分组码和卷积码结合起来，提出了级联码( c o n c a t e n a t e dc o d e s ) ， 作为一种实现具有很大的组长和高的纠错能力的码。信道编码中，码长的增加将会使译 码错误概率减小，但是译码的复杂度和计算量也将增加，而级联码克服了性能与复杂度 的矛盾。一般内码多采用的是卷积码，外码采用r s 码，同时在内外码间加入交织器， 进一步防止突发错误。对于它的译码，一般内码采用软判决译码，外码采用硬判决译码 【1 6 】。但是，如果级联码的外码也采用软判决译码，它的系统性能将得到进一步改善。这 就是软输出译码，它的算法主要有逐符号m a p 类算法和修正v a 类算法，女n s o v a ( s o f t o u t p u t v a ) 等。 m a s s e y 在1 9 7 4 年根据信息论，证明了将编码与调制作为一个整体考虑的最佳设计， 可以明显的改善系统的性能。1 9 8 2 年，昂格尔博克( u n g e r b o e c k ) 提出了卷积码与调 制相结合的网格编码调制( t c m ) 【 】，它的显著优点便是不需要增加传输带宽或者降 低信息传输速率便可以获得可观的编码增益。i m a i 于1 9 7 7 年提出的多层编码( m l c ： m u l t i l e v e lc o d i n g ) 方案，从广义的编码结构看，t c m 是m l c 的一种特殊情况。 1 9 9 3 年，b e r r o u 等在i c c 9 3 会议上提出了t u r b o 码，它引入了随机编码的思想，将 卷积码与位随机交织器结合在起，同时采用软迭代译码来逼近最大似然译码。仿真表 l 绪论硕+ 论文 明，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 码的译 码复杂度高，译码延时大，不适合新一代移动通信系统的要求。1 9 9 4 年r p y n d i a h 等人 受迭代译码思想的启发，在c h a s e 算法【1 8 1 的基础上提出了线性分组码的软输入软输出 ( s i s o ) 算法，并将迭代的方式应用于乘积码，形成 t u r b o 乘积码( t p c ) f 1 9 1 。 结合上面的阐述，我们可以将纠错编码大致可以划分成三个阶段1 2 0 j ： 第一阶段( 1 9 4 9 年一6 0 年代初) ： ( 1 ) 奠定了线性分组码的理论基础 ( 2 ) 提出了可以纠正多个随机错误的b c h 码。 ( 3 ) 提出了卷积码的序列译码。 第二阶段( 6 0 年代初一6 0 年代术) ： ( 1 ) 提出了门限译码( 二进制情况的大数逻辑译码) 。 ( 2 ) 提出了b c h 码的迭代译码算法。 ( 3 ) 提出了卷积码的序列译码和维特比译码。 第三阶段( 7 0 年代初一现在) ： ( 1 ) 发现了一类渐进性z 月北匕1 4 k e i 好的分组码，如g o p p a 码。 ( 2 ) 迅速发展了实用的编译码技术，如分组码的软判决译码。 ( 3 ) 发现了一些接近香农极限的好码，如t u r b o 码。 ( 4 ) 许多关于纠错码的著作发表。 1 1 3t u r b o 乘积码的优点及与其他纠错码的性能对比 自从1 9 9 3 年提出t u r b o 码以来，它已经成为信道编码的研究热点。t u r b o 码不但在抵 御加性高斯白噪声方面性能优越，而且具有很强的抗衰落、抗干扰和抗突发错误能力， 其纠错性能接近s h a n n o n 极限。被广泛的应用于深空通信、无线通信等领域2 1 1 2 2 1 。 但是t u r b o 码交织器延时大，译码复杂度高，不适合并行处理。t u r b o 乘积码在译码 性能上接近t u r b o 码，但是具有较高的编码效率，能够避免t u r b o 卷积码的“地板效应 。 当采用q p s k 调制时，误码率为1 0 _ 5 时，研究表明，t p c f l 皂够提供至少6 d b 的编码增 益。t p c 码增强的e 。n 。性能意味着使用t p c 编码的通信系统可以减少链路的功率需求， 提高数据速率或采用高阶的调制方式而不使用过量的带宽。 当信道是瑞利衰落信道时，与r s 码相比，t p c 码若采用b p s k 调制方式，可以提供 l l r s 码多1 0 d b 的编码增益。而且随着t p c 码迭代次数的增加，性能更加优越。 一般前向纠错技术中，当编码增益提高时，其处理时延也会增加。而t p c 码作为一 种全新的、完全独立的前向纠错编码，使用恰当的编码就可以避免如r s 方式复杂的交 织与解交织。t p c 码的解调器和解码器一直保持同步状态，克服了r s 码的“软膝效应”， 4 硕士论文t p c 编译码算法研究与实现 这在衰落环境中非常有益。而且t p c 克服了传统编码方式的误码平层效应，误码率随信 噪比增加下降很快，形成明显的“瀑布区”。 b c h 码、r s 码、卷积码( v i t e r b i ) 、级联码( r s - v i t e r b i ) 、t c c 和t p c 都是常用的纠错 码，其性能对比列于表1 2 3 1 。 表1t p c 与其他纠错码的性能对比 性能 t p cr sv i t e r b ir s v i t e r b it c c l e 3 l e - 4 42415 5334 增益 l e 6 l e 72 是基于某个聊次本原多项式g f ( 2 肌) 扩域的元 素。编码时，每m 个信息比特映射成一个g 进制码元，通常取q = 2 ”以便于与具有4 ，8 ， 1 6 ，3 2 ，点数星座的p s k 或q a m 调制信号集相匹配。目前采用最多的是m = 8 ， i 1 q = 2 5 6 进制的r s 码。 r s 码的每个码元均取自g f ( q ) ，其生成多项式的根也在g f ( q ) 上。它的生成多项式 表示成 g ( x ) = ( x - a ) ( x 一口2 ) ( x 一口2 ) f 2 7 ) = 一x ” + 一t l x ”一一1 + + q x + 口0 、7 式中，g ( x ) 的各次系数a i ( 待0 以一k o ，1 ，a ，0 29 9 a q - 2 ) ) 。 r s 码的参数为码长胛= g 一1 ，校验元位数，= l l - - k = 2 t ，最小距离a m i 。= n - k - 1 。r s 码是 9 2t p c 码的编译码原理 硕士论文 一种极大最小距离( m d c ) 码。r s 码的纠错能力与m d c 码一样已经发挥到了极限。r s 码存在一种有效的硬判决译码算法，使得该码能够应用于许多需要长码的场合。g 进制 r s 码的二进衍生码具有良好的抗突发差错能力。由于上述优点，r s 码得到了广泛的应 用。 2 2 2 4 卷积码 卷积码是一个有限记忆系统，它与分组码类似也是将信息比特序列分隔成长度为k 的一个分组，所不同的是某一时刻的编码输出不仅与本组的信息数字有关，还与前面若 干组( 三个) 的信息数字发生关系。称l + i 为约束长度，它的编码器示意图见图2 3 【2 5 1 。 卷积码是将发送的信息序列通过一个线性的、有限状态的移位寄存器而产生。二进 制数据移位输入到编码器，沿着移存器每次移动k 比特位。每一个k 比特长的输入序列 对j 立 图2 3 卷积码的编码器 卷积码的纠错能力随着的增加而增大，但是差错率随着的增大而呈指数下降。 由于卷积码利用了各信息组之间的相关性，卷积码中每个信息组的信息元个数k 和对应 的子码的码长n 通常比分组码要小，但在同样的码率，和设备复杂性下，卷积码的性能 一般要优于分组码。分组码有严格的代数结构，但是卷积码至今都没有找到严密的数学 手段把纠错性能与码的结构十分有规律地结合起来。 卷积码的译码分为代数译码和概率译码两种。代数译码方法是基于码的代数结构， 利用生成矩阵和监督矩阵来译码。其中，最重要的代数译码是大数逻辑译码。目前常用 的是概率译码，比较有代表性的是维特比( v i t e r b i ) 译码。维特比( v i t e r b i ) 译码效率 高，速度快，译码简单。但是复杂度随着约束长度m 成指数增加。因而，维特比译码 不适合约束长度太大的码。 l o 硕士论文t p c 编译码算法研究与实现 2 3t p c 译码原理 对于图2 4 所示的数字传输系统，如果发送端0 、l 码元是等概率的，信道干扰为 高斯白噪声干扰，采用的是p s k 调制，则接收端的解调器对接收信号y 可按下述规则 进行解调： 图2 4 一般数字传输系统 相应的概率分布情况如图2 5 所示，译码器直接根据判决门限判决后，输出0 、1 码元 进行译码，该译码过程也叫做硬判决译码。 一 、 、，、巳。 l r ! ；l 蹦一|1。7o l o i o l o l|l ooll0oll 图2 5p ( y lo ) 、p ( y1 ) 及8 阶量化图 上图的判决门限为o ，因此解调器将将和m 判决为1 ，但是从图中可以看出，将 “m 判决为1 要比将“判决为1 更加可靠。如果将l y l 作为相应码元的信任值，那 么可以看出该码元的绝对值越大，判决结果要越可靠。这个y 通常是模拟量，为了便于 实现，可以将其量化【2 6 。 硬判决即解调器供给译码器的码元只取0 、l 两个信息，这种判决会损失掉接收信 号包含的有用信息。因此，解调器可以充分利用码元的信任值这一重要的信息。解调器 在对每个码元作硬判决译码的同时，输出码元的信任值到译码器，然后译码器再按照一 定的规则进行译码，这将极大得改善译码性能。这种译码方法称之为软判决译码。如果 译码器根据每个码元的信任量，按照每个码元错误概率最小准则进行译码，叫做逐位软 判决译码。如果译码器根据根据每个码元的信任值，按照使码字错误概率最小的准则进 行译码，叫逐字软判决译码 2 6 1 。c h a s e 算法是典型的逐字软判决译码。 2t p c 码的编译码原理硕士论文 2 3 1 代数译码 在介绍c h a s e 算法译码之前，我们先介绍下代数译码。代数译码也就是硬判决译码， 以线性分组码c ( n ，k ，d ) 为例，设其一致校验矩阵为h ，c ( n ，k ，d ) 经信道传输后对应的码 字为尺。代数译码器的主要任务就是设法从r 中得到正确的错误图样e ，然后计算估值 码字c 。 具体的译码步骤如下： ( 1 ) 首先根据公式s = r h r 计算伴随式s ； ( 2 ) 如果s = 0 ，则传输无误。如果s 0 ，则有e 0 。根据伴随式s 找出错误图 样e ； ( 3 ) 进行纠错，估计码字为c = r o e ，若c = c ，则译码正确，否则译码错误。 2 3 2c h a s e 算法译码 2 3 2 1c h a s e 译码算法【2 3 】 假设在二元a w g n 信道中发送线性分组码c ，其参数为( ，2 ，七，6 ) ，经过映射： 0 一一1 ，lj + 1 后，得到发送码字u ( u l ，l l i ，) ，经过a w g n 的接受码字为 r = ( ，乃，吒) 可以表示为 r = u + g( 2 8 ) 其中，g = ( 蜀，g t ，g 。) 是标准差为。的加性高斯白噪声。 根据最大似然算法，最优的判决码字d = ( 碣，珥，吃) 为 d = c 矿i r c 1 2 l r c 7 1 2 v l e 1 ，2 】，f ( 2 9 ) 其中，c = ( q t ，巧，) 为c 的第f 个码字，刀与f 之间的欧氏距离为 l 尺一c f = ( 乃一巧) 2 ( 2 1 0 ) 从上面的公式可以看出，我们需要劳举所有可能的码字，才能得到最优判决码字。 译码的复杂度随着k 呈指数增加。 c h a s e 算法是一种低复杂度的次最佳算法，基本思想是认为接收序列中可信值较低 的位置相应的出错概率比较大，根据每个码元的信任值，找到最不可靠位元，产生试探 序列，从中挑选与接收序列有最近软距离的码字即译码输出。下面以c h a s ei i 算法为例 详细介绍。 假设发送信号为u ，接收信号为尺，对此信号进行最大似然译码，在高信噪比的情 况下，码字d 以很大的可能性位于以r 的硬判决码字】厂= ( m ，m ，儿) 为球心，( 5 1 ) 为半径的球内，其中y t = 0 5 ( 1 + s g n ( r t ) ) o ，1 ) 。c h a s e 算法的译码步骤为： 1 2 硕士论文t p c 编译码算法研究与实现 ( 1 ) 根据尺找到y 中p = 6 2 】个具有最低可信值的比特位。 】，的可信值定义为 为 ( m ) = 乙【所p ， e 勺j = ：+ 一l 。l i r 。j r ) ( 2 1 1 ) 其中分子部分可以表示为 尸( 巳= + l 。) = ! 量! 三铲 ( 2 2 ) 若信源是等概率的，即满足p 巳= + l - - p r e j = - 1 ) o 5 ，则式( 2 1 2 ) 可以表示 在a w g n 信道下 尸(巳=+l。)=乏i：i；i_：p：(：rs了：ejjj=丽+1) c 2 3 ， 代入式( 2 1 3 ) 可得 批刊) = 荷1 七2 f ，t 型a1 j 2 仁 p c 勺= + b ，= ：_ ( j 热c 2 _ 5 ， p c 勺= 一l 。，= ：_ ( 三鹣 c 2 6 ， 综上可得 ( 巧) = i n 所( 字 r ，+ l 、 所l j 归一化后，得乃的可信值定义为l ，：，| 。 f ，2 、 2 l j ，：， ( 2 1 7 ) 学 2t p c 码的编译码原理 硕士论文 ( 2 ) 产t - l q = 2 p 个试探错误图样p 。 根据第一步，得到y = ( y l ，乃，蚝) 中每个位元的可靠值，从中挑选p 个可信 值最低的位元。注意：p 小于信息比特数后。最不可靠位元的选择以b p s k 为例： u e c l $ l o n 日9 u n d a 坷 oyl 6 - 。1 一 一r e g i o n 7 1 71 r e g i o nz 2 6 l ，b 一写 一房 7