Turbo译码器中前向递推概率获取方法

摘要

本发明公开了一种Turbo译码器中获取前向递推概率的方法，目的是减少前向递推概率存储容量，并减少时间开销。技术方案是在获取每个时刻的前向递推概率时，将此时刻所有状态的前向递推概率都减去0状态的前向递推概率，保证所有时刻非0状态的前向递推概率都是偶数，同时也保证所有时刻所有状态的前向递推概率不会溢出，避免了传统方法中通过减去前向递推概率中的最大值来防溢出时所带来的存储面积开销和逻辑延迟。采用本发明可使得前向递推概率存储器容量减小为(G-1)×(B-1)×W，且使得获取一个时刻的前向递推概率的时间开销只有τ

说明书

技术领域：本发明涉及一种应用于turbo译码器中的前向递推概率获取 方法，属于纠错码领域。

背景技术：turbo码是一种译码性能优越的前向纠错码，自1993年由 C.Berrou，A.Glavieux和P.Thitimajshiwa三人在瑞士日内瓦举办的通信国际 年会(ICC)上提出以来，立刻备受关注。目前，Turbo码已经成功地应用 到磁介质光介质数据存储、多媒体和有线、无线、光纤、星载通信等多个领 域。

Turbo译码过程如图1所示，首先对一帧长度为N的数据正向地计算前 向递推概率，然后反向地计算后向递推概率，最后再反向地计算后验概率。 后验概率根据前向、后向递推概率来计算，且后向递推概率和后验概率的计 算顺序都是反向的，它们可以同时计算，因此Turbo译码过程必须先正向获 取前向递推概率并保存，然后供反向计算后验概率时使用。

图2是3GPP LTE通信协议采用的Turbo译码网格图和编码网格图，译 码是编码的逆过程，一个Turbo译码器必须有与之相应的Turbo编码器，译 码网格图和编码网格图必须相同。图2中箭头方向是网格图的正向，与箭头 相反的方向是网格图的反向，前向递推概率按照正向获取，后向递推概率按 照反向获取。网格图中，圆圈表示每个时刻的状态，状态的个数由通信协议 采用的Turbo编码器决定，状态的个数G等于2^D，D是与Turbo译码器相应 的编码器中寄存器单元的个数，那么每个状态可以用D位的二进制整数表 示，如3GPP LTE协议编码器中延迟单元个数是3，那么状态的个数就是8 个，即000、001、……、111，也可以表示为s₀、s₁、......、s₇，箭头表示从 k时刻到k+1时刻的状态跳转，称之为路径，每条跳转路径上的X_k/P1_kP2_k表 示的是k时刻输入为X_k，输出为P1_kP2_k，X_k，P1_k，P2_k∈{0，1}。例如，网格图 中k时刻的状态是s₂，假设输入X_k为0，那么k时刻的状态就按照X_k/P1_kP2_k等于0/10路径跳转到k+1时刻的状态s₅。图2中的虚线表示输入X_k为0， 实线表示输入X_k为1。

k+1时刻状态s的前向递推概率与k时刻规约到状态s的路径有关，如 图2中k+1时刻s₀状态的前向递推概率就与k时刻的s₀和s₄状态有关，因 为k时刻的s₀和s₄状态分别有一条路径规约到k+1时刻的s₀状态。设规约 到k+1时刻状态s在k时刻的状态分别为s₁’和s₂’，获取k+1时刻状态s的 前向递推概率A_s，k+1的简化公式为：

$A_{s,k+1}=\underset{{s_1}^{\prime },{s_2}^{\prime }\to s}{\max }((A_{{s_1}^{\prime },k}+{\gamma }_{{s_1}^{\prime }\to s,k}),(A_{{s_2}^{\prime },k}+{\gamma }_{{s_2}^{\prime }\to s,k}))+f_{\mathrm{LUT}}$公式一

公式一是对Turbo译码算法简化后的公式，称之为Max*-Log-MAP算法。 其中的A_s，k+1是k+1时刻状态s的前向递推概率，s∈{s₀、s₁、......、s_G-1}，和 分别是k时刻状态s₁’和s₂’的前向递推概率，f_LUT是为了补偿公式简化时 丢失的精度，称之为查找表LUT(Look-Up Table)函数，如图7中的曲线示 意的就是f_LUT函数。γ_s′→s，k是图2中每条路径的分支量度，它的计算公式为：

${\gamma }_{s^{\prime }\to s,k}=m\left(X_k\right)L\left(X_k\right)+L_c(m\left(X_k\right)y_k^X+m\left({P1}_k\right)y_k^{P1}+m\left({P2}_k\right)y_k^{P2})$公式二

公式二中s′∈{s′₁、s′₁}，系统信息校验信息和是从无线信道接收到的 信息，m(X_k)是图2输入比特X_k经过反相调制(0调制到1；1调制到-1)后 的信息，m(P1_k)和m(P2_k)是输出比特P1_k和P2_k经过调制后的信息，即 m(X_k)，m(P1_k)，m(P2_k)∈{1，-1}，L_c是信道置信度，先验信息L(X_k)是Turbo译码 时的反馈信息。

对一帧长度为N的数据，根据图2网格图的正向重复计算N-1次，即完 成前向递推概率的获取过程。前向递推概率存储器的宽度B有限，采用二进 制补码时，前向递推概率存储器保存的前向递推概率值的范围是： -2^B-1～2^B-1-1。从公式一看出获取前向递推概率是不断叠加的过程，不可避 免地会导致计算的前向递推概率值超出-2^B-1～2^B-1-1的范围，使前向递推概 率存储器保存的前向递推概率值发生错误，降低正确性。

图3是传统获取前向递推概率的流程图，分为下列几个步骤。

第一步：初始化时刻计数值k＝0。将k＝0时刻s₀状态的前向递推概率设置为0，将k＝0时刻s₁、s₂、......、s_G-1状态的前向递推概率都设置成-2^B-1，B是前向递推概率值的宽度，G等于2^D，D为Turbo编 码器中寄存器单元的个数。

第二步：从k时刻开始，根据公式一获取k+1时刻G个状态的前向递推 概率

第三步：找出第二步得到的k+1时刻G个前向递推概率中的最大值 Max A_k+1。实现查找最大值的硬件复杂度与G有关，因为硬件查找多个值的 最大值时采用的是2选1的查找逻辑分级查找，级数为

查找逻辑中2选1查找逻辑的级数为假设一级2选1查找逻辑的 延迟是τ_max，完成第二步总的延迟是如图4所示，假设G等于8， 那么查找8个前向递推概率中的最大值，需要3级2选1的查找逻辑，完成 第二步总的延迟是3×τ_max。

第四步：前向递推概率防溢出处理。将第二步得到的G个前向递推概率 都减去第三步找出的最大前向递推概率Max A_k+1， 得到k+1时刻G个新的前向递推概率设减法操作的延迟是τ_sub，传统方法获取一个时刻的前向递推概率的时间开 销是3×τ_max+τ_sub。

第五步：保存第四步计算得到的k+1时刻G个防溢出处理后的新的前向 递推概率到前向递推概率存储器。

第六步：k＝k+1。

第七步：判断k是否等于N-1，N为一帧数据长度如果不等于，转第二 步；如果等于，结束。

传统获取前向递推概率的过程有两个缺点：一是前向递推概率存储器必 须容量大，假设每个前向递推概率值的宽度是B，那么前向递推概率存储器 总容量为G×B×N。尤其是随着通信协议的不断发展，N值越来越大，前向 递推概率所需要的存储空间也越来越大。第二个缺点是时间开销大，主要是 第二步查找G个前向递推概率最大值需要级逻辑来实现，导致总的时间 开销是

针对传统计算方法的第一个缺点，相关学者提出滑窗算法以减少前向递 推概率存储器容量，如图5所示。滑窗算法将一帧长度为N的待译码数据分 成S个段，称之为“窗”，每个窗的长度为W，即N＝SW。滑窗算法的流程 如图6所示，分为下列步骤。

第一步：初始化窗计算值j＝1。

第二步：初始化时刻计数值k＝0；将k＝0时刻s₀状态的前向递推概率设置为0，将k＝0时刻s₁、s₂、......、s_G-1状态的前向递推概率都设置成-2^B-1，B是前向递推概率值的宽度，G等于2^D，D为Turbo编 码器中寄存器单元的个数。

第三步：从窗j的k时刻开始，根据公式一获取k+1时刻G个状态的前 向递推概率

第四步：找出中的最大值Max A_k+1。

第五步：将第三步得到的G个前向递推概率都减去第四步找出的最大前向递推概率Max A_k+1，得到k+1时刻G个新的 前向递推概率，即

第六步：保存第五步得到的G个防溢出处理后的前向递推概率到前向递 推概率存储器。

第七步：k＝k+1。

第八步：判断k是否等于W-1，如果不等于，转第三步；如果等于，跳 到第九步。

第九步：j＝j+1。

第十步：判断j是否等于S，如果不等于，转第二步；如果等于，结束。

采用滑窗算法后，前向递推概率存储总的容量减小为G×B×W，但是前 向递推概率计算的时间开销仍然是

发明内容：

针对滑窗算法获取前向递推概率的两个缺点：一是需要的前向递推概率 存储容量大，总容量仍为G×B×W，二是前向递推概率获取的时间开销大， 总的时间开销是提出一种新的前向递推概率获取方法，既减 小前向递推概率存储容量，又减少时间开销。

本发明的技术方案包括以下步骤：

第一步：初始化窗计算值j＝1。

第二步：初始化时刻计数值k＝0。将k＝0时刻s₀状态的前向递推概率设置为0，将k＝0时刻s₁、s₂、......、s_G-1状态的前向递推概率都设置成-2^B-1，B是前向递推概率值的宽度，G等于2^D，D为Turbo译 码器相应的Turbo编码器中寄存器单元的个数。

第三步：从窗j的k时刻开始，根据公式一获取k+1时刻G个状态的前 向递推概率公式一中的f_LUT因子量化成偶数Q_LUT。

对Turbo译码算法进行简化时，相关学者提出Max-Log-MAP算法，如 公式一，s∈{s₀、s₁、......、s_G-1}，将获取前向递推概率简化为 即f_LUT因子等于0，这种方法的误码 率性能仍然很高，在现代通信领域应用广泛。而传统的Max*-Log-MAP算法 对f_LUT因子进行奇偶量化，对误码率性能的提高不是很明显，但是增加了硬 件复杂度。本发明采取只对f_LUT因子进行偶数量化的方法，误码率性能介于 Max-Log-MAP算法和传统的Max*-Log-MAP算法，既保持了高的误码率性 能，又不会大幅增加硬件复杂度，对误码率性能需求高的应用场合仍然适用。

第四步：将第三步得到的G个前向递推概率(包括s₀状态的前向递推概率)都减去状态s₀的前向递推概率即得到G个新的前向递推概率这 样处理同样能达到防溢出的目的，且处理后k时刻的始终等于0， 全部是偶数。

从前向递推概率值的宽度B考虑，k+1时刻前向递推概率的范围是 -2^B-1～2^B-1-1，背景技术所述的传统的减去最大值的方法中，最大值也是G 个前向递推概率中随机的一个值，两个B位的操作数进行减法操作，需要加 入1位的符号保护位，那么减法的结果位数需要B+1位。本发明采取减去 s₀状态的前向递推概率，s₀状态的前向递推概率也是G个前向递推概率中的 一个值，只要减法过程中也加入1位保护位，那么本方法就符合Turbo译码 算法基于随机概率的本质，通过模拟仿真结果也能证明这一点。

第五步：保存第四步得到的G-1个防溢出处理后的非零状态的前向递推 概率到前向递推概率存储器，即保存k+1时刻的 非最低位，它们的最低位都是0，不必保存，只需保存B-1位，而等于0，不用保存。在后续计算后验概率的过程中需要用到k+1时刻G个前 向递推概率时，将未保存的0值补充完整，补0的过程不会增加硬件开销和 计算延迟，也可保证计算的正确性。

第六步：k＝k+1。

第七步：判断k是否等于W-1，如果不等于，转第三步；如果等于，跳 到第八步。

第八步：j＝j+1。

第九步：判断j是否等于S，如果不等于，转第二步；如果等于，结束。

采用本发明可以达到以下技术效果：

1、采用本发明后使得所有时刻s₀状态的前向递推概率都等于0，且s₁、 s₂、......、s_G-1状态的前向递推概率都是偶数，前向递推概率存储器容量减小 为(G-1)×(B-1)×W。

2、比传统计算方法中省略了查找G个前向递推概率最大值的逻辑，既 节省了查找电路的面积，又节约了计算的时间。假设一级2选1查找逻辑的 延迟是τ_max，减法操作的延迟是τ_sub，那么，采用本发明计算一个时刻的前向 递推概率的时间开销只有τ_sub，比传统方法节省了极大地提高了译 码速率。

3、由于Turbo译码的过程中前向递推概率的获取和后向递推概率一样， 本发明也可用于后向递推概率的获取。

附图说明

图1为传统的Turbo译码过程；

图2为3GPP LTE协议的Turbo译码(或编码)网格图；

图3为传统获取前向递推概率的流程图；

图4为传统前向递推概率计算逻辑结构；

图5为滑窗算法的Turbo译码过程示意图；

图6为采用滑窗算法获取前向递推概率的流程图；

图7为本发明采用的查找表LUT构建图；

图8为本发明总体流程图；

图9为采用本发明进行译码时的译码错误帧数模拟结果；

图10为采用本发明进行译码时的译码误码率模拟结果。

具体实施方式

如图8所示，本发明总体流程如下：

第一步：初始化窗计算值j＝1。

第二步：初始化时刻计数值k＝0。将k＝0时刻s₀状态的前向递推概率设置为0，将k＝0时刻s₁、s₂、......、s_G-1状态的前向递推概率都设置成-2^B-1，B是前向递推概率值的宽度，G等于2^D，D为Turbo编 码器中寄存器单元的个数。

第三步：从窗j的k时刻开始，根据公式一获取k+1时刻G个状态的前 向递推概率公式一中的f_LUT因子量化成偶数Q_LUT。

图7中的曲线是f_LUT的函数曲线，函数幅值为0.7-0。根据公式一可知： 横座标|x-y|表示纵座标表示 的函数值。通常定点硬件实现时 选取2^-q来量化f_LUT，其中q是量化的小数位数。q越大，精度越高。图7中 带圆圈的折线表示Q_LUT，量化方式是q＝3，即采用[.FFF]的格式，选取的量 化点为2^-1、2^-2、2^-3。本发明选择其中的两个点2^-1和2^-2，即选择0.25和0.5 这两个点，从图7可以看出：当|x-y|小于或等于0.125时，函数f_LUT被量化 成0.25加0.5，等于0.75；当|x-y|大于0.75且小于等于2时，函数f_LUT被量 化成0.25。Q_LUT利用下列分段函数表示：

|x-y|＜＝0.125         →Q_LUT＝2^-2+2^-1＝0.75；

0.125＜|x-y|＜＝0.75   →Q_LUT＝2^-1＝0.5；

0.75＜|x-y|＜＝2       →Q_LUT＝2^-1＝0.25；

2＜|x-y|               →Q_LUT＝0；

采用q＝3位小数位，在定点硬件中采用3位二进制表示 Q_LUT＝{.110，.100，.010，.000}。那么，任意两个值Q_LUT1和Q_LUT2的查找表输 出之差Q_LUT1-Q_LUT2也为偶数。对Turbo译码算法进行简化时，相关学者提出 Max-Log-MAP算法，将前向递推概率的计算简化为 s∈{s₀、s₁、......、s_G-1}，即f_LUT因子等于 0。而传统的Max*-Log-MAP算法对f_LUT因子进行奇偶量化，对误码率性能 的提高不是很明显。本发明只对f_LUT因子进行偶数量化，因此，本发明的误 码率性能介于Max-Log-MAP算法和传统的Max*-Log-MAP算法，对误码率 性能需求高的应用场合仍然适用。

第四步：将第三步得到的G个前向递推概率(包括s₀状态的前向递推概率)都减去状态s₀的前向递推概率即得到G个新的前向递推概率本 发明不采用传统的查找最大前向递推概率的方法，使得本发明比传统方法节 省了的时间开销，极大地提高了译码速率。

由公式一得到防溢出具体计算过程如下式：

$\mathrm{new}\_A_{s,k+1}=A_{s,k+1}-A_{0,k+1}$

$=(\max ((A_{{s_1}^{\prime },k}+{\gamma }_{{s_1}^{\prime }\to s,k}),(A_{{s_2}^{\prime },k}+{\gamma }_{{s_2}^{\prime }\to s,k}))+Q_{\mathrm{LUT}1})$

$-(\max ((A_{{s_1}^{\prime \prime },k}+{\gamma }_{{s_1}^{\prime \prime }\to 0,k}),(A_{{s_2}^{\prime \prime },k}+{\gamma }_{{s_2}^{\prime \prime }\to 0,k}))+Q_{\mathrm{LUT}2})$

$=[\max ((A_{{s_1}^{\prime },k}+{\gamma }_{{s_1}^{\prime }\to s,k}),(A_{{s_2}^{\prime },k}+{\gamma }_{{s_2}^{\prime }\to s,k}))$公式三

$-\max ((A_{{s_1}^{\prime \prime },k}+{\gamma }_{{s_1}^{\prime \prime }\to 0,k}),(A_{{s_2}^{\prime \prime },k}+{\gamma }_{{s_2}^{\prime \prime }\to 0,k}))]$

$+(Q_{\mathrm{LUT}1}-Q_{\mathrm{LUT}2})$

上式中首先 是两个找最大值的操作，因此，由公式一可知max()的最终结果仍然还是 或是只是选择的状态跳转路径不同。例如公式三中 的最大值max()函数的结果不是 就是即要么选择的是从状态s₁’跳转到状态s的路径，要么选择 的是从状态s₂’跳转到状态s的路径。

在第二步中，将0时刻s₀状态的前向递推概率设置为0，而0时刻 s₁、s₂、......、s_G-1状态的前向递推概率都设置成-2^B-1， 这些值都是偶数。k＝1时刻的前向递推概率由k＝0时刻的初始值(即0或 -2^B-1)和分支量度决定。以后每个时刻的前向递推概率都由前一时刻的前向 递推概率和分支量度决定，即前向递推概率实际上是初始状态和各个时刻分 支量度的叠加。将公式二代入到公式三中的

部分得 到：

$[\max ((A_{{s_1}^{\prime },k}+{\gamma }_{{s_1}^{\prime }\to s,k}),(A_{{s_2}^{\prime },k}+{\gamma }_{{s_2}^{\prime }\to s,k}))-\max ((A_{{s_1}^{\prime \prime },k}+{\gamma }_{{s_1}^{\prime \prime }\to 0,k}),(A_{{s_2}^{\prime \prime },k}+{\gamma }_{{s_2}^{\prime \prime }\to 0,k}))]$

$=(X_k^{1}L\left(X_k\right)+\mathrm{Lc}(X_k^1{y}_k^X+A_k^1{y}_k^A+B_k^1{y}_k^B))$

$-(X_k^{2}L\left(X_k\right)+\mathrm{Lc}(X_k^2{y}_k^X+A_k^2{y}_k^A+B_k^2{y}_k^B))$

$={\gamma }_k^{b1}-{\gamma }_k^{b2}$

对于根据公式二都有：例如图2 表示的3GPP LTE协议规定的网格图中，从k时刻跳转到k+1时刻的分支路 径1/11与分支路径1/00的分支量度之差为： 计算得到：任意选取两条分支路径的分支量度之差都等于2乘以一个数，即 前向递推概率计算公式中的

部分在 任意时刻任何状态都是偶数。

第三步中设计的Q_LUT1-Q_LUT2为偶数，综上所述可以得出这样的结论： new_A_s，k+1＝A_s，k+1-A_0,k+1都是偶数。即：

new_A_s，k+1[0]＝0且A_0，k+1＝0。

上式说明每个时刻0状态的前向递推概率都是0，其他状态的前向递推 概率都是偶数。那么，0状态的前向递推概率和其他状态前向递推概率的最 低位都不用保存到前向递推概率存储器中。即传统的前向递推概率存储器由 深度为N(采用滑窗后，深度为W)，宽度为B的G个存储体构成，而采 用本发明后，前向递推概率存储器只需要深度为W，宽度为B-1的G-1个存 储体，即前向递推概率存储器面积为(G-1)×(B-1)×W。

第五步：保存第四步得到的G-1个防溢出处理后的非零状态的前向递推 概率到前向递推概率存储器，即保存k+1时刻的 非最低位，它们的最低位都是0，不必保存，即只需保存B-1位，而等于0，不用保存。在后续过程中需要用到k+1时刻G个前向递推概率时， 将未保存的0值补充完整，补0的过程不会增加硬件开销和计算延迟，也可 保证计算的正确性。

第六步：k＝k+1。

第七步：判断k是否等于W-1，如果不等于，转第三步；如果等于，跳 到第八步。

第八步：j＝j+1。

第九步：判断j是否等于S，如果不等于，转第二步；如果等于，结束。

图9和图10是在Turbo译码中对比采用本发明和采用传统方法后译码性 能的模拟结果。图9的纵座标是在高斯白噪声信道中不同信噪比下错误的帧 数，图10的纵座标是在不同信噪比下的误码率，图9图10的横座标都是信 噪比。模拟环境是3GPP LTE编码，帧长256，帧数10000，迭代5次。从 图9和图10看出，采用本发明后译码性能曲线和传统方法的基本重叠，这 说明本发明在减小前向递推概率存储容量，提高译码速率的同时可以保证译 码的正确性。