特定條件下的LT碼關(guān)鍵參數(shù)性能研究

摘 要：針對(duì)LT碼的編譯碼過(guò)程、度數(shù)分布以及應(yīng)用環(huán)境特性，提出了LT碼度數(shù)分布中的關(guān)鍵參數(shù)分析模型，其核心思想是在對(duì)LT碼的編譯碼參數(shù)進(jìn)行極限值研究，在數(shù)學(xué)分析的基礎(chǔ)上得出了最優(yōu)化參數(shù)條件下的LT碼性能，并且對(duì)各個(gè)參數(shù)的重要性進(jìn)行分析，提出了數(shù)字噴泉碼譯碼失敗概率的具體值。在極限值條件下研究了接收的數(shù)據(jù)量對(duì)LT碼的影響以及得出了最佳接收數(shù)據(jù)量。理論研究和仿真結(jié)果表明：提出的關(guān)鍵參數(shù)分析模型，能夠較好的擬合實(shí)際LT碼性能條件。

關(guān)鍵詞：數(shù)字噴泉碼 LT碼 度數(shù)分布 應(yīng)用模型

中國(guó)分類號(hào)：TN911.22 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1672-3791（2013）07（c）-0001-02

數(shù)字噴泉碼是近年來(lái)興起的一種新型信道編碼技術(shù)。在1998年，M.Luby等國(guó)外專家提出數(shù)字噴泉碼原理后[1]，其理論與應(yīng)用也越來(lái)越受到關(guān)注。它具有一些特殊的優(yōu)點(diǎn)，數(shù)字噴泉碼不需要數(shù)據(jù)重傳信道，可以大大節(jié)省信道資源。在通信中，有效性和可靠性是一對(duì)矛盾，信道編碼技術(shù)是保證信息傳輸可靠性的必要方法。信道編碼實(shí)質(zhì)上是通過(guò)增加信息的冗余來(lái)提高信息傳輸?shù)目煽啃浴Ｔ谛盘?hào)衰減很嚴(yán)重，傳輸信號(hào)淹沒(méi)在噪聲中時(shí)，可靠性問(wèn)題就尤為嚴(yán)重的凸現(xiàn)出來(lái)了。為了使信號(hào)具有較強(qiáng)的抗噪聲干擾的能力，需要對(duì)信號(hào)加以改造，使信號(hào)內(nèi)部結(jié)構(gòu)具有更強(qiáng)的規(guī)律性或相關(guān)性，以保證在噪聲干擾下仍能發(fā)現(xiàn)錯(cuò)誤，甚至糾正錯(cuò)誤，恢復(fù)原來(lái)的信息。

數(shù)字噴泉碼作為一種信道編碼可以改進(jìn)無(wú)反饋信道的通信方式，它是一種前向糾錯(cuò)編碼技術(shù)。信息在發(fā)送端經(jīng)過(guò)糾錯(cuò)編碼后送入信道，接收端通過(guò)糾錯(cuò)譯碼自動(dòng)糾正傳輸中的差錯(cuò)，這樣的方式叫做前向糾錯(cuò)（FEC）[2]，前向則是指過(guò)程是單向的，沒(méi)有反饋。這種方法具有較低的開銷和較精確的差錯(cuò)恢復(fù)能力。而傳統(tǒng)的FEC存在一些缺陷[3]：（1）在傳輸過(guò)程當(dāng)中，數(shù)據(jù)組與組之間有時(shí)延。（2）當(dāng)接收端在沒(méi)有接收到系統(tǒng)所要求數(shù)據(jù)包個(gè)數(shù)的情況下，需要發(fā)送端重傳整個(gè)數(shù)據(jù)塊，不符合實(shí)時(shí)傳輸。而對(duì)于數(shù)字噴泉碼，不需要發(fā)送端與接收端之間的交互，可以大大減少傳輸時(shí)延。而且，當(dāng)沒(méi)有接收到應(yīng)有的數(shù)據(jù)包個(gè)數(shù)時(shí)，不需要重傳整個(gè)數(shù)據(jù)塊。

數(shù)字噴泉碼的應(yīng)用環(huán)境主要是刪除信道，刪除信道主要是指的一種類似于糾錯(cuò)概率很高的噪聲信道，在其中傳輸?shù)臄?shù)據(jù)要么徹底丟失，要么完全正確無(wú)誤的被接收。

1 數(shù)字噴泉碼

數(shù)字噴泉碼可以從K個(gè)原始數(shù)據(jù)分組生成得到無(wú)窮多個(gè)編碼分組，是一種無(wú)碼率的碼。當(dāng)接收端收到足以譯碼的編碼分組的個(gè)數(shù)時(shí)，便能成功譯碼，該種碼便被形象的稱為噴泉碼。數(shù)字噴泉碼不需要數(shù)據(jù)重傳信道，可以提高信息傳輸?shù)目煽啃浴Ｔ跀?shù)字噴泉碼的研究當(dāng)中，將其分為三類[4，5]：（1）隨機(jī)線性噴泉碼。（2）LT碼（Luby Transtion Code）（3）Raptor碼。嚴(yán)格意義上說(shuō)，隨機(jī)線性噴泉碼不算是噴泉碼，其編譯碼復(fù)雜度太大且成功譯碼概率較低；LT碼是第一種可以實(shí)現(xiàn)的噴泉碼算法，它也是一種稀疏碼，其編譯碼過(guò)程是做二分圖的過(guò)程；Raptor碼是在LT碼基礎(chǔ)上進(jìn)行的編碼，其編碼時(shí)平均度數(shù)較低。本文主要研究LT碼，將會(huì)詳細(xì)討論LT碼的編譯碼過(guò)程[5，6]，其余兩類具體編碼可參見(jiàn)參考文獻(xiàn)[7，8，9]。

1.1 LT編碼

（1）從合適的度數(shù)分布當(dāng)中，隨機(jī)地選擇一個(gè)值，該值即為該編碼分組由幾個(gè)原始數(shù)據(jù)生成，叫做該次編碼分組的度數(shù)。

（2）從原始數(shù)據(jù)分組（比特）當(dāng)中隨機(jī)的選擇個(gè)數(shù)據(jù)，將該個(gè)數(shù)據(jù)進(jìn)行模2和。

（3）重復(fù)以上步驟，生成編碼分組。

1.2 LT譯碼

噴泉碼的譯碼，目前普遍采用MP（message passing）算法，過(guò)程如下。

（1）在得到的編碼分組數(shù)據(jù)當(dāng)中，找到度數(shù)為1的編碼分組，若沒(méi)有，則譯碼失敗。

（2）在二分圖當(dāng)中，將該度數(shù)為1的編碼分組直接復(fù)制為原始數(shù)據(jù)分組。

（3）將上一步生成的原始數(shù)據(jù)分別模2和到與之相連的其余編碼分組當(dāng)中，并且去除該原始數(shù)據(jù)和這些編碼分組的連接關(guān)系。

（4）將上一步當(dāng)中的編碼分組數(shù)據(jù)的度數(shù)減少1。

（5）重復(fù)以上四個(gè)步驟，直至恢復(fù)原始數(shù)據(jù)，譯碼完成。

1.3 LT碼的度數(shù)分布

在上述LT碼的編碼過(guò)程當(dāng)中，需要一個(gè)合適的度數(shù)分布，這是該種算法最關(guān)鍵的問(wèn)題，它必須滿足以下兩個(gè)條件。

（1）在一定意義上度數(shù)分布較高，使得生成的編碼分組能夠盡可能包含所有原始數(shù)據(jù)。

（2）要求編碼分組的度數(shù)不能太高，使LT譯碼能夠成功開始以及進(jìn)行下去。

2 LT碼編譯碼過(guò)程的研究與仿真

2.1 有關(guān)參數(shù)的研究

在數(shù)字噴泉碼編譯碼過(guò)程當(dāng)中，一個(gè)重要的指標(biāo)就是譯碼失敗的概率。根據(jù)提出的理論，它不需要反饋信道，通過(guò)發(fā)送端可以給出無(wú)窮多個(gè)編碼分組，是無(wú)碼率的，只要接收端收到足夠的編碼分組，便能以高概率譯碼。而進(jìn)行整個(gè)過(guò)程時(shí)，度數(shù)分布是一個(gè)重要的概念，直接關(guān)系到譯碼能否開始進(jìn)行以及譯碼成功的概率。

在本文的研究過(guò)程中，信源（原始數(shù)據(jù)）選擇的均是相關(guān)性不大的隨機(jī)數(shù)據(jù)比特。通過(guò)對(duì)魯棒孤子分布的參數(shù)進(jìn)行改進(jìn)，得到最優(yōu)化參數(shù)情況下的譯碼失敗概率，本文在對(duì)參數(shù)的研究過(guò)程當(dāng)中，得出參數(shù)c較參數(shù)的影響大，c會(huì)直接影響譯碼失敗概率，而的變化基本對(duì)譯碼失敗概率沒(méi)有影響。據(jù)圖1和圖2可得出最優(yōu)化的參數(shù)c在0.2處轉(zhuǎn)折，可選擇c大于或等于0.2，這里我們選擇c=0.2，因影響較小，對(duì)可以根據(jù)實(shí)際應(yīng)用情況而定，研究當(dāng)中我們選擇=0.01。

用最優(yōu)化的參數(shù)可以使譯碼失敗的概率降到相對(duì)很低的范圍。

2.2 接收數(shù)據(jù)量對(duì)譯碼性能影響的研究

如上所述，數(shù)字噴泉碼是一種無(wú)碼率的碼，而在數(shù)字噴泉碼的研究過(guò)程當(dāng)中，得出數(shù)字噴泉碼能成功譯碼所需接收的最少數(shù)據(jù)量有三種[5，6]：、以及。其中N是接收數(shù)據(jù)量。本文針對(duì)固定的原始數(shù)據(jù)比特K=512比特，當(dāng)接收到的編碼分組個(gè)數(shù)不同時(shí)得到的譯碼效果如圖3所示。

圖3中顯示了接收數(shù)據(jù)分別為以上三種情況時(shí)的譯碼性能。由圖可以看出，隨著接收端收到的數(shù)據(jù)比特?cái)?shù)的增加，譯碼失敗概率在減少，當(dāng)收到的數(shù)據(jù)比特?cái)?shù)在接近K值時(shí)，該概率減少非常迅速，之后速度下降，基本維持穩(wěn)定。在收到 個(gè)編碼分組時(shí)效果最好，可以得到最佳接收數(shù)據(jù)至少為。而且，對(duì)于一定的原始數(shù)據(jù)信息，并不是收到的編碼分組越多，譯碼概率就越高，是取決于其中度數(shù)1的編碼分組S的個(gè)數(shù)。

2.3 譯碼失敗概率具體值的研究

噴泉碼的譯碼概率和以下幾個(gè)因素有關(guān)：（1）收到編碼分組的個(gè)數(shù)。（2）度數(shù)為1的編碼分組個(gè)數(shù)。因?yàn)閲娙a是一種無(wú)碼率的碼，可以生成無(wú)窮多個(gè)編碼分組，能夠保證接收端有足夠的編碼分組成功譯碼。Luby指出，選擇一個(gè)合適的參數(shù)c后（本文得出最優(yōu)參數(shù)c=0.2），當(dāng)接收端收到個(gè)編碼分組時(shí)便能以高概率成功譯碼，該譯碼成功的概率在Luby的理論上的理想值為1-，但實(shí)際過(guò)程中做不到。經(jīng)過(guò)本文的研究仿真，得出在Luby理論下的譯碼失敗概率平均值為10-2數(shù)量級(jí)左右，而使用噴泉碼最初的理論值以及使用（該值是僅僅保證接收端可以開始進(jìn)行譯碼到完成所需的編碼分組個(gè)數(shù)，并不能保證高概率）時(shí)，譯碼失敗概率平均值則比Luby理論下的值大，如圖4所示。

由圖4可得，接收數(shù)據(jù)量為 和時(shí)其譯碼失敗概率在～數(shù)量級(jí)之間，波動(dòng)相對(duì)較大，而且當(dāng)收到時(shí)較效果好。在具體數(shù)值上，平均值基本為10-2數(shù)量級(jí)左右，如表1所示。而接收數(shù)據(jù)量為時(shí)，其譯碼失敗概率比較大，但較平穩(wěn)，為10-1左右。

3 數(shù)字噴泉碼的進(jìn)一步研究

數(shù)字噴泉碼的應(yīng)用環(huán)境只能是刪除信道，而理想的刪除信道是不存在的。在實(shí)際應(yīng)用過(guò)程當(dāng)中，糾錯(cuò)能力較強(qiáng)的噪聲信道近似于刪除信道，那么可以設(shè)想，在實(shí)際應(yīng)用時(shí)，可以將數(shù)字噴泉碼與糾錯(cuò)能力較強(qiáng)的糾錯(cuò)碼進(jìn)行級(jí)聯(lián)，從而體現(xiàn)出數(shù)字噴泉碼的性能。如圖5所示

該圖是數(shù)字噴泉碼在實(shí)際當(dāng)中應(yīng)用的一種可能模型。其中由糾錯(cuò)碼編碼到糾錯(cuò)碼譯碼部分相對(duì)數(shù)字噴泉碼來(lái)說(shuō)相當(dāng)于刪除信道，因?yàn)榧m錯(cuò)碼對(duì)信道進(jìn)行了“改造”。只要糾錯(cuò)碼的糾錯(cuò)性能達(dá)到一定要求，就能體現(xiàn)出數(shù)字噴泉碼在通信當(dāng)中的優(yōu)越性能。其中糾錯(cuò)碼可以采取Turbo碼，LDPC碼等糾錯(cuò)性能較好的碼。

4 結(jié)論

數(shù)字噴泉碼是在前向糾錯(cuò)碼的基礎(chǔ)上發(fā)展而來(lái)的，它應(yīng)用于刪除信道，且不需要顧及信道中刪除事件的統(tǒng)計(jì)特性。它在發(fā)送端發(fā)送無(wú)窮多個(gè)編碼分組，只要接收端收到一定數(shù)量的編碼分組數(shù)據(jù)，就能夠以高概率成功譯碼。數(shù)字噴泉碼在提出的時(shí)候只是一個(gè)概念，并沒(méi)有可行的算法，而LT是第一種實(shí)現(xiàn)的數(shù)字噴泉碼，它充分繼承了數(shù)字噴泉碼的優(yōu)點(diǎn)，但是LT碼的編譯碼復(fù)雜度比較大，實(shí)時(shí)性較差。同時(shí)，刪除信道也是數(shù)字噴泉碼理論的一個(gè)重要組成部分，本文首先對(duì)LT碼的各個(gè)方面性能及參數(shù)做了較深入的研究，給出了LT碼的一些結(jié)論，并且提出了一種可能的刪除信道應(yīng)用模型，當(dāng)應(yīng)用糾錯(cuò)能力較強(qiáng)的碼時(shí)，可以實(shí)現(xiàn)數(shù)字噴泉碼的實(shí)際應(yīng)用。在后續(xù)的研究當(dāng)中，需要對(duì)數(shù)字噴泉碼的算法進(jìn)行改進(jìn)，使其編譯碼復(fù)雜度下降，提高在應(yīng)用時(shí)的可靠性和有效性。

參考文獻(xiàn)

[1]盧守信.噴泉碼技術(shù)研究[J].信息科技，2007，6：101-102.

[2]張宗橙.糾錯(cuò)編碼原理和應(yīng)用[M].北京：電子工業(yè)出版社，2003，4：25-27.

[3]熊鷹，金心宇.前向糾錯(cuò)編碼傳輸機(jī)制的優(yōu)化[J].江南大學(xué)學(xué)報(bào)，2006，4：127-131.

[4]MacKay D J C.Fountain codes[J].IEE Proc.Commun，2005，152（6）：1062-1068.

[5]AminShokrollahi.FountainCodes[J].EPFL.2003.

[6]Michael Luby.LT Codes[C].Proceedings of the 43r Annual IEEE Symposium on Foundations of Computer Science，2002：1-10.

[7]王仕奎，張愛(ài)清.基于噴泉碼的分布式魯棒存儲(chǔ)[J].武漢大學(xué)學(xué)報(bào)：工學(xué)版，2007，6.

[8]孟慶春，王曉京.Raptor Code預(yù)編碼技術(shù)的研究[J].計(jì)算機(jī)工程，2007，1.

[9]Amin Shokrollahi.Raptor Codes[C].IEEE Transactionson Information Theory，2006，52（6）：2551-2567.