噴泉碼編譯碼原理研究和分析

廖林冰（國防科技大學(xué)，長沙　410000）

噴泉碼編譯碼原理研究和分析

廖林冰
（國防科技大學(xué)，長沙410000）

摘要:噴泉碼是一種新型的糾刪碼技術(shù)，其創(chuàng)新性源于它能成圖，因此在工程領(lǐng)域應(yīng)用前景較好。本文首先綜合性地分析了噴泉碼的原理以及實(shí)現(xiàn)方式，然后研究了噴泉碼編譯中兩種譯碼形式，并分析其優(yōu)缺點(diǎn)。

關(guān)鍵詞:噴泉碼;高斯消元算法；算法

1　前言

噴泉碼具有傳播速度快、無需信道反饋的優(yōu)勢，所以被廣泛應(yīng)用在3G網(wǎng)絡(luò)中，不但如此噴泉碼已經(jīng)延伸到分布式儲(chǔ)存和太空通信領(lǐng)域，可見噴泉碼會(huì)隨著時(shí)代的發(fā)展，產(chǎn)生巨大的經(jīng)濟(jì)效應(yīng)。因此研究噴泉碼的編譯原理是當(dāng)下時(shí)代的需要。

2　噴泉碼編譯的原理和實(shí)現(xiàn)方式

無碼率是噴泉碼的一個(gè)特征，該特征能夠完成無終結(jié)性的編碼符號(hào)譯碼，并且編碼符號(hào)都是隨機(jī)、獨(dú)立生成。這類編碼無休止的生成，就如同是水滴向外噴，噴向如同杯子形狀的接收端。噴泉碼具有獨(dú)立且隨機(jī)性的特征，各個(gè)字碼塊中都包括源信息并不被杯狀的接收端重視，而是在到達(dá)刪除信道后，可以任意的刪減噴泉碼中的任意碼，同時(shí)并不影響其余的譯碼參與到信息傳輸中去。

2.1LT譯碼原理

LT編碼方式能夠直接將向量信號(hào)向(x1,x2....xk)輸入后，就會(huì)將任意的獨(dú)立向量計(jì)算出來。以下是對(duì)任意一個(gè)編碼符號(hào)進(jìn)行計(jì)算的環(huán)節(jié)：

2.2輸入信息度分布

之所以度分布信息作為噴泉碼中設(shè)計(jì)編碼特性的關(guān)鍵所在，是因?yàn)閲娙a進(jìn)行譯碼時(shí)以接收信息中d等于1節(jié)點(diǎn)的分列形式為依托。這樣才能夠確保譯碼的實(shí)現(xiàn)，并且在更迭過程中將節(jié)點(diǎn)1永無休止的生成。大多數(shù)節(jié)點(diǎn)都有較小的度值，這樣就會(huì)降低譯碼的復(fù)雜運(yùn)算度，保證譯碼順利完成；度值如果較大，就表明編碼的節(jié)點(diǎn)和參與量均少，為了杜絕遺漏編碼就會(huì)有調(diào)用較大的度值。為了確保正確的譯碼實(shí)現(xiàn)，一個(gè)節(jié)點(diǎn)信息相連接編碼時(shí)，至少是一條邊。

3　介紹噴泉碼中典型的編譯方式以及其仿真結(jié)果

3.1高斯消元譯碼算法

作為一類在噴泉碼技術(shù)中較為常見的高斯消元譯碼算法，能夠適合各類噴泉碼的譯碼。通過研究刪除信道得知，運(yùn)用最大似然譯碼算法應(yīng)用在線性譯碼中與線性公式求解相等，所以高斯消元法是可以實(shí)現(xiàn)噴泉碼的譯碼。以下是高斯消元算法的流程：

將n定義為接收端接收的符號(hào)，N則是表示輸入的n×1接受向量，H表示為矩陣。第一步，在N的作用下，將H擴(kuò)展為H'即增廣矩陣，即H/N＝H’。第二步，將H’轉(zhuǎn)換成為1的矩陣單位，必須依托于矩陣的初等變化原理，此時(shí)1/N’＝H’。第三步，當(dāng)矩陣的單位有最大的矩陣值時(shí)，那么說明能實(shí)現(xiàn)譯碼，這時(shí)譯碼輸出的待求解信息向量X與增廣向量N’相等；當(dāng)沒有盡可能大的矩陣出現(xiàn)，就說明譯碼無法成功，這時(shí)信息會(huì)繼續(xù)輸入到接收端，再進(jìn)行下一個(gè)流程的譯碼。

通過對(duì)高斯消元譯碼整個(gè)流程得知，k這一信息塊長度的增加會(huì)導(dǎo)致運(yùn)算量的迅速增長，所以計(jì)算的難度也有所增加，因此只適合用于短噴泉碼的譯碼工作。

3.2置信傳播編譯算法

置信傳播算法即BP算法，通常被人叫做消息傳播（MP）算法。在度適當(dāng)分布的情況下，利用該種算法能夠在一定程度上提升計(jì)算機(jī)性能，然而在進(jìn)行中長碼字進(jìn)行譯碼時(shí)，無法提升計(jì)算機(jī)的運(yùn)算速度。截至目前為止，BP算法是被人廣泛應(yīng)用卻計(jì)算噴泉碼時(shí)較為有效的算法。

根據(jù)噴泉碼是帶圖糾刪碼技術(shù)的原理，所以用Tanner圖來表示較為恰當(dāng)。將信息符號(hào)n個(gè)輸送到接收端之后，一個(gè)信息符號(hào)所表達(dá)出來的都會(huì)用k維的列向量，這時(shí)H作為校驗(yàn)矩陣，n×k等于H.接收的圖像中用坐標(biāo)（V,E）來表示，每組節(jié)點(diǎn)的組合都是用V=Vs∪Vc來表示，而每組符號(hào)的節(jié)點(diǎn)是用VS={S0,S1...SK-1}來表示，校驗(yàn)節(jié)點(diǎn)則是用VC={C1,C2,...CK}來表示；每組邊集合用E來表示，當(dāng)hi,j≠0,hi,jH,且i小于k大于0和j小于n大于0時(shí)，則會(huì)得出存在邊的與集合的關(guān)系(Si,Cj)E，因此Vs1表示的集合是由全部符號(hào)節(jié)點(diǎn)與其作用的校驗(yàn)節(jié)點(diǎn)所組成。

當(dāng)有k個(gè)接收符號(hào)在接收端時(shí)，會(huì)激活譯碼器，進(jìn)行譯碼作業(yè)。當(dāng)將k個(gè)符號(hào)全部譯完后，就會(huì)停止這一段落的譯碼。在譯碼工作停止后，進(jìn)行下一個(gè)流程的符號(hào)接收工作，一直到滿足k個(gè)時(shí)，譯碼器再進(jìn)行譯碼時(shí)才會(huì)停止接收符號(hào)。BP算法是一個(gè)循環(huán)往復(fù)的計(jì)算過程。因此在置信傳播譯碼算法中我們通常將其分為兩類，即硬判決算法和軟判決算法。

在刪除信道丟失后的一組編碼符號(hào)，沒有任何誤差的情況下，可以利用硬判決進(jìn)行譯碼。特別是在某一個(gè)符號(hào)左右的信息節(jié)點(diǎn)是相對(duì)固定時(shí)，譯碼器就會(huì)默認(rèn)為相鄰信息符號(hào)一致。軟判決算法則是能在信道信號(hào)弱或者受到噪聲影響的情況下執(zhí)行譯碼作業(yè)，這時(shí)采用軟判決譯碼方法會(huì)在很大程度上確保譯碼的正確性。

3.3結(jié)果分析

通過以上我們對(duì)GE算法與BP算法的性能表述和線性隨機(jī)編碼情況下對(duì)兩種算法相比較得知，BP在節(jié)點(diǎn)起始點(diǎn)小于1的狀況下，無法成功譯碼。GE譯碼卻不受以上狀況的影響，能夠在線性隨機(jī)譯碼的任何狀況下，確保譯碼的準(zhǔn)確性。而在信息分布度中來比較GE 和BP兩種算法，在譯碼信息的長短和性能上，BP算法都優(yōu)于GE算法。

4　結(jié)論

通過本文對(duì)GE和BP兩種計(jì)算噴泉碼的方法可以得知，GE算法能夠普遍應(yīng)用在各種編碼中，不過如若是運(yùn)算的程度較為復(fù)雜，就會(huì)由于信息過多，計(jì)算的會(huì)變得遲緩。而BP算法則是只需要起始節(jié)點(diǎn)保證為1，即使對(duì)再復(fù)雜的噴泉碼譯碼都會(huì)在保證效率的情況下，進(jìn)行準(zhǔn)確的譯碼。因此BP算法運(yùn)用在工程上能夠很大程度上滿足各種需要。

參考文獻(xiàn)：

[1]杜超.深空通信中噴泉碼編譯碼性能研究[D].哈爾濱工業(yè)大學(xué),2013（05）：120-127.

[2]李璐穎,吳湛擊,王文博.噴泉碼編譯碼原理研究和分析[J].中國新通信,2012（07）:41-46.

[3]詹奇聰.噴泉碼與極化碼的改進(jìn)及應(yīng)用[D].華南理工大學(xué),2014 （03）：31-20.