（信息与通信工程专业论文）双二进制turbo码的研究.pdf

浙江大学硕士学位论文 摘要 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 码的编译码算法。 首先介绍了8 0 2 1 6 e 标准定义的双二进制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 码译码器的现状，提出了一种通用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 码，循环递归卷积码，停止准则 浙江大学硕士学位论文 a b s t r a c t t u r b oc o d er e c e i v e sl o t so ff o c u sb y p e r f o r m a n c e d u o - b i n a r yt u r b oc o d ei s c o d i n gw o r k e r sb e c a u s eo fi t so u t s t a n d i n g a ni m p r o v e m e n to ft h ei n n o v a t i v et u r b o c o d e s ，c o m p a r e dt oc l a s s i c a ln 曲oc o d e ，d u o b i n a r yt u r b oc o d eh a v el o t so f a d v a n t a g e s ：h i g hc o d er a t e ，g o o dc o n v e r g e n c e ，l o wd e c o d i n gl a t e n c y , e t c n o w d b t ci si nu s ei nm a n yo f t o d a y ss t a n d a r d sf o rr a d i oc o m m u n i c a t i o n t h ee n c o d i n ga n dd e c o d i n ga l g o r i t h m sh a v eb e e nd i s c u s s e di nt h i sp a p e r f i r s t l y , w ei n t r o d u c et h e o r yo ft h ee n c o d i n ga n dd e c o d i n gs t r u c t u r ea n d a l g o r i t h m so fd o u b l e b i n a r yt u r b oc o d eu s e di n 8 0 2 16 ep r o t o c o l s t h e nw e c o m p a r et h ec o m p u t a t i o nc o m p l e x i t ya n dd e c o d i n gp e r f o r m a n c eb ys i m u l a t i o n s a n da i ma tt h ep a r t i c u l a rp o i i l to fd b t c ，w er e s e a r c hi n t ot h r e ea s p e c t s ：c y c l i cs t a t e ， i n t e r l e a v e rp a t t e m ，s l i d i n g w i n d o wa l g o r i t h m t h e n ，t h i sp a p e rp r e s e n t sas t u d yo fe a r l ys t o p p i n gc r i t e r i af o rt u r b od e c o d i n g s e p a r a t et h es t o p p i n gc r i t e r i ao fd o u b l e b i n a r yt u r b oc o d eb yf r a m es t o p p i n ga n d b i ts t o p p i n g o n en e wf l a m es t o p p i n gc r i t e r i ai sr e c o m m e n d e di n t h i s p a p e r s i m u l a t i o ns h o w st h en e w s t o p p i n gc r i t e r i ac a l ls t o pt h ed e c o d i n ge f f e c t i v e l yw i t h a l m o s tn od e c o d i n gp e r f o r m a n c ed e g r a t i o na n da d d i t i o n a lc o m p u t a t i o nc o m p l e x i t y f i n a l l y , o n eg e n e r a lt u r b od e c o d e ri sp r e s e n t e d b yt r e l l i sc o m b i n a t i o na n d o n - - t h e - f l yi n t e r l e a v e r , t h eg e n e r a lt u r b od e c o d e rc a na d a p tt of l e x i b l e a n d p r o g r a m m a b l et u r b od e c o d e r s k e y w o r d s ：d u o b i n a r yt u r b oc o d e ，c y c l i cr e c u r s i v es y s t e m a t i cc o n v o l u t i o n a l ， s t o p p i n gc r i t e r i a l l 浙江大学硕士学位论文 第1 章绪论 本章首先介绍了t u r b o 码的历史背景，然后大致阐述了t u r b o 码的研究现 状和双二进制的提出及其应用，最后指出了本文的主要工作和篇章结构。 1 1 引言 现代数字通信的奠基人香农早在1 9 4 8 年就在信道编码定理【1 1 中指出，只要 随机编码的码长足够大，就可以进行无限逼近信道容量c 的通信并使错误概率 任意小。但香农只是从理论上证明了编码极限的存在，却没有构造一种编译码 结构逼近这种极限。自香农之后，人们不懈地向逼近信道容量的方向努力。许 多性能优异的码相继出现，b c h 码、r s 码和卷积码等等，这些码都能获得不 错的性能，但是与香农提出的性能极限，还存在不少的差距。 直到1 9 9 3 年，t u r b o 码的发现，才使得信道编码理论在逼近香农极限的道 路上向前迈出了一大步。1 9 9 3 年，b e r r o u ，g l a v i e u x 和t h i t i m a j s h i m a 在i c c 的 会议上首次提出了t u r b o 码1 2 j ，通过对子码的伪随机交织实现大约束长度的编 码，采用软输入软输出迭代译码来逼近最大似然译码。仿真结果表明，在信噪 比为0 7 d b 的a w g n 信道条件下，采用( 2 1 ，3 7 ) 递归系统卷积码作为分量码，交 织深度6 5 5 3 6 ，迭代18 次之后误码率下降到1 0 巧以下，离香农极限仅仅只有 0 7 d b 。 t u r b o 码自提出之日起就因其优异的性能成为信息论与编码界工作者热切 关注的焦点。目前，t u r b o 码被看作是t c m ( 网格编码调制) 技术问世以来， 信道编码理论研究上所取得的最伟大的技术成就，具有里程碑的意义。 1 2t u r b o 码的研究现状 1 9 9 3 年至今，经过无数信道编码工作者不懈的研究，t u r b o 码优异的性能 在理论上已经得到了比较可靠的解释。s b e n e d o t t o 通过重量枚举公式推导出了 t u r b o 码的误码率性能界，并提出了交织器增益和有效自由距离等概念【3 j 。p e r e z 从距离谱的角度同样对t u r b o 码的性能界作了分析，分析了交织器在编码器过 程中的作用1 4 j 。这些理论分析不仅对t u r b o 码提供了令人信服的理论依据，而 且对t u r b o 码的设计，尤其是分量码编码器和交织器的设计具有非常重要的指 导意义。 通过对t u r b o 码结构的研究，人们很快将t u r b o 码交织级联和迭代译码的 思想进行推广，派生出了很多改进的编码方式，如串行级联码、多分量码t u 曲o 码等，仿真表明，这些码都能获得很好的性能。另外，由于t u r b o 码的出现， 一1 一 浙江大学硕士学位论文 使得人们又对被遗忘已久的l d p c 码产生了浓厚的兴趣，仿真结果表明，某些 结构的l d p c 码距离信道容量的极限只有0 0 0 4 3 d b 。 t u r b o 码的迭代译码思想已经被誉为“t u r b op r i n c i p l e ，在很多的相关领域， 比如多用户检测、联合信道参数的均衡估计、高密度存储领域，甚至人工智能 方面都得到了不同程度的应用。 在实际应用方面，虽然在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 码作为其 标准之一。在深空通信领域，1 6 状态t u r b o 码被空间数据标准咨询委员会 ( c c s d s ) 歹j j 为一个新标准。而在移动通信领域，3 g p p 正式将t u r b o 码作为i m t 2 0 0 0 的高速数据通信的信道编码标准之一。其中具有代表性的3 个3 g 标准 ( w c d m a ，c d m a 2 0 0 0 和t d s c d m a ) 均在信道编码中使用了t u r b o 码，用于 高速率、高质量的通信业务。 虽然t u r b o 码的译码性能非常优越，但是和其他信道编码方案相比，t u r b o 码仍有很多缺点依旧存在： l ，译码算法非常复杂，实现难度大； 2 ，译码需要反复迭代，译码延时长； 3 ，存在错误平层，即误码率下降到一定程度以后，就下降地很慢，趋近于 恒定，再增加信噪比，都很难获得性能上的提高。 1 9 9 6 年b e r r o u 提出了双二进制t u r b o 码，与传统二进制t u r b o 码相比，双 二进制t u r b o 码具有以下优点1 5 j ： 1 ，采用c r s c 做子码，提高了编码效率； 2 ，交织深度是经典t u r b o 码的一半，译码时延减小； 3 ，通过符号间交织增大最小自由距离，消除误码平层； 4 ，相同复杂度译码器下，双二进制t u r b o 码的纠错性能优于传统t u r b o 码； 5 ，码率删余对于双二进制t u r b o 码的性能影响小于传统t u r b o 码。 由于其优秀的性能，目前双二进制t u r b o 码已经广泛应用于很多无线通信 的标准中，比如w i m a x ( i e e e8 0 2 1 6 ) 【6 1 和欧洲卫星网络标准( d v b r c s ) 1 7 1 都采 用了双二进制t u r b o 码。 1 3 本文的主要工作和篇章结构 全文共分五章。各章的具体内容如下： 第一章为绪论，简述t u r b o 码的历史以及双二进制t u r b o 码的研究动态， ，一j o 浙江大学硕士学位论文 使读者对本文的研究方向有初步的了解。 第二章介绍了双二进制t u r b o 码编码器的基本结构，在传统二进制t u r b o 码迭代译码思想和m a p 类译码算法基础上，推导了双二进制t u r b o 码的两种 译码算法：基于符号判决的译码算法和基于比特判决的译码算法，然后对双二 进制t u r b o 码的各种m a p 类算法进行了仿真分析。 第三章针对双二进制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 码现有的两种基于符号的提前判决准则进行了研究，并提出了一种 新的基于符号的提前判决准则。与译码算法一样，双二进制t u r b o 码也可以采 用基于比特判决的方式停止迭代，通过仿真表明基于比特判决的停止准则也能 获得很好的停止效果。 第五章针对目前只有专用t u r b o 码译码器的现状，阐述了一种通用1 、曲o 码译码器的架构，通过网格图合并技术和实时交织器技术，在增加资源不多的 情况下，将双二进制t u r b o 码与传统二进制t u r b o 码相结合，实现两者的统一 实现。 最后对全文进行总结，并对一些有待继续研究的内容和方向进行展望。 一3 一 浙江大学硕上学位论文 第2 章双二进制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 码的 错误平层，基于符号判决的译码算法在复杂度增加不多的情况下降低了译码时 延，码字序列的双输入降低了高码率码字受删余的影响。 本章主要阐述了双二进制t u r b o 码的编译码结构和b c j r 译码算法，并对 不同译码算法双二进制t u r b o 码的性能进行了比较。 2 1 双二进制t u r b o 码编码器的基本结构 一个典型的双二进制t u r b o 码的编码器结构如图2 1 所示。与传统t u r b o 码类似，由两个反馈系统卷积码编码器( r s c ) 组成，分量码之间通过交织器 消除子码之间的相关性，为了提高码率，也需要对校验位进行删余。与传统二 进制t u r b o 码不同的是双二进制t u r b o 码的输入序列每个符号由两个信息位a 和b 组成，分量码采用的是截尾( t a i l b i t i n g ) 1 8 ，9 1 的反馈系统卷积码。 a b a b 图2 18 0 2 1 6 e 1 6 1 中双二进制t u r b o 码的编码器结构 一4 一 浙江大学硕七学位论文 2 1 1 循环递归系统卷积码 双二进制t u r b o 码分量码编码器采用是循环递归系统卷积码( c r s c ) ，图2 1 所示8 0 2 1 6 e 通信协议规定的生成多项式为( 1 5 ，1 3 ，1 1 ) 的t u r b o 码分量码 编码器结构( d v b - r c s 通信协议规定的双二进制t u r b o 码分量码编码器具有相 同的结构) 。 传统t u r b o 码编码器的初始状态为0 ，为了保证终止状态也为o ，需要添加 尾比特，但是由于交织器的作用，很难使得两个分量码编码器同时归零，w c d m a 采用的是单归零方案，而c d m a 2 0 0 0 采用的是双归零方案。一般而言，从译码性 能上比较，双归零方案优越单归零方案，单归零方案又优于不归零方案。但是 添加尾比特降低了编码效率，并且数据包之间相互独立，大大降低了系统吞吐 量，对于使用短帧数据的系统尤为严重。 循环递归系统卷积码基于自截尾机制，使得编码器的初始状态和终止状态 相同，达到状态上的循环，这个相同的状态称为循环状态& 。 我们定义生成矩阵为g ，循环递归系统卷积码编码器k 时刻状态为& ，输 入序列为向量巩，那么对于时刻k ，1 k n ( 为单帧符号数) ，可以得到递 推关系式： s k = g x s k l + ( 2 1 ) 那么循环递归系统卷积码编码器末状态： 晶= g s o + g 肛 ( 2 2 ) k = l 循环递归系统卷积码要求循环状态s u = s o = s c ，代入上式即可求得循环状 态： s c = ( ，+ g ) 。1 g 肛 ( 2 3 ) k = i 循环状态与信息序列有关，并且存在循环状态& 的前提是矩阵n g 可逆，对应图2 1 的循环递归系统卷积码的生成矩阵有周期7 使得g7 = 1 ，所以 不能是7 的倍数。 再考虑式( 2 2 ) ，如果取岛= o ，那么： ， 磷= g 肛以 ( 2 4 ) k = l 将式( 2 4 ) 代入( 2 3 ) 循环状态的求解公式： s c = ( ，+ g ) x 磷 ( 2 5 ) 一5 一 浙江大学硕： 学位论文 由上述推导可以知道，循环递归系统卷积码的编码过程可以分为两步： 1 ，预编码过程。编码器初始状态为o ，预编码得到末状态- 。然后根据 这个末状态妒 ，求得循环递归系统卷积码编码器的循环状态。由于这个求解 过程只与生成矩阵g 有关，因此对应特定的生成矩阵，可以通过查表的方法简 单获得。8 0 2 1 6 e 的循环状态表2 1 如所示。 2 ，然后将编码器初始状态设置为预编码求得的循环状态，进行最终编 码，编码得到的终止状态等于初始状态& 。 s 0 , n m 词 01234567 106427135 2o3745621 30536271 4 4 041 56 273 5 02571346 607613452 2 1 2 交织器 表2 1 循环状态查找表 交织器是t u r b o 码编码的重要环节，通过交织，编码序列在较长的范围内 具有无记忆性，从而由简单短码构造了近似随机长码。因此，交织器设计的好 坏在很大程度上影响着t u r b o 码的性能。 大致上，交织器的主要作用有以下三个方面： 1 ，保证各个分量码输出之问的独立性。 t u r b o 码迭代译码的原理是子译码器之间相互传递软判决信息，最大限度 地利用信息。而分量码输出信息之间的独立性是软判决信息能迭代利用的前提。 也就是说交织器的这一作用是t u r b o 码优秀性能的保证。 2 ，抗突发错误。 信号在信道传输中会因为突发的干扰信号导致大量连续误码，交织器能把 连续符号打散，将具有相关性的数据恢复成相互独立的数据，从而大大提高译 码器的纠错性能。 3 ，增大生成码字的码字重量即最小自由距离。 单个分量码编码器生成码字的码字重量可能会比较低，但是通过交织器重 新排序之后能以很大的概率获得高重码字，从而提高码字的汉明重量。增大码 一6 一 浙江大学硕士学位论文 字重量能提高码字的抗干扰能力，从而提高t u r b o 码的纠错性能。这是t u r b o 码交织器方案选择的一个重要因素。 双二进制t u r b o 码由于序列的双输入，在交织器的设计上有更大的灵活性。 双二进制t u r b o 码有下列三种交织方式： l ，两列数彳和b 采用相同的交织器y 。 2 ，两列数a 和b 采用不同的交织器砀和砌。 3 ，先对两列数彳和b 进行符号内交织，再采用相同的交织器y o 采用双二进制1 、l r b o 码的几种通信协议种采用的交织器都是第三种交织方 式。这里我们以8 0 2 1 6 e 双二进制t u r b o 码交织器即a i 冲交织器【l o 】为例子说明 它的具体实现方法。8 0 2 1 6 e 双二进制t u r b o 码交织器由两步组成： 1 ，符号内交织： 对于k = - 0 到n - 1 ( 是单帧符号数量) ， 当k 为奇数时，交换符号内顺序似岛b k ) 专( b k ，a k ) 2 ，符号间交织： 对于k = 0 到- l ： 万( 七) = ( 昂k + 1) m o d n ， ( r k + 1 + 与+ n 2 ) m o d n ， ( e 0 k + 1 4 - 罡 ) m o d n ， ( e 0 k + 1 4 - b + n 2 ) m o d n ， k m o d 4 = 0 k m o d 4 = 1 后m 。d 4 ：2 ( 2 6 ) k m o d 4 = 3 其中参数p o ，p l ，p 2 和p 3 与帧长有关，可以通过查表获得。8 0 2 1 6 e 中的 参数如表2 2 所示。 符号内交织的加入，大大增加了交织深度，增大了最小自由距离，有效地 提高了交织器的性能，而且实现非常简单，只需交换符号内顺序即可。下一章 对不同交织器性能的仿真，我们可以更加清楚直观地发现双二进制t u r b o 码符 号内交织和符号问交织的结合，有效地抑制了错误平层的出现。 帧长 p op l 2 尸3 帧长 尸。尸l 尸2 p 3 650o03 01 36 006 0 91 11 8o1 83 61 77 47 22 1 21 32 4o2 44 51 19 009 0 l8 1 1 6 o 64 8 1 1 9 64 8 1 4 4 2 4 74 82 4 7 2 5 41 3 1 0 8 01 0 8 2 7 1 1 5 45 6 26 01 3 1 2 06 0 1 8 0 表2 28 0 2 1 6 e 中双二进制t u r b o 码交织器的参数 一7 浙江大学硕士学位论文 2 1 3 删余器 为了适应不同的传输码率，在t u r b o 码编码输出时对码字进行删余。删余 器可以用删余矩阵来形象地描述。矩阵中的1 表示输出选通，0 表示删除该比 特。 m 羽2 ，5 球胡 抛珊2 ，3 球0 0 1 3 4y l 10o l 4 5y l 1oo o l 形l000l矿l0000l 6 7y l 1 0o oo o l 矽l0 000 0 0 图2 2 所示为双二进制t u r b o 码常用码率的删余矩阵，仔细观察可以发现， 要得到1 2 码率，并不需要对数据进行删余。双二进制t u r b o 码信息位一个符 号由两个比特组成，基本码率为1 2 ，而传统t u 曲o 码的基本码率为1 3 ，所以 为了得到高码率可以比传统二进制t u r b o 码少删除校验位，因此减少了删余对 性能的影响，降低对删余类型的敏感度。所以双二进制t u r b o 码更多地用于对 传输码率要求比较高的通信协议中。 2 2t u r b o 码的迭代译码原理 t u r b o 码能获得那么优异的性能，是与它优秀的迭代译码思想分不开的。 相对于编码过程来说，t u r b o 码的译码过程要复杂的多。由于交织器的作用， 使各个子码信息虽然在本质上一致但在逻辑上却近似独立不相关，因而可以进 行独立的译码。t u r b o 码译码器采用迭代译码的方法，将各个子译码器的译码 结果也就是软输出信息相互传递，这样反复多次迭代，最终各自收敛，逼近整 个t u r b o 码的最大似然译码。 一8 一 浙江大学硕士学位论文 图2 3t u r b o 码译码器结构 图2 3 所示的是两个分量码编码器的t u r b o 码的译码器结构。它由两个子 软输入软输出译码器( s i s o ) 串联组成，分别对应于编码过程中的两个分量码 编码器，交织器采用编码器中所使用的交织器。图2 3 中的符号说明如下： ，是译码器接收到的信息序列； 少1 尸是译码器接收到的分别对应于两个分量码编码器的校验序列； l 。= 4 a e i n o = 4 a 饱们v o 是信道可信度，其中a 为衰落参数，对于a w g n 信 道，a = l ，为码率，珧为信噪比； 厶1 2 、三翻是子译码器之间相互传递的外信息； 厶1 2 、三d 2 l 是子译码器接收到的先验信息； 三l ( 砧、三2 ( 砧分别是第一个子译码器和第二个子译码器的输出似然比； 单个传统编码，通常在译码器的最后得到硬判决译码比特，然而t u r b o 码 的编码是由两个或多个分量码经过不同交织后对同一个信息序列进行编码，所 以t u r b o 码译码算法不局限于在译码器中传递硬判决信息。为了更好的利用译 码器之间的信息，译码算法用的是软输入软输出( s i s o ) ，与通常的硬判决译 码相比，减少了信息丢失，提高了译码性能。 s i s o 的任意比特的判决是由其后验概率对数似然比( l l r ) 决定的，即： 三( u k ) = i n 等嚣 ( 2 7 ) l l r 的符号反映了译码器对该信息比特的判决结果。 l ( u i ) = 厶少+ 乙( ) + t ( ) ( 2 8 ) l l r 的值可以拆分为上式三个项组成，其中第一项表示的是信道值，y 由矿和广组成，第二项为子译码器接收到的先验信息，第三项为子译码器传递 给下一个子译码器的外信息。如图2 3 所示，子译码器1 对分量码1 进行译码， 产生关于信息序列u 中每个比特的似然信息l l ( 甜d ，并将其中的外信息z e l 2 ( 甜k ) 一9 一 浙江大学硕士学位论文 经过交织送给子译码器2 ，作为子译码器2 的先验信息l a l 2 ( “ ) ，然后子译码器 2 对分量码2 进行译码，产生关于交织后的信息序列中每个比特的似然比信息 l 。2 ( u k ) ，然后将其中的外信息p 2 l ( t ) 经过解交织送给子译码器1 ，作为子译码器 1 的先验信息以l ( ”d 进行下一次译码。这样反复多次迭代得到最优性能，这种 译码方式同涡轮( t u r b o ) 发动机的工作方式非常相似，t u r b o 码也是因此得名。 当迭代次数趋于无穷时，译码结果越逼近最佳译码，但是迭代次数越多， 译码延时就越长，译码复杂度越高，因此不可能无限制地进行迭代，而且随着 迭代次数的增多，外信息之间的相关性降低，使得每一次迭代获得的性能上的 增益也逐渐减少。所以一般的做法是设定一个最大的迭代次数，达到迭代次数 就终止迭代。 当迭代译码过程结束时，对信息序列各比特的l l r 进行一次硬判决，得到 译码之后的信息比特序列。 2 3 二进制t u r b o 码的译码算法 目前常用的t u r b o 码译码算法分为两类：一类是由v i t e r b i 算法演化而来的 s o v a 算法【1 ，一类是m a p 类算法【1 2 】，以及由m a p 算法延伸出的l o g m a p 算法和修正l o g m a p 算法。 s o v a 算法与m a x l o g m a p 算法是非常相似的，它们有相同的分支度量 函数，因此两者在最大度量路径选择上是一致的，区别在于s o v a 与 m a x l o g m a p 在软判决信息获取方式的不刚1 3 】。s o v a 算法的译码复杂度最 低，但是性能最差，因此本文只对m a p 类算法进行介绍与讨论。 有必要先给出一些符号定义： l ，s 是编码器的2 册个状态集合，m 是编码器的存储深度。 2 ，s = 0 l ，s 2 ，s n ) 为编码器从时刻0 到时刻n 的状态序列。 3 ，u = ( u l ，2 ，甜) 为信息序列，锹 o ，1 ) 。 4 ，x = 0 l ，x 2 ，确为编码器输出的码字序列，其中x k = x l ，硭1 ，x l 2 ，第 一项对应信息位，后两项对应校验位。 5 ，】，可l = ( y l ，y 2 ，啪为接收到的码字，其中肌= “，1 ，妒) ，分别对 应瓢中的每一位。 2 3 1m a p 算法 m a p 算法，又称为b c j r 算法，于1 9 7 4 年由b a h l 等人提出，但是由于该 算法的计算量非常大，所以该算法一直没有引起人们的太多关注，直到b e r r o u 2 1 将其用于t u r b o 码的迭代译码，才重新了引起人们的重视。当前所使用的t u r b o 码译码器，大部分都是基于m a p 算法实现的。 一1 0 一 浙江大学硕士学位论文 s i s o 译码器的任务就是已知接收到的序列吖求解信息序列中各个符号锹 地) - 1 。g 觥p ( u ky l ( 2 9 ) 2 u lj p ( 甜t 2fly，二琶茎i一p。y墨，l s ，。2 ，。， ：掌竺尘：盛：! ! 兰旦尘! 丝! 兰! 兰翌! 丝! ! 堕 。 名p ( 计。1 ) x p ( y ki 并。1 ) p ( 硝，l y k ) p ( u i = f l y ，) = 吼一。( s ) y k ( s ，s ) f l k ( s ) p ( y ki 计一) ( 2 1 1 ) 啪) = 帮 ( 2 1 2 ) 眦) = 糍潞 ( 2 1 3 ) p l 坛+ ii “。j 1 3 k ( s ) 图2 4 蛳0 ) 和d 加) 的递推示意图【1 4 】 一1 1 浙江大学硕士学位论文 啪，= 甏黼 e p ( y 。，蹦l 计_ ) ：j i 一 p ( y k ，蹦l ) p ( m ，s p ( s i ) ( 2 1 5 ) 2 袁五瓦而雨币巧 s j 圪( s ，s ) 听一- ( j 。) 2 袁甄瓦瓦而 j j 。 眦，= 筹妊 p ( 儿，sls ) p ( 珐，is ) p ( 硝l 并。1 ) 一；p c 胪一) 裂器娥。l y l k ) p ( y ki 吖。1 ) 以( s ，s ) 孱( s ) 2 妻蠹瓦而 j s 。 a 如) 的初始条件与编码器的初始状态有关。传统t u r b o 码编码器的初始状 态总是为0 ，所以a k ( s ) 的初始化条件为： o c o o = s o ) = 1 ，( x o0 s o ) = 0( 2 1 7 ) 而p 如) 的初始条件与编码器的终止状态有关，根据是否采取截尾处理，p 如) 的初始条件会有所不同。 不采取截尾处理，那么终止状态不定，假定取每个状态的概率相同，那么 1 3 u ( s ) = 1 2 所( 2 1 8 ) m 为编码器寄存器的个数。 采取截尾处理时，终止状态为0 ，所以d 鼬) 的初始条件为： p 施= 0 ) = l ，p 施0 ) = 0( 2 1 9 ) 一1 2 浙江大学硕士学位论文 式( 2 1 1 ) 中的分母为公共项，因此删去之后式( 2 9 ) 转化为： ( 2 2 0 ) 由上1 1 1 1 阴推导辽栏口j 以友土见，m a p 算怯最百要的是对似s ，s ) 的计算， 0 【“s ) ，p “j ) 和最后的l ( u k ) 计算都需要丫和，s ) 。下面来推导似s ，s ) 的计算过程。 由式( 2 1 4 ) 可得： 以( s ，s ) 皇p ( s ，y kls 3 = p ( 几ls r , s ) p ( sls ) = p ( y ku k ) p ( = f ) ( 2 2 1 ) 其中事件对应事件状态s 转移到s 。上式中第一项： p c 眺，唧卜譬一譬i 唧_ 盟气笋盟l e x l 学 j q 2 2 却x p l 鼍掣l b k 为常数项。 式( 2 2 1 ) 中第二项p ( u k = 0 是u k 的先验概率，在t u r b o 码的迭代译码方案中， 先验概率p ( u k = f ) 由前一个子译码器的外信息三。( 砌提供： 地) = l o g 端 ( 2 2 3 ) 这里根据外信息l 。( 砌求先验概率p ( u k = f ) 由两种方式。 方式一1 5 1 ，根据式 ( 2 2 3 ) 直接求，有： 5 篇端 亿2 4 ， 以驴o ) 2 鬲茄丽 方式二【1 6 1 ，对上式进行一个简化的处理，转化成一个统一的公式： 地) = ( 糕 e x p 【u t l ( u k ) 2 】 ( 2 2 5 ) 一1 3 一 s j l 一，l 屏一履 s s 一 ，l 一，l 儿一 所 、， 一、， s j 一 听一 婴唧 g o = 己 浙江大学硕士学位论文 由于似s ，s ) 同时出现在式( 2 2 0 ) 的分子和分母，因此可以忽略彳觑： 以( s 7 ，s ) o ce x p 去( r ( ) + t 蚝) + l 。y f x ； = e x p 丢( r ( ) + t 以) 形( t s ) 我们定义： 斛垆唧 知卅 将式 ( 2 2 7 ) 代入式 ( 2 2 0 ) ，可以得到： l ( u k ) = l o g 瓯一。( 5 ) 虻( s ，j ) 厦( s b 瓯一。( s ) r f ( s ，j ) 磊o b = t 蛾+ r c ，。g ( 2 2 6 ) ( 2 2 7 ) 知聃、i 2 2 8 瓯一。( s ) 成( s ，j ) 厦( j ) 其中第一项是信息位的信道值，第二项即是由前一个子译码器传递过来的 先验概率，第三项是传递给后续子译码器的外信息，形 ，s ) 是丫如，s ) 除去信息 位的信道值与先验概率之后的值，只与校验位有关。 校验位之间由于交织器的作用，几乎独立不相关，因此外信息之间也可以 认为是不相关的，外信息在子译码器之间迭代传递，反复利用，尽可能地提高 译码器的译码性能。 2 3 2 对数域m a p 算法 由上节m a p 算法的推导过程我们可以看出，m a p 算法由大量的指数运算 和乘法运算组成，计算量很大而且因为数值比较大很容易溢出，实现非常困难。 如果我们将运算从实数域转换到对数域，那么就可以将乘法运算转换成加法运 算，运算的复杂度就可以大大降低。下面我们来介绍基于对数域的l o g m a p 算法和m a x 1 0 9 m a p 算法【15 1 。a “s ) ，p 如) 和最后的l ( u k ) t - - 算都需要丫和，s ) 我们定义7 ，i ( s ，j ) = l o g y k ( s ，s ) ，口( s ) = l o g c z k _ , ( s ) ，尾( j ) 2l o g i c s ) 。 那么由式( 2 2 6 ) ，有 一 1 1 ，t ( s ，j ) = i 1i ( r ( ) + 厶以) + t c 睇x ；i ( 2 2 9 ) 二一 由式( 2 1 5 ) ，有 一1 4 一 浙江大学硕士学位论文 口( j ) = l o g ( e x p ( 1 0 9 a k l ( s 7 ) + l o g 儿( s ，s ) ) 山矗e x 加g ) + l 啾s s ) q 3 ( s ) = l o g ( e x p ( 1 0 9f l ( s ) + l o gy k ( s 7 ，s ) ) - l o 矗e x 如脚心，) + 1 0 9 椭，一) q 3 d 式( 2 3 0 ) 和( 2 3 1 ) 的第二项都是在m a p 算法中数学推导时为了修正引入 的，这两项在( 2 2 0 ) d ? 分子分母共有，因此实际运算时完全可以将这两项略 去，而对结果丝毫没有影响。 同样的，由式( 2 2 0 ) ，可以得到： l o gl ( u k ) = l o g ( e x p ( 1 0 9a k l ( s ) + l o gy ( j 7 ，s ) + l o gf l k ( s ) ) 山g 亳e x p ( 1 。函) + l o g 加，+ l o g 确) q 3 2 现在列出在l o g 域计算中要引入的两个重要的算式： l o g ( & 历) = l o g ( 西) + l o g ( 国) l n ( e 焉+ p 如) = m a x ( a , ，8 2 ) + l o g ( 1 + e - i 最一磊1 ) 其中m a x ( a i ，8 2 ) 茭b 取最大值函数。 这里我们定义 m a x ( 4 ，4 ) = m a x ( 8 , ，嘎) + 正( i4 一磊i ) 极l 西一为1 ) 为修正函数。 ( 2 3 3 ) ( 2 3 4 ) ( 2 3 5 ) 另外实际中我们需要求的是l n ( e x p 8 i + + e x p s ) ，该式可以由( 2 3 4 ) 递 归求得。假设己知万= l n ( e x p 6 i + + e x p 8 一1 ) ，那么： h a ( e 4 + + p 磊) = l n ( e j + p 磊) = m a x ( 5 ，瓯) + z ( f 万一皖i ) 其中，= 6 ，6 1 + + 扩。 那么式( 2 3 0 ) ( 2 3 1 ) ( 2 3 2 ) 分别转化为： 赢( s ) = m ，a 。x ( 孤( s ) + 无( s ，j ) ) ，m 。s a ，x 。s ( - d t 一( s ) + 歹t ( s 7 ，s ) ) ( 2 3 6 ) ( 2 3 7 ) 成一l ( s ) = m a 。x 。( i ( s ) + y t ( s 7 ，s ) ) 二巍m ) + - l ( t 呦 q 3 酌 浙江大学硕士学位论文 上面两个式子的第二项是修正项，在 ( 2 3 9 ) 为公共项，因此可以省略。 1 0 9 地) 2 警n 瓦，+ 蟹) )( 2 3 9 ) 一m s a x ( 口( s 7 ) + 7 i ( s ，j ) + ( j ) ) 。 由上面的推导过程很明显可以看出对数域的m a p 算法大大简化了译码的 复杂度。 o 7 0 6 0 5 寅0 4 2 0 3 o 2 0 1 0 0 i x i 图2 5 修正函数以j 西一历i ) 1 1 7 1 但是修正函数五( i 西一历i ) 中还存在着大量的指数运算，运算复杂度比较高。 图2 5 描绘出了修j 下函数的曲线，通过各种近似的方法，可以设计不同的 l o g m a p 简化方法。 最简单地，省略修正函数： m a x 。( 4 ，嚷) = m a x ( 磊，疋)( 2 4 0 ) 这就是m a x - l o g m a p 算法。在信噪比较高的时候，磊与破相差较大， 烈i 西一迈i ) 值趋向与0 ，因此m a x 1 0 9 m a p 算法在信噪比较高的时候能获得接近 与l o g - m a p 算法的性能。 也可以通过采用查表近似的方法，只需要存储8 个值就能非常接近 l o g m a p 算法的性能1 5 1 。或者更进一步简化，只存储2 个值，即 c o n s t a n t l o g m a p 算法【1 8 】： m 寂c 4 ，疋，= m a x c 磊，岛，+ ：耄二囊凄； c 2 4 ， 浙江大学硕士学位论文 仿真表明，取c = 0 5 ，丁= 1 5 时性能最好。 也可以采用线性化的近似方法，即l i n e a r - l o g m a p 算法【1 9 1 ： m a x c 磊，岛，= m a x c 4 ，嘎，+ f o 。i4 一岛i 一丁，f 蓦二囊占； c 2 4 2 ， 仿真表明，取口= 一0 2 4 9 0 4a n d 产2 5 0 6 8 时性能最好。 显而易见，实现上m a x - l o g m a p 算法最简单，不需要修正函数，但是性能 上却有比较大的下降，通常会有o 4 到0 6 d b 的下降。增强型m a x l o g m a p 算 法【2 0 】在外信息传递时用校验因子加以修正，很好地减少了性能的下降： l ( u t ) = s f x ( t 少+ 乞( ) + 厶( ) )( 2 4 3 ) 对于3 g p p 来说，校验因子矿取o 7 时能获得显著的性能改善。 2 3 3 几种译码算法的比较 本节我们对上节所述各种不同译码算法进行了性能仿真。编码器采用3 g p p 的( 1 3 ，1 5 ) 编码器，码率为l 3 ，帧长1 5 0 4 ，a w g n 信道，b p s k 调制，交织器 为3 g p p 交织器。 1 1 e 1 1 e - 2 1 e - 3 叱 山 1e 4 1 e 5 1 e 与 1 e 7 - 0 2 0 0 0 20 40 60 81 0 1 21 41 6 1 8 e b n 0 ( d b ) 图2 6 传统t u r b o 码不同译码算法的误码率 一1 7 浙江大学硕