噴泉碼是一類基于圖的線性糾刪碼,而LT碼是一種被提到3GPP標準中的實際可用的噴泉碼,顧名思義,噴泉碼中,編碼包就如同噴泉的水滴,而接收方只要能接收到足夠多的水滴就能夠形成一桶水(譯碼得到原始數據)。反映在實際流程上,就是發送端對原始信息進行編碼,得到源源不斷的編碼信息并且發送,只要接收端能正確接收到足夠的編碼信息就可以譯出原始數據。在二進制刪除信道上(數據包要么正確接收,要么丟包),這個過程相比于反饋重傳的機制來說更為有效,尤其適是RTT較大的環境。
而LT碼的編譯碼過程并不復雜,尤其是編碼過程,十分簡單,依據相應的公式生成度分布,按照流程生成相應的編碼包即可,具體流程如下
LT碼的編碼算法
LT碼作為第一種實用的噴泉碼,其編碼過程較為簡單,下面就某一編碼包的產生過程介紹如下:
①? ?由已定的度分布p(d)(度現有的良好度分布為魯棒孤波分布,具體流程在后續表附錄);
②? ?隨機選取一個度值d;
③? ?將這d 個不同的數據包求異或和,生成該編碼包。
具體過程如下圖所示
不斷重復上面的步驟,就可以得到無限多個編碼分組。在這些步驟中一些細節需要注意:LT 碼編碼之前要先確定度分布函數,度值的確定由度分布函數來計算。不同的度分布,k的概率值是不同的,但度分布概率函數只是確定了取度值為d的概率是多少,而并不能確定這d個原始編碼分組是哪些,所以對于這d個原始編碼分組的選擇來說是任意的,本文對這d個原始編碼分組的選擇采用均勻分布來進行選取,即從區間[1,k]中按均勻分布隨機生成d個整數。區間[1,k]中所有整數被選取的概率是相等的。把這d個整數進行異或,就得到了一個編碼分組。
LT碼的譯碼算法
LT碼的譯碼算法有兩種,BP(后向傳播)譯碼算法和GE(高斯消元)譯碼算法,本文先從廣場噴泉圖的形式講述譯碼過程,再通過矩陣的形式講述譯碼過程,方便大家理解。我們之前提到的,噴泉碼時一類基于圖的線性糾刪碼,什么意思呢?我們來看一個BP譯碼過程的Tanner圖
對于一個編碼包來說,與他相連的所有原始消息進行異或得到了編碼消息,我們可以通過一個度數為1的編碼包(也就是只有一個原始消息參與的編碼包,即編碼包等于原始消息)來使與之關聯的編碼包的度數減1,什么意思呢?我們稱“+”為異或運算,我們知道a+a = 0。對于一個編碼數據包來說,編碼數據為a+b+c,即此編碼包度數為3,而我們此時收到了一個度數為1,消息為a的編碼包,我們可以通過a+b+c+a = b+c。此時編碼包度數為2了,如果我們此時又收到一個度數為1,消息為b的數據包,則可以通過b+c+b = c,使編碼包度數變為1,而此時這個編碼包的度數為1,消息為c,它可以參與到另一個編碼包如c+d的譯碼過程中去,通過這樣的不斷迭程控噴泉代,我們最終就可以把a,b,c,d.....所有原始數據包解出,這也就是所謂的BP譯碼算法。
那么怎么從矩陣的角度來理解譯碼過程呢?設原始數據分片后的消息矩陣為S,編碼過程相當于乘以一個生成矩陣G,設編碼后矩陣為M,則整個編碼過程可以表示為M= SG,式子可以通過向量表示為:
生成矩陣G為一個根據度分布隨機生成的K*N的矩陣,其中K為LT碼碼長,N為生成的編碼包數量,其值理論上可以為無窮大,G矩陣中的每一列中1的個數就表明生成的編碼包的度數,其中1的位置表明參與編碼的源數據包的序號,因此,當G的秩等于K(行滿秩)時,整個方程組是可解的,此時源消息可譯碼,當G的秩不足K時,接收端持續接收數據包,反應在矩陣上為G的列數持續增加,直到G的秩滿足要求。解方程組的過程我們一般通過高斯消元進行,這也就是所謂的高斯消元譯碼。以矩陣的形式來看,BP譯碼也就是每次找尋一個1的個數僅為1的Mi來進行譯碼)
評論（0）