雷維嘉，劉慧鋒，謝顯中

（重慶郵電大學(xué)個(gè)人通信研究所，重慶 400065）

0 引言

數(shù)字噴泉碼的概念最初是由 M.Luby等［1］在1998年提出的，它是一種基于刪除信道的稀疏圖編碼，但當(dāng)時(shí)只提出了這一概念，并未給出具體的實(shí)現(xiàn)方法。M.Luby［2－3］2002 年提出的 LT 碼是數(shù)字噴泉碼的第一種可實(shí)用的噴泉碼。LT碼編譯碼算法簡(jiǎn)單，譯碼開(kāi)銷(xiāo)很低，但在LT碼中有可能出現(xiàn)少數(shù)源數(shù)據(jù)包沒(méi)有與編碼數(shù)據(jù)包中的任何一個(gè)相關(guān)聯(lián)的情況。Raptor碼［4］是數(shù)字噴泉碼的另一種實(shí)現(xiàn)方法，它通過(guò)內(nèi)外碼級(jí)聯(lián)編碼的方式實(shí)現(xiàn)，外碼是普通的糾錯(cuò)碼，內(nèi)碼為弱化的LT碼，從而進(jìn)一步降低了編譯碼復(fù)雜度，同時(shí)可以提高其性能。文獻(xiàn)［5］給出了一種RS數(shù)字噴泉碼的迭代譯碼算法。

假設(shè)編碼器的原始消息由k個(gè)數(shù)據(jù)包組成，LT碼具體的編碼過(guò)程［2－3］為根據(jù)某一度分布函數(shù)產(chǎn)生每個(gè)編碼數(shù)據(jù)包的度d，LT編碼器從k個(gè)源數(shù)據(jù)包中隨機(jī)地選擇d個(gè)數(shù)據(jù)包，組成編碼數(shù)據(jù)包的候選編碼數(shù)據(jù)包子集，再將它們進(jìn)行異或（XOR）運(yùn)算，即得到一個(gè)編碼數(shù)據(jù)包。根據(jù)需要編碼器不斷重復(fù)上述過(guò)程，可以產(chǎn)生無(wú)限長(zhǎng)的編碼數(shù)據(jù)包序列。譯碼器采用置信傳播譯碼算法［2－3］進(jìn)行 LT譯碼。譯碼過(guò)程是從度為1（d=1）的編碼數(shù)據(jù)包開(kāi)始的，由其可直接得到源數(shù)據(jù)包，然后將它從其他與它相關(guān)聯(lián)的編碼數(shù)據(jù)包中移除（進(jìn)行XOR運(yùn)算）。移除后這些編碼數(shù)據(jù)包的度減1。重復(fù)這一過(guò)程，直到譯出所有的源數(shù)據(jù)包或沒(méi)有度為1的編碼數(shù)據(jù)包?？梢?jiàn)，低度的編碼數(shù)據(jù)包在譯碼過(guò)程中起到很重要的作用，度為1和其他低度的編碼數(shù)據(jù)包的數(shù)量決定了譯碼過(guò)程是否能開(kāi)始并持續(xù)下去，是能否成功譯碼的關(guān)鍵。

采用數(shù)字噴泉碼進(jìn)行傳輸，譯碼器不需要頻繁反饋重傳信息，接收端只需要在收到足夠多的編碼數(shù)據(jù)包并成功恢復(fù)原始信息后，向編碼器發(fā)送一個(gè)終止信號(hào)，從而避免了大量的反饋信息的傳輸。數(shù)字噴泉碼可應(yīng)用于廣播傳輸、分布式存儲(chǔ)和并行下載等［6－7］，可以提高傳輸效率，加快數(shù)據(jù)傳輸速度，提高數(shù)據(jù)傳輸和存儲(chǔ)的可靠性，具有很好的應(yīng)用前景。

實(shí)際的譯碼過(guò)程中，譯碼器譯碼成功所需要的編碼數(shù)據(jù)包的數(shù)量N（＞k）與采用的編碼算法有關(guān)。對(duì)于LT碼，N與所采用的度分布密切相關(guān)。LT編碼度分布函數(shù)的好壞直接影響編碼的性能。一個(gè)好的度分布能夠讓接收端從盡可能少的編碼數(shù)據(jù)包中恢復(fù)出所有的原始數(shù)據(jù)包。

文獻(xiàn)［2］中最早提出了一種具體的LT編碼度分布函數(shù)，稱(chēng)為魯棒孤子分布（robust soliton distribution，RSD）。采用這種度分布函數(shù)進(jìn)行LT編碼，產(chǎn)生的編碼數(shù)據(jù)包的平均度相對(duì)較大，可以保證盡可能少的冗余信息的傳輸，但它產(chǎn)生度較小的編碼數(shù)據(jù)包的數(shù)量不夠多，因而其譯碼過(guò)程可能發(fā)生中斷，這時(shí)編碼器就需要發(fā)送更多的編碼數(shù)據(jù)包，恢復(fù)出所有源數(shù)據(jù)包所需的編碼數(shù)據(jù)包的數(shù)量增大。文獻(xiàn)［8］中另提出了一種LT編碼度分布，稱(chēng)為二進(jìn)制指數(shù)分布（binary exponential distribution，BED），采用這種分布，可以保證在編碼過(guò)程中有足夠多的度很小的數(shù)據(jù)包，使譯碼過(guò)程能持續(xù)進(jìn)行。但是，由于其大部分?jǐn)?shù)據(jù)包的度都很小，每個(gè)編碼數(shù)據(jù)包所攜帶的原始信息相應(yīng)地也比較少，容易出現(xiàn)冗余傳輸，而且可能不會(huì)覆蓋完所有的源數(shù)據(jù)包。這時(shí)，譯碼器為了完全恢復(fù)原始信息，編碼器也需要發(fā)送更多的編碼數(shù)據(jù)包，編碼器的傳輸效率及信道利用率將會(huì)降低。

為了提高譯碼器的譯碼效率，減少編碼器編碼數(shù)據(jù)包的傳輸次數(shù)，本文提出了一種改進(jìn)的LT編碼度分布函數(shù)，稱(chēng)之為開(kāi)關(guān)度分布函數(shù)，它結(jié)合BED和RSD 2種度分布函數(shù)的優(yōu)點(diǎn)，可以取得更好的編譯碼性能。在編碼器傳輸編碼數(shù)據(jù)包的開(kāi)始階段，采用BED分布進(jìn)行LT編碼，然后，根據(jù)已經(jīng)發(fā)送的編碼數(shù)據(jù)包的個(gè)數(shù)，編碼器將LT編碼度分布從BED轉(zhuǎn)換到RSD。仿真結(jié)果顯示，采用開(kāi)關(guān)度分布函數(shù)可以提高譯碼器的譯碼效率，減少編碼器編碼數(shù)據(jù)包的傳輸次數(shù)。

1 開(kāi)關(guān)度分布

為了更好地介紹開(kāi)關(guān)度分布，我們首先介紹了2種LT編碼常用的度分布函數(shù)—魯棒孤子分布和二進(jìn)制指數(shù)分布。在此基礎(chǔ)上，再對(duì)開(kāi)關(guān)度分布進(jìn)行詳細(xì)介紹。

1.1 魯棒孤子分布

在LT噴泉譯碼時(shí)，每次都是從度為1的編碼數(shù)據(jù)包開(kāi)始，并將它從其他與它相關(guān)聯(lián)的編碼數(shù)據(jù)包中移除，這些編碼數(shù)據(jù)包的度將會(huì)減1，然后再尋找新的度為1的編碼數(shù)據(jù)包，以進(jìn)行下一次迭代譯碼。在理想情況下，為了避免冗余，希望在每次迭代中，只有一個(gè)度為1的編碼數(shù)據(jù)包，而且在每次迭代譯碼之后，只出現(xiàn)一個(gè)新的度為1的編碼數(shù)據(jù)包。由此，可以得到一種理想孤子分布

（1）式中:d表示每個(gè)編碼數(shù)據(jù)包的度;k表示參與編碼的源數(shù)據(jù)包數(shù)量;ρ（d）表示編碼數(shù)據(jù)包度為d的概率。

在實(shí)際中，這個(gè)度分布并不理想，因?yàn)樵谧g碼過(guò)程中很可能沒(méi)有度為1的編碼數(shù)據(jù)包，這樣，譯碼器的譯碼過(guò)程將無(wú)法進(jìn)行;另一方面，在編碼時(shí)，一些源數(shù)據(jù)包很可能沒(méi)有被覆蓋，因此，譯碼器就無(wú)法完全恢復(fù)出全部原始信息。

通過(guò)在理想孤子分布中引入2個(gè)額外的參數(shù)c和δ，得到另一種分布—魯棒孤子分布。通過(guò)設(shè)計(jì)c和δ，確保譯碼過(guò)程中期望的度為1的編碼數(shù)據(jù)包個(gè)數(shù)s大約為

（2）式中:δ為譯碼器未能完全恢復(fù)原始信息的概率;c為0和1之間的某一常數(shù)。

首先，定義一個(gè)正數(shù)函數(shù)

然后將理想孤子分布ρ加到τ上，再進(jìn)行歸一化得到魯棒孤子分布

1.2 二進(jìn)制指數(shù)分布

魯棒孤子分布產(chǎn)生的編碼數(shù)據(jù)包的度相對(duì)較大，編碼過(guò)程中，可盡可能地覆蓋所有的源數(shù)據(jù)包。但它產(chǎn)生的度較小的編碼數(shù)據(jù)包較少，譯碼過(guò)程可能產(chǎn)生中斷。為了解決這一問(wèn)題，二進(jìn)制指數(shù)分布增加了小度的概率，其表達(dá)式如下

（5）式中:d表示每個(gè)編碼數(shù)據(jù)包的度;k表示參與編碼的源數(shù)據(jù)包數(shù)量;φ（d）表示采用二進(jìn)制指數(shù)分布進(jìn)行編碼時(shí)，編碼數(shù)據(jù)包度為d的概率。

1.3 開(kāi)關(guān)度分布

在編碼數(shù)據(jù)包傳輸?shù)拈_(kāi)始階段，譯碼器沒(méi)有收到足夠多的度為1和其他低度的編碼數(shù)據(jù)包，因此，它不能譯碼度更大的編碼數(shù)據(jù)包，這時(shí)，減小編碼數(shù)據(jù)包的度可以增加譯碼概率，可以減少譯碼所需要的編碼數(shù)據(jù)包。因此，在編碼器傳輸編碼數(shù)據(jù)包的開(kāi)始階段，發(fā)送度較小的編碼數(shù)據(jù)包，可以保證譯碼器在譯碼的過(guò)程中有足夠多的度為1和其他低度的編碼數(shù)據(jù)包，譯碼器可以更早地開(kāi)始譯碼過(guò)程。

當(dāng)發(fā)送了一定數(shù)量度較小的編碼數(shù)據(jù)包后，將為譯碼器提供了足夠多的度為1和其他低度的編碼數(shù)據(jù)包，這時(shí)，如果編碼器仍發(fā)送度很小的編碼數(shù)據(jù)包，譯碼器將會(huì)收到很多冗余的數(shù)據(jù)包。譯碼器就需要更多的噴泉編碼數(shù)據(jù)包才能夠譯碼出所有的源數(shù)據(jù)包。如果增加編碼數(shù)據(jù)包的度，可以減少冗余數(shù)據(jù)包的數(shù)量，增加覆蓋所有源數(shù)據(jù)包的概率，從而可以減少編碼數(shù)據(jù)包的傳輸次數(shù)。

根據(jù)以上分析，將BED和RSD這2種度分布函數(shù)進(jìn)行組合，給出了一種LT編碼開(kāi)關(guān)度分布函數(shù) ?i，k（d），其表達(dá)式如下

（6）式中:?i，k（d）為采用開(kāi)關(guān)度分布進(jìn)行編碼時(shí)，編碼數(shù)據(jù)包度為d的概率;φ（d）為 BED分布;μ（d）為RSD分布;k為參與編碼的源數(shù)據(jù)包的數(shù)量;α為開(kāi)關(guān)點(diǎn);i表示第i個(gè)噴泉編碼數(shù)據(jù)包。

編碼器進(jìn)行LT編碼時(shí)，采用開(kāi)關(guān)度分布，前αk個(gè)噴泉編碼數(shù)據(jù)包的度服從φ（d），保證接收端能收到足夠多的度很小的編碼數(shù)據(jù)包;后面的噴泉編碼數(shù)據(jù)包的度服從μ（d），以減少冗余信息的傳輸。由此可見(jiàn)，開(kāi)關(guān)點(diǎn)α的設(shè)定直接影響編碼器發(fā)送編碼數(shù)據(jù)包的次數(shù)，如果α設(shè)定太小，譯碼器未能收到足夠多的度較小的編碼數(shù)據(jù)包，這樣，在譯碼時(shí)，可能沒(méi)有度為1的編碼數(shù)據(jù)包，譯碼過(guò)程無(wú)法持續(xù)下去;如果α設(shè)定太大，傳輸過(guò)程中的冗余信息可能會(huì)大大增加。對(duì)于這2種情況，譯碼器為了恢復(fù)原始信息，編碼器都需要發(fā)送更多的編碼數(shù)據(jù)包。從理論上推導(dǎo)出最佳開(kāi)關(guān)點(diǎn)α的值比較困難，我們通過(guò)仿真的方法，給出當(dāng)α取不同值時(shí)，對(duì)于不同的源數(shù)據(jù)包數(shù)量，譯碼器成功譯碼時(shí)，編碼器需要發(fā)送的編碼數(shù)據(jù)包數(shù)量來(lái)得到最佳的開(kāi)關(guān)點(diǎn)。

圖1為參與編碼的源數(shù)據(jù)包數(shù)量k變化時(shí)，編碼器發(fā)送的編碼數(shù)據(jù)包的數(shù)量隨開(kāi)關(guān)點(diǎn)α的變化情況。仿真中，取開(kāi)關(guān)點(diǎn)α的變化步長(zhǎng)為0.05，對(duì)每個(gè)源數(shù)據(jù)包數(shù)量k做30次蒙特卡洛仿真，取其平均值。從仿真結(jié)果可以看到，α=0.1是最佳開(kāi)關(guān)點(diǎn)，此時(shí)編碼器發(fā)送的編碼數(shù)據(jù)包數(shù)量是最少的。

2 仿真結(jié)果

我們通過(guò)仿真驗(yàn)證開(kāi)關(guān)度分布的性能，并與魯棒孤子分布和二進(jìn)制指數(shù)分布進(jìn)行性能比較。在仿真中，編碼器將編碼后的數(shù)據(jù)包發(fā)送給譯碼器，假設(shè)傳輸過(guò)程中數(shù)據(jù)包沒(méi)有丟失。在仿真過(guò)程中，RSD分布中的參數(shù)c和δ分別取0.5和0.03，每個(gè)數(shù)據(jù)包的比特長(zhǎng)度為100，譯碼器采用置信傳播譯碼算法［2］來(lái)進(jìn)行 LT 譯碼。

圖1 參與編碼的源數(shù)據(jù)包數(shù)量變化時(shí)，編碼器發(fā)送的編碼數(shù)據(jù)包數(shù)量與開(kāi)關(guān)點(diǎn)α的關(guān)系Fig.1 Number of transmitted encoded packets for different switch point and different number of source packets

當(dāng)編碼器原始數(shù)據(jù)包數(shù)量k=1 000時(shí)，采用3種不同的度分布進(jìn)行LT編碼時(shí)，譯碼器成功譯碼的源數(shù)據(jù)包的比率與正確接收的編碼數(shù)據(jù)包的數(shù)量之間的關(guān)系如圖2所示。從圖2中可以看出，開(kāi)關(guān)度分布與魯棒孤子分布相比，當(dāng)譯碼器正確接收到的編碼數(shù)據(jù)包較少時(shí)，采用開(kāi)關(guān)度分布進(jìn)行編碼，譯碼器成功譯碼的源數(shù)據(jù)包的比率更大，即譯碼器能譯出的源數(shù)據(jù)包更多。而且采用開(kāi)關(guān)度分布，譯碼器的譯碼時(shí)延更小。與BED分布相比，采用開(kāi)關(guān)度分布時(shí)，接收到少量的編碼數(shù)據(jù)包時(shí)，譯碼器成功譯碼的源數(shù)據(jù)包的比率較小，但隨著接收到的編碼數(shù)據(jù)包數(shù)量的增加，其比率值上升更快，當(dāng)收到1 080個(gè)編碼數(shù)據(jù)包時(shí)，將大于BED分布的比率值。另外，采用開(kāi)關(guān)度分布，譯碼器成功恢復(fù)原始信息所需要的編碼數(shù)據(jù)包更少。

圖2 當(dāng)k=1 000時(shí)，譯碼器成功譯碼的源數(shù)據(jù)包的比率與正確接收的編碼數(shù)據(jù)包的數(shù)量的關(guān)系Fig.2 When k=1 000，the ratio of recovered source packets with different number of the encoded packets successfully received by the destination

譯碼效率η表示編碼器發(fā)送信息的數(shù)據(jù)包數(shù)量k與譯碼器成功譯碼時(shí)編碼器所發(fā)送的編碼數(shù)據(jù)包的數(shù)量N的比值，即η=k/N（0＜ η≤1），譯碼效率越接近于1，度分布函數(shù)性能越好。圖3給出當(dāng)源數(shù)據(jù)包數(shù)量變化時(shí)，譯碼器要成功譯碼原始信息，編碼器需要發(fā)送的編碼數(shù)據(jù)包數(shù)量。從圖3中可以看出，對(duì)于不同數(shù)量的源數(shù)據(jù)包，當(dāng)采用開(kāi)關(guān)度分布進(jìn)行LT編碼時(shí)，與魯棒孤子分布和二進(jìn)制指數(shù)分布相比，譯碼器成功譯碼時(shí)，需要接收的編碼數(shù)據(jù)包數(shù)量都有一定程度的減少，譯碼效率更高。

圖3 參與編碼的源數(shù)據(jù)包數(shù)量變化，譯碼器成功譯碼時(shí)，編碼器發(fā)送的編碼數(shù)據(jù)包數(shù)量Fig.3 Number of the transmitted encoded packets from the source to the destination，the number of the source packets is variable

從圖3中可知，采用BED分布進(jìn)行編碼時(shí)，譯碼器的譯碼效率比采用RSD分布和開(kāi)關(guān)度分布時(shí)的譯碼效率都要差很多。為了更清楚地說(shuō)明開(kāi)關(guān)度分布與RSD分布的區(qū)別，圖4給出了當(dāng)編碼器原始數(shù)據(jù)包數(shù)量k變化時(shí)，編碼器采用RSD和開(kāi)關(guān)度分布進(jìn)行LT編碼時(shí)，譯碼器的譯碼效率。從圖4可以看出，采用開(kāi)關(guān)度分布進(jìn)行LT編碼，譯碼器的譯碼效率總要高于采用RSD分布時(shí)的譯碼效率，即譯碼器成功譯碼時(shí)，編碼器發(fā)送的編碼數(shù)據(jù)包更少。

圖4 參與編碼的源數(shù)據(jù)包數(shù)量變化時(shí)，譯碼器的譯碼效率Fig.4 Decoding efficiency of the destination when the number of the source packets is variable

3 總結(jié)

本文中我們提出了一種改進(jìn)的LT數(shù)字噴泉碼度分布:開(kāi)關(guān)度分布，它綜合了RSD和BED這2種度分布的優(yōu)點(diǎn)，既可以產(chǎn)生足夠多的度較小的編碼數(shù)據(jù)包，又盡可能地覆蓋所有的源數(shù)據(jù)包。通過(guò)仿真得到，當(dāng)開(kāi)關(guān)點(diǎn)為0.1時(shí)，譯碼器成功恢復(fù)原始信息所需的編碼數(shù)據(jù)包數(shù)量最少。仿真結(jié)果顯示，與

RSD和BED這2種度分布相比，其性能都有明顯的改善。在今后的工作中，將進(jìn)一步從理論上推導(dǎo)證明開(kāi)關(guān)點(diǎn)的取值。

［1］ BYERS J，LUBY M，MITZENMACHER M，et al.A digital fountain approach to reliable distribution of bulk data［J］.ACM SIGCOMM Computer Communication Review，1998，28（4）:56－67.

［2］LUBY M.LT codes［C］//Proceedings of the 43rd Annual IEEE Symposium on Foundations of Computer Science（FOCS），2002.USA:IEEE Press，2002:271－280.

［3］MACKAY D.Fountain codes［J］.IEEE Communications Proceedings，2005，152（6）:1062－1068.

［4］ SHOKROLLAHIA.Raptor codes［J］.IEEE Transactions on Information Theory，2006，52（6）:2551－2567.

［5］雷維嘉，張?chǎng)?，謝顯中.一種迭代方法的RS噴泉碼的編譯碼算法［J］.重慶郵電大學(xué)學(xué)報(bào):自然科學(xué)版，2010，22（3）:308－311.

LEIWei－jia，ZHANG Xin，XIE Xian－zhong. Iterative coding and decoding algorithm of RS fountain code［J］.Journal of Chongqing University of Posts and Telecommunications:Natural Science Edition，2010，22（3）:308－311.

［6］ BYERS J，LUBY M，MITZENMACHER M.A Digital Fountain Approach to Asynchronous Reliable Multicast［J］.IEEE Journal on Selected Areas in Communications，2002，20（10）:1528－1540.

［7］ MITZENMACHER M.Digital Fountains:A Survey and Look Forward［C］//IEEE Information TheoryWorkshop.USA:IEEE Press，2004:271－276.

［8］ AGHA K，STOJMENOVIC I.Fountain Code with XOR of Encoded Packets for Broadcasting and Source independent backbone in Multi－h(huán)op Networks using Network Coding［C］//Vehicular Technology Conference， VTC－2009.USA:IEEE Press，2009:1－5.