对LT码的编码方式进行修改，不产生度为1的数据包，改为产生相关联的度2和度3的编码数据包，避免信息的直接泄露.由于不能使用常规的置信传播（BP）算法进行译码，相应给出在BP译码算法基础上增加度2数据包处理环节的译码算法（D2BP算法），同时也给出降低译码复杂度的高斯消元译码算法（SGE算法）.仿真结果显示，D2BP算法可在较低的译码开销下成功完成删除度1的LT码的译码. SGE译码算法译码开销明显低于BP类的译码算法，信道删除概率对其译码性能没有影响.相比较传统的高斯消元算法，SGE算法的复杂度明显下降.
There are a large number of LT encoded packets with degree one which are copies of source information packets. An illegal recipient can intercept the information with part of the encoded packets even if the way of encoding is unknown. For this, the way of encoding of LT was modified. The packets with degree one is replaced with a pair packet of degree two and three. As the conventional BP algorithm can not decode this kind of codes, a BP-based decoding algorithm(D2BP) in which an extra processing for degree two packets is included was presented, while a complexity reduced Gaussian elimination decoding algorithm(SGE) is given. Simulations show that D2BP and SGE algorithms can successfully decode LT codes so that the degree one packets is deleted, and SGE algorithm has significantly higher decoding efficiency than BP and D2BP algorithms. The channel erasure has no influence on the decoding performance of SGE. Compared with traditional Gauss elimination algorithm, the complexity of SGE algorithm is obviously decreased.
2002年Luby提出了第一种实用的喷泉码LT(Luby-Transform)码[1]，同时提出了理想孤子分布(ISD，ideal soliton distribution)和在此基础上改进的鲁棒孤子分布(RSD，robust soliton distribution)，其中RSD是目前LT码最常用的编码度分布.学者们也对已有度分布进行了优化[2-3].喷泉码的译码算法主要有置信传播(BP，belief propagation)和高斯消元(GE, Gaussian elimination)算法[4]. LT码的译码一般采用BP算法，其译码过程简单且接收到少量数据包即可开始译码，但要求译码过程中一直存在度为1的数据包，否则译码中断，需接收更多的数据包才能继续译码. GE算法译码开销较小而译码复杂度明显高于BP算法.学者们也在此基础上提出了一些改进的译码算法[5-6].基于稀疏矩阵的高斯消元(SGE, sparse-matrix-based Gaussian elimination)[5]算法利用LT编码矩阵的稀疏性降低了译码复杂度.
RSD是根据BP译码的要求而设计的. BP译码算法要求有足够比例的度为1的编码数据包，度为1的编码数据包就是源数据包的复制，可根据其直接恢复信息.这在存在窃听者的环境中应用时，信息很容易泄露，信息缺少基本的安全保护.因此，给出一种不产生度1数据包的编码方案，并相应提出一种增加度2数据包处理环节的BP译码算法.在对译码开销要求较高的场合，也给出一种与文献[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.
重复以上1)~3)步，可生成无限长编码数据包.
1.2 LT码的BP译码BP译码的过程如下：
1) 在接收到的编码数据包中找出度为1的编码数据包tn，设其关联的源数据包为si，令si=tn.
2) 将其他所有与si相关连的编码数据包(记为tm)与si进行异或运算，tm=tm⊕si.
3) 去除所有编码数据包与si的关联.
重复以上1)~3)步译码过程，直到恢复出所有源数据包或者没有度为1的编码数据包为止.
1.3 LT码的编码度分布理想孤子度分布函数为
| $\rho \left( d \right) = \left\{ \begin{gathered} 1/k,\;\;\;\;\;\;\;\;\;\;\;\;d = 1 \hfill \\ 1/d\left( {d - 1} \right),\;\;d = 2,3, \cdots ,k \hfill \\ \end{gathered} \right.$ | (1) |
其中：d为编码数据包的度值，k为源数据包的个数，ρ(d)为编码数据包度为d的概率.鲁棒孤子度分布引入了2个参数c和δ来确保译码过程中期望的度为1的编码数据包个数s为
| $s = c\ln \left( {\frac{k}{\delta }} \right)\sqrt k $ | (2) |
其中：δ为译码器未能完全恢复源信息的概率，c为0到1之间的常数.同时还设计了一个τ函数来增加编码数据包取较大度值的概率
| $\tau \left( d \right)=\left\{ \begin{align} & \frac{s}{k}\frac{1}{d},d=1,2,\cdots ,\left( k/s \right)-1 \\ & \frac{s}{k}\ln \left( s/\delta \right),d=k/s \\ & 0d>k/s \\ \end{align} \right.$ | (3) |
将τ函数与理想孤子度分布函数归一化合并，即可得到鲁棒孤子度分布函数为
| $\mu \left( d \right) = \frac{{\rho \left( d \right) + \tau \left( d \right)}}{Z}$ | (4) |
其中
| $Z = \sum\limits_d {\left( {\rho \left( d \right) + \tau \left( d \right)} \right)} $ | (5) |
其中μ(d)表示采用鲁棒孤子度分布编码时，产生的编码数据包度为d的概率.
2 增强安全性的LT码编码方案因为度为1的编码数据包就是源数据包的复制，可根据其直接恢复出源数据包，这使得在存在窃听者的环境中应用时，信息很容易泄露.仍以鲁棒孤子度分布为基础，但对常规LT码的编码方案进行修改.编码过程中，如果根据鲁棒孤子度分布函数随机产生的度为1时，不产生度为1的数据包，改为产生一个度为2和一个度为3的编码数据包，度为3的编码数据包所关联的源数据包中有2个就是度为2的数据包所关联的源数据包.该方案与常规LT码编码方案的不同点在编码步骤中的第2)步.分2种情况.当d>1时，与常规的LT码相同.当d=1时，则改为生成2个数据包：从k个源数据包中随机地选出2个数据包，对选出的源数据包进行异或运算，生成一个度为2的编码数据包，tn=sn, 1⊕sn, 2；再从k个源数据包中随机地选出1个数据包，将这个数据包与前面已经选出的2个源数据包进行异或运算，生成1个度为3的编码数据包，tn+1=sn, 1⊕sn, 2⊕sn, 3.该编码过程如图 1所示.
|
图 1 度为1时的编码过程 |
采用这样的编码方式不会产生度为1的编码数据包，对于窃听者来说即使窃取到编码数据包，如果不知道数据包的关联关系，也无法直接恢复源信息.而对于知道编码信息的合法接收者来说，将关联产生的度2和度3的编码数据包进行异或即可得到1个度1数据包，也就可以恢复出源数据包.
3 增强安全性的LT码译码方案 3.1 增加度2数据包处理环节的BP译码算法由于增强安全性的LT码编码方案不生成度为1的编码数据包，故不能再采用常规BP算法进行译码.编码过程中，在度值为1时生成的度为2和度为3的编码数据包相关联，因此根据它们就可产生一个度1数据包.根据这一性质，提出一种增加度2数据包处理环节的BP译码算法(D2BP，degree 2 belief propagation)，该算法首先对度为2的编码数据包进行处理，然后再进行传统的BP译码.
下面介绍的D2BP译码步骤中，第1)~3)步处理度为2的数据包，第5)~7)步进行常规的BP译码.
1) 在接收到的编码数据包中找出度为2的编码数据包tn，设与tn相连的源数据包为sn, 1和sn, 2.
2) 将其他与sn, 1和sn, 2皆相连的编码数据包(记为tm)与tn进行异或运算，tm=tm⊕tn；
3) 去除上述编码数据包与sn, 1和sn, 2的关联；
4) 重复步骤1)~3)，直至处理完所有度为2的编码数据包；
5) 在度2处理后的编码数据包中找出度为1的编码数据包tN，令si=tN；
6) 将其他与si相连的编码数据包(记为tM)与si进行异或运算，tM=tM⊕si；
7) 去除所有编码数据包与si的关联；
8) 重复步骤5)~7)，直到恢复出所有源数据包或者没有度为1的编码数据包为止；
9) 若此时未能成功译码，但译码过程中产生了新的未处理过的度为2的编码数据包，则跳至步骤1)继续处理.
重复循环上述步骤直至译码成功，或者既没有度为1的编码数据包也没有可处理的度为2的编码数据包为止.
D2BP译码过程如图 2所示.
|
图 2 D2BP译码过程示例 |
首先处理度为2的编码数据包. 图 2(a)中第1、3、7个编码数据包的度为2.其中第1个编码数据包由s1、s3异或得到.其他编码数据包中与s1、s3同时相连的数据包有第2个，因此将第1个编码数据包与第2个编码数据包作异或运算，并将所得结果赋值给第2个编码数据包，同时去除第2个编码数据包与s1、s3的关联.类似，对第3、7个编码数据包作相应处理后得到双向图(b).在所有度为2的编码数据包都已经处理后，进行常规的BP译码，无度1的编码数据包后，双向图变为图(c).可以看到第4、5个编码数据包的度降为2，再次进行度2数据包的译码处理，双向图变为图(d)，然后继续进行常规BP译码，最终译出s=[1 0 0 1 1 0]T.
对去除度1的LT码采用D2BP译码算法、常规LT编码采用BP译码算法时的性能进行仿真.两者皆采用鲁棒孤子度分布.仿真了源数据包个数k分别为1 000和100时，不同信道删除概率Pe下，成功译码时平均所需接收的编码数据包个数和译码开销.译码开销定义为
| $\varepsilon = \frac{{n - k}}{k}$ | (6) |
其中k为源数据包个数，n为译码成功时接收的编码数据包个数.仿真结果如表 1所示.
|
表 1 D2BP和常规BP算法译码成功所需编码数据包个数n和译码开销ε |
仿真结果显示，鲁棒孤子分布参数c和δ的取值对2种算法的译码开销都有一定程度的影响.不同的信道删除概率对常规LT码的译码开销几乎没有影响，但对增强安全性的LT码的译码开销有一定影响.在删除概率低时，D2BP的译码开销低于常规BP的译码开销.这是由于D2BP算法的译码过程中不仅包含了常规BP译码过程，还增加了度2数据包的处理过程，降低了译码中断的概率，从而降低了译码开销.而随着信道删除概率的增加，D2BP的译码开销逐渐增大.这是因为去除度1的LT码编码方案中，不直接发送度为1的数据包，改为发送相互关联的一个度为2及一个度为3的编码数据包，通过采用D2BP译码算法对度2的数据包进行处理恢复度1的数据包.这2个相互关联的编码数据包中的任何一个被删除都将影响译码算法的处理，最终体现在译码开销增大.另一方面，源数据的长度对译码的性能有较大的影响.当k=1 000时，2种BP算法的译码开销在适当的c和δ的取值时为15%左右，而在k=100时，译码开销上升到40%.这是因为k较大时，随机产生的度值能更符合预先设计的概率分布特性.
3.2 基于稀疏矩阵的高斯消元法删除度1的LT码采用D2BP译码算法时译码开销会随信道删除概率的增大而增加，同时短码时译码开销很高，这与常规BP译码算法相同.为提高译码效率可采用GE算法进行译码. LT码中一个编码数据包对应一个线性方程，对于译码器而言，该方程中未知数是源信息数据包，已知数是编码数据包.收到n个编码数据包后，相当于就建立了一个由n个方程组成的、有k个未知数的线性方程组.只要n个方程中线性无关的方程数达到k，就可解出k个源数据包. GE算法不要求存在度1的数据包，信道的随机删除也无影响，具有比BP算法低得多的译码开销. GE算法计算复杂度高，而LT码的编码数据包度值绝大多数为较小的值，编码生成矩阵是一个稀疏矩阵，利用该稀疏性可对高斯消元法进行改进，降低译码复杂度.下面给出一种与Li等[5]所提方案类似的基于稀疏矩阵的高斯消元法.
假设发送端发送k个源数据包，接收端接收到n个编码数据包，那么对应的编码生成矩阵G为一个n行k列的矩阵，其元素只有0和1两种取值，其第i行第j列的元素为
| ${g_{ij}} = \left\{ \begin{gathered} 1,\;\;\;{t_i}与{s_j}有关联 \hfill \\ 0,\;\;\;其他 \hfill \\ \end{gathered} \right.$ | (7) |
其中i=1, 2, …, n，j=1, 2, …, k.为叙述方便，下面的介绍中假设数据包的大小为1个符号.
LT码的编码过程可表示为
| $\mathit{\boldsymbol{t = Gs}}$ | (8) |
其中：G为编码矩阵，s为k个源数据组成的列向量，t为n个编码数据组成的列向量.
SGE算法步骤为：
1) 将G矩阵扩展为包含编码数据向量的增广矩阵G′=[G|t].
2) 利用矩阵初等行变换将编码矩阵G变为单位矩阵，此时增广矩阵G′=[I|t′].
此过程由前向消元和后向回代2步组成.前向消元过程是将编码矩阵变换为阶梯形式，这一过程的计算复杂度很高.因此，选择一个恰当的消元基准元能够有效地加速这一过程.在第k步消元时，消元剩余矩阵中第k列的非零元个数为l，如果在第k列中被选为消元基准元所在的行中非零元个数为h，那么在第k步消元时，就会产生h(l-1)次计算量.因此SGE算法就在每次选择消元基准元时，不再按照普通高斯消元从上到下的方式来选择，而是在剩余矩阵中相应列的非零元中选择h值最小的元为消元基准元，这样就可以大大减少消元时的计算量，提高译码速度.举例说明，如图 3所示.
|
图 3 SGE译码算法示例 |
第1步消元时，第1列中非零元为g11、g31和g41，而它们所在行的非零元个数分别为4、2和3，因此选择所在行非零元个数最少的g31为消元基准元.将第1、4行分别与第3行做按位异或运算进行消元，G′变为(a)，在这步消元中，SGE算法的计算量为2×2=4次异或运算.而普通高斯消元根据从上到下的方式选择非零元g11为消元基准元，则计算量为4×2=8.将第1、3行交换后G′变为(b).第2步消元时，第2列中非零元为g22、g32和g42，而它们所在行的非零元个数分别为3、2和3，因此选择所在行非零元个数最少的g32为消元基准元.将第2、4行分别与第3行做按位异或运算进行消元，G′变为(c)，在这步消元中，SGE算法的计算量为2×2=4.而普通高斯消元根据从上到下的方式选择非零元g22为消元基准元，则计算量为3×2=6.以此类推并进行后项回代，G′变为(e).可见相对于普通GE算法，SGE算法在每次消元时利用消元基准元的选择，最大限度地减小了消元的计算量，减小了复杂度.
3) 若G能成功化为单位阵，那么可将s解出，即t′；若G不能成功化为单位阵，则不能解出s中的所有数据包，需继续接收编码数据包，再尝试译码.上例中，G成功化为单位阵，则译出s=[1 1 0 1]T.
下面给出删除度1后的LT码采用SGE译码算法时的性能仿真结果.性能评价指标与BP和D2BP算法相同.仿真结果如表 2所示.
|
|
表 2 SGE算法译码成功所需编码数据包个数n和译码开销ε |
仿真结果显示，GE算法的译码开销远低于BP和D2BP译码算法. BP和D2BP算法如果在译码过程中没有或不能再产生度1的编码数据包，译码就被迫中止.此时编码生成矩阵的秩仍有很大可能达到k，用GE算法可以成功译码.因此，GE算法的译码开销要远低于BP和D2BP算法.同时因各种度值编码数据包被删除的概率相同，而提出的编码方案中关联产生的度2和度3数据包发生删除也不影响GE算法的译码，所以不同的信道删除概率对GE算法译码开销没有影响.另外，虽然相比较长码，GE算法在短码时的译码开销有所上升，但仍然很小，如k=1 000时约为0.3%附近，k=100时约为3%，实际上都是仅需要多接收2~3个编码数据包就能正确译码.
最后将SGE算法与普通GE算法的运行时间进行仿真对比.度分布仍为鲁棒孤子分布，参数为c=0.05，δ=0.05，源数据包的个数为k=1 000，在接收到n=1 020个编码数据包后进行译码.仿真结果显示，普通GE算法译码所需的时间为SGE算法的18.03倍，可见SGE算法的运算复杂度明显降低.
4 结束语现有文献中对LT码的编译码方案的优化研究较多，但较少从信息安全的角度对其进行研究.为了使用低译码复杂度的BP译码算法，需要相当比例的度1编码数据包.窃听者即使不知道编码生成矩阵，仍然可以直接从度为1的编码数据包中获取信息.对LT码的编码过程进行修改，当随机选择的度为1时，不直接发送度1的数据包，改为发送1个度2和1个度3的数据包，这2个数据包是相关联的.由于LT码编码的随机性，只要窃听者不能获得编码生成矩阵的相关信息，即使窃取到编码数据包后也不能直接获得信息.由于没有度1的数据包，译码器不能再使用常规的BP译码算法.提出了一种增加度2数据包处理环节的BP译码算法.仿真结果显示，当信道删除概率较小，源数据包长度较大时，删除度1的LT码可用D2BP译码算法在较小的译码开销下成功译码，该译码开销甚至低于常规LT码进行BP译码时的开销.但信道出现删除时会对D2BP算法的译码造成一定的影响. GE译码算法能高效进行LT码的译码，没有度1的数据包和信道的随机删除对其译码性能没有影响，适合于对删除度1的LT编码进行译码.针对LT码的稀疏性给出了一种降低译码复杂度的高斯消元算法，相比较原来的GE算法，译码复杂度有明显降低.
| [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. doi:10.1109/TCOMM.2015.2428244 |
| [3] | Rafie B R, Ardakani M. Fountain code design for the Y-network[J]. IEEE Communications Letters , 2015, 19 (5) :703–706. doi:10.1109/LCOMM.2015.2407878 |
| [4] | 朱宏杰.喷泉码编译码技术与应用研究[D].北京:清华大学, 2009. http://cdmd.cnki.com.cn/article/cdmd-10003-2009224199.htm |
| [5] | Li Xiangming, Jiang Tao. Fountain codes over GF(q)[J]. Wireless Communications and Mobile Computing , 2013, 13 (16) :1423–1434. |
| [6] | 焦健, 杨志华, 顾术实, 等. 基于随机置换展开与停止集的LT码联合编译码算法[J]. 通信学报 , 2013, 34 (2) :31–39. Jiao Jian, Yang Zhihua, Gu Shushi, et al. Novel joint encoding/decoding algorithms of LT codes based on random permute egde-growth and stopping set[J]. Journal on Communications , 2013, 34 (2) :31–39. |