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

廖林冰（國防科技大學，長沙　410000）

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

廖林冰
（國防科技大學，長沙410000）

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

關鍵詞:噴泉碼;高斯消元算法；算法

1　前言

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

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

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

2.1LT譯碼原理

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

2.2輸入信息度分布

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

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

3.1高斯消元譯碼算法

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

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

通過對高斯消元譯碼整個流程得知，k這一信息塊長度的增加會導致運算量的迅速增長，所以計算的難度也有所增加，因此只適合用于短噴泉碼的譯碼工作。

3.2置信傳播編譯算法

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

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

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

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

3.3結果分析

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

4　結論

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

參考文獻：

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

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

[3]詹奇聰.噴泉碼與極化碼的改進及應用[D].華南理工大學,2014 （03）：31-20.