基于预译码技术的Turbo码译码方法

，，，

(南京理工大学电子工程与光电技术学院， 江苏 南京 210094)

0 引言

早在1948年，现代数字通信的奠基人香农从理论上证明了只要信息传输速率小于信道容量，总存在一种编码方式使得错误概率任意小。自定理[1]提出以来，学者们提出了众多的编码方式，不断朝着香农限逼近，但是距离香农极限还存在不小差距。直到1993年，C.Berrou,A.Glavieux和P.Thitimasjshima在国际通信会议上提出了Turbo码[2]，其优异的性能引起了广大学者的研究热潮。目前,Turbo码被看作是网格编码调制技术问世以来,信道编码理论研究上所取得的最伟大的技术成就,具有里程碑的意义。双二进制Turbo码在编码效率、译码时延、纠错性能等方面优于传统的Turbo码。但现有双二进制Turbo码译码器对预译码所得信息利用率较低。本文针对此问题，提出了基于预译码技术的Turbo码译码方法，以及减小FPGA实现复杂度的方法。

1 编译码原理

编码器决定了一种码的性能，译码器最大限度地挖掘这种码的优势，Turbo码的优异性能来自于巧妙的编码结构和循环迭代译码思想。

1.1 编码原理

图1所示为双二进制Turbo码编码器结构，交织器消除两个子码之间的相关性，突发错误下交织器有利于级联码的纠错[3]，删余器通过对校验位进行删余提高码率。与传统Turbo码不同的是输入序列是由两个比特信息位组成的符号，因此得名双二进制Turbo码。信息位输入分为两个支路，每个支路由A,B两路组成，开关打到上支路，A,B两路送入编码器，输出三路校验位V,Y,W，开关打到下支路，A,B两路通过交织器再送入编码器，输出三路校验位V′，Y′，W′。最后通过删余器可以形成多种速率的编码输出。

分量码编码器采用自截尾[4-5]的循环递归系统卷积码。传统的编码器采用添加全零尾比特使得编码器的初始状态和终止状态全为零，但是双二进制Turbo码由于交织器的存在不能保证两个分量码编码器终止状态同时为零。自截尾机制原理是在确定生成矩阵的情况下，通过数学推导可以推导出只与信息位长度和预编码末状态有关的查找表,查找表所得即为循环状态Sc,预编码即编码器初始状态为零的一次编码。

在数学推导前，我们定义编码器的生成矩阵为G，k时刻编码器状态为Sk，k时刻输入序列为Pk，则可用下式表示该卷积编码器：

Sk+1=GSk+Pk

(1)

由上式进行递推可得到编码器初始状态与终止状态的关系表达式：

(2)

为了实现自截尾机制，要求S0=SN=Sc，即：

(3)

由上式可知循环状态Sc存在的条件是I+GN可逆，观察式(2)和式(3)可得如下关系式：

(4)

对于图1所示编码器，根据式(4)可列出如下查找表[6]。

表1 循环状态查找表Tab.1 Look-up table of Circular state

表1为图1的查找表，双二进制Turbo码编码分为两步，首先，编码器初始状态为零进行编码，编码终止状态作为列索引，信息长度模7作为行索引进行查表，查表所得即为正式编码的循环状态Sc。最后，将预编码所得循环状态作为编码器的初始状态进行编码，编码所得序列即为最终编码。

1.2 译码原理

Turbo码常用的算法有SOVA算法[7]，MAP算法[8]以及改进的MAP算法。SOVA算法复杂度上低于MAP算法，但是性能较差。目前常用的是MAX-LOG-MAP算法[9]。

图2所示的框图是下文介绍的译码算法的整体框图。该算法分成预译码和正式译码，预译码估计编码的循环状态Sc。预译码和正式译码的内部结构相同，在FPGA实现时，预译码和正式译码可以共用一个模块，节省FPGA资源，降低实现复杂度。

(5)

在这里引入三个递归矩阵，分别为前向递归矩阵αk(s)，分支度量矩阵γk(s′，s)，后向递归矩阵βk(s)，其数值代表编码器该时刻各个状态的概率，公式(5)可以转换为这三个矩阵的表达式[10]，如下所示：

(6)

最后根据后验似然比进行判决。由于编码器采用了自截尾，所以αk(s)和βk(s)的初始状态都为循环状态，但对于接收端的译码器循环状态是未知的，故需要先进行预译码估计循环状态再进行译码[11-13]。

1.2.1预译码

式(7)和式(8)分别是前向递归矩阵αk(s)，后向递归矩阵βk(s)的递归公式：

(7)

(8)

由公式可知αk(s)和βk(s)分别是由α0(s)和βN(s)根据分支度量矩阵γk(s′，s)递推而得的，但是预译码前不知初始状态，所以假设初始状态在每个状态的可能性是相等的，即：

α0(s)=2-m,s=0,1,2,…,2m-1

(9)

βN(s)=2-m,s=0,1,2,…,2m-1

(10)

α0(s)通过前向递推得到的αN(s)正是终止状态的概率分布，经过多次迭代，取最后一次迭代所得的αN(s)，得到：

(11)

同理，β0(s)正是初始状态的概率分布：

(12)

(13)

1.2.2正式译码

正式译码与预译码整体框架一致，只是α0(s)和βN(s)的初始状态与预译码时有所不同：

α0(s=Sc)=1,α0(s≠Sc)=0

(14)

βN(s=Sc)=1,βN(s≠Sc)=0

(15)

其中，Sc为预译码所得的循环状态。

上文提到的前向递归矩阵αk(s)和后向递归矩阵βk(s)是根据分支度量矩阵γk(s′，s)递推得到的，在预译码后确定了两个递归矩阵的初始状态，然后再由式(7)和式(8)递归出αk(s)和βk(s)，所以确定γk(s′，s)后就能递推得到所有的衡量矩阵。

2 基于预译码的译码方法

在Turbo出现以前，信道编码使用的算法是最大似然算法(ML)，它假设信源输出0,1是等概率出现的，是一种次优的译码算法。香农信息论指出最优的译码算法是最大后验概率算法(MAP)，Turbo码译码器采用了最大后验概率算法，但正式译码的第一次译码迭代将信源符号假设为等概率出现，下文将介绍一种利用预译码为正式译码提供先验信息的方法，以及一种减小FPGA运算量的方法。

2.1 一种利用预译码为正式译码提供先验信息的方法

Turbo码译码还存在另一种译码方式，即不进行循环状态的预估计，将预译码作为一次完整的译码，对预译码所得的后验似然比直接进行判决，得到译码数据。我们在AWGN信道下进行了仿真，如图3所示。编码器为图1所示，码率为1/3，帧长2 808 bit，BPSK调制，预译码迭代6次。虽然预译码直接进行判决性能较差，但其后验似然比是有效的。

受该译码方法的启发，可将预译码所得的后验似然比转换为后验概率作为正式译码的先验概率。图4所示为改进后的译码框图，其中L(μk)为预译码所得的后验似然比。

根据式(5)，我们可以由后验似然比L(μk)反推出每个符号的后验概率：

P(μk=0|Y)=(1+eL(μk=1)+
eL(μk=2)+eL(μk=3))-1

(16)

P(μk=i|Y)=eL(μk=i)×
(1+eL(μk=1)+eL(μk=2)+eL(μk=3))-1
i=1,2,3

(17)

正式译码时将P(μk|Y)作为每个符号的先验概率。

2.2 一种分支度量矩阵生成的方法

图1所示的分量编码器状态机为3位，有8个状态，在某个状态下，根据输入的2位信息位可向下一个状态转移，故在某状态下可向4个不同的状态转移，所以分支度量矩阵在某时刻有32个分支，并且每个分支有确定的信息位和校验位。

译码器的输入为软信息，本文所用的软信息为3比特量化，故可将软信息转化为8个可信度等级，然后可用下表计算分支度量矩阵每条分支的可信度，由于运算是在对数域上进行的，所以下表的可信度是负值的。

行索引为该分支对应的信息位或者校验位，列索引为输入的软信息，查表所得为该分支可信度的一个度量。以四分之一码率编码器为例，译码器中的一个子译码器每个时刻有2位信息位和3位校验位，则该子译码器的分支度量矩阵中一条分支的可信度为5个度量之和。

表2 可信度查找表Tab.2 Look-up table of reliability

我们定义k时刻收到的信息位为ak和bk，校验位为wk、yk、vk，信息位和校验位都为3比特，k时刻第i条分支理论的信息位为Ak,i和Bk,i，校验位为Wk,i，Yk,i，Vk,i，则k时刻分支度量矩阵的生成公式为：

γk,i=〈Ak,i|ak〉+〈Bk,i|Bk〉+
〈Wk,i|wk〉+〈Yk,i|yk〉+〈Vk,i|vk〉
i=1,2,3,…,32

(18)

式中，〈|〉符号代表查找表所得的数值。

3 仿真与FPGA实现

我们使用Matlab对改进后的译码方法进行了性能仿真，编码器为图1所示，码率为1/3，帧长2 808 bit，AWGN信道，BPSK调制，预译码迭代3次，正式译码迭代3次。

图3仿真曲线直接对预译码的后验似然比进行判决，误比特率明显降低，说明预译码的后验似然比是具有参考价值的。通过式(16)和式(17)将后验似然比转换为后验概率并作为正式译码的先验概率加快了译码的收敛速度，由仿真图5可知改进后能提高约0.3 dB的性能。并且该方法没有对译码结构和译码迭代次数进行改变，所以译码时延以及资源消耗和改进前保持一致。

关于γk(s′，s)的生成，我们采用了可信度查找表的方法，还有一种常用的方法是欧氏距离生成法。我们对两种生成方式在AWGN信道下进行了仿真，如图6所示。编码器为图1所示，码率为1/3，帧长2 808 bit，BPSK调制，预译码迭代3次，正式译码迭代3次。两者性能基本没有差别，但是可信度查找表的方法较欧氏距离生成法计算量小很多。

在实现方面，本文所用的FPGA为Spartan3系列的xc3s2000，时钟频率为38.4 MHz。图7所示为FPGA实现的总框图，其中实线表示数据流向，虚线表示控制信号或地址。图1编码器中两个分量码的结构一致，所以译码器的两个分量码译码器可以共用一个模块以节省FPGA资源。控制模块控制译码迭代次数，信息序列的交织以及后验似然比的解交织。图7中分量码译码器与似然比存储器形成了一个环路，在控制模块的控制下，分量码译码器对信息序列进行顺序译码和交织译码，迭代次数满足停止准则后，断开环路对最后一次迭代得到的符号似然比进行判决输出。顺序译码指信息序列和对应校验序列有序输入分量码译码器进行译码，交织译码指信息序列交织后和对应校验序列输入分量码译码器进行译码。交织映射表存储器在控制模块控制下，为输入数据缓冲器和似然比存储器提供交织地址。

由于FPGA资源和译码时延的限制，输入的数据为3 bit量化，译码迭代次数为6次，其中3次预译码迭代，3次正式译码迭代,在时钟频率为38.4 MHz的情况下，一次迭代FPGA耗时5 ms左右。

4 结论

本文提出了基于预译码技术的Turbo码译码方法，该方法将预译码所得的后验似然比转换为后验概率并作为正式译码的先验概率，仿真结果表明该方法可以提升0.3 dB的译码性能，并且译码时延以及资源消耗和改进前保持一致。最后修改了分支度量矩阵生成方式，与欧式距离生成法译码性能差不多，时延降低，在时钟频率为38.4 MHz的情况下，一次迭代FPGA耗时为5 ms左右。

参考文献:

[1]Shannon C E. A mathematical theory of communication[J]. Bell System Tech. J.,1948(1):876-878.

[2]Berrou C, Glavieux A, Thitimajshima P. Near shannon limit error-correcting coding and decoding： Turbo codes[C]// in Proc. 1993 Int. Conf. Comm,1993(2):1064-1070.

[3]郝天铎,王可人,金虎,等.不同错误图样分布对级联码译码性能的影响[J].探测与控制学报,2015,36(3)：86-90.

[4]Berrou C, Douillard C, Jézéquel M. Multiple parallel concatenation of circular recursive convolutional (CRSC) codes[J]. Annals of Telecommunications, Tome 54, N°3-4, 2000:21-24.

[5]Anderson J B, Hladik S M. Tailbiting MAP decoders[C]// IEEE J. Sel, Areas Commun, 1998,16(2):297-302.

[6] Soleymani MR,Gao Yingzi,Vilaipornsawai.Turbo coding for Satellite and Wireless Communications[M].Massachusetts：Kluwer Academic Publishers,2002.

[7] Hagenauer J, Hoeher P. A Viterbi algorithm with soft-decision out-puts and its applications[C]// in Proc. Global Telecommunications Conf,1989(3):1680-1686.

[8] Bahl l, Cocke J, Jelinek F, et al. Optimal decoding of linear codes for minimizing symbol error rate[C]// IEEE Trans. Inf. Theory, 1974:284-287.

[9] Roberston P, Villebrun E, Hoeher P. A comparison of optimal and sub-optimal MAP decoding algorithms operatiting in the log domain[C]// in Proc. IEEE Int. Conf. Communications, 1995:1009-1013.

[10] 朱益.双二进制Turbo码的研究[D].杭州：浙江大学,2008.

[11] Im S B, Kim M G, Choi H J. An Efficient Tail-biting MAP Decoder for Convolutional Turbo Codes in OFDM System[C]// IEEE Region 10 Conference, TENCON 2004 Volume B,2004：589-592.

[12] Giancristofaro D, Bartolazzi A. Novel DVB-RCS standard Turbo Code：details and performances of a decoding algorithm[C]// ESA conference, 2001:467-469.

[13] Douillard C, Jezequel M, Berrou C, The Turbo code Standard for DVB-RCS[C]// 2nd International Symposium on Turbo Codes & Related Topics, Brest, France, 2000:535-538.