（通信与信息系统专业论文）多重级联奇偶校验码的fpga实现.pdf

中文摘要 摘要 自1 9 4 8 年香农提出并证明了著名的有扰信道编码定理以来，人们一直在努力 寻找一个逼近香农理论极限的好码。1 9 9 3 年t u r b o 码的出现则为彻底地解决这一 问题带来希望。最初提出的t u r b o 码是一类并行级联卷积码，虽然其理论和实际 应用都发展的比较成熟，但由于它本身的一些缺点，例如码率较低，译码复杂度 较高，使得其开发利用有了一定的局限。目前t u r b o 码的概念已经有了很大的拓 展，其子码不仅可以是卷积码，而且也可以是分组码；级联形式不仅可以并联， 也可以串联，甚至两者混合；由多个子码而形成的级联码称为多重级联码。并行 级联分组码也已经显示出接近香农理论极限的卓越性能，而其译码采用的也是一 种相对简单的迭代译码技术。本文所研究的多重级联奇偶校验码就是这种类型的 具有很强纠错能力的差错控制编码。它是以非常简单的奇偶校验码作为子码来构 造多重( 多维) 级联分组码。除了编码，译码简单外，多重级联奇偶码还具有很 多优点：较高的编码效率，相对较低的编码，译码复杂度，灵活可变的输入数据 长度、码率等优点。这些优点都是原先t u r b o 码所不具备的，因此多重级联奇偶 码特别具有理论研究和开发应用的价值。 本文工作主要分为三部分：第一本分主要介绍t u r b o 码和级联分组码编码技 术，阐述了m a p ( 最大后验概率译码) 译码方法和迭代译码思想；第二部分研究 了多重级联奇偶校验码的编码和译码方法，深入探讨和分析了两种的编译码结构 以及对应的m a p 和m a x l o g m a p 迭代译码算法；第三部分着重研究了多重级联 奇偶校验码的f p g a 实现，在前两部分理论研究的基础上，提出了适合f p g a 实 现的4 p c s p c ( 四维并行级联奇偶校验) 码的译码方案。完成该码的编码器和译 码器的f p g a 实现，并对该方案做了相应的验证。该编码器和译码器适合用于高 速率的现代通信技术，特别是硬件资源较丰富的环境。 关键词：t u r b o 码；多重级联码；n a p 译码；迭代译码；f p g a 实现 英文摘要 t h ef p g a i m p l e m e n to fm u l t i - d i m e n s i o n a lc o n c a t e n a t e ds i n g l e p a r i t yc h e c kc o d e s a b s t r a c t s i n c es h a n n o np r o p o s e da n dp r o v e df a m o u sc o d i n gt h e o r e mi n 1 9 4 8 ，p e o p l eh a v e b e e nm a k i n gg r e a te f f o r t st ol o o kf o rak i n do fg o o dc o d e ，w h o s ep e r f o r m a n c ec o u l d a p p r o a c ht ot h es h a n n o n st h e o r e t i c a ll i m i t i n1 9 9 3 ，t h ee m e r g e n c eo ft u r b oc o d e b r o u g h tt h eh o p ef o rt h o r o u g h l ys o l v et h i sp r o b l e m i n i t i a l l y ，t u r b oc o d ei sak i n do f 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 n a lc o d e s ，a l t h o u g hi t h a v em a t u r ed e v e l o p m e n to f t h e o r e t i c a la n dp r a c t i c a la p p l i c a t i o n s ，t h e r ea r es t i l ls o m es h o r t c o m i n g so fi t so w n ，s u c h a sl o wc o d i n gr a t ea n dh i g hc o m p l e x i t yo fd e c o d i n g ，w h i c hm a k et u r b oc o d eh a sa c e r t a i nl i m i t a t i o n so nd e v e l o p m e n t a tp r e s e n tt h ec o n c e p to ft u r b oc o d eh a v eag r e a t e x p a n s i o n ，i t ss o nc o d ei sn o to n l yt h ec o n v o l u t i o n a lc o d e ，b u ta l s ob l o c kc o d e ；t h ef o r m o fc o n c a t e n a t e dc a nn o to n l yp a r a l l e lb u ta l s os e r i e s ，a n de v e nt h et w om i x e d t h e c o n c a t e n a t e dc o d ec o m p o s e dw i t hm u l t i s o nc o d e si sn a m e da sm u l t i d i m e n s i o n a l c o n c a t e n a t e dc o d e t h e 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 eh a sb e e ns h o w nt oy i e l d r e m a r k a b l ep e r f o r m a n c ec l o s et ot h e o r e t i c a ll i m i t s ，y e ta d m i t t i n gar e l a t i v e l ys i m p l e i t e r a t i v ed e c o d i n gt e c h n i q u e t h em u l t i p l ec o n c a t e n a t e dp a r i t yc h e c k - c o d es t u d i e di n t h i sp a p e ri st h i st y p eo fc o d e ，w h i c hh a ss t r o n ge r r o r c o r r e c t i n ga b i l i t y i tt a k e st h ev e r y s i m p l ep a r i t yc h e c kc o d ea ss o nc o d et oc o n s t r u c tm u l t i - d i m e n s i o n a lc o n c a t e n a t e d c o d e i na d d i t i o nt o s i m p l ee n c o d i n ga n dd e c o d i n g ，m u l t i p l ec o n c a t e n a t e d p a r i t y c h e c kc o d ea l s oh a sm a n ya d v a n t a g e s ：h i g hc o d i n gr a t e ，r e l a t i v e l yl o we n c o d i n g , d e c o d i n gc o m p l e x i t y ，f l e x i b l ev a r i a b l el e n g t ho ft h ei n p u td a t a ，a n dc o d er a t ee t c t h e s e a d v a n t a g e sw h i c ht h eo r i g i n a lt u r b oc o d e sd 0n o th a v e ，a r ee s p e c i a l l ym e a n i n gt ot h e t h e o r e t i c a ls t u d ya n dp r a c t i c a la p p l i c a t i o n t h i sp a p e rm a i n l yp r e s e n t st h r e ep a r t s ：t h ef i r s tp a r ti n t r o d u c e st u r b oc o d e sa n d c o n c a t e n a t e db l o c kc o d i n gt e c h n o l o g y ，e x p a t i a t et h em a p ( m a x i m u map o s t e r i o r i p r o b a b i l i t y ) d e c o d i n gm e t h o d sa n di t e r a t i v ed e c o d i n gt h o u g h t ；t h es e c o n dp a r ts t u d i e s e n c o d i n ga n dd e c o d i n gm e t h o d so ft h em u l t i p l ec o n c a t e n a t e dp a r i t y - c h e c kc o d e ， d e e p l yd i s c u s s e d a n da n a l y z e dt w od i f f e r e n tc o d e d e c o d es t r u c t u r ea n dm a p ， m a x l o g m a pi t e r a t i v ed e c o d i n ga l g o r i t h mr e s p e c t i v e l y ；t h et h i r dp a r tf o c u s e so nt h e 英文摘要 i m p l e m e n to fm u l t i p l ec o n c a t e n a t e dp a r i t y - c h e c kc o d e so nf p g a o nt h eb a s i so f t h e o r y s t u d i e di nt h ef o r m e rt w op a a s ，p r o p o s e dt h es c h e m ef o r t h e4 p c s p c ( 4 一d i m e n s i o n a lp a r a l l e lc o n c a t e n a t e dp a r i t y c h e c k ) c o d ew h i c hi ss u i t a b l ef o rt h ei m p l e m e n t a t i o no nf p g a , c o m p l e t et h ee n c o d e ra n dd e c o d e r si m p l e m e n to nf p g aa n d m a d et h ec o r r e s p o n d i n gt e s to nt h ep r o g r a m p r o p o s e db e f o r e t h ee n c o d e ra n dd e c o d e r i so p t i m i z e df o rh i g h 。s p e e dm o d e mc o m m u n i c a t i o n st e c h n o l o g y ，p a r t i c u l a r l yi nt h e h i g h e rh a r d w a r er e s o u r c e se n v i r o n m e n t k e yw o r d s ：t u r b oc o d e s ；m u l t i d i m e n s i o n a lc o d e s ；m a pd e c o d e ：i t e r a t i v e d e c o d e ；f p g ai m p l e m e n t a t i o n 大连海事大学学位论文原创性声明和使用授权说明 原创性声明 本人郑重声明：本论文是在导师的指导下，独立进行研究工作所取得的成果， 撰写成博士硕士学位论文：垒重缝珐壹倡撞验旦的壁q 塞理：。除论文中 已经注明引用的内容外，对论文的研究做出重要贡献的个人和集体，均已在文中 以明确方式标明。本论文中不包含任何未加明确注明的其它个人或集体已经公开 发表或未公开发表的成果。 本声明的法律责任由本人承担。 论文作者签名：陬办1 c ，则不存在能够实现无 差错传输的编泽码方式。近些年来，随着通信技术的发展和实际应用的不断增加， 研究者们一直努力在寻找一种更能逼近香农理论极限的信道编码方式。 最早出现的一种信道编码是一类纠单个错误的分组码- - h a m m i n g 码，它是由 h a m m i n g 于1 9 5 0 年提出的，这种码的系统性能与香农极限之间差距很大。直到 1 9 5 9 年，由b o s e ，r a y c h a u d h u r i ，h o c q u e n g h e m 找到一大类可以纠正多个差错的 码一b c h ，以及由r e e d ，s o l o m o n 找到的一类非二进制纠错码- - r s 码，才丰富了 信道编码理论。目前这些码类仍然处于应用之中。其后，卷积码的提出以及v i t e r b i 译码算法实现，使得信道编码技术在实际中得到了极其广泛的应用。1 9 9 3 年， c b e r r o u 等人提出的t u r b o 码，并给出如下的仿真结果用：在a w g n 信道下，当 噪声比大于或等于0 7 d b 时，一个码率为1 2 的t u r b o 码经过数次迭代后其误比特 率小于或等于1 0 ，这一逼近香农极限的优异性能引起了信息与编码学的轰动。 t u r b o 码的出现，给信道编码带来了革命性的突破。此后，信道编码技术同趋成熟， 给通信等领域的发展带来了无限生机。 近些年来，原先由g a l l a g e r 提出的l d p c 码重新被人们研究，发现其也具有 逼近香农极限的卓越性能。在码率为1 2 ，码长为1 0 7 b i t ，在a w g n 信道下对二元 l d p c 码进行性能仿真，发现其与香农极限只差0 0 1 d b 钔。至此，信道编码理论又 有了重大进展。目前，t u r b o 码，l d p c 码以及迭代译码已经成为了当今信道编码 领域研究的重点。 信道编码的发展已经经历了5 0 多年的历史。在理论方面，它沿着香农编码定 理的方向不断地发展和完善；尽管在实际应用方面还有些欠缺，但是随着数字通 信技术的不断提高，它的应用也将越来越广泛。 本文所讨论的多重级联奇偶校验码，它属于t u r b o 分组码的一种，译码方法 也是采用当今流行的t u r b o 迭代译码思想，其性能跟t u r b o 码接近，具体的编码和 译码方法将在后面章节晕详细介绍。 多重级联奇偶校验码的f p g a 实现 1 5 本文所做的工作和内容安排 本文所研究的范围有tt u r b o 码以及级联分组码的研究，多重级联奇偶校验 码编码和译码技术的研究以及其f p g a 的实现。全文的内容具体安排如下： 第二章主要介绍了信道编码的基本知识，主要介绍信道编码的思想，分类， 然后着重介绍了线性分组码的理论知识，最后给出了最大似然译码和最大后验概 率译码的定义。 第三章主要介绍了几种高性能的信道编码译码技术，包括t u r b o 卷积码，t u r b o 分组码，r a 码。具体介绍了它们共同的迭代译码思想，此外还介绍了m a p 算法 在t u r b o 卷积码和t u r b o 分组码中的应用。 第四章主要介绍了多重级联奇偶校验码的编码和译码方法。提出了两种编码 和译码的结构和方法。 第五章主要介绍了多重级联奇偶校验码的f p g a 实现。主要提出了针对 4 - p c s p c 这一类型码的译码结构和方法，并将这种方法进行f p g a 的实现。最后 提出了一些需要改进的地方。 第六章概括了全文了主要结论和研究的成果，并对未来的研究提出了一些个 人的看法。 第2 章信道编码技术理论基础 第2 章信道编码技术理论基础 2 1 信道编码的基本思想和分类 2 1 1 信道编码的基本思想 信道编码是为了保证通信系统的传输可靠性，克服信道中的噪声和干扰，而 专门设计的一类抗干扰的技术和方法。它根据一定的规律在待发送的信息码元中 加入一些必要的监督码元，在接收端利用这些监督码元与信息码元之间的规律， 发现和纠正差错，以提高信息码元传输的可靠性。信道编码的目的是试图以最少 的监督码元为代价，以换取最大程度的可靠性的提高。 下面举例来说明信道编码的思想。 用图1 1 所示的模型来讨论二进制序列通过该系统时所发生的情况。假设从信 源发送出字母a ，它的二进制序列可表示为1 1 0 0 0 ，以基带信号传输，经过发射机 调制后，送往信道的已调信号如图2 1 所示。 o s ( t ) mt 。 人人 7 o 图2 11 1 0 0 0 发送的已调信号 f i 9 2 j lm o d u l a t e ds i g n a l “11 0 0 0 t r a n s m i t t e d s ( t ) 仆、t 。 。 一f 7 幽2 2 接收端收到的失真信号波形 f i 9 2 2d i s t o r t i o ns i g n a lr e c e i v e d 山于信道的干扰，接收端收到信道输出的信号产生了失真，如图2 2 所示。这 些失真信号由接收机进行判决时，第一，二，四，五个码元的波形失真都不太大， 多重级联奇偶校验码的f p g a 实现 可以很容易的进行判决，得到1 ，l ，o ，o ；但是第三个码元产生了严重的失真， 判断很困难，这时有以下三种判决方法：一是硬判决，直接判为o 或1 ；另一种是 对该码元不作判决，而输出一个未知的信号“x ”，称其为删除符号；第三种方法 是输出一种有关该码元的信息，例如关于0 和1 的后验概率或似然函数，这种判 决方法称为软判决。当然软判决方法性能较好，但实现起来比较复杂。 这里以重复编码来简单地阐述信道编码在相同的信噪比情况下为什么会获得 更好的系统性能。设发送的信息0 ，1 是等概率出现的，采用2 p s k 调制方式，由 此得出最佳接收的系统比特误码率为： 只毛叫罔 现在假设，1 0 - ，如果将信息0 编码成0 0 ，信息1 编码成1 1 ，仍然采用上 述系统，则在接收端可以做出如下判断：如果发送的是0 0 ，而收到的是0 1 或1 0 ， 此时就知道发生了错误，要求发送端重新发送，直到传送正确的为止，只有接收 到1 1 ，我们才错误地认为当前发送的是1 。因此在这种情况下发生译码错误的概 率是o - 5 乎；同理，如果发送的是1 1 ，只有接收到o o 时才可能发生错误译码，所 以在这种情况下发生译码错误的概率也是o 5 乎。所以采用0 0 ，1 1 编码的系统比 特误码率为牙，系统的性能明显提高。如果在上例中，将0 ，1 采用0 0 0 0 0 ，1 1 1 1 1 编码，在接收端采用如下的译码方法，每收到5 个比特译码一次，采用大数译码 判决，即5 个比特中0 的个数大于1 的个数译码成0 ，反之译码成1 ；不采用检错 重发方式。那么，这种编码方式就成了纠错编码。由于传输错误，当接受端收到 1 1 0 0 0 ，1 0 1 0 0 ，1 0 0 1 0 ，1 0 0 0 1 ，0 1 0 1 0 ，0 1 0 0 1 ，0 0 l1 0 ，0 0 1 0 1 ，0 0 0 11 中的任何一 种时，都自动译码成0 0 0 0 0 。 2 1 2 信道编码的分类 传输信道中常见的差错分为以下三种： 随机错误：错误的出现是随机的，一般来说错误出现的位置是随机分布的， 第2 章信道编码技术理论基础 也就是说各个码元是否发生错误是相互独立，但通常不是连续的出现错误。这种 情况一般是由信道的加性随机噪声引起的。因此，将具有此特性的信道称为随机 信道。 突发错误：错误的出现是一连串的，通常在一个突发出错持续时间内，开头 和末尾的码元总是错误的，中间的某些码元可能错也可能对，但错误的码元相对 比较多。这种错误通常发生在移动通信中信号在某一段时问内发生衰落；汽车发 动时电火花干扰；光盘上的条划痕等情况下，这种信道称之为突发信道。 混合错误：也就是既有突发错误又有随机错误的情况，这种信道称为混合信 、厶 追。 数字通信系统中，利用纠错码或者检错码进行差错控制的方法有以下几种： 检错重发( a r q ) ：在接收端根据编码规则进行检查，如果发现规则被破坏， 则通过反向信道通知发送端重新发送，直到正确接受为止。采用这种差错控制方 法需要具有双向信道，优点是只要少量的多余码元就能获得极低的输出误码率， 检错码基本上与信道的差错统计特性无关，成本和复杂度比较低。缺点是需要反 馈信道，效率低。a r q 有不同的重发机制：可以等待重发，x 2 5 协议的滑动窗口 选择重发。 前向纠错( f e c ) ：接收端不仅能在收到的信号中发现有错码，而且还能够纠 错。对于二进制系统来说，如果能够确定错码的位置，就能够纠正它。这种方法 不需要反馈信道，也不存在由于反复重发而延误时间，实时性好，但随着纠错能 力的提高，编码和译码设备相对复杂。 混合纠错方式( h e c ) ：发送端发送的码不仅能够检测出错误，而且还具有一 定的纠错能力。接收端接收到信号后，首先进行检测错误，如果在纠错能力的范 围之内，则自动进行纠错；如果错误超过了纠错能力，但能检测出来，那么就通 过反馈信道，要求重新传送出错部分的信息。这种差错控制方式在一定程度上克 服了前两种方式的缺点，并且能够达到较低的误码率，因此在实际应用中越来越 广。 根据差错控制编码的不同功能可以分为：纠错码，检错码和纠错检错码。根 多匝级联奇偶校验码的f p g a 实现 据信息位和校验位的关系可分为：线性码和非线性码。根据信息码元和监督码元 的关系可分为：分组码和卷积码。还有其他的分类方法，这罩就不一一介绍。 2 2 线性分组码 2 2 1 分组码 差错控制编码的码型按照对信息码元处理方法的不同，可以分为分组码和卷 积码两大类。分组码是把信息源输出的信息序列，以k 个码元划分为一组，通过编 码器把这k 个信息元按照一定的规律产生厂个监督码元，最后输出长为以= k + ，的 一个码组，所以每一个码组总的监督码元仅仅与本组的信息码元相关，与其他码 组无关。通常将上述的分组码表示为( n , k ) ，刀表示码长，k 表示信息位，码率表 示为r = 七n 。 分组码对每段长度为七的信息处理，得到一个分组码，然后再由这些分组码组 成长度为以的序列：( 厶- 1 厶一2 ，c o ) ，这个序列就叫做码字。对于一个刀长的序列 来说，可能的排列总共有2 一中，而( 玎，七) 分组码的码字集合只有2 七种。因此，分组 码的编码就规定：从? 种排列中选取矿个码字，被选取的为许用码组，否则称为 禁用码组。 2 2 2 汉明距离 一个码字c 中非零码元的个数，称为该码字的汉明重量，用( c ) 表示；两个 码字z ，y 之间，对应位置墩值不同的个数，称为这两个码字的汉明距离，用d ( x ，y ) 表示。在一组分组码中，任意两个码字之间的距离最小值，称为该分组码的最小 汉明距离，用表示。汉明距离是分组码的一个非常重要的参数，汉明距离越人， 同组码字之间的差别也就越大，码的抗干扰能力就越强，在相同的译码方法f ， 错误概率也就越小。 根据上面所讲的，码率j r 和最小汉明距离d o 是分组码最重要的两个参数。其 第2 章信道编码技术理论基础 基本编码思想就是构造出一定码率r ，而使d o 尽可能大的码类；或者是d o 一定， 构造出使j r 尽可能高的码类。 分组码依据其最小汉明距离，具有以下的定理： ( 1 ) 如果码的最小距离d o 乏e + 1 ，则该码可以检测出所有不多于e 个错误； ( 2 ) 如果码的最小距离d o 之2 t + 1 ，则该码可以纠j 下所有不多于f 个错误； ( 3 ) 如果码的最小距离如已+ “l ( p f ) ，则该码可以纠正所有不多于f 个错 误，并能检测出t + 1 到e 个错误； 2 2 3 分组码的生成矩阵和校验矩阵 对于【咒，七 分组码的编码方法就是在刀维线性空间k 中，找出满足一定要求的， 由2 个向量组成的七维线性子空间。一个分组码亭中有2 个信息组，表示为： u = “o ，甜1 一，一1 ) ，还有与之对应的2 七个码组，表示为：c 一 c o ，c 1 ，一1 ) 。因 为分组码是一个k 维的子空间，就一定存在k 个线性独立的向量：g o ，g l 一，g 七一l 能 够生成该分组码亭。u 和c 对应的映射关系很明显地可以表示为： c 置u o g o + “l g l + + l 七一l g 七一1 ( 2 1 ) 表示成矩阵形式为：c ；u g ，其中 g g ol i g ll i l l g j 七跏 这里的g 就是分组码的生成矩阵。 g f l 中各个向量是线性独立的，所以g 的秩为七。对g 进行行变换和列变换 后，g 就可以变成如下的形式： g - ，l e 多重级联奇偶校验码的f p g a 实现 其中i 是单位阵。 子空间亭具有厅一七维的零空问手，可以由以下刀一七个线性独立的向量生成： j i l o ，啊，一七一l 。对于属于手的任一个，都有：c 吩= o , v i e o , n k 一1 ，于是得到： c h r - - o , ( c c e ) ( 2 2 ) 其中h = 这罩的日就是分组码的监督矩阵。 刭帅 啊 l 七一li f 。一i i x 。 对于一个( 万，k ) 的线性分组码亭来说，假设发送的码字为ci ( c o ，c l ，厶一1 ) ， 信道产生的错误图样为e ；( ，q ，一1 ) ，那么接收到的码组为：y = c o e ，如果 h y r = 日( c o p ) r - h c ro 舰r = 0 ( 2 3 ) 得到发送的码字c 。现在定义一个向量s r = 协r h e r 即s = e h r ，由此可以看出， 向量s 与c 无关，仅与e 有关，这反映了信道干扰的情况。如果能够从s 中得到p ， 利用c = y e 就可以恢复原先发送的码字。因此，译码的任务就转化为对向量s 的 研究。这罩我们把s 叫做y 的校币子或伴随式。 - - 4 6 ，3 系统的分组码，其典型的校验矩阵为： 日2 三季三三；】 第2 章信道编码技术理论基础 可以看出该码的最小汉明距离d o 一3 ，可以纠讵一个错误或者是检出2 个错误。接 收机在接收到码组y 后，计算y 的伴随式sz y h r 。若没有发生错误，则显然s = o 。 若发生1 个错误，则s 与h r 的一个行向量相同。如果s 与日r 的第f 个行向量相同， 则说明y 中第i 个码兀错误。若发生1 位错误或者2 个错误，则s 必然不为0 ，如 此接收端根据伴随式进行判断译码。 2 3 最大后验概率译码和最大似然译码 信息在信道的传输过程中由于受到噪声和干扰的影响，会发生错误。错误概率 与信道的统计特性，译码过程以及译码方法有关。假设信道输入的码字集合为 u = u 【f 】，i = 1 , 2 ，k ) ，编码后输出的序列为c = c j ，j = j ，2 ，) ，如果对应 每一个输入序列u f 】都有唯一确定的函数f ，使得c - ， 与u 钼存在着一一对应关 系，即： f ( c 巾一u f ，i = 1 2 ，k ；j ；1 ，2 ， ( 2 4 ) 那么就称这样的函数为该编码的译码规则。 确定译码规则之后，如果编码信道输出c 歹】，则一定可以译码为u f ，如果信 道输入刚好就是“叼，那么译码就正确；否则就是错误的。因此在译码器接收到c j 的情况下，j 下确译码的条件概率为： p ( f ( c i c = p ( u c ( 2 5 ) 错误译码条件概率为： p ( eic 一1 一p ( f ( c 圳c ；1 一p ( u f lc 巾 ( 2 6 ) 利用统计学的方法得到平均错误概率为： p e = e ( p ( e 吣】) ) = 童p ( c 】访( p 吣 ) c2 7 ) 多重级联奇偶校验码的f p g a 实现 选择译码规则的目的就是使得译码的错误概率最小，即以最小。要使p e 达到最小， 只要使得上式右边和的每一项最小，由于p ( c 巾与译码的规则没有关系，所以只 要使p ( p l c j 】) 最小，再根据式( 2 6 ) o - - t 知，只要使p ( f ( c _ ) l c ， ) 达到最大就 可以了，所以下面给出最大后验概率m a p ( m a x i m u map o s t e r i o r i ) 译码的定义。 选择译码规则f ( c 功= u j ，使之满足条件 p ( u 小2p ( u c 巾 ( 2 8 ) 那么就称之为最大后验概率译码。 最大后验概率译码是一种最佳译码策略，使用这种译码方法可以使译码性能 达到最优，但译码的复杂度也会达到最耐1 4 1 。 但通常来说后验概率很难确定，应用因此也不方便，于是利用贝叶斯公式， 将( 2 8 ) 式改为： 销2 一 汜9 ， p ( c 巾 夕( c 巾 。 于是可得 p ( c iu ，) p ( u ，) 苫p ( c 门iu f ) p ( u f ) ( 2 1 0 ) 这样就得到了最大似然m l ( m a x i m u ml i k e l i h o o d ) 译码。 当信道输入为等概率分布时，有p ( u ，) 一p ( u 棚，则可将( 2 1 0 ) 式化为： p ( c 啪u ) 乏p ( c “f ) ( 2 1 1 ) 该式中的条件概率就是信道转移概率矩阵中的元素，通常都用该式进行译码，如 果信道输入为非等概率分布，那么就只能用( 2 1 0 ) 式进行译码。 2 4 信道编码定理 1 9 4 8 年香农在他丌创性论文通信的数学理论中，首次给出了著名的信道 编码定理，从而奠定了信道编f ；i 5 的基础。下面给出信道编码定理的具体内容。 对于一个给定的有扰离散信道，假设其信道容量为c ，待传送码字的码率为 第2 章信道编码技术理论基础 尺，如果r c ，那么必然存在一个码长为挖的分组码，使得译码错误概率降至任 意小，数学表达式为： ps 一嘶( 尺)(一一)e e21 2 s lj 式中的e c ( r ) 是误差函数，有关文献给出它随着容量c 增加而增加，随着r 的增加 而减小。 从上式可以看出，译码错误概率随着甩和r ) 的增加呈指数规律递减的，因 此对于一个数字通信系统来说，为了降低误码率既，可以通过两种方法来实现： 一是增加信道容量c ，从而使( r ) 变大，这是改善了信道的特性；二就是在码率 一定的条件下，增加分组码的码长疗，带来的后果是增加了编码和译码的复杂度。 2 5 本章小结 本章主要介绍了信道编码技术的基础理论知识。首先介绍了信道编码的基本 思想和分类，然后介绍了信道编码中的最简单的一种码类一分组码，通过这种码 详细介绍了汉明距离，生成矩阵和监督矩阵的概念。接着给出了最大似然译码和 最大后验概率译码的基本定义，为后面译码算法的研究打下一些基础。本章最后 简单介绍了一下信道编码定理，这是整个信道编码理论技术研究的基础。 多重级联奇偶校验码的f p g a 实现 第3 章t u r b o 码与级联分组码 本文所讨论的多重级联奇偶校验码可以说是t u r b o 分组码的一类，也可以说 是级联码的一类，因为其编码的方式和t u r b o 类似，译码方法也采用了t u r b o 码迭 代译码的思想，但同时其码的结构是采用级联的方式得到。因此将介绍分组码， t u r b o 码的一些理论性知识，以便于更好的研究多重级联奇偶校验码。 3 1 t u r b o 卷积码 3 1 1 编码方式 t u r b o 码是在1 9 9 3 年由c b e r f o u 等人提出的，其编码器的原理框图如下： u 0 丽_ l ? 1 l 一j l 删 余 差。上 接。_ ! 器i 一圆 图3 1t u r b o 卷积码编码器 f i g3 1t h ec o d e ro ft h et u r b oc o n v o l u t i o nc o d e 上图中，t u r b o 卷积码的两个子码采用并行级联结构，在两个编码器之间加入一个 交织器。若输入编码器的信息序列为u ，它一方面经过编码器1 产生校验序列u 1 ， 另一方面对u 进行交织后，经过编码器2 产生校验序列u 2 ，将u 1 和u 2 经过删 余与原信息序列复用后完成编码。 删余单元的作用是为了调整码率，若尺l ，r 分别表示两个子码的编码效率，那 么t u r b o 码的码率满足下面方程： 第3 章t u r b o 码j 级联分组码 三：! + 三一1 一= 一一一l r rr ( 3 1 ) 在实际中，一般使信息序列全部传送，而适当的删除校验序列，在接受端对接收 序列进行内插，未被传送的比特用零补充，以保证序列的完整。复用单元完成编 码的并串转换，使输出适合信道的传输。交织器的作用就是使整个码字具有随机 码的特性，使用交织器能使突发性不可纠的错误变为随机可纠的错误，从而大大 提高编码的纠错能力。 3 1 2 译码结构 t u r b o 码没有采用简单的硬判决方式，而是充分利用了译码信息，经过反复迭 代译码从而较为准确地恢复了源信息。其译码器的基本结构如下图所示。 外信肌一赡奴 叫交织器 图3 2t u r b o 卷积码译码器 f i g3 2t h ed e c o d e r o ft h et u r b oc o n v o l u t i o nc o d e 译码 输出 上图所示t u r b o 的码译码器是由两个软输入软输出译码器串联而成，交织器 与编码中使用的交织器相同。译码器1 对分量码u l 进行译码，产生关于信息序列 u 中每一比特的似然信息，并将其中的外信息经过交织送给译码器2 ，译码器2 将 此信息作为先验信息，对分量码u 2 进行译码，产生关于交织后信息序列中每一比 特的似然信息，然后将其中外信息经过解交织送给译码器1 ，进行下一次译码。这 器决 判一 一 盐值 一 然 似 输译器：黼蝉嘴2 t 卜 h 川 息 列 一 信 序 外 验一鹫校 织r 懂 沁 值然 似一 榭矧列 叫、 k 列 列 序 序 验 据 校 数 多重级联奇偶校验码的f p g a 实现 样经过多次迭代，译码器1 和译码器2 的外信息渐趋稳定，似然比逼近于对整个 码的最大似然译码的结果，最后再进行判决，便得到信息序列的最佳估计值。 若假设t u r b o 码译码器的接收序列为y = ( x 七，砭) ，冗余信息k 经过解复用后， 分别送给译码器1 和译码器2 。则两个译码器的输入序列分别为：k 一( 邑，) 和 砭一( 以，砭七) 。为了使译码后的比特错误率最小，根据最大后验概率m a p 译码准 则，t u r b o 译码器的最佳译码方法是：根据接收序列y 计算后验概率 p ( 噍) = e ( a 七i k ，匕) 。由于这种方法对于较长的码来说，其计算复杂度比较高， 因此t u r b o 码采用了一种次优的译码方法，将上面的k ，砭分开来考虑，由两个分 量译码器分别计算后验概率p ( 畋l x ，) 和p ( 以ik ，) ，然后通过两个译码器 之问的多次迭代，使他们近似逼近于p ( 以) = e ( a 七i k ，v 2 ) 。这里的和为外 信息。其中，是由译码器2 提供的，作为译码器1 的先验信息；是由译码 器1 提供的，作为译码器2 的先验信息。下面就简单讨论一下分量码译码算法。 3 1 3 分量码的译码算法 对于一个软输入软输出的译码器来说，输入的是先验信息l ( “) 和信道输出信 g v ；输出信息又包括信息比特的外信息。( 五) ，软信息( 五) 以及编码比特的外 信息l 。( 戈) 和软信息( 戈) 。 软信息可以由对数似然比表示。设u 是随机变量，其取值范围为 + 1 ，一1 ) ，则 u 的对数似然比可以定义为： ) - l 。g 描 2 ， 其中而( h ) 为随机变量u 取值为“的概率。对数似然比( “) 就叫做随机变量u 的 软信息，其符号代表硬判决值，绝对值表示该判决的可靠性。一般情况下对数取 第3 章t u r b o 码与级联分组码 自然对数。有时候还常用条件对数似然比来作为随机变量的软信息，其定义如下： 训咖。g 描礼g 描刮小钿h ) 3 ， 此外，还需要定义一下信道的软信息值。设信道输入为x ，经过高斯信道或衰 落信道传输，采用b p s k 调制，在译码器的接收端接收的模拟值为y ，则有： m 乩g 等舞叫 在以上的传输条件下，可以得到： 竺幽兰三二! ) ! ! 兰三! ! ! e ( yi x 一- 1 ) p ( x 一一1 ) ( 3 4 ) m = o g 一 e s t 、2 咖矧比州粥， 假设经过信道后接收的序列为掣= r ，氐) ，其中心= y z ，y ) ，令s 表 e 仅l 尺，) ( d t ) = l 。g 翮 3 6 詹n ，l 叫 再定义条件转移概率： 多重级联奇偶校验码的f p g a 实现 ( m ) = t r d k 吐t m l 掣) f = 0 ，1 ( 3 7 ) 该公式表示接收到序列掣，而当前状态为m ，发送为f 的条件转移概率，则有 由此( 3 6 ) 式可变为： 将( 3 8 ) 式代入( 3 9 ) 式可得： l ( d 七) = l o g ( m ) ( m ) e 似一t , s k = 训掣) m ( 3 8 ) ( 3 9 ) ( 3 1 0 ) 设七一1 时刻的状态为所7 ，将序列掣分为磷一，坟，哎l 三段，把条件概率转为 联合概率，利用b a y e s 公式，可以得到 只 = 腕，i 群d ) 只似乩= 所，& s k - l = m p r r t u + 鸺i = 所 ( 以) 礼g 霞mm 丽i 丽嗣雨i 再面瓜j 币耳忑司 令 则有： 吼( 肌) = e 反( m ) 一只 y i ( r ，m ，胁) = 只 d k= i ，& = 胁，i 一l = 川) ) ，。( r ，m7 ，m k 一，( 所) 反( m ) y o ( r ，m ，肌b 七一。( m7 ) 反( m ) 1 9 ( 3 1 1 ) ( 3 1 2 ) 砖一砖 旦册 g 0 窖 、l， 厶h d ，l l m 群 = m 卜驴喘 旦m 旦m g 0 = 、l - ，女 d ，、 己 第3 章t u d ) o 码与级联分组码 其中吼( m ) 和反( 班) 可以通过迭代得到： n ( r ，脚，m ) g r k _ 1m ) ( 掰) = j 亚等一 ( 3 1 3 ) ；磊砟( r , m t , m ) a k 拟) 以( r + - ，肌，肌) 反+ ，( 聊) 刚州。嚣厮1 丽 以( r 小忉，肌) 吼( 柳) “ 它们的初始化分别为： 引m ) 。茹嚣 脚) 2 三嚣 r i ( r , ，m ，m ) 是关于七时候某一状态的转移概率，其可以表示为： ( 3 1 5 ) n ( 尺七，m ，m ) = p ( ri d 七一f ，s k ；m ，一l m 肪( ri 噍一f ，= 所，& 一。= m ) 只 & l & 一。) 综上所述，这个m a p 算法的计算步骤可以归纳为： ( 3 1 6 ) 1 ) 令编码器以全零状态作为其初始状念和终止状态，初始化( 川) 和f i n ( m ) ： 2 ) 根据每个接收值磁，根据( 3 1 3 ) 式和( 3 1 6 ) 式，计算( 坍) 和y i ( r ，所7 ，m ) ； 3 ) 当掣全部接收完后，得到所有的玢( ，m ，所) 和a 七( m ) ，利用( 3 1 4 ) 式计算 反( m ) ； 4 ) 利用式( 3 1 2 ) 计算每一个时刻的( 以) ，进行译码判决。 为了进行迭代译码，我们有必要分析接收码元的可靠性值，外信息以及先验 信息的产生。对于式( 3 1 2 ) 可以分解成下面两项： 多重级联奇偶校验码的f p g a 实