采用定長節(jié)點分類窗口的低誤碼平臺LT 編碼算法

宋鑫，程乃平，倪淑燕，廖育榮，雷拓峰

（1.航天工程大學研究生院，北京 101416；2.航天工程大學電子與光學工程系，北京 101416）

1 引言

噴泉碼[1]最初是針對二進制刪除信道（BEC,binary erasure channel）設計的，旨在為大規(guī)模數(shù)據(jù)分發(fā)和可靠廣播場景提出一種理想的解決方案[2]。以LT 碼[3]為代表的噴泉碼，具有天然的信道自適應特性，可以靈活地產生任意數(shù)量的編碼符號。因此，無論信道刪除概率多大，發(fā)送端總能源源不斷地產生編碼數(shù)據(jù)直到譯碼器恢復出源數(shù)據(jù)。這使得它非常適合應用于傳輸視頻、音頻的廣播場景[4]、協(xié)作中繼場景[5]、水聲通信場景[6]和自由空間光通信場景[7]等。

盡管噴泉碼最初是面向BEC 進行設計的，但其在加性白高斯噪聲（AWGN,additive white Gaussian noise）信道中也具有潛在的應用前景[8-9]。文獻[10]研究結果表明，LT 碼在二進制對稱信道（BSC,binary symmetric channel）和AWGN 信道中存在明顯的誤碼平臺。文獻[11-14]考慮通過優(yōu)化校驗度分布來改善誤碼平臺。文獻[11]給出了一種在二進制輸入AWGN（BIAWGN,binary input AWGN）信道中設計LT 碼校驗度分布的方法，即以最大化LT 碼的碼率值為目標函數(shù)，以校驗節(jié)點每次迭代輸出的消息值遞增為約束條件，采用線性規(guī)劃的方法求解出最優(yōu)的度分布系數(shù)。文獻[12]針對極低信噪比條件提出了一種改進的度分布設計方式。文獻[13]給出了一種適用于大范圍信噪比的度分布函數(shù)策略，主要思想是根據(jù)信道狀態(tài)信息（CSI,channel state information）的變化及時調整至最合適的度分布函數(shù)以保持足夠高的碼率效率。文獻[14]針對系統(tǒng)LT 碼，引入了誤比特率（BER,bit error rate）下界作為新的約束條件，實現(xiàn)了以更小的譯碼開銷進入瀑布區(qū)的效果。

但是，在BIAWGN 信道中，優(yōu)化校驗度分布函數(shù)對降低誤碼平臺的效果有限，特別是在碼長較短時。在利用線性規(guī)劃方法設計度分布時，往往考慮的都是無限碼長和甚高迭代次數(shù)時的理想狀態(tài)。因此，所設計的度分布一般只在碼長較長時才能表現(xiàn)出優(yōu)良的漸進性能，但對中短碼長BER 性能的改善效果卻十分有限。

針對上述問題，本文暫不考慮優(yōu)化度分布的問題，而是試圖通過改進LT 碼的編碼算法來提升其BER 性能。文獻[15]指出誤碼平臺主要是由不可靠的小度數(shù)值信息節(jié)點造成的，這些節(jié)點沒有連接至足夠多的校驗節(jié)點，因此，被成功恢復的概率更低。為此，文獻[15]提出了一種改進的編碼算法：對信息節(jié)點按照度數(shù)值大小進行分類，并迫使校驗節(jié)點優(yōu)先從度數(shù)最小的一類信息節(jié)點中選取。這種算法幾乎完全消除了小度數(shù)值的信息節(jié)點，并使幾乎所有信息節(jié)點具有了相同的度數(shù)。文獻[16]則將文獻[15]的編碼思想應用到了不等差錯保護場景中，以略微增加譯碼開銷為代價，將最重要比特（MIB,most important bit）的BER 平臺降低了將近3 個數(shù)量級。文獻[17]提出的改進算法在校驗節(jié)點選擇每個信息節(jié)點時，都先從所有的信息節(jié)點中隨機選取T個節(jié)點作為一組，然后再從這一組中選擇度數(shù)最小的信息節(jié)點進行連接。需要說明的是，文獻[17]的改進算法對BER 性能的提升程度取決于額外引入的參數(shù)T，但是沒有給出關于該參數(shù)的嚴謹設計方法。相較于文獻[17]，文獻[18]的改進算法則引入了更多的參數(shù)，如衡量校驗節(jié)點度數(shù)值大小的參數(shù)d*。若當前校驗節(jié)點的度數(shù)大于d*，則將優(yōu)先連接至小度數(shù)值的信息節(jié)點；若度數(shù)小于d*，則仍從所有的信息節(jié)點中隨機選取；若度數(shù)等于d*，則依據(jù)預先給定的權重確定選取方法。仿真結果顯示，這幾種改進算法在BEC 或者AWGN 信道中都能夠使LT碼更快地進入BER 瀑布區(qū)，并能顯著地降低誤碼平臺。

但是這幾種改進算法也存在下述問題：1) 沒有給出算法所涉及參數(shù)的優(yōu)化設計方法；2) 算法可達的BER 性能不具備可調控性；3) 算法設計中沒有考慮信道條件的約束。

針對上述問題，本文設計了一種面向AWGN信道的改進LT 編碼算法，主要思想是引入節(jié)點分類窗口對編碼過程進行直接操控，利用該窗口標記度數(shù)值相對較小的信息節(jié)點，并強迫這些節(jié)點頻繁地連接至校驗節(jié)點，從而使其獲得足夠可靠的度數(shù)值。本文主要工作是建立了最優(yōu)參數(shù)設計模型。首先，分析了移除小度數(shù)值信息節(jié)點后的LT 碼BER性能，并將理論BER 下界作為算法參數(shù)的第1 個約束條件。其次，分析了改進算法的收斂性，設計了參數(shù)外信息增益損失比（GLR,gain loss ratio），并將最大化GLR 值作為第2 個約束條件。最后，分析了不同算法參數(shù)對編碼效率和編碼復雜度的影響，指出了參數(shù)的優(yōu)先選取原則，并將其作為第3 個約束條件。仿真結果顯示，本文的改進算法能夠顯著地降低LT 碼的誤碼平臺，獲得了比傳統(tǒng)LT 碼和文獻[15,17]的改進LT 碼更優(yōu)的BER 性能，證明了算法的可行性。

2 誤碼平臺分析及改進的LT 編碼算法

2.1 傳統(tǒng)LT 碼模型

對于傳統(tǒng)LT 碼，編碼器會對K個信息節(jié)點v={v1,v2,… ,vK}進行編碼，生成N個校驗節(jié)點c={c1,c2,… ,cN}，且N個編碼節(jié)點與校驗節(jié)點一一相連。LT 碼的Tanner 如圖1 所示。

圖1 LT 碼的Tanner

如圖1 所示，定義每個校驗節(jié)點連接的信息節(jié)點的個數(shù)為該校驗節(jié)點的度數(shù)值，同理，每個信息節(jié)點連接的校驗節(jié)點的個數(shù)為該信息節(jié)點的度數(shù)值。例如，校驗節(jié)點c1的度數(shù)值為2，信息節(jié)點v3的度數(shù)值為3。此外，定義校驗節(jié)點的度分布函數(shù)為，其中，Ωj表示度數(shù)為j的校驗節(jié)點出現(xiàn)的概率，dc表示校驗節(jié)點的最大度數(shù)值。定義信息節(jié)點度分布為，其中，Λi表示度數(shù)為i的信息節(jié)點出現(xiàn)的概率，dv表示信息節(jié)點的最大度數(shù)值。盡管LT 碼是無速率碼，但仍定義其瞬時碼率值為R=。為便于后文分析，此處給出傳統(tǒng)LT 碼的編碼算法，如算法1 所示。

算法1傳統(tǒng)LT 碼的編碼算法

初始化給定K個信息節(jié)點v={v1,v2,…,vK}，待生成校驗節(jié)點個數(shù)N和校驗度分布函數(shù)Ω(x)，記n=1。

1) 依據(jù)度分布函數(shù)Ω(x)選擇當前校驗節(jié)點的度數(shù)值d。

2) 從K個信息節(jié)點中，隨機選取d個。

3) 將上述d個信息節(jié)點的值進行異或，作為第n個校驗節(jié)點的值。

4) 令n=n+1。若n＜N，則返回步驟1)；若n=N，則結束編碼，并輸出N個校驗節(jié)點c={c1,c2,… ,cN}。

盡管每個校驗節(jié)點的度數(shù)是依據(jù)校驗度分布生成的，但可以求得每個校驗節(jié)點的平均度數(shù)為，則每個信息節(jié)點的平均度數(shù)值為。信息度分布函數(shù)的系數(shù)Λi為

根據(jù)文獻[11]可知，傳統(tǒng)LT 碼的信息度分布可以看作以α為均值的泊松分布，即

如圖1 所示，在信息節(jié)點和校驗節(jié)點之間任選一條邊，定義該條邊連接到度數(shù)為j的校驗節(jié)點的概率為ρj，連接到度數(shù)為i的信息節(jié)點的概率為λi。在此基礎上，進一步定義校驗節(jié)點邊的度數(shù)分布為，信息節(jié)點邊的度數(shù)分布為λ(x)=。其中，系數(shù)ρj和λi的計算方法如下[19]

2.2 LT 碼的誤碼平臺分析

傳統(tǒng)LT 碼在生成度數(shù)為d的校驗節(jié)點時，隨機選取d個信息節(jié)點進行異或，在這種方式下得到的信息節(jié)點度分布近似服從泊松分布。然而，從式(1)和式(2)可以看出，即使α足夠大，小度數(shù)值信息節(jié)點（包括度數(shù)為0 的節(jié)點）存在的概率仍不為零。因此，可以預測，在大量重復實驗下，必然還會出現(xiàn)一定數(shù)量的小度數(shù)值信息節(jié)點，這些節(jié)點所連接的校驗節(jié)點很少，在譯碼過程中往往無法獲得足夠多的來自校驗節(jié)點的對數(shù)似然比（LLR,log-likelihood ratios）信息，因此，很難對自身的比特值進行正確判決，可靠性較低。

針對這個問題，可以考慮改進編碼算法以消除小度數(shù)值的信息節(jié)點，進而提升LT 碼的BER 性能。這一結論可以利用LT 碼的BER 下界計算式進行驗證。文獻[15]指出，在二元輸入加性白高斯噪聲（BIAWGN,binary input AWGN）信道中，LT 碼的平均BER 的下界可表示為

從式(5)可以看出，LT 碼的BER 下界只與信息節(jié)點的度分布有關，因此，在設計改進的編碼算法時，一般只需要考慮信息節(jié)點的分布情況即可。為了觀察小度數(shù)信息節(jié)點對LT 碼誤碼平臺的影響，分別移除了度數(shù)為1，度數(shù)為1、2，度數(shù)為1、2、3 的信息節(jié)點，并計算其各自的BER 下限，結果如圖2 所示。仿真采用的碼率值為，度分布為文獻[20]中K=512 設計的校驗度分布，記為Ω1(x)。

圖2 移除低度數(shù)信息節(jié)點后的LT 碼BER 下界

從圖2 可以看出，移除度數(shù)為1、2、3 的信息節(jié)點后，信噪比為5 dB 的BER 比傳統(tǒng)算法低了將近3 個數(shù)量級，這驗證了通過改進編碼算法降低誤碼平臺的可行性。需要說明的是，圖2 中的計算結果是針對碼長逼近無限長時的情況，因此，當采用中短碼長時，實際的BER 性能可能會有所損耗，且碼長越短，與理論BER 下限之間的差距越大。

2.3 改進的LT 編碼算法

在實際應用中，為了確保每個信息節(jié)點都能正確恢復，并非直接刪除小度數(shù)值信息節(jié)點，往往是通過控制編碼過程使每個信息節(jié)點都獲得足夠大的度數(shù)值。例如，文獻[15-17]中的改進算法會記錄并及時更新信息節(jié)點的度數(shù)值，并強迫小度數(shù)值的信息節(jié)點優(yōu)先參與編碼進程。但是，上述幾種算法也存在2 點不足。1) 無法設立預期可達的BER 標準。換言之，上述文獻只是設計了一類優(yōu)化的信息節(jié)點選取規(guī)則，當給定編碼參數(shù)后，算法所生成的信息節(jié)點度分布隨之確定，即算法的BER 下界隨之確定且無法靈活調整。2) 沒有考慮信道條件的約束。從式(5)可以看出，LT 碼的BER 下界受到信道參數(shù)的約束，即與BIAWGN 信道的方差有關。但是，上述改進算法在優(yōu)化信息度分布時并沒有將信道狀態(tài)信息的影響考慮在內，這可能造成非最優(yōu)匹配的編碼結果。

為了克服上述問題，本文擬設計一種改進的LT編碼算法，如算法2 所示。考慮以更直接的控制方式，即引入長度為Tv的節(jié)點分類窗口W，用于存儲可靠性較低的信息節(jié)點，然后強迫窗口內的節(jié)點頻繁地參與校驗節(jié)點的生成，直至這些信息節(jié)點具備較高的度數(shù)值和可靠性，便可暫時地脫離該窗口。具體而言，將編碼過程分為2 個階段。第1 階段仍然采用傳統(tǒng)方式進行，確保所有的信息節(jié)點獲得初始度數(shù)值，以便于開啟第2 階段的編碼進程。在第2階段，節(jié)點窗口內存儲度數(shù)值位于前Tv類的信息節(jié)點并動態(tài)更新，該編碼階段內生成的校驗節(jié)點都將只能從此窗口中選取信息節(jié)點。假設待生成校驗節(jié)點總數(shù)為N，第1 階段的校驗節(jié)點個數(shù)為NP，第2階段的校驗節(jié)點個數(shù)為NS，且滿足NP+NS=N。令節(jié)點窗口長度為Tv。

算法2改進的LT 編碼算法

初始化給定K個信息節(jié)點v={v1,v2,…,vK]和校驗度分布函數(shù)Ω(x)，令所有信息節(jié)點構成的集合為V，記n=1。

1) 采用算法1 進行編碼，生成NP個校驗節(jié)點，記n=NP。

2) 更新所有信息節(jié)點的度數(shù)值并進行分類，將度數(shù)值位于前Tv類的信息節(jié)點存儲至窗口W中，記錄窗口中的節(jié)點個數(shù)為ζ。

3) 依據(jù)度分布函數(shù)Ω(x)生成當前校驗節(jié)點的度數(shù)值d。

4) 如果當前度數(shù)值d小于ζ，則從窗口W中隨機選取d個信息節(jié)點；如果d大于ζ，則選中窗口W中的所有信息節(jié)點，并再從集合V中隨機選取d-ζ個信息節(jié)點。

5) 將選中的d個信息節(jié)點進行異或，作為當前校驗節(jié)點的值。

6) 令n=n+1。若n＜N，則返回步驟2)；若n=N，則結束編碼，并輸出N個校驗節(jié)點c={c1,c2,… ,cN}。

本文所提出的改進算法的優(yōu)點如下。

1) 度數(shù)值相對較小的信息節(jié)點能夠被優(yōu)先選取。算法2 引入節(jié)點窗口，在第2 階段的每個校驗節(jié)點生成之前，將所有可靠性較低，即度數(shù)值相對較小的信息節(jié)點匯聚在一起，從而使這些節(jié)點能夠始終優(yōu)先連接至更多的校驗節(jié)點。

2) 能夠靈活地調整BER 下界。算法2 可以通過調整窗口的長度Tv，調整改進算法能夠達到的BER 下限。這可以利用極限思維分析：若Tv足夠大，則所有的信息節(jié)點都將被置于窗口中且被無差別地選取，改進算法將退化為傳統(tǒng)的編碼算法，且仍然保持較高的誤碼平臺；若Tv的值較合理，則度數(shù)值相對較小的信息節(jié)點就能始終被高概率地選取，從而實現(xiàn)更低的誤碼平臺。

需要說明的是，對某個信息節(jié)點而言，其是否會位于窗口內并非固定不變的，而是取決于其度數(shù)值的相對大小。這意味著，某個度數(shù)值足夠大的信息節(jié)點跳出窗口外后，并非會一直保持在窗口外。隨著編碼過程的進行，若其度數(shù)值又處于前Tv類時，便又將重新回到該窗口內，等待被編碼。

2.4 改進算法的復雜度分析

相較于傳統(tǒng)算法，本文算法增加了分類信息節(jié)點的操作，因而不可避免地增加了算法的復雜度，本節(jié)將對其進行詳細分析。

傳統(tǒng)LT 編碼算法的關鍵步驟包括：1) 依概率選取校驗度數(shù)d；2) 隨機選取d個信息節(jié)點；3) 將選中的d個信息節(jié)點進行異或。對比算法2 可知，本文算法主要對傳統(tǒng)算法的步驟2)進行了改動，而在選取校驗度數(shù)和求異或值時，與傳統(tǒng)算法完全相同。因此，本節(jié)重點分析信息節(jié)點的選取方式對編碼復雜度的影響。

在算法2 中，每個校驗節(jié)點選取信息節(jié)點時，新增操作為節(jié)點按度數(shù)值大小排序、度數(shù)值d和窗口內節(jié)點個數(shù)大小比較。類似地，文獻[15]中的改進算法增加的操作為節(jié)點按度數(shù)值大小排序、度數(shù)值d和每種度數(shù)節(jié)點個數(shù)大小比較。文獻[17]的改進算法增加的操作為隨機選取T個節(jié)點、節(jié)點按度數(shù)值大小排序、已選信息節(jié)點和當前所選信息節(jié)點的序號比較。表1 給出了上述幾種算法在生成N個校驗節(jié)點時所產生的新增操作及其次數(shù)。

表1 幾種算法生成N 個校驗節(jié)點時的新增操作對比

對3 種改進算法而言，生成每個校驗節(jié)點時需對信息節(jié)點按度數(shù)值大小進行排序，這必然會增加編碼復雜度。以歸并排序算法為例，在本文算法和文獻[15]算法中，其平均時間復雜度均為O(KlbK)。因此，本文算法和文獻[15]算法復雜度相當，但均高于傳統(tǒng)算法。對于文獻[17]算法而言，其平均時間復雜度為O(TlbT)，其中T為該算法中的參數(shù)且T＜K。但是，文獻[17]算法中的排序、數(shù)值比較、隨機選取的操作次數(shù)均遠大于本文算法和文獻[15]算法，因此，其總體復雜度相對較高。

3 改進LT 編碼算法的分析與設計

3.1 改進算法的收斂性分析

改進算法改變了信息節(jié)點的選取方式，但是并不希望過多地增加LT 碼的譯碼復雜度，因此，本節(jié)對改進LT 碼的收斂性進行分析，并引入?yún)?shù)增益損失比作為算法的約束條件。

LT 碼在AWGN 信道中采用置信傳播（BP,belief propagation）算法進行迭代譯碼，分析LT 碼譯碼收斂性常用的工具為外信息傳遞（EXIT,extrinsic information transfer）圖法。參考文獻[21]，定義單調遞增函數(shù)J(θ)為

J(θ)具有唯一的反函數(shù)θ=J-1(I)。關于J(·)和J-1(·)，文獻[22]給出了一種近似的計算方法。為便于分析，將LT 碼的譯碼器分為校驗節(jié)點譯碼器（CND,check node decoder）和信息節(jié)點譯碼器（IND,information node decoder）。在BIAWGN 信道下，LT碼CND 的EXIT 計算式為

LT 碼IND 的EXIT 計算式為

本文改進算法會改變信息節(jié)點的度分布，但不改變校驗度分布。因此，令改進算法的IND 的EXIT 計算式為

改進算法的CND 的EXIT 計算式仍如式(7)所示。需要說明的是，EXIT 圖法常用來尋找固定碼率時能夠成功譯碼的臨界信噪比，或者是固定信噪比時能夠成功譯碼的臨界碼率值。但是，對于改進的LT 碼，更需要關注的是收斂性的損失或增益情況，即IND 的輸入先驗信息相同時，改進算法和傳統(tǒng)算法的輸出外信息的大小對比情況。此處定義LT 碼瞬時碼率的倒數(shù)為R-1，改進算法在第1 階段產生的校驗節(jié)點個數(shù)與信息個數(shù)之比為，第2 階段校驗節(jié)點個數(shù)與信息節(jié)點個數(shù)之比為，且滿足

為了更直觀地觀察，在不同窗口長度下進行了仿真。仿真參數(shù)為R-1=2，=1，采用校驗度分布為Ω1(x)，=4 dB。結果如圖3 所示。

在圖3 中，為了便于觀察LT 碼的迭代收斂路徑，本文參考文獻[15]，將信息節(jié)點的輸入先驗信息和輸出外信息分別置于x軸和y軸；將校驗節(jié)點的輸出外信息和輸入先驗信息分別置于x軸和y軸。

進一步地，定義CND 曲線和IND 曲線之間的空隙為“譯碼收斂區(qū)”。理論上，如果2 條曲線沒有交點，那么當碼長K足夠長時，譯碼器總可以經過有限次迭代成功恢復出源信息，圖3 中的階梯即為迭代軌跡。此外，從圖3 可以看出，仿真結果與分析結論吻合，即改進算法的CND 曲線與傳統(tǒng)算法的CND 曲線會重合，而兩者的IND 曲線則存在一個或多個交點。這說明在不同的先驗信息IA,I條件下，改進算法和傳統(tǒng)算法的輸出外信息差值正負不定，可以直觀地理解為譯碼收斂區(qū)在不同位置會出現(xiàn)拓寬和壓縮的情況。

圖3 改進算法和傳統(tǒng)算法的收斂性對比

若改進IND 曲線位于下方，表明改進算法損失了一定量的外信息，譯碼收斂區(qū)被壓縮；若改進IND 曲線位于上方，表明改進算法獲得了額外的外信息增益，譯碼收斂區(qū)被拓寬。當信噪比較低或者碼率值較小時，壓縮現(xiàn)象會更明顯，嚴重時會導致算法無法成功收斂。因此，為了確保譯碼成功，應合理設計節(jié)點窗口長度以確保1) 譯碼收斂區(qū)是打開的；2) IND 曲線的增益最大、損失最小。

3.2 算法參數(shù)的約束條件

算法2 引入了額外的參數(shù)NP和Tv，為了獲得最優(yōu)的參數(shù)組合，本節(jié)將分析該組參數(shù)對改進算法性能的影響，并給出參數(shù)應滿足的約束條件。

依據(jù)3.1 節(jié)的結論，考慮引入?yún)?shù)外信息增益損失比（GLR,gain loss ratio）對算法參數(shù)進行設計。令傳統(tǒng)算法和改進算法的IND 曲線交點為(x,y)，結合式(8)和式(9)，可得IND 的外信息損失量為

則IND 的外信息增益量為

在此基礎上，定義GLR 為

改進算法設計的初衷是使LT 碼達到足夠低的誤碼平臺，但是并不希望過度地壓縮譯碼收斂區(qū)，以致出現(xiàn)輸出外信息無法收斂至1 的情況。

現(xiàn)將改進算法的參數(shù)設計模型總結如下。給定固定信噪比、碼率值R以及校驗度分布Ω(x)。在區(qū)間(0,μ0]中設置D個等間隔μ分布的點，滿足μD-1＜μD-2＜ …＜μ1＜μ0，其中，μ0=floor(R-1)，floor 函數(shù)表示向下取整函數(shù)，并記間隔μ為第1 階段編碼步長。給定初始節(jié)點窗口探測范圍為[1,α]。需要說明的是，待設計參數(shù)為算法2 中的NP和Tv，但為了便于表述，將NP轉化為進行設計，這兩者是等同的。現(xiàn)希望輸出的是最優(yōu)的參數(shù)組合，故引入?yún)?shù)的第1 個約束條件如下。

約束條件1最優(yōu)參數(shù)組合應具有最大的GLR 值。記為

表2 給出了不同參數(shù)組合下的GLR 計算結果，其中，校驗度分布為Ω1(x)，R-1=2。

表2 改進算法在不同參數(shù)下的增益損失比

通過表2 的數(shù)據(jù)可以得出以下結論。

1) 窗口長度Tv的變化會引起GLR值的大范圍變動，而參數(shù)的變化則對GLR 值的影響有限。這是因為Tv的大小直接決定了小度數(shù)值信息節(jié)點的消除效果，也影響著信息節(jié)點的度分布和IND 曲線的走向，進而決定了GLR 值的大小。

2.2 節(jié)指出，直接反映編碼結果優(yōu)劣的是BER 下界，因此，有必要將BER 下界也作為改進算法參數(shù)的約束條件之一。此外，考慮到不同的通信場景對BER 的需求不同，應事先給定預期的BER 標準，且該標準可按實際情況進行調整，這也體現(xiàn)了本文改進算法的可控制性、可預測性。

現(xiàn)在，給定期望BER 標準為PE，引入?yún)?shù)的第2 個約束條件如下。

約束條件2最優(yōu)參數(shù)組合的BER下界應高于期望BER。記為

其次，綜合約束條件1，參數(shù)組合應具有最大GLR值，即滿足以下2 點。

1) 對于i∈[1,α]且i≠Tv(opt)，j∈(0,μ0]且，可存在某組參數(shù)使Pe(i,j)≤PE，但其不可滿足GLR (i,j)＞GLR

2) 對于i∈[1,α]且i≠Tv(opt)，j∈(0,μ0]且，可存在某組參數(shù)使增益損失比滿足，但其不可滿足Pe(i,j)≤PE。

對于上述求解模型，需要說明以下幾點。1)計算BER 下界和GLR 值時需要獲知信息度分布，為此，本文參考文獻[11]，采用多次蒙特卡羅仿真的方法，以獲取準確的信息度分布。2) 關于步長μ的設置。根據(jù)定義，μ=floor(R-1)/D。因此可以按照編碼需求取值，如將間隔段數(shù)D設置為10。3) 關于節(jié)點窗口長度的上限。2.3 節(jié)指出，Tv值不宜過大，因此，本文擬采用傳統(tǒng)算法的信息節(jié)點均值α作為上限。事實上，后續(xù)的設計結果也表明，最優(yōu)的Tv遠未達到均值α。

3.3 最優(yōu)參數(shù)的設計方法

3.2 節(jié)給出了參數(shù)設計的約束條件，即在所有滿足BER 標準的組合中，尋找GLR 值最大的一組作為最優(yōu)。但是，這樣的約束條件設計的結果可能存在2 個趨向性：易于向較大Tv值處靠攏、易于向較小值處靠攏。這是因為GLR 值的變化存在一定的規(guī)律性，會隨著Tv的增大而增大、隨著的減小而增大，這點從表2 中容易看出。

但是，在實際應用中，并不希望Tv值過大和值過小，主要有以下2 點原因。

1)Tv值越大，小度數(shù)值信息節(jié)點的消除效果越差。這是因為節(jié)點窗口長度越大，包含的不同度數(shù)信息節(jié)點越多，而校驗節(jié)點則是等概率地選取，因此，這就等效于降低了小度數(shù)值信息節(jié)點被選中的概率。換言之，當Tv值更小時，改進算法能夠更準確、更高效地消除小度數(shù)值信息節(jié)點。為了更直觀地展示，圖4 給出了不同度數(shù)信息節(jié)點隨校驗節(jié)點個數(shù)的變化情況。仿真參數(shù)為=0.2，R-1=2，校驗度分布為Ω1(x)。

從圖4 可以看出，①Tv值越小，消除效率越高。例如，當Tv=1時，每類信息節(jié)點的分布圖均比較陡峭；當Tv=6時，信息節(jié)點的分布圖則比較平緩，且拖尾很長。這說明，Tv值較小，則消除速度越快。②Tv值越小，消除效果越好。例如，當生成相同數(shù)目的校驗節(jié)點時，Tv=1中已經幾乎不存在度數(shù)為8 的信息節(jié)點了；而Tv=6中尚有剩余。

圖4 不同種類信息節(jié)點隨校驗節(jié)點個數(shù)的變化情況

基于上述2 條原因，設計結果實際上應向較小vT值、較大值處靠攏。因此，考慮更改3.2 節(jié)中的參數(shù)設計約束條件，不再以最大GLR 值作為篩選條件，而是以最大GLR 值為中心，劃定可選GLR 范圍，并尋找在此范圍內的最小Tv值、最大值的組合作為最優(yōu)組合。為此，引入GLR 半徑系數(shù)γ(0＜γ≤1)，并設計參數(shù)的第3 個約束條件如下。

約束條件3以最大GLR 值為中心、γGLRmax為半徑的范圍中，最優(yōu)參數(shù)組合的Tv應最小、應最大。

綜上所述，將基于3 個約束條件的算法參數(shù)設計模型改寫為算法3。按照算法3，給出了一組設計結果示例，如表3 所示。初始條件為采用的校驗度分布為Ω1(x)，期望BER 為PE=10-9，步長μ=0.2，半徑系數(shù)γ=0.85。

表3 由算法3 求解出的最優(yōu)參數(shù)組合

算法3求解最優(yōu)參數(shù)的算法

輸入期望BER 標準PE，步長μ，窗口長度初始范圍[1,α]，半徑系數(shù)γ。初始化m=1

輸出最優(yōu)的組合參數(shù)

1) 計算第m個節(jié)點窗口長度下，D個不同值對應的BER 下界，記為向量Pm。

2) 篩選出向量Pm中所有小于PE的值，記錄其對應的參數(shù)組合。計算這些參數(shù)組合對應的增益損失比，記為向量GLRm。

3) 若m＜α，令m=m+1。重復步驟1)和步驟2)，并記錄。若m=α，則進行步驟4)。

4) 從記錄的向量GLR1,…,GLRm中，尋找出最大的GLR 值，記為GLRmax。在上述向量中，尋找所有GLR 值大于γG LRmax的參數(shù)組合，并記錄。

5) 從4) 得到的所有組合中，以Tv值優(yōu)先的原則，篩選出Tv值最小、最大的組合。輸出該組合為

需要說明的是，表3 的結果只對所設置的初始條件來說是最優(yōu)的。而初始條件可以根據(jù)不同的通信需求進行調整。例如，若需要更低的BER，則可以將PE的值調得更低一些；若需要更精細的分布，則可以將的值調得更低一些；若對收斂性要求更高，則可將γ調高一些；若希望編碼效率更高、復雜度更低，則可將γ調得更小一些。總之，算法3 是綜合考慮了BER 性能、收斂性、小度數(shù)信息節(jié)點消除效率、編碼復雜度等因素在內的設計方法。因此，設計結果是一種折中選擇，可能不一定具有最低的BER 下界，但具備較穩(wěn)定、較全面的BER 性能。

4 仿真分析

本節(jié)對本文的改進LT 編碼算法進行仿真分析，并與其他幾種算法進行性能對比。為便于對照，記文獻[3]算法為傳統(tǒng)算法，文獻[15]算法為等度數(shù)（ED,equal degree）算法，文獻[17]算法為選擇連接（CC,connection choice）算法。仿真條件為發(fā)送端采用BPSK 調制方式，采用校驗度分布Ω1(x)，碼長K=2 048；接收端采用BP 迭代譯碼算法，最大迭代次數(shù)設置為50 次。所有的結果均通過500 000 次蒙特卡羅仿真得到。

4.1 不同參數(shù)組合時的BER 性能

1) 圖5 中，固定Tv不變，BER 隨著的減小而減小。這是因為，值越小，意味著節(jié)點分類窗口能夠及早地發(fā)揮作用，即在初始時就利用校驗節(jié)點去主動地連接至小度數(shù)值的信息節(jié)點；此外，值越小，則第2 階段的校驗節(jié)點越多，也就是能夠發(fā)揮降低誤碼平臺作用的校驗節(jié)點越多，從而達到更低的BER 下界。

3) 改變算法參數(shù)產生的BER 性能變化是可控的。例如圖6 中，當=1.8時，Tv為1 時可達最低BER，約為8×10-5，而Tv為5 時則達到最高BER，約為7×10-5，相差不大。如圖5 所示，無論Tv是何值，=0.2時均可達到最低BER，=1.8時達到最高BER，但兩者均保持在相同的數(shù)量級范圍內。因此，這驗證了3.3 節(jié)得出的結論：①可犧牲部分收斂性，以使參數(shù)組合向較小Tv值處靠攏；②在對BER 性能要求不高時，可以較大值獲取低編碼復雜度。

圖5 不同節(jié)點窗口長度時的BER 性能

圖6 不同值時的BER 性能

4.2 不同信噪比時的BER 性能

圖7 =0.2時，不同信噪比下的BER 性能

圖8 =1.6時，不同信噪比下的BER 性能

1) 改進算法能夠實現(xiàn)優(yōu)于傳統(tǒng)算法的BER 性能，達到了預期的設計目的。例如，當=2 dB時，改進算法可將誤碼平臺降低近4 個數(shù)量級。此外，當=0 dB 時，改進算法的BER 小于10-5，已經低于傳統(tǒng)算法在為2 dB 時的BER。由此，可認為改進算法至少能夠獲得2 dB 的編碼增益，這驗證了算法的正確性。

2) 通過優(yōu)化參數(shù)組合，改進算法能夠實現(xiàn)優(yōu)于CC 算法和ED 算法的性能。例如，圖7 中，當為0.2、Tv為5 時，改進算法的BER 性能并不優(yōu)于ED 算法。但是，將Tv調整至1 后，便具有了低于CC 算法和ED 算法的BER 下界。若以10-8為衡量標準，相比CC 算法和ED 算法，改進算法可獲得近0.5 dB、0.2 dB 的編碼增益，這也體現(xiàn)了本文算法的優(yōu)勢。

3) 通過調整參數(shù)組合，能夠調控改進算法的BER 下界。改進算法引入了可供調控的參數(shù)Tv和，因而具備較強的精準性，且能夠降低編碼復雜度，這點要優(yōu)于CC 算法和ED 算法。但是，需要說明的是，仿真結果顯示，無論采用何種參數(shù)組合，改進算法的BER 性能與理論BER 下界值始終存在一定的差距。例如，當=0.2、Tv為1 時，3 dB處的理論BER 下界值為1.91×10-10，但實際上改進算法的BER 只達到了4.88×10-9。不過，這是受限于編碼長度的結果，而不是算法的缺陷。理論BER值是基于無限長碼長的計算結果，但受限于編譯碼復雜度，仿真驗證時只能采用中短碼長。因此，不僅是改進算法，CC 算法和ED 算法也面臨著相同的問題，這實際上是不可避免的折中。總之，仿真結果已經驗證了算法的有效性和正確性，這也達到了預期目的。

4.3 不同碼率值時的BER 性能

圖9 =0.2時，不同碼率值下的BER 性能

圖10 1.6=時，不同碼率值下的BER 性能

1) 當固定信噪比不變時，改進算法依然能夠顯著地降低誤碼平臺。例如，當R-1=2 時，改進算法遠大于傳統(tǒng)算法的下界，因此，至少可節(jié)省30%的編碼開銷。

2) 改進算法的BER 性能要優(yōu)于ED 算法和CC算法。例如，當=0.2、Tv=1時，改進算法的BER 均低于上述2 種算法。此外，盡管改進算法在=1.6時的BER 性能有所降低，但仍具有更低的誤碼平臺。若以ED 算法的最低BER 值為參照，改進算法最多可節(jié)省近20%的編碼開銷，這也體現(xiàn)了改進算法的優(yōu)勢。

5 結束語

針對LT 碼在AWGN 信道中存在的嚴重誤碼平臺問題，本文設計了基于定長節(jié)點分類窗口的改進編碼算法。為了尋找合理的算法參數(shù)組合，以BER性能、收斂性、算法效率等為約束條件建立了參數(shù)設計模型。首先，設置參數(shù)探測范圍，以理論BER下界值為約束條件1，篩選出所有可達標準的參數(shù)組合。然后，引入了外信息增益損失比為約束條件2，尋找使GLR 值最大的參數(shù)組合，并以此為中心，將半徑范圍γ內的所有參數(shù)組合作為待選。最后，以算法效率和編碼復雜度為約束條件3，使設計結果優(yōu)先向較小節(jié)點窗口長度、較大編碼開銷值處靠攏，進而得出最優(yōu)參數(shù)組合。仿真結果表明，與傳統(tǒng)LT 碼相比，改進算法最高可將誤碼平臺降低3 個數(shù)量級；此外，改進算法也能夠實現(xiàn)優(yōu)于對比算法LT 碼的BER 性能。