一種基于反饋的Raptor碼編碼改進(jìn)方案

張 偉，雷維嘉，謝顯中

(重慶郵電大學(xué)移動(dòng)通信技術(shù)重慶市重點(diǎn)實(shí)驗(yàn)室，重慶400065)

0 引言

文獻(xiàn)［1］在1998年首次提出數(shù)字噴泉碼這一概念，文獻(xiàn)［2］在2002年給出了第1種實(shí)用的數(shù)字噴泉碼—LT碼。對(duì)于LT碼，編譯碼k個(gè)源數(shù)據(jù)包需要k ln k次異或(XOR)運(yùn)算，也就是說(shuō)LT碼并不具有線性時(shí)間譯碼［3］?；诖?，2006年文獻(xiàn)［4］提出了另外一類數(shù)字噴泉碼，即Raptor碼，它由外碼和內(nèi)碼通過(guò)級(jí)聯(lián)編碼的方式實(shí)現(xiàn)。外碼是傳統(tǒng)的信道糾刪碼，內(nèi)碼是弱化的LT碼。這里，弱化的LT碼是指其度分布中最大度為一個(gè)較小的值，且平均度d*是個(gè)常數(shù)，編譯碼k個(gè)源數(shù)據(jù)包需要kd*次XOR運(yùn)算。因此，Raptor碼實(shí)現(xiàn)了線性時(shí)間譯碼。

為了提高噴泉碼的譯碼效率，許多方案都引入了反饋。文獻(xiàn)［5］提出一種實(shí)時(shí)遺漏糾錯(cuò)方案，接收端向發(fā)送端反饋?zhàn)g出的源數(shù)據(jù)包個(gè)數(shù)，發(fā)送端根據(jù)反饋信息選擇一個(gè)固定的度分布，使接收端譯出全部源數(shù)據(jù)包的時(shí)間減短。同樣，文獻(xiàn)［6］給出一種混合噴泉碼，發(fā)送端根據(jù)反饋信息直接發(fā)送相應(yīng)的源數(shù)據(jù)包，加速了譯碼進(jìn)程。又有學(xué)者針對(duì)短碼給出一種無(wú)率反饋碼方案［7］，該方案通過(guò)多次反饋并改變度分布，使譯碼開銷減少等。

以上方案雖然通過(guò)反饋提高了譯碼效率，但忽略了譯碼效率變化的特點(diǎn)。本文針對(duì)Raptor碼譯碼的最后階段出現(xiàn)譯碼效率明顯降低的問(wèn)題，提出了一種帶反饋的編碼改進(jìn)方案，并給出最佳的反饋控制點(diǎn)。仿真結(jié)果顯示:改進(jìn)的方案明顯提高了譯碼效率，減小了譯碼開銷等。

1 Raptor碼

1.1 Raptor碼的編碼和譯碼

Raptor碼的編碼包括預(yù)編碼和LT編碼兩部分。預(yù)編碼:編碼器對(duì)k個(gè)源數(shù)據(jù)包使用糾刪碼(比如，LDPC碼［8］)產(chǎn)生K個(gè)中間數(shù)據(jù)包，其中K比k略大一點(diǎn)。LT編碼:根據(jù)弱化的LT碼度分布對(duì)K個(gè)中間數(shù)據(jù)包進(jìn)行噴泉編碼，產(chǎn)生需要的編碼包數(shù)量。

相應(yīng)地，Raptor碼的譯碼包括了兩階段譯碼，采用與LT碼相同的置信傳播算法［2］。LT譯碼:編碼包譯出絕大多數(shù)中間數(shù)據(jù)包。預(yù)編碼的譯碼:由譯出的這部分中間數(shù)據(jù)包恢復(fù)全部源數(shù)據(jù)包。

Mackay在文獻(xiàn)［9］中指出:當(dāng)譯碼器接收N(N比k略大一點(diǎn))個(gè)編碼包后進(jìn)行譯碼，有一部分中間數(shù)據(jù)包不能恢復(fù)出來(lái)，其比例為f=exp(－d*)。對(duì)此，他提出了一種編譯碼策略:預(yù)編碼階段應(yīng)產(chǎn)生k/(1－f)個(gè)中間數(shù)據(jù)包，而譯碼器只需譯出大約k個(gè)中間數(shù)據(jù)包，然后通過(guò)預(yù)編碼的譯碼恢復(fù)全部的源數(shù)據(jù)包。

1.2 弱化的LT碼度分布

在LT碼的譯碼過(guò)程中，為了避免冗余，希望每次迭代中只有一個(gè)度為1的編碼包。由此得到一種理想孤子分布ρ:

其中，ρ(d)為選到度為d的概率。

然而實(shí)際中，理想孤子分布的效果并不好。一方面，譯碼過(guò)程中很可能因?yàn)闆](méi)有度為1的編碼包而出現(xiàn)譯碼中斷;另一方面，編碼時(shí)可能有些源數(shù)據(jù)包沒(méi)有被覆蓋，導(dǎo)致無(wú)法譯出。Luby對(duì)理想孤子分布進(jìn)行了修改［2］，設(shè)計(jì)了一個(gè)正數(shù)函數(shù)τ:

其中，參數(shù)с和δ保證了譯碼過(guò)程中期望產(chǎn)生度為1的編碼包個(gè)數(shù)大約為:

式中，с為0和1之間的某一常數(shù);δ為接收一定數(shù)量的編碼包后，未能成功譯出全部源數(shù)據(jù)包的概率。然后，將ρ與τ相加再歸一化得到魯棒孤子分布μ:

魯棒孤子分布的最大度是k，而弱化的LT碼度分布是將魯棒孤子分布的最大度設(shè)置成一個(gè)較小的值，但理想孤子分布和正數(shù)函數(shù)的最大度不變［9］，下面定義其表達(dá)式:

式中，n為參與編碼的數(shù)據(jù)包個(gè)數(shù);D為最大度;i為度;z=ρ(i)+τ(i)。特別地，對(duì)于不同的n，當(dāng)D取8時(shí)，μn，D的平均度d*均為3。

2 譯碼性能及改進(jìn)的編碼方案

2.1 譯碼性能

這里主要研究Raptor碼的LT譯碼階段，即由編碼包譯出k個(gè)中間數(shù)據(jù)包這一過(guò)程。預(yù)編碼采用LDPC碼，其度分布Ω(x)=(2x+3x2)/5［4］，碼率為0.95。為了便于分析，定義4個(gè)參數(shù):譯碼比例β，表示譯出的中間數(shù)據(jù)包個(gè)數(shù)M占源數(shù)據(jù)包個(gè)數(shù)k的比例，即β=M/k;接收比例θ，表示接收的編碼包個(gè)數(shù)N占k的比例，即θ=N/k;譯碼效率η=M/N;譯碼開銷ε［10］，表示成功譯碼時(shí)接收的編碼包個(gè)數(shù)與k的差值占k的比例。圖1給出了k分別取1 000和5 000時(shí)，多次仿真其譯碼比例β隨接收比例θ變化的曲線，其中每條曲線代表每次仿真的結(jié)果。

觀察圖1a中k=1 000的譯碼曲線，當(dāng)橫坐標(biāo)0＜θ＜0.8時(shí)，曲線比較平緩，縱坐標(biāo)β的值非常小，只譯出少部分中間數(shù)據(jù)包，說(shuō)明譯碼效率很低;當(dāng)θ大約為0.9時(shí)，曲線出現(xiàn)陡增，β迅速增大到0.8左右，表明譯出了大約0.8k個(gè)中間數(shù)據(jù)包，譯碼效率大大提高;最后一段曲線變平緩，β變化緩慢，說(shuō)明譯碼效率明顯降低，當(dāng)θ大約為1.2時(shí)，譯碼結(jié)束，譯碼開銷約為0.2。觀察圖1b，k=5 000時(shí)表現(xiàn)出與k=1 000相似的譯碼曲線。

2.2 理論分析

度分布的設(shè)計(jì)對(duì)于數(shù)字噴泉碼來(lái)說(shuō)是至關(guān)重要的，它的好壞直接決定了譯碼性能。在譯碼過(guò)程中，度為1和其他低度的編碼包的數(shù)量決定了譯碼能否開始并持續(xù)進(jìn)行，但這些數(shù)據(jù)包攜帶的原始信息較少，可能不會(huì)覆蓋全部的源數(shù)據(jù)包。為了譯出全部源數(shù)據(jù)包，譯碼器需要接收更多的編碼包。度分布的平均度代表了平均的編譯碼復(fù)雜度。因此，較小的平均度確保了譯碼過(guò)程的流暢性，但可能造成譯碼開銷增大。比如，當(dāng)d*=3，不同k值的譯碼開銷ε均達(dá)到了0.2之多，而這個(gè)值并不理想。

圖1 不同的源數(shù)據(jù)包數(shù)k，譯碼比例β隨接收比例θ變化的曲線

譯碼開銷增大主要是因?yàn)樽g碼的最后階段譯碼效率明顯降低。分析認(rèn)為:當(dāng)譯碼器譯出大約βk個(gè)中間數(shù)據(jù)包后，編碼器新生成的編碼包中只包含譯出數(shù)據(jù)包信息的比例為P=βd*，而這些編碼包對(duì)未譯出的數(shù)據(jù)包是冗余信息。由圖1可看出:當(dāng)β大約為0.8時(shí)，曲線開始變平緩。這時(shí)，P=0.83，大約為50%。因此，最后階段接收的編碼包中有一半是不包含未譯出的數(shù)據(jù)包信息，導(dǎo)致了譯碼效率明顯降低。

為了提高這一階段的譯碼效率，編碼器再編碼時(shí)可以考慮只對(duì)未譯出的數(shù)據(jù)包進(jìn)行編碼，但需要譯碼器反饋這部分?jǐn)?shù)據(jù)包的包號(hào)。下面給出具體的改進(jìn)方案。

2.3 改進(jìn)的編碼方案

根據(jù)反饋控制編碼器中參與編碼的數(shù)據(jù)包的思想，改進(jìn)的編碼方案為:

(Ⅰ)編碼器按照度分布μK，8對(duì)K個(gè)中間數(shù)據(jù)包進(jìn)行噴泉編碼。

(Ⅱ)譯碼器接收一定數(shù)量的編碼包后開始譯碼;當(dāng)譯出大約αk個(gè)中間數(shù)據(jù)包時(shí)，向編碼器反饋剩余未譯出的數(shù)據(jù)包個(gè)數(shù)(K－αk)和具體數(shù)據(jù)包的包號(hào)。

(Ⅲ)編碼器根據(jù)反饋信息，僅對(duì)這(K－αk)個(gè)數(shù)據(jù)包按照度分布μ(K－αk)，8噴泉編碼。

(Ⅳ)譯碼器譯出大約k個(gè)中間數(shù)據(jù)包后，由這k個(gè)數(shù)據(jù)包恢復(fù)出全部的源數(shù)據(jù)包。

這里，稱α為反饋控制點(diǎn)。從圖1中曲線的變化趨勢(shì)來(lái)看，曲線在α=0.8左右開始變平緩，而改進(jìn)方案的關(guān)鍵是α取何值時(shí)，可使譯碼開銷最少，即尋找最佳的反饋控制點(diǎn)。從理論上推導(dǎo)最佳的反饋控制點(diǎn)α的值比較困難，本文通過(guò)仿真的方法，對(duì)不同的源數(shù)據(jù)包數(shù)k、α分別取0.75、0.80、0.85和0.90這4個(gè)值，比較各自的譯碼開銷來(lái)得到最佳的反饋控制點(diǎn)。圖2仿真了不同的源數(shù)據(jù)包數(shù)k，譯碼開銷ε隨反饋控制點(diǎn)α變化的關(guān)系。從該圖可得到最佳的反饋控制點(diǎn)α為0.8，此時(shí)譯碼開銷均最少。

改進(jìn)方案需要譯碼器反饋未譯出數(shù)據(jù)包的包號(hào)，這樣雖然增加了系統(tǒng)的復(fù)雜度，但譯碼開銷的大幅降低遠(yuǎn)彌補(bǔ)了這一不足。另外，當(dāng)源數(shù)據(jù)包數(shù)k較大時(shí)，反饋數(shù)據(jù)較多，復(fù)雜度增加，也會(huì)使總的效率降低。例如k=5 000時(shí)，反饋量達(dá)到1 000。因此，改進(jìn)方案更適合k不超過(guò)1 000的情況。

3 性能仿真

本文通過(guò)仿真的方法，與原來(lái)無(wú)反饋的編碼方案作比較，驗(yàn)證改進(jìn)方案的性能。仿真中，弱化的LT碼度分布中с和δ分別取0.03和0.50。首先，比較兩種方案的譯碼開銷。原來(lái)的方案(圖2中，當(dāng)α= 1.00時(shí)縱坐標(biāo)ε的取值)，對(duì)于不同的源數(shù)據(jù)包k，譯碼開銷都達(dá)到了0.22;而改進(jìn)的方案(圖2中，當(dāng)α=0.80時(shí)縱坐標(biāo)ε的取值)，譯碼開銷減小了10%左右，且隨著k的增大，譯碼開銷逐漸減小，當(dāng)k=1 000時(shí)，ε僅為0.096。

譯碼效率η是衡量一種方案的性能很重要的參數(shù)，η越趨近1說(shuō)明方案的性能越好。圖3為不同的源數(shù)據(jù)包數(shù)k，兩種方案的譯碼效率對(duì)比情況，原來(lái)方案的η大約為0.82且隨k的變化很小;改進(jìn)方案的η隨k的增大而增大，當(dāng)k=1 000時(shí)，η達(dá)到了0.91，體現(xiàn)了很好的性能。

為了更清楚表明譯碼的最后階段，改進(jìn)方案明顯提高了譯碼效率，這里定義另外一個(gè)參數(shù)，最后階段的譯碼效率η0=0.2k/△N，△N表示譯出最后0.2k個(gè)中間數(shù)據(jù)包，譯碼器還需接收的編碼包數(shù)。η0的具體含義為譯碼器接收一個(gè)編碼包平均能譯出中間數(shù)據(jù)包的個(gè)數(shù)。表1為不同的源數(shù)據(jù)包數(shù)k，兩種方案最后階段的譯碼效率η0對(duì)比，由表1可看出:譯碼的最后階段，無(wú)反饋的方案中譯碼器接收一個(gè)編碼包可譯出一個(gè)中間數(shù)據(jù)包，而改進(jìn)的方案可譯出兩個(gè)中間數(shù)據(jù)包，效率提高了一倍以上。

圖2 不同的源數(shù)據(jù)包數(shù)k，譯碼開銷ε和反饋控制點(diǎn)α的關(guān)系

圖3 不同的源數(shù)據(jù)包數(shù)k，兩種方案的譯碼效率對(duì)比情況

4 結(jié)束語(yǔ)

本文給出了一種基于反饋的Raptor碼編碼改進(jìn)方案，它通過(guò)反饋來(lái)控制編碼器中參與編碼的數(shù)據(jù)包，減少了冗余信息，提高了最后階段的譯碼效率。經(jīng)仿真得到最佳的反饋控制點(diǎn)。仿真結(jié)果顯示:與原來(lái)無(wú)反饋的編碼方案比較，改進(jìn)方案的譯碼性能得到明顯改善。

表1 不同的源數(shù)據(jù)包數(shù)k，兩種方案最后階段的譯碼效率η0對(duì)比

［1］ Byers J，Luby M，Mitzenmacher M，et al.A Digital Fountain Approach Distribution of Bulk Data［J］.ACM Sigcomm Computer Communication Review，1998，28(4):56－67.

［2］ Luby M.LT Codes［C］//Proceedings of 43rd Annual IEEE Symposium on Foundations of Computer Science(FOCS’02).USA:IEEE Press，2002:271－280.

［3］ 慕建君，焦曉鵬，曹訓(xùn)志.數(shù)字噴泉碼及其應(yīng)用的研究進(jìn)展與展望［J］.電子學(xué)報(bào)，2009，37(7):1571－1577.

［4］ Shokrollahi A.Raptor Codes［J］.IEEE Transactions on Information Theory，2006，52(6):2551－2567.

［5］ Beimel A，Dolev S，Singer N.RTOblivious Erasure Correcting［J］.IEEE/ACM Transactions on Networking，2007，15(6): 1321－1332.

［6］ Kokalj-Filipovic S，Spasojevic P.ARQ with Doped Fountain Decoding［C］//IEEE ISSSTA’08.2008:780－784.

［7］ Jesper H S，Toshiaki K A，Philip O.Rateless Feedback Codes［C］//IEEE International Symposium on Information Theory Proceedings.2012:1767－1771.

［8］ 王立新，劉躍軍，吳亮.基于LDPC優(yōu)化圖結(jié)構(gòu)的ACE改進(jìn)算法［J］.河南科技大學(xué)學(xué)報(bào):自然科學(xué)版，2010，31(4):46－52.

［9］ Mackay D JC.Fountain Codes［C］//IEE Communications Proceedings.2005:1062－1068.

［10］ Mitzenmacher M.Digital Fountains:A Survey and Look Forward［C］//IEEE Information Theory Workshop.USA:IEEE Press，2004:271－276.