李 杰

無線傳輸中短碼長噴泉碼的度分布優(yōu)化算法*

李 杰**

（上海工程技術(shù)大學(xué)高等職業(yè)技術(shù)學(xué)院，上海 200437）

數(shù)字噴泉碼是針對大規(guī)模網(wǎng)絡(luò)數(shù)據(jù)分發(fā)而提出的一種新的信道編碼方式。度分布是決定數(shù)字噴泉碼譯碼性能的關(guān)鍵因素。為提高譯碼性能，針對應(yīng)用于無線信道的噴泉碼提出了一種度分布優(yōu)化的算法。首先，根據(jù)理想孤子分布和魯棒孤子分布產(chǎn)生度值序列，然后將該度值序列截短，在此基礎(chǔ)上根據(jù)優(yōu)化算法求解該序列中每個度值的最優(yōu)概率，最后得到優(yōu)化的度分布。仿真結(jié)果表明，本算法產(chǎn)生的度分布進(jìn)行編譯碼產(chǎn)生的誤碼率低于魯棒孤子分布和固定度分布，提高了譯碼性能。

無線傳輸；信道編碼；數(shù)字噴泉碼；LT碼；度分布；優(yōu)化算法

1　引 言

無線傳輸中為了對抗噪聲干擾和信道變化，通常采用自動重傳請求（Automatic Repeat Request，ARQ）來實現(xiàn)數(shù)據(jù)在無線通信網(wǎng)絡(luò)中的可靠傳輸。然而ARQ技術(shù)要求系統(tǒng)中有反饋信道，在很多情況下系統(tǒng)中不存在反饋信道，比如廣播信道。即使存在反饋信道，當(dāng)用戶數(shù)量較多時，大量用戶的反饋數(shù)據(jù)將形成“反饋風(fēng)暴”，甚至導(dǎo)致網(wǎng)絡(luò)癱瘓。

噴泉碼是一種新型的前向信道編碼［1］。對于給定的輸入信號，發(fā)送端可以按照接收端的需要生成任意數(shù)量的編碼包，接收端只要接收到其中任意足夠的編碼包就能譯碼得出源數(shù)據(jù)包，并且不用考慮接收順序問題，因此噴泉碼也被稱為無碼率編碼。噴泉碼只要接收到充足的數(shù)據(jù)，即便數(shù)據(jù)的順序是混亂的，接收機(jī)也可以正確地解碼恢復(fù)源數(shù)據(jù)。噴泉碼不依賴反饋信息的特點很適合在無線信道中傳輸。

2002年，Luby［2］提出了第一個實用數(shù)字噴泉碼LT碼（Luby Transform Codes）。該編碼算法簡單，具有較低的運算復(fù)雜度，編碼性能主要由度分布決定。在文獻(xiàn)［2］中Luby也提出了構(gòu)造度分布的方法并且設(shè)計了兩種實用的度分布，即理想孤子分布（Ideal Soliton Distribution）和魯棒孤子分布（Robust Soliton Distribution）。這兩種度分布在數(shù)據(jù)包較大時譯碼性能較好，當(dāng)數(shù)據(jù)包長度趨于無窮時，譯碼性能也接近最優(yōu)；數(shù)據(jù)包長度較小時，由于實際度分布常常不滿足度分布函數(shù)，因而譯碼失敗概率較高，譯碼性能下降。針對這一問題通?？梢酝ㄟ^接收更多的碼字來完成譯碼，但增加碼字需要較多的內(nèi)存和CPU資源，在一些資源受限的場合并不適用，比如無線多媒體傳輸中移動設(shè)備的內(nèi)存和CPU資源就相對有限［3-4］。針對這一問題，本文對短數(shù)據(jù)包應(yīng)用環(huán)境下度分布的優(yōu)化進(jìn)行了研究。

度分布的優(yōu)化方面已有一些研究成果。文獻(xiàn)［5］提出了利用馬爾科夫鏈優(yōu)化度分布的算法，通過遞歸算法對最大長度達(dá)到20個塊的信息包推導(dǎo)出了最優(yōu)的度分布；該算法復(fù)雜度較高。文獻(xiàn)［6］提出了改進(jìn)的魯棒孤子分布，通過調(diào)整度分布中1度值和2度值的選擇概率，降低方差，增加譯碼成功概率；該算法只對度值1和度值2的選擇概率進(jìn)行了調(diào)整，沒有優(yōu)化其他度值的選擇概率。文獻(xiàn)［7］中采用斐波那契數(shù)列作為度值序列，將度值的選取概率看作是判決變量，將譯碼性能看作是優(yōu)化目標(biāo)，求解能夠使譯碼性能最優(yōu)的度分布。文獻(xiàn)［8］提出了對不同碼長的輸入源進(jìn)行度分布優(yōu)化的實際架構(gòu)。文獻(xiàn)［9］提出了一種適用于反饋噴泉碼的基于部分信息度分布構(gòu)造方法。針對無線傳輸，本文研究了短噴泉碼的度分布優(yōu)化算法，通過縮小度值的取值范圍和優(yōu)化度值的選擇概率得到適合短噴泉碼的度分布。

2　LT碼

當(dāng)譯碼器接收到N個碼字y1，y2，…，yN后開始譯碼，N≈k。首先在接收到的碼字中尋找度為1的碼字yi，令譯碼器輸出xi=yi，然后對所有與xi相接的yi進(jìn)行異或運算，yj=yj⊕xi并與xi相接的節(jié)點度值減1。重復(fù)上述步驟直到所有xi都恢復(fù)。如果沒有度值為1的碼字或存在未被恢復(fù)的碼字，則說明接收端必須接收更多的碼字才能完成譯碼。LT碼編碼或譯碼k個碼字大概需要進(jìn)行klgk次異或運算。

3　度分布

噴泉碼的度分布設(shè)計是決定譯碼性能的關(guān)鍵，在編碼過程中度值的選擇至關(guān)重要，它決定了有多少輸入碼字用于產(chǎn)生一個輸出碼字。一旦度值被確定，相應(yīng)的個數(shù)的輸入符號被隨機(jī)挑選出來進(jìn)行異或。一個好的度分布能使接收端用盡可能少的接收符號和盡可能小的復(fù)雜度恢復(fù)出原始信息。噴泉碼譯碼的開始取決于接收信息中d=1節(jié)點的分布，之后如果在迭代過程中可持續(xù)產(chǎn)生d=1節(jié)點，譯碼就可以順利開展。通常大部分的節(jié)點的度值應(yīng)該較小，以減少譯碼整體的冗余運算并保證譯碼過程的持續(xù)進(jìn)行；少量節(jié)點應(yīng)該度值較大，以增加迭代更新提高正確性。

3.1理想孤子分布

Luby提出的理想孤子分布是噴泉碼最理想的度分布。每次迭代譯碼都保證恢復(fù)出一個符號，并產(chǎn)生一個新的d=1的節(jié)點，這樣既保證了譯碼的順利進(jìn)行又使得譯碼運算次數(shù)最少。該分布定義如下：

式中：d表示度值；ρ（d）表示度值d的選擇概率。

但是在實際應(yīng)用中，由于數(shù)據(jù)長度有限，編碼時度分布無法精確符合理想分布，因此在解碼過程中很容易丟失d=1的節(jié)點，導(dǎo)致譯碼無法開始，或是在后續(xù)迭代中無法產(chǎn)生新的d=1的節(jié)點導(dǎo)致譯碼失敗。因此，Soliton分布實際性能并不夠理想。

3.2魯棒孤子分布

由于理想孤子分布的不足，Luby提出了改進(jìn)的度分布，也就是魯棒孤子分布。魯棒孤子分布定義如下：

式中：參數(shù)c和δ是兩個大于0的參數(shù)，用來保證在譯碼過程中d=1的節(jié)點數(shù)量能夠達(dá)到期望值。該分布有效地結(jié)合理想孤子分布的的優(yōu)點，只需k+個編碼碼字就可以以至少1-δ（δ∈（0，1］）的概率正確恢復(fù)出原碼字［2］。

4　無線信道中的度優(yōu)化

Luby提出的理想孤子分布和魯棒孤子分布采用隨機(jī)方式進(jìn)行編碼，通常在數(shù)據(jù)包達(dá)到104或更高量級時才能取得良好的編譯碼性能，而在無線信道中數(shù)據(jù)包較短，使得編碼符號的實際度分布與設(shè)定的度分布很可能不一致，從而導(dǎo)致譯碼的失敗。針對這一問題，本文提出了針對短噴泉碼的度分布優(yōu)化算法，通過縮小度值的取值范圍和優(yōu)化短數(shù)據(jù)輸入條件下度值的選擇概率得到適合短噴泉碼的度分布。

為了確保接收端接收到最少的數(shù)據(jù)后就可以成功解碼，需要每個編碼碼字?jǐn)y帶的信息對接收端而言都是有用的，因此要求度值較高；而在譯碼中BP算法中需要度值為1的編碼碼字，因此度值越低，度為1的碼字出現(xiàn)概率也就越大，譯碼成功率越大，因此要求度值越低越好。這兩個條件對度的要求相互矛盾，因此度分布的設(shè)計需要均衡這兩者的要求，尋找折衷的方案［10］。本文提出了一個適合于不同輸入信號的度值選擇算法，以獲得更好的譯碼性能。

理想孤子分布或魯棒孤子分布中度值的取值范圍從1到k，dI∈DI，DI=｛1，2，…，k｝，其中k是輸入數(shù)據(jù)長度，DI是度值的集合。當(dāng)數(shù)據(jù)較長時，就會產(chǎn)生較大的度值，同時該度值的選擇概率很小。以k= 2 000為例，大于500的度值對應(yīng)的概率只有10-6量級，該度值被選擇用來編碼的可能性很小，可以忽略不計。因而需要縮小度值的范圍，截短度值序列。定義概率門限p1將理想孤子分布或魯棒孤子分布的每個度值對應(yīng)的選擇概率和門限相比較，如果一個度值dI的選擇概率大于門限，即ΩI（dI）＞p1，其中Ω表示概率，ΩI（dI）表示度值dI被選擇概率，那么該度值被保留，否則將該度值從DI中刪除。由于這兩種分布在度值較大區(qū)域是遞減函數(shù)，因此當(dāng)某個度值的選擇概率小于給定門限后，比該度值大的其余度值對應(yīng)的概率也一定小于門限，這些度值都將刪除，度值集合也被截短。將截短的度值集合表示為dt∈Dt，Dt=｛1，2，…，m｝，m

綜上所述，度值選擇算法的主要步驟如下：

第1步 初始化參數(shù)p1，p2，w，累加概率s=0和目標(biāo)度值集合D=｛｝；

第2步 對給定的數(shù)據(jù)長度產(chǎn)生理想孤子分布（或魯棒孤子分布）ΩI（dI），dI∈DI；

第3步 根據(jù)門限p1對度值集合進(jìn)行截短，得到Dt；

第4步 將Dt中的度值所對應(yīng)的概率ΩI（dt），dt∈Dt和門限p2相比較，如果概率大于門限，跳至第5步；如果概率小于門限，則

（1）計算加權(quán)概率和s=s+ΩI（dt）×w，將s和門限p2比較；

（2）如果大于門限，將dt加入目標(biāo)度值集合；否則，檢查下一個度值dt+1；

（3）重復(fù)上兩步直到s≈p2；

第5步 將當(dāng)前的度值加入到目標(biāo)度值集合中并置概率和s=0；

第6步 重復(fù)第4～5步，檢查Dt中其余的度值，直到所有度值都檢查完畢。

在該算法中p1用來截短度值序列。如果p1=0，那么所有初始的度值都會被保留下來Dt=DI。p1越大，被刪除的度值越多，保留的度值越少。同時由于去除了部分度值，因此截短后的度值集合Dt中所有度值的概率和小于1。但是，由于刪除度值的概率非常小，因此Dt中所有度值的概率和可以近似為1。比如當(dāng)k=1 000、p1=0.000 1時，所有保留的度值的概率和為0.991；k=4 000、p1=0.000 1時，所有保留的度值的概率和為0.990 2。門限p2的選擇同樣影響最終的度值集合，p2越大，被刪除的度值越多，保留的度值越少，目標(biāo)度值集合越小。

根據(jù)上述算法確定度值后，每個度值的選擇概率也相應(yīng)確定，但此時的概率一定不是最優(yōu)的，還要進(jìn)一步對概率分布進(jìn)行優(yōu)化。在無線信道傳輸中，由于傳輸錯誤，LT譯碼端通常不能將所有碼字正確譯碼。因此度概率分布的設(shè)計目標(biāo)是獲得一組最優(yōu)的概率分布，使得接收端可以以最小的開銷恢復(fù)出最多的碼字。這個問題可以轉(zhuǎn)化為在給定開銷OB的條件下，求解能夠使譯碼碼字最多的概率分布：

式中：ber（Ω，d）是該概率分布條件下的誤碼率；O是開銷。上式所表示的最優(yōu)化問題可以通過全局搜索求解，例如可以使用進(jìn)化策略搜索最優(yōu)的概率分布。

5　實驗結(jié)果

度分布優(yōu)化算法的實驗分為兩步。首先，根據(jù)度值算法確定合理的度值，以輸入數(shù)據(jù)k=300為例進(jìn)行實驗，選取不同的門限時，得到的度值不同：

確定度值后再對度值的概率分布進(jìn)行優(yōu)化，就能夠得到在該度值集合下最優(yōu)的譯碼性能。

第二步，求解度值集合中度值的最優(yōu)選擇概率，得到優(yōu)化的度分布。將本算法優(yōu)化得到的度分布的譯碼性能和固定度值分布以及魯棒孤子分布的性能進(jìn)行了比較。其中固定度值分布是一種使用較為廣泛的度分布［12］，相應(yīng)的多項式為

該度值分布具有較好的譯碼性能。

本文分別在固定數(shù)據(jù)包長度和固定譯碼開銷的條件下對算法的譯碼性能進(jìn)行了測試。根據(jù)Luby的算法，魯棒孤子分布中的參數(shù)c和δ分別取0.5和0.03［2］。設(shè)定度值的最優(yōu)選擇概率算法迭代200次。由于無線信道上數(shù)據(jù)包較短，不失一般性的定義固定數(shù)據(jù)包的比特長度為1 000。不同開銷條件下的譯碼性能如圖1所示，其中橫坐標(biāo)的譯碼開銷表示發(fā)送端實際發(fā)送的數(shù)據(jù)包與源數(shù)據(jù)包的比值，縱坐標(biāo)表示此條件下的誤碼率。從圖1可以看出隨著譯碼開銷的增大，誤碼率減小，同時在相同開銷下，本算法得到的度分布編碼后的誤碼率低于魯棒孤子分布和固定度分布，具有最好的譯碼性能。圖2還在譯碼開銷為1的條件下對不同長度的編碼包進(jìn)行了測試，從圖中可以看出此時本算法得到的度分布編碼優(yōu)于魯棒孤子分布和固定度分布。由于誤碼率隨著譯碼開銷的增大而減小，當(dāng)譯碼開銷較大時，本算法的優(yōu)勢不明顯；在開銷較小時，短碼長噴泉碼使用本文的優(yōu)化算法能夠得到更好的譯碼性能。

圖1　不同開銷條件下譯碼性能比較Fig.1　BER of different algorithms versus decoding overhead

圖2　不同數(shù)據(jù)長度條件下譯碼性能比較Fig.2　BER of different algorithms versus data length

通常傳輸?shù)男畔⒉痪哂型鹊闹匾?，比如無線網(wǎng)絡(luò)中控制信號要比用戶數(shù)據(jù)更重要。而無線通信是一個噪聲信道，因此為了保護(hù)傳輸數(shù)據(jù)中更重要的那部分信息通常采用不等差錯保護(hù)的傳輸方式。本文也測試了在不等差錯保護(hù)的傳輸模式下優(yōu)化后的度分布的譯碼性能。不等差錯保護(hù)采用的是基于噴泉碼的擴(kuò)展窗方案［13］，根據(jù)該保護(hù)方案，按照重要性將數(shù)據(jù)分為兩個等級，重要數(shù)據(jù)和非重要數(shù)據(jù)，其中重要數(shù)據(jù)占總數(shù)據(jù)的25%。在此平臺上對固定分布、魯棒孤子分布和本文所提的優(yōu)化分布的譯碼性能分別進(jìn)行了測試，如圖3所示，可以看出在不等差錯保護(hù)的編碼平臺下本文的算法同樣具有最好的譯碼性能。圖4顯示了不等差錯保護(hù)條件下，重要數(shù)據(jù)在不同開銷條件下譯碼后的誤碼率，可以看出由于得到了更多的保護(hù)，這部分?jǐn)?shù)據(jù)的誤碼率較低，同時本文的算法得到的誤碼率也是所比較算法中最低的。

圖3　不等差錯保護(hù)條件下譯碼性能比較Fig.3　BER of different algorithms versus decoding overhead under unequal error protection

圖4　不等差錯保護(hù)條件下重要數(shù)據(jù)譯碼性能比較Fig.4　BER of important data versus decoding overhead under unequal error protection

本算法由度值的確定和度分布的優(yōu)化兩部分組成，其中度值的確定計算量很小，度分布的優(yōu)化計算量較大，算法的復(fù)雜度主要集中在度分布的優(yōu)化部分。當(dāng)數(shù)據(jù)包長度為1 000 b時在2.7 GHz Intel i5處理器的計算機(jī)上對不同迭代次數(shù)的耗時和誤碼率進(jìn)行測試，結(jié)果見表1?？梢钥闯龆戎颠x擇算法的復(fù)雜度和迭代次數(shù)無關(guān)，并且計算量很??；度分布優(yōu)化算法的計算量和迭代次數(shù)成正比，但是誤碼率并不會隨迭代次數(shù)的增加有明顯降低。

表1　迭代次數(shù)和耗時的比較Tab.1　Number of iterations versus computing time

6　結(jié)束語

噴泉碼是一種新型的低密度無碼率信道編碼碼字，并得到了廣泛應(yīng)用。但噴泉碼在短碼長編碼時性能不佳，成為了噴泉碼在無線通信中應(yīng)用的瓶頸。針對這一問題，本文在通過分析度分布對無線傳輸中噴泉碼編譯碼的影響，提出了一種數(shù)字噴泉碼中度分布的優(yōu)化算法。該算法先根據(jù)設(shè)定的門限值確定度值的集合，然后通過優(yōu)化算法求解每個度值的最優(yōu)概率。仿真結(jié)果表明，在相同數(shù)據(jù)包長度下，使用本算法產(chǎn)生的度分布進(jìn)行LT編碼得到的誤碼率低于魯棒孤子分布和固定度分布，同時當(dāng)數(shù)據(jù)包長度改變時，本算法產(chǎn)生的度分布仍然具有最優(yōu)的譯碼性能。本算法能夠提高短碼長噴泉碼的譯碼性能，對噴泉碼在無線傳輸上的應(yīng)用具有參考價值。算法有一定復(fù)雜度，未來還可進(jìn)一步研究降低復(fù)雜度的方法。

［1］ BYERS J W，LUBY M，MITZENMACHER M，et al.A digital fountain approach to reliable distribution of bulk data［C］//Proceedings of the ACM SIGCOMM′98 Conference on Applications，Technologies，Architectures，and Protocols for Computer Communication.New York：ACM，1998：56-67.

［2］ LUBY M.LT codes［C］//Proceedings of 2002 IEEE Symposium on Foundations of Computer Science.Vancouver，Canada：IEEE，2002：271-280.

［3］ 于國海，王呈貴，張哲.采用噴泉碼的無線協(xié)同多跳信息累積廣播協(xié)議［J］.電訊技術(shù)，2011，51（3）：84-88.

YU Guohai，WANG Chenggui，ZHANG Zhe.Cooperative multi-hop broadcast protocols using fountain codes for wireless networks［J］.Telecommunication Engineering，2011，51（3）：84-88.（in Chinese）

［4］ 姚渭箐，易本順.噴泉碼在認(rèn)知無線電網(wǎng)絡(luò)中的應(yīng)用［J］.電訊技術(shù)，2015，55（8）：935-941.

YAO Weiqing，YI Benshun.Application of fountain code in cognitive radio network［J］.Telecommunication Engineering，2015，55（8）：935-941.（in Chinese）

［5］ HYYTIA E，TIRRONEN T，VIRTAMO J.Optimal degree distribution for LT codes with small message length［C］// Proceedings of 2007 26th IEEE International Conference on Computer Communications.Anchorage，AK：IEEE，2007：2576-2580.

［6］ TSAI P C，CHEN C M，CHEN Y P.A novel evaluation function for LT codes degree distribution optimization［C］//Proceedings of 2014 IEEE Congress on Evolutionary Computation（CEC）.Beijing：IEEE，2014：3030-3035.

［7］ CHEN C M，CHEN Y P，SHEN T C，et al.On the optimization of degree distributions in LT code with covariance matrix adaptation evolution strategy［C］//Proceedings of 2010 IEEE Congress on Evolutionary Computation.Barcelona：IEEE，2010：1-8.

［8］ CHEN C M，CHEN Y P，SHEN T C.A practical optimization framework for the degree distribution in LT codes［J］.IEICE Transactions on Communications，2013，96（2）：2807-2815.

［9］ 牛芳琳，李寶明，陳付亮，等.一種改進(jìn)的基于部分信息噴泉碼度分布設(shè)計［J］.電子學(xué)報，2016，44（2）：295-299.

NIU Fanglin，LI Baoming，CHEN Fuliang，et al.The improved degree distribution for rateless code under partial information［J］.ACTA Electronica Sinica，2016，44（2）：295-299.（in Chinese）

［10］ 鄒衍芳.無線多媒體傳輸中噴泉碼技術(shù)研究［D］.北京：北京郵電大學(xué)，2013.

ZOU Yanfang.Research on fountain codes technology in wireless multimedia transmission［D］.Beijing：Beijing University ofPostsandTelecommunications，2013.（in Chinese）

［11］ TSAI P C，CHEN C M，CHEN Y P.Sparse degrees analysis for LT codes optimization［C］//Proceedings of 2012 IEEE World Congress on Computational Intelligence. Brisbane，Queensland，Australia：IEEE，2012：1-6.

［12］ SHOKROLLAHIM A.Raptor codes［J］.IEEE Transactions on Information Theory，2003，52（6）：2551-2567.

［13］ BOGINO M，CATALDI P，GRANGETTO M，et al.Expanding window fountain codes for unequal error protection［C］//Proceedings of 41st Asilomar Conference.Pacific Grove：IEEE，2007：1020-1024.

李 杰（1975—），女，吉林白山人，2001年于長春理工大學(xué)獲碩士學(xué)位，現(xiàn)為上海工程技術(shù)大學(xué)高級工程師，主要從事無線通信網(wǎng)絡(luò)、光通信網(wǎng)絡(luò)等方面的研究。

LI Jie was born in Baishan，Jilin Province，in 1975.She received the M.S.degree from Changchun University of Science and Technology in 2001.She is now a senior engineer.Her research concerns wireless communication network and optical communications.

Email：stslijie@163.com

A Degree Distribution Optimization Algorithm for Small Size Fountain Codes in Wireless Transmission

LI Jie
（Advanced Vocational Technical College，Shanghai University of Engineering Science，Shanghai 200437，China）

Digital fountain code is a popular class of erasure code，which is often used in the case of large network data transmission.The performance of Luby Transform（LT）code is mainly decided by the degree distribution.To improve the decoding performance，a degree distribution optimization algorithm is designed for wireless transmission.Firstly，based on classical soliton distribution and robust soliton distribution，the set of degree values is determined.Then the degree distribution that minimizes the number of un-recovered source symbols is found.The optimal degree distribution can be solved by evolutionary strategy.The experimental results show that compared with LT code with robust soliton distribution and the fixed degree distribution，the proposed algorithm improves the number of the recovered symbols obviously with the same overhead.

wireless transmission；channel coding；digital fountain code；LT code；degree distribution；optimization algorithm

**通信作者:stslijie@163.com stslijie@163.com

TN911.2

A

1001-893X（2016）08-0900-06

10.3969/j.issn.1001-893x.2016.08.012

2016-01-19；

2016-05-10

date:2016-01-19；Revised date:2016-05-10

引用格式:李杰.無線傳輸中短碼長噴泉碼的度分布優(yōu)化算法［J］.電訊技術(shù)，2016，56（8）：900-905.［LI Jie.A degree distribution optimization algorithm for small size fountain codes in wireless transmission［J］.Telecommunication Engineering，2016，56（8）：900-905.］