程乃平, 宋 鑫, 廖育榮, 倪淑燕, 雷拓峰
(1.航天工程大學電子與光學工程系, 北京 101400; 2.航天工程大學研究生院, 北京 101400)
噴泉碼[1]最初是針對二進制刪除信道(binary erasure channel, BEC)設計的,旨在為大規(guī)模數據分發(fā)和可靠廣播場景提供一種理想的解決方案[2]。以盧比變換(Luby transform, LT)碼[3]為代表的噴泉碼,具有天然的信道自適應特性,可以靈活地產生任意數量的編碼符號,因此,無論信道刪除概率多大,發(fā)送端總能源源不斷地產生編碼數據直到接收端恢復出源數據。這使得它非常適合應用于傳輸視頻和音頻的廣播場景[4]、協(xié)作中繼場景[5]、水聲通信場景[6]、不等差錯數據保護場景[7-8]等。
盡管噴泉碼最初是面向BEC進行設計的,但其在加性高斯白噪聲(additive white gaussian noise, AWGN)信道中也具有潛在的應用前景[9-10]。文獻[11]研究結果表明,LT碼在二進制對稱信道(binary symmetric channel, BSC)和AWGN信道中存在明顯的誤碼平臺。文獻[12-15]考慮通過優(yōu)化校驗度分布來改善誤碼平臺。文獻[12]針對二進制輸入AWGN(binary input AWGN, BIAWGN)信道,提出以最大化LT碼的碼率值為目標函數,采用線性規(guī)劃的方法求解出最優(yōu)的度分布系數。文獻[13]針對極低信噪比條件提出了一種改進的度分布設計方式。文獻[14]給出了一種適用于大范圍信噪比的度分布函數策略,通過及時調整度分布函數以保持足夠高的碼率效率。文獻[15]針對系統(tǒng)LT碼,引入了誤比特率(bit error rate, BER)下界作為新的約束條件,實現了以更小的譯碼開銷進入瀑布區(qū)的效果。
但是,在BIAWGN信道中,通過優(yōu)化校驗度分布來提升BER性能,卻存在以下兩個問題:①度分布設計不可避免地引入了高斯噪聲方差作為初始條件,且僅對某一小范圍內的信噪比最優(yōu);②優(yōu)化的度分布函數改善誤碼平臺的效果有限,特別是在碼長較短時。
針對上述問題,現暫不考慮優(yōu)化度分布的問題,而是試圖通過改進LT碼的編碼算法來提升其BER性能。文獻[16]指出誤碼平臺主要是由不可靠的小度數值信息節(jié)點造成的。為此,文獻[16]提出了一種基于節(jié)點分類選取的改進編碼算法,這種算法使得幾乎所有的信息節(jié)點都具有了相同的度數值。文獻[17]則將文獻[16]的編碼思想應用到了不等差錯保護場景中,以略微增加譯碼開銷為代價,將最重要數據(most important bits, MIB)的BER平臺降低了將近3個數量級。文獻[18]的改進算法,是在校驗節(jié)點選擇每個信息節(jié)點時,都先從所有的信息節(jié)點中隨機選取T個節(jié)點作為一組,然后再從這一組中選擇度數最小的信息節(jié)點進行連接。需要說明:文獻[17]中改進算法對BER性能的提升程度取決于額外引入的參數T,但是卻沒有給出關于該參數的嚴謹設計方法。相較于文獻[18],文獻[19]的改進算法則引入了更多的參數,如衡量校驗節(jié)點度數值大小的參數d*。若當前校驗節(jié)點的度數大于d*,則將優(yōu)先連接至小度數值的信息節(jié)點;若度數小于d*,則仍從所有的信息節(jié)點中隨機選??;若等于d*,則依據預先給定的權重確定選取方法。仿真結果顯示,這幾種改進算法在BEC或者AWGN信道中都能夠使LT碼更快地進入BER瀑布區(qū),并能顯著地降低誤碼平臺。
但是這幾種改進算法也存在下述問題:①沒有給出算法所涉及參數的選取原則;②算法的編碼過程不具備可調控性;③缺乏對算法收斂性的分析。
針對上述問題,現設計一種面向AWGN信道的改進LT編碼算法。引入可變的閾值對信息節(jié)點進行分類,將度數值相對較小的信息節(jié)點聚集在一起,并強迫這些節(jié)點頻繁地連接至校驗節(jié)點,從而使其獲得足夠可靠的度數值。首先,分析誤碼平臺的成因,設計閾值遞增的節(jié)點按序消除編碼算法。其次,計算改進算法的理論BER下界,分析不同參數對改進算法BER性能的影響。最后,分析改進算法對LT碼收斂性的影響,并指出算法參數的選取原則。改進算法能夠顯著地降低LT碼的誤碼平臺,實現優(yōu)于文獻[16-18]的BER性能。
對于傳統(tǒng)LT碼,編碼器會對K個信息節(jié)點v={v1,v2,…,vK}進行編碼,生成N個校驗節(jié)點c={c1,c2,…,cN},且N個編碼節(jié)點與校驗節(jié)點一一相連。LT碼的Tanner圖如圖1所示。
圖1 LT碼的Tanner圖Fig.1 The Tanner graph of LT codes
算法1 傳統(tǒng)LT碼的編碼算法
(1)
根據文獻[11]可知,傳統(tǒng)LT碼的信息度分布可以看作以α為均值的泊松分布,即
(2)
(3)
(4)
在AWGN信道中,LT碼采用置信傳播(belief propagation, BP)算法進行迭代譯碼。該算法將對數似然比(log-likelihood ratio, LLR)信息在信息節(jié)點和校驗節(jié)點之間進行迭代更新,使LLR信息逐漸收斂于穩(wěn)定值并據此進行最佳判決。
令Lcj→vi表示迭代過程中第j個校驗節(jié)點傳遞給第i個信息節(jié)點的LLR信息,定義為
(5)
(6)
式(6)中:N(i)(j)為除第j個校驗節(jié)點之外,與第i個信息節(jié)點相連的所有校驗節(jié)點的集合。
對于信息節(jié)點vi,其LLR判決值為
(7)
當達到最大迭代次數后,采用式(8)對比特值進行判決:
(8)
傳統(tǒng)LT碼在生成度數為d的校驗節(jié)點時,是隨機選取d個信息節(jié)點進行異或,在這種方式下得到的信息節(jié)點度分布近似服從泊松分布。然而,從式(1)和式(2)中可以看出,即使α足夠大時,小度數值信息節(jié)點(包括度數為0的節(jié)點)存在的概率仍不為零。因此,可以預測在大量重復試驗時,必然還會出現一定數量的小度數值信息節(jié)點,這些節(jié)點所連接的校驗節(jié)點很少,在譯碼過程中往往無法獲得足夠多的來自校驗節(jié)點的LLR信息,因此,很難對自身的比特值進行正確判決,可靠性較低。
針對這個問題,擬對傳統(tǒng)編碼算法進行改進,以消除小度數值的信息節(jié)點,進而提升LT碼的BER性能[21]。考慮以更直接的控制方式,即引入一個閾值,用于篩選出度數值小于該閾值的信息節(jié)點,并迫使這些節(jié)點頻繁地參與校驗節(jié)點的生成,從而使其獲得足夠可靠的度數值。此外,閾值是可變的,因此,可以保證改進算法持續(xù)發(fā)揮作用,按序消除低度數的信息節(jié)點,且能夠便捷地控制信息節(jié)點能夠達到的最小度數值。
具體而言,將編碼過程分為兩個階段。第一個階段,利用可變的閾值篩選出待編碼的信息節(jié)點并動態(tài)更新,在生成校驗節(jié)點時,只能從這些信息節(jié)點中選取。第二個階段,當閾值達到給定的上限時,恢復為傳統(tǒng)編碼算法。編碼過程如算法2所示。
算法2 改進的LT編碼算法
所提出的改進算法的優(yōu)點有以下幾個方面。
(1)能夠精準地消除小度數值的信息節(jié)點。算法2引入閾值,在每個校驗節(jié)點生成之前,將所有可靠性較低,即度數值相對較小的信息節(jié)點匯聚在一起,從而使得這些節(jié)點能夠始終優(yōu)先連接至更多的校驗節(jié)點。此外,在第一階段的編碼過程中,閾值是遞增的,因此,能夠確保所有的低度數值信息節(jié)點均被按序消除,不存在遺漏。
(2)能夠靈活地調整信息節(jié)點能夠達到的最低度數值。從算法2中可看出,編碼后的信息節(jié)點最小度數值即為閾值上限,因此,可以通過改變閾值上限,調整信息節(jié)點的度數值下界,進一步可以借此預測算法的BER性能。這可以利用極限思維分析:若Tv為0,則所有的信息節(jié)點都將被無差別地選取,改進算法將退化為傳統(tǒng)的編碼算法,且仍然保持較高的誤碼平臺。若Tv的值較為合理,則度數值相對較小的信息節(jié)點就能始終被高概率地選取,從而獲得不小于Tv的度數值。
需要說明的是,通過改變閾值上限并非能夠無限制地增大信息節(jié)點的度數值。這是因為,隨著編碼的進行,信息節(jié)點的度數會不斷地向閾值上限處累積,這會造成某一種度數值的信息節(jié)點大量聚集。在這種情況下,若要再提高這些信息節(jié)點的度數值,將耗費更多的校驗節(jié)點。但是,通信系統(tǒng)往往期望能以最小的譯碼開銷實現成功譯碼,因此,校驗節(jié)點的個數不能無限制地增大,這就限制了信息節(jié)點度數值的提升。
相較于傳統(tǒng)算法,本文算法增加了分類信息節(jié)點的操作,因而不可避免地增加了算法的復雜度,下面對其進行詳細分析。
傳統(tǒng)LT編碼算法中,關鍵步驟包括:①依概率選取校驗度數d;②隨機選取d個信息節(jié)點;③將選中的d個信息節(jié)點進行異或。對比算法2可知,本文算法主要對傳統(tǒng)算法的第二步進行了改動,而在選取校驗度數和求異或值時,與傳統(tǒng)算法完全相同。因此,現重點分析信息節(jié)點的選取方式對編碼復雜度的影響。
算法2中,每個校驗節(jié)點選取信息節(jié)點時,新增操作為:節(jié)點按度數值大小排序、度數值d和閾值大小比較。但是,當閾值達到上界Tv時,便不再進行這兩種操作。類似地,文獻[16]中的改進算法增加的操作為:節(jié)點按度數值大小排序、度數值d和每種度數節(jié)點個數大小比較。文獻[18]中的改進算法增加的操作為:隨機選取T個節(jié)點、節(jié)點按度數值大小排序、已選信息節(jié)點和當前所選信息節(jié)點的序號比較。表1給出了上述幾種算法在生成N個校驗節(jié)點時,所產生的新增操作及其次數。
表1 生成N個校驗節(jié)點時的新增操作對比Table 1 Comparison of new operations when generating N check nodes
對于三種改進算法而言,生成每個校驗節(jié)點時需對信息節(jié)點按度數值大小進行排序,這必然會增加編碼復雜度。以歸并排序算法為例,在本文算法和文獻[16]算法中,其平均時間復雜度均為O(Klog2K)。但本文算法的排序、數值對比次數均不超過文獻[16]算法,因此,本文算法的編碼復雜度要低于文獻[16]算法,但兩者均高于傳統(tǒng)算法。對于文獻[18]算法而言,其平均時間復雜度為O(Tlog2T),其中T為該算法中的參數且T 表2給出了三種改進算法的編碼運行時間。設計仿真次數為2 000次,K=512,N=1 024。其中,本文算法閾值上界Tv=10,文獻[18]算法中T=3??梢钥闯?,與傳統(tǒng)算法相比,三種改進算法的平均編碼運行時間均增加了。但本文算法的運行速度則相對較快,這與上述分析結果相一致,也體現了本文算法的優(yōu)勢。 表2 不同算法的平均運行時間Table 2 Average running time of different algorithms 評價LT碼的好壞,通常從BER性能和收斂性兩方面進行考慮[12]。文獻[16]中指出,在BIAWGN信道中,傳統(tǒng)LT碼的平均BER的下界可表示為 (9) 從式(9)中可以看出,LT碼的BER下界只與信息節(jié)點的度分布有關,因此,在設計改進的編碼算法時,一般只需要考慮信息節(jié)點的分布情況即可。為了觀察改進算法對誤碼平臺的影響,仿真了不同參數下的理論BER下限,結果如圖2所示。仿真采用的碼率值為1/2,度分布為文獻[22]中為K=512設計的校驗度分布,記為Ω1(x)。 從圖2中可以看出,改進算法能夠顯著地降低LT碼的誤碼平臺,并且,當閾值上限增加時,BER性能也會隨之提升,這驗證了算法的有效性。 圖2 改進算法的BER下界Fig.2 The BER lower bound of the improved scheme 需要說明的是,這僅僅是理論計算結果,可能會與實際仿真結果存在一定的差距,主要有以下兩點原因:①有限碼長引起的損耗,式(9)是針對碼長無限長時的計算情況,因此,當采用中短碼長時,實際的BER性能可能會有所損耗,且碼長越短,與理論BER下限之間的差距越大;②度分布改變造成的差距,傳統(tǒng)算法的信息度分布近似服從泊松分布,而改進算法的度分布則無明顯的規(guī)律,因此,采用式(9)直接計算BER時可能會造成偏差。 改進算法改變了信息節(jié)點的選取方式,但是并不希望出現無法收斂導致譯碼失敗的情況,因此,對改進LT碼的收斂性進行分析。 LT碼在AWGN信道中采用BP算法進行迭代譯碼,分析LT碼譯碼收斂性常用的工具為外信息傳遞(extrinsic information transfer, EXIT)圖法。參照文獻[23-24],定義單調遞增函數J(θ)為 (10) 式(10)中:ε為積分變量;σ為噪聲N的標準差;J(θ)具有唯一的反函數為θ=J-1(I)。關于J(·)和J-1(·),文獻[25]中給出了一種近似的計算方法。為便于分析,將LT碼的譯碼器分為校驗節(jié)點譯碼器(check node decoder, CND)和信息節(jié)點譯碼器(information node decoder, IND)。在BIAWGN信道下,LT碼CND的EXIT公式為 (11) LT碼IND的EXIT公式為 (12) 式(12)中:σI為來自CND的先驗信息的標準差,σI=J-1(IA,I),IA,I為信息節(jié)點的輸入先驗信息。 本文中的改進算法會改變信息節(jié)點的度分布,但不改變校驗度分布。因此,令改進算法的IND的EXIT公式為 (13) 式(13)中:λi(S)為改進算法的信息節(jié)點邊的度數分布;dv(S)為改進算法的最大信息節(jié)點度數值。 圖3 改進算法和傳統(tǒng)算法的收斂性對比Fig.3 The convergence comparison between the improved algorithm and the conventional algorithm 在圖3中,定義CND曲線和IND曲線之間的空隙為“譯碼收斂區(qū)”。理論上而言,如果兩條曲線沒有交點,那么當碼長K足夠長時,譯碼器總可以經過有限次迭代成功恢復出源信息,圖3中的階梯即為迭代軌跡??梢钥闯?,仿真結果與分析結論吻合。即改進算法的CND曲線與傳統(tǒng)算法的CND曲線會重合,而兩者的IND曲線則存在1個或多個交點。這說明在不同的先驗信息IA,I條件下,改進算法和傳統(tǒng)算法的輸出外信息差值正負不定,可以直觀地理解為:譯碼收斂區(qū)在不同位置會出現拓寬和壓縮的情況。 若改進IND曲線位于下方,表明改進算法損失了一定量的外信息,譯碼收斂區(qū)被壓縮;若改進IND曲線位于上方,表明改進算法獲得了額外的外信息增益,譯碼收斂區(qū)被拓寬。當信噪比較低,或者碼率值較小時,壓縮現象會更為明顯,嚴重時會導致算法無法成功收斂。這意味著,改進算法是以略微損失收斂性為代價,換取了誤碼平臺的大幅度降低。因此,為改進LT碼仍能成功譯碼,應合理設計閾值上限以確保:①譯碼收斂區(qū)是打開的;②被壓縮的區(qū)域不應過窄。這為改進算法的設計指明了一條原則。 為驗證本文算法的有效性,對改進LT編碼算法的性能進行仿真分析,并與傳統(tǒng)算法、參考文獻算法進行對比。為便于對照,記文獻[15]中的算法為等度數(equal degree, ED)算法。仿真條件為:發(fā)送端采用BPSK調制方式,采用校驗度分布Ω1(x),碼長K=512;接收端采用BP迭代譯碼算法,最大迭代次數設置為50次。所有的結果均通過500 000次蒙特卡洛仿真得到。 圖4 R-1=2時,不同閾值上限時的BER性能Fig.4 The BER performance at different upper bounds of the threshold when R-1=2 圖5 信噪比為1 dB時,不同閾值上限時的BER性能Fig.5 The BER performance at different upper bounds of the threshold when SNR=1 dB (1)改進算法存在明顯的瀑布區(qū)。從2.1節(jié)中得知,傳統(tǒng)算法存在明顯的誤碼平臺,即當BER達到某一界限時,繼續(xù)增加信噪比或者增大譯碼開銷,均不能使BER產生明顯的降低。但是,從圖4中可以看出,與信噪比為2 dB相比,3 dB時的BER下降了近兩個數量級;類似的,圖5中,相比于R-1=2.2,R-1=2.3時的BER也降低了近兩個數量級。這意味著,增大信噪比和譯碼開銷時,改進算法能夠實現BER的瀑布式下降,從而顯著地提升了LT碼的性能,這也驗證了算法的正確性。 (2)提高閾值上限,能夠提升算法的BER性能。這是因為,提高閾值上限時,改進算法能夠達到的最低信息節(jié)點度數值也隨之提升。這意味著,可靠性較低的信息節(jié)點越來越少,因此,誤碼平臺將會進一步降低。這與2.3節(jié)中的結論一致。 圖6 改進算法在不同信噪比時的BER性能Fig.6 The BER performance of the improved algorithm at different SNRs 圖7 改進算法在不同碼率值時的BER性能Fig.7 The BER performance of the improved algorithm at different code rates (2)改進算法的BER性能,隨著的Tv增加而提升。這與3.1節(jié)中的結論完全一致,此處不再贅述。 (3)通過合理設置參數,改進算法能夠實現優(yōu)于參考文獻算法的性能。例如,圖6中當Tv=7時,改進算法與ED算法的性能相近,但當Tv=10時,改進算法的性能便明顯優(yōu)于ED算法。類似的,在圖7中,盡管Tv為7和8時,BER性能不及ED算法,但當Tv為10時,便可獲得低于ED算法的BER下界,這也體現了本文算法的優(yōu)勢。 針對LT碼在AWGN信道中存在的嚴重誤碼平臺問題,設計了一種改進的編碼算法。主要思想是對信息節(jié)點進行分類篩選,并迫使度數值最小的一類信息節(jié)點優(yōu)先參與編碼,從而達到了消除低度數值信息節(jié)點的目的。通過理論推導和仿真分析,可得出以下結論。 (1)改進算法能夠顯著地降低LT碼的誤碼平臺。在本文中仿真條件下,與傳統(tǒng)算法相比,改進算法可將BER下界降低近3個數量級,并獲得近3.5 dB的編碼增益。 (2)可以通過改變閾值上限,調整改進算法的BER性能。當閾值上限較大時,算法的持續(xù)效果會更久,可靠性較低的信息節(jié)點會被不斷地消除,從而進一步地降低了誤碼平臺。這為合理地設置算法參數提供了依據。 (3)改進算法能夠實現優(yōu)于參考文獻算法的BER性能。當閾值上限較小時,改進算法的BER性能差于ED算法;但通過調整參數,改進算法總可以達到優(yōu)于ED算法的BER下界,體現了本文算法的優(yōu)勢。 (4)改進算法的收斂性略有損失。算法規(guī)定了校驗節(jié)點必須選取度數值靠前的信息節(jié)點,這會在一定程度上破壞LT碼的隨機性,且不利于快速收斂。因此,下一步研究中可以考慮設計具有無損收斂性的編碼算法。2.3 改進算法的BER性能分析
2.4 改進算法的收斂性分析
3 仿真結果
3.1 不同參數對算法性能的影響
3.2 傳統(tǒng)算法與改進算法的性能對比
4 結論