RS/LT级联编码在DVB广播中的应用

张菁，李惟

（长安大学 电控学院，陕西 西安 710061）

LT码[1]是实现码率无关的数字喷泉码[2-4]的一种编码方法。DVB喷泉码最先设计应用于BEC信道中删除信息的恢复。在DVB上进行广播业务时，1999年，M.Luby在喷泉码的理论基础上提出LT传输码。在应用层使用LT码，通过建立传输内容之间的XOR约束关系，在丢失一定数量传输符号的情况下，仍然可以恢复原输入符号序列。

然而，传统LT码在某些应用中也存在着不足：首先，实时流媒体广播要求对接收流数据的译码具有相对实时性（这要求能够以最小的编码冗余度恢复原始信息）。传统LT码对无法恢复的输入符号，只能等待某些后续编码符号才能恢复。这样，在进行实时流媒体广播中可能因为媒体流失同步而导致画面阻塞。其次，编码符号度分布函数的选择不当也会导致LT编码过程存在较大的译码失败概率。这说明，由于输入序列的个别符号没有被"覆盖"而导致无法完整地恢复原始信息。

解决上述2个问题都归结为：如何有效地提高短LT码的符号恢复能力（提高可译码概率或者降低编码冗余度）的问题。因此，这里构造了一种采用LT码作为内码、RS码作为外码的RS-LT级联编码方案。仿真结果表明，这种方案可以提高LT码的可译码概率和符号恢复能力，进而提高系统恢复码元的实时性，减少了传统LT码在DVB广播中因媒体流失同步而导致的画面阻塞。

1 LT码和RS码的编译码过程

1.1 LT码的编译码过程

LT码的编码过程如图1所示。设传输的符号序列长度为k，每个符号表示为Ai（1≤i≤k）。 编码过程是将2个输入符号经过XOR校验矩阵D，产生n个输出符号（编码符号）。G=（g1g2… gj…gn-1gn）代表校验矩阵，其列重称为度dj（1≤i≤k）。 编码符号Xj（1≤j≤k）与输入符号产生XOR校验关系为⊕（[A1A2…Ak]× gj）。 文献[1]绐出了2种度分布函数，选择不同的度分布函数将对LT码的可译码概率有很大的影响。

图1 LT码的编码过程示意

由于LT编码与输入符号的长度l无关，所以可以将LT码表示为：LT{k，ρ（d）}。 其中，k为编码输入符号序列的长度， ρ（d）为所采用的编码符号的度概率分布函数。一般（n≥k），n的值为每次编码动态产生。因为LT码码率无关，所以在LT定义中并不包含编码后序列长度n和信道特征参数δ。

LT码的一次编码码率为：R=k/n（n＞k）。 n的值在统计意义下与以下因素有关：1）度分布ρ（d）；2）输入符号序列长度k；3）删除信道的删除概率δ。很明显，在每次LT码的编码过程中n可能都不相同，因此称LT码为码率无关的编码方法。在删除概率为δ的删除信道中，在概率为P=1-δ的意义下，恢复k个输入符号序列所需要的编码符号序列长度nP=k+Oδ））[1]。 LT的一次编码冗余度为：r=n/k。

LT码的译码过程可以用二部图辅助表示，如图2所示。在图2中编码符号 [X1:X6]的度为：[2，2，2，3，2，1]。 其中，X4=A2⊕ A3⊕A4，其他以此类推。译码过程进行迭代。由译码过程可知，即使在δ=0的情况下，LT译码过程仍然存在一定的LT码不可译概率。

图2 简单的LT编码约束关系二部图

1.2 RS码的编译码过程[5-6]

RS频域编、译码过程如图3所示。图3中，错误图案多项式e（X）和错误定位多项式d（X）的关系是：e（X）的非零系数对应d（X）的零系数；e（X）的零系数位置对应的d（X）系数可以任意取。这样可以得到（2t-1）-t+1=t个方程，称为关键方程。

图3 RS频域编、译码过程

编码过程：将信息序列和2t个零点构成的序列看做是某个RS码字的频域变换结果，则对该序列进行逆傅里叶变换就可以得到所对应的RS码字，使用带反馈的移位寄存器很容易实现。

译码过程：首先对接收序列进行有限域傅里叶变换。变换后的频域序列的后2t位作为校正子。很明显，如果接收序列是一个码字，则校正子多项式的系数全为零，否则，应当依据校正子找到小于等于t个出错的位置来进行纠错。

RS频域译码可以利用频域错误序列的递归扩展过程来获得E（z），实现上采用递归扩展的移位寄存器，比采用Chien氏搜索算法复杂度低，译码速度快。

2 RS/LT级联编码构造方法

由删除信道和LT码的特点，LT码不可译码和传输信息丢失是等效的，表现为存在无法恢复的输入符号。传统LT码的处理方法是继续接收后续的编码符号序列以恢复这些当前无法恢复的输入符号。采用RS/LT级联编码则可以由RS编码在一定程度上恢复出这些输入符号。

级联编码构造时需要匹配LT码的符号长度和RS码符号的边界，以达到最大的效率。设LT码符号长度为l，需要首先由本原多项式构造适当的有限域GF（q），设q=2m，则GF（q）中元素（符号）可由最高阶数为m-1次的多项式表示，并取符号与其对应多项式系数为符号和二进制序列之间的对应关系。对（n，k）RS码，如果采用频域编码，设定纠t个错，有n-k=2t，一个RS码字符号帧长度为q-1。

采用RS/LT级联编码构造方法，相对文献[1]中提出的LT编码方法，可以提高给定k值的LT编码可译概率。这说明：首先，在给定ρ（d）下，降低Kρ值，等效为缩短了可译输入符号序列长度；其次，尽可能小的编码冗余度也意味能够提高LT码的可译码概率。

下面给出在删除信道下RS/LT级联编码构造方法如下：1）对输入符号序列｛Ak,l｝进行RS编码，得到编码后的符号序列｛Ck,m｝；2） 对RS编码序列｛Ck,m｝再进行LT编码，得到LT编码符号序列｛Bk,m｝。

3 仿真结果

设由于LT编码不可译或信道删除原因，有k′≤k个原始输入符号被LT译码恢复，定义恢复失败率：η＝（k-k′）/k。 从平均意义上讲，只要η小于RS码的（符号）纠错能力η≤[t/n]（[t/n]为取整运算），那么，LT码没有恢复的符号就可以由RS码恢复得到。

为了提高LT码的可译码概率，采用RS/LT级联编码与Robust-Solicon分布的LT码进行对比。仿真条件如下：删除概率δ=0，RS码k=255，n=113，选择一个符号长度为8 bit。 LT码的度分布函数选取Robust-Solicon分布。具体仿真结果如图4所示。

图4 RS/LT码与LT码的性能比较

从图4可以看到，在无删除的短输入符号序列（k=255）的情况下，RS/LT级联编码在编码冗余度为1.09时即可完全恢复输入符号，而LT码在冗余度为1.2时才可全部恢复输入符号。

在删除信道中，RS/LT级联编码可以提高LT码的抗删除能力。正如前面分析的结论：在给定条件下，提高可译码概率或者降低编码冗余度都能够改善LT码的性能。在删除概率δ=0.05的情况下，LT码和RS/LT级联编码的性能比较结果如图5所示。从图5中发现，级联码的可译码概率曲线有轻微的波动，这是由于在短输入序列情况下，LT译码后不可恢复符号的分布影响了RS码纠删结果所引起的。

图5 RS/LT码与LT码的性能比较

4 结束语

通过分析认为，数字喷泉码族在编码冗余度、可译码概率等2个外在方面上的性能是等效的，也就是说：如果能够在一定的可译码概率下降低编码冗余度，或者反之，在一定编码冗余度下提高可译码概率，都可以提高LT码的抗删除能力。

采用RS/LT级联编码可以有效地在短输入序列下提高LT码的可译码概率，在输入符号序列长度为255的条件下可降低大约12%的编码冗余度。减小了传统LT码在DVB广播中因为媒体流失同步而导致画面阻塞。这是单独采用2种编码方法都无法达到的，具有很好的应用前景。

[1]LUBY M.LT Codes-proceedings of the 43rd IEEE Symp.computer ccience（FOCS'02）[C].Los Alamitos:IEEE Computer Society Press Room，2002:271-280.

[2]SHOKROLLAH A.Raptor codes information theory[J].IEEE Trans actions，2006，52（6）:2551-2567.

[3]王新梅，肖国镇.纠错码－原理与方法[M].西安：西安电子科技大学出版社，2003:259-268.

[4]邓善征，唐红，杨军，等.无线数据传输中RS/LT级联码的应用[J].空军工程大学学报:自然科学版，2008，9（1）：62-64.

[5]杨军，茹乐，杜兴民，等.RS-LT级联码在无线图像传输中的应用[J].无线电工程:2007，37（10）47-49.

[6]MACKAY D J C.Fountain codes[J].Communication IEEE Proceeding，2005，152（6）:1062-1068.