姚渭箐 胡 凡

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

引 言

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

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

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

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

1 LT碼及度分布

1.1 LT碼編譯碼過(guò)程

LT碼的編碼過(guò)程非常簡(jiǎn)單，具體如下：

Step 1從度分布中隨機(jī)選擇一個(gè)度i；

Step 2隨機(jī)且均勻地選取i個(gè)原始分組；

Step 3將這i個(gè)原始分組進(jìn)行異或生成一個(gè)編碼分組。

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

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

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

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

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

1.2 度分布

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

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

圖1 LT碼編譯碼過(guò)程Fig.1 LT encoding and decoding process

式中

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

1.3 度分布重要特性

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

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

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

AFSA[15]是一種模擬魚(yú)群的覓食、聚群、追尾等典型行為在搜索域中實(shí)現(xiàn)尋優(yōu)的智能進(jìn)化算法。人工魚(yú)對(duì)視野范圍內(nèi)的環(huán)境進(jìn)行感知，即模擬群聚行為和追尾行為，然后進(jìn)行行為評(píng)價(jià)，選擇最優(yōu)者來(lái)實(shí)際執(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ù)；然后，通過(guò)比較和迭代逼近最大目標(biāo)值從而獲得優(yōu)化的度分布。

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

重要度數(shù)的比例對(duì)應(yīng)一個(gè)人工魚(yú)的狀態(tài)為Ω=(Ω(1),Ω(2),Ω([k/R]))。基于度分布特性和RSD(μ(1),μ(2),…,μ(k))產(chǎn)生人工魚(yú)初始值

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

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

（3） 人工魚(yú)群算法

度分布優(yōu)化問(wèn)題的解決是通過(guò)人工魚(yú)在尋優(yōu)過(guò)程中以局部最優(yōu)和個(gè)體最優(yōu)形式表現(xiàn)出來(lái)的。尋優(yōu)的過(guò)程中，跟蹤記錄最優(yōu)個(gè)體的狀態(tài)，該過(guò)程可通過(guò)模擬人工魚(yú)追尾行為來(lái)實(shí)現(xiàn)。追尾行為有助于快速地向某個(gè)極值方向前進(jìn)，可防止人工魚(yú)在局部振蕩而停滯不前。隨著尋優(yōu)過(guò)程的進(jìn)展，人工魚(yú)往往會(huì)聚集在極值點(diǎn)的周?chē)⑶胰肿顑?yōu)的極值點(diǎn)周?chē)ǔＤ芫奂^多的人工魚(yú)，該過(guò)程可通過(guò)模擬人工魚(yú)聚群行為實(shí)現(xiàn)。在對(duì)追尾行為和聚群行為進(jìn)行評(píng)價(jià)后，自動(dòng)選擇合適的行為，從而實(shí)現(xiàn)對(duì)度分布高效快速的尋優(yōu)?；贏FSA度分布尋優(yōu)原理如圖2所示。

具體人工魚(yú)行為描述如下。

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

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

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

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

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

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

2.2 尋優(yōu)步驟

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

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

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

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

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

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

3 性能仿真及分析

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

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

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

為獲得更為直觀的對(duì)比結(jié)果，采用256×256×8=524288 bit的灰度圖作為傳輸數(shù)據(jù)。將原始數(shù)據(jù)均分為1024個(gè)原始分組(每個(gè)原始分組包含512 bit)，當(dāng)接收端接收到1200個(gè)編碼分組時(shí)強(qiáng)制譯碼恢復(fù)，對(duì)圖像的恢復(fù)質(zhì)量進(jìn)行直觀評(píng)估，結(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é)束語(yǔ)

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