張菁，李惟

（長安大學(xué) 電控學(xué)院，陜西 西安 710061）

LT碼[1]是實(shí)現(xiàn)碼率無關(guān)的數(shù)字噴泉碼[2-4]的一種編碼方法。DVB噴泉碼最先設(shè)計(jì)應(yīng)用于BEC信道中刪除信息的恢復(fù)。在DVB上進(jìn)行廣播業(yè)務(wù)時(shí)，1999年，M.Luby在噴泉碼的理論基礎(chǔ)上提出LT傳輸碼。在應(yīng)用層使用LT碼，通過建立傳輸內(nèi)容之間的XOR約束關(guān)系，在丟失一定數(shù)量傳輸符號(hào)的情況下，仍然可以恢復(fù)原輸入符號(hào)序列。

然而，傳統(tǒng)LT碼在某些應(yīng)用中也存在著不足：首先，實(shí)時(shí)流媒體廣播要求對(duì)接收流數(shù)據(jù)的譯碼具有相對(duì)實(shí)時(shí)性（這要求能夠以最小的編碼冗余度恢復(fù)原始信息）。傳統(tǒng)LT碼對(duì)無法恢復(fù)的輸入符號(hào)，只能等待某些后續(xù)編碼符號(hào)才能恢復(fù)。這樣，在進(jìn)行實(shí)時(shí)流媒體廣播中可能因?yàn)槊襟w流失同步而導(dǎo)致畫面阻塞。其次，編碼符號(hào)度分布函數(shù)的選擇不當(dāng)也會(huì)導(dǎo)致LT編碼過程存在較大的譯碼失敗概率。這說明，由于輸入序列的個(gè)別符號(hào)沒有被"覆蓋"而導(dǎo)致無法完整地恢復(fù)原始信息。

解決上述2個(gè)問題都?xì)w結(jié)為：如何有效地提高短LT碼的符號(hào)恢復(fù)能力（提高可譯碼概率或者降低編碼冗余度）的問題。因此，這里構(gòu)造了一種采用LT碼作為內(nèi)碼、RS碼作為外碼的RS-LT級(jí)聯(lián)編碼方案。仿真結(jié)果表明，這種方案可以提高LT碼的可譯碼概率和符號(hào)恢復(fù)能力，進(jìn)而提高系統(tǒng)恢復(fù)碼元的實(shí)時(shí)性，減少了傳統(tǒng)LT碼在DVB廣播中因媒體流失同步而導(dǎo)致的畫面阻塞。

1 LT碼和RS碼的編譯碼過程

1.1 LT碼的編譯碼過程

LT碼的編碼過程如圖1所示。設(shè)傳輸?shù)姆?hào)序列長度為k，每個(gè)符號(hào)表示為Ai（1≤i≤k）。 編碼過程是將2個(gè)輸入符號(hào)經(jīng)過XOR校驗(yàn)矩陣D，產(chǎn)生n個(gè)輸出符號(hào)（編碼符號(hào)）。G=（g1g2… gj…gn-1gn）代表校驗(yàn)矩陣，其列重稱為度dj（1≤i≤k）。 編碼符號(hào)Xj（1≤j≤k）與輸入符號(hào)產(chǎn)生XOR校驗(yàn)關(guān)系為⊕（[A1A2…Ak]× gj）。 文獻(xiàn)[1]紿出了2種度分布函數(shù)，選擇不同的度分布函數(shù)將對(duì)LT碼的可譯碼概率有很大的影響。

圖1 LT碼的編碼過程示意

由于LT編碼與輸入符號(hào)的長度l無關(guān)，所以可以將LT碼表示為：LT{k，ρ（d）}。 其中，k為編碼輸入符號(hào)序列的長度， ρ（d）為所采用的編碼符號(hào)的度概率分布函數(shù)。一般（n≥k），n的值為每次編碼動(dòng)態(tài)產(chǎn)生。因?yàn)長T碼碼率無關(guān)，所以在LT定義中并不包含編碼后序列長度n和信道特征參數(shù)δ。

LT碼的一次編碼碼率為：R=k/n（n＞k）。 n的值在統(tǒng)計(jì)意義下與以下因素有關(guān)：1）度分布ρ（d）；2）輸入符號(hào)序列長度k；3）刪除信道的刪除概率δ。很明顯，在每次LT碼的編碼過程中n可能都不相同，因此稱LT碼為碼率無關(guān)的編碼方法。在刪除概率為δ的刪除信道中，在概率為P=1-δ的意義下，恢復(fù)k個(gè)輸入符號(hào)序列所需要的編碼符號(hào)序列長度nP=k+Oδ））[1]。 LT的一次編碼冗余度為：r=n/k。

LT碼的譯碼過程可以用二部圖輔助表示，如圖2所示。在圖2中編碼符號(hào) [X1:X6]的度為：[2，2，2，3，2，1]。 其中，X4=A2⊕ A3⊕A4，其他以此類推。譯碼過程進(jìn)行迭代。由譯碼過程可知，即使在δ=0的情況下，LT譯碼過程仍然存在一定的LT碼不可譯概率。

圖2 簡單的LT編碼約束關(guān)系二部圖

1.2 RS碼的編譯碼過程[5-6]

RS頻域編、譯碼過程如圖3所示。圖3中，錯(cuò)誤圖案多項(xiàng)式e（X）和錯(cuò)誤定位多項(xiàng)式d（X）的關(guān)系是：e（X）的非零系數(shù)對(duì)應(yīng)d（X）的零系數(shù)；e（X）的零系數(shù)位置對(duì)應(yīng)的d（X）系數(shù)可以任意取。這樣可以得到（2t-1）-t+1=t個(gè)方程，稱為關(guān)鍵方程。

圖3 RS頻域編、譯碼過程

編碼過程：將信息序列和2t個(gè)零點(diǎn)構(gòu)成的序列看做是某個(gè)RS碼字的頻域變換結(jié)果，則對(duì)該序列進(jìn)行逆傅里葉變換就可以得到所對(duì)應(yīng)的RS碼字，使用帶反饋的移位寄存器很容易實(shí)現(xiàn)。

譯碼過程：首先對(duì)接收序列進(jìn)行有限域傅里葉變換。變換后的頻域序列的后2t位作為校正子。很明顯，如果接收序列是一個(gè)碼字，則校正子多項(xiàng)式的系數(shù)全為零，否則，應(yīng)當(dāng)依據(jù)校正子找到小于等于t個(gè)出錯(cuò)的位置來進(jìn)行糾錯(cuò)。

RS頻域譯碼可以利用頻域錯(cuò)誤序列的遞歸擴(kuò)展過程來獲得E（z），實(shí)現(xiàn)上采用遞歸擴(kuò)展的移位寄存器，比采用Chien氏搜索算法復(fù)雜度低，譯碼速度快。

2 RS/LT級(jí)聯(lián)編碼構(gòu)造方法

由刪除信道和LT碼的特點(diǎn)，LT碼不可譯碼和傳輸信息丟失是等效的，表現(xiàn)為存在無法恢復(fù)的輸入符號(hào)。傳統(tǒng)LT碼的處理方法是繼續(xù)接收后續(xù)的編碼符號(hào)序列以恢復(fù)這些當(dāng)前無法恢復(fù)的輸入符號(hào)。采用RS/LT級(jí)聯(lián)編碼則可以由RS編碼在一定程度上恢復(fù)出這些輸入符號(hào)。

級(jí)聯(lián)編碼構(gòu)造時(shí)需要匹配LT碼的符號(hào)長度和RS碼符號(hào)的邊界，以達(dá)到最大的效率。設(shè)LT碼符號(hào)長度為l，需要首先由本原多項(xiàng)式構(gòu)造適當(dāng)?shù)挠邢抻騁F（q），設(shè)q=2m，則GF（q）中元素（符號(hào)）可由最高階數(shù)為m-1次的多項(xiàng)式表示，并取符號(hào)與其對(duì)應(yīng)多項(xiàng)式系數(shù)為符號(hào)和二進(jìn)制序列之間的對(duì)應(yīng)關(guān)系。對(duì)（n，k）RS碼，如果采用頻域編碼，設(shè)定糾t個(gè)錯(cuò)，有n-k=2t，一個(gè)RS碼字符號(hào)幀長度為q-1。

采用RS/LT級(jí)聯(lián)編碼構(gòu)造方法，相對(duì)文獻(xiàn)[1]中提出的LT編碼方法，可以提高給定k值的LT編碼可譯概率。這說明：首先，在給定ρ（d）下，降低Kρ值，等效為縮短了可譯輸入符號(hào)序列長度；其次，盡可能小的編碼冗余度也意味能夠提高LT碼的可譯碼概率。

下面給出在刪除信道下RS/LT級(jí)聯(lián)編碼構(gòu)造方法如下：1）對(duì)輸入符號(hào)序列｛Ak,l｝進(jìn)行RS編碼，得到編碼后的符號(hào)序列｛Ck,m｝；2） 對(duì)RS編碼序列｛Ck,m｝再進(jìn)行LT編碼，得到LT編碼符號(hào)序列｛Bk,m｝。

3 仿真結(jié)果

設(shè)由于LT編碼不可譯或信道刪除原因，有k′≤k個(gè)原始輸入符號(hào)被LT譯碼恢復(fù)，定義恢復(fù)失敗率：η＝（k-k′）/k。 從平均意義上講，只要η小于RS碼的（符號(hào)）糾錯(cuò)能力η≤[t/n]（[t/n]為取整運(yùn)算），那么，LT碼沒有恢復(fù)的符號(hào)就可以由RS碼恢復(fù)得到。

為了提高LT碼的可譯碼概率，采用RS/LT級(jí)聯(lián)編碼與Robust-Solicon分布的LT碼進(jìn)行對(duì)比。仿真條件如下：刪除概率δ=0，RS碼k=255，n=113，選擇一個(gè)符號(hào)長度為8 bit。 LT碼的度分布函數(shù)選取Robust-Solicon分布。具體仿真結(jié)果如圖4所示。

圖4 RS/LT碼與LT碼的性能比較

從圖4可以看到，在無刪除的短輸入符號(hào)序列（k=255）的情況下，RS/LT級(jí)聯(lián)編碼在編碼冗余度為1.09時(shí)即可完全恢復(fù)輸入符號(hào)，而LT碼在冗余度為1.2時(shí)才可全部恢復(fù)輸入符號(hào)。

在刪除信道中，RS/LT級(jí)聯(lián)編碼可以提高LT碼的抗刪除能力。正如前面分析的結(jié)論：在給定條件下，提高可譯碼概率或者降低編碼冗余度都能夠改善LT碼的性能。在刪除概率δ=0.05的情況下，LT碼和RS/LT級(jí)聯(lián)編碼的性能比較結(jié)果如圖5所示。從圖5中發(fā)現(xiàn)，級(jí)聯(lián)碼的可譯碼概率曲線有輕微的波動(dòng)，這是由于在短輸入序列情況下，LT譯碼后不可恢復(fù)符號(hào)的分布影響了RS碼糾刪結(jié)果所引起的。

圖5 RS/LT碼與LT碼的性能比較

4 結(jié)束語

通過分析認(rèn)為，數(shù)字噴泉碼族在編碼冗余度、可譯碼概率等2個(gè)外在方面上的性能是等效的，也就是說：如果能夠在一定的可譯碼概率下降低編碼冗余度，或者反之，在一定編碼冗余度下提高可譯碼概率，都可以提高LT碼的抗刪除能力。

采用RS/LT級(jí)聯(lián)編碼可以有效地在短輸入序列下提高LT碼的可譯碼概率，在輸入符號(hào)序列長度為255的條件下可降低大約12%的編碼冗余度。減小了傳統(tǒng)LT碼在DVB廣播中因?yàn)槊襟w流失同步而導(dǎo)致畫面阻塞。這是單獨(dú)采用2種編碼方法都無法達(dá)到的，具有很好的應(yīng)用前景。

[1]LUBY M.LT Codes-proceedings of the 43rd IEEE Symp.computer ccience（FOCS'02）[C].Los Alamitos:IEEE Computer Society Press Room，2002:271-280.

[2]SHOKROLLAH A.Raptor codes information theory[J].IEEE Trans actions，2006，52（6）:2551-2567.

[3]王新梅，肖國鎮(zhèn).糾錯(cuò)碼－原理與方法[M].西安：西安電子科技大學(xué)出版社，2003:259-268.

[4]鄧善征，唐紅，楊軍，等.無線數(shù)據(jù)傳輸中RS/LT級(jí)聯(lián)碼的應(yīng)用[J].空軍工程大學(xué)學(xué)報(bào):自然科學(xué)版，2008，9（1）：62-64.

[5]楊軍，茹樂，杜興民，等.RS-LT級(jí)聯(lián)碼在無線圖像傳輸中的應(yīng)用[J].無線電工程:2007，37（10）47-49.

[6]MACKAY D J C.Fountain codes[J].Communication IEEE Proceeding，2005，152（6）:1062-1068.