一种LT码度分布优化方法

姚渭箐; 胡凡; Yao Weiqing; Hu Fan

网刊加载中。。。

使用Chrome浏览器效果最佳，继续浏览，你可能不会看到最佳的展示效果，

确定继续浏览么?

复制成功，请在其他浏览器进行阅读

一种LT码度分布优化方法 PDF

姚渭箐 ^1,2
胡凡 ²

1. 国网湖北省电力有限公司信息通信公司，武汉，430077； 2. 武汉大学电子信息学院，武汉，430072

中图分类号： TN911

发布日期：2019-10-17

DOI：10.16337/j.1004-9037.2019.05.015

摘要

作为一类码率不受限的纠删码，Luby变换(Luby transform, LT)码已成功地应用于无线通信，实现数据的可靠传输。度分布是影响LT码性能优劣的关键因素。然而，传统的鲁棒孤子分布(Robust soliton distribution, RSD)在LT码码长较短下的性能不够理想。针对该问题，提出一种适用于二进制删除信道(Binary erasure channel, BEC)的新型LT码度分布优化方法。基于度分布重要特性，采用人工鱼群算法(Artificial fish swarm algorithm, AFSA)对RSD中某些重要度数的比例进行寻优。仿真结果表明，与类似方法及传统的RSD相比，采用新度分布进行LT编码可降低译码开销，并节约编译码耗时。

关键词

喷泉码; Luby变换码; 鲁棒孤子分布; 人工鱼群算法; 平均度数

引言

喷泉码是一类纠删码^[

1,2]，具有无需反馈重传、无码率性、兼容性强和编译码复杂度低等特征，已广泛应用于深空通信^{[参考文献 3
查找原文

3]}、认知无线电^{[参考文献 4
查找原文

4]}、物联网^{[参考文献 5
查找原文

5]}和云存储等领域^{[参考文献 6
查找原文

6]}。2002年，Luby提出了第一个喷泉码的具体实现方案——LT(Luby transform)变换码^{[参考文献 7
查找原文

7]}，完成了对LT码的编译码算法及度分布构造的基础研究，其中最重要的贡献是完成了对鲁棒孤子分布(Robust soliton distribution, RSD)的推导及分析。

RSD也存在一定局限性，在一些实时性要求较高的应用中，例如视频图像传输，为提高传输速率需尽量减小码长。然而，在短码长构造下RSD的译码性能较差，需要较大的译码开销才能译码成功。针对该问题，国内外诸多学者和科研机构在LT码的度分布优化问题上做了大量研究工作。

文献[

8,9]分别采用粒子群优化算法(Particle swarm optimization, PSO)和蚁群算法(Ant colony algorithm, ACA)对LT码度分布进行优化。将度分布中度数的比例值映射到仿生算法的解空间构建初始路径，经过仿生算法迭代优化，从一定程度上能够得到相同度分布参数要求下更优的度分布值。文献[10]将二进制指数分布(Binary exponential distribution, BED)和RSD相结合提出一种译码性能更优的开关度分布(Switch degree distribution, SDD)。在编码器编码的初始阶段，采用BED进行编码，当已经产生一定数量编码分组后，将BED切换到RSD。文献[11]基于置信传播(Belief propagation, BP)算法的AND⁃OR分析，将度分布优化问题转化为半正定规划(Semi⁃definite programming, SDP)形式，随后又转化为一个线性规划问题。文献[12]引入加权系数将改进的泊松分布(Improved Poisson robust soliton distribution, IPD)和RSD联合成一种适用于LT码的联合泊松鲁棒孤子分布(Combined Poisson robust soliton distribution, CPRSD)。并基于期望可译集特性，采用黄金分割点算法对加权系数进行寻优。

尽管现有的度分布优化方案已取得一定研究成果，但仍然存在提升的空间。为了得到更优的度分布，本文基于度分布重要特性，采用人工鱼群算法(Artificial fish swarm algorithm, AFSA)对RSD中某些重要度数的比例进行寻优。仿真结果证明，在二进制删除信道(Binary erasure channel, BEC)中，采用优化后的度分布对短码长LT码进行编码，能有效降低译码开销，并节约编译码耗时。

1 LT码及度分布

1.1　LT码编译码过程

LT码的编码过程非常简单，具体如下：

Step 1 从度分布中随机选择一个度 $i$ ；

Step 2 随机且均匀地选取 $i$ 个原始分组；

Step 3 将这 $i$ 个原始分组进行异或生成一个编码分组。

重复以上步骤，编码生成无限且灵活数量的编码分组。

接收端接收到N个编码分组(N略大于k)，然后开始译码^[

7]。通常，LT码采用BP算法进行译码。

Step 1 度数为1( $i = 1$ )的编码分组直接译码；

Step 2 译出的原始分组与跟其相连的编码分组进行异或后替代原编码分组，同时删除其连接关系。

重复以上步骤，直至译码完成。LT码编译码过程如图1所示。

图1 LT码编译码过程

Fig.1 LT encoding and decoding process

1.2　度分布

根据LT码编译码过程可知，度分布对LT码的性能影响至关重要。文献[

7]指出，一个好的度分布需满足两个设计目标：（1）译码成功所需的平均编码分组数量尽可能少，确保LT译码成功的编码数量对应于确保原始分组全部译出的编码分组数量。（2）编码分组的平均度数尽可能小，平均度数是生成一个编码分组所需的平均异或运算次数，因此，平均度数决定了编码复杂度，而译码复杂度则是平均度数乘以译码成功所需编码分组数量。

最经典的是Luby在2002年提出的RSD^[

7]，其表达式如下

$μ (i) = \frac{ρ (i) + τ (i)}{\overset{k}{\sum_{i = 1}} (ρ (i) + τ (i))} i = 1,2, \dots, k$

(1)

式中

$τ (i) = \{\begin{array}{l} \frac{R}{i k} & i = 1,2, \dots, [\frac{k}{R}] - 1 \\ \frac{R}{k} l n (\frac{R}{δ}) & i = [\frac{k}{R}] \\ 0 & i = [\frac{k}{R}] + 1, \dots, k \end{array}$

(2)

$ρ (i) = \{\begin{array}{l} \frac{1}{k} & i = 1 \\ \frac{1}{i (i - 1)} & i = 2,3, \dots, k \end{array}$

(3)

且 $R = c l n (k / δ) \sqrt[]{k}$ 为译码过程中期望度数为1的编码分组数量，k为原始分组数量，c为正常数，δ为允许的译码失败概率。

RSD函数最后的“Spike”τ(k/R)能保证编码过程中高效地覆盖所有原始分组。

1.3　度分布重要特性

度分布中某些度数对LT码可译码性的影响至关重要，通过调整这些度数在度分布中的比例，LT码可获得良好的性能。首先，度数为2在度分布中所占比例最高，当 $k \to \infty$ 时，该比例趋近于1/2^[

13]。其次，需要度数为1的编码分组来触发BP译码开始，意味着度数为1的比例大于0。但是，过多的度数为1的编码分组会造成低效译码，也就是说，度数为1的比例必须要小。可以发现，好的度分布都具有一个共性，即度数为1的比例远小于度数为2的比例，否则，会导致一个相当大的最小译码开销^{[参考文献 14
查找原文

14]}。

2 基于人工鱼群算法的度分布优化方法

基于度分布重要特性，对RSD进行改进。采用AFSA对RSD中度数为1、度数为2以及度数为k/R的比例进行寻优，从而得到相同度分布参数要求下更优的度分布。

AFSA^[

15]是一种模拟鱼群的觅食、聚群、追尾等典型行为在搜索域中实现寻优的智能进化算法。人工鱼对视野范围内的环境进行感知，即模拟群聚行为和追尾行为，然后进行行为评价，选择最优者来实际执行，默认行为方式为觅食行为。

2.1　寻优原理

基于AFSA度分布寻优的核心是：首先，将度分布中度数为1、度数为2以及度数为k/R的比例值映射到AFSA的解空间构建初始值；接着，基于平均度数构建该算法的目标函数；然后，通过比较和迭代逼近最大目标值从而获得优化的度分布。

（1）　初始值产生

重要度数的比例对应一个人工鱼的状态为 $Ω = (Ω (1), Ω (2), Ω ([k / R]))$ 。基于度分布特性和RSD $(μ (1), μ (2), \dots, μ (k))$ 产生人工鱼初始值

$\{\begin{array}{l} Ω (1) \in (0, μ (1)) \\ Ω (2) \in (μ (2), 0.5) \\ Ω ([k / R]) = μ (1) + μ (2) + μ ([k / R]) - Ω (1) - Ω (2) \end{array}$

(4)

（2）　目标函数构建

为降低编译码复杂度，希望编码分组的平均度数尽可能小^[

7]。由于非重要度数的比例保持不变，因此，将度分布优化问题转换为最小化

$Ω (1), Ω (2), Ω ([k / R])$ 的平均度数，即通过最小化式（5）来获得优化度分布

$y = Ω (1) + 2 \cdot Ω (2) + ([k / R]) \cdot Ω ([k / R])$

(5)

（3）　人工鱼群算法

度分布优化问题的解决是通过人工鱼在寻优过程中以局部最优和个体最优形式表现出来的。寻优的过程中，跟踪记录最优个体的状态，该过程可通过模拟人工鱼追尾行为来实现。追尾行为有助于快速地向某个极值方向前进，可防止人工鱼在局部振荡而停滞不前。随着寻优过程的进展，人工鱼往往会聚集在极值点的周围，并且全局最优的极值点周围通常能聚集较多的人工鱼，该过程可通过模拟人工鱼聚群行为实现。在对追尾行为和聚群行为进行评价后，自动选择合适的行为，从而实现对度分布高效快速的寻优。基于AFSA度分布寻优原理如图2所示。

图2 基于AFSA的度分布优化模型

Fig.2 Optimization of degree distribution based on AFSA

具体人工鱼行为描述如下。

（1）视觉模拟(逼近搜索)：设一个人工鱼的当前状态为 $Ω = (Ω (1), Ω (2), Ω ([k / R]))$ ，在搜索域( $V i s u a l$ )内进行随机搜索，如果感知到更优状态 $Ω' = (Ω' (1), Ω' (2), Ω' ([k / R]))$ ，则朝该状态的位置方向前进一步；否则，继续搜索。该过程可以表示为

$Ω' (i) = Ω (i) + V i s u a l \cdot R a n d ()$

(6)

$Ω_{n e x t} = Ω + \frac{Ω' - Ω}{| | Ω' - Ω | |} \cdot S \cdot R a n d ()$

(7)

式中： $R a n d \in (- 1,1)$ ， $S$ 为最大移动步长。

（2）聚群行为(局部寻优)：设人工鱼当前状态为 $Ω$ ，在 $V i s u a l$ 内随机搜索聚集成群的 $n_{y}$ 个人工鱼，并定位这 $n_{y}$ 个人工鱼间的中心位置 $Ω_{c}$ ，如果 $y_{c} / n_{y} > d \cdot y$ ( $d$ 为拥挤度因子，表示与其他人工鱼之间的拥挤情况)，表明该位置为局部最优位置，则根据式(7)，朝 $Ω_{c}$ 方向前进一步；否则执行觅食行为。

（3）追尾行为(个体寻优)：设人工鱼当前状态为 $Ω$ ，在 $V i s u a l$ 内随机搜索 $n_{y}$ 个人工鱼，并定位其中 $y_{j}$ 为最小的 $Ω_{j}$ ，如果 $y_{j} / n_{y} > d \cdot y$ ，表明该状态为个体最优，则根据式(7)，朝 $Ω_{j}$ 方向前进一步；否则执行觅食行为。

（4）觅食行为(随机寻优)：设人工鱼当前状态为 $Ω$ ，在视野范围内随机搜索一个状态 $Ω_{j}$ ，如果 $y > y_{j}$ ，表明该状态优于当前状态，则根据式(7)，朝 $Ω_{j}$ 方向前进一步；反之，再重新搜索。反复试探多次后，如果仍无法定位更优状态，则根据式(6)，随机移动一步。

2.2　寻优步骤

Step 1 基于RSD产生初始鱼群，例如，鱼群大小为 $m$ ，有3个待优化的参数，即 $Ω = (Ω (1), Ω (2), Ω ([k / R]))$ 。其中， $Ω (1) \in (0, μ (1))$ ， $Ω (2) \in (μ (2), 0.5)$ ， $Ω ([k / R]) = μ (1) + μ (2) + μ ([k / R]) - Ω (1) - Ω (2)$ ，则要随机产生一个3行 $m$ 列初始鱼群 ${Ω_{v} | v = 1,2, \dots, m}$ 。

Step 2 每个人工鱼执行群聚行为得到局部最优值，执行追尾行为得到个体最优值。

Step 3 通过行为评价，即比较两种行为的目标函数值，选取函数值较小者作为一个人工鱼的最优值 $y_{v m i n}$ 及其对应的 $Ω_{v m i n}$ 。

Step 4 $m$ 个人工鱼完成一次感知行为得到 ${y_{1 m i n}, y_{2 m i n}, \dots, y_{m m i n}}$ 及其对应的 ${Ω_{1 m i n}, Ω_{2 m i n}, \dots, Ω_{m m i n}}$ ，再比较 $m$ 个人工鱼目标函数值，选取函数值最小者作为人工鱼群的最优值，得到 $y_{m i n}$ 及其对应的 $Ω_{m i n}$ 。

Step 5 将 $y_{m i n}$ 与前一次的最优值进行比较，得到一次迭代的最优值 $y_{b e s t}$ 及其对应的 $Ω_{b e s t}$ ，如果迭代次数小于设定值，转移到Step 2，否则寻优完成，得到全局最优目标函数值 $y_{b e s t}$ 及其对应的人工鱼状态 $Ω_{b e s t}$ 。

优化后的 $Ω_{b e s t} (2)$ 的比例有所增加且满足 $Ω_{b e s t} (1) ≪ Ω_{b e s t} (2)$ ，符合度分布通用特性^[

14]，可降低恢复所有原始分组所需的最小译码开销。而此时，

$Ω_{b e s t} ([k / R])$ 仍然保持较高比例，从而保证编码过程中高效地覆盖所有原始分组。并且，由于平均度数降低，意味着编译码过程中进行的异或运算量大大降低，从而加快编译码速度。因此，即使在码长较短(原始分组数k<10⁴)时，也能保证较好的译码性能和编译码效率。

3 性能仿真及分析

为验证所提方法的有效性，根据参考文献[

12]，选取相同参数

$k = 1 000$ ，

$c = 0.1$ ，

$δ = 0.005$ 时，分别对本文改进的RSD(Modified RSD, MRSD)、参考文献[8,9,10]中的度分布设计方法和RSD进行1 000次编译码仿真，然后对实验结果进行比较和分析。AFSA算法中对各参数的取值范围比较宽容，并且对算法的初值也基本无要求^{[参考文献 15
查找原文

15]}。根据每个度值的初始值约束范围，经过多次实验选取AFSA参数为：人工鱼数量为m=50个，试探次数为100次，迭代次数为50次，Visual=0.001，d=0.618，S=0.000 5。仿真实验平台为Intel(R) Core(TM) 2.8 GHz处理器，4 GB内存。采用Matlab R2014a编程仿真。

MRSD及其他4种度分布的译码成功率随译码开销((N-k)/k)变化情况如图3所示。译码成功率为译码器接收不同数量的编码分组时，成功译出的分组数占原始分组总数的比例。从图3可以明显看出，传统的RSD不太适用于短码长LT码。RSD初始译码成功率较低，并需要50.7%译码开销才能完全恢复k=1 000原始分组。而MRSD译码性能最优，不仅初始译码成功率较高，并随着接收编码分组数的增多，译码成功率快速上升，达到恢复k=1 000原始分组时的译码开销仅为25.2%。与其他3种优化度分布相比，MRSD译码性能也是最优。

图3 不同度分布译码性能( $k = 1 000, c = 0.1, δ = 0.005$ )

Fig.3 Decoding performance for different degree distributions

表1对5种度分布的译码成功所需的平均译码开销、平均度数以及单次编译码耗时进行比较。当k=1 000时采用MRSD度分布进行LT编码，译码成功所需的平均译码开销比其他4种度分布降低了5.7%~25.5%，并且节约了至少8.5%(8.5%~44.9%)的平均编译码耗时。

表1 不同度分布性能比较(

$k = 1 000, c = 0.1, δ = 0.005$ )

Tab.1 Performance comparison for different degree distributions (

$k = 1 000, c = 0.1, δ = 0.005$ )

参数	文献[8]	文献[9]	文献[10]	RSD	MRSD
译码开销/%	40.4	30.9	45.1	50.7	25.2
平均度数	7.5	6.8	10.7	11.7	6.6
平均编译码耗时/s	17.5	14.0	23.4	17.9	12.9

为获得更为直观的对比结果，采用256×256×8=524 288 bit的灰度图作为传输数据。将原始数据均分为1 024个原始分组(每个原始分组包含512 bit)，当接收端接收到1 200个编码分组时强制译码恢复，对图像的恢复质量进行直观评估，结果如图4所示。从图4中明显看出，RSD以及其他3种优化度分布恢复的图像都存在不同程度的失真，而MRSD度分布几乎完全恢复图像。

图4 5种度分布图像恢复质量比较

Fig.4 Image recovery for five degree distributions

4 结束语

针对RSD在LT码码长较短时性能不够理想的情况，本文提出一种适用于BEC信道的度分布优化方法。基于度分布特性和AFSA，通过调整度分布中某些重要度数的比例，从而提高短码长LT码的译码性能。基于原始分组k=1 000的仿真结果表明，与传统的RSD及类似方法相比，采用所提出的方法优化度分布更能有效提高短码长LT码的编译码效率和译码成功率。

参考文献

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

徐大专,邵汉钦,张小飞,等.数字喷泉码及网络喷泉码的最新进展[J].数据采集与处理, 2014, 29(3): 351⁃359.

Xu Dazhuan, Shao Hanqin, Zhang Xiaofei, et al. Recent research progress on digital fountain codes and network fountain codes[J]. Journal of Data Acquisition and Processing, 2014, 29(3): 351⁃359.

Chen S, Yao C, Dai R. The design of a rateless channel coding scheme for deep⁃space communication[C]//New Technologies, Mobility and Security (NTMS), 2015 7th International Conference on.

[S.l.]: IEEE, 2015: 1⁃5.

易本顺,姚渭箐.LT码度分布改进及在认知无线电链路保持中的应用[J].通信学报, 2018, 39(4): 76⁃83.

Yi Benshun, Yao Weiqing. The degree distribution optimization for LT codes and its application in link maintenance of cognitive radio [J]. Journal on Communications, 2018, 39(4): 76⁃83.

Nessa A, Kadoch M. Joint network channel fountain schemes for machine⁃type communications over LTE⁃advanced[J]. IEEE Internet of Things Journal, 2016, 3(3): 418⁃427.

Anglano C, Gaeta R, Grangetto M. Exploiting rateless codes in cloud storage systems[J]. IEEE Transactions on Parallel and Distributed Systems, 2015, 26(5): 1313⁃1322.

Luby M. LT codes[C]//Proc of the 43rd Annual IEEE Symposium on Foundations of Computer Science. Vancouver, Canada: IEEE, 2002: 271⁃280.

黄诚. 喷泉码理论与若干关键技术研究[D]. 武汉：武汉大学, 2010.

Huang Cheng. Research on theory and key technique of fountain codes[D]. Wuhan: Wuhan University, 2010.

黄诚, 易本顺, 吴雄斌, 等. 短码长 LT 码的蚁群算法度分布优化[J]. 北京邮电大学学报, 2010, 33(6): 129⁃133.

Huang Cheng, Yi Benshun, Wu Xiongbin, et al. The degree distribution optimization of short code length LT codes using ant colony algorithm[J]. Journal of Beijing University of Posts and Telecommunications, 2010, 33(6): 129⁃133.

Zhang M, Lei W, Xie X. Combined degree distribution: A simple method to design the degree distribution of fountain codes[C]//Proc of Information Science and Technology (ICIST), 2013 International Conference on. Yangzhou, China: IEEE, 2013: 1089⁃1092.

Jafarizadeh S, Jamalipour A. An exact solution to degree distribution optimization in LT codes[C]//Proc of Wireless Communications and Networking Conference (WCNC), 2014 IEEE. Istanbul, Turkey: IEEE, 2014: 764⁃768.

Yao W Q, Yi B S, Li W Z, et al. CPRSD for LT codes[J]. IET Communications, 2016, 10(12): 1411⁃1415.

Etesami O, Shokrollahi A. Raptor codes on binary memoryless symmetric channels[J]. Information Theory, IEEE Transactions on, 2006, 52(5): 2033⁃2051.

Karp R, Luby M, Shokrollahi A. Finite length analysis of LT codes[C]//Proc of Information Theory, 2004. ISIT 2004. Proceedings International Symposium on. Chicago, USA: IEEE, 2004: 39.

李晓磊, 邵之江, 钱积新. 一种基于动物自治体的寻优模式：鱼群算法[J]. 系统工程理论与实践, 2002, 22(11): 32⁃38.

Li Xiaolei, Shao Zhingjiang, Qian Jixin. An optimization mode based on autonomous: Fish⁃swarm algorithm[J]. Systems Engineering Theory and Practice, 2002, 22(11): 32⁃38.

您是本站第访问者

通信地址：南京市御道街29号南京航空航天大学(明故宫校区)

邮编：210016 传真：025-84892742

电话：025-84892742 E-mail：sjcj@nuaa.edu.cn

技术支持：北京勤云科技发展有限公司

一种LT码度分布优化方法 PDF

摘要

关键词

引 言

1 LT码及度分布

1.1 LT码编译码过程

1.2 度分布

1.3 度分布重要特性