數字噴泉編碼的研究

張曉晨，苑 林，李曉光

河北大學，河北 保定 071002

0 引言

通信系統的基本目的在于將信息由信源高效且可靠地傳送到信宿。早期人們普遍認為：通信系統的可靠性和有效性是一對不可調和的矛盾。隨著香農在他的論文《通信中的數學理論》[1]中，提出了著名的有擾信道編碼定理，這篇文章奠定了信息理論的基礎，構造接近香農容量限的糾錯碼一直是信道編碼理論的理想，一般使用的都是差錯控制編碼技術[2]。進行差錯控制的方式主要是重發反饋或者是前向糾錯，或者是兩者混合的方式。但在不管在何種方式下，進行編碼時，都給予一定的信道假設，必須預先設定好信道的刪除性，才能設計具體的編譯碼方法。由于信道的時變性，當信道優于假設時，傳輸效率就會降低；當信道劣于假設時，傳輸的可靠性就會降低[3]。近年來受到普遍關注的數字噴泉碼（Digital Fountain Codes）成為構造這種可靠傳輸方案的最佳技術，噴泉碼的發明解決了以上問題。

文件在網絡中傳輸時，是基于包通信的。傳統傳輸協議是簡單的把文件分成若干個數據包，進行重復傳輸直到每一個反饋信道都告知準確接收到。相反，噴泉碼編碼是對文件的隨機編碼，可以產生半無限長的編碼序列，而不考慮信道刪除概率就能恢復源文件。噴泉碼是一種在刪除信道下性能優越的稀疏矩陣碼，也是一種糾刪碼。它是一種與碼率無關的且具有線性譯碼復雜度的隨機編碼方式，由源文件經過編碼產生的碼元不受限制，可以產生無限多的碼元，不論信道中被刪除的碼元有多少，都能通過發送足夠多的編碼碼元供解碼器恢復源文件。由于其編譯碼的特性以及成功譯碼的高概率，不需要對每個數據幀進行逐幀反復確認，因此不會產生“反饋風暴”。 噴泉編碼由k個原始分組生成任意數量的編碼分組,而接收方只要收到其中任意m個編碼分組,即可通過譯碼以高概率成功恢復全部原始數據分組。一般情況下,這里的m略大于k,從而引入一定的譯碼開銷ε,定義為ε=m/k-1,也即m=k（1+ε）。該種編碼生成的數據包有如水珠，接收端有如水杯，每個編碼包不分先后順序，對于接收端，只需要接收足夠數量的編碼包，傳輸就能順利完成。可以形象地說，噴泉碼編碼器就如同源源不斷產生水滴的噴泉，我們只要用杯子接足夠數量的水珠，就可達到飲用的目的[4]。

1 噴泉碼介紹

1.1 LT碼的編譯碼原理

1998年，Luby等首次提出了用于分布數據的數字噴泉技術。一個理想的數字噴泉應該具有如下特征：

1）能夠利用原數據產生無限編碼包序列；

2）對于被分割為k個數據包的一消息，一旦接收到編碼包流中任意m個編碼包，接收者就能重構這一消息。這種重構算法應該非常快。

2002年，Luby提出了一個非常適用于網絡數據分布的編碼方案——LT碼[5]，這是第一類碼率不受限碼的實用實現。LT碼的度分布定義為一個輸出符號節點的度為d的概率。它的編碼算法：

根據給定的度分布函數隨機選取度d；

隨機選取d個不同的輸入符號；

3）編碼后的輸出符號為這d個不同輸入符號的異或和。

如圖1，編碼過程：

1）取一個度分布函數，根據度分布函數進行隨機試驗，選取編碼分組的度數d；

2）從預編碼之后的數據分組中，隨機的選取d個；

3）將這d個數據分組進行模二相加，生成編碼分組。

圖1 編碼過程

解碼過程：

1）在接收端收到的編碼信息單元中，如果存在鄰接度為1（即只有一個鄰接單元）的節點，則其鄰接單元（對應于某一碼層次的輸入數據單元）可以被恢復，因為根據編碼過程該單元是接收到的編碼信息單元的拷貝；

2）如果已經被恢復的輸入數據單元是某個鄰接度不為1的編碼信息單元的鄰接單元，則該編碼信息單元的鄰接度減1，并且在相應的鄰接圖中刪除二者鄰接的邊；

3）如果已經被恢復的輸入數據單元是某個鄰接度為1的編碼信息單元的鄰接單元，則刪除兩者鄰接的邊以及上述與之相連的編碼信息單元；

4）如果在代表鄰接關系的二部圖中找不到與上面剛被恢復的輸入數據單元鄰接的其他編碼信息單元，則刪除該原始輸入數據單元和步驟1）中發起本次疊代過程的編碼信息單元，最后在相應的鄰接圖中刪除代表二者之間鄰接關系的邊，重復從步驟1）開始新一輪的疊代過程；

5）如果在某次疊代過程中，鄰接圖右側不再具有鄰接度為1的編碼信息單元節點則解碼過程結束，若鄰接圖中左側的原始輸入數據單元的節點都得到成功恢復，則解碼過程成功，否則解碼過程失敗[6]。

理論上，生成的編碼符號可以無限多次的通過信道傳輸，編碼符號之間是相互獨立的，這使得噴泉碼是無碼率的，因為噴泉碼的編碼包數目是不固定的，相應的，碼率也是不固定的。實際上，LT碼的編碼算法定義了一個連續輸出符號到輸入符號的二部圖，而度分布直接決定了LT碼的譯碼是否成功，同時也決定產生編碼包所需要的異或運算次數。

度分布函數設計的好壞在很大程度上決定了譯碼的成功率。一個好的度分布函數既要保證編碼器輸出中含有一小部分d 與k差不多大的數據包， 這樣才能保證所有的源數據參與到最終的編碼。同時，又要包含許多d 較小的數據包， 這樣才能保證譯碼的過程不會因為預譯碼集的消失而使譯碼被終止。最初，理想孤波分布被認為是理論上最適合的度分布函數∶

理想孤波分布函數定義：

在理想的情況下，LT碼的編碼分組在每一步中解碼的概率是1/k，每一個釋放的原始分組就會增加到預處理集中，經過k步解碼，k組原始數據就會恢復。但是這個過程是在均值分析的基礎上進行的，在實際應用中，上述過程經常會出現波動，在將k組原始數據都被恢復出來之前，預處理集可能已經為空。因此，由于理想孤波分布的輸入波紋期望值為1，一些小的變化也會導致譯碼的完全失敗。Luby在此基礎上使用了魯棒孤波分布：

魯棒孤波分布如下式：

其中s=cln（k/δ） k1/2[7]，c 取一適當的常數c＞0。δ是接收到K 個確認的數據包后無法解碼的概率的極限， 其中K=k+O（k1/2ln2（k/δ））。將理想孤波分布ρ（d）加上τ（d）就生成了魯棒孤波分布μ（d）。

在使用魯棒孤波分布的情況下，能夠使用接近最小的包來恢復所有的原始數據，LT 碼譯碼成功率至少為1-δ。但是效果也并非十分理想，為了將LT碼的譯碼復雜度降低為線性時間復雜度，可以對其增加預編碼，這種碼就叫做Raptor碼[8]。

1.2 Raptor碼的編譯碼原理

Raptor碼是由Shokrollahi提出的迄今為止最有效的一類數字噴泉碼[9]，如圖2，Raptor碼采用多層預編碼，首先對原始數據進行預編碼，最后使用LT碼進行編碼。中間兩層節點為中間編碼校驗單元，輸入單元到第一層中間編碼校驗單元的映射采用擴展漢明碼，第一層到第二層中間編碼校驗單元的映射采用的是是Gallager在1963年提出的[10]LDPC碼。

圖2 Raptor碼預編碼過程

輸入單元到第1層中間編碼校驗單元的映射采用的編碼是擴展漢明碼，擴展漢明碼是在（2m-1,2m-m-1）的漢明碼的基礎上，再加入一個對于所有碼位進行奇偶校驗的碼位，因此擴展漢明碼碼位滿足以下方程：

這樣（Cn-1，Cn-2，……，C1，C0，C0′）共同組成一個完整的碼字。擴展漢明碼有效信息位為k位，校驗位為m+1位，碼長為n+1，符合（2m,2m-m-1）的形式。在進行解碼的過程中經常由于停止集過小而引起解碼失敗，擴展漢明碼的最小漢明距離為4，在這種情況下停止集的大小一般為2或者3，因此LDPC碼具有較高的解碼概率。

由于Raptor碼的編碼過程包括預編碼過程和LT編碼過程，使得即使編碼后的數據包僅有一部分可恢復，也可以利用這部分被恢復的編碼包來恢復原來的所有數據包。這樣將一個經過預編的碼與一個適當選取的LT碼級聯即得一個具有線性時間譯碼復雜度的Raptor碼。

2 結論

LT Code有著較小編譯碼復雜度，Raptor Code由于采用了預編碼技術對LT Code進行了擴展，因此具有更高的解碼效率。目前，噴泉碼仍在不斷發展，應用領域不斷擴大，具有光明的發展前景。嘗試其它編碼技術（如RS碼和交織碼）與Raptor Code相結合將是今后進一步的研究方向。

[1]C.E.SHANNON.A Mathematical Theory of Communication,Bell Syst.the.J，1948：27.

[2]王新梅.糾錯碼-原理與方法[M].西安：西安電子科技大學出版社，2003：259-268.

[3]王新梅，肖國鎮.糾錯碼——原理與方法[M].西安：西安電子科技大學出版社，1991.

[4]J W Byers,M Luby,M Mitzenmacher.A digital fountain ap-proach to reliable distribution of bulk data[A].Proceedings of the ACM SIGCOMM’98conference on Applications,technolo-gies,architectures,and protocols for computer communication[C].Canada:Vancouv er1998,28(4):56-67.

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

[6]孟慶春，王曉京.Raptor Code預編碼技術研究.計算機工程，2007，33(1)：1-3.

[7]L uby M. LT codes.In:Proceeding of the 43rd Annual IEEE.Symposium on the Foundations of Computer Science(STOC),Vancouver, Canada, 2002，11.

[8]Amin Shokrollahi.Raptor codes.IEEE Transactions on Information Theory，2003，52(6):2551-2567.

[9]A Shokrollahi.Raptor codes[J].IEEE Transactions on Infor-mation theory, 2006, 52(6):2551-2567.

[10]Gallager R G.Low Density Parity Check Codes[D].Cambridge:Cambridge University，1963.