宋鑫 廖育榮 丁丹

摘 ?要： 無速率碼的出現(xiàn)為自適應(yīng)數(shù)據(jù)傳輸提供了新途徑。作為第一種實(shí)用的無速率碼，LT碼在高斯信道中的性能不佳，存在較高的誤碼平臺。針對此問題，提出一種選擇編碼（SE）算法。SE算法按照度數(shù)值大小將信息節(jié)點(diǎn)分類成若干個集合，并通過控制編碼過程使每個校驗(yàn)節(jié)點(diǎn)優(yōu)先從小度數(shù)值節(jié)點(diǎn)集合中選取與之相連接的信息節(jié)點(diǎn)，從而消除了小度數(shù)值的信息節(jié)點(diǎn)，降低了LT碼的誤碼平臺。通過蒙特卡洛仿真得到不同條件下SE算法中信息節(jié)點(diǎn)的度分布，并利用外信息傳遞圖法對SE算法及傳統(tǒng)編碼方法的收斂性進(jìn)行對比分析，結(jié)果顯示SE算法能夠進(jìn)一步拓寬譯碼通道，使誤比特率更快趨近于0。此外，SE算法在給定范圍信噪比及碼率值條件下均能降低誤碼平臺，當(dāng)誤比特率為10-5時，碼長為512 bit的LT碼可以得到近5 dB的性能改善。

關(guān)鍵詞： 信道編碼; LT碼; 高斯信道; 編碼算法; 外信息傳遞; 收斂性

中圖分類號： TN911.22?34 ? ? ? ? ? ? ? ? ? ?文獻(xiàn)標(biāo)識碼： A ? ? ? ? ? ? ? ? ? ? ? ?文章編號： 1004?373X（2019）12?0001?06

Abstract： The emergence of the rateless code provides a new way for adaptive data transmission. As the first practical rateless code， the LT code has a poor performance and high error floor in the Gaussian channel. Therefore， a selective encoding （SE） algorithm is proposed. In accordance with the degree values， information nodes are sorted into several sets by the SE algorithm. The encoding process is controlled to enable each check node to preferentially select the information node connecting with it from the small degree node sets， so as to eliminate small degree information nodes and decrease the error floor of the LT code. The degree distributions of information nodes in the SE algorithm under different conditions are obtained by the Monte-Carlo simulation. The convergences of the SE algorithm and conventional encoding algorithm were compared and analyzed by using the extrinsic information transfer （EXIT） chart method. The results demonstrate that the SE algorithm can further expand the decoding channel， make the error bit rate approach zero faster， decrease the error floor with a given range of SNRs and bit rate values， and make the LT code of 512 bit length achieve performance improvement of about 5 dB when the error bit rate is 10-5.

Keywords： channel coding; LT code; Gaussian channel; encoding algorithm; extrinsic information transfer; convergence

0 ?引 ?言

作為一種特殊的信道編碼，無速率碼[1]最初應(yīng)用于二進(jìn)制刪除信道（Binary Erasure Channel，BEC）中以提高數(shù)據(jù)傳輸效率。LT碼[2]是第一種實(shí)用的無速率碼，Raptor碼[3]則是以LT碼為內(nèi)碼、高碼率的預(yù)編碼為外碼的級聯(lián)無速率碼。無速率碼在BEC中具有優(yōu)良性能，文獻(xiàn)[4?5]證明，經(jīng)過恰當(dāng)設(shè)計，無速率碼也可以應(yīng)用于加性高斯白噪聲（Additive White Gaussian Noise，AWGN）信道中。

LT碼在AWGN信道中存在較高的誤碼平臺，而Raptor碼中的外碼能夠進(jìn)一步糾正LT碼的錯誤，因此Raptor碼的誤比特率（Bit Error Rate， BER）能隨著編碼長度的增加瀑布式下降，但這是以高編譯碼復(fù)雜度為代價的[6]。實(shí)際上，作為無速率碼的核心，LT碼的性能直接影響著無速率碼的性能及實(shí)用性，而對LT碼性能造成直接影響的是LT碼的編碼方式和校驗(yàn)節(jié)點(diǎn)度分布函數(shù)。因此，文獻(xiàn)[7?8]考慮對LT碼的編碼過程進(jìn)行改進(jìn)以提高其性能。此外，LT碼的度分布函數(shù)的設(shè)計方法也在不斷優(yōu)化改進(jìn)，如基于聯(lián)合譯碼算法和外信息傳遞（Extrinsic Information Transfer，EXIT）圖法的設(shè)計方法[9];基于多邊網(wǎng)絡(luò)結(jié)構(gòu)的設(shè)計方法[10?11];基于譯碼“波紋”的設(shè)計方法[12];基于分類信息節(jié)點(diǎn)的設(shè)計方法[13]等。然而，上述文獻(xiàn)均是從LT碼校驗(yàn)節(jié)點(diǎn)度分布的角度出發(fā)，通過優(yōu)化LT碼自身結(jié)構(gòu)以提高BER性能，未能從信息節(jié)點(diǎn)的角度出發(fā)考慮信息節(jié)點(diǎn)度分布對LT碼性能的影響。此外，大多數(shù)文獻(xiàn)均是將LT碼作為Raptor碼的一部分進(jìn)行聯(lián)合設(shè)計，未能單獨(dú)針對AWGN信道中的LT碼進(jìn)行改進(jìn)。LT碼作為Raptor碼的核心，如果能提高LT碼的性能，實(shí)際上就相當(dāng)于提高了Raptor碼的性能。

針對上述兩個問題，本文提出一種適用于LT碼的選擇編碼（Selective Encoding，SE）算法。該算法通過改變編碼過程中校驗(yàn)節(jié)點(diǎn)選擇信息節(jié)點(diǎn)的方式，優(yōu)化了LT碼的信息節(jié)點(diǎn)度分布，從而改善了LT碼的誤碼平臺現(xiàn)象。首先，從信息節(jié)點(diǎn)的角度出發(fā)分析了造成LT碼誤碼平臺現(xiàn)象的原因，得到隨機(jī)選擇信息節(jié)點(diǎn)的方式并不是最優(yōu)編碼方式，并通過仿真證明移除小度數(shù)值的信息節(jié)點(diǎn)有助于提升LT碼的BER性能。因此，本文提出的SE算法按照度數(shù)值大小將待編碼的信息節(jié)點(diǎn)分類，在每生成一個校驗(yàn)節(jié)點(diǎn)時會優(yōu)先從小度數(shù)值節(jié)點(diǎn)集合中選取信息節(jié)點(diǎn)，從而消除了小度數(shù)值的信息節(jié)點(diǎn)。進(jìn)一步利用EXIT圖法對SE算法及傳統(tǒng)編碼方法的收斂性進(jìn)行對比分析，驗(yàn)證了SE算法的有效性。另外，SE算法沒有改變校驗(yàn)節(jié)點(diǎn)度分布，因此，算法的譯碼復(fù)雜度與傳統(tǒng)方式相當(dāng)。最后，AWGN信道中的仿真結(jié)果顯示，SE算法能夠在大范圍信噪比及任意碼率條件下均實(shí)現(xiàn)BER性能的提升。

1 ?LT碼

1.1 ?LT碼的編碼

在LT碼中，對包含K個信息比特的向量[v=v1，v2，…，vK]編碼產(chǎn)生包含N個編碼比特的向量[w=w1，w2，…，wN]。每產(chǎn)生一個編碼比特[wj1≤j≤N]時，首先根據(jù)度分布函數(shù)[Ωx]依概率生成一個度數(shù)值d，然后從K個信息比特中隨機(jī)選取d個進(jìn)行異或，將結(jié)果賦值給wj。重復(fù)上述過程直至生成N個編碼比特，此次編碼結(jié)束。校驗(yàn)節(jié)點(diǎn)度分布函數(shù)定義為[Ωx=j=1dcΩjxj]，其中[Ωj]是選中度數(shù)j的概率，dc是最大校驗(yàn)節(jié)點(diǎn)度數(shù)值。LT碼還可以用Tanner圖來表示，如圖1所示。其中，每個信息節(jié)點(diǎn)連接的邊的個數(shù)即為該信息節(jié)點(diǎn)的度數(shù)值。定義信息節(jié)點(diǎn)的度分布函數(shù)為[Λx=i=1dvΛjxi]，其中，dv為最大信息節(jié)點(diǎn)度數(shù)值。

圖1 LT 碼的Tanner 圖

在LT碼中，定義信息節(jié)點(diǎn)和校驗(yàn)節(jié)點(diǎn)基于邊的度數(shù)分布分別為[λx=i=1dvλixi-1]和[ρx=j=1dcρjxj-1]。[λx]滿足[λx=Ω′xΩ′1]，[ρx]滿足[ρx=Λ′xΛ′1]。盡管LT碼是無速率碼，但定義其瞬時碼率為[R=KN]。

1.2 ?LT碼的譯碼

在AWGN信道中，LT碼采用置信傳播（Belief Propagation， BP）算法進(jìn)行迭代譯碼。該算法將對數(shù)似然比（Log?Likelihood Ratio，LLR）信息在信息節(jié)點(diǎn)和校驗(yàn)節(jié)點(diǎn)之間進(jìn)行來回傳遞和更新，使LLR信息逐漸收斂于穩(wěn)定值并據(jù)此進(jìn)行最佳判決。令[Lcj→vi]表示迭代過程中第j個校驗(yàn)節(jié)點(diǎn)傳遞給第i個信息節(jié)點(diǎn)的LLR信息，定義為：

2 ?選擇編碼算法及其收斂性分析

2.1 ?LT碼誤碼平臺分析

本節(jié)從信息節(jié)點(diǎn)的角度出發(fā)，分析誤碼平臺形成的原因以及改進(jìn)措施。傳統(tǒng)LT碼中，隨機(jī)選擇信息節(jié)點(diǎn)的編碼方式使得信息節(jié)點(diǎn)的度數(shù)服從均值和方差為α的泊松分布，且[α=βNK，β=j=1dcjΩj]，其中[β]為校驗(yàn)節(jié)點(diǎn)平均度數(shù)，[α]又被稱為信息節(jié)點(diǎn)平均度數(shù)。換言之，信息節(jié)點(diǎn)的度分布只與校驗(yàn)節(jié)點(diǎn)度分布函數(shù)和碼率倒數(shù)相關(guān)。在泊松分布下，小度數(shù)值信息節(jié)點(diǎn)的比例不為0，因此，無論參與編碼的信息節(jié)點(diǎn)的個數(shù)是多少，在大量重復(fù)實(shí)驗(yàn)時，總會存在相當(dāng)一部分的小度數(shù)值信息節(jié)點(diǎn)。這些小度數(shù)值信息節(jié)點(diǎn)連接的校驗(yàn)節(jié)點(diǎn)的個數(shù)有限，能夠獲得的來自校驗(yàn)節(jié)點(diǎn)的LLR信息較少，往往不足以使其準(zhǔn)確地判斷自身的狀態(tài)，從而無法被正確恢復(fù)。這些可靠性較低的小度數(shù)值信息節(jié)點(diǎn)的存在使得LT碼的BER始終無法隨編碼長度的增加降至為0，即造成了誤碼平臺現(xiàn)象。

以文獻(xiàn)[14]中給出的度分布為例，通過仿真驗(yàn)證小度數(shù)值信息節(jié)點(diǎn)對LT碼性能的影響，考慮如下仿真條件：信息節(jié)點(diǎn)長度為[K=256]，信噪比為[EsN0=0]，譯碼迭代次數(shù)設(shè)置為50。仿真對以下情況進(jìn)行比較：不改變信息節(jié)點(diǎn)度數(shù)、移除度數(shù)為1的信息節(jié)點(diǎn)、移除度數(shù)為1和2的信息節(jié)點(diǎn)、移除度數(shù)不超過3的信息節(jié)點(diǎn)，結(jié)果如圖2所示。顯然，隨著小度數(shù)值信息節(jié)點(diǎn)數(shù)目的減少，LT碼的誤碼平臺不斷降低，這表明，可以通過移除小度數(shù)值的信息節(jié)點(diǎn)進(jìn)一步降低LT碼的誤碼平臺。

圖2 移除不同度數(shù)值信息節(jié)點(diǎn)時的BER 性能

綜上所述，在傳統(tǒng)編碼算法中，隨機(jī)選擇信息節(jié)點(diǎn)的方式并不能使LT碼的BER性能達(dá)到最優(yōu)。因此，本文考慮通過改變選擇信息節(jié)點(diǎn)的方式消除小度數(shù)值信息節(jié)點(diǎn)，達(dá)到提高LT碼BER性能的目的。

2.2 ?選擇編碼算法

根據(jù)第2.1節(jié)的分析，提出針對LT碼的選擇編碼算法，見算法1。算法中涉及的參數(shù)有：信息比特個數(shù)K，編碼比特個數(shù)N，度分布[Ωx]。算法流程如下：

算法1中，每生成一個編碼比特時都按當(dāng)前校驗(yàn)節(jié)點(diǎn)度數(shù)值[d]優(yōu)先選取前[d]種度數(shù)的信息節(jié)點(diǎn)，則在生成第[k+1]個編碼比特時，度數(shù)不大于[β]的信息節(jié)點(diǎn)就已經(jīng)不存在了。因此，算法1消除了小度數(shù)值的信息節(jié)點(diǎn)，并將98%以上的信息節(jié)點(diǎn)的度數(shù)值都集中于[α-2，α+8]區(qū)間內(nèi)，提高了中等度數(shù)值信息節(jié)點(diǎn)的比例，從而改善了誤碼平臺現(xiàn)象。另外，算法1沒有改變校驗(yàn)節(jié)點(diǎn)的度分布，即校驗(yàn)節(jié)點(diǎn)與信息節(jié)點(diǎn)之間的平均邊數(shù)仍為[Nβ]，因此譯碼復(fù)雜度與傳統(tǒng)方式相當(dāng)。

2.3 ?算法的收斂性分析

為了驗(yàn)證算法1的有效性，本節(jié)利用EXIT圖法對算法1的收斂性進(jìn)行分析。

將LT碼的譯碼器分為信息節(jié)點(diǎn)譯碼器（IND）和校驗(yàn)節(jié)點(diǎn)譯碼器（CND），則LT碼的譯碼過程可以看作LLR信息在IND和CND之間的傳遞更新。在第1.1節(jié)的基礎(chǔ)上，定義函數(shù)[Jσ]為x與y之間的互信息，滿足：

算法1對信息節(jié)點(diǎn)的選擇方式進(jìn)行了優(yōu)化改進(jìn)，因此，算法1中的校驗(yàn)節(jié)點(diǎn)邊度數(shù)分布不變，而信息節(jié)點(diǎn)邊度數(shù)不再服從泊松分布，即式（5）不再成立。與傳統(tǒng)的信道編碼方式不同，LT碼實(shí)際上是一種基于概率選擇的特殊編碼，但是在算法1中，無法利用概率值的大小精確定義非空信息節(jié)點(diǎn)集合的個數(shù)以及每個集合中信息節(jié)點(diǎn)的個數(shù)，即無法利用數(shù)學(xué)理論推導(dǎo)算法1中信息節(jié)點(diǎn)邊度數(shù)分布。因此，本文考慮利用蒙特卡洛仿真結(jié)果代替真實(shí)結(jié)果對算法1的收斂性進(jìn)行分析。為了證明算法的普適性，表1給出了不同度分布和不同碼率值條件下的仿真結(jié)果（部分），度分布采用文獻(xiàn)[14]中針對不同碼長設(shè)計的度分布，限于篇幅此處不一一列舉。

利用表1中測得的數(shù)據(jù)，繪制出K=64和K=128時的EXIT圖，見圖3和圖4。、

圖3 K=64 時的EXIT 圖

CND曲線和IND曲線之間的通道稱為譯碼通道，只有當(dāng)譯碼通道打開，即CND曲線和IND曲線不相交且收斂于1時，BER才能趨近于0。從圖3和圖4中可以看出，在相同信噪比和碼率值下，SE算法能夠進(jìn)一步拓寬譯碼通道，使得LT碼能夠在更少的迭代次數(shù)下成功譯碼，提高了譯碼效率。另外，SE算法還能在相同條件下提高譯碼成功概率，如在[EsN0]=0，R=[23]時，傳統(tǒng)編碼算法的IND曲線與CND曲線存在相交點(diǎn)，因此無論經(jīng)過多少次迭代，傳統(tǒng)LT碼的BER都無法趨近于0;而SE算法的IND曲線與CND曲線之間的譯碼通道仍處于打開狀態(tài)，因此若采用SE算法則能使LT碼在有限次迭代后成功譯碼。

圖4 K=128 時的EXIT 圖

綜上所述，與傳統(tǒng)編碼算法相比，SE算法能夠在不同校驗(yàn)節(jié)點(diǎn)度分布、不同碼率值、不同信噪比條件下均實(shí)現(xiàn)更為優(yōu)良的收斂性，從而進(jìn)一步驗(yàn)證了算法的有效性和普適性。

3 ?仿真結(jié)果及分析

表1 不同情況下信息節(jié)點(diǎn)邊度數(shù)分布系數(shù)（部分）

本節(jié)對傳統(tǒng)算法以及SE算法在二進(jìn)制AWGN信道中的性能進(jìn)行仿真對比。所有仿真結(jié)果均通過1 000 000次蒙特卡洛仿真得到，采用BP譯碼算法時最大迭代次數(shù)均設(shè)置為50次，LT碼的碼長分別為K=64，K=128，K=256，K=512，校驗(yàn)節(jié)點(diǎn)度分布與文獻(xiàn)[14]中相同。

圖6 R=1 2 時LT 碼的BER 性能對比圖

首先，在信噪比[EsN0=0]時對不同長度LT碼的BER隨碼率變化情況進(jìn)行仿真，見圖5。圖中實(shí)線為傳統(tǒng)算法的結(jié)果，虛線為SE算法的結(jié)果，兩種曲線從上至下分別代表K=64，K=128，K=256，K=512?？梢钥闯?，在相同條件下SE算法最多可將BER減少近2個數(shù)量級，較大程度地降低了LT碼的誤碼平臺，提高了LT碼的譯碼成功概率，這與第2.3節(jié)對SE算法收斂性的分析結(jié)果相一致。另外，SE算法在任意碼長和任意校驗(yàn)節(jié)點(diǎn)度分布下均能實(shí)現(xiàn)BER性能的提升，且碼長越長，算法的增益越大。

其次，在固定碼率[R=12]時對不同長度LT碼的BER隨信噪比變化情況進(jìn)行仿真，見圖6。圖中曲線分布情況與圖5相同。可以看出，SE算法極大地改善了LT碼的誤碼平臺現(xiàn)象。以K=512為例，傳統(tǒng)算法在5 dB時的BER與SE算法在0時的BER相近，即SE算法能夠?qū)T碼性能提升將近5 dB。類似地，其他三種情況下的增益分別近似為2 dB，3.5 dB，4.2 dB，說明SE算法對任意范圍的信噪比均能適用。

作為Raptor碼實(shí)現(xiàn)無速率功能的關(guān)鍵部分，LT碼性能的提升同樣可以給Raptor碼帶來有益效果。本文在上述LT碼的基礎(chǔ)上引入碼率為0.9的規(guī)則（3，30）LDPC碼作為預(yù)編碼，以此驗(yàn)證SE算法對Raptor碼性能的增益。

圖7 Es N0=0 時Raptor 碼的BER 性能對比圖

為了便于分析，將信息比特長度分別設(shè)置為K=63，K=126，K=252，K=504，因此經(jīng)過LDPC編碼后的碼字長度分別為70，140，280以及560，以便進(jìn)行下一步的LT編碼。LDPC碼部分采用BP譯碼算法。

圖5 Es N0= 0 時LT 碼的BER 性能對比圖

圖7為上述Raptor碼在信噪比[EsN0]=0時的BER仿真結(jié)果，為便于表示，橫坐標(biāo)仍為LT碼的碼率倒數(shù)（R-1）。圖中4組曲線的分布情況與圖5相同。可以看出，采用SE算法的Raptor碼能夠獲得更為優(yōu)良的BER性能，并且碼長越長，增益越明顯。以K=504的Raptor碼為例，傳統(tǒng)算法需以R-1 = 2.4的開銷方能使BER達(dá)到10-6標(biāo)準(zhǔn)，而SE算法只需使R-1 = 2.2。說明SE算法能夠使Raptor碼以更高的碼率達(dá)到相同的BER性能，從而可以在相同的時間內(nèi)傳輸更多的有效數(shù)據(jù)，提高了數(shù)據(jù)傳輸效率。

4 ?結(jié) ?語

本文從信息節(jié)點(diǎn)的角度出發(fā)分析了AWGN信道中LT碼性能不佳的原因，進(jìn)而提出一種新的SE算法。通過改變編碼過程中信息節(jié)點(diǎn)的選擇方式，消除了小度數(shù)值信息節(jié)點(diǎn)，并使得信息節(jié)點(diǎn)和校驗(yàn)節(jié)點(diǎn)之間的連接關(guān)系更加合理化，從而改善了LT碼的誤碼平臺現(xiàn)象。另外，本文利用EXIT圖法比較了不同編碼條件下傳統(tǒng)編碼算法和SE算法的收斂性，從理論上證明了SE算法的可行性和普適性。最后，仿真結(jié)果表明，無論是在LT碼還是Raptor碼中，SE算法均能降低BER，幅度可達(dá)1～4個數(shù)量級，且沒有增加譯碼復(fù)雜度，從而提高了無速率碼在AWGN信道中的實(shí)用性。

參考文獻(xiàn)

[1] COSTA M， PINHO M. An algorithm for optimal unequal error protection rate allocation exploring granular channel rates [J]. IEEE communications letters， 2018， 22（5）： 926?929.

[2] LUBY M. LT codes [C]// Proceedings of the 43rd Annual IEEE Symposium on Foundations of Computer Science. Vancouver： IEEE Computer Society， 2002： 271?280.

[3] SHOKROLLAHI A. Raptor codes [J]. IEEE transactions on information theory， 2006， 52（6）： 2551?2567.

[4] YANG W， LI Y， YU X， et al. Rateless superposition spinal coding scheme for half?duplex relay channel [J]. IEEE transactions on wireless communications， 2016， 15（9）： 6259?6272.

[5] CHEN H， MAUNDER R G， MA Y， et al. Hybrid?ARQ?aided short fountain codes designed for block?fading channels [J]. IEEE transactions on vehicular technology， 2015， 64（12）： 5701?5712.

[6] ALBAYRAK C， SIMSEK C， TURK K. Low?complexity early termination method for rateless soft decoder [J]. IEEE communications letters， 2017， 21（11）： 2356?2359.

[7] HUSSAIN I， XIAO M， RASMUSSEN L K. Error floor analysis of LT codes over the additive white Gaussian noise channel [C]// Proceedings of 2011 IEEE Global Telecommunications Conference. Kathmandu： IEEE， 2011： 1?5.

[8] 姚渭箐，易本順.基于存儲機(jī)制的LT碼編譯碼方法[J].系統(tǒng)工程與電子技術(shù)，2018，40（1）：165?170.

YAO Weiqing， YI Benshun. Memory?based encoding and decoding of LT codes [J]. Systems enginerring and electronics， 2018， 40（1）： 165?170.

[9] SHIRVANIMOGHADDAM M， JOHNSON S. Raptor codes in the low SNR regime [J]. IEEE transactions on communications， 2016， 64（11）： 4449?4460.

[10] JAYASOORIYA S， SHIRVANIMOGHADDAM M， ONG L， et al. Analysis and design of raptor codes using a multi?edge framework [J]. IEEE transactions on communications， 2017， 65（12）： 5123?5136.

[11] JAYASOORIYA S， SHIRVANIMOGHADDAM M， ONG L， et al. Raptor codes for higher?order modulation using a multi?edge framework [J]. IEEE wireless communications letters， 2017， 7（1）： 110?113.

[12] SORENSEN J H， KOIKE?AKINO T， ORLIK P， et al. Ripple design of LT codes for AWGN channel [C]// Proceedings of 2012 IEEE International Symposium on Information Theory. Cambridge： IEEE， 2014： 1757?1761.

[13] KHAREL A， CAO L. Improved fountain codes for BI?AWGN channels [C]// Proceedings of 2017 IEEE Wireless Communications and Networking Conference. San Francisco： IEEE， 2017： 1?6.

[14] ZHANG W， HRANILOVIC S， SHI C. Soft?switching hybrid FSO/RF links using short?length raptor codes： design and implementation [J]. IEEE journal on selected areas in communications， 2010， 27（9）： 1698?1708.