一种降低Fano算法译码器堆栈溢出概率的方法

摘要

本发明公开了一种降低Fano算法译码器堆栈溢出概率的方法，主要解决Fano算法译码器堆栈溢出概率过高的问题。本发明的具体思路，一是增加观测距离来筛选出最优节点，以降低译码器进入错误路径的概率；二是判断特定点的可靠性来修正其Fano度量，以降低译码器离开正确路径的概率。本发明的具体步骤包括：(1)译码器参数初始化；(2)筛选出最优节点；(3)对译码节点进行处理；(4)对停机条件进行判断；(5)对特定点的Fano度量进行修正；(6)对门限进行紧缩处理；(7)得到向后窥测度量；(8)对门限进行缩减处理；(9)对观测方向进行选择。本发明具有系统实现复杂度低、译码速度快、堆栈溢出概率低的优点。本发明显著地降低了Fano算法译码器的堆栈溢出概率，提高了卷积码Fano算法译码在信道较差时的译码速度和译码稳定性。

说明书

技术领域

本发明属于通信技术领域，更进一步涉及信道编码领域的一种降低Fano算法译码器堆栈溢出概率的方法，可用于降低Fano算法译码器堆栈溢出概率，提高了卷积码Fano算法译码在信道较差时的译码速度和译码稳定性。

背景技术

卷积码是1955年由Elias等人提出的，是一种非常有前途的编码方法，并且获得了广泛的应用。卷积码译码方法主要采用概率译码。概率译码又分为维特比译码和序列译码2大类。

维特比译码是一种最大似然译码算法，是一种最佳的概率译码方法。在码的约束长度较小时，它具有速度快、计算量恒定、译码器简单的优点。自提出以来，无论是理论上还是实践上，都得到了极速的发展，广泛应用于各种数传系统，尤其是卫星通信中。可是，卷积码的维特比译码的复杂性随着成指数增长，故不能适用于太大的码，从而限制了维特比译码输出的误码率不能做得太低，致使维特比译码方法在应用上受到限制。

序列译码是一种准最大似然译码算法，且译码复杂性与码的约束长度无关，从而使较大的码的应用成为可能，进而获得较低的误码率。序列译码的计算量随信道干扰大小变化，从而可使其平均计算量减小，译码速度加快。

Fano算法是由Fano于1963年提出，是序列译码中“两大算法之一”。其译码基本原理概括地说，就是不断地在码树图中移动观察点(码树图中分叉节点)，通过接收码组和码树分支的比较计算得到各个分支的Fano度量，选取码树上度量最小的路径前进，通过路径总的度量值和预置门限值大小，前后探测，进退反复地搜索，以尽早地排除错误路径，并以最大的正确概率尽早地回到正确路径上，从而使译码器的平均计算量减少。序列译码的另外一大算法是堆栈译码算法。相比堆栈译码算法，Fano算法译码要搜索更多的节点，但是，堆栈译码算法需要非常大量的储存器。另外，Fano算法的多层判断和嵌套循环非常适合硬件实现。

Fano算法的不足之处是：Fano算法的译码器需要一个输入缓冲器，以储存输入的接受序列，以备译码器搜索分离点时储存后面输入的序列，以及提供以前接收到的接收序列。但是当信道干扰很大时，译码器搜索时间很长，这时就可能引起缓存器溢出。因此，在Fano算法中，译码错误概率不是主要的问题，而缓存器溢出却是一个主要的问题。

毛淑华等人在文章“一种基于分支度量标准的新卷积码译码算法”(《云南大学学报(自然科学版)》，2010,32(SI)：376～378)中提出了一种门限可调的序列译码算法，来克服缓存器溢出的难题。该算法使用了新的分支度量，并通过发送特定的导频序列来估计噪声大小来调整门限电平。该方法存在的不足之处是，它插入了导频，降低了信息速率。

发明内容

本发明的目的在于克服上述已有技术的不足，提供一种降低Fano算法译码器堆栈溢出概率的方法，仅仅增加少量计算，以很小的性能损失，便能显著减少Fano算法译码在信道干扰较大时的搜索平均次数和最大次数，从而提高译码速度并降低堆栈溢出概率。

实现本发明目的的具体思路，一是增加观测距离来筛选出最优节点，以降低译码器进入错误路径的概率；二是判断特定点的可靠性来修正其Fano度量，以降低译码器离开正确路径的概率。

本发明实现上述目的具体步骤如下：

(1)译码器参数初始化：

设置译码器的门限值为零，设置码树的第一个节点的Fano度量为零，设置码树的第一个节点为译码节点；

(2)筛选出最优节点：

(2a)从序列缓冲器中读取当前译码节点对应的码组；

(2b)根据当前译码节点对应的码组，分别计算从当前译码节点出发的各个分支的Fano度量和从当前译码节点出发的各个分支所到达的节点的Fano度量；

(2c)根据候选点筛选方法从上述分支中筛选一个作为最优节点；

(3)对译码节点进行处理：

(3a)计算最优节点的Fano度量；

(3b)判断最优节点的Fano度量是否大于或等于门限T，若是，则将当前译码节点移动到最优节点，否则，执行步骤(7)；

(4)对停机条件进行判断：

判断当前译码节点是否为码树的终点，若是，则停机，否则，继续执行下一步骤；

(5)对特定点的Fano度量进行修正：

根据点可靠性判断方法对特定点的Fano度量进行修正，其中的特定点为点可靠性判断方法中指定的点；

(6)对门限进行紧缩处理：

(6a)判断当前译码节点是否首次被访问，若是，则进行紧缩门限处理；否则，保持当前门限不变；

(6b)执行步骤(2)；

(7)得到向后窥测度量：

将当前译码节点的前一个节点的Fano度量作为当前译码节点的向后窥测度量，若当前译码节点为初始节点，则设置当前节点的向后窥测度量为负无穷大；

(8)对门限进行缩减处理：

判断向后窥测度量是否小于门限，若是，则对门限进行缩减，然后执行步骤(2)，否则，将译码节点回退到当前译码节点向的前一个节点；

(9)对观测方向进行选择：

根据最坏分支判断方法，判断上一步的译码节点回退是否是从最坏分支回退而来，若是，则执行步骤(7)，否则，向前窥测余下节点的最优节点，然后执行步骤(3)。

本发明与现有技术相比具有以下优点：

第一，由于本发明采用增加观测距离和判断特定点的可靠性的方法，通过少量的计算，克服了原Fano算法在信道条件较差时，平均访问次数和最大访问次数过多，堆栈溢出概率过大的缺点，使得本发明具有译码速度快、堆栈溢出概率低、译码稳定性高的优点。

第二，由于本发明采用增加观测距离和判断特定点的可靠性的方法，仅增加了少量的计算，克服了现有技术插入训练序列从而降低信息速率的缺点，使得本发明具有系统实现复杂度低、信息速率高的优点。

附图说明

图1为本发明的算法流程图；

图2为本发明的候选点筛选方法的流程图；

图3为本发明的点可靠性判断方法的流程图；

图4为本发明译码一个编码信息块搜索访问状态的平均访问次数的仿真图；

图5为本发明在E_b/N₀为0dB时译码一个编码信息块搜索访问状态次数的CCDF仿真图；

图6为本发明在E_b/N₀为0.5dB时译码一个编码信息块搜索访问状态次数的CCDF仿真图；

图7为本发明接收译码误比特率仿真图。

具体实施方式

参照附图1，下面结合实施例，对本发明的实现方法做进一步描述。

步骤1，译码器参数初始化。

设置译码器的门限值为零，设置码树的第一个节点的Fano度量为零，设置码树的第一个节点为译码节点。

所述的码树为卷积码状态转移的一种表达方式，码树的节点对应卷积码的状态，卷积码不同输入产生的状态转移对应码树中的各个分支，码树的深度由编码长度决定，每个节点的分支数量由卷积码参数决定。

步骤2，筛选出最优节点。

首先，从序列缓冲器中读取当前译码节点对应的码组。

其次，根据当前译码节点对应的码组，分别计算从当前译码节点出发的各个分支的Fano度量和从当前译码节点出发的各个分支所到达的节点的Fano度量。

所述的从当前译码节点出发的各个分支的Fano度量按照下列公式进行计算：

其中，log₂表示以2为底的对数，R_i表示接收的第i个码组矢量，c_i表示发送的第i个码组矢量，P(R_i|c_i)表示在c_i的条件下R_i发生的概率，R_c表示R_i发生的概率，n₀表示卷积码码段长度，R_c表示码率，M_F(R_i|c_i)表示第i个分支的Fano度量。

所述的从当前译码节点出发的各个分支所到达的节点的Fano度量按照下列公式计算：

M_i+1＝M_i+M_F(R_i|c_i)

其中，M_i为第i个译码节点的Fano度量，M_i+1为从第i+1个译码节点的Fano度量，M_F(R_i|c_i)为第i个译码节点与第i+1个译码节点之间对应分支的Fano度量。

最后，根据候选点筛选方法从上述分支中筛选一个作为最优节点。

下面结合附图2对本发明中候选点筛选方法的具体步骤进行描述。

第一步，从当前译码节点出发的所有分支中，选择Fano度量最大的分支作为最佳分支；

第二步，判断最佳分支的个数是否大于1，若是，则得到多个最佳分支，否则，将此分支定为最优分支，将最优节点设置为由当前译码节点沿最优分支方向前进到达的下一个节点，执行第十步；

第三步，任取一个最佳分支，将由该最佳分支所到达的节点设置为临时节点；

第四步，计算由临时节点出发的各个分支的Fano度量，选择其中Fano度量最大的分支为二次最佳分支；

第五步，判断二次最佳分支的个数是否等于1，若是，则将此二次最佳分支所到达的节点设置为二次预选节点，否则，任选一个二次最佳分支，将此二次最佳分支所到达的节点设置为二次预选节点；

第六步，判断是否取完所有最佳分支，若是，则得到多个二次预选节点，否则，执行第三步；

第七步，计算多个二次预选节点的Fano度量；

第八步，从所有二次预选节点中选择Fano度量最大的节点；

第九步，判断上一步选择的Fano度量最大的节点的个数是否大于1，若是，则将最优节点设置其中任意一个节点的前一个节点，否则，将最优节点设置为该节点的前一个节点。

第十步，结束所有步骤，得到最优节点。

步骤3，对译码节点进行处理。

首先，计算最优节点的Fano度量。

然后，判断最优节点的Fano度量是否大于或等于门限T，若是，则将当前译码节点移动到最优节点，否则，执行步骤7。

步骤4，对停机条件进行判断。

判断当前译码节点是否为码树的终点，若是，则停机，否则，继续执行下一步骤。

步骤5，对特定点的Fano度量进行修正。

根据点可靠性判断方法对特定点的Fano度量进行修正，其中的特定点为点可靠性判断方法中指定的点。

下面结合附图3对本发明中点可靠性判断方法的具体步骤进行描述。

第一步，设置回溯点数为某一固定值，设置可靠性门限值为某一固定值；

第二步，判断当前译码节点的在码树中的阶数是否小于或等于回溯点数，若是，则结束所有步骤，否则，继续执行下一步；

第三步，计算当前译码节点的Fano度量减去回溯终点的Fano度量得到的差值，其中回溯终点表示由当前译码节点后退回溯点数个节点后所到达的节点；

第四步，判断上一步得到的差值是否小于可靠性门限值，若是，则结束所有步骤，否则，继续执行下一步骤；

第五步，判断译码器是否首次到达当前节点，若是，则重置回溯终点的前一个节点的Fano度量为负无穷大，否则，结束全部步骤。

步骤6，对门限进行紧缩处理。

首先，判断当前译码节点是否首次被访问，若是，则进行紧缩门限处理；否则，保持当前门限不变。

所述的紧缩门限处理的具体步骤为：循环执行T←T+Δ，直到当前译码节点的Fano度量M满足T≤M＜T+Δ，其中，T表示门限值，Δ表示门限增量，M表示当前节点的Fano度量，门限增量通常取整数，范围为2～8。

其次，执行步骤2。

步骤7，得到向后窥测度量。

将当前译码节点的前一个节点的Fano度量作为当前译码节点的向后窥测度量，若当前译码节点为初始节点，则设置当前节点的向后窥测度量为负无穷大。

步骤8，对门限进行缩减处理。

判断向后窥测度量是否小于门限，若是，则对门限进行缩减，然后执行步骤2，否则，将译码节点回退到当前译码节点向的前一个节点。

所述的对门限进行缩减的具体步骤为：令T←T-Δ，其中，T表示门限值，Δ表示门限增量，门限增量通常取整数，范围为2～8。。

步骤9，对观测方向进行选择。

根据最坏分支判断方法，判断上一步的译码节点回退是否是从最坏分支回退而来，若是，则执行步骤7，否则，向前窥测余下节点的最优节点，然后执行步骤3。

所述的最坏分支判断方法的具体步骤为：判断当前分支是否是当前译码节点所有分支中最后一个被选中而前进的分支，若是，则当前分支为最坏分支，否则，当前分支不是最坏分支。

下面通过本发明的仿真实验对本发明的效果做进一步说明。

1.仿真条件：

本发明的仿真软件使用Matlab 8.5.0，仿真信道为高斯信道，调制方式为BPSK调制，卷积码为(2,1,7)卷积码，其生成多项式如下：

G(D)＝[1+D²+D³+D⁵+D⁶,1+D¹+D²+D³+D⁶]

发送端编码信息块的长度设置为128bit，接收端译码采用硬判决译码，门限增量设置为3，回溯点数设置为9，可靠性门限值设为回溯经过的各分支均无比特错误时这些分支Fano度量的总和。

2.仿真内容：

本发明的仿真实验是使用本发明方法和原Fano算法，分别对卷积码进行译码，进行多个方面对比。

2.1、平均访问次数对比：

仿真结果：

附图4为仿真得到的平均访问次数曲线，其中，横轴表示信噪比E_b/N₀，单位为dB。纵轴为译码一个编码信息块，搜索访问状态的平均访问次数。附图4中以三角标志的曲线表示使用本发明提出的方法译码一个编码信息块，搜索访问状态的平均访问次数；以圆圈标志的曲线表示原Fano算法译码一个编码信息块，搜索访问状态的平均访问次数。

仿真结果分析：

由附图4的仿真结果可见，本发明在信噪比E_b/N₀接近于0dB时，本发明平均访问次数小于2500，而原Fano算法的平均访问次数大于4000。而在信道条件较好时，两者基本持平。这表明，在信道条件较差时，本发明相比原Fano算法，可以显著降低平均访问次数，提高译码速度。

2.2、搜索访问状态次数的CCDF对比：

仿真结果：

附图5、附图6为仿真得到的译码一个编码信息块的搜索访问状态次数的CCDF(互补累计分布函数，Complementary Cumulative Distribution Function)曲线，横坐标为访问次数，纵坐标为概率，曲线上一点的含义为译码一个编码信息块搜索访问次数大于横坐标值的概率为纵坐标的取值。图中以三角标志的曲线表示使用本发明提出的方法的CCDF曲线；以圆圈标志的曲线表示原Fano算法的CCDF曲线。附图5为信噪比E_b/N₀为0dB条件下得到，附图6为信噪比E_b/N₀为0.5dB的条件下得到。

仿真结果分析：

由附图5可知，在信噪比E_b/N₀为0dB时，原Fano算法的访问次数超过10⁵的概率约为1/250，而本发明其概率小于1/5000。由附图6可知，在信噪比E_b/N₀为0.5dB时，在1/1000的概率时，本发明的访问次数在10⁴量级，而原Fano算法在10⁵量级，减小了约一个数量级。由于CCDF和译码的堆栈溢出概率直接相关，从附图5、附图6可以看出，本发明可以很大程度上降低Fano译码时堆栈溢出的概率。

2.3、译码误比特率对比：

仿真结果：

附图7为仿真得到的译码误比特率曲线，横坐标为信噪比E_b/N₀，单位为dB，纵坐标为误比特率。附图7中以三角标志的曲线表示使用本发明提出方法的译码误比特率曲线；以圆圈标志的曲线表示原Fano算法的译码误比特率曲线；虚线表示未编码BPSK的理论误比特率曲线。

由附图7的仿真结果可见，相比原Fano算法，在相同误比特率下，在信噪比较低时，本发明损失了约0.3dB；而在信噪比较高时，二者误比特率曲线重合。可知，在很小的误比特率损失下，本发明显著地提高了译码速度，很大程度地降低堆栈溢出的概率。译码速度提高，使更长约束的卷积码的应用成为可能，从而能获得更好的性能。

以上详细描述了本发明的较佳具体实施例。应当理解，本领域的普通技术人员无需创造性劳动就可以根据本发明的构思做出诸多修改和变化。因此，凡本技术领域中技术人员依本发明的构思在现有技术的基础上通过逻辑分析、推理或者有限的实验可以得到的技术方案，皆应在由权利要求书所确定的保护范围内。