面向數(shù)據(jù)可靠傳輸?shù)母咦g碼率帶反饋的LT碼

劉瀟瀟，郭馨澤，田家政，謝 鯤+

(1.湖南大學(xué) 信息科學(xué)與工程學(xué)院，湖南 長沙 410082；2.國網(wǎng)湖南綜合能源服務(wù)有限公司 大數(shù)據(jù)中心，湖南 長沙 410000；3.長沙電力職業(yè)技術(shù)學(xué)院 經(jīng)濟管理系，湖南 長沙 410000)

0 引 言

近年來，由于網(wǎng)絡(luò)、移動通信等技術(shù)的飛速發(fā)展，網(wǎng)絡(luò)數(shù)據(jù)呈現(xiàn)出井噴式的增長，這無疑對網(wǎng)絡(luò)的服務(wù)能力和服務(wù)質(zhì)量造成了極大挑戰(zhàn)[1,2]。數(shù)據(jù)包在不穩(wěn)定網(wǎng)絡(luò)傳輸時，一些數(shù)據(jù)包可能出現(xiàn)丟失。提高傳輸?shù)目煽啃猿蔀闊o線傳輸?shù)难芯繜狳c。與直接傳輸原始數(shù)據(jù)不同，利用糾刪碼的傳輸機制能夠提高傳輸可靠性[3]。

在糾刪編碼中編碼率定義為R=k/n，其中k為源碼個數(shù)，n為編碼個數(shù)?，F(xiàn)有的糾刪碼按照是否需要預(yù)先估計編碼率，可以分為有碼率和無碼率兩類。在傳統(tǒng)的有碼率編碼方案中[4]，需要通過信道信息確定編碼率。而在動態(tài)變化的無線傳輸信道下，信道傳輸特征容易發(fā)生突變，這就迫使發(fā)送者考慮最壞情況，大大降低了網(wǎng)絡(luò)的傳輸效率。

與傳統(tǒng)有碼率編碼方案不同，噴泉碼最大的特點就是碼率無關(guān)性。噴泉碼主要可分為兩類：LT碼和Raptor碼。與Raptor相比，LT碼編譯碼復(fù)雜度低，且實現(xiàn)起來更加簡單。然而，傳統(tǒng)的LT碼的譯碼方案[5]，需要通過迭代查找度為1的編碼來實現(xiàn)譯碼。當(dāng)找不到度為1的編碼時，譯碼停止，剩下的編碼無法譯碼。

為了提高LT碼的譯碼率，本文提出一種LT碼譯碼方案，該方案通過迭代選取多個編碼來產(chǎn)生度為1的數(shù)據(jù)包，實現(xiàn)譯碼。而且，以新的譯碼方案為基礎(chǔ)，設(shè)計對應(yīng)的反饋機制，使其能夠以小的代價，在不穩(wěn)定的網(wǎng)絡(luò)環(huán)境中更加效率可靠地傳輸數(shù)據(jù)。實驗結(jié)果表明，與現(xiàn)有譯碼方案相比，本文譯碼方案可以提高譯碼率35%。

1 LT碼原理和相關(guān)工作

LT碼屬于無碼率糾刪碼，糾刪碼的實現(xiàn)機制如圖1所示，發(fā)送端要向接收端發(fā)送一組源碼 {s1,s2,s3,s4,s5}。 首先發(fā)送端的編碼器對這組源碼進行異或操作，并獲得數(shù)量略大于源碼數(shù)量的編碼分組 {t1,t2,t3,t4,t5,t6,t7}， 并將這些編碼持續(xù)發(fā)送到接收端。由于網(wǎng)絡(luò)傳輸狀態(tài)不穩(wěn)定等原因，某些編碼在傳輸?shù)倪^程中丟失。而接收端在接收到一定數(shù)量的編碼后，譯碼器會對這些接收到的編碼進行譯碼。雖然傳輸中丟失部分編碼，但是接收到的編碼中含有全部的源碼數(shù)據(jù)，通過譯碼最終仍能獲得全部的源碼。因此，基于糾刪碼的數(shù)據(jù)傳輸能夠提高數(shù)據(jù)傳輸?shù)目煽啃浴?/p>

圖1 糾刪碼原理

LT碼分為編碼和譯碼兩部分，其中LT的編碼過程如下：

(1)根據(jù)預(yù)定的度分布函數(shù)，隨機選擇一個di作為編碼數(shù)據(jù)的度數(shù)；

(2)在k個源碼中，隨機選取di個源碼；

(3)對所選的di個源碼進行異或運算產(chǎn)生編碼數(shù)據(jù)ti。

這里的度di是編碼ti關(guān)聯(lián)的源碼的個數(shù)。如圖2所示，編碼器首先會使用預(yù)定的度函數(shù)策略隨機產(chǎn)生一個度di，然后在源碼中隨機選取di個源碼。在選到di個源碼后，編碼器對這di個源碼進行異或運算，產(chǎn)生編碼ti。

LT碼的譯碼過程如下：

(1)在接收到的編碼分組中找到一個度數(shù)為1的編碼，恢復(fù)與之相連的唯一一個源碼；

(2)將已經(jīng)恢復(fù)的源碼和與其相連的所有其它編碼進行模二和(異或)運算，并將二分圖中對應(yīng)的邊刪除；

(3)重復(fù)步驟(1)、(2)，直至當(dāng)前編碼分組中不存在度數(shù)為1的編碼時，譯碼停止。

圖3 LT碼譯碼過程

如圖3所示，首先在圖3(a)中找到度為1的編碼t2，恢復(fù)與之相連的唯一源碼s2，并刪除與編碼t2關(guān)聯(lián)的邊，結(jié)果如圖3(b)所示。將已經(jīng)恢復(fù)的源碼s2和與其相關(guān)聯(lián)的所有其它編碼t3和t4進行模二和運算，并將其對應(yīng)的邊刪除，結(jié)果如圖3(c)所示。繼續(xù)在圖3(c)中找到度為1的編碼t4，重復(fù)上述操作，直至全部解出3個源碼s1，s2，s3，結(jié)果如圖3(f)所示。

一方面由于LT碼的譯碼是基于度為1的編碼進行譯碼的，因此譯碼代價會因R集合為空集概率的增加而增加(集合R指度為1的編碼集合)。當(dāng)沒有度為1的碼出現(xiàn)時，基于LT碼的譯碼過程失敗，接收端需要繼續(xù)接收經(jīng)過編碼的源碼，進而又加大了發(fā)送消息數(shù)目的代價。

度概率分布影響了LT碼的編譯碼的性能，一方面，di的選取既要保證編碼數(shù)據(jù)攜帶足夠的源信息，選擇較大的di使得更多的源碼參與編碼。另一方面，di過大會加重編碼和譯碼的復(fù)雜性。為了提高LT碼性能，在文獻[6]中，Wang等嘗試優(yōu)化具有少量符號的LT代碼的度分布的配置參數(shù)。在文獻[7]中，Ebrahimzadeh等定義了一種全新的度數(shù)分布函數(shù)，并應(yīng)用高斯消元法[8]進行譯碼。通過這種方式雖然減少了分組開銷，但其譯碼復(fù)雜度卻是二次方的。在文獻[9]中，Zhang和Lei分析了度選擇的影響，并將兩個度分布按一定比例組合在一起，通過優(yōu)化波紋大小進一步調(diào)整度，從而獲得一個新的度分布。在文獻[10]中，作者提出了一種使用全部K個編碼和K-1個編碼異或產(chǎn)生的編碼進行譯碼，但是譯碼率和傳統(tǒng)的LT譯碼率相同。文獻[11]中，作者提出通過兩個度數(shù)相差1的兩個編碼，存在通過異或產(chǎn)生度為1的新的編碼的方法，結(jié)果確實可以在一定程度上提高譯碼的效率。

雖然現(xiàn)有方法在提高編碼和譯碼性能做了不少嘗試。然而，當(dāng)不存在一個包的度為1和兩個編碼異或產(chǎn)生度為1包時，現(xiàn)有方案無法譯碼，譯碼率低下。而且，現(xiàn)有的LT碼通常不反饋，使得每次發(fā)送的碼很大的概率是對譯碼沒有幫助的碼，這也進一步增加了發(fā)送消息數(shù)目的代價。本文針對上述問題，提出高譯碼率帶反饋的LT碼，從而提高譯碼率降低傳輸代價。

2 高譯碼率帶反饋的LT碼

針對LT碼存在的譯碼率不高且發(fā)送消息數(shù)目代價大的問題，本文提出了一種高譯碼率帶反饋的LT碼(H-ACK-LT)。下面介紹H-ACK-LT的編碼、譯碼和反饋3個過程。

2.1 H-ACK-LT編碼

H-ACK-LT采用第1章LT碼編碼框架，實現(xiàn)無碼率編碼。因為度分布會影響譯碼的效率，因此選取合適的度函數(shù)至關(guān)重要。目前有許多關(guān)于度分布的函數(shù)，如基于MBRD度分布函數(shù)[12]，理想孤波度分布和魯棒孤波度分布[13]等。在理想的孤波分布函數(shù)中，為了能夠保證產(chǎn)生的絕大多數(shù)數(shù)據(jù)包的度較低，度概率分布的設(shè)計如下

(1)

然而理想孤波分布在譯碼過程中發(fā)生沒有度為1的編碼的情況。而在一些更壞的情況下，可能一些源碼sk根本沒有參與編碼，因此也無法通過譯碼獲得。目前被廣泛使用的魯棒孤波度分布函數(shù)，它是基于理想孤波分布函數(shù)的改進，魯棒孤波度分布函數(shù)的定義請參見文獻[14]。

魯棒孤波度分布函數(shù)引入了一個補充函數(shù)τ(d)

(2)

改進后的魯棒孤波度分布函數(shù)μ(d) 如下

(3)

其中，Z是一個歸一化參數(shù)，Z=∑dρ(d)+τ(d)。 當(dāng)譯碼成功的概率至少為1-δ時，需要接收編碼的個數(shù)為k′=kZ。

2.2 H-ACK-LT譯碼

傳統(tǒng)的譯碼方法當(dāng)處理完度數(shù)為1的編碼后，譯碼過程將無法繼續(xù)，這使得傳統(tǒng)譯碼的譯碼率通常不高。后來提出的一種基于二次譯碼的算法指出，在譯碼停止后剩下的未譯碼的編碼數(shù)據(jù)中仍然具有可解性。因此，本算法嘗試對剩余編碼數(shù)據(jù)包進行譯碼，進一步提升譯碼率。

設(shè) {s1,s2,…,sk} 為源碼集合， {t1,t2,…,tn} 為編碼集合，對應(yīng)的編碼矩陣A為0,1矩陣

(4)

其中，A∈k×n。

該矩陣的第j個列向量表示第j個編碼是由哪些源碼數(shù)據(jù)編碼完成的。當(dāng)列向量只有一個1時，表明這個編碼是度數(shù)為1的編碼，可以直接求解對應(yīng)的源碼。LT譯碼就是當(dāng)收到一組編碼數(shù)據(jù)(令收到的編碼個數(shù)為k′)，以及其對應(yīng)的編碼矩陣時，求解源碼的過程。

安：當(dāng)然了，我們剛才所討論的一切，并不意味著一個功底不足、技術(shù)疏漏的普通人可以迅速通過這樣的方法來演奏如此之難的作品。而是說，有相當(dāng)技術(shù)的專業(yè)學(xué)生，在面對這樣極具挑戰(zhàn)的作品時，可通過這樣的方法，達到事半功倍的效果。而且，這樣的方法本身也需要極大的智慧！這不僅事關(guān)句法的選擇、旋律的修飾，更是需要我們時刻思考發(fā)力的方法，以及對聲音的考量。

在LT譯碼過程中，找到度為1的編碼數(shù)據(jù)成為譯碼的關(guān)鍵?，F(xiàn)有工作要么通過直接找度為1的編碼或者找兩個編碼異或生成度為1的編碼來進行譯碼，如果通過編碼數(shù)據(jù)之間的異或運算無法產(chǎn)生度為1的編碼時，則譯碼停止。我們發(fā)現(xiàn)，即使現(xiàn)有方法的譯碼過程停止時，仍然有機會獲得度為1的編碼，并進一步繼續(xù)譯碼。如 {abcde,abc,bcd,ce} 表示4個由源碼 {a,b,c,d,e} 編碼后得到的編碼，通過這4個編碼進行異或運算得到新的編碼：abcde?abc?bcd?ce→b。 新的編碼b只包含一個源碼，由于新的編碼b的度數(shù)為1，譯碼過程可以繼續(xù)進行。因此，我們提出新的LT譯碼算法如下：

(1)初始化i=1

(2)While(i≤k′)

1)選取編碼矩陣的i列，將選取i列進行異或運算，如果i=1時，將選取的1列與0向量異或

2)如果能找到i列，使得異或結(jié)果為度為1列向量

則根據(jù)異或的結(jié)果恢復(fù)與此編碼相連的唯一源碼。將已經(jīng)恢復(fù)的源碼和與此源碼相連的所有其它編碼進行模二和運算，消除此源碼在這些編碼中的模二和分量，并更新編碼矩陣，令i=1；

3)如果不能找到異或結(jié)果為度為1的列向量

i=i+1；

圖4 編碼和編碼矩陣

如圖4所示，圖4(a)中給出源碼與編碼關(guān)系的二分圖，其中黑色圓圈表示未恢復(fù)的源碼，白色圓圈表示已恢復(fù)的源碼，方塊表示編碼。圖4(b)給出相應(yīng)的編碼矩陣，矩陣行表示源碼，列表示編碼。矩陣第i行第j列元素為1，表示第j列的編碼是由第i行的源碼生成的。若一列只有一個元素為1，表明該編碼是度為1的編碼。在圖4(a)中發(fā)送端有一組源碼： {a,b,c,d,e,f,g}。 首先編碼器基于度分布策略對源碼進行隨機編碼，得到一組編碼： {abcdefg,abc,bcd,cef,f,abcdef}， 并將它們發(fā)送給接收端。在接收端，對接收到的這組編碼進行譯碼。定義兩個集合S和T，分別表示已恢復(fù)源碼集合和待恢復(fù)編碼集合。譯碼過程如下：

相應(yīng)更新編碼矩陣

(2)此時T中無法找到度為1的編碼，傳統(tǒng)的譯碼過程在這種情況下已經(jīng)結(jié)束。而基于二次譯碼的譯碼方法可以通過兩兩異或產(chǎn)生新的度為1的編碼。通過找到度數(shù)相差1的兩個編碼： {abcdeg,abcde}， 兩者異或產(chǎn)生度為1的編碼g，再對與g相關(guān)聯(lián)的編碼做異或：S={f,g}，T={abc,bcd,ce,abcde}。

更新后的編碼矩陣

(3)經(jīng)過步驟(2)，T中無法找到度為1的編碼，同時也無法找到兩個度數(shù)相差1的編碼。此時，基于二次譯碼的方法由于無法產(chǎn)生度為1 的編碼而終止譯碼。而能夠處理更復(fù)雜組合的H-ACK-LT譯碼方法則可以繼續(xù)譯碼。H-ACK-LT算法首先隨機選擇3個組合，嘗試通過相互異或產(chǎn)生度為1的編碼，然而最終無法通過異或產(chǎn)生度為1的編碼。接下來嘗試選擇4個編碼組合來產(chǎn)生度為1的編碼，如下：abcde?abc=de，de?bcd=bce，bce?ce=b。 得到了度為1的編碼b，對所有與b相關(guān)聯(lián)的編碼做異或：S={f,g,b}，T={ac,cd,ce}。

更新后的編碼矩陣為

(4)重復(fù)上述步驟，直至嘗試所有組合仍無法通過異或產(chǎn)生度為1的編碼，此時H-ACK-LT譯碼算法停止。

H-ACK-LT譯碼算法在進行譯碼時，先在編碼中尋找度為1的編碼，通過異或譯碼和此編碼相連的編碼。當(dāng)沒有度為1的編碼數(shù)據(jù)包時，通過多組編碼間的異或運算產(chǎn)生度為1的編碼，通過異或譯碼和此編碼相連的源碼。重復(fù)上述步驟，直至譯碼成功或者無法再產(chǎn)生度為1的編碼。通過上述譯碼過程，當(dāng)傳統(tǒng)譯碼和基于二次譯碼停止時，H-ACK-LT譯碼方法能夠深度挖掘出度為1的編碼。因此，相較于傳統(tǒng)傳統(tǒng)譯碼和基于二次譯碼方法，H-ACK-LT有更高的譯碼率。

2.3 反饋機制

H-ACK-LT算法的譯碼機制很大程度上提升了譯碼率，但是一些情況下，譯碼過程因為無法繼續(xù)產(chǎn)生度為1的編碼而被迫終止，因而無法成功解出全部源碼。因此，需要繼續(xù)接收編碼來重新啟動譯碼。此時，重傳的編碼若是由那些已經(jīng)譯碼的源碼異或而成，則這些編碼不僅無法幫助進一步的譯碼，反而會增加譯碼的復(fù)雜度和編碼的冗余。隨著譯碼的源碼越來越多，這種情況的概率也會明顯增加。

由于重傳不同的編碼對譯碼程度的影響不同，因此隨機重傳編碼無法保證最大程度譯碼，甚至?xí)黾幼g碼復(fù)雜度和帶來冗余。為了進一步最大程度譯碼剩余的編碼，接收方可根據(jù)當(dāng)前的譯碼情況，主動向發(fā)送方發(fā)送數(shù)據(jù)包請求。如圖5所示，在LT碼二分圖中，未恢復(fù)的源碼的度值越大，說明該源碼參與的編碼就越多。如果度數(shù)值大的源碼已知，通過模二和運算就能消除此源碼在這些編碼中的模二和分量。最大可能地進一步產(chǎn)生度為1的編碼數(shù)據(jù)，從而提高譯碼率。

圖5 LT碼二分圖

因此，本文在所有的未恢復(fù)的源碼中，選擇度最大的源碼作為重傳編碼，主動要求發(fā)送端發(fā)送該源碼，從而提高譯碼率，降低傳輸延遲。當(dāng)接收端收到新的度為1的編碼時，將重新開啟譯碼過程。

如圖6所示，經(jīng)過H-ACK-LT算法的一輪譯碼后，此時不存在度為1的編碼，譯碼停止。此時需要重傳一個僅由一個源碼生成的編碼來重啟譯碼過程。而此時待恢復(fù)源碼還有s1、s2和s3，度數(shù)分別為4，2和4。重傳不同度數(shù)的源碼，對后續(xù)譯碼過程的影響顯然是不同的。如圖6(a)所示，重傳度數(shù)為2的源碼s2生成的編碼t5，最終只能恢復(fù)出源碼s2。而如圖6(b)、圖6(c)所示，如果重傳度為4的源碼s1或s3生成的編碼，經(jīng)譯碼后則可被完全譯碼。因此每次重傳最大度數(shù)源碼生成的編碼，能最大程度提升譯碼率。

圖6 反饋機制示例

帶反饋機制的譯碼過程具體描述如下：

(1)當(dāng)接收端譯碼器無法對剩下編碼中異或產(chǎn)生新的度為1的包，接收端計算每個元數(shù)據(jù)si的度數(shù)，并向發(fā)送端發(fā)出度數(shù)最大的si需求指令；

(2)發(fā)送端收到接收端的需求指令，發(fā)送只包含si的編碼；

(3)接收端譯碼器在接收到si編碼后，重新啟動H-ACK-LT譯碼算法。若全部譯碼成功，則停止譯碼。否則，重復(fù)(1)、(2)步驟，直至解出所有源碼。

3 仿真實驗

為了驗證本文所提的H-ACK-LT性能，除了H-ACK-LT之外，本文還實現(xiàn)了文獻[5]和文獻[11]的譯碼方案來進行實驗的比較，文獻[5]和文獻[11]的譯碼方案分別表示為Sta-LT和K-1-LT。Sta-LT在譯碼過程中，每次查找度為1的編碼，若存在，則譯碼，若不存在，則停止。K-1-LT在譯碼過程中，首先查找度為1的編碼，若存在，則譯碼，若不存在，則繼續(xù)查找是否存在兩兩異或產(chǎn)生度為1的編碼。若存在，則繼續(xù)嘗試使用通過兩個編碼異或運算產(chǎn)生的度為1的編碼進行譯碼，若不能產(chǎn)生度為1的編碼，則譯碼停止。H-ACK-LT算法首先查找度為1的編碼，若存在，則譯碼，不存在則嘗試?yán)脙蓛僧惢虍a(chǎn)生度為1的編碼進行譯碼。若不存在，則繼續(xù)嘗試使用3個、4個、5個……k′等運算產(chǎn)生的度為1的編碼進行譯碼，若不能產(chǎn)生度為1的編碼，則譯碼停止。這里的k′是所收到的全部編碼數(shù)據(jù)包的個數(shù)。

因為現(xiàn)有工作Sta-LT和K-1-LT均不涉及反饋機制，為了進行公平比較，首先我們在沒有反饋的情況下，考察3種算法的譯碼性能。為了進一步驗證所提反饋機制對H-ACK-LT 的影響，我們將Sta-LT和K-1-LT加入本文的反饋機制，進行實驗。下面列出實驗結(jié)果。

3.1 無反饋編碼實驗

本文首先考察無反饋機制下的譯碼性能，采用k=15個源碼進行編碼實驗。接收端接收到略大于源碼個數(shù)的k′=(15+1) 個編碼后，譯碼器分別用Sta-LT、K-1-LT和H-ACK-LT這3種算法進行譯碼。為使結(jié)果更具說服力，這樣的過程重復(fù)實驗100次，分別統(tǒng)計3種算法各自成功譯碼的次數(shù)。如圖7所示，在100次譯碼中，Sta-LT成功譯碼9次，K-1-LT成功譯碼20次，而H-ACK-LT成功譯碼44次。結(jié)果表明，因為H-ACK-LT算法能夠更加充分地挖掘潛在度為1的編碼的能力，大大提高了獲得度為1編碼的概率，所以H-ACK-LT要顯著優(yōu)于前兩種算法，其中H-ACK-LT相對于Sta-LT，譯碼成功率提高了近35%。

圖7 100次編碼實驗中成功譯碼次數(shù)比較

在圖8中進一步給出100次實驗中，每次實驗中15個源碼中被成功譯碼的個數(shù)。為方便比較，圖9列出比較3種算法譯碼成功個數(shù)的均值。

圖8 成功譯碼個數(shù)比較

如圖9所示，Sta-LT平均每次能夠解出5.91個源碼，K-1-LT平均每次能夠解出7.81個源碼，而H-ACK-LT平均每次能夠解出11.68個源碼。比較得出，在無反饋機制下H-ACK-LT每次解出源碼的個數(shù)是最多的，解出源碼個數(shù)大約是Sta-LT算法的兩倍，是K-1-LT算法的1.5倍。上述結(jié)果表明，本文提出的H-ACK-LT譯碼算法可以大大提高譯碼的成功率。

圖9 平均成功譯碼個數(shù)

3.2 帶反饋編碼實驗

本文接下考察反饋機制下的譯碼性能。同樣的，首先使用編碼器對k=15個源碼進行編碼實驗。接收端接收到略大于源碼個數(shù)的k′=(15+1) 個編碼后，譯碼器分別用Sta-LT、K-1-LT和H-ACK-LT這3種算法進行譯碼。若仍有編碼未被解出且算法無法找到度為1的編碼而導(dǎo)致譯碼終止，則調(diào)用反饋機制繼續(xù)進行譯碼，直到譯碼所有的編碼。實驗分別統(tǒng)計3種算法譯碼成功所需的反饋數(shù)據(jù)包的個數(shù)。3種算法每次譯碼成功所需調(diào)用反饋的次數(shù)如圖10 所示。同樣，為了方便比較，我們分別求出調(diào)用反饋次數(shù)的均值。

圖10 反饋重傳數(shù)據(jù)包個數(shù)比較

如圖11所示，Sta-LT成功譯碼平均每次要反饋1.58次，K-1-LT算法成功譯碼平均每次要調(diào)用反饋1.18次，而H-ACK-LT成功譯碼平均每次要調(diào)用反饋0.74次，H-ACK-LT 所需反饋數(shù)據(jù)包最少，因此具有最小的傳輸和通信代價。

圖11 平均反饋重傳數(shù)據(jù)包個數(shù)

4 結(jié)束語

現(xiàn)有LT譯碼方法存在譯碼率不高的問題。本文提出的新的高譯碼率帶反饋的LT碼，利用多個編碼之間相互異或制造新的譯碼條件，可以大大提高譯碼率。在此基礎(chǔ)上，本文提出相應(yīng)的反饋機制，在有反饋的情況下，不僅避免冗余編碼的重傳，而且重傳的編碼以極大的概率是那個能夠幫助最快譯碼的編碼。實驗結(jié)果表明，與現(xiàn)有譯碼方案相比，本文譯碼方案可以提高譯碼率35%。