卷积Turbo码双向并行译码方法

摘要

本发明提供一种减少译码延时、节省存储器的卷积Turbo码的译码方法。在分量译码过程中，本发明将前向递归与后向递归同时进行，前向、后向递归分为运算量相当的两个阶段，后验似然比信息在第二阶段的开始就能依次计算得到。即从开始递归运算开始至后验似然比信息运算结束时的延时，本发明相比现有的译码过程缩短了一倍。并且，现有的后验似然比运算是串行，本发明的后验似然比运算采用双向并行同时进行，所需的计算时间与递归计算的时间重合，则不需另外分配计算时间，此外，双向并行的结构可以使得用来存储状态度量的存储器减半。进一步的，通过拆分分支度量的计算，减少冗余计算并且存储分支度量的空间减半。

说明书

技术领域

本发明属于通信领域，主要涉及信道编码，尤其是Turbo码译码的相关技术。

背景技术

自从迭代译码概念的提出开始，Turbo码就被广泛研究和应用。卷积Turbo码(CTC)以其 编码效率更高、编码速度更快和自由距离更大的特点得以在近年来快速发展，目前已被标准 802.16e和802.16m选作物理层的前向纠错码型。

标准802.16m选用双二元卷积Turbo码(DB-CTC)作为信道编码方案之一。系统码DB-CTC 是在编时每一时刻并行输入2比特信息，输出6比特。由于采用了二次编码的方案，编码前、 后的状态一致，从而无需收尾比特。然而DB-CTC的这些特点也使得其译码比较复杂。

DB-CTC的译码器采用两个相同分量译码器并行迭代的结构，待译码的数据(卷积Turbo 码经信号传输后的信号符号经软解调后所得到的软信息值(信道软输出似然比信息))分别输 入这两个分量译码器(分量译码器1、分量译码器2)，分量译码器1输出后验似然比信息，并 将该后验似然比信息作为外部信息再经过交织后传回给分量译码器2作为译码的先验似然比 信息；分量译码器2经译码后输出后验似然比信息，并作为外信息经解交织后成为分量译码 器1的先验似然比信息，由此完成一次迭代。当达到预设的最大迭代次数时，分量译码器2 输出的后验似然比信息经解交织和硬判决，得到最终的译码结果。卷积Turbo码的迭代译码 正是通过在两个分量译码器间相互传递外部信息的方式逐渐使译码结果收敛，并由此提高译 码性能。

由于MAP算法的实现过程中含有大量的乘法运算和中间变量，因此译码复杂度高，且译 码时延长。所以在仿真研究和工程中常用MAP算法的改进型Log-MAP算法或其简化型 Max-Log-MAP译码算法。虽然减少了乘法运算，但是采用了Log-MAP算法或Max-Log-MAP 算法的分量译码器仍然有较长的译码延时。

分量译码器用于将接收的信道软信息值通过MAP算法计算输出后验似然比信息。采用了 Log-MAP算法或Max-Log-MAP算法的分量译码器的译码过程包括：分支度量的计算、前向 递归、后向递归和后验似然比信息的计算。第i时刻的后验似然比信息L_i(i＝0，...，N-1)由第 i时刻的前向状态度量、第i+1时刻的后向状态度量以及第i时刻的分支度量计算得到，N为 卷积Turbo码编码过程中输入的双二元比特组长度。通常，分量译码器用从信道软解调的软 信息值计算0至N-1时刻的分支度量后，需要先通过前向递归依次计算出从0至N时刻的前 向状态度量，并进行存储，之后再通过后向递归依次计算从N至0时刻的后向状态度量，并 存储。最后，进行后验似然比信息的计算。0至N-1时刻的前向状态度量、1至N时刻的后 向状态度量用于0至N-1时刻的后验似然比信息的直接计算，第N时刻的前向状态度量、第 0时刻的后向状态度量用作初始化下一次迭代的状态度量。

发明内容

本发明所要解决的技术问题是，采用双向并行的译码结构，提供一种减少译码延时、节 省存储器的卷积Turbo码的译码方法。

本发明为解决上述技术问题所采用的技术手段是，卷积Turbo码双向并行译码方法，包 括：

待译码的数据输入采用两个分量译码器并联的迭代译码器；

当未达到预设最大迭代次数时，分量译码器译码后输出后验似然比信息，转化为外部信 息，再经交织或解交织后，作为先验似然比信息输入至所述另一个分量译码器；

当达到预设最大迭代次数时，最后一个工作的分量译码器经译码后输出的后验似然比信 息，经解交织和硬判决，得到译码结果；

其特征在于，分量译码器的译码过程具体包括以下步骤：

分支度量计算与双向递归的初始化步骤：利用输入的待译码的数据与先验似然比信息计 算并存储从0至(N/2)-1时刻的前N/2个时刻的分支度量、N/2至N-1时刻的后N/2个时刻 的分支度量，初始化第0时刻的前向状态度量与第N时刻的后向状态度量；所述N为双二元 比特组长度；

第一阶段步骤：以初始化的第0时刻的前向状态度量为起点，用前N/2个时刻的分支度 量参与前向递归计算，依次得到0至N/2时刻的前向状态度量，并存储；同时，以第N时刻 的后向状态度量为起点，用后N/2个时刻的分支度量参与后向递归计算，依次得到N至N/2 时刻的后向状态度量，并存储；

第二阶段步骤：以第N/2个时刻的后向状态度量为起点，用前N/2个时刻的分支度量度量 参与后向递归计算，依次得到从N/2至0时刻的后向状态度量，并依次与第一阶段存储的(N/2) -1至0时刻的前向状态度量以及前N/2个时刻的分支度量一起参与后验似然比计算，得到从 (N/2)-1至0时刻的前N/2个时刻的后验似然比信息；同时，以第N/2时刻的前向度量为起 点，用后N/2个时刻的分支度量参与前向递归计算依次得到N/2至N时刻的前向状态度量， 并依次与第一阶段存储的(N/2)+1至N时刻的后向状态度量以及后N/2个时刻的分支度量 一起参与后验似然比计算，得到从N/2至N-1时刻的后N/2个时刻的后验似然比信息。

相比现有的分量译码器需前向递归完成后，才后向递归开始，然后后验似然比信息才能 开始计算；本发明将前向递归与后向递归同时进行，前向/后向递归分为运算量相当的两个阶 段，后验似然比信息在第二阶段的开始就能依次计算得到。即从开始递归运算开始至后验似 然比信息运算结束时的延时，本发明相比现有的译码过程缩短了一倍。并且，现有的后验似 然比运算是串行，本发明的后验似然比运算采用双向并行同时进行，所需的计算时间与递归 计算的时间重合，则不需另外分配计算时间，此外，双向并行的结构可以使得用来存储状态 度量的存储器减半。

具体的，分支度量的计算为：

γ_k(s’，s)＝L^a(u_k)+1/2×v_kar_ka+1/2×v_kar_kb+1/2×v_kyr_ky+1/2×v_kwr_kw；

其中，k表示当前时刻，s’为当前时刻的可能状态，s为下一时刻的可能状态，γ_k(s’，s)为k 时刻状态s’转移到k+1时刻状态s的分支度量，u_k＝(u_ka，u_kb)为第k时刻输入编码器的双二元比 特信息，L^a(u_k)为第k时刻的先验似然比信息，v_k＝(v_ka，v_ka，v_ky，v_kw)为发送比特，r_k＝(r_ka，r_kb，r_ky，r_kw) 表示信道接收的第k时刻的待译码的数据(软解调后的软信息值)。

进一步的，为了减少分支度量的计算量，在计算分支度量时，将分支度量拆分为两个因 子p_k和q_k：

p_k＝L^a(u_k)+1/2×v_kar_ka+1/2×v_kar_kb；

q_k＝1/2×v_kyr_ky+1/2×v_kwr_kw。

根据v_k＝(v_ka，v_ka，v_ky，v_kw)的取值，则p_k共有p_k，00，p_k，01，p_k，10，p_k，11四种取值，q_k共有q_k，00， q_k，01，q_k，10，q_k，11四种取值，所以每两个时刻间的32个分支度量(16个不同值)可以用8个 因子全部构造出来。相对经典Log-MAP算法以及Max-Log-MAP算法每个时刻计算分支度量 需要进行80次乘法和64次加法，经拆分后的分支度量仅需要做24次乘法和28次加法(包 括用因子构造分置度量的加法)；相对经典Log-MAP算法以及Max-Log-MAP算法每个时刻 计算分支度需存储16个不同值，经拆分后的分支度量仅需存储8个不同因子。

本发明的有益效果是，在分支译码器的译码过程中，采用双向并行的方式计算状态度量 与后验似然比信息，将进行前向、后向递归的操作同时进行，时间减半，并把后验似然比的 计算时间融入到递归操作的时间里，由此大大减小了译码延时与状态度量的存储空间；进一 步的，通过拆分分支度量的计算，减少冗余计算并且存储分支度量的空间减半。

附图说明

图1为DB-CTC编码在任两个时刻之间的网格图；

图2为分量译码器中内部译码示意图。

具体实施方式

本发明针对卷积Turbo译码中分量译码器中的译码过程进行改进，其他处理过程不变， 卷积Turbo译码过程包括：

待译码的数据、先验似然比信息输入两个分量译码器并联的迭代译码器；

当未达到预设最大迭代次数时，分量译码器译码后输出后验似然比信息，转化为外部信 息，再经交织或解交织后，作为先验似然比信息输入至所述另一个分量译码器；

当达到预设最大迭代次数时，最后工作的分量译码器译码输出后验似然比信息，经解交 织和硬判决，得到译码结果。

本实施例在不改变原有误码性能的条件下对分量译码器Log-MAP译码方法进行改进：包 括分支度量的拆分和双向并行运算。

分支度量是联系分量译码器输入和输出的关键量，在递归计算前向状态度量和后向状态 度量时和在计算后验似然比信息时都会用到分支度量，而分量译码器的最终目的是输出后验 似然比信息(后验似然比信息的计算需要前向状态度量、后向状态度量和分支度量)。

如图1所示，任两个时刻之间都有32条分支度量，共16个不同值。分支度量的计算公 式为：

γ_k(s’，s)＝L^a(u_k)+1/2×v_kar_ka+1/2×v_kar_kb+1/2×v_kyr_ky+1/2×v_kwr_kw，

其中，s’为当前时刻的可能状态，s为下一时刻的可能状态，γ_k(s’，s)为k时刻状态s’转移 到k+1时刻状态s的分支度量，u_k＝(u_ka，u_kb)为k时刻输入编码器的双二元比特信息，L^a(u_k)为 k时刻的先验似然比信息，v_k＝(v_ka，v_ka，v_ky，v_kw)为发送比特，r_k＝(r_ka，r_kb，r_ky，r_kw)表示信道接收的第k 时刻的软值。

将分支度量拆分为两个因子p_k和q_k，其中：

p_k＝L^a(u_k)+1/2×v_kar_ka+1/2×v_kar_kb

q_k＝1/2×v_kyr_ky+1/2×v_kwr_kw

根据v_k＝(v_ka，v_ka，v_ky，v_kw)的取值，则p_k共有p_k，00，p_k，01，p_k，10，p_k，11四种取值，q_k共有q_k，00， q_k，01，q_k，10，q_k，11四种取值，所以每两个时刻间的16个分支度量可以用8个因子全部构造出来。 于是计算分支度量拆分成的因子可以减少计算冗余，节省存储器。

引入分支度量的拆分后，求第k+1时刻的前向状态度量α_k+1(k 0，…，N)的前向递归 运算为：第k时刻的前向状态度量矩阵A_k与第k时刻的前向递归矩阵C_k求和，求和得到的矩 阵第i行的各个元素取自然指数后相加，求和后再取自然对数，就是第k+1时刻状态s′_i-1所对 应的前向状态度量，i＝1，2，...8。

其中，第k时刻的前向状态度量矩阵A_k与第k时刻的前向递归矩阵C_k相加表示为：

$A_k+C_k=\left(\begin{array}{cccc}{\alpha }_k\left(s_0\right)& {\alpha }_k\left(s_1\right)& {\alpha }_k\left(s_6\right)& {\alpha }_k\left(s_7\right)\\ {\alpha }_k\left(s_2\right)& {\alpha }_k\left(s_4\right)& {\alpha }_k\left(s_3\right)& {\alpha }_k\left(s_5\right)\\ {\alpha }_k\left(s_5\right)& {\alpha }_k\left(s_3\right)& {\alpha }_k\left(s_4\right)& {\alpha }_k\left(s_2\right)\\ {\alpha }_k\left(s_7\right)& {\alpha }_k\left(s_1\right)& {\alpha }_k\left(s_6\right)& {\alpha }_k\left(s_0\right)\\ {\alpha }_k\left(s_1\right)& {\alpha }_k\left(s_7\right)& {\alpha }_k\left(s_0\right)& {\alpha }_k\left(s_6\right)\\ {\alpha }_k\left(s_3\right)& {\alpha }_k\left(s_5\right)& {\alpha }_k\left(s_2\right)& {\alpha }_k\left(s_4\right)\\ {\alpha }_k\left(s_4\right)& {\alpha }_k\left(s_2\right)& {\alpha }_k\left(s_5\right)& {\alpha }_k\left(s_3\right)\\ {\alpha }_k\left(s_6\right)& {\alpha }_k\left(s_0\right)& {\alpha }_k\left(s_7\right)& {\alpha }_k\left(s_1\right)\end{array}\right)+\left(\begin{array}{cccc}{p}_{k,00}+q_{k,00}& p_{k,01}+q_{k,10}& p_{k,10}+q_{k,11}& p_{k,11}+q_{k,01}\\ p_{k,00}+q_{k,10}& p_{k,01}+q_{k,00}& p_{k,10}+q_{k,01}& p_{k,11}+q_{k,11}\\ p_{k,00}+q_{k,11}& p_{k,01}+q_{k,01}& p_{k,10}+q_{k,00}& p_{k,11}+q_{k,10}\\ p_{k,00}+q_{k,01}& p_{k,01}+q_{k,11}& p_{k,10}+q_{k,10}& p_{k,11}+q_{k,00}\\ p_{k,00}+q_{k,00}& p_{k,01}+q_{k,10}& p_{k,10}+q_{k,11}& p_{k,11}+q_{k,01}\\ p_{k,00}+q_{k,10}& p_{k,01}+q_{k,00}& p_{k,10}+q_{k,01}& p_{k,11}+q_{k,11}\\ p_{k,00}+q_{k,11}& p_{k,01}+q_{k,01}& p_{k,10}+q_{k,00}& p_{k,11}+q_{k,10}\\ p_{k,00}+q_{k,01}& p_{k,01}+q_{k,11}& p_{k,10}+q_{k,10}& p_{k,11}+q_{k,00}\end{array}\right)$

                                                                a_k(s_i) (i＝1，2，...8)表示第k时刻状态s_i的前向状态度量。从前向递归矩阵C_k中看出分支度量由p_k与q_k两种因子构成。矩阵C_k的行1和5、2和6、3和7、4和8分别相等，即只需计算出C_k的前四行就可以表示出C_k。任一因子p_k，ij或q_k，ij在矩阵C_k中出现的次数均为8，对这些因子 只需计算一次而非经典Log-MAP算法的4次，这样就消除了原有算法中的冗余计算。

类似的，求第k时刻的后向状态度量β_k的后向递归运算为：后向状态度量矩阵B_k+1与后 向递归矩阵D_k求和，求和得到的矩阵的每行各个元素取自然指数后分别求和，求和后取自然 对数即为该行所对应的后向递归结果。

其中，第k+1时刻的后向状态度量矩阵B_k+1与第k时刻的后向递归矩阵D_k相加表示为：

$B_{k+1}+D_k=\left(\begin{array}{cccc}{\beta }_{k+1}\left(s_0\right)& {\beta }_{k+1}\left(s_3\right)& {\beta }_{k+1}\left(s_4\right)& {\beta }_{k+1}\left(s_7\right)\\ {\beta }_{k+1}\left(s_4\right)& {\beta }_{k+1}\left(s_7\right)& {\beta }_{k+1}\left(s_0\right)& {\beta }_{k+1}\left(s_3\right)\\ {\beta }_{k+1}\left(s_1\right)& {\beta }_{k+1}\left(s_2\right)& {\beta }_{k+1}\left(s_5\right)& {\beta }_{k+1}\left(s_6\right)\\ {\beta }_{k+1}\left(s_5\right)& {\beta }_{k+1}\left(s_6\right)& {\beta }_{k+1}\left(s_1\right)& {\beta }_{k+1}\left(s_2\right)\\ {\beta }_{k+1}\left(s_1\right)& {\beta }_{k+1}\left(s_2\right)& {\beta }_{k+1}\left(s_5\right)& {\beta }_{k+1}\left(s_6\right)\\ {\beta }_{k+1}\left(s_5\right)& {\beta }_{k+1}\left(s_6\right)& {\beta }_{k+1}\left(s_1\right)& {\beta }_{k+1}\left(s_2\right)\\ {\beta }_{k+1}\left(s_0\right)& {\beta }_{k+1}\left(s_3\right)& {\beta }_{k+1}\left(s_4\right)& {\beta }_{k+1}\left(s_7\right)\\ {\beta }_{k+1}\left(s_4\right)& {\beta }_{k+1}\left(s_7\right)& {\beta }_{k+1}\left(s_0\right)& {\beta }_{k+1}\left(s_3\right)\end{array}\right)+\left(\begin{array}{cccc}{p}_{k,00}+q_{k,00}& p_{k,11}+q_{k,00}& p_{k,10}+q_{k,11}& p_{k,01}+q_{k,11}\\ p_{k,00}+q_{k,00}& p_{k,11}+q_{k,00}& p_{k,10}+q_{k,11}& p_{k,01}+q_{k,11}\\ p_{k,00}+q_{k,10}& p_{k,11}+q_{k,10}& p_{k,10}+q_{k,01}& p_{k,01}+q_{k,01}\\ p_{k,00}+q_{k,10}& p_{k,11}+q_{k,10}& p_{k,10}+q_{k,01}& p_{k,01}+q_{k,01}\\ p_{k,01}+q_{k,00}& p_{k,10}+q_{k,00}& p_{k,11}+q_{k,11}& p_{k,00}+q_{k,11}\\ p_{k,01}+q_{k,00}& p_{k,10}+q_{k,00}& p_{k,11}+q_{k,11}& p_{k,00}+q_{k,11}\\ p_{k,01}+q_{k,10}& p_{k,10}+q_{k,10}& p_{k,11}+q_{k,01}& p_{k,00}+q_{k,01}\\ p_{k,01}+q_{k,10}& p_{k,10}+q_{k,10}& p_{k,11}+q_{k,01}& p_{k,00}+q_{k,01}\end{array}\right)$

                                                                β_k+1(s_i) (i＝1，2，...8)表示第k+1时刻状态s_i的后向状态度量。

因为前向递归与后向递归运算的相对独立性和对称性，在同一时间内可以实现双向并行 递归运算，而似然比信息的计算也同样并行完成。

分量译码器中双向并行运算如图2所示，其中虚线将双向并行结构分为两个阶段，虚箭 头表示运算的方向。包含状态度量的实线方格为单位存储器，虚线方格中的状态度量为临时 存储的状态度量(也即节省的用来存储状态度量的存储器)。α_k、β_k分别表示第k时刻的全部 前向状态度量和第k时刻的全部后向状态度量。分量译码器接收到的软信息参与计算得到分 支度量因子，并存入存储器，如P_k＝{p_k，00，p_k，01，p_k，10，p_k，11}、Q_k＝{q_k，00，q_k，01，q_k，10，q_k，11}为 第k时刻的8个因子。α₀和β_N用于初始化递归运算，α_N/2和β_N/2为第一阶段递归所得，用来 作为第二阶段状态度量递归的起点。α_N和β₀用来初始化下一次迭代的相应状态度量。后验似 然比信息为分量译码器的输出，在图2中，包含后验似然比L_k(k＝0，1，2，...，N-1)的模块负责 计算后验似然比信息。

分量译码器的译码过程具体包括以下步骤：

分支度量拆分的计算步骤：利用输入的待译码的数据与先验似然比信息计算并存储从0 至(N/2)-1时刻的前N/2个时刻的P、Q因子、N/2至N-1时刻的后N/2个时刻的全部的P、 Q因子；

初始化步骤：初始化第0时刻的前向状态度量；初始化第N时刻的后向状态度量；N为 双二元比特组长度；

第一阶段步骤：同时进行第一阶段前向递归与第一阶段后向递归；

第一阶段前向递归：以第0时刻的前向状态度量α₀为起点，构造前向状态度量矩阵A_k， 用前N/2个时刻的分支度量因子P、Q构造前向递归矩阵C_k(k＝0，1，2，...，(N/2)-1)。通过前向 递归计算依次得到0至N/2时刻的(N/2+1)×8个前向状态度量，并存储；

第一阶段后向递归：以第N时刻的后向状态度量β_N为起点，构造后向状态度量矩阵B_k+1， 用后N/2个时刻的分支度量因子P、Q构造后向递归矩阵D_k(k＝N-1，N-2，...，N/2)，通过后向 递归计算依次得到N至N/2时刻的(N/2+1)×8个后向状态度量，并存储；

第二阶段步骤：

第二阶段后向递归以及似然比计算：以第N/2个时刻的后向状态度量β_N/2为起点，构造后 向状态度量矩阵B_k+1，用前N/2个时刻的分支度量因子P、Q构造后向递归矩阵D_k(k＝N/2-1，N/2-2，...，0)，通过后向递归计算依次得到从N/2至0时刻的(N/2+1)×8个后向 状态度量，并依次与第一阶段存储的(N/2)-1至0时刻的前向状态度量以及前N/2个时刻的 分支度量因子P、Q进行计算，得到从(N/2)-1至0时刻的前N/2个时刻的后验似然比信息； 后向递归计算最后得到的第0时刻后向状态度量β₀用来初始化下一次迭代的后向状态度量；

第二阶段前向递归以及后验似然比信息计算：以第N/2个时刻的前向状态度量α_N/2为起 点，构造前向状态度量矩阵A_k，用后N/2个时刻的分支度量因子P、Q构造前向递归矩阵C_k(k＝N/2，N/2+1，...，N-1)，通过前向递归依次得到N/2至N时刻的(N/2+1)×8个前向状态度量， 并依次与第一阶段存储的从(N/2)+1至N时刻的后向状态度量以及后N/2个时刻的分支度 量因子进行计算，得到从N/2至N-1时刻的后N/2个时刻的后验似然比信息；前向递归计算 得到的第N时刻前向状态度量α_N用来初始化下一次迭代的前向状态度量。

第一阶段的双向并行运算是部分前向状态度量与部分后向状态度量的并行递归，第二阶 段的双向并行运算是部分前、后向状态度量的并行递归和后验似然比信息的并行计算。在第 二阶段中每一时刻后验似然比信息的计算紧接着该时刻状态度量的计算，所以后验似然比的 计算时间融合到了双向递归运算的时间里，而且由此带来了状态度量存储空间的减半。所以 分支度量的拆分和双向并行结构为DB-CTC的译码带来了译码更快速和更省存储空间的效果。

如果将本实施方式扩展到Max-Log-MAP，则分支度量拆分的运算相同，在双向并行运算 时，双向并行结构与运算步骤不变，需要变化的是在前向和后向递推运算与后验似然比信息 的运算中引入最大对数近似处理。