賈惠寧

摘 要： 數(shù)字噴泉碼是一類不受限的糾錯碼，即從原始數(shù)據分組編碼產生的編碼分組序列是無限的。通過研究數(shù)字噴泉碼中譯碼終止的原因，得出在數(shù)字噴泉碼中，譯碼終止是由于缺少度數(shù)為1的編碼包，導致譯碼提前終止以至譯碼失敗。注意到度數(shù)為2的編碼包在整個編碼包中占有很高的比例；因此，將數(shù)據包分成兩組，在度數(shù)為2時，分別從兩組中取出數(shù)據，這樣可以有效地提高數(shù)據的覆蓋率，降低譯碼提前終止的概率。通過對編碼算法的改進，提高整個數(shù)字噴泉碼的譯碼成功率。

關鍵詞： 數(shù)字噴泉碼； 譯碼終止； 度數(shù)； 改進算法

中圖分類號： TN911?34 文獻標識碼： A 文章編號： 1004?373X（2015）14?0020?04

Analysis and improvement for coding?decoding of LT code

JIA Huining

（Beijing Xinli Machinery Co.， Ltd， Beijing 100039， China）

Abstract： Digital fountain code is a class of rateless erasure code. The number of encoded symbols that is generated from the original data is potentially limitless. By the relative study， the reason of decoding termination of digital fountain code was found， which caused by the lack of degree?1 encode packages， and may lead to decode terminate ahead of time and decoding failure. Because of this， it is found that the degree?2 encode packages occupies a high proportion in the whole encode packages. Therefore， the data package is divided into two groups. When the degree is 2， the data is taken out respectively from the two groups. In this way， the coverage of data can be improved effectively， and the probability of decoding termination in advance can be reduced. With the improvement of coding algorithm， the decoding success rate of digital fountain code was improved.

Keywords： digital fountain code； decoding end； degree； improved algorithm

數(shù)字噴泉碼與傳統(tǒng)的信道編碼相比，具有“無固定速率”這一特性。這使得數(shù)字噴泉碼可以應用到許多復雜的信道當中，這一特性是由數(shù)字噴泉碼的編碼和譯碼方式直接決定的，因此有必要得到性能更加優(yōu)良的數(shù)字噴泉碼的編譯碼方案，使得它在實際應用中可以更加方便，運算復雜度更低。LT碼和Raptor碼是數(shù)字噴泉碼中最典型的兩種方案，而Raptor碼是在LT碼編碼之前進行了一個預編碼，因此LT碼成為了現(xiàn)在最基礎也是研究最為廣泛的編碼方案。本文將對LT碼的編譯碼方案進行系統(tǒng)的分析，并在此基礎上對其編碼算法進行改進，使其性能更加的優(yōu)良，最后通過仿真驗證結論。

1 LT碼編譯碼方案分析

1.1 LT碼編碼方案分析

LT碼的生成矩陣與其編碼的二分圖是一一對應的，節(jié)點的度對應到二分圖中表示與對應節(jié)點相關聯(lián)的邊的個數(shù)。因此，LT碼的度分布函數(shù)決定了其編碼的結構，合理的度數(shù)分布函數(shù)是LT碼編碼方案的關鍵。當使用固定的BP譯碼算法時，LT碼編碼的性能幾乎完全由度數(shù)分布函數(shù)決定；因此希望LT碼的度數(shù)分布函數(shù)盡量滿足以下條件：

（1） 盡可能用最少的接收到的編碼包譯出原始的數(shù)據包，即譯碼開銷盡量小。

（2） 在編碼時使所選取的平均度數(shù)盡量小，這樣可以減少模運算，使得編譯碼代價盡可能的小。

LT碼的度數(shù)分布函數(shù)應該保證所有的數(shù)據包都至少被選取1次，形成所需要的編碼包，即編碼過程應該覆蓋到所有的數(shù)據包，使得在譯碼的過程中不會丟掉某一個數(shù)據包導致譯碼失敗。從編碼的角度考慮，要使平均度數(shù)盡可能小，這樣可以保證運算量小，但是同樣為了保證編碼包可以覆蓋到每一個數(shù)據包，就必須有少量的大數(shù)值度數(shù)存在。如當數(shù)據包的長度[k=100]時，除了要選取大量的小數(shù)值的度數(shù)，如1或2，同時也要選取極少量的大數(shù)值的度數(shù)如99或100。從譯碼的角度考慮，一方面要保持編碼包的釋放速率以得到對應的數(shù)據包，但是同時，釋放的速率不可以太快，如果太快就將導致有大量的數(shù)據包被重復的釋放，這樣帶來不必要的冗余。

1.2 LT碼譯碼方案分析

對于具有良好的度數(shù)分布函數(shù)的LT碼編碼算法，BP譯碼算法往往可以達到較為理想的譯碼復雜度。

LT碼的BP譯碼算法，首先譯出與所有度數(shù)為1的編碼包相連的數(shù)據包，然后再處理與這些數(shù)據包相關聯(lián)的其他編碼包，稱這些編碼包為預處理集；然后再處理預處理集，將預處理集中的元素與相連的編碼包中的元素進行模運算，并且去除度數(shù)為1的編碼包與數(shù)據包的相關聯(lián)性，經過這個處理，原來度數(shù)為1的編碼包將不存在，而原來度數(shù)不為1的編碼包現(xiàn)在度數(shù)將變?yōu)?；最后再對上述過程進行反復，即可以得出譯碼結果；如果最終有1個數(shù)據包未被譯碼出來，稱之為譯碼失敗，反之譯碼成功。

由上述分析可知，BP譯碼算法的關鍵是在查找度數(shù)為1的編碼包，只有不斷地有度數(shù)為1的編碼包存在，譯碼過程才可以不斷地進行下去，而如果在未完成譯碼時，一旦度數(shù)為1的編碼包為0，譯碼將提前終止，這是不希望看到的。而度數(shù)為1的編碼包的數(shù)量直接由LT碼的度數(shù)分布函數(shù)決定，因此就要對LT碼的度數(shù)分布函數(shù)進行專門的分析，以了解度數(shù)為1的編碼包的具體分布和變化情況。

1.3 LT碼度數(shù)分布函數(shù)分析

由于度數(shù)分布函數(shù)是LT碼當中最重要的函數(shù)，其性能的優(yōu)劣直接影響到編碼譯碼算法的進行，因此應該先對度數(shù)分布函數(shù)進行分析。

首先假設一種最理想的度數(shù)分布函數(shù)，即所有的編碼包的度數(shù)均為1，這是在譯碼過程中非常樂意見到的，需要所有的編碼包可以覆蓋到所有的數(shù)據包，這樣在譯碼的過程中將不會有數(shù)據包被遺漏。假設數(shù)據包的個數(shù)為[k]，編碼包的個數(shù)為[n]，則任意一個符號被覆蓋的概率[P]，可等效為所有的符號都不被覆蓋概率，即為：

[P=1-1kn] （1）

假設編碼包中度數(shù)為0的編碼包出現(xiàn)的概率為[δ]，那么所有的數(shù)據包都至少被一個編碼包覆蓋的概率為[1-δ]，則在度數(shù)都為1的分布中，所需要的編碼包的個數(shù)[n]至少需要：

[n>k?lnkδ] （2）

由式（2）可表明，如果度數(shù)分布全部為1，則在譯碼的過程中所需要接收到的編碼包的數(shù)量[n]將是一個極大的值，即譯碼開銷非常大，所以假設的這一理想度數(shù)分布函數(shù)在實際中是不可能使用的。

現(xiàn)在，假設某一個編碼包的度數(shù)為[i]，此時未被處理的輸入符號個數(shù)為[L]，那么[qi，L]表示度數(shù)為[i]的編碼包，在還有[L]個數(shù)據包未被處理時被釋放的概率，則：

[q1，k=1] （3）

[q2，L=2Lkk-1， L=1，2，…，k-1] （4）

[qi，L=ii-1j=0i-3k-L+1-jj=0i-1k-j， i=3，4，…，k；L=1，2，…，k-i+1] （5）

[qi，L=0， i和L為其他] （6）

由上面式子可得，由于[ri，L]表示還剩下[L]個原始數(shù)據包未被處理時度數(shù)為[i]的編碼包中被選中并被釋放的概率，因此[ri，L=piqi，L]，[ rL]表示還有[L]個原始數(shù)據包未被處理時一個編碼包被釋放的概率，因此：

[rL=ri，L] （7）

由以上論述可知，在進行BP譯碼算法時，為了使得BP譯碼算法可以順利的進行，在譯碼的每一步，至少需要一個度數(shù)為1的編碼包，同時，當此次譯碼結束，下一輪譯碼開始的時候，要保證又有新的度數(shù)為1的編碼包出現(xiàn)，這樣才能保證譯碼順利的進行下去。

在理想的度數(shù)分布函數(shù)的情況下，每輪的BP譯碼算法都有且僅有一個度數(shù)為1的編碼包被釋放；在這輪譯碼完成之后，又會有且僅有一個度數(shù)為1的編碼包出現(xiàn)。這就使得在譯碼的過程中，輸入符號加入到BP譯碼的速率與其被處理的數(shù)據相等。一方面，釋放的編碼包需要隨機的譯出一個對應的數(shù)據包；另一方面，要形成一個新的度數(shù)為1的編碼包以使得譯碼過程可以繼續(xù)進行下去。當[k]個輸入符號全部被譯出來之前，一旦不存在度數(shù)為1的編碼包時，譯碼就將失敗，從這個角度來看，要保證度數(shù)為1的編碼包的個數(shù)適當?shù)拇笠恍?，而不要?。綜上分析可知，度數(shù)為1的編碼包的個數(shù)應該適當?shù)拇笮?，這樣可以提高譯碼的效率，同時提高譯碼的成功率。

聯(lián)立式（3）～式（7）以及理想的度數(shù)分布函數(shù)，可以得到[rL=1k]，證實了剛才的結論。理想度數(shù)分布函數(shù)在譯碼過程中度數(shù)為1的編碼包個數(shù)始終保持不變，始終維持在有且僅有一個度數(shù)為1的編碼包。

在實際應用中，并不可以按照理想的度數(shù)分布函數(shù)來設計數(shù)字噴泉碼，因為這樣會造成在實際譯碼過程中，第一步不能夠快速完成，導致后面的很難找到度數(shù)為1的編碼包，使得譯碼終止。所以理想度數(shù)分布函數(shù)是一種可行性很差的度數(shù)分布函數(shù)，僅在理論研究上存在，也僅具有理論意義。

因此，在具體實踐過程中，又提出了魯棒度數(shù)函數(shù)分布（Robust Soliton Distribution），在此對它的性能和實用性進行分析。

在魯棒度數(shù)函數(shù)分布中提出了中間變量[S]，[S]的物理意義是每一步迭代譯碼中度數(shù)為1的編碼包的個數(shù)，這是它與理想度數(shù)分布函數(shù)的最大不同之處，這樣將使得譯碼的效率大大提高，同時，在每一輪迭代譯碼的過程中，也不會因為沒有度數(shù)為1的編碼包導致譯碼終止。魯棒度數(shù)分布函數(shù)的其余原理與理想度數(shù)分布函數(shù)基本上一致，但是[S]的引入，已經從本質上改變編譯碼過程的算法復雜度，以及整個編譯碼的譯碼開銷。

魯棒度數(shù)分布函數(shù)所需要的編碼包的個數(shù)為：

[n=k?ρi+μi≈k+Okln2kδ] （8）

魯棒度數(shù)分布函數(shù)的平均度數(shù)為：

[d=i?μi≈Olnkδ] （9）

同時可知，魯棒度數(shù)分布函數(shù)中的[c，δ]兩個參數(shù)的大小也會影響到譯碼的效率，但它們是個經驗值，并沒有太多的理論依據來確定它們到底取多大，因此需要在實際應用仿真中總結經驗，來確定它的大小。

2 改進的LT碼編碼方案

經過上面分析可知，BP譯碼算法在譯碼初期經常頻繁地停止譯碼，是因為缺少度數(shù)為1的編碼包。因此除了對度數(shù)分布函數(shù)進行改進，使其在每一輪都有足夠多的度數(shù)為1的編碼包之外，還可以對LT碼的編碼方案本身進行改進，從而使得BP譯碼算法不會頻繁的在初期終止，以提高譯碼的成功率以及譯碼效率。在改進方案中使用最經典的，同樣也是使用最廣泛的魯棒度數(shù)分布函數(shù)。

由魯棒度數(shù)分布函數(shù)可知，在編碼包的度數(shù)分布中，度數(shù)為2的編碼包的個數(shù)接近所有編碼包的一半，因此，需要合理地處理好編碼過程中度數(shù)為2的編碼包，以實現(xiàn)效率和成功率的提高。

當隨機度數(shù)為2時，編碼器會在[k]個原始數(shù)據包中，隨機選取2個數(shù)據包，并對他們進行模運算，得到相對應的編碼包，然后發(fā)送到信道中傳輸。但是在選取這2個原始數(shù)據包時，如果采用隨機的方式選取，則總共有[C2k]種可能性，而如果在將原始的數(shù)據包分成2份（可以相等也可以不相等），則總共的可能性為[C2zk-z]，選取的可能性大大降低，意味著覆蓋率將大大提高，這樣，更加有助于在譯碼的每一步都有足夠多的度數(shù)為1的編碼包用于譯碼。

可以將改進的LT碼的編碼方案描述為：

（1） 將原始的數(shù)據按照等長[l]分成[k]個數(shù)據包（不足的通過補0完成）；

（2） 將原始數(shù)據包分成2組，每組的數(shù)據包個數(shù)相等；

（3） 根據已經設計好的度數(shù)分布函數(shù)[ρ]，隨機地選取度數(shù)[d]，作為數(shù)據包的編碼度數(shù)；

（4） 判定[d]是否等于2，如果等于2則從已經分好的兩組當中分別選取一個數(shù)據包，如果不等于2，則在[k]個數(shù)據包中等概率地選[d]個數(shù)據包；

（5） 將選出的[d]個數(shù)據包進行異或運算，生成一個編碼包；

（6） 重復上述步驟，直至接收端接收到足夠多的編碼包。

綜上所述，其實就是在根據度數(shù)選取數(shù)據包時進行了一個判定的過程，依據所隨機到的度數(shù)是否為2，按照不同的方法選取數(shù)據包進行模運算。接下來將會通過仿真，對改進后的LT碼的性能進行研究。

3 仿真及其分析

為了使得仿真可以正確地反應改進的方案，選取魯棒分布作為對比算法公用的度分布函數(shù)。同時為了保證數(shù)據比較準確，選取[K=2 000]，即初始的數(shù)據包個數(shù)為2 000。圖 1為改進前的算法和改進后的算法對應的仿真示意圖。其中[c=0.2，δ=0.01]。

圖1 使用魯棒分布改進前后的性能對比

通過上述仿真結果可看出，在接收包為2 400以下時，兩種算法的性能差不多，這是因為在接收包較少的情況下，度數(shù)為2的編碼包的個數(shù)本身就很少，這就直接導致改進后的算法在性能上并不一定能優(yōu)于改進前的性能，但是隨著接收包的增多，度數(shù)為2的編碼包的個數(shù)極具的增多，這就使得改進后的算法的優(yōu)越性就體現(xiàn)出來了，因此，越往后面走，改進后的算法的性能就越好。同時再次考慮到數(shù)據包分成兩組的過程中，如果不按照等分的方法進行分配的情況再進行一次仿真，這次選取度數(shù)為2的數(shù)據包的分組是不等分的情況，結果如圖2所示。

圖2 度數(shù)為2的數(shù)據包分組不同的情況下性能對比

從圖中可看到未等分的性能差一些，因為當兩組數(shù)據的個數(shù)不相等的情況下，兩者數(shù)據的數(shù)量相差越大，則越近似于原有的編碼方案，相當于算法又回到了過去。

4 結 語

本文詳細的對LT碼的編碼，譯碼和度數(shù)分布函數(shù)進行了剖析，得知在譯碼的過程中離不開度數(shù)為1的編碼包，而它又是動態(tài)存在的，因此需要將度數(shù)為1的編碼包的個數(shù)始終保持在很高的程度，這樣在譯碼的過程中，就不會因為缺少度數(shù)為1的編碼包而導致譯碼終止，最終導致譯碼失敗。因此考慮到在編碼的過程中，對度數(shù)為2的編碼包的編碼過程進行特殊的處理，將所有的數(shù)據包，分成2組（最好等分），從每一組中隨機選取1個數(shù)據包進行模運算，這樣可以大大提高數(shù)據包的發(fā)概率，也大大降低了在譯碼過程中缺少度數(shù)為1的數(shù)據包的可能性，使譯碼的成功率提高。

參考文獻

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

[2] LUBY M. LT codes [C]// Proceedings of the 43rd.Annual IEEE Symposium Foundations of Computer Science （FOCS）. Vancouver， Canada： IEEE， 2002： 271?280.

[3] 朱宏鵬，張更新，謝智東.噴泉碼中LT碼的次優(yōu)度分布[J].應用科學學報，2009，27（1）：6?11.

[4] LEE K R H. A maximum?likelihood decoding algorithm of LT codes with a small fraction of dense rows [C]// IEEE International Symposium on Information Theory. [S.l.]： IEEE， 2007： 2006?2010.

[5] 劉國超，陳霄，蘇偉偉，等.短長度分布式噴泉碼的性能分析[J].通信技術，2012，45（8）：5?8.

[6] MACKAY D J C. Fountain codes [J].IEEE Proc?Commun， 2005， 152（6）： 1062?1068.

[7] KARP R， LUBY M， SHOKROLLAHI A. Finite length analysis of LT codes [C]// IEEE International Symposium on Information Theory. [S.l.]： IEEE， 2004： 39?48.

[8] SHOKROLLAHI A. Raptor codes [J]. IEEE Transactions on Information Theory， 2006， 52（6）： 2551?2567.

[9] Anon. On the optimization of degree distributions in LT code with covariance matrix adaptation evolution strategy [C]// Proceedings of the IEEE Congress on Evolutionary Computation. [S.l.]： IEEE， 2010： 1?8.

[10] BYERS J W， LUBY M， MITZENMACHER M， et al. A digital fountain approach to reliable distribution of bulk data [C]// Proceedings of ACM SIGCOMM98. Vancouver： ACM， 1998： 56?67.