一種適用于LT碼的選擇編碼算法

宋鑫 廖育榮 丁丹

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

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

中圖分類號： TN911.22?34 ? ? ? ? ? ? ? ? ? ?文獻標識碼： 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]最初應用于二進制刪除信道（Binary Erasure Channel，BEC）中以提高數據傳輸效率。LT碼[2]是第一種實用的無速率碼，Raptor碼[3]則是以LT碼為內碼、高碼率的預編碼為外碼的級聯無速率碼。無速率碼在BEC中具有優良性能，文獻[4?5]證明，經過恰當設計，無速率碼也可以應用于加性高斯白噪聲（Additive White Gaussian Noise，AWGN）信道中。

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

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

1 ?LT碼

1.1 ?LT碼的編碼

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

圖1 LT 碼的Tanner 圖

在LT碼中，定義信息節點和校驗節點基于邊的度數分布分別為[λ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）算法進行迭代譯碼。該算法將對數似然比（Log?Likelihood Ratio，LLR）信息在信息節點和校驗節點之間進行來回傳遞和更新，使LLR信息逐漸收斂于穩定值并據此進行最佳判決。令[Lcj→vi]表示迭代過程中第j個校驗節點傳遞給第i個信息節點的LLR信息，定義為：

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

2.1 ?LT碼誤碼平臺分析

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

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

圖2 移除不同度數值信息節點時的BER 性能

綜上所述，在傳統編碼算法中，隨機選擇信息節點的方式并不能使LT碼的BER性能達到最優。因此，本文考慮通過改變選擇信息節點的方式消除小度數值信息節點，達到提高LT碼BER性能的目的。

2.2 ?選擇編碼算法

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

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

2.3 ?算法的收斂性分析

為了驗證算法1的有效性，本節利用EXIT圖法對算法1的收斂性進行分析。

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

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

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

圖3 K=64 時的EXIT 圖

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

圖4 K=128 時的EXIT 圖

綜上所述，與傳統編碼算法相比，SE算法能夠在不同校驗節點度分布、不同碼率值、不同信噪比條件下均實現更為優良的收斂性，從而進一步驗證了算法的有效性和普適性。

3 ?仿真結果及分析

表1 不同情況下信息節點邊度數分布系數（部分）

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

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

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

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

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

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

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

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

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

4 ?結 ?語

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

參考文獻

[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] 姚渭箐，易本順.基于存儲機制的LT碼編譯碼方法[J].系統工程與電子技術，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.