张瑞丹 徐大专 邓大椿

（南京航空航天大学电子信息工程学院，南京，211106）

引 言

为解决大规模数据分发和可靠广播等问题，1998年Luby等首次提出数字喷泉码(Digital fountain,DF)的概念[1]，它具有无码率特性、无需反馈、不限用户以及实时性好等优良特性。此后第一种实用喷泉码LT码[2]和具有优良性能的Raptor码[3]的提出使得喷泉码逐渐受到业界的广泛关注[4-6]。

喷泉码的译码多采用BP(Belief propagation)译码算法，该算法思路简单，但复杂度较高。已有大量文献对降低BP译码算法的复杂度进行研究。文献[7-8]提出了一种最小和算法，将迭代过程中的乘法运算转化成加法，避免了非线性函数的复杂运算，降低了复杂度，但由于近似计算导致性能变差。文献[9-10]对LDPC码中的最小和算法进行了改进，改善了其收敛特性和译码性能。文献[11-13]通过对信息节点进行可靠性分析，加快了其收敛速度。Frey等还曾提出过“及早判决”的概念[14]，将迭代过程中似然比超过某个门限值的节点及时译出，不再继续更新，以减少计算量，但并未给出门限值的具体计算方法。利用“及早判决”的思想，文献[15-17]对Turbo码和LDPC码的译码算法进行了改进，给出了门限值选取的一些理论依据。

虽有以上研究对传统BP算法进行了改进，但应用于喷泉码时，复杂度依然较高。译码需接收到一定数量的码字后开始译码，迭代至预设最大次数后再对变量节点进行硬判决。若译码失败，需继续接收更多数量的码字重新迭代，使得之前迭代的信息没有得到有效利用，复杂度依然较大。利用“及早判决”的思想，为提高BP译码算法应用于喷泉码时的效率，本文分析了二进制加性高斯白噪声（Binary input additive white Gaussian noise，BIAWGN）信道下LT码的BP算法原理,根据理想误码率与信噪比及似然比之间的关系，推导出了变量节点加入可译集成功译码时似然比所需达到的门限值Tre。将迭代过程中似然比达到门限值的变量节点加入可译集提前译出，不再继续参与迭代，一方面减少了迭代过程中的计算量；另一方面，即使译码失败，开销增加时也可利用已经达到门限值成功译出的部分变量节点简化Tanner图，只对未达到译码门限的变量节点进行迭代，进一步减少计算量。仿真实验表明，该算法与传统的BP译码算法性能相同，但计算量大大减少，效率显著提高。

1 传统BP译码算法原理

无线信道中，喷泉码常用的译码算法为对数域BP算法，也称和积译码算法（Sum-product,SP）。本文讨论BIAWGN信道中LT码的BP译码算法。假设喷泉的原始信息比特序列为x=(x1,x2,…,xk),喷泉编码后生成的序列为y=(y1,y2,…,yn)，生成矩阵为G,则y=x*G。 对编码序列y进行BPSK（Binary phase shift keying）调制，得到序列y'。经BIAWGN信道传输后，接收端收到的信息序列为r=(r1,r2,…,rn)，其关系为

式中：z为信道噪声，服从N(0,σ2)分布。利用生成矩阵Tanner图中的联系，在变量节点和校验节点之间不断地相互传递似然比信息来逐渐收敛到可靠值，节点的对数似然比定义为

则变量节点和校验节点的似然比迭代公式为[18]

BP译码步骤为

(1)初始化。由于没有先验信息，变量节点是0和1的概率相同，因此变量节点的初始似然比为零，即=0。

(2)校验节点信息更新。如图1所示，根据式(4)计算校验节点的似然比信息并更新。

(3)变量节点信息更新。在校验节点已更新的基础上，根据式(4)计算变量节点的似然比信息并更新，如图2所示。

图1 校验节点似然比更新Fig.1 Likelihood ratio update of check nodes

图2 变量节点似然比更新Fig.2 Likelihood ratio update of variable nodes

(4)判决。步骤(2)和(3)重复进行迭代，达到规定次数后进行硬判决，此时变量节点似然比信息计算公式为

判决准则为

应用于喷泉码进行译码时，需接收到一定数量的数据包之后开始译码。若译码失败，需增加开销，继续接收更多数量的数据包重新开始迭代，直到完全译码成功。

2 可译门限值Tre的估计

为减少传统BP译码算法迭代过程中的计算量，并利用到低开销译码中的有用信息，定义了无线信道中可译集的概念，将似然比达到门限值Tre的变量节点加入可译集提前译出。关于门限值Tre的取值，若太小，则不能保证已加入到可译集中变量节点的正确性，可能造成错误传播；若太大，则不能保证将正确节点尽快译出以减少计算量。本文根据理想误码率与信噪比和似然比的关系，推导出了门限值Tre的合适取值，过程如下。

已知在BIAWGN信道中，BPSK调制模式下，误码率BER和信噪比SNR的关系为

根据式(3)有

因此在期望达到误码率BER时，需满足

可将条件放大至

因此似然比需满足

将式(9)代入式(13)即可得译码门限值Tre为

式中SNR可由式(8)求得。

3 基于可译集的增量译码算法

上面已推导出变量节点可正确译码时似然比所需达到的门限值Tre，将该门限值作为变量节点加入可译集的判定依据，利用可译集从两方面减少传统BP译码算法中的计算量。

（1）如图3所示，在开销固定的一次译码过程中，该算法在每次迭代结束后对变量节点的似然比进行一次判定，将似然比Lxi≥Tre的变量节点xi利用式(6)提前进行硬判决，并删除xi在Tanner图中的连接。图中，若x2，x4的似然比达到译码门限值，则加入可译集并删去与其相连的边，不再继续参与迭代，以减少计算量。

为保证缩小后的Tanner图可继续正确迭代，需对删除后的信道似然比加以修正：

(a)若变量节点xi判决为0，则无需修正；(b)若变量节点xi判决为1，需对所有与其相连的校验节点所在的信道似然比进行修正：

图3 利用可译集简化Tanner图Fig.3 Simplify Tanner graphs using translatable sets

令S表示所有已经译出的所有变量节点集合，将xi加入集合S，则提前译出部分节点后的似然比迭代公式变为

继续迭代，直至所有变量节点全部译出或达到预设最大迭代次数。若迭代次数达到lmax后变量节点未能全部译出，则根据迭代结束后的最终似然比对剩余变量节点进行硬判决，判决公式同式(6)。

（2）进行增量译码时，在固定开销下利用上面的迭代算法进行迭代及提前译出。若当前开销下未能成功译码，需增大开销接收更多数据包，先利用可译集简化Tanner图，再对未译出节点进行译码。如图4，传统BP算法在开销增大时需进行译码的Tanner图为图4(a)。而图4(b)中基于可译集的增量译码算法可利用集合S中已经成功译出的部分变量节点x2,x4简化Tanner图，只对未译出的变量节点按照步骤(1)中固定开销的情况进行迭代及提前译出，进一步减少计算量。

图4 增加开销y6y7y8时两种算法Tanner图比较Fig.4 Tanner map comparison when increasing overhead

4 仿真分析

利用Matlab为工具对提出的基于可译集的增量译码算法和传统BP译码算法进行了仿真比较。考虑LT码在BIAWGN信道中，BPSK调制下，取不同码长时的性能和时间效率比较。仿真次数取1 000次，最大迭代次数lmax=30，实际信道的信噪比SNR'取3dB，期望误码率取BER=10-6，本文中用接收到的校验节点数目n与变量节点数目K的商表示开销，利用式(14)计算得到的译码门限值Tre=23.57。

图5和图6分别仿真了码长为2 000和5 000时两种算法的误码率曲线。可以看出，新提出的译码算法与传统BP译码算法性能几乎相同，改进的算法并没有造成性能的下降。

5 复杂度分析

当码长趋于无穷时，若信道是二元对称信道，则BP译码迭代过程中节点的似然比服从对称高斯分布。可利用高斯近似法[19]分析追踪每次迭代结束后的高斯均值，即可知此时的节点似然比分布。定义度分布函数

图5 K=2 000时两种译码算法的性能比较Fig.5 Decoding performance comparison when K＝2 000

图6 K=5 000时两种译码算法的性能比较Fig.6 Decoding performance comparison when K＝5 000

式中：Ωd表示变量节点度为d的概率。同时边角度的输入度分布函数λ(x)和输出度分布函数ω(x)分别定义为

式中：λd表示与某条边相连的输入节点的度为d的概率，ωd表示与某条边相连的输出节点的度为d的概率，则输入节点的似然比均值迭代公式为

式中φ(x)定义为

定义PTre为码长无穷时，似然比达到门限值的变量节点所占比例，即

计算得理想状态下增量译码算法在不同开销下，对应的仍需参与迭代的变量节点所占比例为图7所示。

由图7可知，理想状态下90%以上的变量节点在译码过程中已达到门限值可提前译出，并释放存储空间。而传统BP算法仍需完全迭代所有变量节点，即完全译码成功前参与迭代的变量节点比例一直为1。因此，基于可译集的增量译码算法在理想情况下在时间和空间上均可减少90%的复杂度。

但在实际应用中，码长一般为有限值，因此图8仿真了码长为2 000时两种算法计算量的比较。设Tanner图中每条边进行一次信息相互传递的计算量为1，取最大迭代次数lmax=30，开销取0～1.4变化。因为传统BP算法参与迭代的变量节点固定为最大值不变，因此计算量随着开销的增大而线性递增。而利用可译集的增量译码算法在开销较小时并没有节点的似然比达到门限值，所以和传统BP算法的计算量相同。但随着开销的增大，达到门限可译出并删去的节点越来越多，计算量反而逐渐减少，直到开销为1时节点全部译出。虽不能达到理想情况下减少90%的复杂度，但相比传统BP算法计算量已大大减少。

图7 码长无穷时Tre-BP算法未达到门限值的比例Fig.7 Ratio of no-decoding infinite length codes with Tre-BP decoding

图8 码长K=1 000时两种算法在不同开销下计算量Fig.8 Computation complexity comparison in different overhead when K=1 000

表1给出了相同仿真条件下基于可译集的增量译码算法和传统BP译码算法的执行时间。可以看出基于可译集的增量译码算法执行效率大大提高，约为传统BP算法的5倍。

表1 不同码长下两种译码算法的运行时间比较Tab.1 Time comparison of different code lengths

6 结束语

本文针对无线信道中传统BP译码算法应用于数字喷泉码时复杂度较高、效率低下的问题，提出了一种基于可译集的增量译码算法。该算法首先提出了无线信道中可译集的概念，并给出了合适门限值Tre选取的理论依据。一方面，在开销固定时将译码过程中似然比高于门限值Tre的变量节点归入可译集，提前译出并停止参与迭代，减少了迭代过程中的计算量。另一方面，利用可译集的概念，即使在低开销译码失败时，也可利用其中已经达到门限值成功译出的部分变量节点先简化Tanner图，增加开销时只对未达到译码门限的变量节点进行迭代译码，进一步减少了计算量。此外，利用高斯近似法对改进后的译码算法进行复杂度理论分析，在码长趋于无穷的理想状态下分析得出90%以上的变量节点在译码过程中已达到门限值可提前译出，并释放存储空间，在时间和空间上均可减少90%的复杂度。最后又通过仿真实验表明，在码长有限的实际情况中，该算法与传统BP译码算法相比，拥有相同的译码性能，但大大减少了计算量，译码效率显著提高。