一种LT码编码生成矩阵的伪随机产生方案

2017-05-18雷维嘉谢显中

重庆邮电大学学报(自然科学版) 2017年2期

关键词：译码器度值孤子

盛洁，雷维嘉，谢显中

(重庆邮电大学移动通信技术重庆市重点实验室，重庆 400065)

一种LT码编码生成矩阵的伪随机产生方案

盛洁，雷维嘉，谢显中

(重庆邮电大学移动通信技术重庆市重点实验室，重庆 400065)

常用的LT码编码生成矩阵的传输方案是在每个编码数据包的头部额外增加一个开销，用于放置该数据包对应的编码生成矢量。该方案会产生较大的开销，造成传输效率降低。给出了一种编码生成矩阵在编码器和译码器间伪随机同步产生的方案。采用该方案时，只要编码器和译码器伪随机数发生器的算法相同，种子也相同，就能产生一样的均匀伪随机数序列，将其进行转化后就能得到相同的编码生成矩阵。种子数据量小，且只需要在伪随机数发生器初始化时编码器和译码器间交换一次即可。实验结果显示，生成的伪随机度值符合指定的度分布函数，数据包的伪随机选择也符合泊松分布。相比较传统方案，该方案避免了编码生成矩阵的直接传输，减少了传输开销，提高了传输效率。

数字喷泉码；LT码；编码生成矩阵；伪随机产生

0 引言

1998年，Michael Luby等提出了数字喷泉码的概念。发送端可随机地、源源不断地产生编码数据包，而接收端不需要关心具体接收到了哪些编码数据包，只要其数量略大于源数据包的个数，那么源信息就能以很大的概率被完全恢复出来。2002年Luby[1]提出了第一种实用的喷泉码LT码，同时提出了2种度分布[1]：理想孤子度分布(ideal soliton distribution, ISD)；改良的鲁棒孤子度分布(robust soliton distribution, RSD)。其中，RSD是目前LT码最常用的编码度分布[2-4]。

在LT码编码过程中，编码器利用特定的度分布函数产生随机度值，并随机选择相应个数的源数据包，得到一个编码生成矢量，根据该矢量进行编码得到一个编码数据包。编码生成矢量构成了编码生成矩阵。在译码过程中，不论是采用置信传播(belief propagation, BP)还是高斯消元(Gaussian elimination, GE)算法译码，译码器都需要根据编码生成矩阵来处理编码数据包。相关文献中通常假设译码器对编码生成矩阵是已知的[5]。由于编码生成矩阵是随机生成的，实际上需要由编码器传输给译码器。常用的方法是在编码数据包的头部额外增加一个开销，用于放置该数据包对应的编码生成矢量。这种方案的传输效率较低，参与编码的源数据量越大，编码生成矢量就越长，传输开销就越大。为提高传输效率，另一种可行的方案是在编码器和译码器之间采用伪随机的方式同步产生编码生成矩阵。采用该方案时，只要编码器和译码器伪随机数发生器的算法相同，种子也相同，就能产生一样的编码生成矩阵。种子数据量小且只需要在伪随机数发生器初始化时交换一次即可，避免了编码生成矩阵在信道上的传输，减少了传输开销，提高了传输效率。其缺点是产生的编码生成矢量不是真正的随机数，有一定的规律，但只要伪随机数的周期足够长，也能满足需要。

1 LT码

1.1 LT码的编码

设源数据包为s1,s2,…，编码数据包为t1,t2,…，LT码生成编码数据包的过程如下。

1)每k个源数据包分为一组，编码在一个分组内以数据包为单位进行。不失一般性，假设一个分组内的k个源数据包为(s1,s2,…,sk)。

2)根据编码度分布函数随机产生一个度d，并从一个分组内的k个源数据包中随机地选出d个数据包(sn,1,sn,2, …,sn,d)。

3)对选出的源数据包进行异或运算，生成一个编码数据包，tn=sn,1⊕sn,2⊕…⊕sn,d。

重复以上3步，可生成无限长编码数据包。

LT码的编码过程还可以用矩阵的形式表示为

(1)

每个编码数据包对应一个编码生成矢量，如第n个编码数据包对应的编码生成矢量为Gn=[gn1,gn2,…,gn(k-1),gnk]T，其中被选中的源数据包对应元素位为1，其余为0，最终产生的编码数据包tn由Gn中元素1所对应的源数据包异或得到。编码过程中每个编码数据包对应的编码生成矢量Gn共同组成了编码数据包的生成矩阵。

1.2LT码的BP译码

LT码的译码通常采用BP译码算法，该算法的译码过程相对简单，具有较低的译码复杂度，且接收到少量数据包即可开始译码。

BP译码的过程如下。

1)在接收到的编码数据包中找出度为1的编码数据包tn，设其关联的源数据包为si，令si=tn。

2)将其他所有与si相关连的编码数据包(记为tm)与si进行异或运算，tm=tm⊕si。

3)去除所有编码数据包与源数据包si的关联。

重复以上3步译码过程，直到恢复出所有源数据包或者没有度为1的编码数据包为止。

无论采用何种算法译码，译码器在译码时都需要知道编码生成矩阵信息。

1.3 编码度分布

LT码常用的编码度分布是鲁棒孤子度分布，是在理想孤子度分布的基础上构造的。理想孤子度分布函数为

(2)

(2)式中：d表示编码数据包的度值；k表示源数据包个数；ρ(d)表示编码数据包度为d的概率。鲁棒孤子度分布在理想孤子度分布基础上，引入2个参数c和δ来确保译码过程中期望的度为1的编码数据包个数为

(3)

(3)式中：s为编码数据包个数；δ为译码器未能完全恢复源信息的概率；c为0～1的常数。同时还引入了一个τ函数来增加编码数据包取较大度值的概率：

(4)

将τ函数与理想孤子度分布函数归一化合并即可得到鲁棒孤子度分布函数：

(5)

(5)式中，

(6)

(6)式中，μ(d)表示采用鲁棒孤子度分布编码时，产生的编码数据包度为d的概率。

2 均匀伪随机数发生器

服从任意概率分布的伪随机数都可以通过反函数法、舍选抽样法等对(0,1)上均匀分布的伪随机数进行变换得到[6-7]。伪随机数是利用数学递推公式生成的随机数，只要给定了初值就能重复生成完全相同的随机数序列。虽不是真正的随机数，但是如果采用性能良好的递推算法，可以使得生成的随机数具有类似真随机数的统计特性。下面对几类常用的均匀伪随机发生器作简要介绍，这些伪随机发生器都能产生(0,1)上的均匀随机数。

2.1 线性同余发生器

线性同余发生器[6]的其递推公式为

(7)

(7)式中：a为乘量；c为增量；x0为初值，也就是种子；m为模数，0≤xi0时，则为混合线性同余发生器。若线性同余发生器的增量c=0，则称为乘线性同余发生器。若m≤2L的最大素数，L为一个正整数，则可获得周期T=m-1、统计性能良好的素数模乘同余发生器。

2.2 满抛物线映射随机数发生器

满抛物线映射的表达式为

(8)

递推时的初值x0为初值，就是种子。其中，x为状态变量，φ为参数。

当φ=2时，满抛物线映射的表达式为

(9)

其迭代值概率密度函数为

(10)

区间两端有奇异性，对其求积分，分布函数为

(11)

(11)式中，y(x)为(-0.5,0.5)上均匀分布的伪随机数列，将其变换为(0,1)上的均匀伪随机数列为

(12)

满抛物线映射随机数发生器作为一种混沌伪随机数发生器[8]，具有较好的统计特性，但其高维伪随机数列的独立性较差。

2.3 组合发生器

为了得到周期更长、统计特性更优的伪随机数列，把多个独立伪随机数发生器组合在一起，以这样的方式得到的新的发生器被称为组合发生器[5]。

一类组合发生器算法的具体步骤如下。

1)用第1个伪随机数发生器生成q个伪随机数，将这q个伪随机数按顺序保存在T=(t1,t2,…,tq)中，令i=1；

2)用第2个伪随机数发生器生成一个伪随机整数j，1≤j≤q；

3)令ri=tj，再次用第一个伪随机数发生器生成一个伪随机数y，令tj=y,i=i+1；

4)重复步骤2)、3)，获得的数列{ri}就是组合发生器生成的伪随机数列。

3 编码生成矩阵的伪随机产生

LT码的一个编码数据包的生成过程分成2个步骤：首先产生出符合指定度分布的随机度值；然后再根据产生的度值随机选取相应个数的源数据包进行异或运算，得到一个编码数据包。因此，产生编码生成矩阵需要2个伪随机数发生器，一个产生符合指定度分布的随机度值；另一个产生选取源数据包的编号，它们都可以采用离散分布的直接抽样法[6]由(0,1)上的均匀伪随机数转换得到。

3.1 编码数据包度值的产生

设需要由均匀伪随机数产生符合度分布函数μ(d)的伪随机度值。若源数据包个数为k，首先求出不同度的概率值μ(1)～μ(k)，然后根据这些度值将(0,1)划分为k个取度区间，如表1所示。

表1 各度值的取度区间

由服从(0,1)上均匀分布的伪随机变量的概率密度函数可知，落在(0, 1)内任何子区间上的概率仅与此子区间的长度成正比，而与子区间所在的位置无关。根据各个度的取值概率μ(1)～μ(k)，在(0, 1)内依次划分不同长度的子空间。如度为2的取度概率为μ(2)，则对应划分区间(μ(1),μ(1)+μ(2)]，该区间长度为μ(2)，那么均匀随机数落在该区间的概率就为μ(2)，其他度值情况依次类推。调用伪随机数发生器，产生(0, 1)上的均匀伪随机数后，判断伪随机数落在划分的哪个区间，就相应得到符合指定度分布函数的伪随机度值。

为验证这种度值的取得是否符合指定度分布函数，首先利用3个发生器分别产生1.02×107个均匀伪随机数。各发生器的递推公式如下。

1)发生器A：素数模乘同余发生器

(13)

2)发生器B：满抛物线映射随机数发生器

(14)

3)发生器C：发生器A和发生器B形成的组合发生器，首先用发生器A生成长度为127的随机数列，即q=127，然后用发生器B将生成的随机数列打乱重排，并最终生成1.02×107个(0,1)上的均匀随机数。

上述发生器生成的随机数列皆通过参数、均匀性及独立性检验。各统计检验方法详见文献[5]。

然后由这些伪随机数产生符合k=1 000，c和δ皆为0.05的鲁棒孤子度分布的伪随机度值。统计产生的伪随机度中各度值出现的个数，求出取得各个度值的频率，并将其与鲁棒孤子度分布概率作对比。对比情况如表2所示。根据鲁棒孤子度分布的特征，将取较大概率值的度1～30，64的概率值和伪随机产生的度值的频率值进行对比。表2中，第2列“概率值”为根据鲁棒孤子度分布的数学表达式计算得到的各度值的概率值，第3～5列为不同伪随机数发生器输出各度值的频率值，即某种度值出现的次数与产生的伪随机数总数的比值。可见，各个伪随机数发生器产生的度值频率值都与鲁棒孤子度分布的概率值非常契合，产生的伪随机度值均符合鲁棒孤子度分布。

表2 按鲁棒孤子度分布伪随机产生的度值的频率

3.2 根据度值伪随机选择源数据包

LT码的编码中，产生出符合指定度分布的伪随机度值后，还需要随机选取相应个数的源数据包进行异或运算，最终得到编码数据包。

设源数据包个数为k，由于是均匀选择，每个源数据包被选中的概率均为1/k，因此，将(0,1)划分为k个子区间，如表3所示。调用伪随机数发生器，产生(0,1)上的均匀伪随机数后，判断这个伪随机数落在划分的哪个区间，就确定了具体选择哪个编号的源数据包。

表3 源数据包被选中的区间

实际编码时，产生每个编码数据包时需按照其度值选择完全不同的d个源数据包进行异或。因此，对同一个编码数据包而言，选择源数据包的过程是不放回抽样，即当选到同一个源数据包编号时应舍弃重选，直至选出完全不同的d个编号为止；而对不同的编码数据包而言，选择源数据包的过程才是真正的放回抽样。理论上各个源数据包被选中的次数应渐近服从泊松分布。其概率函数为

(15)

泊松参数λ的表达式为

(16)

(16)式中，Ωavg表示编码数据包的平均度值；k为源数据包个数；n为编码数据包的个数。

对源数据包选择过程进行实验验证。首先由发生器A产生1 200个(0,1)上的伪随机数，然后利用3.1节的方法将其转化为1 200个符合k=1 000，c和δ皆为0.05的鲁棒孤子度分布的伪随机度值，最后再利用上述方法随机选取源数据包。然后对各个源数据包被选中的次数进行统计，计算得到各次数出现的频率值。共进行20 000次这样的实验，将实验结果平均得到实验的平均频率值。理论上，源数据包被选中次数的概率应服从泊松分布P(λ)，λ=12.225811858256170×1.2。实验得到的次数的频率值与泊松分布概率值的对比情况如表4所示，表中列出取较大概率值的3～30次的情况。从表4可知，实验得到的源数据包被选中次数的频率值与泊松分布概率值非常接近。

表4 源数据包被选中次数频率与相应泊松分布概率的对比

3.3 传输开销分析

由于生成编码数据包的过程中度值及对应编码数据包的选取都是利用伪随机发生器产生的，只要发送端与接收端采用相同的伪随机发生器并取相同初值，就能实现生成矩阵在编译码器间的同步产生。因此，只需要在数据传输开始时在编、译码器间交换1次2个伪随机数发生器的种子(即发生器的初值)即可，可降低编码生成矩阵信息传输的开销。下面简单分析一下开销的降低情况。

假设一个编码数据包的信息数据长度为Lp字节，每k个编码数据包为一组进行LT码编码传输。采用传统的方法时，需要在数据包头增加一个开销，传输对应的编码生成矢量(长度就是k)，开销大小就是k比特，相对的开销为

(17)

(18)

采用本文提出的方案时，仅需要每k个编码数据包交换一次2个伪随机数发生器的种子，设种子长度为Ls比特，则相对开销为

(19)

4 总结

编码生成矩阵对LT码的编译码都具有十分重要的意义，其在编码器和译码器之间传输时常用的方法是在每个编码数据包的头部额外增加一个开销，用于存放该数据包对应的编码生成矢量。这种方法的传输效率较低，特别当一次LT编码时源数据包的数量较大时，传输开销会大大增加。为提高传输效率，本文给出一种编码生成矩阵在编码器和译码器间伪随机同步产生的方案。首先利用素数模乘同余发生器、满抛物线映射随机数发生器或它们组合得到的伪随机发生器产生(0,1)上均匀分布的伪随机数，然后利用离散分布的直接抽样法将均匀伪随机数转化为符合度分布的随机度值以及选择源数据包时所需的随机序号值。通过实验验证了生成的随机度值符合指定的度分布函数，数据包被随机选择的次数也服从泊松分布。采用该方案时，只要编码器和译码器伪随机数发生器的算法相同，种子也相同，就能产生一样的随机度值以及选择源数据包时所需要的随机序号值，即得到相同的编码生成矩阵。种子数据量小，且只需要在伪随机数发生器初始化时在编码器和译码器间交换一次即可。相比较将编码生成矩阵在信道中传输的方案，该方案显著提高了传输效率。

[1] LUBY M. LT codes[C]//The 43rd annual IEEE symposium on Foundations of Computer Science. Vancouver: IEEE Press, 2002: 271-280.

[2] SUH Y K, BAIK J Y, RAHNAVARD N, et al. Fountain code design for broadcasting systems with intermediate-state users[J]. IEEE Transactions on Communications, 2015, 63(9): 3057-3068.

[3] MENG Z,CALDERBANK R,SHUGUANG C.On design of rateless codes over dying binary erasure channel[J].IEEE Transactions on Communications,2012,60(4):889-894.

[4] RAFIE B R, ARDAKANI M. Fountain code design for the Y-network[J]. IEEE Communications Letters, 2015, 19(5): 703-706.

[5] MACKAY D J C. Fountain codes[J]. IEE Proceedings Communications, 2005, 152(6): 1062-1068.

[6] 高惠璇. 统计计算[M]. 北京: 北京大学出版社, 1995: 80-223. GAO H X. Statistical calculations[M]. Beijing: The Peking University Publishing House, 1995: 80-223.

[7] CHEN J, MOON J, BAZARGAN K. Reconfigurable readback-signal generator based on a field-programmable gate array[J]. IEEE Transactions on Magnetics, 2004, 40(3): 1744-1750.

[8] BEIRAMI A, NEJATI H. A framework for investigating the performance of chaotic-map truly random number generators[J]. IEEE Transactions on Circuits and Systems, 2013, 60(7): 446-450.

(编辑：刘勇)

A pseudo-random scheme to generate the generator matrix of LT codes

SHENG Jie, LEI Weijia, XIE Xianzhong

(Chongqing Key Laboratory of Mobile Communication Technology, Chongqing University of Posts and Telecommunications, Chongqing 400065, P.R. China)

The generator vector of LT codes is transmitted by using an overhead in the header of each encoded packet to place code generation vector correspondingly in the traditional scheme.This scheme brings a large overhead, which causes the decline of transmission efficiency. Based on this, a pseudo-random generation scheme is given in this paper, which generates the generator matrix at encoder and decoder synchronously. The generator matrices generated in this way will be identical to each other, as long as the encoder and decoder use the same pseudo-random generator and the same seed. The seed is small data-wise, and it only needs to be exchanged once between the encoder and decoder when the pseudo-random generators are initialized. Experimental results show that the generated pseudo-random values are in accordance with the specified degree distribution, and the pseudo-random indices of source packets for encoding obey Poisson distribution values. Compared with traditional methods, this scheme avoids direct transmission of the generator matrix, which can reduce transmission cost and improve transmission efficiency.

digital fountain codes; LT codes; generator matrix; pseudo-random generation

10.3979/j.issn.1673-825X.2017.02.003

2016-05-10

2016-09-28 通讯作者：盛洁 1220315828@qq.com

国家自然科学基金(61471076， 61301123)；长江学者和创新团队发展计划(IRT1299)；重庆市科委重点实验室专项经费

Foundation Items：The National Nature Science Foundation of China(61271259,61471076); The Changjiang Scholars and Innovative Research Team Plan(IRT1299); The Special Fund of Chongqing Key Laboratory

TN919.3

1673-825X(2017)02-0155-06