（微电子学与固体电子学专业论文）dsp上turbo编译码的实现.pdf

摘要 从1 9 4 8 年，s h a n n o n 发表通信的数学理论这篇论文以来，信道编码技术 取得了极大的发展。其中最大的成就莫过于t u r b o 码的提出。由于其接近香浓限 的良好性能，所以自从1 9 9 3 年t u r b o 码被提出来以后就受到通信界的广泛关注， 并成为信道编码领域的研究重点之一。 经过十几年的研究与发展，t u r b o 码的理论基础已经非常完善，t u r b o 码已经 可以应用在实际的系统中，因此本文主要介绍如何利用实际的d s p 处理器来实现 t u r b o 码的译码器，并且对t u r b o 码的迭代译码中的有关技术问题进行了研究。 本文的主要内容有： 首先，介绍了t u r b o 编译码的原理，包括编码器、译码器、译码算法等。对 t u r b o 的两种译码算法原理进行了推导，并给出了两种算法的m m l a b 浮点程序仿 真结果。 然后，介绍了实现t u r b o 码译码器的硬件平台x x xd s p ，包括该d s p 的硬 件资源、指令集、存储空间等。说明了评测的具体要求、所需提供的材料和评测 的步骤。 接着，介绍了用定点d s p 处理浮点程序的方法：定点化，并给出了两类译码 算法的定点程序的仿真结果。 最后，经过分析与比较后，采用s o v a 译码算法作为t u r b o 译码算法，利用 x x xd s p 的指令集完成了基于s o v a 译码算法的t u r b o 码译码器，详细介绍了如 何用汇编指令实现译码器的各个部分以及译码算法的各个步骤，并在实际的d s p 芯片原型验证平台上运行t u r b o 译码器的汇编程序，所得到的实际结果和与 m m l a b 定点仿真得到的结果相差不大。 关键词：t u r b o 码s o v a 译码算法d s p 处理器 a b s t r a c t a b s t r a c t a g r e a td e v e l o p m e n th a sb e e n a c c e l e r a t e ds i n c e19 4 8 ，a f t e rs h a n n o np u b l i s h e dh i s p a p e r “am a t h e m a t i c a lt h e o r yo fc o m m u n i c a t i o n t h em o s ti m p o r t a n ta c h i e v e m e n t m u s tb et h et u r b oc o d e b e c a u s eo fi t sg o o dp e r f o r m a n c eo fc l o s i n gt os h a n n o nl i m i t , s i n c e19 9 3a f t e rt h et u r b oc o d ew a sr a i s e d ，t h ec o m m u n i c a t i o na r e ap a yg r e a ta t t e n t i o n t oi t ，a n di tb e c a m eo n eo ft h ek e ya r e a so f r e s e a r c hi nc h a n n e lc o d i n g a f t e rt e n so fr e s e a r c ha n dd e v e l o p m e n t ，t h et h e o r yo ft u r b oh a sb e e nc o m p l e t e d m o s t l y , a n di tc a n n o wb eu s e di nar e a ls y s t e m ，s ot h i sp a p e rm a i n l yd e s c r i b e sh o wt o i m p l e m e n tt h et u r b od e c o d e rb yu s i n gd s pp r o c e s s o r t h e t h e s i si n c l u d e st h e f o l l o w i n gp a r t s ： f i r s t ，t h ep r i n c i p l eo ft u r b oe n c o d ea n dd e c o d ei si n t r o d u c e d ，i n c l u d i n gd e c o d e r 、 e n c o d e r 、d e c o d i n ga l g o r i t h m s t h e nt h ep r i n c i p l eo f t h e s et w od e c o d i n ga l g o r i t h m si s d e r i v e d ，a n dt h es i m u l m i o nr e s u l t so ft h em a t l a bp r o g r a m so ft h e s et w od e c o d i n g a l g o r i t h mt i t l eg i v e n s e c o n d l y ，t h eh a r d w a r ep l a t f o r mo fa c h i e v i n gt u r b od e c o d e ri sd e s c r i b e d ：x x x d s p , i n c l u d i n gt h er e s o u r c e s 、t h ei n s t r u c t i o ns e ta n dt h em e m o r ys p a c eo fi t a n dt h e s p e c i f i cr e q u i r e m e n to fe v a l u a t i n g 、t h ed a t as h o u l db eg i v e na n dt h es t e p so fe v a l u a t i n g a r ed e s c r i b e d t h i r d l y , w ed i s c u s s e dt h ew a yt or u nt h ef l o a t - p o i n tp r o g r a mo nf i x p o i n td s p , a n dt h es i m u l a t i o nr e s u l t so ft h et w of x p o i n tp r o g r a m sa r eg i v e n f i n a l l yw ec o m p l e t e dt u r b od e c o d e rw h i c hu s e ds o v ad e c o d e ra l g o r i t h mb y u s i n gx x xd s pi n s t r u c t i o ns e t w ed e s c r i b e di nd e t a i lh o wt oa c h i e v et h ep a r t so f d e c o d e ra n dt h ed e c o d i n ga l g o r i t h mi na s s e m b l yi n s t r u c t i o ns e t , a n dr u nt h ed e c o d i n g p r o g r a mo nt h er e a lc h i p sv e r i f i c a t i o np l a t f o r m ；t h er e s u l t sa r ec l o s et ot h em a t l a b s i m u l a t i o nr e s u l t so ft h ef i x - p o i n t e dp r o g r a m s k e y w o r d ：t u r b o s o v a d e c o d i n ga l g o r i t h m d s pp r o c e s s o r 第一章绪论 第一章绪论 1 1 数字通信原理 衡量一个通信系统性能好坏的主要指标是有效性和可靠性。信息在信道中传 输时总会受到信道噪声的干扰，引入了误差，降低了通信的可靠性。因此必须采 取信道编码技术来减少噪声对信息的干扰，以保证通信的可靠性。信道编码的一 般原理是在消息序列中加入特定的冗余序列，从而使消息序列之间满足某种约束 关系；在接收端译码器根据这些约束关系进行译码，将受到噪声干扰而出现的错 误检测或纠正过来。因此，消息首先从发送端发出，然后经过信道编码器编码， 然后再经过调制器调制后发送出去，接收端的信号经过解调器解调后再经过译码 器译码恢复出原始的发送信息。 一个典型的数字通信系统组成如图1 1 所示【4 】： 图1 1 数字通信系统的基本组成结构 图1 1 中的信道编译码器就是我们进行差错控制的工具，也是本文所研究的 内容，而所要实现的就是图中的信道编码器。 1 2 信道编码的发展 1 9 4 8 年，c l a u d ee s h a n n o n 发表了著名的通信的数学理论这篇论文，在 该论文中提出的香浓定理指出：任何一个通信信道都有一个固定的信道容量c 只要该信道的传输速率r 不大于该信道的信道容量c ，就存在某种编码方法，当 码长充分长并采用最大似然译码时，能使得该信道传输的误码率任意小【5 1 。 首先被使用的差错控制码为分组码。分组码码字中的冗余码元与其他码组的 码元无关，而只与本组的码元有关。汉明码和循环码是目前应用比较广泛的两种 2 d s p 上t u r b o 编译码的实现 分组码。汉明码是r h a m m i n g 于1 9 5 0 年提出的，通常被认为是第一个差错控制 码，汉明码可以纠正单个比特错误；随后，1 9 5 4 年，r e e d 和m u l l e r 提出了一种 新的分组码，称为r e e d m u l l e r 码，简称r m 码；r m 码之后又提出了循环码，循 环码虽然也是一种分组码，但其码字具有循环移位特性，即循环码的码字比特经 过循环移位后仍然是循环码码字集合中的码字。h o c q u e n g h e m 在1 9 5 9 年，b o s e 和r a y - c h a u d h u r i 在1 9 6 0 年几乎同时提出的b c h 码是一种重要的循环码；然后 r e e d s o l o m o n 将b c h 码扩展到了非二元的情况，得到了r s ( r e e d s o l o m n ) 码1 9 1 。 1 9 5 5 年，e l i a s 等提出卷积码。卷积码通过利用各个信息块之间的相关性，提 高了译码编码增益。通常卷积码记为仳k ，m ) 码，其中，n 为码长，k 为信息元个数， m 为编码器中寄存器个数。卷积码的编码过程是连续进行的，即依次连续将k 个 信息元输入编码器中，经过编码后得到n 个码元。编码后的码元中的校验元不仅 与本码组的信息元有关，还与以前m + 1 个时刻的信息元( 反应在编码器中寄存器 的内容上) 有关。同时，在卷积码的译码过程中，不仅要从本码中提取译码信息， 还要充分利用以前和以后m + 1 个时刻收到的码组，从这些码组中提取译码相关信 息，提高了译码的性能。卷积译码利用解调器输出的软信息，能够提高译码性能， 同时译码过程也相对简单。并且译码可以连续进行，从而使译码延时相对比较小。 尤其是1 9 6 7 年，v i t e r b i 译码算法被提出后，卷积码得到了广泛的应用【l 。 1 3t u r b o 码的提出与研究现状 1 3 1t u r b o 码的提出 1 9 9 3 年，在瑞士日内瓦召开的i e e e 国际通信大会( i c c 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 l l 舭码 编码技术 7 1 。 t u r b o 码又称为并行级联卷积码( 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 n a l c o d e ) ，它巧妙地将卷积码和交织器级联起来，通过将短的分量码( r s c ) 联合来达 到实现具有近似无限长度的码字。同时，译码时采用具有软输入软输出的译码器 和迭代译码来近似达到最大似然译码。因此，t u r b o 码很好的实现了香浓定理中 的随机性编、译码的条件，获得了几乎接近香浓极限的译码性能。仿真结果表明， 在交织长度为6 5 ，5 3 6 ，译码迭代1 8 次，信噪比e 0 0 7 d b 并采用b p s k 调制 的仿真条件下，码率为1 2 的t u r b o 码在a w g n 信道上的误码率( b e r ) l o 。5 ， 与香浓极限仅相差0 7 d b l 7 1 。 1 3 2t u r b o 码的研究现状 第一章绪论 由于t u r b o 码能得到如此优异的性能，因此，它的一出现就引起了巨大的轰 动，并产生了一股研究t u r b o 码的热潮。目前，主要从以下几个方面对t u r b o 码 进行研究： ( 1 ) 编码理论研究与性能分析 在介绍t u r b o 码的第一篇论文里，b e n o u 等人没有给出严格的理论证明和 解释，仅给出了t u r b o 码的基本组成和迭代译码原理。因此，关于t u r b o 的理论证明就显得尤为重要。截止目前为止，最重要的理论研究成果之一 是1 9 9 6 年j h a g e n a u e r 等发表的论文，文章首次从理论上阐述了迭代译码 的原理，并研究了可应用于卷积码和分组码的软输入软输出译码算法【1 2 1 。 ( 2 ) t u r b o 码的设计 t u r b o 码由分量码经过交织器级联而成。因此，分量码和交织器的设计决 定了t u r b o 码的性能。实验表明，t u r b o 的分量码应采用系统递归卷积码 ( r s c ) 。交器的主要作用是减小译码输出之间的相关性和提高低中序列的 输出码重，它影响着t u r b o 码的性能和距离谱。什么是最合适的交织图案 是t u r b o 码的又一个重要的研究方向。 ( 3 ) t u r b o 码的译码算法 目前t u r b o 码最主要译码算法为基于最大后验概率的m a p 译码算法和基 于软输入软输出的v i t e r b i ( s o v a ) 译码算法。m a p 译码算法的性能很好， 但计算复杂度高，有大量的乘法运算和指数运算，不利于硬件的实现。可 以将m a p 运算转换到对数域中计算，这样就将乘法运算变为加法运算， 省略了指数运算，简化了运算，这就是l o g m a p 译码算法。m a x l o g - m a p 算法采用对数公式的近似形式，运算更简单，但性能要比m a p 译码算法 差零点几d b 。s o v a 译码算法计算简单，便于硬件实现，性能和 m a x l o g - m a p 译码算法的性能相差不大。如何设计出性能优良并且便于 硬件实现的译码算法对t u r b o 的实际应用起决定作用。 ( 4 ) 与调制技术的结合 根据信道编码定理，信息码元经过信道编码后引入冗余码元，为了不减小 码元的传输速率则需要增加信道的带宽。利用t c m 技术可以在不增加系 统带宽的条件下提高编码增益。将t u r b o 码与t c m ( t r e l l i sc o d e m o d u l a t i o n ) 技术相结合以实现高频谱效率、高增益的编码调制方案称为 t - t c m 。s l g o f 对t u r b o 码直接与符号映射相结合进行了研究； s b e n e d e t o 和d d i v s a l a r 等对t u r b o 码和各种高阶调制技术相结合进行了 研究。如何将t - t c m 方案有效地应用于实际的系统中，也是t u r b o 码研 究的方向之一。 4 d s p 上t u r b o 编译码的实现 1 4 本文的内容 本文作者所在项目组参加了中国电子科技集团第5 8 研究所负责的“核高基 国家重大专项：高性能d s pi p 的设计，本文作者负责评测该所高性能低功耗d s p x x xd s p 芯片的实际应用性能，经过仿真分析后确定采用t u r b o 的s o v a 译码算 法作为应用评测程序。本人主要完成了t u r b o 编译码程序的浮点、定点仿真；然 后用x x xd s p 的指令集实现了t u r b o 码译码器，其中子译码器采用s o v a 译码 算法，并在d s p 芯片原型验证平台上成功运行。 全文具体安排如下： 第一章论述无线通信原理和t u r b o 码的产生及研究现状。 第二章介绍t u r b o 码编译码原理，介绍t u r b o 的两种主要译码算法，给出了 具体的数学推导的公式，然后给出各种译码算法的运算复杂度比较以及浮点程序 的仿真结果： 第三章介绍实现t u r b o 译码器的硬件平台x x xd s p ，具体介绍了该d s p 的 结构、资源、指令集等。根据中电集团第四研究所的评测规范，介绍评测d s p 处 理器的实际应用性能的规范、要求的软硬件环境和主要流程。 第四章首先讨论了浮点程序的定点化问题，并给出了各种译码算法的定点仿 真结果；然后论述了应用x x xd s p 实现t u r b o 码译码器的方案，t u r b o 译码器主 要由两个子译码器、交织器、解交织器、硬判决器组成，本文详细讨论了如何用 该d s p 的指令集实现以上各个部分以及实现过程中所遇到的问题；最后介绍了 x x xd s p 的原型验证平台，并给出t u r b o 译码器的汇编程序在该原型验证平台上 的运行结果。 第五章总结全文，指出研究的不足以及未来工作的展望。 第二章t u r b o 编译码原理与译码算法原理 第二章t u r b o 编译码原理与译码算法原理 t u r b o 码编码器巧妙地通过将两个分量卷积编码器( r s c ) 和交织器级联起来， 通过将短码级联来近似地得到长度无限长的长码；t u r b o 码译码器通过软输入软 输出迭代译码i 能近似得到接近香浓极限的性能；t u 曲0 的译码算法主要包括基 于最大后验概率的m a p 译码算法和基于软输入软输出v i t e r b i ( s o v a ) 译码算法。 本章首先论述了t u r b o 码的编码器和译码器结构，然后讨论了t u r b o 子译码器的 这两种主要译码算法，并给出具体的算法原理推导和仿真性能以及计算复杂度的 分析。 2 1t u r b o 编码原理及编码器结构 t u 曲0 码编码器的结构如图2 1 1 所示，包括两个分量编码器r s c l 和r s c 2 ， 通过一个交织器将两个分量编码器级联。实验证明，分量编码器采用系统递归卷 积编码器能获得较好的性能1 3 。信息序列经过分量编码器1 编码后，生成第一个 校验序列珐。；同时，信息序列经过交织器交织后，输入到分量编码器2 中进行编 码，生成第二个校验序列岛。两个分量编码器产生的校验序列经过删余器通过 是否删除码字而得到不同的码率，经过删余后的校验序列以和原信息序列d 复 用，即合成一个序列作为编码后的序列发送出去。 信息序列d p 1 k 分量编码器l 复 删 p k 用 y 余 器 1 器 2 加驵d k 一 ，目 占7 t 11 ：1 口 p 盐 l 父玖葡 刀里钢嗣丽z 图2 1 1t u r b o 编码器结构 t u r b o 码编码器中的分量编码器一般采用系统递归卷积码( r e c u r s i v e s y s t e m a t i cc o n v o l u t i o n a l ，r s c ) 。t u r b o 码可以用分量编码器的生成多项式来表示， 码率为1 2 ，约束长度为v + 1 的r s c 编码器的生成多项式可以表示为： 6d s p 上t u r b o 编译码的实现 g c 删，器h ，等锶端， 叫， 其中，彰= o ，l ；i = l 2 v j = o ，1 。 本文中采用的t u r b o 码码率为1 3 ，分量编码器的生成矩阵为( 1 3 ，1 5 ) ，码率 为1 2 ，其具体结构如刚8 】： 信 回表示编码器中的寄存器 。表示模二取余运算 图2 1 2 本文所采用的的t u r b o 编码器 信息序列一方面输入到分量编码器r s c l 中进行编码，生成第一路校验序列 p k 和系统序列d i 【，一方面经过交织器交织后，输入到分量编码器r s c 2 中进行编 码，生成第二路校验序列p k ，然后系统序列和生成的两路校验序列合并为一路 序列发送出去。 卷积码通过网格截断，即输入全零的尾比特强制编完码后编码器的状态回到 零状态来保证下一次编码时编码器的初始状态为零状态。但是首先由于交织器的 作用，第二个分量编码器的尾比特不像第一个分量编码器那样位于信息序列的末 端；其次交织器的作用和子编码器的递归性使得尾比特的计算很困难，因此，在 t u r b o 码中的网格截断就不能像卷积码中的网格截断那么简单【1 1 】。在本文中采用 对第一个分量编码器进行网格截断，第二个分量编码器不截断的方式。 第二章t u r b o 编译码原理与译码算法原理7 2 2t u r b o 译码原理及译码器结构 t u r b o 译码器的结构如图2 2 1 所示：主要由两个软输入软输出( s i s o ) 子译码 器、硬判决器、交织器、解交织器组成。两个子译码器分别对应于编码器中的两 个分量编码器，子译码器间通过交织器和解交织器互相连接，交织器的交织图案 和编码器的交织图案相刚6 1 。 图2 2 1t u r b o 译码器结构图 t u r b o 译码过程是一个迭代的过程，其译码的过程为：首先，将接受到的信 道信息序列解复用为信息序列、分量编码器1 产生的校验序列1 和分量编码器2 产生的校验序列2 。对于子译码器1 ，将信息序列、校验序列1 和序列的先验信息 ( 初始的先验信息为零序列) 输出到子译码器中进行译码，得到序列的似然信息， 从子译码器1 产生的似然信息中产生外信息l ，经过交织器交织后，作为该序列 的先验信息输入到子译码器2 中，同时将经过交织器交织后的信息序列和校验序 列2 输入到子译码器2 中进行译码，得到信息的似然信息，再从该似然信息中产 生子译码器2 的外信息，经过解交织器解交织后作为子译码器l 的先验信息，以 进行下一轮的译码，至此完成了一次迭代译码的过程。在达到预定的迭代次数后， 对子译码器2 产生的似然信息解交织后进行硬判决，从而产生译码结果【6 】。 由此可见，子译码器是t u r b o 译码器的核心。t u r b o 的子译码器采用软输入 软输出( s i s o ) 译码器，如图2 2 2 所示。输入是信息序列、校验序列和前一个 子译码器产生的先验信息；输出是信息序列的似然信息和外信息，外信息经过交 8 d s p 上t u r b o 编译码的实现 织或者解交织后作为下一个子译码器的先验信息输入。 s i s o 译码器 图2 2 2 子译码器 一般把似然信息输出表示为后验概率对数似然比( l l r ) 的形式，即 d 地怒舞 仁2 m s i s o 译码器的输出三( i 即可表示为系统信息厶蟒、先验信息l ( u k ) 和外信 息厶( 心) 三项之和的形式，即： t ( u 。iy ) = 厶以+ 三( ) + 厶( ) ( 2 2 2 ) 其中，先验信息三( ) 被定义为先验概率的对数似然比，即 三( u k 灿；黼 叫) 因为外信息厶( 蜥) 与系统信息厶以和先验信息三( ) 无关，所以可以将前一个 子译码器生成的外信息经过交织后作为后一个子译码器的先验信息输入，进行迭 代译码，从而提高了译码的性能。 由公式( 2 2 2 ) 可知，s i s o 译码器输出的外信息为： 厶( ) = l ( u 。ir ) - 厶以一l ( u 。) ( 2 2 4 ) 2 3t u r b o 码的译码算法 t u r b o 码的译码算法就是指译码器中的子译码器所使用的译码算法。目前， 研究和应用比较广泛的译码算法主要有基于最大后验概率的m a p 类译码算法和 基于最大似然函数的软输入软输出v i t e r b i ( s o v a ) 译码算法这两类【1 2 】。 2 3 1 译码准则 通常使用广泛的译码准则有两种：最大后验概率准则和最大似然准则。 最大似然准则译码的估值方法是：对于所有的码字可能值，p r ( cir ) 应最大。 根据贝叶斯准则： 第二章t u r b o 编译码原理与译码算法原理9 p r ( c ir ) ：p r ( r c ) p r ( c ) ( 2 3 1 1 ) 。7 p r ( r ) 假设发送端每个码字的概率p r ( c ) 都相同，并且p r ( r ) 与译码方式无关，所以 求p r ( c i 尺) 的最大值就等价于求p r ( ric 。) 的最大值。p r ( ric ) 就称为最大似然函 数，求使得p r ( ric ) 最大的c 的译码方法就被称为最大似然准则译码。 根据概率论的定义，p r ( c lr ) 称为最大后验概率，同时根据信源的马尔科夫 性： p r ( c i 尺) = 兀p r ( c , i 足) ( 2 3 1 2 ) 因为发送序列c 与信源序列 反) 一一对应，所以p “glr ) 最大等价于 p r ( d kir ) 最大。最大后验概率准则译码就是求使公式( 2 3 1 2 ) 最大的码字c 。下 面首先介绍基于最大后验概率译码准则的m a p 译码算法。 2 3 2m a p 译码算法原理 m a p 类译码算法是基于最大后验概率准则的译码算法，最早由l b a h l 、 j c o o k e 、e j e l i n e k 和j r a v i v 等人提出，因此被命名为b c j r 算法，它是r s c 子 译码器的最佳译码算法【引。m a p 译码算法的核心思想是：译码时分别计算每一个 码元的后验概率似然值，并以所得的后验概率值来判断该码元的值。 假设译码器所输入信息序列为y = 吖= ( y l ，y 2 ，y 3 ，y n ) ，其中， 儿= ( 以，群) ，n 表示信息序列的帧长，码元的后验概率似然比三( 以) 表示为 地) _ l 。g 嬲 鲫1 ) 其中，p ( l 。i ) 和p ( ：。l ) 是码元巩的后验概率。 由贝叶斯公式，式( 2 3 2 1 ) 可以改写为 地川。g 畿耥礼g 嬲 叫力 在栅格图中，任何一条分支转移的概率等于所有的分支转移概率之和： p ( s k 一。= s ，& = s ，) 以u k ) = l o g 警丽i 骊 q & 2 3 ( s ，s ) 魄= 0 公式中的求和是对所有由巩= 1 ( 或u = o ) 引起的状态从瓯一。到状态的转 l o d s p 上t u r b o 编译码的实现 移。其中，最一。表示网格图中k - 1 时刻的状态，最表示网格图中k 时刻的状态。 为简便起见，后面将用s 表示k - 1 时刻的状态，用s 表示k 时刻的状态。 接收序列可以分为三个部分：k 时刻之前接收到的序列片一，k 时刻接收 的码字y k = ( 以，y f ) ，以及k 时刻之后接收到的序列藏，则 p ( s ，s ，) = e ( s ，s ，计一，妖，y 鲁1 ) ( 2 3 2 4 ) 由贝叶斯公式可得： p ( s ，s ，) = 户( y 芝。is ，s ，并- 1 儿) 尸( s ，s ，并一，败) = 展( s ) ) ，t ( s 。，s ) o t i l ( s 。) ( 2 3 2 5 ) 在公式中，引入三个定义，分别为： o t k _ l ( s ) = e ( s ，并q ) ( 2 3 2 6 ) 风( s ) = p ( 坛n + ls ) ( 2 3 2 7 ) 7 ，t ( s 。，s ) = p ( 以，ss 。)( 2 3 2 8 ) 其中，式( 2 3 2 6 ) 、( 2 3 2 7 ) 、( 2 3 2 8 ) 分别称为前向状态度量、后向状态度量、 分支转移度量。 因此，m a p 算法求码字比特的后验概率必须要求出前向状态度量、后向状态 度量和分支转移度量。以下就推导这三者的计算过程。 首先是前向状态度量( s ) 的计算过程，由贝叶斯公式可得： ( s ) = p ( s ，衅) = r k ( s ，s ) a ( s ) ( 2 3 2 9 ) _ ” s 下面推导后项状态度量成( s ) 的计算过程，由贝叶斯公式可得： 成一。( s ) = 尸( i s ) = 反 ) r k ( s ，s ) ( 2 3 2 1 0 ) _ _ 。” s 最后推导分支转移度量的计算过程。根据分支转移度量的定义式和贝叶斯公 式，有： “( s 1 ，s ) = 尸( 儿，sls 。) = p ( 儿i s ，s ) p ( ) ( 2 3 2 1 1 ) 其中，是引起从状态s 一= s 到状态& = s 转移所输入的信息比特，p ( 以) 是矾 的先验概率，p ( 儿is ，s ) ) 等效于尸( 欺i 矗) 。其中，x k 为从状态瓯一，= s 到状态 第二章t u r b o 编译码原理与译码算法原理i i 最= s 转移所发送的信息比特。 假设信道是无记忆信道，则 p ( 儿l s ，s ) = 尸( 以l 靠) = 兀p ( 妇l 翰) ，l l 其中，和蜥分别是发送码字吒和接收码字m 的比特位，n 表示发送和接收码 字的长度。假设发送码字经过b p s k 调制，并经过均值为零，方差为盯2 = 0 2 的 a w g n 信道，则： p ( 1 ) 2 去e x p ( 一鲁( 虼一) 2 ) ( 2 3 2 1 3 ) 其中，e 表示发送每- - l l 特所需的能量。带入上式可得： 地邮) = 鼻去晰奇( 妇训2 ) 其中，分别令： = c y k ( 1 ) f ( 2 ) m v r s 争喜c 虼 c o ) = 丽1e 卅鲁和 碟= 时导扣 式( 2 3 1 1 5 ) 只依赖于信道的信噪比s n r 值和接收码字的大小，式( 2 3 1 1 6 ) 只依赖于信道的信噪比s n r 值。所以这两项都可以看成是常数。 下面计算的先验信息p ( ) 。根据译码器的先验信息l a ( u k ) 的定义： 圳驴l o g 揣 可得到： 鹏，= 舞糍端 根据以上各式得出分支转移度量九( s ，s ) ： “( s ，s ) = 嗖锷吃( ) e x p ( u k l 口( 以) ) e x p e ( 妇) ) fn l ， 1 = 1 1 2d s p 上t u r b o 编译码的实现 ( 2 3 2 1 9 ) 上式中，嗖、锈和吒( u i ) 可以从分子、分母中删去，又因为y k = ( 以，巧) ， = ( ，) ，所以上式可以简化为： y k ( s 。，s ) = e x p ( u k l a ( u k ) ) e x p f 等( 以+ 蟛) ) ( 2 3 2 2 0 ) u 根据前面推导的前向状态度量、后向状态度量、转移状态度量的计算公式， 可以得到巩的对数似然比三( ) 的计算公式为： f s s 1 。 a k - ( s ) r i ( s ，s ) 卢i ( s ) 工( 阢) = 工口( 以) + 工c 以+ l o g 意兰一 a t - i ( s ) 以( s ，s ) 卢。( s ) = 上口( 酞) + 三c 以+ l e ( u k ) 其中，口( ) 为前一个子译码器为后一个译码器提供的的先验信息，k 以为 信道信息值，l e ( u k ) 为的外信息。在t u r b o 译码器迭代译码的过程中，需要计 算子译码器产生的外信息，并将外信息经过交织或者解交织作为外信息输入到下 一个子译码器中，所以要先计算出的对数似然比三( 以) ，再减去上一个子译码 器提供的先验信息和接收到的信道信息，即： l e ( u k ) = 三( 以) - l a ( u , ) - l c * 成 2 3 3l o g - m a p 译码算法原理 从上面的推导可以看出，m a p 译码算法中存在大量的乘法运算和指数运算， 如果用硬件实现这些运算将非常困难。所以在实际实现t u r b o 译码器时一般都不 采用m a p 译码算法。为了降低译码算法的复杂度，便于硬件的实现，通常将m a p 译码算法转换到对数域上来，这样就将乘法运算变为加法运算，并避免了指数运 算。 在l o g - m a p 算法中，分别将m a p 算法中的前向状态度量、后向状态度量和 分支转移度量变换到对数域，并且根据雅克比公式前向状态度量可以简化为： 4 i ( s ) = 一l i l a i ( s ) ( 2 3 3 1 ) 同理，可以将后向状态度量的计算公式改为： 反一l ( s 。) = 一l i l ( 反一。( s ) ) ( 2 3 3 2 ) 分支状态转移度量的计算公式改为： 第二章t u r b o 编译码原理与译码算法原理 1 3 r i ( s ，s ) = 一l n ( r i ( s ，s ) ) 这样，经过变换后的对数似然值计算公式为： f s s 、 a k - i ( s ) ) ，。( s ，s ) 风( s ) l ( u k ) = l o g a ( s ) r k ( s ，s ) 成( s ) “。o - - _ ? 叼；t ￥( 彳后一l ( s 。) + b 七( s ) + f 七( s 。，s ) ) 以= o 、 、7、7 、 - m ，a ，x ( 彳七一l ( s 。) + 曰t ( s ) + r 七( s 。，s ) ) 以= l 、 、7 、7、7 2 3 4m a x - l o g - m a p 算法原理 ( 2 3 3 3 ) ( 2 3 3 4 ) 为了更进一步的降低运算的复杂度，可以将雅克比等式后面的修正项去掉， 则前向状态度量、后向状态度量和码元的对数似然比计算式可以写为： 4 ( s ) = m i l l s ( 4 一l ( s ) + r i ( s 。，s ) ) ( 2 3 4 1 ) 最一l ( s ) = m i n s ( 最( s ) + r ( s ，s ) ) ( 2 3 4 2 ) = 啪舢m 邸h 叫3 ) 一m 吣i n 。( a h ( s 。) + 瞰( s ) + r 七( s ，s ) ) 2 4s o v a 译码算法原理 s o v a 算法是对v i t e r b i 译码算法进行修正，使之能提供软信息的输出后得来 的，称改进后的算法为软输出v i t e r b i 算法，记做s o v a ( s o f to u t p u tv i t e r b i a l g o r i t h m ) 算法【1 3 】。 v i t e r b i 译码算法的核心思想就是寻找信息序列材伽或者状态序列s t m 使后验 概率p ( s ( 胂i 】，) 最大【1 l 】。假设每个状态有且只有两条输出路径，则m 的值为l 或 者2 ，分别代表幸存路径和竞争路径。并且设两条路径的路径度量值分别为：m 1 1 和膨孙。 在t 时刻栅格图中的某个节点的软信息值( 似然比值) 为： a ? = 去i 叫n 一彬2 ) | ( 2 4 1 ) 二 t 时刻选择路径m 的概率与s o v a 度量之间的关系为： 1 4d s p 上t u r b o 编译码的实现 嘏鳓叫辩唧降) 叩， 在t 时刻，选择正确幸存路径的概率为 p ( 路径- d = 丽孺而夏丽 一e x p a 。 l。+。e。x。p。a。 则这个路径判决的可靠性概率为： e x p a 。 ( 2 4 3 ) lg老18可l+expa。expa=? ( 2 4 4 ) 1 _ 儿删 1 ；j 1 l + o x p b ? l 在t 时刻某节点的幸存路径的可靠性值可以表示为，其中 m e m = 0 ，1 ，t 。如果在m e m = k 处( t m e m 时刻) 幸存路径和竞争路径相对应的 信息比特不同，就会发生比特错误判决的情况。此时就必须更新这里位置的可靠 性。如图2 4 1 所示，需要更新m e m = 2 和m e m = 4 这两个时刻的可靠性值】。 经过更新后的比特判决的似然值或者软输出值为： a ( u t 删) ：u t m e m ! a ； ( 2 4 5 ) 一 删) = 一 ： ( 2 5 ) 为简化计算，公式( 2 4 5 ) 可以近似为： 一 、 a ( u ，一删) = 址删。艇 a t ( 2 4 回 第二章t u r b o 编译码原理与译码算法原理1 5 t 4 a t 3 a t 2 j l 土j j l 土l j + t t - 6t - 5t - 4 t - 3t - 2t - 1t 6 5432l0 图2 4 1s o v a 算法的一个例子 下面总结s o v a 译码算法的译码过程( 包括可靠性信息的更新过程) ： ( 1 ) 根据生成矩阵产生栅格图，译码器的生成矩阵和t u r b o 编码器的相同； ( 2 ) 在t = 0 的时刻，进行初始化，初始化零时刻零状态的路径度量值m 帕 为零，其他时刻的各个状态的路径度量为哪； ( 3 ) 在t 寸t + l 时刻，对栅格图中的每个状态计算状态度量值： ，、 ( 4 ) 在每个状态下计算最大路径度量值m a ) 【心川，令彬1 表示幸存路径 m 的度量，m 1 2 ) 表示竞争路径的度量； ( 5 ) 存储幸存路径的路径度量值m 1 ) 以及相应的幸存比特和状态路径； ( 6 ) 计算并存储每个状态的幸存路径和竞争路径的路径度量差： a ? = i 1l 心1 ) 一心2 l ； 二 ( 7 )比较t 时刻每个状态处的幸存路径和竞争路径的判决值，并存储两条 路径上比特判决值不同的时刻m e m ； ( 8 ) 利用公式( 2 4 6 ) 从小到大更新所有的m e m 对应的度量值 ( 9 ) 返回( 3 ) ，直到接收完整个发送序列； ( 1 0 ) 输出估计的译码序列u 和相应的软信息值a ( u ) = u ，软信息值作为 先验信息经过交织或者解交织后输入到下一个子译码器中。 t ，r ， 1 6d s p 上t u r b o 编译码的实现 2 5t u r b o 译码算法性能的分析比较 在上面阐述了m a p 类译码算法和s o v a 译码算法的原理，并给出了具体的 数学推导过程，下面从译码性能和计算复杂度两方面对这两种译码算法进行分析 比较。 2 5 1 不同译码算法译码复杂度的比较 假设编码长度为n ，约束长度为v ，s o v a 算法中的译码步长为w ，则不同 译码算法的复杂度如下表： 表2 5 。l 不同译码算法的复杂性比较 操作 l o g m 印 m a x - l o g m a p s o v r a 加法 1 5 2 ”+ 9l o 2 ”+ 1 1 2 2 + 8 乘法8 88 求最大值5xt - 2 5x2 9 22 2 ”+ w 2 查找表 5x2 v - 2o0 存储量 ( n + 1 ) x 2 ”+ 1 ( n + 1 ) x2 + 1( 3 + w ) 2 7 + 1 从表2 5 1 中可以看出，l o g - m a p 译码算法将乘法运算变成加法运算，并消 除了指数运算，从而降低了算法的复杂性。m a x l o g m a p 译码算法减少了查找表 运算，所以进一步降低了运算的复杂性。当v = 2 时，s o v a 译码算法的运算量是 m a x - l o g - m 印译码算法运算量的2 倍，但是当v - - 4 时，后者的运算量差不多变成 前者运算量的两倍了。 2 5 2 不同译码算法仿真性能的比较 图2 5 1 是分别采用l o g m a p 算法、m a x - l o g m a p 算法、s o v a 算法的t u r b o 码仿真结果。仿真是在a w g n 信道下进行的，t u r b o 码编码器的生成多项式为( 1 3 ， 1 5 ) ，编码速率为l 3 ，并且第一个分量编码器添加1 2 个尾比特使分量编码器编 完码后归零，仿真数据帧长为1 0 2 4 ，迭代次数为4 次。仿真结果以信噪比毛o 误比特率b e r 的关系曲线形式给出。 第二章t u r b o 编译码原理与译码算法原理 1 7 图2 5 1 三种算法浮点仿真结果比较 由图中可以看出，l