速龙码概况
电信资料2007年第1期
速龙码概况
本文简要介绍速龙码,这是一种应用于可靠多播传输的最新DialFountain模型 信道编码
.
1背景
1.1水泉码
对于给定的k个输入码元(..,)和一个可能的包含无限个输出码元z1,z2,... 数据流,可生成水泉码.输入和输出码元可以是任意长度的二进制矢量.每个输出码元
都是随机和单独选择的输入码元子集之和在接收端通过分组报头或发送端和接收端之
间的其它同步的与应用无关的方式可以获取有关输入和输出码元之间关系的信息.
一
种水泉码的可靠译码方法应能从任意m个输出码元中恢复出原始的k个输入码 元,同时错误概率较低.比率m/k就称为开销.编码成本为生成每个输出码元预期所需
的算术运算次数.译码成本为恢复k个输入码元预期所需的算术运算次数再除以k.对
于水泉码来说,较理想的状态为开销接近1,同时编码和译码成本固定不变.通用水泉
码的译码器应能从任意尺寸接近最优的输出码元集中恢复出源码元,而且错误概率很
低.-
1.2Tornado码
Tornado并不是严格意义上的水泉码,因为其输出码元的数量对于特定编码来说
是
固定的.但它们是LT和速龙码的前身.Tornado码源于稀疏,非正则的随机二分图, 与该图相关联的编码和译码算法每边进行一次异运算需谨慎选择这些图的边的度分
布,从而当已知其所有相邻值时,只需使用一个简单的信度传播(1iP)译码器来设定图
电信资料2007年第1期
中的节点数值,即可进行高概率的成功译码.
Tornado码将这些图串联起来.对于任何给定的速率R和开销1+,都可以设计 一
个编码和译码成本为O(1og(1/E))的(,=Rn)Tornado码,可从(1+)七个输出 码元中恢复出一个码字,概率为1一o(k).
1-3LT码
LT码是第一种通用的水泉码.从一些适合的度分布中随机选择一个度d,随机选 择d个不同的输入码元,然后取其和,即可生成一个输出码元.
如果根据R0bustsoliton分布来选择输出码元度,那么从任意+(=)(?l0g(k/8) 个输出码元从可以恢复k个输入码元,概率为1一.平均的编码和译码成本为 O(1og(k/).
2LT码的不足
以下定理显示一个可靠的LT码译码器的译码图至少有O(klog(k))个边.因此, 如果译码所需的输出码元数量m接近k,那么每个输出码元平均是O0og(k))个输入码
元的和.每个码元的编码成本为OOog(k)).
定理1:如果k个输入码元的一个LT码使用一种可靠的译码算法,那么存在一个 常数c,使得译码图拥有至少cklog(k)个边.
3速龙码
速龙码的主要思想是减少对恢复所有输入码元所需条件的限制.如果LT码只需要
恢复其固定输入码元部分,那么其译码图只需要Of,个边,从而可进行线性时间编码.
通过将传统的纠错码与LT码进行级联,我们仍然可以恢复所有的输入码元.使用一个
(n,k)纠错分组码对k个输入码元进行编码会产生n个中间码元.该纠错码可根据中
间码元的,个固定成分恢复出所有输入码元.然后使用一个LT码对这n个中间码元进
8
电信资料2007年第1期
行编码.速龙码使用参数(七,C,Qf,)进行定义,其中.c为(n,k)纠错分组码,称 为预编码,而臼r为LT码度分布的生成多项式,Q)=?Q即,其中q为i=l 输出节点的度为i的概率.
1.1节中定义的性能参数开销和译码成本可直接应用于速龙码.但是,速龙码的编 码成本有所不同一一将预编码的编码成本除以k再加上LT码的编码成本.速龙码也需
要存储中间码元,所以容量消耗也是一个重要的性能参数.
4速龙码实例
4.1LT码
具有k个输入码元和输出分布Q(x)的LT码本身就是一个参数为(,,Q()) 的速龙码,其中是维数和分组长度为k的一个平凡码由于不需要预编码,所以需 使用具有对数编码和译码成本的复杂输出分布Q(),如第2节中所述.开销和空间接
近1.
4.2仅预编码(PC0)的速龙码
仅预编码的速龙码是这一编码系列的另一种极端情况.这些码具有一个复杂的预编
码,但是输出分布Q)是一个平凡分布,等于x.将每个输出码元的该分布值设置为
随机和平均选择输入码元的概率.通过该方法可根据任何分组码生成一个水泉码. 译码时将收集预定的m个输出码元,通过m可确定中间码元Z的值.然后对这些 恢复的中间值应用预编码的译码算法,计算出输入码元值.
PCO速龙码的性能取决予其预编码的性能.
5具有良好渐进特性的速龙码
具有良好渐进特性的速龙码(即编码和译码成本为常数,空间消耗和开销接近1) 9
电信资料2007年第1期
可通过选择适当的预编码C和输出分布Q)来获取.
从周期的角度考虑BP译码更为有效:由每个周期中所有释放的输出节点(即与未 恢复的输入节点相连的节点)恢复出其附带的输入节点,然后通过这些所有恢复的输入
节点更新其附带的输出节点.这样就可以恢复出与恢复节点相连的所有边. 我们从原图中随机选择一个边(v,w),可通过(v,w)未删除以及输入节点x部分 未恢复时输出节点W释放的概率来确定输出边分布()的生成多项式.类似地,通过 (v'w)未删除以及输出节点l—x部分未释放时输入节点v恢复的概率可以确定输入边
分布l(x)的生成多项式.
假设所有的输入节点在初始时都是未知的,周期f中一个随机选择的边携带其附带
输出码元信息的概率为P,,那么我们可以得到以下递归公式:
P."=coo—z(1一Pj))(1)
如果周期f中随机选择的边未携带其附带输入码元信息的概率为g,那么可以得到 一
个类似的递归公式:
q1z(1一co(1一g))
可靠恢复输入节点中部分所需的约束条件为
l(1-ca(1-x))x<,?,1】
6有限长度速龙码的设计和
(2)
(3)
上一节中介绍的渐进性分析在实际设鹭中用处不大'其中介绍的错误概率范围并不
适用于有限长度码,丽码设计选择尽管具有渐进性,但在实际中
现不好. 6.1LT码的设计和分析
LT码可通过线性编程获得.考虑对(1+s)个输出码元运行译码算法的情况.根 据等式1,如果周期f中未恢复的输入码元概率为,那么可以得到以下递归式: l0
电信资料2007年第l期
=
1一J
这说明如果在周期之初,输入码元的x部分已经得到恢复,那么该周期内预期恢复 的输入节点部分为1一—P'n''.N#~Nn(x)以最小化目标函数Q(1),从而 满足约束条件,即每个周期中预期恢复的输入码元节点数量比未恢复输入码元数量的平
方根大一个常数因子c.
给定度分布时,使用动态编程方法可以精确计算LT译码器的错误概率. 6.2预编码的设计和分析
LDPC码适合作为预编码使用,其构造方法如下:对于每个信息节点,从分布中随 意选择一个度d,然后选择d个随机校验节点为该信息节点的相邻节点.我们提供了一
种针对整体错误概率的复杂分析表达式.
6.3组合错误概率
用p表示恢复,个中间码元后LT译码器的失效概率,p;表示预编码C不能对j 个随机选择擦除进行译码的概率,那么无法从(1+)个输出码元中恢复出k个输入码
元的概率为
?pp,l=O
7系统速龙码
我们提供一种算法,可将一个给定的参数为(,C,Q(x))的速龙码转换为系统速龙 码.首先,计算包含k个位置的一个集合,它将是系统输出码元的位置.考虑预编码生
成矩阵G和LT码第一个kO+占)码元的生成矩阵即可完成该步骤.使用高斯消去法,
可确定组成一个满秩平方子矩阵R的SG的k行.这些行与系统输出码元的位置相对应.
首先将GR一从左边乘以输入码元矢量,得到矢量U,然后再用s左边乘以该结果.
电信资料2007年第1期
将LT码应用于矢量u,即可得到输出码元.
通过应用原速龙码的译码算法可得到一个码元矢量Y,从而可进行译码.原输入码 元由Ry给出.
8结论
本文对速龙码的基本思想进行了说明,并对包括简单仅预编码速龙码,渐进良好速 龙码和有限长度以及系统速龙码的设计和分析工具进行了说明. 12
译自因特网资料
(王滢波译)
(杨敏芝校)