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

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

1 引言

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

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

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

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

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

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

2 誤碼平臺(tái)分析及改進(jìn)的LT 編碼算法

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

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

圖1 LT 碼的Tanner

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

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

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

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

2) 從K個(gè)信息節(jié)點(diǎn)中，隨機(jī)選取d個(gè)。

3) 將上述d個(gè)信息節(jié)點(diǎn)的值進(jìn)行異或，作為第n個(gè)校驗(yàn)節(jié)點(diǎn)的值。

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

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

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

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

2.2 LT 碼的誤碼平臺(tái)分析

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

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

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

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

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

2.3 改進(jìn)的LT 編碼算法

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

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

算法2改進(jìn)的LT 編碼算法

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

1) 采用算法1 進(jìn)行編碼，生成NP個(gè)校驗(yàn)節(jié)點(diǎn)，記n=NP。

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

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

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

5) 將選中的d個(gè)信息節(jié)點(diǎn)進(jìn)行異或，作為當(dāng)前校驗(yàn)節(jié)點(diǎn)的值。

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

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

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

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

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

2.4 改進(jìn)算法的復(fù)雜度分析

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

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

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

表1 幾種算法生成N 個(gè)校驗(yàn)節(jié)點(diǎn)時(shí)的新增操作對比

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

3 改進(jìn)LT 編碼算法的分析與設(shè)計(jì)

3.1 改進(jìn)算法的收斂性分析

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

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

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

LT 碼IND 的EXIT 計(jì)算式為

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

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

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

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

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

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

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

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

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

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

則IND 的外信息增益量為

在此基礎(chǔ)上，定義GLR 為

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

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

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

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

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

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

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

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

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

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

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

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。

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

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

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

但是，在實(shí)際應(yīng)用中，并不希望Tv值過大和值過小，主要有以下2 點(diǎn)原因。

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

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

圖4 不同種類信息節(jié)點(diǎn)隨校驗(yàn)節(jié)點(diǎn)個(gè)數(shù)的變化情況

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

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

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

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

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

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

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

1) 計(jì)算第m個(gè)節(jié)點(diǎn)窗口長度下，D個(gè)不同值對應(yīng)的BER 下界，記為向量Pm。

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

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

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

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

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

4 仿真分析

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

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

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

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

圖5 不同節(jié)點(diǎn)窗口長度時(shí)的BER 性能

圖6 不同值時(shí)的BER 性能

4.2 不同信噪比時(shí)的BER 性能

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

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

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

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

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

4.3 不同碼率值時(shí)的BER 性能

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

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

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

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

5 結(jié)束語

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