2010 年第 08 期，第 43 卷 通 信 技 术 Vol.43，No.08,2010 总第 224 期 Communications Technology No.224,Totally Raptor 码译码算法的改进方案 余国华①， 杨宇航①， 魏岳军② （①上海交通大学 电子工程系，上海 200240; ②华为技术有限公司，广东 深圳 518129） 【摘 要】喷泉码是一类重要的纠删码，特别是 Raptor 码，由于其非固定码率、逼近信道容量、可以有效纠删等方面的 内在特点，非常适合作为应用层 FEC 而使用到各类系统中。主要就 Raptor 码的译码算法展开深入的讨论，在介绍现有译码算 法的基础上，提出了 Raptor 码译码算法的优化思路，它能更好的平衡译码失败率和译码计算复杂度两个指标之间的关系，以 更好的适用于某些特定应用场景的需要。 【关键词】喷泉码；二进制删除信道；Raptor 码；LT 码；前向纠错；译码 【中图分类号】TN911.22 【文献标识码】A 【文章编号】1002-0802(2010)08-0087-02 An Improved Algorithm for Decoding of Raptor Codes YU Guo-hua①， YANG Yu-hang①， WEI YUE-jun② (①Dept. of Electronic Engineering, Shanghai Jiaotong University, Shanghai 200240, China; ②Huawei Technologies, Shenzhen Guangdong 518129, China) 【Abstract】Fountain code is an important erasure code, and Raptor code in particular, for its unfixed code rate, approximating to the channel capacity and effective erasure, is very suitable to being an application-layer FEC. This paper first gives in-depth discussion of the existing decoding algorithm for Raptor code, then proposes and efficient algorithm and could fairly balance the relation between decoding failure and computational complexity. Thus, the proposed algorithm for decoding Raptor code could be applied to certain specific application scenarios. 【Key words】fountain codes；binary erasure channel（BEC）；Raptor code；LT codes；forward error correction （FEC）；decode 0 引言 26.346（MBMS）标准[4]内采用的 Raptor 码为例子，来分析 Raptor 编码是由预编码（一般为 LDPC 码[1]）和 LT 编 Raptor 码的译码算法。 码[2]两个环节组成。为了设计出性能优异的 Raptor 码，预编 （1）算法A 码环节可以显著的提高 LT 码的性能[3]，在 MBMS 标准里，预 一切可以求解线性方程组的算法，都可作为Raptor码的 编码是 LDPC 码与 Half 码的组合[4]。LT 编码是 M. Luby 在 2002 译码算法。在3GPP26.346标准里，建议了一种译码算法，它 年发明，是一类最早实现的喷泉码。Raptor 码可以看作一个 可以有效的减少传统高斯消元法的运算复杂度，大大降低译 改进的 LT 码。它继承了 LT 编码的主要优点的同时，具有更 码所需的时间。在文献[5]中提出了一种针对3GPP建议算法的 好的纠错性能。故而，在 MBMS,DVB-H 等国际标准里面被采 改进算法。仿真表明，可以进一步降低译码所需的时间。下 纳的都是 Raptor 码。 1 Raptor 码的解码 Raptor 码是一个增加了预编码的 LT 编码。下面以 3GPP 收稿日期：2009-10-26。 作者简介：余国华（1983-），男，硕士，主要研究方向为无线物理层技 术，无线网络编码；杨宇航（1962-），男，教授，博士生导 师，主要研究方向为无线物理层技术，无线宽带技术，无线 传感器网络；魏岳军（1977-），男，工程师，硕士，主要研 究方向为无线信道编译码技术。 面先介绍此译码算法，此算法分为如下三个阶段： 第一阶段：首先把矩阵A分割为如下所示的分块矩阵。 子矩阵I 全0矩阵 矩阵U 全0矩阵 矩阵V 参数i，u决定每个子矩阵的大小，i，u初始化为0。子矩 阵I：I为一个 i i× 矩阵，它由前i行与前i列交叉的元素组成， 在每一步变换操作的最后，I为单位矩阵。V上部的全0矩阵： 由前i行与除了前i列、后u列的所有列交叉的元素组成，它为 87 

i 在第一阶段的起始时刻， 全0矩阵。子矩阵U：由最后的u列元素组成的矩阵。V左侧的 全0矩阵：前i列与除了前i行的所有行交叉的元素组成，它为 全0矩阵。子矩阵V：除了前i行的所有行与除了前i列、后u 列的所有列交叉的元素组成的矩阵。 0 u= = ，即 V=A。在开始介 绍第一阶段的译码之前，先介绍几个术语和符号。约定 A 内 某一行在 V 中含有 1 的个数记为 R，令 r 为所有 R 值中的最 小值。定义第 i 行的 score 值为：当第 i 行被处理后，V 矩阵 中被消去的 1 的个数。矩阵 也可以表征为一个 + + 个右节点的二部图矩阵，第 j 个 k ija = ， 左节点与第 i 个右节点相连（又称相邻）当且仅当 故而，第 i 行的 score 值即为第 i 个右节点的所有相邻节点的 度的和。 第一阶段的译码过程如下： + + 个左节点、n s h a ( s h )ij A 1 r ≠ ， 在 所有 R r= 的 行 内 任 选其 一 ； 如 果 r = ，在所有 2R = 且 score 值最大的行中任选其一； ① 如 果 2 2 ②在 A 的某一行被选出之后，把 V 中的第一行所在的行 与被选出的行进行交换，使得被选出的行成为 V 中的第一 行。接着做列交换，使得 V 中的第一行的首元素为 1，剩余 的 1r − 个 1 处于 V 的最后 1r − 列； ③把 V 中的第一行异或到所有 V 中首元素为 1 的其它行 上，此时 V 中首列元素除首行的一个为 1 外都为 0； l ( r k u u s h : = + 1) − ； i= + 1, i ④ : ⑤跳到①。在第一阶段最多会有 l = + + 步，当且仅 + = 时，V 完全消失，第一阶段成功结束；否则译码 当 i u 失败。 第二阶段：经过第一阶段的变换，在此阶段的开始时刻， 二部图矩阵 A 为如下所示。 upperU downU i i× 的单位矩阵 全 0 矩阵 此阶段对 downU 矩阵做高斯消元法处理。若矩阵 downU 的 秩等于 u ，则通过变换使得 downU 前 u 行变为单位矩阵，此 后可以忽略 A 矩阵的最后 n k− 行；若矩阵 downU 的秩小于 u ， 此时 A 为非满秩矩阵，译码失败。 第三阶段：在本阶段，一切消去 upperU 使得矩阵 A 的前 l 行变为 l l× 单位矩阵的算法都可以采纳。本文针对第一、二 阶段的算法进行改进，本阶段的详细步骤可参看文献[4]。 于整个译码过程里面，A 矩阵每个右节点的相邻结点以及每 个左节点的度都很容易获得，此时求最大 score 值最多只需 ( )nΟ 的运算量[5]。综合上述算法可知，算法 A 产生了较大的 U 矩阵，而 3GPP 建议的算法在产生最小的 U 矩阵的过程中 引入了太多的运算复杂度。 算法 A 产生的 U 矩阵大概率都是列数比较小的，但也以 较小概率产生列数较大的 U 矩阵，尽管列数较大的 U 矩阵出 现的概率比较小，但是一旦出现就会使第二阶段的译码花费很 多的时间。针对以上特点，算法 B 在算法 A 的基础上进行如 下修改：在第一阶段，当u 增大到某一个预定值 *u 时，停止 译码。由于第二阶段运算大 U 矩阵需要很多的运算量，此算法 的优势是可以避免产生较大的 U 矩阵而有效减少第二阶段的 译码复杂度。 *u 的大小可以根据具体的应用场景来有效选择。 （3）算法 C 在某些存在简单反馈信道的系统里面，只需要增加极少 的系统开销，就可以较好的提升译码性能。具体来说，在译 码失败的情况下，可以选择反馈一个译码失败信号 NACK 给 发送端，此时发送端可以再发 T symbol 的数据给接收端，接 收端可以用新收到的 T symbol 数据扩充原矩阵的行来进一 步进行求解[6]。 进一步，在某些情况下，可以把算法 B、C 结合起来使用， 具体来说，在第一阶段，当 u 大于某一个预定值 *u 时，停止 译码，接收端发送 NACK 给发送端，此时发送端可以再发 T symbol 的数据给接收端，接收端可以用新收到的 T symbol 数据扩充原矩阵的行继续译码。 2 仿真结果的比较 现对前述介绍的算法进行了仿真比较，仿真程序在同一 台电脑上运行，仿真链路除了译码算法不同之外，其余运行 环境都是相同的。仿真相关参数为 K=3 000，接收端收到的 symbol 的冗余系数为 5%，程序执行次数为 1 000 次。仿真 结果如下表 1 所示。 表 1 算法 A 与 B 的仿真数据 算法 算法 A 失败率/(%) 时间/s 1.796 1.739 1.720 1.691 1.2 2.9 3.8 5.4 算法 B( 算法 B( 算法 B( *u =100) *u =80) *u =60) （2）算法 B 现讨论的译码算法都是接收端收到的 symbol 数比较少 的情况。以 score 值作为选择某一行的标准，有一个明显的 弱点是生成的 U 矩阵不是最小的，也即参数 u 会略大于 3GPP 建议算法的值。U 矩阵越大，在第二阶段对 U 矩阵的 处理所需要的运算量就越大。尽管如此，文献[5]给出的仿真 结果表明，算法 A 译码所需时间远低于 3GPP 建议的算法。 尽管 3GPP 算法可以保证产生的 U 矩阵拥有最少的列向量 数，但为此引入了太多的译码计算复杂度。在算法 A 里，由 88 从上述算法可以看出，在算法 B 里，译码时间得到了有 效的减少，译码失败率和译码时间之间是可以相互转化的。 在实际应用场景中，可以根据需求而选择合适的 *u 值。 3GPP 算法为了得到最小的 U 矩阵的列数而引入了过多 的计算复杂度。算法 B 中约定 *u ，也就是说当 U 矩阵的列 数大于 *u 的时候，算法就会停止译码，本次译码记为失败， 故而，算法 B 具有更小的运行时间。与此同时，算法 B 相比 算法 A 会提高译码失败率。故而，在工业界的设备研发实现 （下转第 91 页） 

5 ms 长的数据帧、40 个用户进行向基站上传业务，信道采 用实际的基站系统无线环境。 系统开辟的内存大小为 N=12 160 byte，设定最大 HARQ 数据包 1 448 byte，并且设定：大小为 512～1 448 byte 范围 内的数据包为大型 HARQ 数据包；大小为 181～512 byte 范 围内的数据包为中型 HARQ 数据包；大小为 64～181 byte 范围内的数据包为小型 HARQ 数据包。设定每个用户每数据 帧只调用一个 HARQ 数据包。 系统相关参数的设置为：Direction：Uplink（MS->BS）； Bandwidth：10 MHz；Sampling Frequency：11.2 MHz；FFT Size：1 024；CyclicPrefixDuration：1/8 of FFT size；Carrier Frequency：2.5 GHz；Permutation：PUSC；Subchannel Number： 35；Symbol Number：15；BS RX Antenna：2；MS TX Antenna: 1; HARQ Mode: Chase Combining; Max RTX Number: 3; FEC Scheme: CTC。 图 3 中纵坐标表示系统的吞吐量，横坐标表示用户数目。 从图 3 可以看出，按照传统的等分比方法来分配内存时，按 照最大的 HARQ 数据包分配 buffer，即所有的数据包占用一 样大小的 buffer，当用户数达到 8 时，buffer 数就已经全被占 用，但是由于数据包的大小是按照一定的比例出现，给中包 和小包也同样分配了和大包一样大的内存，浪费了内存，导 致吞吐量最多为 4.4 Mb。当采用不等分比进行控制时，按照 HARQ 数据包的大小和出现的比例来分配内存，就可以充分 利用内存，最多可以分配 24 个 buffer，吞吐量可达到 18.4 Mb， 极大地提高了系统的吞吐量。实际系统中信道质量是实时变 化的，通过实时对 HARQ 缓存区的使用情况进行统计，使系 统能够判断出导致缓存区拥挤或空闲的原因，动态调整每类 缓存区使用，极大的提高了系统的运行效率。 3 结语 在系统运行过程中，根据信道质量进行实时控制。观察 在实际应用中，数据突发的大小和数据流量均不固定， 系统可接纳的用户连接数以及系统的吞吐量，经多次测试， 多用户，各种业务连接测试，取典型值如图 3 所示。 根据本文提供的方法，能较灵活根据数据量多少和数据突发 大小合理的分配 HARQ 缓存区，实时对 HARQ 缓存区的使 用情况进行统计，动态的调整每类缓存区的使用。通过后期 的调整来改善在前期将缓存区大小和个数固定所带来的弊 端，使得缓存区的使用能够灵活的适应系统的运行。 参考文献 [1] 陈庆春.基于码合并的混合差错控制及相关理论研究[D].成都:西南 交通大学,2000. [2] 曹红梅,张国斌,酆广增.OFDMA 技术及其在 IEEE802.16a 中的应 用[J].通信技术,2003(12): [3] 谢显中.基于 TDD 的第四代移动通信技术[M].电子工业出版社, 2007:260-272. 11-12. ) s / b M ( / 量 吐 吞 用户数/个 图3 改进前后对系统吞吐量的影响 （上接第 88 页） 中，对某些实时性要求高、运算资源有限的应用场景下，算 法 B 具有很大的优势。 [2] LUBY M.LT Codes[J].In Proc. 43rd Annual IEEE Symposium on Foundation of Computer Science,2002,2(07):12-16. 3 结语 [3] SHOKROLLAHI A.Raptor Codes[J].IEEE Trans. Information Theory,2006,52(06):8-25. 在详细分析了算法 A 的基础上，提出了算法 B。算法 B 在增大少许译码失败率的条件下，可以有效的提高第一阶段 [4] 3GPP.3GPP TS 26.346-2008.Technical Specification Group Services and System Aspects[S].3GPP TS 26.346 v7.7.0（2008 和第二阶段的运算效率，有效的节约了译码时间，这在某些 －03）:108-124. 对实时性要求较高、芯片运算能力不强的场景是值得应用 的。算法 C 是在存在反馈信道的系统里面（可以是最简单的 反馈信道），可以通过反馈 NACK 来有效的提升译码性能。 综上所述，在 Raptor 码的实际应用中，可以根据具体的场景 来选择译码算法 A、B 与 C。 [5] KIM S,LEE S,CHUNG S Y.An Efficient Algorithm for ML Decoding of Raptor Codes over the Binary Erasure Channel[J].IEEE Communications Letters, 2008,12(08):21-26. [6] KIM S,KO K, CHUNG S Y.Incremental Gaussian Elimination Decoding of Raptor Codes over BEC[J].IEEE Communication Letters,2008,12(04):27-32. 参考文献 [7] 贾向东,欧阳玉花,谢伟.LDPC-COFDM 无线通信系统译码算法研 [1] 袁 李 林 , 李 贵 勇 .LDPC 码 及 其 应 用 [J]. 通 信 技 术 ,2007,40(09): 究[J].通信技术,2007,40(05):12-15. 91