單次反饋的Raptor 碼的內(nèi)碼度分布設(shè)計

雷維嘉，張偉，謝顯中

(重慶郵電大學(xué)移動通信技術(shù)重慶市重點實驗室，重慶 400065)

0 引言

Luby在1998年提出了數(shù)字噴泉碼的概念［1］。噴泉碼是一種碼率不固定的信道編碼，在發(fā)送端由k個源數(shù)據(jù)包可以生成任意數(shù)量的編碼包，接收端只要收到任意k(1+ε)個編碼包后能以很大的概率成功譯出全部源數(shù)據(jù)包，其中ε是譯碼開銷。Luby在2002年給出第一類實用的噴泉碼—LT碼［2］。之后，Shokrollahi提出了另外一類性能更佳的噴泉碼，即Raptor碼［3］。目前，Raptor碼已經(jīng)被3GPP中多媒體廣播和多播業(yè)務(wù)(multimedia broadcastmulticast service，MBMS)標準［4］以及掌上數(shù)字視頻廣播(digital video broadcastinghandheld ，DVB－H)標準［5］所采用。

當系統(tǒng)存在反饋時，除用反饋控制信息傳輸外，還可利用反饋來調(diào)整噴泉碼的編碼過程，提高編譯碼性能。文獻［6］提出在應(yīng)用噴泉碼的中繼傳輸中，目的端向中繼反饋具體譯出哪些源包，接著中繼調(diào)整編碼對象，來減少譯碼開銷。類似地，文獻［7］所提方案不僅調(diào)整編碼對象，同時，根據(jù)反饋信息改進度分布，可進一步減少譯碼開銷，提高譯碼效率。文獻［8］針對短碼給出一種基于反饋的Raptor碼編碼方案，通過反饋具體譯出哪些源包來改變度分布，減少譯碼開銷。文獻［9］給出一種混合噴泉編碼，通過反饋具體哪些源包未譯出，發(fā)送端再直接發(fā)送相應(yīng)的源包，加速了譯碼進程等。除此之外，還可以從調(diào)整度分布和反饋時間的選擇方面進行綜合研究，提高譯碼效率。

本文給出一種單次反饋的Raptor碼的內(nèi)碼度分布方案:接收端在最佳反饋時間點反饋譯出中間包的比例系數(shù)α，發(fā)送端根據(jù)α來調(diào)整度分布，可減小冗余包的傳輸。通過理論分析和仿真得到最佳的反饋時間點，并通過仿真表明，采用該度分布方案，不僅編譯碼復(fù)雜度較小且是線性的，而且，可明顯減小譯碼開銷。

1 Raptor碼

Raptor碼是在LT碼的基礎(chǔ)上發(fā)展而來，LT碼譯碼過程中，恢復(fù)全部源數(shù)據(jù)包至少需要k log k次異或運算，不具有線性的譯碼復(fù)雜度，其中，k表示源數(shù)據(jù)包的個數(shù)。Raptor碼通過預(yù)編碼和弱化的LT編碼，使譯碼的運算量降低為k log(1/ε)，實現(xiàn)了線性的譯碼復(fù)雜度。

1.1 Raptor碼的編碼

Raptor碼的編碼包括預(yù)編碼和LT編碼2個部分。其中，預(yù)編碼作為外碼;LT編碼作為內(nèi)碼。預(yù)編碼:編碼器對k個源數(shù)據(jù)包使用傳統(tǒng)糾刪編碼(比如Tornado碼［10］、LDPC 碼［11］或者重復(fù)累積碼)產(chǎn)生 K個中間數(shù)據(jù)包，其中，K=k/R，R為預(yù)編碼的碼率。LT編碼:將K個中間包作為LT碼的輸入包進行編碼，得到Raptor碼的編碼包。整個編碼如圖1所示。

圖1 Raptor碼的編碼Fig.1 Encoding of Raptor codes

1.2 Raptor碼的譯碼

Raptor碼的譯碼包括2個階段，第1階段為LT碼的譯碼，由編碼包譯出K(R+σ)個中間數(shù)據(jù)包，其中，σ≥ 0;第2階段為糾刪碼譯碼，由譯出的中間數(shù)據(jù)包恢復(fù)k個源數(shù)據(jù)包。LT碼的譯碼可采用高斯消元法或者置信傳播(belief propagation，BP)算法［2］，前者譯碼開銷小，但譯碼速度慢且復(fù)雜度相對高;后者雖然譯碼開銷大點，但譯碼速度快且復(fù)雜度較低。實際應(yīng)用中多采用BP算法，本文針對采用BP譯碼時的譯碼復(fù)雜度和譯碼開銷等進行分析。

1.3 內(nèi)碼度分布

度分布的設(shè)計對噴泉碼的性能至關(guān)重要，它的好壞直接決定了編譯碼性能。一方面，度為1和其他低度的編碼包的數(shù)量決定了譯碼能否開始并持續(xù)進行，但這些編碼包覆蓋的原始信息較少，為了成功譯碼需要接收更多的編碼包;另一方面，度較大的編碼包能覆蓋更多的原始信息，減小譯碼開銷，但容易出現(xiàn)譯碼中斷，同時編譯碼復(fù)雜度也高。

Raptor碼的內(nèi)碼度分布為弱化的LT碼度分布，為了實現(xiàn)線性的譯碼復(fù)雜度，其度分布中最大度不再是K，而是一個較小的值。下面介紹3種常用的內(nèi)碼度分布。度分布的表達式常用函數(shù)表達式和多項式2種方式來描述，前者是度分布的概率分布律，而后者用多項式中的冪次表示度的值，系數(shù)為取相應(yīng)值的概率。

1 )平均度為3的度分布 ωK(d)。度分布ωK(d)［12］是由魯棒孤子分布 μ(d)改進得到，μ(d)是基于理想孤子分布ρ(d)和正數(shù)函數(shù)τ(d)而來，其中，ρ(d)的表達式為

表1給出了k=1 000，R=0.95時，分別采用上述3種度分布編碼時的譯碼開銷。不難看出，隨著平均度的增大，譯碼開銷逐漸減小，但平均度的增大意味著需要進行更多的編譯碼異或操作。因此，為了減小譯碼開銷而顯著增大平均度的設(shè)計思想并不可取。

表1 k=1 000，采用3種度分布編碼時的平均度和譯碼開銷Tab.1 Average degree and overhead of three degree distributions with k=1 000

本文重點研究當系統(tǒng)存在單次反饋時，如何利用反饋來提高Raptor碼的譯碼性能，而度分布對噴泉碼的性能至關(guān)重要，于是在度分布ωK(d)的基礎(chǔ)上，本文提出一種單次反饋的內(nèi)碼度分布，不僅可實現(xiàn)線性且較小的譯碼復(fù)雜度，而且使譯碼開銷明顯降低。

2 單次反饋的內(nèi)碼度分布

當系統(tǒng)存在反饋時，除用反饋控制信息傳輸外，如何有效利用反饋來減小譯碼開銷，可以從3個方面重點考慮:反饋內(nèi)容、反饋時間和發(fā)送端如何調(diào)整。反饋內(nèi)容方面，主要有反饋成功譯出中間包個數(shù)(或者一個比例系數(shù))和反饋具體哪些中間包已譯出(或者沒有譯出的中間包)等2種;反饋時間方面，研究最佳的反饋時間點使譯碼開銷最小;發(fā)送端調(diào)整方面，調(diào)整度分布或者編碼對象等。

2.1 反饋內(nèi)容

當反饋具體哪些中間包已譯出時，需要一個K比特的向量表示，即 g=(g1，…，gi，…，gK)T，其中，gi=0表示第i個中間包未譯出，gi=1表示第i個中間包已譯出。對于短碼來說，K值較小反饋量不大，文獻［8］研究了短碼采用這種反饋方式，并取得了較好的效果。當K的數(shù)量級為103或者104以上的中長碼，反饋量非常大將導(dǎo)致占用過多的信道資源，也會降低整體的效率。因此，中長碼一般采用反饋成功譯出中間包個數(shù)的方式。

當接收端譯出n個中間包后，如果接收的編碼包僅覆蓋譯出的中間包，則該編碼包成為冗余包。例如，中間包 x和 y已譯出，編碼包 m=x⊕ y，“⊕”表示異或運算，由于m中沒有包含對譯碼有

由(7)式不難得出，當n趨近于K時，p趨近1，說明接收端譯出的中間包越多，則接收的冗余編碼包也越多。

2.2 調(diào)整度分布

這里定義，反饋時間點α為接收端譯出中間包的個數(shù)n占源包個數(shù)k的比例。為了最大程度地消除冗余編碼包，期望的編碼對象是K－αk個未譯出的中間包，只需調(diào)整編碼對象，于是度分布應(yīng)為ωK－αk(d)，d=1，2，…，D。但反饋內(nèi)容是一個數(shù) α，發(fā)送端無法只對K－αk個未譯出的中間包進行編碼，編碼對象仍是K個中間包。

設(shè)反饋之后發(fā)送端編碼采用的度分布為ψK(d)，那么ψK(d)應(yīng)滿足(8)式，其中，R是預(yù)編碼的碼率。

當R與α一定時，d是一個常數(shù)，說明采用用的信息，該包為冗余包，接收端會將其丟棄。一個度為d的編碼包是冗余包的概率為ψK(d)編碼具有線性的譯碼復(fù)雜度。

2.3 最佳的反饋時間點

在單次反饋的情況下(假設(shè)反饋信號能被正確接收)，找出使譯碼開銷最小的最佳反饋時間點α非常重要。下面從譯碼進程中編碼包被釋放概率的角度分析，這里參照Luby給出的幾個定理［2］，然后推出Raptor碼每次譯碼迭代后恢復(fù)中間包個數(shù)的表達式。

定義1 編碼包被釋放是指在譯碼進程中，一個中間包譯碼迭代后使某個編碼包的度變?yōu)?，該編碼包恢復(fù)其相關(guān)聯(lián)的中間包后，度變?yōu)?被釋放。

定理1 當還有L個中間包未譯碼迭代時，一個度為d的編碼包被釋放的概率q(d，L)為

由于每個編碼包被釋放時能恢復(fù)一個中間包，那么每次譯碼迭代后恢復(fù)中間包個數(shù)的期望值是K×r(L)，這里假定有K個編碼包。目前，理論進一步推導(dǎo)譯碼效率的變化比較困難，我們仿真了不同k值采用ωK(d)編碼時的K×r(L)與譯碼進程(KL)的函數(shù)曲線，其中L表示未譯碼迭代的中間包個數(shù)，它們表現(xiàn)非常相似，這里僅以 k=1 000，R=0.95為例，仿真曲線如圖2所示。

從圖2可看出，當K－L＞600后，曲線開始下滑，說明恢復(fù)中間包的速率開始變慢;在K－L＞800后，K×r(L)＜1，表明每次譯碼迭代后恢復(fù)中間包的個數(shù)不足1個，譯碼效率明顯降低。因此，可以考慮當譯出大約0.8×k個中間包時反饋具體α的值，發(fā)送端接收反饋信息來調(diào)整編碼度分布，減小冗余包的傳輸，從而提高譯碼效率。

最后，我們給出單次反饋的內(nèi)碼度分布θα(d)方案:發(fā)送端先采用ωK(d)編碼，當接收端譯出大約α×k個中間包后反饋α，發(fā)送端接收α后采用ψK(d)編碼，直到接收端成功譯碼為止。θα(d)的表達式為

3 仿真結(jié)果

圖3仿真了不同的源數(shù)據(jù)包個數(shù)k時，采用內(nèi)碼度分布θα(d)編碼，選擇不同反饋時間點α?xí)r的譯碼開銷ε。α的變化步長為0.1，每個ε值是通過100次蒙特卡洛仿真取平均值得來。可看出，對于不同k值，反饋時間點α取0.8時，譯碼開銷均最小，驗證了0.8是最佳反饋時間點的理論結(jié)果。，小于f2(x)的平均度5.87，說明采用θα(d)編碼，譯碼復(fù)雜度較小，達到了預(yù)期目標。為了進一步驗證θα(d)的性能，這里增加文獻［6］提出的方案γ(d)，即反饋譯出具體哪些中間包進而發(fā)送端調(diào)整編碼對象。表2給出了5種度分布的平均度比較。

圖3 采用θα(d)編碼，選擇不同反饋時間點α?xí)r的譯碼開銷Fig.3 Overhead of different feedback time points for θα(d)

表2 5種度分布的平均度Tab.2 Average degree of five degree distributions

圖4仿真了k=1 000，2 000和5 000時，分別采用5種度分布編碼時的譯碼開銷ε。從圖4中可看出，對于相同的源包個數(shù)k，采用θα(d)和γ(d)編碼時的譯碼開銷大體相同且均最小，同樣達到了預(yù)期的要求。另外，與度分布γ(d)相比，雖然θα(d)的平均度為4.8，大于前者，但采用γ(d)方案所需的反饋量為K比特，其值非常大導(dǎo)致占用過多的信道資源，降低了整體效率。因此，綜合來講，采用θα(d)方案反饋量非常小，譯碼復(fù)雜度較低，同時譯碼開銷明顯減小，表現(xiàn)出更佳的性能。

圖4 分別采用5種度分布編碼時的譯碼開銷εFig.4 Overhead of five degree distributions

4 總結(jié)

本文研究了當系統(tǒng)存在單次反饋時，反饋時間的選擇，以及Raptor碼的內(nèi)碼度分布的調(diào)整方案，目的是為了減少冗余編碼包，進而減小譯碼開銷，同時保持較小的譯碼復(fù)雜度。通過理論分析和仿真給出了最佳的反饋時間點α的值，以及度分布的調(diào)整方案。仿真結(jié)果表明，采用反饋和度分布調(diào)整編碼，明顯減小了譯碼開銷，同時譯碼復(fù)雜度是線性的，達到了預(yù)期的設(shè)計要求。

［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.USA:IEEE Press，2002:271－280.

［3］SHOKROLLAHI A.Raptor codes［J］.IEEE Transactions on Information Theory，2006，52(6):2551－2567.

［4］3GPP.3GPPTS 26.346 V6.3.0，Technical specification

［5］ETSI.TS 102 472 V1.2.1，DVB BlueBook A101 digital video broadcasting(DVB);IP datacast over DVB－H:content delivery protocols［S］. ［s.l.］:ETSI，2006.

［6］JAMES A，MADHUKUMAR A S，ADACHI F.Adaptive rateless coding with feedback for cooperative relay networks［C］//Wireless Communications and Networking Conference.Shanghai:Conference Publications，2012:587－591.

［7］FAZELIM，JAMSHIDIA.The performance evaluation of fountain codes with feedback in cooperative systems［C］//IEEE Iranian Conference on Electrical Engineering.Mashhad:Conference Publications，2013，21:1－5.

［8］SORENSEN JH，KOIKE－AKINO T，ORLIK P.Rateless feedback codes［C］//IEEE International Symposium on Information Theory Proceedings.Cambrige，MA:IEEE press，2012:1767－1771.

［9］YUE G，UPPALM，WANG X.Doped LTDecodingwith Application to Wireless Broadcast Service［C］//IEEE International Conference on Communications.［s.l.］:Conference Publications，2011:1－5.

［10］LUBY M G，MITZENMACHER M，SHOKROLLAHIM A，et al.Efficienterasure correcting codes［J］.IEEE Transactions on Information Theory，2001，47(2):569－584.

［11］AZIZ T，SALEEM N，LQBALM，etal.Performance evaluation ofmulticast relay network using LDPC and convolutional channel codes along－with XOR network coding［J］.The Journal of China Universities of Posts and Telecommunications，2012，19(4):122－128.

［12］MACKAY D JC.Fountain codes［J］.IEE Communications Proceedings，2005，152(6):1062－1068.

雷維嘉(1969－)，男，云南元謀人，博士，教授，主要研究方向為無線通信技術(shù)。E－mail:leiwj@cqupt.edu.cn。

張 偉(1988－)，男，山西臨汾人，碩士研究生，主要研究方向為協(xié)作通信。E－mail:zhangwcqupt@sina.com。

謝顯中(1966－)，男，四川通江人，博士，教授，主要研究方向為移動通信技術(shù)。E－mail:xiexzh@cqupt.edu.cn。

(編輯:魏琴芳)