-1-
中国科技论文在线
喷泉码的编译码算法研究
谢飞
北京邮电大学信号与信息处理系， 北京（100876）
摘 要：喷泉码的无码率特性和低编译码复杂度使得其得到了广泛的关注和应用。本文介绍
了 LT码和 Raptor的编译码算法并分析了 3GPP MBMS中的译码算法。在此基础上，我们提
出了一种简单有效的译码算法。仿真结果表明，与 GPP MBMS译码算法相比，本文提出的
译码算法所需的译码时间更少。
关键词：喷泉码；3GPP；BP译码算法；高斯消去
中图分类号：TN92
1. 引言
喷泉码的概念由M. Luby等人于 1998[1]年首次提出, 但当时并没有给出现实可行的喷泉
码设计方案。2002 年, M. Luby[2]提出了第一种现实可行的喷泉码——LT 码。目前，喷泉码
受到产业界的广泛关注, 获得了越来越多的实际应用。一种由 Digital Fountain 公司设计的系
统 Raptor 码[3]也已经被 DVB-H 标准和 3GPP 组织的 MBMS[4]标准采用, 并且正在参与其他
多项国际标准的制定。
所谓喷泉码, 是指该种编码可以由 k 个原始数据分组生成任意数量的编码分组, 而接收
方只要收到其中任意m个编码分组, 即可通过译码以高概率成功恢复全部原始数据分组。一
般情况下 , m 略大 k , 从而引入一定的译码开销 ε , 定义为 / 1m kε = − , 也即
)1( ε+= km 。可以看到, 上述编码过程就如同源源不断产生水滴（编码分组）的喷泉（编
码器), 而我们只要用杯子（译码器）接收足够数量的水滴, 即可达到饮用（成功译码）的目
的。正因如此, 该种编码被称为喷泉码。
2. 喷泉码的编译码算法
LT 码的编译码算法
最早的喷泉码是 Luby 等人提出的 LT 码[2]，假设我们要在删除信道上传输 k 个初始的输
入符号，LT 码生成每个编码符号的过程如下：
1)根据设计的度分布 ( )xΩ ，随机地选取编码符号的度d 。
2)从 k 个输入符号中，等概率地随机选取d 个不同的输入符号。
3)将这d 个输入符号模二和，生成一个编码符号。
理论上，生成的编码符号可以无限多次的通过信道传输。LT 码生成的编码符号之间是
相互独立的，这使得喷泉码是无码率的，因为喷泉码的编码包数目是不固定的，相应的，码
率也是不固定的。
接收端在收取到一定数量的编码包后，采用简单的 BP 算法译码：它先根据编码符号与
输入符号的对应关系建立双向图。然后选取一个度为 1 的编码符号，恢复与该编码符号相连
的输入符号，并将该编码符号从双向图中移除。对于已经恢复的输入符号，将其模二和到与
其相连的所有其他编码符号中，从而使得这些编码符号的度数减 1，这样就可能产生新的度
为 1 的编码符号。直到译码结束或者没有度为 1 的编码符号，迭代过程停止。
-2-
中国科技论文在线
Raptor 码的编译码算法
Raptor 码[3]的编码过程如图 1 所示，由预编码过程和 LT 码编码过程组成。预编码过程
将 k 个输入符号，通过 LDPC 等传统纠删码转换为 l个中间符号，然后将 l个中间符号作为
LT 码的输入符号来进行二次编码，从而得到 Raptor 码的编码符号。
图 1 Raptor 码编码过程
Raptor 码的译码同样分为两步：译出中间符号和译出源输入符号。
第一步，接收端接收到略大于 l个编码符号后，然后通过 LT 码的解码方法译出 l个中间
符号。
第二步，再利用传统纠删码的解码性质，将 l个中间符号译码恢复成 k 个源输入符号。
至此，译码过程结束。
3. GPP MBMS 标准中的 Raptor 码
3GPP MBMS 标准中的 Raptor 码[4]的编码方法与传统的 Raptor 码类似，但是其预编码矩
阵是由一个 LDPC 编码矩阵和一个 HALF 编码矩阵构成。3GPP MBMS 标准的译码方式已
不再采用简单的 BP 译码方式，而是通过矩阵变换和高斯消去相结合的方式进行译码。
3GPP MBMS 的译码方法
3GPP MBMS提出的译码方法本质上采用的是用高斯消去将译码矩阵A( )M L× 转换成
一个对角矩阵。但是该方法先通过一系列的矩阵变换将稀疏矩阵 A 简化，然后再对简化后
的 A’矩阵高斯消去，从而大大减少了译码的时间。3GPP MBMS 先将 A矩阵按图 2 分为几
个子矩阵，然后，利用四个译码阶段将 A矩阵转化为对角矩阵。
单位矩阵 I
i i×
全零矩阵
( )i L i u× − −
全零矩阵
( )M i i− ×
矩阵
V ( ) ( )M i L i u− × − −
矩阵
U
i u×
图 2 对矩阵 A的划分
-3-
中国科技论文在线
译码第一阶段
3GPP MBMS 的译码方法的核心和关键操作在于其译码的第一阶段。该阶段最多包含 L
个步骤，当矩阵 V 以及 V 上面的全零矩阵全部消除，A 只由矩阵 I，矩阵 I 下面的全零矩阵
和矩阵 U 组成时，译码第一阶段成功结束。如果不能将矩阵 V 消除，译码第一阶段失败。
令 r为 V 矩阵的行的度的最小值，按如下方式对矩阵 A 的进行操作：
步骤（1）选择 A 的一行，该行在 V 中的部分应该包含 r个 1。
a) 当 2r ≠ 时，任意选取一行；
b) 当 2r = 时，选取这样的一行，该行包含了与矩阵 V 相关的图 G 的最大元素；
步骤（2）将V的第一行与选中的行交换，并将剩下的 1r − 个1交换到V的最后 1r − 列；
步骤（3）将V的其余行与第一行做异或操作，使得V的其余行的第一列为0；
步骤（4）单位矩阵I加1，矩阵U加 1r − ；
步骤（5）重复步骤（1）~（4）直至V被消除。
译码第二阶段至第四阶段
3GPP MBMS 译码的第二阶段至第四阶段主要作用是将 U 矩阵进一步分解，并采用高斯
消去将其转化为对角矩阵。然后将 A 矩阵中的最后M L− 行舍弃，这样，A 矩阵就变成了
一个单位矩阵，从而译码过程成功结束。
4. BP 算法与高斯消去联合译码
通过本文第三部分的分析可知，3GPP MBMS 译码算法的本质是先简化 A 矩阵，然后采
用高斯消去的方法将 A 对角化。但是，该译码方法的第一阶段中过程比较复杂，而且，第
一阶段步骤（1）中寻找与矩阵 V 相关的图 G 的最大元素的复杂度较高，在实际的操作过程
中不易实现。因此我们提出了一种简单有效的译码方式，即采用 BP 译码算法与高斯消去的
方法联合的译码方式。该方法分为两个阶段：
第一阶段：采用与 LT 码译码相同的 BP 译码算法，对译码矩阵 A 进行译码操作，得到
译码矩阵 A’。
第二阶段：采用高斯消去的方法将译码矩阵 A’转化为对角矩阵，从而实现成功译码。
高斯消去法的具体步骤如下：
步骤（1）通过行交换使矩阵 A’的对角元素非零，若行交换未找到非零元素，则通过列
交换使矩阵对角元素非零；
步骤（2）消去矩阵第 i 行的后 i+k 列元素，即将矩阵 A 变成上三角矩阵元素；
步骤（3）判断矩阵是否满秩，如果矩阵不满秩，译码失败，反之，译码继续；
步骤（4）再自右向左的消去对应非对角元素，使之成为单位矩阵。
显然，与 3GPP MBMS 中的译码方法相比，这种译码方法采用的算法更为简单，译码
过程更加清楚，而且更容易实现。在实际的译码系统中，其相应的译码设备也更加简单。
5. 仿真结果
这里，我们给出了输入符号的长度为 1024k = ，译码端分别采用 3GPP MBMS 中的译
码算法和 BP 高斯联合译码的仿真结果。图 4 显示了在 100 次仿真中，采用不同的译码算法，
总的译码时间与译码开销ε 的关系。
-4-
中国科技论文在线
2
4
6
8
10
12
14
译码开销: ε
平
均
译
码
时
间
(
单
位
:s
)
3GPP MBMS 译码算法
BP算法与高斯消去联合译码
图 3 采用不同译码算法，平均译码时间与译码开销ε 的关系
从图 3 的仿真结果可以看出，与 3GPP MBMS 译码算法相比，采用 BP 算法与高斯消去
联合译码时，平均译码时间更少。并且与 3GPP MBMS 译码算法类似，采用 BP 算法与高斯
消去联合译码的译码时间随着译码开销的增加而减小。
接下来，我们给出了译码开销为 ε = 时，译码端分别采用 3GPP MBMS 中的译码
算法和 BP 高斯联合译码的仿真结果。
512 768 1024 1280 1536 1792 2048
0
10
20
30
40
50
60
70
80
90
输入符号长度: k
平
均
译
码
时
间
(
单
位
:s
)
3GPP MBMS 译码算法
BP算法与高斯消去联合译码
图 4 采用不同译码算法，平均译码时间与输入符号长度 k 的关系
-5-
中国科技论文在线
图 4 表示了在 100 次仿真中，采用不同的译码算法，总的译码时间与输入符号长度 k 的
关系。从图 4 的仿真结果可以看出，与 3GPP MBMS 译码算法相比，当输入符号在 512 到
2048 范围变化时，BP 与高斯消去联合译码的平均译码时间更少。
6. 结论
本文介绍了传统的喷泉的编译码方法，并进一步分析了 3GPP MBMS 采用的 Raptor 码
的译码过程及其缺点，在此基础上，我们进一步提出了一中简单有效的译码方法。仿真结果
表明，在输入符号长度为 1024 时，采用 BP 算法与高斯消去联合译码比原来 3GPP MBMS
译码算法所需时间更少。
参考文献
[3] M. Luby, M. Mitzenmacher and M. A. Shokrollahi et al．Practical Loss-Resilient Codes [J]．Proc. 29th
Symposium on Theory of Computing, 150–159, 1997
[2] M. Luby．LT Codes [J]．in Proceedings of the 43rd Annual IEEE Symposium on Foundations of Computer
Science, 271–282, 2002
[3] A. Shokrollahi．Raptor codes [J]．IEEE Trans. on Information Theory, 2006.
[4] 3GPP TS ．Technical Specification Group Services and System Aspects; Multimedia
Broadcast/Multicast Service; Protocols and Codes［S］．3GPP, Sept. 2007.
Research of Encoding and Decoding Algorithm of Fountain
Codes
Xie Fei
Xitucheng RD 10, student Apt 3-521, Haidian district, Beijing, China
Abstract
Fountain codes deserve a lot of attention because of its characteristics of rateless and low complexity
encoding and decoding algorithm. This paper introduces the encoding and decoding algorithm of LT
codes and Raptor codes, and analyses the decoding algorithm in 3GPP MBMS. Then we propose a
simplified decoding algorithm according to the analysis. Simulation results show that average decoding
time of the proposed decoding algorithm is much less than the decoding algorithm in 3GPP MBMS.
Keywords: fountain code, 3GPP, BP decoding algorithm, Gaussian elimination
