LT碼編譯碼分析及改進(jìn)

賈惠寧

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

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

中圖分類號(hào)： TN911?34 文獻(xiàn)標(biāo)識(shí)碼： A 文章編號(hào)： 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)的信道編碼相比，具有“無(wú)固定速率”這一特性。這使得數(shù)字噴泉碼可以應(yīng)用到許多復(fù)雜的信道當(dāng)中，這一特性是由數(shù)字噴泉碼的編碼和譯碼方式直接決定的，因此有必要得到性能更加優(yōu)良的數(shù)字噴泉碼的編譯碼方案，使得它在實(shí)際應(yīng)用中可以更加方便，運(yùn)算復(fù)雜度更低。LT碼和Raptor碼是數(shù)字噴泉碼中最典型的兩種方案，而Raptor碼是在LT碼編碼之前進(jìn)行了一個(gè)預(yù)編碼，因此LT碼成為了現(xiàn)在最基礎(chǔ)也是研究最為廣泛的編碼方案。本文將對(duì)LT碼的編譯碼方案進(jìn)行系統(tǒng)的分析，并在此基礎(chǔ)上對(duì)其編碼算法進(jìn)行改進(jìn)，使其性能更加的優(yōu)良，最后通過(guò)仿真驗(yàn)證結(jié)論。

1 LT碼編譯碼方案分析

1.1 LT碼編碼方案分析

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

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

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

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

1.2 LT碼譯碼方案分析

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

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

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

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

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

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

[P=1-1kn] （1）

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

[n>k?lnkδ] （2）

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

現(xiàn)在，假設(shè)某一個(gè)編碼包的度數(shù)為[i]，此時(shí)未被處理的輸入符號(hào)個(gè)數(shù)為[L]，那么[qi，L]表示度數(shù)為[i]的編碼包，在還有[L]個(gè)數(shù)據(jù)包未被處理時(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]個(gè)原始數(shù)據(jù)包未被處理時(shí)度數(shù)為[i]的編碼包中被選中并被釋放的概率，因此[ri，L=piqi，L]，[ rL]表示還有[L]個(gè)原始數(shù)據(jù)包未被處理時(shí)一個(gè)編碼包被釋放的概率，因此：

[rL=ri，L] （7）

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

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

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

在實(shí)際應(yīng)用中，并不可以按照理想的度數(shù)分布函數(shù)來(lái)設(shè)計(jì)數(shù)字噴泉碼，因?yàn)檫@樣會(huì)造成在實(shí)際譯碼過(guò)程中，第一步不能夠快速完成，導(dǎo)致后面的很難找到度數(shù)為1的編碼包，使得譯碼終止。所以理想度數(shù)分布函數(shù)是一種可行性很差的度數(shù)分布函數(shù)，僅在理論研究上存在，也僅具有理論意義。

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

在魯棒度數(shù)函數(shù)分布中提出了中間變量[S]，[S]的物理意義是每一步迭代譯碼中度數(shù)為1的編碼包的個(gè)數(shù)，這是它與理想度數(shù)分布函數(shù)的最大不同之處，這樣將使得譯碼的效率大大提高，同時(shí)，在每一輪迭代譯碼的過(guò)程中，也不會(huì)因?yàn)闆](méi)有度數(shù)為1的編碼包導(dǎo)致譯碼終止。魯棒度數(shù)分布函數(shù)的其余原理與理想度數(shù)分布函數(shù)基本上一致，但是[S]的引入，已經(jīng)從本質(zhì)上改變編譯碼過(guò)程的算法復(fù)雜度，以及整個(gè)編譯碼的譯碼開(kāi)銷。

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

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

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

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

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

2 改進(jìn)的LT碼編碼方案

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

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

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

可以將改進(jìn)的LT碼的編碼方案描述為：

（1） 將原始的數(shù)據(jù)按照等長(zhǎng)[l]分成[k]個(gè)數(shù)據(jù)包（不足的通過(guò)補(bǔ)0完成）；

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

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

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

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

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

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

3 仿真及其分析

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

圖1 使用魯棒分布改進(jìn)前后的性能對(duì)比

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

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

從圖中可看到未等分的性能差一些，因?yàn)楫?dāng)兩組數(shù)據(jù)的個(gè)數(shù)不相等的情況下，兩者數(shù)據(jù)的數(shù)量相差越大，則越近似于原有的編碼方案，相當(dāng)于算法又回到了過(guò)去。

4 結(jié) 語(yǔ)

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

參考文獻(xiàn)

[1] 王新梅，肖國(guó)鎮(zhèn).糾錯(cuò)碼原理與方法[M].西安：西安電子科技大學(xué)出版社，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].應(yīng)用科學(xué)學(xué)報(bào)，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] 劉國(guó)超，陳霄，蘇偉偉，等.短長(zhǎng)度分布式噴泉碼的性能分析[J].通信技術(shù)，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.