張曉晨，苑 林，李曉光

河北大學(xué)，河北 保定 071002

0 引言

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

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

1 噴泉碼介紹

1.1 LT碼的編譯碼原理

1998年，Luby等首次提出了用于分布數(shù)據(jù)的數(shù)字噴泉技術(shù)。一個(gè)理想的數(shù)字噴泉應(yīng)該具有如下特征：

1）能夠利用原數(shù)據(jù)產(chǎn)生無限編碼包序列；

2）對(duì)于被分割為k個(gè)數(shù)據(jù)包的一消息，一旦接收到編碼包流中任意m個(gè)編碼包，接收者就能重構(gòu)這一消息。這種重構(gòu)算法應(yīng)該非?？?。

2002年，Luby提出了一個(gè)非常適用于網(wǎng)絡(luò)數(shù)據(jù)分布的編碼方案——LT碼[5]，這是第一類碼率不受限碼的實(shí)用實(shí)現(xiàn)。LT碼的度分布定義為一個(gè)輸出符號(hào)節(jié)點(diǎn)的度為d的概率。它的編碼算法：

根據(jù)給定的度分布函數(shù)隨機(jī)選取度d；

隨機(jī)選取d個(gè)不同的輸入符號(hào)；

3）編碼后的輸出符號(hào)為這d個(gè)不同輸入符號(hào)的異或和。

如圖1，編碼過程：

1）取一個(gè)度分布函數(shù)，根據(jù)度分布函數(shù)進(jìn)行隨機(jī)試驗(yàn)，選取編碼分組的度數(shù)d；

2）從預(yù)編碼之后的數(shù)據(jù)分組中，隨機(jī)的選取d個(gè)；

3）將這d個(gè)數(shù)據(jù)分組進(jìn)行模二相加，生成編碼分組。

圖1 編碼過程

解碼過程：

1）在接收端收到的編碼信息單元中，如果存在鄰接度為1（即只有一個(gè)鄰接單元）的節(jié)點(diǎn)，則其鄰接單元（對(duì)應(yīng)于某一碼層次的輸入數(shù)據(jù)單元）可以被恢復(fù)，因?yàn)楦鶕?jù)編碼過程該單元是接收到的編碼信息單元的拷貝；

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

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

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

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

理論上，生成的編碼符號(hào)可以無限多次的通過信道傳輸，編碼符號(hào)之間是相互獨(dú)立的，這使得噴泉碼是無碼率的，因?yàn)閲娙a的編碼包數(shù)目是不固定的，相應(yīng)的，碼率也是不固定的。實(shí)際上，LT碼的編碼算法定義了一個(gè)連續(xù)輸出符號(hào)到輸入符號(hào)的二部圖，而度分布直接決定了LT碼的譯碼是否成功，同時(shí)也決定產(chǎn)生編碼包所需要的異或運(yùn)算次數(shù)。

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

理想孤波分布函數(shù)定義：

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

魯棒孤波分布如下式：

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

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

1.2 Raptor碼的編譯碼原理

Raptor碼是由Shokrollahi提出的迄今為止最有效的一類數(shù)字噴泉碼[9]，如圖2，Raptor碼采用多層預(yù)編碼，首先對(duì)原始數(shù)據(jù)進(jìn)行預(yù)編碼，最后使用LT碼進(jìn)行編碼。中間兩層節(jié)點(diǎn)為中間編碼校驗(yàn)單元，輸入單元到第一層中間編碼校驗(yàn)單元的映射采用擴(kuò)展?jié)h明碼，第一層到第二層中間編碼校驗(yàn)單元的映射采用的是是Gallager在1963年提出的[10]LDPC碼。

圖2 Raptor碼預(yù)編碼過程

輸入單元到第1層中間編碼校驗(yàn)單元的映射采用的編碼是擴(kuò)展?jié)h明碼，擴(kuò)展?jié)h明碼是在（2m-1,2m-m-1）的漢明碼的基礎(chǔ)上，再加入一個(gè)對(duì)于所有碼位進(jìn)行奇偶校驗(yàn)的碼位，因此擴(kuò)展?jié)h明碼碼位滿足以下方程：

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

由于Raptor碼的編碼過程包括預(yù)編碼過程和LT編碼過程，使得即使編碼后的數(shù)據(jù)包僅有一部分可恢復(fù)，也可以利用這部分被恢復(fù)的編碼包來恢復(fù)原來的所有數(shù)據(jù)包。這樣將一個(gè)經(jīng)過預(yù)編的碼與一個(gè)適當(dāng)選取的LT碼級(jí)聯(lián)即得一個(gè)具有線性時(shí)間譯碼復(fù)雜度的Raptor碼。

2 結(jié)論

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

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

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

[3]王新梅，肖國鎮(zhèn).糾錯(cuò)碼——原理與方法[M].西安：西安電子科技大學(xué)出版社，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預(yù)編碼技術(shù)研究.計(jì)算機(jī)工程，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.