鄧在輝 同小軍 甘良才

（1.武漢紡織大學(xué)數(shù)學(xué)與計(jì)算機(jī)學(xué)院，武漢，430200；2.武漢大學(xué)電子信息學(xué)院，武漢，430072）

引 言

噴泉碼由于其能很好適應(yīng)信道變化和具有低的編譯碼復(fù)雜度而受到理論界和產(chǎn)業(yè)界的廣泛關(guān)注，主要包括LT（Luby transform，LT）碼、Raptor碼［1-3］。其最初的實(shí)現(xiàn)方案中，所有的數(shù)據(jù)是同等被保護(hù)的，但在很多情況下，比如多媒體通信、深空通信中，部分?jǐn)?shù)據(jù)需要更高的可靠性，因此設(shè)計(jì)具有不等差錯(cuò)保護(hù)（Unequal error protected，UEP）的噴泉碼成為研究噴泉碼的一個(gè)重要方面。

文獻(xiàn)［4］首次實(shí)現(xiàn)了不等差錯(cuò)保護(hù)的噴泉碼，在編碼時(shí)對于給定的度分布在生成度值后，選取原始信息符號時(shí)增加重要信息比特（More important bits，MIB）的選擇概率，從而提高對MIB的保護(hù)程度。文獻(xiàn)［5］通過改變原始信息符號的選擇策略來實(shí)現(xiàn)噴泉碼的不等差錯(cuò)保護(hù)，讓小的度值編碼符號偏向MIB。文獻(xiàn)［6］采用擴(kuò)展窗方法實(shí)現(xiàn)噴泉碼的不等差錯(cuò)保護(hù)性能，通過窗口包含使優(yōu)先級越高的信息符號被包含的窗口越多，通過窗口的選擇概率和其采用的度分布來增加對優(yōu)先級高的信息符號的保護(hù)。文獻(xiàn)［7］通過一個(gè)編碼二分圖來改變編碼符號度值分配以及與原始信息符號的映射關(guān)系來實(shí)現(xiàn)噴泉碼不等差錯(cuò)保護(hù)，其完全不能利用已有的好度分布。文獻(xiàn)［8-9］在不改變標(biāo)準(zhǔn)噴泉碼結(jié)構(gòu)的基礎(chǔ)上結(jié)合視頻流的參數(shù)來實(shí)現(xiàn)噴泉碼的不等差錯(cuò)保護(hù)，由于其采用了多個(gè)編碼二分圖，會(huì)增大總的傳輸冗余開銷。文獻(xiàn)［10］通過對信息符號集復(fù)制的方法來使不同優(yōu)先級的信息符號的復(fù)制程度不同以實(shí)現(xiàn)不等差錯(cuò)保護(hù)，實(shí)驗(yàn)表明其性能整體上好于文獻(xiàn)［4，6］中的算法。本文采用與或樹工具對其性能進(jìn)行分析，并在其基礎(chǔ)上通過改變原始信息符號的選擇策略，對于度為1和2的編碼符號鏈接的原始信息符號偏向MIB，使得對MIB有更好的保護(hù)能力，而沒有損失對次要信息比特（Less important bits，LIB）的保護(hù)。

1 LT碼編譯碼原理

重復(fù)以上步驟即能產(chǎn)生無限的編碼符號，原始信息符號和編碼符號的關(guān)系如圖1所示，度分布通常采用魯棒孤子分布［1］。

圖1 LT碼示意圖Fig.1 Graph of LT code

其解碼過程采用置信傳播（Belief propagation，BP）譯碼算法，在由信息符號和編碼符號形成的二分圖中，度為1的編碼符號能直接恢復(fù)出信息符號。（1）找出只有一條邊連在原始符號ij的編碼符號em，如果沒有這樣的符號，即停止譯碼。令ij＝em，恢復(fù)出ij。（2）對于所有的連接到ij且x≠m的編碼符號ex，令ex＝ex⊕ij（⊕表示異或操作），同時(shí)去除所有連接到原始符號ij的邊。

重復(fù)以上步驟即完成BP譯碼算法，從中可看出其譯碼過程為不斷去邊的過程，所有原始信息符號被成功解碼的概率隨著接收到的編碼符號的增加而增加。

2 改進(jìn)的塊復(fù)制UEP噴泉碼

傳統(tǒng)噴泉碼對信息符號的保護(hù)是等差錯(cuò)保護(hù)，但在許多情形下，如視頻傳輸中往往需要其具有不等差錯(cuò)保護(hù)特性。

2.1 塊復(fù)制UEP噴泉碼

2.2 基于與或樹的理論分析

圖2 塊復(fù)制UEP噴泉碼的虛擬原始分組構(gòu)建Fig.2 Building virtual source block with UEP fountain codes based on block duplication

式中y0，j＝1，β（x）＝Ω′（x）／Ω′（1），μ＝Ω′（1），δj（x）＝enpjμγ（x-1）。

顯然，在LT碼編碼過程中，原始信息符號的選擇概率能決定其在譯碼過程中的恢復(fù)概率，只要pj＞pi，在t≥1時(shí)，則集合sj中的符號的譯碼成功概率就大于sj中符號的譯碼成功概率，滿足Gt，i，j＞1。

假設(shè)原始信息符號的長度為k，其中高優(yōu)先級信息符號MIB長度為h，復(fù)制因子RF1，RF2分別為R1，R2，擴(kuò)展因子EF為E1，令RF2＝1，則編碼過程中MIB中符號的選擇概率ph，LIB中符號的選擇概率pl分別為式（4）和式（5）

由于R1＞1，于是ph＞pl，據(jù)式（4）得Gt，h，l＞1，即相同次數(shù)譯碼迭代后，高優(yōu)先級信息符號的譯碼概率要大于低優(yōu)先級符號的譯碼概率，實(shí)現(xiàn)噴泉碼不等差錯(cuò)保護(hù)性能。通過增加高優(yōu)先級符號的選擇概率能從整體上提高噴泉碼的不等差錯(cuò)保護(hù)性能，即度數(shù)為1到截?cái)嘀档木幋a符號中有邊連接到高優(yōu)先級符號的概率整體上要高于有邊連接到低優(yōu)先級符號的概率。

2.3 改進(jìn)的塊復(fù)制UEP噴泉碼

文獻(xiàn)［10］中將復(fù)制擴(kuò)展的UEP和文獻(xiàn)［4，6］中不等差錯(cuò)保護(hù)的性能進(jìn)行比較，文獻(xiàn)［10］中的性能在當(dāng)收到大于k的編碼符號時(shí)表現(xiàn)較好，但是，在許多應(yīng)用環(huán)境中經(jīng)常出現(xiàn)收到的編碼符號數(shù)小于k，如在無線視頻實(shí)時(shí)傳輸中，接收到的編碼符號往往少于碼長k，在該情況下希望能盡早地、盡量多地恢復(fù)出重要的信息比特。文獻(xiàn)［10］通過復(fù)制擴(kuò)展能從整體上改變MIB和LIB的不等保護(hù)程度，其思想本質(zhì)上一方面加大了對MIB的選擇概率，另一方面增加了原始信息符號的長度，從而改變了整體上的度分布。在此基礎(chǔ)上，本文從局部上進(jìn)行改進(jìn)，在對信息符號的選取上改變其選取策略，而不損失整體上的不等差錯(cuò)保護(hù)性能。

度為1和2的編碼符號對整個(gè)原始信息符號的譯碼起至關(guān)重要的作用，因?yàn)榻獯a過程是從度為1的編碼符號開始，所有的度為1的編碼符號直接從高優(yōu)先級的符號中選取，則在譯碼過程中，它們能被直接恢復(fù)為原始符號，而不需要等到其他的符號先被解碼出來，增加了高優(yōu)先級符號先于低優(yōu)先級符號被解碼出來的可能性，且其所占比例不能太大。并且度數(shù)越低的輸出符號，其在解碼過程中通過去邊而成為度為1符號的可能性越大。將度為2的編碼符號的一條邊連接到優(yōu)先級高的比特，一邊連接著低優(yōu)先級的原始符號，這樣既保證了對優(yōu)先級高的符號的優(yōu)先保護(hù)，同時(shí)也使得整體的原始符號都有邊能連接到，因?yàn)閲娙a的譯碼過程實(shí)質(zhì)是不斷去邊的過程。改變度為1和2的原始符號選取策略從局部加大了對高優(yōu)先級符號的可靠性保護(hù)，而剩下的度為2和更高度數(shù)的符號能開始低優(yōu)先級符號的解碼并繼續(xù)下去，因此，低優(yōu)先級符號的解碼性能基本沒有下降。

3 實(shí)驗(yàn)結(jié)果及分析

為了評估本文所提出算法的性能，采用與文獻(xiàn)［10］相同的參數(shù)進(jìn)行性能比較，文獻(xiàn)［10］中算法記為塊復(fù)制方法、本文算法記為改進(jìn)的塊復(fù)制方法，簡稱改進(jìn)方法。假設(shè)原始信息符號長度分別為k＝1 000和k＝5 000，信息符號分為兩個(gè)優(yōu)先級塊，其中MIB塊的大小為原始信息符號長度的10%，魯棒孤子分布的參數(shù)為c＝0.1，δ＝0.5，于是，度值為1的編碼符號個(gè)數(shù)遠(yuǎn)小于MIB塊原始符號個(gè)數(shù)，由于刪除信道上的LT碼為通用噴泉碼，通信信道假設(shè)為無損信道［11］。

3.1 比特錯(cuò)誤率的比較

采用BP算法對噴泉碼進(jìn)行譯碼，在迭代過程中，二分圖中如果沒有了度為1的編碼符號，而且這時(shí)還有原始符號沒有被譯碼出來，則整個(gè)譯碼過程結(jié)束，未被譯碼出來的原始符號被判決為誤碼。圖3和圖4分別反映當(dāng)k為1 000和5 000時(shí)的MIB和LIB的比特錯(cuò)誤率（Bit error rate，BER）隨信息冗余長度變化的情況。BER表示錯(cuò)誤符號個(gè)數(shù)與總符號個(gè)數(shù)的比值，即（k1-d）／k1，d表示正確解碼出來的符號的個(gè)數(shù)，k1表示相應(yīng)的原始符號的個(gè)數(shù)。由于LT碼的編解碼具有隨機(jī)的特性，仿真采用多次仿真求平均值的方法，仿真次數(shù)為1 000次。

在k＝1 000時(shí)，采用與文獻(xiàn)［10］中相同的復(fù)制因子RF1＝3，RF2＝1，擴(kuò)展因子EF＝4。如圖3所示，本文提出算法MIB的BER要明顯好于文獻(xiàn)［3］的仿真結(jié)果，當(dāng)傳輸冗余開銷為t′＝0.21時(shí)，MIB的BER值低于10-4，而文獻(xiàn)［10］算法MIB的BER的值低于10-4時(shí)對應(yīng)的頭部開銷t′為0.25，雖然對于LIB的BER相對于文獻(xiàn)［10］中的算法有所下降，本文算法在傳輸冗余開銷為0.38時(shí)，LIB的BER低于10-3，而文獻(xiàn)［10］中此情況下對應(yīng)的t′為0.37，但是，從圖中可以看出，在相同的傳輸冗余開銷時(shí)，兩種算法對于LIB的BER而言基本相同，所以說從整體上而言，在基本沒有損失LIB的性能情況下，很大程度上提高了MIB的BER性能。另外從不等恢復(fù)時(shí)間上看，所提出的算法加大MIB和LIB的譯碼不等恢復(fù)時(shí)間的程度。

圖3 不同傳輸冗余開銷時(shí)的BER（k＝1 000）Fig.3 BER versus transmission overhead for improvement approach and method of Ref.［10］（k＝1 000）

圖4 不同傳輸冗余開銷時(shí)的BER（k＝5 000）Fig.4 BER versus transmission overhead for improvement approach and method of Ref.［10］（k＝5 000）

在k＝5 000時(shí)，采用與文獻(xiàn)［10］中相同的復(fù)制因子RF1＝2，RF2＝1和擴(kuò)展因子EF＝4。如圖4所示，本文提出算法MIB的BER同樣要明顯好于文獻(xiàn)［10］的仿真結(jié)果，當(dāng)傳輸冗余開銷t′為0.1時(shí)，MIB的BER值低于10-5，而文獻(xiàn)［10］中塊復(fù)制算法MIB的BER值低于10-5時(shí)對應(yīng)的傳輸冗余開銷t′為0.13，同樣，所提出的算法在整體上沒有損失LIB的性能，兩種方法都在t′＝0.2時(shí)BER值低于10-7。本文所提出的算法在于不同的碼長都能更高程度地保護(hù)重要的信息比特。

3.2 高優(yōu)先級符號譯碼失敗分布比較

為評估不等差錯(cuò)保護(hù)方法對重要性數(shù)據(jù)的保護(hù)能力，當(dāng)收到的編碼符號個(gè)數(shù)少于原始信息符號個(gè)數(shù)時(shí)，通過直方圖來仿真分析接收MIB數(shù)據(jù)的失敗分布情況，仿真次數(shù)為1 000次。

在k＝1 000、傳輸冗余開銷為-0.05時(shí)，高優(yōu)先級符號譯碼失敗分布如圖5所示，負(fù)號表示接收到的編碼符號個(gè)數(shù)小于原始符號個(gè)數(shù)?？v坐標(biāo)表示發(fā)生的次數(shù)，橫坐標(biāo)表示還有待于譯碼的高優(yōu)先級符號個(gè)數(shù)的百分比，反映在該冗余開銷量情況下，沒有譯碼出來的高優(yōu)先級符號個(gè)數(shù)所占比重。文獻(xiàn)［10］中算法在收到950個(gè)編碼符號時(shí)，至少有95%以上的高優(yōu)先級符號沒有譯出的次數(shù)約為28，而且，占比重最多的情況發(fā)生在70%～75%，約為140。而在本文提出改進(jìn)算法中最多有70%～75%的高優(yōu)先級符號未譯出，且該次數(shù)為4。占比重最多的情況發(fā)生在25%～30%，約為210。比較兩種方法所得出的優(yōu)先級符號譯碼失敗分布，從中可得出提出算法相比文獻(xiàn)［10］中算法能明顯加快MIB的譯碼，使高優(yōu)先級符號得到更好的差錯(cuò)保護(hù)。

在k＝5 000、傳輸冗余開銷為-0.05時(shí)，高優(yōu)先級符號譯碼失敗分布如圖6所示，文獻(xiàn)［10］中算法在收到4 500個(gè)編碼符號時(shí)，至少有95%以上的高優(yōu)先級符號沒有譯出的次數(shù)約為16，而且，占比重最多的情況發(fā)生在65%～70%，約為138。而在提出改進(jìn)算法中最多有55%～60%的高優(yōu)先級符號未譯出，且次數(shù)為3。占比重最多的情況發(fā)生在15%～20%，約為260。從圖6中可得出在k＝5 000時(shí)提出算法相比文獻(xiàn)［10］中算法同樣能明顯加快高優(yōu)先級符號的譯碼，得到了更好的不等差錯(cuò)保護(hù)性能。

圖5 MIB譯碼失敗分布（k＝1 000）Fig.5 Histogram of failure distribution for MIB with improvement approach and method of Ref.［10］（k＝1 000）

圖6 MIB譯碼失敗分布（k＝5 000）Fig.6 Histogram of failure distribution for MIB with improvement approach and method of Ref.［10］（k＝5 000）

4 結(jié)束語

本文分析了基于塊復(fù)制的不等差錯(cuò)保護(hù)LT碼的實(shí)質(zhì)，在其基礎(chǔ)上提出了改進(jìn)的不等差錯(cuò)保護(hù)的LT碼。在編碼時(shí)改變了MIB和編碼符號的鏈接策略，不僅能保持從整體上提高M(jìn)IB和LIB的差錯(cuò)保護(hù)，同時(shí)在不損失LIB的保護(hù)基礎(chǔ)上，能更高程度保護(hù)MIB。通過信息符號選擇策略從局部增加了對MIB的保護(hù)力度，同時(shí)提升了MIB和LIB的恢復(fù)時(shí)間差別。仿真結(jié)果表明本文提出的方法要好于文獻(xiàn)［10］中的方法。

［1］ Luby M.LT codes［C］∥Proc 2002IEEE Symp Foundations of Computer Science（FOCS）.Vancouver，Canada：IEEE，2002：271-282.

［2］ Mackay D J C.Fountain codes［J］.IEEE Proceedings Communications，2005，152（6）：1062-1068.

［3］ Shokrollahi A.Raptor codes［J］.IEEE Transactions on Information Theory，2006，52（6）：2551-2567.

［4］ Rahnavard N，Vellambi B N，F(xiàn)ekri F.Rateless codes with uneaual error protection protection property［J］.IEEE Transactions on Information Theory，2007，53（4）：1521-1532.

［5］ Simon S W，Cheng M K.Prioritized LT codes［C］∥Proceedings of the 42Annual Information Sciences and Systems.New Jersey，USA：［s.n.］，2008：568-573.

［6］ Vukobratovic D，Stankovic V，Sejdinovic D，et al.Scalable video multicast using expanding window fountain codes［J］.IEEE Transactions on Multimedia，2009，11（6）：1094-1104.

［7］ Cao Y，Blostein S D，Chan W Y.Unequal error protection rateless coding design for multimedia multicasting［C］∥ISIT 2010.Austin，Texas，USA：IEEE，2010：2438-2442.

［8］ Tan A S，Aksay A，Akar G B，et al.Rate-distortion optimization for stereoscopic video streaming with unequal error protection［J］.EURASIP Journal on Advances in Signal Processing，2009，2009：1-14.

［9］ Cataldi P，Grangetto M，Tillo T，et al.Sliding-window raptor codes for efficient scalable wireless video broadcasting with unequal loss protection［J］.IEEE Transactions on Image Processing，2010，19（6）：1491-1503.

［10］Ahmad S，Hanzaoui R，Al-Akaidi M.Unequal error protection using fountain codes with application to video communication［J］.IEEE Transactions on Multimedia，2011，13（1）：92-101.

［11］黃誠，易本順.基于拋物線映射的混沌LT編碼算法 ［J］.電子與信息學(xué)報(bào)，2009，31（10）：2527-2531.

Huang Cheng，Yi Benshun.Chaotic LT encoding algorithm based on parabolic map［J］.Journal of Electronics ＆Information Technology，2009，31（10）：2527-2531.