師春靈　董金明　楊爭艷

摘 要： 在多媒體數(shù)據(jù)傳輸中，重要數(shù)據(jù)對可靠性要求比較高，在較差信道條件下需要更強的保護，為此提出了一種具有不等保護能力的級聯(lián)型UEP-LT碼方案。該方案先對重要比特（More Important Bits，MIB）數(shù)據(jù)進行預(yù)編碼，并引入擴展窗技術(shù)進行優(yōu)化設(shè)計，然后利用And-Or樹分析法對誤碼率性能進行分析。仿真結(jié)果表明，基于擴展窗的級聯(lián)型UEP-LT碼增強了對MIB數(shù)據(jù)的保護程度，并且降低了對次重要比特（Less Important Bits，LIB）性能的損失，具有良好的UEP特性。

關(guān)鍵詞： UEP-LT碼； 不等差錯保護； 擴展窗； 與或樹

中圖分類號：TP391 文獻標志碼：A 文章編號：1006-8228（2013）08-52-04

0 引言

Fountain碼是一類基于Tanner圖的前向糾錯（Forward Error Correcting，F(xiàn)EC）編碼技術(shù)，主要包括LT碼[1]、Raptor碼[2]，采用隨機編碼思想，碼率靈活可變，并且可以糾正、刪除錯誤，它最主要的特點是通過給定一組碼字，可以生成無盡的序列，因此，又叫無碼率碼。無碼率碼與傳統(tǒng)分組碼不同，其碼長n不是預(yù)先確定的，信道的丟失率也未知，編碼符號的個數(shù)隨需要而確定，即：無論信道的丟失率有多大，編碼器可以一直生成編碼符號并通過刪除信道發(fā)送出去，直到接收端接收到足夠多的編碼符號可以恢復(fù)原始信息序列為止。但傳統(tǒng)的Fountain碼實現(xiàn)方案中，各原始數(shù)據(jù)都以相同概率被隨機選取，即對數(shù)據(jù)都只能提供等差錯保護（Equal Error Protection，EEP）。然而，在很多實際場合中，某些信息位的重要性比其余的要高得多，或者要求在譯碼時比其他數(shù)據(jù)優(yōu)先恢復(fù)出來，因此，就提出了一個要求：對不同的信息位，按照其重要程度，分別給予不同的抗干擾保護。不等差錯保護Fountain碼（Unequal Error Protection Fountain，UEPF）就是一種可以滿足這樣應(yīng)用需求的一種新型Fountain碼。我們通過給不同優(yōu)先級的數(shù)據(jù)以不同的編碼冗余度，來實現(xiàn)對不同優(yōu)先級數(shù)據(jù)的保護，使得在編碼速率相同的情況下，相對于EEP來說，較重要的數(shù)據(jù)得到了更高程度的保護，從而能夠在惡劣的條件下提高數(shù)據(jù)傳輸?shù)聂敯粜浴?/p>

本文采用擴展窗技術(shù)來設(shè)計級聯(lián)型UEP-LT碼，實現(xiàn)較小程度的損失低優(yōu)先級數(shù)據(jù)的性能，來增強對高優(yōu)先級數(shù)據(jù)的保護，從而提高數(shù)據(jù)的整體UEP特性。

1 級聯(lián)型UEP-LT碼編譯碼原理

1.1 級聯(lián)型UEP-LT碼編碼原理

LT碼[1]編譯碼性能的好壞取決于度數(shù)分布函數(shù)設(shè)計得是否合理，級聯(lián)型UEP-LT度數(shù)分布仍采用魯棒孤波分布，對MIB數(shù)據(jù)進行編碼時加入預(yù)編碼，本文選用規(guī)則LDPC碼作為預(yù)編碼，編碼完成后的數(shù)據(jù)再通過UEP-LT碼編碼，這樣在較小程度損失LIB數(shù)據(jù)性能的情況下，增強對MIB數(shù)據(jù)的保護程度，同時可以消除LT碼的錯誤平層問題。

假設(shè)k個原始信息符號S1，S2，…，Sk，可以產(chǎn)生無限多個編碼符號T1，T2，…，Tk，…，T∞，本文僅考慮兩種優(yōu)先級的數(shù)據(jù)：MIB數(shù)據(jù)和LIB數(shù)據(jù)，k1為MIB數(shù)據(jù)的個數(shù)，α1=k1/k為MIB數(shù)據(jù)占原始數(shù)據(jù)的比例，則LIB數(shù)據(jù)所占比例為1-α1，個數(shù)為k2=（1-α1）k。p1，p2，…，pk為所有原始信息符號的度分布函數(shù)中每個度數(shù)的概率，q1，q2，…，為MIB數(shù)據(jù)的度分布函數(shù)中每個度數(shù)的概率，一般情況下，α1遠大于p1，而且每個編碼符號的產(chǎn)生都遵從以下法則：

⑴ 先對MIB數(shù)據(jù)進行預(yù)編碼，得到m個中間符號，再將得到的m個符號和k2個LIB數(shù)據(jù)符號作為LT編碼時的信息符號，即m+k2個信息符號；

⑵ 根據(jù)設(shè)計的度數(shù)分布函數(shù)Ω，隨機地選取一個編碼符號的度d；

⑶ 從m+k2個信息符號中，隨機等概率地選取d個不同的信息符號；

⑷ 對所選取的d個信息符號進行異或運算，得到一個編碼符號；

⑸ 不斷重復(fù)上述過程，直到編碼完成。圖1給出了級聯(lián)型UEP-LT碼的編碼過程。

1.2 級聯(lián)型UEP-LT碼譯碼原理

級聯(lián)型UEP-LT碼的譯碼過程分為兩部分：LT碼譯碼過程和LDPC碼譯碼過程。在刪除信道下，LT碼和LDPC碼都采用BP（Belief Propagation，BP）迭代譯碼算法進行譯碼，對于度分布函數(shù)設(shè)計合理的LT碼，這種譯碼算法將較大程度地降低譯碼的復(fù)雜度，具體譯碼過程如下：

⑴ 譯碼端接收到一定數(shù)量的編碼符號集合，根據(jù)編碼符號集合的符號建立與信息符號對應(yīng)關(guān)系的Tanner圖；

⑵ 譯碼端尋找編碼符號中度為1的符號Tj，即編碼符號只與惟一的信息符號鄰接，如果存在，則將和編碼符號Tj鄰接的信息符號Si的值還原為編碼符號Tj的值，即Si=Tj；如果不存在，則譯碼停止；

⑶ 尋找⑴中與已恢復(fù)信息符號Si相鄰的編碼符號集合，將Si與集合中所有的編碼符號進行異或運算，生成新的編碼符號，并刪除Tanner圖中對應(yīng)的邊，從而使得這些編碼符號的度數(shù)減少1，如果在此過程中某一個編碼符號的度數(shù)變?yōu)?，則稱該編碼符號被釋放；

⑷ 重復(fù)步驟⑵和⑶，如果信息符號都已恢復(fù)，則譯碼成功，輸出譯碼值；否則未被恢復(fù)的符號通過預(yù)編碼譯碼恢復(fù)出來。

2 基于擴展窗的級聯(lián)型UEP-LT設(shè)計

2.1 擴展窗方法介紹

擴展窗方法[7-8]的核心思想就是將信息符號按優(yōu)先級分成不同的窗，在同一窗中以相同的概率隨機選取符號進行編碼，在不同的窗中以不同的概率選取符號進行編碼，則信息符號中較重要的符號或要求優(yōu)先譯碼的符號就會被賦予更高的優(yōu)先級，從而實現(xiàn)了對數(shù)據(jù)的不等差錯保護。如圖2所示，將m+k2個信息符號按優(yōu)先級分為t個集合s1，s2，…，st，m為對MIB數(shù)據(jù)進行預(yù)編碼得到的中間編碼符號，用|sl|=（l=1，2，…，t）表示每種優(yōu)先級符號的個數(shù)，用窗wi（i=1，2，…，t）覆蓋所有的信息符號，窗wi包含s1，s2，…，si中的所有符號，那么，并且，第一個窗僅包含MIB數(shù)據(jù)，第二個窗包含MIB數(shù)據(jù)和LIB數(shù)據(jù)，其中與第一個窗重疊部分表示MIB數(shù)據(jù)，依次可以類推其他窗的含義，從而實現(xiàn)了MIB數(shù)據(jù)的被選取概率大于LIB數(shù)據(jù)的被選取概率。

編碼過程如下：

⑴ 對MIB數(shù)據(jù)進行LDPC碼預(yù)編碼，得到m個符號，再將得到的m個符號和LIB數(shù)據(jù)符號作為LT編碼時的信息符號，即m+k2個信息符號；

⑵ 根據(jù)設(shè)計的魯棒孤波分布確定度值d；

⑶ 以概率選取第i個窗；

⑷ 從選中的窗中隨機等概率選取d個信息符號；

⑸ 對所選取的d個信息符號進行異或運算得到一個編碼符號；

⑹ 重復(fù)⑴-⑸，直到編碼完成為止。

2.2 基于擴展窗的級聯(lián)型UEP-LT碼的度分布函數(shù)

假設(shè)K個信息符號，如果UEP-LT碼的接收開銷ε，則譯碼端接收到K（1+ε）個編碼符號，將編碼符號集合中的符號分為r類，并且由屬于不同的窗的信息符號得到，第i類編碼符號的度分布函數(shù)用Ω（i）（x）表示，則第i類編碼符號個數(shù)平均為ΓjK（1+ε），平均度為，將信息符號按優(yōu)先級分為t個集合{s1，s2，…，st}，每個信息符號集合的度分布函數(shù)由對應(yīng)的集合表示，并且，可由信息符號度分布函數(shù)集合計算得到，并且表示大小為kj（）的第j個窗中的信息符號的度分布函數(shù)，則

2.3 與或樹（And-Or Tree）分析法

用Tl表示深度為2l的樹，樹的根符號深度為0，它的孩子符號深度為1，當孩子符號作為根符號時形成的樹，稱Tl的子樹，深度1的符號的孩子符號深度為2，以此類推其他符號，深度為2的或符號作為根符號形成的子樹用Tl-1表示，每棵子樹 Tl-1是獨立的。如圖3所示，定義深度為偶數(shù)（0，2，4，…，2l-2）的符號為或（Or）符號，深度為奇數(shù)（1，3，5，…，2l-1）的符號為與（And）符號。或符號以概率δi，隨機選取i個孩子符號進行或運算，沒有孩子符號的或符號被賦值0；與符號以概率βi，隨機選取i個孩子符號進行與運算，沒有孩子符號的與符號被賦值1，深度為2l每個符號為0或1。如果將樹作為布爾循環(huán)，yl表示Tl的根符號估計0的概率， yl-1表示Tl-1的根符號估計0的概率，那么yl可以看作yl-1的函數(shù)：

下面給出式⑹的推導(dǎo)過程：

用yl表示X符號估計為0的概率，xl-1表示Y符號估計為0的概率，yl-1表示Z符號估計為0的概率，Y符號的值通過其子符號“與”運算得到，當且僅當其所有的子符號的值都為1時，Y符號的值為1。Y符號以概率βi選取i個子符號，每個子符號的值為1的概率為1-yl-1，所有子符號的值都為1的概率為（1-yl-1）i。所以，當Y符號有i個子符號，且其值都為1的概率為xl-1，i=βi（1-yl-1）i，那么

由式⑺和⑻可以得到式⑹的結(jié)論。

下面分析具有r類或符號的與或樹，每一類或符號的個數(shù)足夠大，用GTlj表示深度為2l的樹，它的根符號為第j類或符號，用類似Tl的方法構(gòu)造GTlj，第k類或符號以概率δi，k，k=1，2，…，r隨機選取i個孩子符號進行運算，與符號以概率βi，隨機選取i個孩子符號進行運算，每個與符號的孩子以概率qk成為k類或符號，深度為2l的第k類的每個符號為0或1，y0，k表示GTlj估計0的概率，沒有孩子符號的或符號被賦值0，沒有孩子符號的與符號被賦值1，yl，j表示與或樹GTlj根符號值估計0的概率，那么

Luby等人將隨機編碼的信息符號看成或（Or）符號，編碼符號看成與（And）符號，編碼時形成的Tanner圖作為一個深度為2l的與或樹，利用與或樹分析法對譯碼過程進行分析，得到第l次譯碼的理論誤碼率。將k個信息符號分為t個集合s1，s2，…，st，每個優(yōu)先級的個數(shù)為αik（i=1，2，…，t），且，編碼時采用的度數(shù)分布函數(shù)為Ω（x），文獻[4]給出了第j個優(yōu)先級在l次迭代譯碼后的誤碼率：

pj表示Tanner圖中一條邊與sj中一個信息符號相鄰的概率，qi表示Tanner圖中一條邊與si集合相鄰的概率。若接收端收到的編碼符號個數(shù)為n，則譯碼開銷γ=n/k。定義，容易看到Gl，i，j越大，sj中符號相對于si中符號的誤碼率越低，即恢復(fù)的概率越高，由式（10）可得到式（11）

由式（11）容易看出，當且僅當pj>pi，有Gl，i，j>1，也就是說，要想降低某集合譯碼時的誤碼率，就要增大該集合中每個符號的被選取概率。也就是說在實現(xiàn)LT碼的UEP特性時，一種有效的方法就是增大較高優(yōu)先級集合中信息符號的被選取概率。

2.4 基于擴展窗的級聯(lián)型UEP-LT的誤碼率性能分析

以兩個擴展窗為例，利用And-Or樹分析法對基于擴展窗的級聯(lián)型UEP-LT碼誤碼率性能進行分析，如圖4所示。

由擴展窗方法得到某個編碼符號時，所選取的信息符號要么全部來自w1，要么全部來自w2，對于圖4當信息符號僅來自w1時，參與編碼的符號不包含LIB數(shù)據(jù)，那么LIB集合中符號被選取概率pLIB=0。在選中w1的情況下，MIB集合中符號被選取概率pMIB=Γ1/α1k，MIB集合被選取概率qMIB=1，根據(jù)式⑻得到MIB集合和LIB集合的誤碼率為：

對于圖4當信息符號全部來自w2時，MIB集合和LIB集合中符號被選取概率相等pMIB=pLIB=Γ2/k，MIB集合選取概率α1，相應(yīng)的LIB集合的選取概率為1-α1，根據(jù)式⑻得到MIB集合和LIB集合的誤碼率：

根據(jù)與或樹分析，編碼符號是與符號，兩種情況滿足相“與”關(guān)系，最后得到擴展窗方法的MIB集合和LIB集合的誤碼率：

3 仿真結(jié)果

本文從誤碼率性能方面對基于擴展窗的UEP-LT碼進行仿真，在仿真中，選取信息符號個數(shù)k=4000，MIB集合的符號個數(shù)為400，魯棒孤波分布參數(shù)c=0.01，δ=0.05，Ω（x）=0.001993x+0.490505x2+0.163793x3+0.082042x4+0.049313x5+0.017705x8+0.013795x9+0.002955x19+0.000262x65+0.000255x66。

譯碼過程采用BP迭代譯碼算法，迭代次數(shù)l=80，窗選取概率Γ1=0.12，非均勻權(quán)重UEP-LT碼，km=2，仿真結(jié)果如圖5所示。

EWCUEP-LT表示基于擴展窗級聯(lián)型UEP-LT碼，從圖5中可以看出，當譯碼開銷γ較小時，EWCUEP-LT和非均勻權(quán)重UEP-LT對MIB數(shù)據(jù)和LIB數(shù)據(jù)的誤碼率差距較小，當譯碼開銷γ大于0.9時，EWCUEP-LT對MIB數(shù)據(jù)和LIB數(shù)據(jù)的誤碼率明顯低于非均勻權(quán)重UEP-LT。

均勻權(quán)重UEP-LT誤碼率仿真對比

4 結(jié)束語

為了實現(xiàn)在惡劣信道條件下對MIB數(shù)據(jù)和LIB數(shù)據(jù)的不等差錯保護的同時，降低對LIB數(shù)據(jù)的損失，本文利用擴展窗方法設(shè)計了級聯(lián)型UEP-LT碼，這種在選取符號之前，先選取一個窗的方法，有效地避免了某一次編碼符號只包一個優(yōu)先級數(shù)據(jù)的情況，使得信息符號的選取更具有隨機性，對MIB和LIB的誤碼率性能明顯優(yōu)于非均勻權(quán)重UEP-LT。

參考文獻：

[1] Luby M. LT codes[C] .Proceedings of the 43rd Annual IEEE Symposium Foundations of Computer Science，2002：271-282

[2] Shokrollahi A. Raptor codes[R]. Digital Fountain，Technical Report，2003：1-37

[3] Rahnava rd N， Fekri F. Finite-length Unequal Error Protecti on Rateless Codes：Design and Analysis[C]. Procof IEEE GLOBECOM，2005：1353-1357

[4] Rahnavard N， Vellambi BN， Fekri F.Rateless codes with unequal error protection property[J].IEEE Transactions on InformationTheory，2007.53（4）：1521-1532

[5] Kozat U C， Ramprashad S A. Unequal error protection rateless codes for scalable information delivery in mobile networks[C]. Proceedings of IEEE International Conference on Computer Communications，2007：2316-2320

[6] Woo S S，Cheng M K. Prioritized LT codes[C].Proceedings of the 42nd Annual Information Sciences and Systems，2008：568-573

[7] Studholme C， Blake I. Windowed Erasure Codes[C].Proc. of the ISIT，2006：509-513

[8] 杜超，郭慶.深空通信中基于噴泉碼的前向糾刪方法[J].通信技術(shù)，2010.43（3）：51-53