光电工程  2020, Vol. 47 Issue (3): 190623      DOI: 10.12086/oee.2020.190623     
无线光通信中喷泉码的发展现状与展望
吴一 , 刘宏展 , 郝源 , 刘丽媛     
华南师范大学信息光电子科技学院,广东省微纳光子功能材料与器件重点实验室,广东 广州 510006
摘要:无线光通信信道复杂多变,喷泉码作为一种新兴的无速率编码无需信道的先验信息即可实现不同信道环境下的自适应传输,与传统编码相比更能提升无线传输的质量。本文首先总结了喷泉码应用于无线光通信的优势以及国内外喷泉码的发展现状,然后深入研究了两类喷泉码编码方案的设计以及对喷泉码性能影响重大的度分布函数的设计,总结了一种喷泉码即(LT)码的译码方法以及近些年不断提出优化的方案,同时指出了喷泉码设计中亟需解决的关键难点,最后提出了喷泉码应用于无线光通信的必要技术和探索方向。
关键词无线光通信    喷泉码    无速率编码    度分布函数    
Development and prospect of fountain codes in optical wireless communication
Wu Yi, Liu Hongzhan, Hao Yuan, Liu Liyuan     
Guangdong Provincial Key Laboratory of Nanophotonic Functional Materials and Devices, School of Information and Optoelectronics, South China Normal University, Guangzhou, Guangdong 510006, China
Abstract: The optical wireless communication channel is complex and changeable. Fountain codes as an emerging rateless coding can achieve adaptive transmission in different channel environments without a priori information of the channel. Compared with traditional coding, it can improve the quality of wireless transmission. In this paper, we first summarize the advantages of fountain codes applied to optical wireless communication and the domestic and foreign researches on the development status of fountain codes. Then we deeply study the design of two kinds of fountain codes coding schemes, as well as the degree distribution function which has significant influence on the performance of fountain code. Soon we put forward one kind of fountain codes, namely Luby transform (LT) codes, and introduce the optimization schemes in recent years. Meanwhile, the key difficulties that need to be solved in the fountain codes design are pointed out. Finally, the necessary technologies and explorations direction of fountain codes for wireless optical communication are proposed.
Keywords: optical wireless communication    fountain codes    rateless coding    degree distribution function    

1 引言

无线光通信(Optical wireless communication,OWC)是一种新兴的视距传输技术,与传统射频(radio frequency,RF)通信相比,具有保密性好、带宽高、信道容量大以及无需频率请求等优点。但是,由于激光信号在大气中传输易受到大气湍流等效应的影响,易产生光束漂移,强度起伏等问题,使得无线光通信中光束传输质量降低,严重影响了OWC系统的性能[1]

无线光通信信道复杂多变,受天气、海拔等条件影响较大,传统的线性分组码、卷积码、极化码等编码方法往往采用事先确定好的码率传输,在受到信道条件不规律变化的影响时,会使得译码端复杂度高,并造成较高的误码率和通信时延; 并且,在大气条件较好时,若采用较低的发射功率与较低码率编码方案,又会影响通信效率,使其无法充分利用无线光通信中丰富的信道资源[2],考虑到喷泉码的诸多特性,将其应用于无线光通信具有一定的研究意义。

喷泉码最初在解决大规模数据可靠性传输和广播或者多播快速传输的问题中被提出。与传统信道编码相比,喷泉码由于其码率不固定的特性更加适合无线光通信[3],其本身可以利用信道估计和译码端信噪比估计等算法,估计大气信道的衰落特性,然后利用喷泉码的译码累积分布函数动态调整码率和发射机发射功率,根据信道的变化自动改变编码方式,用来提高无线光通信的有效性,甚至在信道反馈或者信道估计不准确时也能一定程度上保证通信质量。喷泉码具有广阔的应用前景,目前已被DVB-H和3GPP TS等国际标准采用[4]

本文介绍了喷泉码的优势以及目前国内外发展现状,综述了已经提出的两类实用喷泉码的度分布函数的设计以及不同的译码方案,归纳了前人对喷泉码性能不断优化的方案,同时指出了喷泉码应用于无线光通信中需要解决的一些关键问题,最后对喷泉码在无线光通信领域的发展前景和研究方向进行了展望。

2 喷泉码的优势和发展现状

传统的前向纠错(forward error correction,FEC)方式需要预先估计信道状态信息,并根据实际情况选择合适的编码长度及码字,通常在OWC系统中,信道质量因为天气的变化区别较大,故需要多次重复设计编码方案,这样大大增加了系统的复杂度[5]

除此之外,无线通信下大规模MIMO(multiple input multiple output)系统可以引入喷泉码,不同的接收端可以根据处理能力和信道条件自主选择接收合适数量的编码包,一旦完全恢复了原始信息就停止接收,不同接收端不会相互影响,有效地降低了MIMO系统的复杂度。喷泉编码器产生的不同编码数据包之间相互独立且完全等价,能否译码成功仅仅取决于接收到编码包的数量,与接收到编码包种类和顺序无关[6]。由于无线光通信系统在恶劣天气条件下通常会通信中断,利用喷泉码的特性,在接收端叠加累积译码,可以在高中断概率的条件下得到比较好的效果,也可以有效解决断点续传和异步接入带来的复杂度问题。而且一旦成功译码,接收端只需给发送端一个反馈信号,从而避免了传统线性分组码的复杂反馈过程带来的“反馈风暴”问题[7]

基于以上优势,喷泉码在被提出后的二十多年来受到了广泛的关注[8]。目前的研究主要集中于编码方式的选择[9]、度分布的设计与优化、译码算法的设计、与具有高纠错能力的编码级联[10-12]、利用不等差错理论[13]实现高质量传输以及喷泉码理论在数据传输,深空通信和云存储等场景的实际应用拓展[14]

表 1介绍了喷泉码的研究现状。在国内的研究中,2017年,重庆理工大学的张勋课题组研究了在2×2的MIMO_FSO系统中,用Gamma-Gamma模型模拟大气湍流信道下基于修正转移鲁棒孤子度分布(ISRSD)[15]的LT码与传统LDPC码的性能比较。使用改进的LT码能够在强湍流条件下,误码率为10-6时获得2.2 dB的编码增益,同样误码率情况下,在弱湍流条件下获得0.9 dB的编码增益。随后,又研究了鲁棒泊松度分布(PRSD)下的LT码在3×3 MIMO-FSO的性能。在强湍流条件下,误码率为10-6时,采用PRSD度分布的LT码比RSD获得了1 dB的编码增益; 弱湍流条件下,同样误码率下,采用PRSD的LT码比RSD获得了0.4 dB的编码增益。以上成果研究了喷泉码及其改进方案,对优化无线光通信质量大有裨益[15]

表 1 国内外喷泉码的研究进展 Table 1 Research progress of fountain codes abroad
年份 研究者 研究进展
1998 Byers和Luby 首次提出了数字喷泉的概念[7]
2002 Luby 提出了第一种实用的喷泉码—LT(Luby Transform)码
2004 Shokrollahi 构造了具有线性时间复杂度的Raptor码
2005 Luby和Shokrollahi 成立了数字喷泉公司,提出的多项方案成为了3GPP多媒体广播业务的标准方案
2006 Puducherry 提出了分布式编码方案及其性能[16-17]
2007 Hyytia 研究了短码长下LT码度分布的优化设计[18]
2009 Sejdinovic 利用加窗的方式构造了具有不等差错保护特性的喷泉码[19]
2009 Bioglio 提出了即时高斯消元法(OFG)译码算法降低了译码复杂度和译码时延[20]
2012 Sorensen 研究了在AWGN信道下LT码ripple的设计[21]
2015 雷维嘉 提出了修正二进制-鲁棒孤子分布
2016 姚伟清 提出了鲁棒泊松度分布[22]
2017 牛芳琳 提出了基于部分信息度分布构造喷泉码的方法
2017 张勋 比较了转移鲁棒孤子分布下LT码与LDPC码性能[23]
2018 曹阳 将LT码与奇偶校检码级联降低了MIMO系统误码扩散的问题[24]
3 喷泉码的原理与分类

喷泉码可以形象地表示为图 1,这里编码器为一个喷泉源,喷泉源向外面随机地喷洒水珠(编码包),接收水桶即为译码器,目的是接到足够的水(完成译码)。“水桶”不关心水从哪里来,如果某次检查发现水不够(译码失败),则继续接水珠(编码包),直到解渴(完成译码)[25-27]

图 1 喷泉码原理示意图 Fig. 1 Schematic diagram of fountain code principle

图 2介绍了上述喷泉码编码器和译码器的原理,首先编码器对数据进行分割,进行异或操作得到源源不断的数据包; 然后译码器接收到编码器产生的源源不断的数据包,对数据包进行处理恢复出原始数据[28]

图 2 (a) 喷泉码的编码器原理;(b)喷泉码的译码器原理 Fig. 2 (a) Coding principle of fountain code; (b) Decoding principle of fountain code

从理论上来看,喷泉码的编码器和译码器仍有一些细节需要考虑:

编码器:1)需要预先设定相应的函数来保证所有的数据包都能被选择,而不会有遗漏导致译码失败; 2)在保证喷泉码译码端能译码成功条件下,译码端所需要的编码分组尽可能小,编码数据包应该尽可能简单,减少译码器的工作负担[29]

译码器:译码器选择的译码算法应该能从任意一组N(N > K)个编码数据包中恢复K个原始数据。N接近K即意味着译码开销很低,而且译码器的复杂度能够与K个原始数据有线性关系,这就是比较优良的译码器。

根据以上讨论,目前有两类受到广泛研究的喷泉码,即LT码和Raptor码。

3.1 LT码

2002年,Luby等人在喷泉码的基础上,改进了喷泉码采用随机编码的方法,第一次将度分布函数应用于喷泉码上,并构造了比较完备的度分布函数使得编码矩阵变得稀疏,而且在译码端不再使用高复杂度的高斯消元译码的方法,而是采用置信传播(BP)译码的方法,让喷泉码真正地变得实用。原始消息被分成K个信息符号$S{\rm{ = \{ }}{s_1}, {s_2}, \cdots , {s_K}{\rm{\} }}$,根据一定准则选择d个信息符号,选择的信息符号进行异或得到编码符号,称d为编码符号的度值,定义LT码的度分布函数:

$\mathit{\Omega} (x) = \sum\limits_{d = 1}^{d = {d_{\max }}} {{\mathit{\Omega} _d}} {x^d}, $ (1)

其中:dmax为最大可以选择的度值,$\mathit{\Omega} (x)$为度值d被选择的概率。

图 3,LT码的编码过程:1)根据预先选定的度分布函数随机选择一个度值d;2)从K个原始信息符号中随机选择d个符号进行异或得到一个编码符号;3)不断根据上述方法源源不断地产生编码符号。

编码过程实际上就是原始信息和编码符号建立线性关系的过程,用编码矩阵可以表示为$S{{\mathit{\boldsymbol{G}}}_{K \times N}} = Y$,其中$Y{\rm{ = \{ }}{y_1}, {y_2}, \cdots , {y_N}{\rm{\} }}$为产生的N个编码符号。图 3所示过程的编码矩阵可以表示为[30]

${{\mathit{\boldsymbol{G}}}_{K \times N}}{\rm{ = }}\left[ {\begin{array}{*{20}{c}} 1&1& \cdots &0 \\ 1&0& \cdots &0 \\ 0&0& \cdots &1 \\ \vdots & \vdots & \vdots & \vdots \\ 0&1& \cdots &1 \end{array}} \right]。$ (2)
图 3 LT码的编码过程 Fig. 3 Encoding process of LT code

式(2)的编码矩阵取决于度分布函数,度分布函数对LT码的编译码复杂度、错误平层和译码开销等有重要影响[31]。早期提出的线性喷泉码由于采用了均匀分布的度函数,编码符号的平均度值很高使其有较高的编译码复杂度,故这类喷泉码并不实用。所以设计出的一个好的度函数既要保证较低的编译码复杂度,还要实现在接收到比较少的编码符号时就可以开始译码,而且在译码迭代的过程可以持续进行,不至于找不到度值为1的编码符号而译码中断[32-33]

为了在译码迭代过程中能源源不断找到度值为1的编码数据包,同时平均度值不会明显增加。Luby在理想孤波分布基础上进行了一定的修正,提出了鲁棒孤子分布(robust soliton distribution,RSD):

$\mu (d) = \frac{{\rho (d) + \tau (d)}}{{\sum\limits_{i = 1}^K {\rho (i) + \tau (i)} }}, $ (3)
$ \tau (d) = \left\{ {\begin{array}{*{20}{c}} {\frac{R}{{d \cdot K}}}&{d = 1, 2, \cdots \left( {\frac{K}{R}} \right)}\\ {R\ln \left( {\frac{R}{\delta }} \right)}&{d = \frac{K}{R}}\\ 0&{d = \left( {\frac{K}{R}} \right) + 1, \cdots , K} \end{array}} \right., $ (4)
$ R = c\ln \left( {\frac{K}{\delta }} \right)\sqrt K。$
$ \rho (d) = \left\{ {\begin{array}{*{20}{c}} {\frac{1}{K}}&{i = 1}\\ {\frac{1}{{d(d - 1)}}}&{d = 2, 3, \cdots , K} \end{array}} \right., $ (5)

Luby在鲁棒孤子分布中引入了两个可变参数c$\delta $(c > 0,$\delta $≤1),c为常数,$\delta $为译码失败概率。这两个可变参数的加入使得在译码迭代的过程中度值更新为1的编码符号数的期望为$R = c\ln \left( {K/\delta } \right)\sqrt K $,远大于理想孤子分布的期望,保证了译码器能够以很高的概率找到度值为1的编码符号使得译码中断概率更低。故c$\delta $的选取对LT码的性能有重要影响。

图 4给出了在K=10000,$\delta $=0.05,c改变时鲁棒孤子分布的概率密度曲线。

图 4 K=10000,δ=0.05,c=0.2,0.3,0.4,0.5,0.6时RSD的概率密度分布 Fig. 4 Probability density distribution of RSD at K=10000, δ=0.05, c=0.2, 0.3, 0.4, 0.5, 0.6

图 4可以看到,改进后的RSD使得度值为1的概率有了明显的提高,同时在$d = K/R$ ($R = c\ln \left( {K/\delta } \right)\sqrt K $)处还出现了一个尖峰保证了未恢复的数据中至少有一个度值会更新为1的编码符号,使得编码符号对原始数据的覆盖率大大提升,使得译码失败的概率降低。当接收到$n = k + 2R\ln (R/\delta )$个编码符号时使得译码成功率不低于$1 - \delta $。随着c的降低,度值为1的概率会增加,同时度值尖峰会出现在更高度值的位置[34]

2016年,Yao等提出了性能更加优良的泊松鲁棒孤子分布(Poisson robust soliton distribution,PRSD)。其首先研究了泊松度分布(Poisson distribute,PD)。$P(d) = ({m^d}{{\rm{e}}^{ - m}}{\rm{)/}}d{\rm{!}}$$d = 1,2, \cdots ,K$$m$为正的常数。与RSD相比,PD产生度为1的编码符号的可能性更大,同时编码符号的平均度值会更小,PD能够在减小译码中断的可能性下降低译码复杂度。将PD与RSD结合起来得到了PRSD。

$ \theta (d) = \left\{ {\begin{array}{*{20}{c}} {\frac{1}{2}}&{d = 2}\\ {\frac{{{\lambda ^d}{{\rm{e}}^{ - \lambda }}}}{{d!}}}&{{\rm{other}}} \end{array}} \right., $ (6)
$\mathit{\Omega} (d) = \frac{{\theta (d) + \tau (d)}}{{\sum\nolimits_{d = 1}^K {\theta (d) + } \tau (d)}}, $ (7)

其中:λ为正的常数,$d = 1, 2, \cdots , K$

表 2比较了优化的PRSD和RSD的性能。

表 2 PRSD和RSD的性能对比 Table 2 Performance comparison between PRSD and RSD
输入符号 平均译码开销/(%) 平均度值 译码耗时/s
K RSD PRSD RSD PRSD RSD PRSD
500 24.27 9.42 9.50 5.76 3.81 2.17
1000 20.46 7.56 10.72 6.30 17.48 8.08
2000 16.80 5.82 11.63 6.51 47.21 25.21
3.2 Raptor码

尽管LT码作为第一种实用的喷泉码已经有了不错的性能,但其仍有两个比较大的缺点:一是LT码的编译码复杂度为$O(k\ln k) $是非线性的; 二是LT码构造过程决定了其误码平层(error floor)较高,将其直接应用于复杂的信道环境并不现实。基于这两点,2004年,Shokrollahi将线性分组码(LDPC码,Turbo码等)与LT码级联,构造了全新的喷泉码—Raptor(rapid tornado code)码,即快速龙卷风码。与LT码相比,Raptor码的译码复杂度进一步降低为O(k),从而可以实现线性时间编译码,同时具有比较低的误码平层,可以在复杂环境下更好地保护数据,使得喷泉码的应用场景得到了很大的拓展。Raptor码通常以高码率的LDPC码作为外码,具有不固定码率的LT码作为内码。

编码过程:1) LDPC码编码:将K个原始符号进行LDPC码编码,编为码长为N的LDPC码码字,即预编码过程; 2) LT码编码:将上述过程产生的LDPC码编码码字作为LT码的输入符号进行LT码编码,产生的LT编码输出符号即为Raptor码的编码符号。

在RSD度分布的LT码中,编码符号的平均度值$\ln K$随着源符号的增加而增加,高度值的编码符号对源符号有了更好的覆盖,方便接收端不遗漏地译出所有源符号。但是高度值的编码符号使得译码复杂度迅速提升,同时低度值编码符号比例的降低使得译码中断概率更高,在源符号长度很高的情况下,这种现象影响更加严重。Shokrollahi提出了编码符号平均度值与源符号K无关的度分布函数${\mathit{\Omega} _d}(x)$

${\mathit{\Omega} _d}(x) = \frac{1}{{\mu + 1}}\left( {\mu x + \sum\limits_{i = 2}^D {\frac{{{x^i}}}{{i(i - 1)}}} + \frac{{{x^{D + 1}}}}{D}} \right), $ (8)

其中:$D{\rm{ = }}[4(1 + \varepsilon )/\varepsilon ]$为最大度值,$\mu {\rm{ = }}\varepsilon {\rm{/2 + (}}\varepsilon {\rm{/2}}{{\rm{)}}^{\rm{2}}}$$\varepsilon $为译码开销。这种度分布函数降低了编码符号的平均度值使得LT码译码复杂度更低,而且在译码迭代过程中,度值更新为1的编码符号增加,使得译码中断的概率降低。同时,由于低度值的编码符号增多使得其对源符号的覆盖率降低,少部分源符号为参与编码而无法被成功译码,因此,Raptor码在LT码基础上级联了一个线性分组码作为外码,先将源信息进行预编码再将外码的码字作为LT码的输入。虽然部分外码码字由于上述原因没有参与LT编码而无法被译出,但借助外码LDPC码的纠错能力可以恢复这一部分码字,进而对这一缺陷进行了弥补。

Shokrollahi结合了码长来考虑了度分布的设计,得到了Raptor码在有限码长下的度分布设计准则,如表 3所示。

表 3 不同码长下优化出Raptor码的度分布 Table 3 Optimizing the degree distribution of Raptor codes under different code length
K 65536 80000 100000 120000
Ω1 0.007969 0.007544 0.006495 0.004807
Ω2 0.493570 0.493610 0.495044 0.496472
Ω66 0.03135 0.010479 0.016298 0.009100
Ω67 \ 0.017365 0.010777 \
ε 0.038 0.035 0.028 0.02
α 5.87 5.91 5.85 5.83

其中以码长K=65536为例:

Shokrollahi结合了码长来考虑了度分布的设计,得到了Raptor码在有限码长下的度分布设计准则,如表 3所示。

其中以码长K=65536为例:

$ \begin{array}{l} {\mathit{\Omega} _{\rm{1}}}(x) = 0.007967x + 0.493570{x^2} + \cdots \\ + 0.025023{x^{65}} + 0.003135{x^{66}} \end{array}, $ (9)

Raptor码与LT码相比拥有线性时间复杂度,并且其错误平层很低可以对信息进行较好的保护非常适合于在复杂差错环境下传输数据。目前,有两类Raptor码被广泛应用和研究,即R10(Raptor10)码和RQ(RaptorQ)码。R10码已经被多个国际化标准组织使用,如3GPP(3rd Generation Partnership Project),DVB-H(Digital Video Broadcasting-Handheld)和IETF(Internet Engineering Task Force)。作为FEC的传输方案,R10码适合于中等长度数据块,应用于移动广播等对数据保护要求不高的场合,RQ码适合于目前无线光通信等复杂环境的大规模数据传输且需要较高精确度的场合。

3.3 喷泉码的译码

3.2中介绍的Raptor码是LDPC码和LT码级联得到的,故译码过程为先对LT码进行译码再进行LDPC码译码。故这里着重介绍LT码在BEC信道和AWGN信道下的译码方法[35]

3.3.1 LT码在二进制删除信道下的BP译码

首先假设信息符号为$S{\rm{ = \{ }}{s_1}, {s_2}, \cdots , {s_K}{\rm{\} }}$,译码器接收到的N个编码符号为$Y{\rm{ = \{ }}{y_1}, {y_2}, \cdots , {y_N}{\rm{\} }}$

1) 在编码符号集Y中寻找一个度为1的编码符号yi,假设在二分图上编码符号yi与原始符号si相连;

2) 直接令si=yi,并在二分图上一出siyi相连的边;

3) 找到与si相连的所有编码符号${y'_i}$,令${y'_i} = {y'_i} \oplus {y_i}$,同时在二分图上删除si${y'_i}$的边;

4) 重复上述步骤,直到原始符号S被全部译出,或者在迭代的过程中找不到度为1的编码符号。

图 6给出了一个BP译码的流程接收到的编码符号集为$Y{\rm{ = \{ 1, 0, 0, 1, 1\} }}$,最终译出原始符号集为$S{\rm{ = \{ 1}}, 1, 0, 1{\rm{\} }}$。从图 6可以看出,只要在迭代过程中能够找到度值为1的编码符号,就能够利用计算机方便实施的异或操作来更新对应的编码符号使得迭代继续。BP是一种低复杂度的次优算法,译码的复杂度为$O(K\ln K)$。给出的示例图 6说明了LT码的BP译码很容易找不到度为1的编码符号集而译码中断,故设计出一个好的度分布对于LT码的性能有至关重要的影响[36]

图 5 Raptor的编码过程 Fig. 5 Encoding process of Raptor code

图 6 LT码的BP译码方法 Fig. 6 BP decoding method for LT codes

2012年Chong等人提出了一种设计简单的短消息喷泉码(short message fountain codes),能够在理想的信道下,到删除率为0.5的删除信道下以较低的效率成功译码。Huang等人研究了带有消息传递(message passing,MP)和最大似然(maximum likelihood,ML)解码算法的喷泉码在删除信道下的性能,证明了MP算法能够在中长码长下有较高的译码效率,对于短码长MP算法会带来较大的译码开销,在此基础上提出了针对于短码长消息的混合消息传递和快速最大似然译码方法。

3.3.2 高斯消元法译码

在删除信道下,LT码的高斯消元法(Gaussian elimination,GE)实际上对$S{{\mathit{\boldsymbol{G}}}_{K \times N}} = Y$求解线性方程组恢复S。本质上是通过高斯消元法来求解线性方程组。即${(S{{\mathit{\boldsymbol{G}}}_{K \times N}})^{\rm{T}}} = {Y^{\rm{T}}}$,假设${\mathit{\boldsymbol{x}}} = {S^{\rm{T}}}$${\mathit{\boldsymbol{A}}} = {{\mathit{\boldsymbol{G}}}^{\rm{T}}}$${\mathit{\boldsymbol{b}}} = {Y^{\rm{T}}}$,则构造了${\mathit{\boldsymbol{Ax}}} = {\mathit{\boldsymbol{b}}}$的形式通过构造增广矩阵,上三角化,回代等操作即可恢复出原始信息。

运用高斯消元译码不需要BP译码中寻找度为1的过程,只需要生成矩阵和增广矩阵的秩等于信息符号数目就可以利用高斯消元译码的方法恢复出原始信息。高斯消元译码中涉及的复杂矩阵上三角化和回代求解等操作是一种复杂度为$O({K^3})$的方法,与BP译码方法相比,高斯消元算法在源码长增加的情况下可以以比较小的译码开销恢复原始信息但是其译码复杂度会急剧增加,在无线光通信等长距离传输中会带来严重的通信时延。图 7模拟了LT码的BP和GE译码算法在不同码长下的性能,在码长较短情况下BP译码的误码平层很高,采用GE译码的方法能改善其一定的性能,随着码长的增加,这两类译码方法的性能也显著提升。

图 7 LT码的BP译码和GE译码在不同码长K下的性能 Fig. 7 Performance of BP and GE decoding of LT codes under different code length K

2008年Kim等人提出了增量高斯消元法(incremental Gaussian elimination,IGE)[37]译码在Raptor中的应用,根据GE在上三角化失败后矩阵部分仍为上三角的原理,在译码效率不变的情况下优化了GE的译码时间,减少了通信时延。2009年Bioglio等人提出了即时高斯消元(on the fly Gaussian elimination,OFG)译码算法,将上三角化所需的运算量分布到编码符号接收的整个过程中,将译码复杂度降低到了$O({K^2})$[20]

3.3.3 LT码在有噪信道下的译码

最初喷泉码的提出是基于删除信道下的,所以在有噪信道下LT码的BP译码和GE译码会更复杂。2006年Etesami和Shokrollahi等人在一般噪声二进制输入无记忆对称(binary input has no memory symmetric,BIMS)信道下利用BP译码更新的算法研究了喷泉码的性能[38]。Palanki论述了在有噪信道中考虑到译码速率和复杂性,在接收到一定数量编码符号后应当继续接收还是译码的问题[39]。Jenkac提出了在译码端设计一个度量使得有足够的编码数据被接收到时再开始译码。论证了喷泉码采用增量解码方案时,若小于最大译码迭代次数,译码器在译码尝试时进行等待操作,接收到一定编码数据才进行译码[40]。Castura等人研究了在块衰落信道中,喷泉码解码时间的分布[41]。比较流行的算法是Jenkac和Palanki等人给出了LT码在AWGN信道下的软判决译码算法先验似然对数比算法:

$L(x|y) = \log (P(X = 0|y){\rm{)}} - \log (P(X = 1|y){\rm{) = 2}}y{\rm{/}}{\sigma ^{\rm{2}}},$

${\sigma ^{\rm{2}}}$为信道噪声的方差。考虑到噪声信道下解码算法与删除信道的不同,Auguste等人根据噪声信道的特点重新设计了喷泉码的度分布[42]。2009年Liu等人讨论了中继网络中基于喷泉码的中继协议,喷泉码无速率码的特性非常适合在深空通信的衰落信道中,他们设计了几种无速率的中继协议并且在缓慢且深交织的衰落信道中结合16QAM仿真了Raptor的性能[43]。2012年Yuan优化了最小和(min-sum,MS)算法,提出了归一化MS算法和偏移MS算法来作为高斯信道下喷泉码的译码算法,并且通过高斯近似的算法分析了喷泉码在各个译码算法下的性能,优化了两种MS算法的参数。2017年,Subhagya等人将LT码应用于无线多媒体传感器网络,运用LT码产生潜在的无限冗余的数据包,接收节点利用这些数据包恢复原始数据,得到了比利用传统RS码更为优良的结果[44]。Borkotoky等人研究了在多跳分组无线网络中的喷泉码,并结合实际无线广播情况设计了更加高效的度分布函数[45]。2018年,Spencer等人研究了具有强鲁棒性的四进制喷泉码,并结合AWGN干扰信道证明了该喷泉码的良好性能[46]。徐大专课题组提出了一种从点对点AWGN信道扩展到AWGN MACS上的系统LT码的度分布模型,通过仿真证实了这种模型在实际MACS网络中这种度分布更优秀。2019年何继光等人分析了在AWGN信道下多源、单中继和单目的地网络的分布式LT码的误码平层,提出一种在信源处的新的协作方案,即在信源编码的过程和中继合并方案进行了协调得到了比传统方案性能更好的分布式LT码[47]

4 总结和展望

目前喷泉码的研究已经取得不小的成功,但目前喷泉码的研究大部分停留在理论研究和实验仿真上。喷泉码灵活多变的特性在未来的无线光通信领域有重大的应用前景,目前喷泉码亟需解决的问题有:

1) 需要借助概率论等工具从理论上分析LT码中RSD的本质原因。在源数据K较大时,选用RSD的LT码有良好的性能,目前需要设计出在短码长条件下LT码性能优良的度分布。5G通信要求的高速、低时延,使得短码长在日后有重大的应用前景,所以短码长的Raptor码的性能也是亟需改善的。

2) 喷泉码本身的误码平层高于普通的线性分组码,在应用于信噪比较低的无线光通信下时会带来非常大的误差,所以优化喷泉码的误码平层构造性能更加优良的Raptor码也是未来的研究重点。

研究喷泉码与其它信道编码(如Turbo码,卷积码等)级联时的性能,以及特点级联方案优化的译码方法。将喷泉码的研究拓展到更多的信道,并对不同的信道应当由新的译码方案被提出。

3) 喷泉码在无线光通信领域的应用受到了广泛的研究。在OWC领域,将自适应技术与喷泉码相结合可以大大提高OWC系统的传输效率,充分利用频带资源; 目前喷泉码应用于OWC系统的重点在于信道估计,经典的无线通信信道估计策略并不完全适合于光通信场景,所以需要设计出借助光信号对大气信道时刻变化的大气湍流、大气衰减等效应以及在深空通信中对太阳光闪烁等效应进行估计。在实际工程应用中,如何利用自适应技术来动态调整发射接收设备的相关设置,在实际信道中提升OWC系统的性能,都是发展潜力较大的领域。

参考文献
[1]
Xu G L, Zhang X P, Xu W H, et al. Free space optical communication[J]. Optoelectronic Technology, 2002, 22(4): 198-205.
许国良, 张旭苹, 徐伟弘, 等. 自由空间光通信[J]. 光电子技术, 2002, 22(4): 198-205 [Crossref]
[2]
Hayajneh K F, Yousefi S. Overlapped LT codes over the binary erasure channel: analysis and design[J]. IET Communications, 2019, 13(16): 2567-2572. [Crossref]
[3]
Xu D Z, Xu S K, Hua J, et al. Recent progress on optimization design of degree distributions in digital fountain codes[J]. Journal of Data Acquisition and Processing, 2015, 30(4): 733-746.
徐大专, 许生凯, 华洁, 等. 数字喷泉码度分布优化设计的最新研究进展[J]. 数据采集与处理, 2015, 30(4): 733-746 [Crossref]
[4]
Xiong K, Zhang Y, Fan P Y, et al. Evaluation framework for user experience in 5G systems: on systematic rateless-coded transmissions[J]. IEEE Access, 2016, 4: 9108-9118. [Crossref]
[5]
Luby M. LT codes[C]//Proceedings of the 43rd Annual IEEE Symposium on Foundations of Computer Science, 2002: 271-280.
[6]
Byers J W, Luby M, Mitzenmacher M. A digital fountain approach to asynchronous reliable multicast[J]. IEEE Journal on Selected Areas in Communications, 2002, 20(8): 1528-1540. [Crossref]
[7]
Luby M G, Mitzenmacher M, Shokrollahi M A, et al. Practical loss-resilient codes[C]//Proceedings of the Twenty-Ninth Annual ACM Symposium on Theory of Computing, 1997: 150-159.
[8]
Mirrezaei S M, Faez K, Yousefi S. Towards fountain codes[J]. Wireless Personal Communications, 2014, 77(2): 1533-1562. [Crossref]
[9]
Byers J W, Luby M, Mitzenmacher M. A digital fountain retrospective[J]. ACM SIGCOMM Computer Communication Review, 2019, 49(5): 82-85. [Crossref]
[10]
Palanki R, Yedidia J S. Rateless codes on noisy channels[C]//Proceedings of International Symposium onInformation Theory, 2004: 37.
[11]
Castura J, Mao Y. Rateless coding over fading channels[J]. IEEE Communications Letters, 2006, 10(1): 46-48. [Crossref]
[12]
Jiao J, Qinyu Z, Hui L. Design of Concatenated Fountain Code in Deep Space Communication[C]// 5th International Conference on Wireless Communications, Networking and Mobile Computing, IEEE, 2009.
[13]
Rahnavard N, Vellambi B N, Fekri F. Rateless codes with unequal error protection property[J]. IEEE Transactions on Information Theory, 2007, 53(4): 1521-1532. [Crossref]
[14]
Wu G, Yang C Y, Li S Q, et al. Recent advances in energy-efficient networks and their application in 5G systems[J]. IEEE Wireless Communications, 2015, 22(2): 145-151. [Crossref]
[15]
Zhang X, Cao Y, Peng X F, et al. Performance analysis of LT codes in MIMO-FSO system[J]. Laser Journal, 2017, 38(3): 61-64.
张勋, 曹阳, 彭小峰, 等. MIMO-FSO系统中LT码的性能分析[J]. 激光杂志, 2017, 38(3): 61-64 [Crossref]
[16]
Puducheri S, Kliewer J, Fuja T E. Distributed LT codes[C]//Proceedings of 2006 IEEE International Symposium on Information Theory, 2006: 987-991.
[17]
Puducheri S, Kliewer J, Fuja T E. The design and performance of distributed LT codes[J]. IEEE Transactions on Information Theory, 2007, 53(10): 3740-3754. [Crossref]
[18]
Hyytia E, Tirronen T, Virtamo J. Optimal Degree Distribution for LT Codes with Small Message Length[C]// INFOCOM 2007. 26th IEEE International Conference on Computer Communications, 2007.
[19]
Sejdinovic D, Vukobratovic D, Doufexi A, et al. Expanding window fountain codes for unequal error protection[J]. IEEE Transactions on Communications, 2009, 57(9): 2510-2516. [Crossref]
[20]
Bioglio V, Grangetto M, Gaeta R, et al. On the fly gaussian elimination for LT codes[J]. IEEE Communications Letters, 2009, 13(12): 953-955. [Crossref]
[21]
Sorensen J H, Koike-Akino T, Orlik P, et al. Ripple design of LT codes for BIAWGN channels[J]. IEEE Transactions on Communications, 2014, 62(2): 434-441. [Crossref]
[22]
Yao W Q, Yi B S, Huang T Q, et al. Poisson robust soliton distribution for LT codes[J]. IEEE Communications Letters, 2016, 20(8): 1499-1502. [Crossref]
[23]
Zhang X. Research on fountain code and its cascade over atmospheric laser communication[D]. Chongqing: Chongqing University of Technology, 2018.
张勋.大气激光通信中喷泉码及其级联码技术研究[D].重庆: 重庆理工大学, 2018.
[24]
Cao Y, Zhang X, Peng X F, et al. Cascade scheme based on multiple-input multiple-output in spatial optical communication[J]. Acta Optica Sinica, 2018, 38(1): 0106003.
曹阳, 张勋, 彭小峰, 等. 空间光通信中基于多输入多输出的级联码方案研究[J]. 光学学报, 2018, 38(1): 0106003 [Crossref]
[25]
Lázaro F, Liva G, Bauch G. Inactivation decoding of LT and Raptor codes: analysis and code design[J]. IEEE Transactions on Communications, 2017, 65(10): 4114-4127.
[26]
Byers J W, Luby M, Mitzenmacher M, et al. A digital fountain approach to reliable distribution of bulk data[C]//Proceedings of the ACM SIGCOMM '98 Conference on Applications, Technologies, Architectures, and Protocols for Computer Communication, 1998: 56-67.
[27]
MacKay D J C. Fountain codes[J]. IEE Proceedings Communications, 2005, 152(6): 1062-1068. [Crossref]
[28]
Liang M S, Duan J J, Zhao D F. Optimal redundancy control strategy for fountain code-based underwater acoustic communication[J]. IEEE Access, 2018, 6: 69321-69334. [Crossref]
[29]
MacKay D J C. Information Theory, Inference, and Learning Algorithms[M]. Cambridge: Cambridge University Press, 2003.
[30]
Li G T, Wu H K, Lee H C, et al. Systematic physical-layer raptor coding to attain low decoding complexity[J]. IEEE Communications Letters, 2018, 22(6): 1124-1127. [Crossref]
[31]
Karp R, Luby M, Shokrollahi A. Finite length analysis of LT codes[C]//Proceedings of International Symposium on Information Theory, 2004: 39.
[32]
Di C Y, Proietti D, Telatar I E, et al. Finite-length analysis of low-density parity-check codes on the binary erasure channel[J]. IEEE Transactions on Information Theory, 2002, 48(6): 1570-1579. [Crossref]
[33]
Xu S K, Xu D Z. Design of degree distributions for finite length LT codes[J]. Wireless Personal Communications, 2018, 98(2): 2251-2260. [Crossref]
[34]
Abbas R, Shirvanimoghaddam M, Huang T, et al. Novel design for short analog fountain codes[J]. IEEE Communications Letters, 2019, 23(8): 1306-1309. [Crossref]
[35]
Huang W Z. Investigation on digital fountain codes over erasure channels and additive white Gaussian noise channels[D]. Columbus: Ohio University, 2012.
[36]
Khonsari H, Okpotse T, Valipour M, et al. Analysis of ripple size evolution in the LT process[J]. IET Communications, 2018, 12(14): 1686-1693. [Crossref]
[37]
Kim S, Ko K, Chung S Y. Incremental Gaussian elimination decoding of raptor codes over BEC[J]. IEEE Communications Letters, 2008, 12(4): 307-309. [Crossref]
[38]
Etesami O, Shokrollahi A. Raptor codes on binary memoryless symmetric channels[J]. IEEE Transactions on Information Theory, 2006, 52(5): 2033-2051. [Crossref]
[39]
Palanki R. Iterative decoding for wireless networks[D]. Pasadena, California: California Institute of Technology, 2004.
[40]
Castura J, Mao Y Y. When is a message decodable over fading channels?[C]//Proceedings of the 23rd Biennial Symposium on Communications, 2006: 59-62.
[41]
He J G, Hussain I, Li Y, et al. Distributed LT codes with improved error floor performance[J]. IEEE Access, 2019, 7: 8102-8110. [Crossref]
[42]
Auguste, Poulliat C, Declercq D. Jointly Decoded Raptor Codes: Analysis and Design for the BIAWGN Channel[J]. EURASIP Journal on Wireless Communications and Networking, 2009, 2009: 1-11. [Crossref]
[43]
Liu X, Lim T J. Fountain codes over fading relay channels[J]. IEEE Transactions on Wireless Communications, 2009, 8(6): 3278-3287. [Crossref]
[44]
Subhagya A A M, Kaythry P, Kishore R. LT code based forward error control for wireless multimedia sensor networks[C]//Proceedings of 2017 International Conference on Wireless Communications, Signal Processing and Networking, 2017: 1612-1616.
[45]
Borkotoky S S, Pursley M B. Fountain-coded broadcast distribution in multiple-hop packet radio networks[J]. IEEE/ACM Transactions on Networking, 2019, 27(1): 29-41. [Crossref]
[46]
Spencer J, Hayajneh K F, Yousefi S. Robust quaternary fountain codes in AWGN interference[J]. IET Communications, 2018, 12(20): 2561-2567. [Crossref]
[47]
Deng D C, Xu D Z, Xu S K. Optimisation design of systematic LT codes over AWGN multiple access channel[J]. IET Communications, 2018, 12(11): 1351-1358. [Crossref]