基于擴(kuò)展窗的級(jí)聯(lián)型UEP—LT碼設(shè)計(jì)

師春靈　董金明　楊爭(zhēng)艷

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

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

中圖分類(lèi)號(hào)：TP391 文獻(xiàn)標(biāo)志碼：A 文章編號(hào)：1006-8228（2013）08-52-04

0 引言

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

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

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

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

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

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

⑴ 先對(duì)MIB數(shù)據(jù)進(jìn)行預(yù)編碼，得到m個(gè)中間符號(hào)，再將得到的m個(gè)符號(hào)和k2個(gè)LIB數(shù)據(jù)符號(hào)作為L(zhǎng)T編碼時(shí)的信息符號(hào)，即m+k2個(gè)信息符號(hào)；

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

⑶ 從m+k2個(gè)信息符號(hào)中，隨機(jī)等概率地選取d個(gè)不同的信息符號(hào)；

⑷ 對(duì)所選取的d個(gè)信息符號(hào)進(jìn)行異或運(yùn)算，得到一個(gè)編碼符號(hào)；

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

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

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

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

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

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

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

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

2.1 擴(kuò)展窗方法介紹

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

編碼過(guò)程如下：

⑴ 對(duì)MIB數(shù)據(jù)進(jìn)行LDPC碼預(yù)編碼，得到m個(gè)符號(hào)，再將得到的m個(gè)符號(hào)和LIB數(shù)據(jù)符號(hào)作為L(zhǎng)T編碼時(shí)的信息符號(hào)，即m+k2個(gè)信息符號(hào)；

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

⑶ 以概率選取第i個(gè)窗；

⑷ 從選中的窗中隨機(jī)等概率選取d個(gè)信息符號(hào)；

⑸ 對(duì)所選取的d個(gè)信息符號(hào)進(jìn)行異或運(yùn)算得到一個(gè)編碼符號(hào)；

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

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

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

2.3 與或樹(shù)（And-Or Tree）分析法

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

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

用yl表示X符號(hào)估計(jì)為0的概率，xl-1表示Y符號(hào)估計(jì)為0的概率，yl-1表示Z符號(hào)估計(jì)為0的概率，Y符號(hào)的值通過(guò)其子符號(hào)“與”運(yùn)算得到，當(dāng)且僅當(dāng)其所有的子符號(hào)的值都為1時(shí)，Y符號(hào)的值為1。Y符號(hào)以概率βi選取i個(gè)子符號(hào)，每個(gè)子符號(hào)的值為1的概率為1-yl-1，所有子符號(hào)的值都為1的概率為（1-yl-1）i。所以，當(dāng)Y符號(hào)有i個(gè)子符號(hào)，且其值都為1的概率為xl-1，i=βi（1-yl-1）i，那么

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

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

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

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

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

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

以?xún)蓚€(gè)擴(kuò)展窗為例，利用And-Or樹(shù)分析法對(duì)基于擴(kuò)展窗的級(jí)聯(lián)型UEP-LT碼誤碼率性能進(jìn)行分析，如圖4所示。

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

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

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

3 仿真結(jié)果

本文從誤碼率性能方面對(duì)基于擴(kuò)展窗的UEP-LT碼進(jìn)行仿真，在仿真中，選取信息符號(hào)個(gè)數(shù)k=4000，MIB集合的符號(hào)個(gè)數(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。

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

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

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

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

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

參考文獻(xiàn)：

[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