一種LT碼度分布優(yōu)化方法

姚渭箐 胡 凡

（1.國網(wǎng)湖北省電力有限公司信息通信公司，武漢，430077；2.武漢大學(xué)電子信息學(xué)院，武漢，430072）

引 言

噴泉碼是一類糾刪碼[1,2]，具有無需反饋重傳、無碼率性、兼容性強和編譯碼復(fù)雜度低等特征，已廣泛應(yīng)用于深空通信[3]、認(rèn)知無線電[4]、物聯(lián)網(wǎng)[5]和云存儲等領(lǐng)域[6]。2002年，Luby提出了第一個噴泉碼的具體實現(xiàn)方案——LT(Luby transform)變換碼[7]，完成了對LT碼的編譯碼算法及度分布構(gòu)造的基礎(chǔ)研究，其中最重要的貢獻是完成了對魯棒孤子分布(Robust soliton distribution,RSD)的推導(dǎo)及分析。

RSD也存在一定局限性，在一些實時性要求較高的應(yīng)用中，例如視頻圖像傳輸，為提高傳輸速率需盡量減小碼長。然而，在短碼長構(gòu)造下RSD的譯碼性能較差，需要較大的譯碼開銷才能譯碼成功。針對該問題，國內(nèi)外諸多學(xué)者和科研機構(gòu)在LT碼的度分布優(yōu)化問題上做了大量研究工作。

文獻[8,9]分別采用粒子群優(yōu)化算法(Particle swarm optimization,PSO)和蟻群算法(Ant colony algorithm,ACA)對LT碼度分布進行優(yōu)化。將度分布中度數(shù)的比例值映射到仿生算法的解空間構(gòu)建初始路徑，經(jīng)過仿生算法迭代優(yōu)化，從一定程度上能夠得到相同度分布參數(shù)要求下更優(yōu)的度分布值。文獻[10]將二進制指數(shù)分布(Binary exponential distribution,BED)和RSD相結(jié)合提出一種譯碼性能更優(yōu)的開關(guān)度分布(Switch degree distribution,SDD)。在編碼器編碼的初始階段，采用BED進行編碼，當(dāng)已經(jīng)產(chǎn)生一定數(shù)量編碼分組后，將BED切換到RSD。文獻[11]基于置信傳播(Belief propagation,BP)算法的AND-OR分析，將度分布優(yōu)化問題轉(zhuǎn)化為半正定規(guī)劃(Semi-definite programming,SDP)形式，隨后又轉(zhuǎn)化為一個線性規(guī)劃問題。文獻[12]引入加權(quán)系數(shù)將改進的泊松分布(Improved Poisson robust soliton distribution,IPD)和RSD聯(lián)合成一種適用于LT碼的聯(lián)合泊松魯棒孤子分布(Combined Poisson robust soliton distribution,CPRSD)。并基于期望可譯集特性，采用黃金分割點算法對加權(quán)系數(shù)進行尋優(yōu)。

盡管現(xiàn)有的度分布優(yōu)化方案已取得一定研究成果，但仍然存在提升的空間。為了得到更優(yōu)的度分布，本文基于度分布重要特性，采用人工魚群算法(Artificial fish swarm algorithm,AFSA)對RSD中某些重要度數(shù)的比例進行尋優(yōu)。仿真結(jié)果證明，在二進制刪除信道(Binary erasure channel,BEC)中，采用優(yōu)化后的度分布對短碼長LT碼進行編碼，能有效降低譯碼開銷，并節(jié)約編譯碼耗時。

1 LT碼及度分布

1.1 LT碼編譯碼過程

LT碼的編碼過程非常簡單，具體如下：

Step 1從度分布中隨機選擇一個度i；

Step 2隨機且均勻地選取i個原始分組；

Step 3將這i個原始分組進行異或生成一個編碼分組。

重復(fù)以上步驟，編碼生成無限且靈活數(shù)量的編碼分組。

接收端接收到N個編碼分組(N略大于k)，然后開始譯碼[7]。通常，LT碼采用BP算法進行譯碼。

Step 1度數(shù)為1(i=1)的編碼分組直接譯碼；

Step 2譯出的原始分組與跟其相連的編碼分組進行異或后替代原編碼分組，同時刪除其連接關(guān)系。

重復(fù)以上步驟，直至譯碼完成。LT碼編譯碼過程如圖1所示。

1.2 度分布

根據(jù)LT碼編譯碼過程可知，度分布對LT碼的性能影響至關(guān)重要。文獻[7]指出，一個好的度分布需滿足兩個設(shè)計目標(biāo)：（1）譯碼成功所需的平均編碼分組數(shù)量盡可能少，確保LT譯碼成功的編碼數(shù)量對應(yīng)于確保原始分組全部譯出的編碼分組數(shù)量。（2）編碼分組的平均度數(shù)盡可能小，平均度數(shù)是生成一個編碼分組所需的平均異或運算次數(shù)，因此，平均度數(shù)決定了編碼復(fù)雜度，而譯碼復(fù)雜度則是平均度數(shù)乘以譯碼成功所需編碼分組數(shù)量。

最經(jīng)典的是Luby在2002年提出的RSD[7]，其表達式如下

圖1 LT碼編譯碼過程Fig.1 LT encoding and decoding process

式中

RSD函數(shù)最后的“Spike”τ(k/R)能保證編碼過程中高效地覆蓋所有原始分組。

1.3 度分布重要特性

度分布中某些度數(shù)對LT碼可譯碼性的影響至關(guān)重要，通過調(diào)整這些度數(shù)在度分布中的比例，LT碼可獲得良好的性能。首先，度數(shù)為2在度分布中所占比例最高，當(dāng)k→∞時，該比例趨近于1/2[13]。其次，需要度數(shù)為1的編碼分組來觸發(fā)BP譯碼開始，意味著度數(shù)為1的比例大于0。但是，過多的度數(shù)為1的編碼分組會造成低效譯碼，也就是說，度數(shù)為1的比例必須要小。可以發(fā)現(xiàn)，好的度分布都具有一個共性，即度數(shù)為1的比例遠(yuǎn)小于度數(shù)為2的比例，否則，會導(dǎo)致一個相當(dāng)大的最小譯碼開銷[14]。

2 基于人工魚群算法的度分布優(yōu)化方法

基于度分布重要特性，對RSD進行改進。采用AFSA對RSD中度數(shù)為1、度數(shù)為2以及度數(shù)為k/R的比例進行尋優(yōu)，從而得到相同度分布參數(shù)要求下更優(yōu)的度分布。

AFSA[15]是一種模擬魚群的覓食、聚群、追尾等典型行為在搜索域中實現(xiàn)尋優(yōu)的智能進化算法。人工魚對視野范圍內(nèi)的環(huán)境進行感知，即模擬群聚行為和追尾行為，然后進行行為評價，選擇最優(yōu)者來實際執(zhí)行，默認(rèn)行為方式為覓食行為。

2.1 尋優(yōu)原理

基于AFSA度分布尋優(yōu)的核心是：首先，將度分布中度數(shù)為1、度數(shù)為2以及度數(shù)為k/R的比例值映射到AFSA的解空間構(gòu)建初始值；接著，基于平均度數(shù)構(gòu)建該算法的目標(biāo)函數(shù)；然后，通過比較和迭代逼近最大目標(biāo)值從而獲得優(yōu)化的度分布。

（1） 初始值產(chǎn)生

重要度數(shù)的比例對應(yīng)一個人工魚的狀態(tài)為Ω=(Ω(1),Ω(2),Ω([k/R]))?；诙确植继匦院蚏SD(μ(1),μ(2),…,μ(k))產(chǎn)生人工魚初始值

（2） 目標(biāo)函數(shù)構(gòu)建

為降低編譯碼復(fù)雜度，希望編碼分組的平均度數(shù)盡可能小[7]。由于非重要度數(shù)的比例保持不變，因此，將度分布優(yōu)化問題轉(zhuǎn)換為最小化Ω(1),Ω(2),Ω([k/R])的平均度數(shù)，即通過最小化式（5）來獲得優(yōu)化度分布

（3） 人工魚群算法

度分布優(yōu)化問題的解決是通過人工魚在尋優(yōu)過程中以局部最優(yōu)和個體最優(yōu)形式表現(xiàn)出來的。尋優(yōu)的過程中，跟蹤記錄最優(yōu)個體的狀態(tài)，該過程可通過模擬人工魚追尾行為來實現(xiàn)。追尾行為有助于快速地向某個極值方向前進，可防止人工魚在局部振蕩而停滯不前。隨著尋優(yōu)過程的進展，人工魚往往會聚集在極值點的周圍，并且全局最優(yōu)的極值點周圍通常能聚集較多的人工魚，該過程可通過模擬人工魚聚群行為實現(xiàn)。在對追尾行為和聚群行為進行評價后，自動選擇合適的行為，從而實現(xiàn)對度分布高效快速的尋優(yōu)。基于AFSA度分布尋優(yōu)原理如圖2所示。

具體人工魚行為描述如下。

圖2 基于AFSA的度分布優(yōu)化模型Fig.2 Optimization of degree distribution based on AFSA

（1）視覺模擬(逼近搜索)：設(shè)一個人工魚的當(dāng)前狀態(tài)為Ω=(Ω(1),Ω(2),Ω([k/R]))，在搜索域(Visual)內(nèi)進行隨機搜索，如果感知到更優(yōu)狀態(tài)Ω'=(Ω'(1),Ω'(2),Ω'([k/R]))，則朝該狀態(tài)的位置方向前進一步；否則，繼續(xù)搜索。該過程可以表示為

式中：Rand∈(-1,1)，S為最大移動步長。

（2）聚群行為(局部尋優(yōu))：設(shè)人工魚當(dāng)前狀態(tài)為Ω，在Visual內(nèi)隨機搜索聚集成群的ny個人工魚，并定位這ny個人工魚間的中心位置Ωc，如果yc/ny＞d?y(d為擁擠度因子，表示與其他人工魚之間的擁擠情況)，表明該位置為局部最優(yōu)位置，則根據(jù)式(7)，朝Ωc方向前進一步；否則執(zhí)行覓食行為。

（3）追尾行為(個體尋優(yōu))：設(shè)人工魚當(dāng)前狀態(tài)為Ω，在Visual內(nèi)隨機搜索ny個人工魚，并定位其中yj為最小的Ωj，如果yj/ny＞d?y，表明該狀態(tài)為個體最優(yōu)，則根據(jù)式(7)，朝Ωj方向前進一步；否則執(zhí)行覓食行為。

（4）覓食行為(隨機尋優(yōu))：設(shè)人工魚當(dāng)前狀態(tài)為Ω，在視野范圍內(nèi)隨機搜索一個狀態(tài)Ωj，如果y＞yj，表明該狀態(tài)優(yōu)于當(dāng)前狀態(tài)，則根據(jù)式(7)，朝Ωj方向前進一步；反之，再重新搜索。反復(fù)試探多次后，如果仍無法定位更優(yōu)狀態(tài)，則根據(jù)式(6)，隨機移動一步。

2.2 尋優(yōu)步驟

Step 1基于RSD產(chǎn)生初始魚群，例如，魚群大小為m，有3個待優(yōu)化的參數(shù)，即Ω=(Ω(1),Ω(2),Ω([k/R]))。 其 中 ，Ω(1)∈(0,μ(1))，Ω(2)∈ (μ(2),0.5)，Ω([k/R])=μ(1)+μ(2)+μ([k/R])-Ω(1)-Ω(2)，則要隨機產(chǎn)生一個3行m列初始魚群{Ωv|v=1,2,…,m}。

Step 2每個人工魚執(zhí)行群聚行為得到局部最優(yōu)值，執(zhí)行追尾行為得到個體最優(yōu)值。

Step 3通過行為評價，即比較兩種行為的目標(biāo)函數(shù)值，選取函數(shù)值較小者作為一個人工魚的最優(yōu)值yvmin及其對應(yīng)的Ωvmin。

Step 4m個人工魚完成一次感知行為得到{y1min,y2min,…,ymmin}及其對應(yīng)的{Ω1min,Ω2min,…,Ωmmin}，再比較m個人工魚目標(biāo)函數(shù)值，選取函數(shù)值最小者作為人工魚群的最優(yōu)值，得到y(tǒng)min及其對應(yīng)的Ωmin。

Step 5將ymin與前一次的最優(yōu)值進行比較，得到一次迭代的最優(yōu)值ybest及其對應(yīng)的Ωbest，如果迭代次數(shù)小于設(shè)定值，轉(zhuǎn)移到Step 2，否則尋優(yōu)完成，得到全局最優(yōu)目標(biāo)函數(shù)值ybest及其對應(yīng)的人工魚狀態(tài)Ωbest。

優(yōu)化后的Ωbest(2)的比例有所增加且滿足Ωbest(1)?Ωbest(2)，符合度分布通用特性[14]，可降低恢復(fù)所有原始分組所需的最小譯碼開銷。而此時，Ωbest([k/R])仍然保持較高比例，從而保證編碼過程中高效地覆蓋所有原始分組。并且，由于平均度數(shù)降低，意味著編譯碼過程中進行的異或運算量大大降低，從而加快編譯碼速度。因此，即使在碼長較短(原始分組數(shù)k＜104)時，也能保證較好的譯碼性能和編譯碼效率。

3 性能仿真及分析

為驗證所提方法的有效性，根據(jù)參考文獻[12]，選取相同參數(shù)k=1000，c=0.1，δ=0.005時，分別對本文改進的RSD(Modified RSD,MRSD)、參考文獻[8-10]中的度分布設(shè)計方法和RSD進行1000次編譯碼仿真，然后對實驗結(jié)果進行比較和分析。AFSA算法中對各參數(shù)的取值范圍比較寬容，并且對算法的初值也基本無要求[15]。根據(jù)每個度值的初始值約束范圍，經(jīng)過多次實驗選取AFSA參數(shù)為：人工魚數(shù)量為m=50個，試探次數(shù)為100次，迭代次數(shù)為50次，Visual=0.001，d=0.618，S=0.0005。仿真實驗平臺為Intel(R)Core(TM)2.8 GHz處理器，4 GB內(nèi)存。采用Matlab R2014a編程仿真。

MRSD及其他4種度分布的譯碼成功率隨譯碼開銷((N-k)/k)變化情況如圖3所示。譯碼成功率為譯碼器接收不同數(shù)量的編碼分組時，成功譯出的分組數(shù)占原始分組總數(shù)的比例。從圖3可以明顯看出，傳統(tǒng)的RSD不太適用于短碼長LT碼。RSD初始譯碼成功率較低，并需要50.7%譯碼開銷才能完全恢復(fù)k=1000原始分組。而MRSD譯碼性能最優(yōu)，不僅初始譯碼成功率較高，并隨著接收編碼分組數(shù)的增多，譯碼成功率快速上升，達到恢復(fù)k=1000原始分組時的譯碼開銷僅為25.2%。與其他3種優(yōu)化度分布相比，MRSD譯碼性能也是最優(yōu)。

表1對5種度分布的譯碼成功所需的平均譯碼開銷、平均度數(shù)以及單次編譯碼耗時進行比較。當(dāng)k=1000時采用MRSD度分布進行LT編碼，譯碼成功所需的平均譯碼開銷比其他4種度分布降低了5.7%～25.5%，并且節(jié)約了至少8.5%(8.5%～44.9%)的平均編譯碼耗時。

為獲得更為直觀的對比結(jié)果，采用256×256×8=524288 bit的灰度圖作為傳輸數(shù)據(jù)。將原始數(shù)據(jù)均分為1024個原始分組(每個原始分組包含512 bit)，當(dāng)接收端接收到1200個編碼分組時強制譯碼恢復(fù)，對圖像的恢復(fù)質(zhì)量進行直觀評估，結(jié)果如圖4所示。從圖4中明顯看出，RSD以及其他3種優(yōu)化度分布恢復(fù)的圖像都存在不同程度的失真，而MRSD度分布幾乎完全恢復(fù)圖像。

圖3 不同度分布譯碼性能(k=1000,c=0.1,δ=0.005)Fig.3 Decoding performance fordifferent degree distributions

表1 不同度分布性能比較（k=1000，c=0.1，δ=0.005）Tab.1 Performance comparison for different degree distributions（k=1000，c=0.1，δ =0.005）

圖45種度分布圖像恢復(fù)質(zhì)量比較Fig.4 Image recovery for five degree distributions

4 結(jié)束語

針對RSD在LT碼碼長較短時性能不夠理想的情況，本文提出一種適用于BEC信道的度分布優(yōu)化方法?；诙确植继匦院虯FSA，通過調(diào)整度分布中某些重要度數(shù)的比例，從而提高短碼長LT碼的譯碼性能?；谠挤纸Mk=1000的仿真結(jié)果表明，與傳統(tǒng)的RSD及類似方法相比，采用所提出的方法優(yōu)化度分布更能有效提高短碼長LT碼的編譯碼效率和譯碼成功率。