開關度分布:一種改進的LT 數(shù)字噴泉編碼度分布

雷維嘉，劉慧鋒，謝顯中

（重慶郵電大學個人通信研究所，重慶 400065）

0 引言

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

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

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

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

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

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

1 開關度分布

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

1.1 魯棒孤子分布

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

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

在實際中，這個度分布并不理想，因為在譯碼過程中很可能沒有度為1的編碼數(shù)據(jù)包，這樣，譯碼器的譯碼過程將無法進行;另一方面，在編碼時，一些源數(shù)據(jù)包很可能沒有被覆蓋，因此，譯碼器就無法完全恢復出全部原始信息。

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

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

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

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

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

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

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

1.3 開關度分布

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

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

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

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

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

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

2 仿真結果

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

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

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

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

圖3 參與編碼的源數(shù)據(jù)包數(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分布進行編碼時，譯碼器的譯碼效率比采用RSD分布和開關度分布時的譯碼效率都要差很多。為了更清楚地說明開關度分布與RSD分布的區(qū)別，圖4給出了當編碼器原始數(shù)據(jù)包數(shù)量k變化時，編碼器采用RSD和開關度分布進行LT編碼時，譯碼器的譯碼效率。從圖4可以看出，采用開關度分布進行LT編碼，譯碼器的譯碼效率總要高于采用RSD分布時的譯碼效率，即譯碼器成功譯碼時，編碼器發(fā)送的編碼數(shù)據(jù)包更少。

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

3 總結

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

RSD和BED這2種度分布相比，其性能都有明顯的改善。在今后的工作中，將進一步從理論上推導證明開關點的取值。

［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］雷維嘉，張鑫，謝顯中.一種迭代方法的RS噴泉碼的編譯碼算法［J］.重慶郵電大學學報:自然科學版，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.