基于扩展窗的级联型UEP—LT码设计

师春灵　董金明　杨争艳

摘 要： 在多媒体数据传输中，重要数据对可靠性要求比较高，在较差信道条件下需要更强的保护，为此提出了一种具有不等保护能力的级联型UEP-LT码方案。该方案先对重要比特（More Important Bits，MIB）数据进行预编码，并引入扩展窗技术进行优化设计，然后利用And-Or树分析法对误码率性能进行分析。仿真结果表明，基于扩展窗的级联型UEP-LT码增强了对MIB数据的保护程度，并且降低了对次重要比特（Less Important Bits，LIB）性能的损失，具有良好的UEP特性。

关键词： UEP-LT码； 不等差错保护； 扩展窗； 与或树

中图分类号：TP391 文献标志码：A 文章编号：1006-8228（2013）08-52-04

0 引言

Fountain码是一类基于Tanner图的前向纠错（Forward Error Correcting，FEC）编码技术，主要包括LT码[1]、Raptor码[2]，采用随机编码思想，码率灵活可变，并且可以纠正、删除错误，它最主要的特点是通过给定一组码字，可以生成无尽的序列，因此，又叫无码率码。无码率码与传统分组码不同，其码长n不是预先确定的，信道的丢失率也未知，编码符号的个数随需要而确定，即：无论信道的丢失率有多大，编码器可以一直生成编码符号并通过删除信道发送出去，直到接收端接收到足够多的编码符号可以恢复原始信息序列为止。但传统的Fountain码实现方案中，各原始数据都以相同概率被随机选取，即对数据都只能提供等差错保护（Equal Error Protection，EEP）。然而，在很多实际场合中，某些信息位的重要性比其余的要高得多，或者要求在译码时比其他数据优先恢复出来，因此，就提出了一个要求：对不同的信息位，按照其重要程度，分别给予不同的抗干扰保护。不等差错保护Fountain码（Unequal Error Protection Fountain，UEPF）就是一种可以满足这样应用需求的一种新型Fountain码。我们通过给不同优先级的数据以不同的编码冗余度，来实现对不同优先级数据的保护，使得在编码速率相同的情况下，相对于EEP来说，较重要的数据得到了更高程度的保护，从而能够在恶劣的条件下提高数据传输的鲁棒性。

本文采用扩展窗技术来设计级联型UEP-LT码，实现较小程度的损失低优先级数据的性能，来增强对高优先级数据的保护，从而提高数据的整体UEP特性。

1 级联型UEP-LT码编译码原理

1.1 级联型UEP-LT码编码原理

LT码[1]编译码性能的好坏取决于度数分布函数设计得是否合理，级联型UEP-LT度数分布仍采用鲁棒孤波分布，对MIB数据进行编码时加入预编码，本文选用规则LDPC码作为预编码，编码完成后的数据再通过UEP-LT码编码，这样在较小程度损失LIB数据性能的情况下，增强对MIB数据的保护程度，同时可以消除LT码的错误平层问题。

假设k个原始信息符号S1，S2，…，Sk，可以产生无限多个编码符号T1，T2，…，Tk，…，T∞，本文仅考虑两种优先级的数据：MIB数据和LIB数据，k1为MIB数据的个数，α1=k1/k为MIB数据占原始数据的比例，则LIB数据所占比例为1-α1，个数为k2=（1-α1）k。p1，p2，…，pk为所有原始信息符号的度分布函数中每个度数的概率，q1，q2，…，为MIB数据的度分布函数中每个度数的概率，一般情况下，α1远大于p1，而且每个编码符号的产生都遵从以下法则：

⑴ 先对MIB数据进行预编码，得到m个中间符号，再将得到的m个符号和k2个LIB数据符号作为LT编码时的信息符号，即m+k2个信息符号；

⑵ 根据设计的度数分布函数Ω，随机地选取一个编码符号的度d；

⑶ 从m+k2个信息符号中，随机等概率地选取d个不同的信息符号；

⑷ 对所选取的d个信息符号进行异或运算，得到一个编码符号；

⑸ 不断重复上述过程，直到编码完成。图1给出了级联型UEP-LT码的编码过程。

1.2 级联型UEP-LT码译码原理

级联型UEP-LT码的译码过程分为两部分：LT码译码过程和LDPC码译码过程。在删除信道下，LT码和LDPC码都采用BP（Belief Propagation，BP）迭代译码算法进行译码，对于度分布函数设计合理的LT码，这种译码算法将较大程度地降低译码的复杂度，具体译码过程如下：

⑴ 译码端接收到一定数量的编码符号集合，根据编码符号集合的符号建立与信息符号对应关系的Tanner图；

⑵ 译码端寻找编码符号中度为1的符号Tj，即编码符号只与惟一的信息符号邻接，如果存在，则将和编码符号Tj邻接的信息符号Si的值还原为编码符号Tj的值，即Si=Tj；如果不存在，则译码停止；

⑶ 寻找⑴中与已恢复信息符号Si相邻的编码符号集合，将Si与集合中所有的编码符号进行异或运算，生成新的编码符号，并删除Tanner图中对应的边，从而使得这些编码符号的度数减少1，如果在此过程中某一个编码符号的度数变为1，则称该编码符号被释放；

⑷ 重复步骤⑵和⑶，如果信息符号都已恢复，则译码成功，输出译码值；否则未被恢复的符号通过预编码译码恢复出来。

2 基于扩展窗的级联型UEP-LT设计

2.1 扩展窗方法介绍

扩展窗方法[7-8]的核心思想就是将信息符号按优先级分成不同的窗，在同一窗中以相同的概率随机选取符号进行编码，在不同的窗中以不同的概率选取符号进行编码，则信息符号中较重要的符号或要求优先译码的符号就会被赋予更高的优先级，从而实现了对数据的不等差错保护。如图2所示，将m+k2个信息符号按优先级分为t个集合s1，s2，…，st，m为对MIB数据进行预编码得到的中间编码符号，用|sl|=（l=1，2，…，t）表示每种优先级符号的个数，用窗wi（i=1，2，…，t）覆盖所有的信息符号，窗wi包含s1，s2，…，si中的所有符号，那么，并且，第一个窗仅包含MIB数据，第二个窗包含MIB数据和LIB数据，其中与第一个窗重叠部分表示MIB数据，依次可以类推其他窗的含义，从而实现了MIB数据的被选取概率大于LIB数据的被选取概率。

编码过程如下：

⑴ 对MIB数据进行LDPC码预编码，得到m个符号，再将得到的m个符号和LIB数据符号作为LT编码时的信息符号，即m+k2个信息符号；

⑵ 根据设计的鲁棒孤波分布确定度值d；

⑶ 以概率选取第i个窗；

⑷ 从选中的窗中随机等概率选取d个信息符号；

⑸ 对所选取的d个信息符号进行异或运算得到一个编码符号；

⑹ 重复⑴-⑸，直到编码完成为止。

2.2 基于扩展窗的级联型UEP-LT码的度分布函数

假设K个信息符号，如果UEP-LT码的接收开销ε，则译码端接收到K（1+ε）个编码符号，将编码符号集合中的符号分为r类，并且由属于不同的窗的信息符号得到，第i类编码符号的度分布函数用Ω（i）（x）表示，则第i类编码符号个数平均为ΓjK（1+ε），平均度为，将信息符号按优先级分为t个集合{s1，s2，…，st}，每个信息符号集合的度分布函数由对应的集合表示，并且，可由信息符号度分布函数集合计算得到，并且表示大小为kj（）的第j个窗中的信息符号的度分布函数，则

2.3 与或树（And-Or Tree）分析法

用Tl表示深度为2l的树，树的根符号深度为0，它的孩子符号深度为1，当孩子符号作为根符号时形成的树，称Tl的子树，深度1的符号的孩子符号深度为2，以此类推其他符号，深度为2的或符号作为根符号形成的子树用Tl-1表示，每棵子树 Tl-1是独立的。如图3所示，定义深度为偶数（0，2，4，…，2l-2）的符号为或（Or）符号，深度为奇数（1，3，5，…，2l-1）的符号为与（And）符号。或符号以概率δi，随机选取i个孩子符号进行或运算，没有孩子符号的或符号被赋值0；与符号以概率βi，随机选取i个孩子符号进行与运算，没有孩子符号的与符号被赋值1，深度为2l每个符号为0或1。如果将树作为布尔循环，yl表示Tl的根符号估计0的概率， yl-1表示Tl-1的根符号估计0的概率，那么yl可以看作yl-1的函数：

下面给出式⑹的推导过程：

用yl表示X符号估计为0的概率，xl-1表示Y符号估计为0的概率，yl-1表示Z符号估计为0的概率，Y符号的值通过其子符号“与”运算得到，当且仅当其所有的子符号的值都为1时，Y符号的值为1。Y符号以概率βi选取i个子符号，每个子符号的值为1的概率为1-yl-1，所有子符号的值都为1的概率为（1-yl-1）i。所以，当Y符号有i个子符号，且其值都为1的概率为xl-1，i=βi（1-yl-1）i，那么

由式⑺和⑻可以得到式⑹的结论。

下面分析具有r类或符号的与或树，每一类或符号的个数足够大，用GTlj表示深度为2l的树，它的根符号为第j类或符号，用类似Tl的方法构造GTlj，第k类或符号以概率δi，k，k=1，2，…，r随机选取i个孩子符号进行运算，与符号以概率βi，随机选取i个孩子符号进行运算，每个与符号的孩子以概率qk成为k类或符号，深度为2l的第k类的每个符号为0或1，y0，k表示GTlj估计0的概率，没有孩子符号的或符号被赋值0，没有孩子符号的与符号被赋值1，yl，j表示与或树GTlj根符号值估计0的概率，那么

Luby等人将随机编码的信息符号看成或（Or）符号，编码符号看成与（And）符号，编码时形成的Tanner图作为一个深度为2l的与或树，利用与或树分析法对译码过程进行分析，得到第l次译码的理论误码率。将k个信息符号分为t个集合s1，s2，…，st，每个优先级的个数为αik（i=1，2，…，t），且，编码时采用的度数分布函数为Ω（x），文献[4]给出了第j个优先级在l次迭代译码后的误码率：

pj表示Tanner图中一条边与sj中一个信息符号相邻的概率，qi表示Tanner图中一条边与si集合相邻的概率。若接收端收到的编码符号个数为n，则译码开销γ=n/k。定义，容易看到Gl，i，j越大，sj中符号相对于si中符号的误码率越低，即恢复的概率越高，由式（10）可得到式（11）

由式（11）容易看出，当且仅当pj>pi，有Gl，i，j>1，也就是说，要想降低某集合译码时的误码率，就要增大该集合中每个符号的被选取概率。也就是说在实现LT码的UEP特性时，一种有效的方法就是增大较高优先级集合中信息符号的被选取概率。

2.4 基于扩展窗的级联型UEP-LT的误码率性能分析

以两个扩展窗为例，利用And-Or树分析法对基于扩展窗的级联型UEP-LT码误码率性能进行分析，如图4所示。

由扩展窗方法得到某个编码符号时，所选取的信息符号要么全部来自w1，要么全部来自w2，对于图4当信息符号仅来自w1时，参与编码的符号不包含LIB数据，那么LIB集合中符号被选取概率pLIB=0。在选中w1的情况下，MIB集合中符号被选取概率pMIB=Γ1/α1k，MIB集合被选取概率qMIB=1，根据式⑻得到MIB集合和LIB集合的误码率为：

对于图4当信息符号全部来自w2时，MIB集合和LIB集合中符号被选取概率相等pMIB=pLIB=Γ2/k，MIB集合选取概率α1，相应的LIB集合的选取概率为1-α1，根据式⑻得到MIB集合和LIB集合的误码率：

根据与或树分析，编码符号是与符号，两种情况满足相“与”关系，最后得到扩展窗方法的MIB集合和LIB集合的误码率：

3 仿真结果

本文从误码率性能方面对基于扩展窗的UEP-LT码进行仿真，在仿真中，选取信息符号个数k=4000，MIB集合的符号个数为400，鲁棒孤波分布参数c=0.01，δ=0.05，Ω（x）=0.001993x+0.490505x2+0.163793x3+0.082042x4+0.049313x5+0.017705x8+0.013795x9+0.002955x19+0.000262x65+0.000255x66。

译码过程采用BP迭代译码算法，迭代次数l=80，窗选取概率Γ1=0.12，非均匀权重UEP-LT码，km=2，仿真结果如图5所示。

EWCUEP-LT表示基于扩展窗级联型UEP-LT码，从图5中可以看出，当译码开销γ较小时，EWCUEP-LT和非均匀权重UEP-LT对MIB数据和LIB数据的误码率差距较小，当译码开销γ大于0.9时，EWCUEP-LT对MIB数据和LIB数据的误码率明显低于非均匀权重UEP-LT。

均匀权重UEP-LT误码率仿真对比

4 结束语

为了实现在恶劣信道条件下对MIB数据和LIB数据的不等差错保护的同时，降低对LIB数据的损失，本文利用扩展窗方法设计了级联型UEP-LT码，这种在选取符号之前，先选取一个窗的方法，有效地避免了某一次编码符号只包一个优先级数据的情况，使得信息符号的选取更具有随机性，对MIB和LIB的误码率性能明显优于非均匀权重UEP-LT。

参考文献：

[1] Luby M. LT codes[C] .Proceedings of the 43rd Annual IEEE Symposium Foundations of Computer Science，2002：271-282

[2] Shokrollahi A. Raptor codes[R]. Digital Fountain，Technical Report，2003：1-37

[3] Rahnava rd N， Fekri F. Finite-length Unequal Error Protecti on Rateless Codes：Design and Analysis[C]. Procof IEEE GLOBECOM，2005：1353-1357

[4] Rahnavard N， Vellambi BN， Fekri F.Rateless codes with unequal error protection property[J].IEEE Transactions on InformationTheory，2007.53（4）：1521-1532

[5] Kozat U C， Ramprashad S A. Unequal error protection rateless codes for scalable information delivery in mobile networks[C]. Proceedings of IEEE International Conference on Computer Communications，2007：2316-2320

[6] Woo S S，Cheng M K. Prioritized LT codes[C].Proceedings of the 42nd Annual Information Sciences and Systems，2008：568-573

[7] Studholme C， Blake I. Windowed Erasure Codes[C].Proc. of the ISIT，2006：509-513

[8] 杜超，郭庆.深空通信中基于喷泉码的前向纠删方法[J].通信技术，2010.43（3）：51-53