基于單反饋SLT碼的糾錯碼與MP聯合譯碼

牛芳琳，王洪玉，祝開艷

（1．大連理工大學信息與通信工程學院，遼寧大連116023；2．遼寧工業大學電子與信息工程學院，遼寧錦州121001；3．大連海洋大學信息工程學院，遼寧大連116023）

基于單反饋SLT碼的糾錯碼與MP聯合譯碼

牛芳琳1，2，王洪玉1，祝開艷3

（1．大連理工大學信息與通信工程學院，遼寧大連116023；2．遼寧工業大學電子與信息工程學院，遼寧錦州121001；3．大連海洋大學信息工程學院，遼寧大連116023）

轉移LT（shifted Luby transform，SLT）碼是信源依據接收端的反饋信息進行的LT（Luby transform，LT）編碼方法，這種編碼方法可以有效地減少解碼所需要的數據包個數，由此，本文針對基于單次反饋SLT碼的信道糾錯碼與信息傳遞（message propagation，MP）聯合譯碼方法，對原有的轉移魯棒孤立子分布（shifted robust soliton distribution，SRSD）函數進行改進得到適合MP聯合譯碼的擴展轉移魯棒孤立子分布（expand shifted robust soliton distribution，ESRSD）函數。將本文提出的ESRSD用于MP聯合譯碼方案分別與LT碼、反饋SRSD MP聯合譯碼相比，實驗結果顯示，采用本文提出的ESRSD進行編碼在MP譯碼所需要數據包的個數最少。

SLT編碼；糾錯碼；魯棒孤立子分布；信息傳遞譯碼

0 引 言

在數字信號傳輸過程中，受到噪聲的干擾，數字符號會產生無法恢復的錯誤，為了保證數據可靠傳輸，傳統方法是采用檢錯重發（automatic repeat request，ARQ）和前向糾錯（forward error correction，FEC）技術。ARQ技術，其重發機制對信道容量會產生較大的資源浪費，尤其是當用戶數較多時或信道受到較大干擾的情況下，需要利用反饋信道傳送大量不必要的反饋確認信息（acknowledgement， ACK），ACK占用較多的網絡資源，導致不能進行正常的數據傳輸；而采用FEC技術無需利用反饋信道和重傳應答機制，不會產生重傳等待應答帶來的時延，但其糾錯能力隨著碼長的增加相應增加，譯碼器的復雜性也相應地增加，而且在帶寬和功率方面也需要付出更多的代價。

與ARQ和糾錯碼相比，采用噴泉碼［1-2］編碼方法，不需要ARQ的重傳機制，也不需要通過增加糾錯碼的長度來提高糾錯能力。噴泉碼編碼方法是對k個具有校驗功能的數據包按照一定的度分布函數隨機選取d個數據包進行異或得到編碼包，這些編碼包源源不斷地從信源發送出去，接收端將接收到的編碼包進行校驗，如果編碼包是正確的，則將其參與到信息傳遞（message propagation，MP）譯碼中去；如果編碼包是錯誤的，則將其丟棄，繼續接收新的編碼包進行譯碼，直到接收端譯出信源數據包則結束譯碼過程。度分布函數是噴泉碼實現的關鍵，設計有效的度分布可以降低譯碼開銷，文獻［3］中最早給出一種穩健的魯棒孤立子分布（robust soliton distribution，RSD）實現了LT（Luby transform，LT）編碼。度分布的優化問題一直是LT編碼研究的熱點，如文獻［4- 6］等都對度分布進行改進降低譯碼開銷。文獻［7- 12］等對LT碼傳輸方法進行改進，提出基于反饋信息的轉移LT（shifted Luby transform，SLT）編碼，在已經恢復部分數據包的情況下，將恢復數據包的個數按照一定規則反饋給信源，信源根據反饋信息對傳統的RSD進行轉移，得到基于反饋信息的轉移度分布（shifted robust soliton distribution，SRSD）函數進行LT編碼，接收端將接收到的編碼包與已經恢復的數據包相結合進行MP譯碼。為了進一步降低譯碼開銷，LT碼與信道編碼級聯的編碼方法被提出，如文獻［13］中將LT碼作為外碼與低密度奇偶校驗（low density parity check，LDPC）碼構成級聯碼，而文獻［14］中在LT碼與糾錯碼構成級聯碼的基礎上對傳統的度分布進行優化，有效地提高了譯碼增益。文獻［15］中，對于接收到的多個錯誤數據包，利用數據包之間所滿足的邏輯關系提出刪除法進行譯碼，這種方法需要對接收到的信號先進行硬判決，對得到的數字符號進行校驗以判斷接收到的數據包是否正確。

為了更有效地恢復錯誤數據包，提高通信傳輸效率，本文針對單反饋的SLT碼與信道糾錯碼相聯合的MP譯碼方法，對SLT編碼轉移的SRSD度分布的基礎上進行改進，得到適合糾錯碼與MP聯合譯碼的擴展轉移魯棒孤立子分布（expand shifted robust soliton distribution，ESRSD）。

本文首先介紹了SLT碼與糾錯碼聯合MP譯碼算法；然后對SRSD進行改進得到ESRSD；最后通過實驗仿真驗證采用ESRSD可以有效地降低信源發送編碼包個數。

1 單反饋SLT與糾錯碼聯合MP譯碼

設接信源按時間順序發送k個具有校驗功能的數據包｛s1，s2，…，sk｝，接收端對接收到的k個數據包經過校驗統計出正確數據包的個數n，將n反饋給信源，信源依據n得到一個新的度分布函數，并進行LT編碼，編碼包源源不斷地發送給接收端，對錯誤的數據包進行恢復，直到所有的錯誤數據包全部被恢復。采用傳統的MP譯碼方法，一個編碼包最多只能恢復一個錯誤數據包，而編碼包與糾錯碼聯合的MP譯碼方法，存在同時恢復多個錯誤數據包的情況。

設信源發送S1、S2、S3和S4共4個數據包，經過校驗，S2正確，其余均為錯誤數據包。圖1為基于單反饋SLT編碼的MP解碼過程，黑色圓點表示正確數據包，白色圓點表示錯誤的數據包，l表示一個編碼包最多能夠恢復錯誤數據包的個數，設l≤2。

圖1 l≤2單反饋的SLT編碼的MP譯碼過程

信源依據反饋信息發送SLT編碼包Pi。如圖1（a）所示，首先接收到編碼包P1，依據攜帶的編碼地址可知，P1＝S1＋S2＋S4，在接收端，S2已知，S1、S4為錯誤數據包，則P1＝S1＋S4，依據硬判決網絡信道聯合譯碼［15］解出S1、S4。繼續接收編碼包P2，如圖1（b），P2＝S1＋S3，S1已知，解出S3。

傳統的MP譯碼，只有當編碼包的相鄰節點數為1的時候才能解出未知數據包，采用這種聯合譯碼結構，存在1個編碼包可以同時解出多個錯誤數據包的情況。如圖1中存在3個錯誤數據包，采用聯合譯碼方法僅需要2個編碼包即可恢復，因此這種與信道編碼相結合的MP譯碼方法所需要的編碼包個數減少，提高了糾錯能力。

在信道糾錯碼與MP相結合的譯碼方案中，經過迭代后，如果編碼包與錯誤數據包之間滿足p＝s1＋s2＋…＋slmod（2）邏輯關系，Si表示發生錯誤的數據包，即1個正確編碼包與多個錯誤數據包相鄰，構成網絡信道聯合譯碼的結構，則可以解出所有的Si。

單反饋SLT與糾錯碼聯合MP譯碼方法的流程圖如圖2所示，具體步驟如下。

圖2 單反饋SLT與糾錯碼聯合MP譯碼方法

步驟1 信源對信源符號進行信道編碼，得到k個具有校驗功能的數據包，按順序發送出去。

步驟2 接收端對于接收到的k個數據包分別校驗，統計出正確數據包的個數n。如果n＝k，則得到所有信源信息，發送ACK反饋給信源；如果n＜k，則將n反饋給信源。

步驟3 信源依據反饋信息n，修正度分布函數并對k個數據包進行SLT編碼，發送給接收端進行糾錯。

步驟4 接收端將接收到的編碼包與先前接收到正確的數據包進行糾錯碼與MP聯合譯碼，直到恢復所有錯誤數據包，發送ACK給信源，停止發送編碼包。

2 度分布設計

2.1 擴展的理想度分布

由第1節可知，SLT編碼包與糾錯碼聯合MP譯碼，存在1個編碼包同時恢復小于等于l個錯誤數據包的情況，針對這種聯合譯碼方案，需要設計一種合適的度分布以降低譯碼開銷。

文獻［3］提出了一種理想孤立子分布（ideal soliton distribution，ISD），它是一種理想情況下可以成功進行的LT譯碼的度分布，本文在文獻［3］和文獻［6］的度分布基礎上對ISD度分布進行擴展，得到同時恢復出小于等于l的適合MP聯合譯碼的ISD度分布

對ρ（d，l）進行歸一化即為擴展理想孤立子分布（expand ISD，EISD）

式中，d為編碼的度；k為編碼包個數；l為1個編碼包最多能夠解出數據包的個數；γi為比例系數。

對式（1）進行歸一化計算

符合概率分布。式（2）即為糾錯碼與MP聯合譯碼的EISD度分布。

下面對式（1）進行推導，過程如下。

由文獻［3］可知，對于接收到的度為d的編碼符號，只有當編碼符號相鄰節點為1時才能解出未知的1個符號，即d－1個符號已知；其概率ρ（d）表示度為d的編碼符號在d－1個符號已知的時候解出剩余1個符號的概率，概率等于1／［d（d－1）］，記為ρ（d，1）。LT碼與糾錯碼MP聯合譯碼方案中，則存在1個度為d的編碼包與d－l個數據包相鄰，可以同時解出剩余的l個錯誤數據包。例如度為d的編碼包，如果需要同時解出2個錯誤數據包，即l＝2，只有與d－2個數據包相鄰才能恢復剩余2個錯誤數據包，其解出任意2個錯誤數據包的概率為1／［d（d－2）］，如果l≤2，MP譯碼每次都可以恢復小于或等于2個錯誤數據包，則輸入1個度為ρ（d）編碼包解出2個錯誤數據包的概率為記為ρ（d，2）。由此可以解出小于等于l個錯誤數據包，1個度為ρ（d）編碼包解出l個錯誤數據包的概率為

γi大小影響到同時解出i個數據包所對應修正項在ISD度分布中占有的比例。設可以同時解出i個數據包，對應的度為d的編碼包中需要與d－i個已知的數據包相鄰，才能解出i個錯誤數據包，由前面分析已知其度分布為當1≤d≤k，其概率之和等于1，由此可以求出γi，本文給出一種計算γi的方法，計算過程如下：

（1）當l＝1時，經過MP譯碼可以解出1個錯誤數據包，其分布度函數即為文獻［3］中的ISD度分布

（2）當l＝i時，如果編碼包的度為d，需要已知d－i個數據包，才能解出剩余的i個錯誤數據包，則同時解出i個數據包的概率等于由此得到

將γi帶入式（1）得到EISD度分布函數，推導過程結束。

2.2 ESRSD度分布函數分布

與ISD相同，EISD分布存在度為1的波紋比較小，在迭代過程中容易消失，因此引入τ（d）［3］對EISD（見式（2））進一步修正，綜合上述的EISD

因此，改進后得到的ERSD度分布為

文獻［6］提出反饋的SLT編碼方法對應的SRSD度分布為

式中，k為信源需要發送的數據包個數；n為接收到的正確數據包個數；u（d）為RSD；round表示四舍五入取整。

對式（7）進行歸一化得

結合信道糾錯碼與MP聯合譯碼方案，將式（6）代入式（8），對ERSD度分布進行偏移，得到轉移后的rESRSD（j，l），并進行歸一化，得到ESRSD度分布為

式中，RESRSD（j，l）符合概率分布，即為本文提出的適用MP聯合譯碼的ESRSD度分布函數。

2.3 ESRSD度分布函數性能分析

圖3為k＝80，n／k＝0.5，l≤3的SRSD與ESRSD的度分布圖。

基于單反饋的SLT編碼，在已經接收到大量數據包時，信源編碼不再考慮1的概率分布，圖3中1的概率為0。將SRSD進行擴展得到ESRSD，存在當l≤3可以解碼，對于d較低的度分布波紋要求不高，因此ESRSD度分布中，當d較小時其波紋也較小，增加了其他度的概率分布。

圖3 度分布圖

3 仿真及分析

假設一個理想狀態，接收端采用糾錯碼與MP聯合譯碼，每個編碼包均可以恢復小于等于l個未知數據包，丟包率（packet error rate，PER）即為信道刪除概率，LT編碼中，c＝0.03，δ＝0．5。采用Matlab對實驗進行仿真，仿真次數為1 000。

信源需要發送的數據包個數k＝200，采用信道糾錯碼與MP聯合解碼，度分布分別選取SRSD（l＝1、l≤2和l≤3）、ESRSD（l＝1、l≤2和l≤3），與LT碼相比，在不同PER條件下信源需要發送數據包的個數如圖4所示。圖中l＝1，表示采用傳統的MP譯碼。

從圖4中可以看出，采用LT碼譯碼所需要的數據包個數最多；采用信道糾錯碼與MP聯合譯碼，當l＝1時，SRSD度分布譯碼所需要的編碼包個數最多，當l≠1時，l相同，采用ESRSD度分布所需要的編碼包個數小于SRSD度分布編碼，并且隨著l的增加，所需要編碼包個數下降。當信道丟包概率PER＝0時，采用本文方案不需要任何冗余信息，即僅需要發送200個信源數據包即可傳輸所有的信源信息，而LT編碼方法譯碼需要存在冗余的編碼包才能譯碼，譯碼所需要的數據包個數大于信源數據包個數。

圖4 比較不同方案在刪除信道解碼時所需要數據包個數

圖4 是一種理想情況下的比較，受到MP聯合解碼能力的限制，不是所有小于等于l個錯誤數據包都能被恢復，需要考慮到采用刪除法聯合譯碼方法恢復l個錯誤數據包的概率分布情況。在無線通信環境中，高斯白噪聲信道，采用二進制相移鍵控調制，信源發送數據包個數k＝500，信道編碼為（31，21）線性分組碼，采用糾正1個錯誤符號同時校驗出2個錯誤符號檢糾錯方法，度分布分別選取ESRSD（l≤3）、SRSD（l＝1）與SRSD（l≤3），比較在不同信噪比（signal noise ratio，SNR）信源發送數據包個數。實驗結果如圖5所示，當SNR較低時，采用ESRSD（l≤3）明顯優于SRSD（l＝1）和SRSD（l≤3），隨著SNR的增加，信源發送數據包個數逐漸減少，當SNR≥2 dB，編碼包中發生錯誤的符號個數降低，通過（31，21）信道糾錯碼即可恢復，幾乎不需要再接收SLT編碼包來恢復錯誤數據包，因此3種情況譯碼所需數據包個數幾乎相同。

圖5 采用（31，21）線性分組碼與單反饋無碼率編碼聯合譯碼信源需要的發送數據包個數

4 結 論

本文對于單反饋的SLT碼與糾錯碼MP聯合譯碼方法給出一種新的ESRSD度分布函數，在信道環境較差的時候，由于ESRSD度分布考慮到譯碼可以同時解出小于等于l個數據包概率分布情況，其編碼效果優于SRSD。由此得出采用ESRSD度分布進行單反饋的SLT編碼，在噪聲信道中可以有效地減少信源發送編碼包的個數，提高了編碼增益。

［1］Byers J W．A digital fountain approach to asynchronous reliable multicast［J］．Selected Areas in Communications，2002，20（8）：1528- 1540．

［2］Mac Kay D J C．Fountain codes［J］．Communications，2005，152（6）：1062- 1068．

［3］Michael L．LT codes［C］∥Proc.of the Foundations of Computer Science，2002：271- 282．

［4］Nguyen T D，Yang L L，Ng S X，et al．An optimal degree distribution design and a conditional random integer generator for the systematic Luby transform coded wireless internet［C］∥Proc.of the Wireless Communications and Networking Conference，2008：243- 248．

［5］Lei W J，Liu H F，Xie X Z．Switch degree distribution：an improved degree distribution for LT digital fountain code［J］．Journal of Chongqing University of Posts and Telecommunications，2012，24（1）：34- 38．（雷維嘉，劉慧峰，謝顯中．開關度分布：一種改進的LT數字噴泉編碼度分布［J］．重慶郵電大學學報，2012，24（1）：34- 38．）

［6］Chen Y Y，Liu W．Compressed fountain codes based on new random degree distribution［J］．Journal of Electronics&Information Technology，2012，34（5）：1185- 1190．（陳月云，劉偉．基于新型隨機度分布的壓縮噴泉碼［J］．電子與信息學報，2012，34（5）：1185- 1190．）

［7］Agarwal S，Labs D T A G B，Hagedorn A，et al．Adaptive rateless coding under partial information［C］∥Proc.of the Information Theory and Applications Workshop，2008：5- 11．

［8］Hagedorn A，Agarwal S，Starobinski D，et al．Rateless coding with feedback［C］∥Proc.of the IEEE INFOCOM，2009：1791- 1799．

［9］Sorensen J H，Koike A T，Orlik P．Rateless feedback codes［C］∥Proc.of the IEEE International Symposium on Information Theory Proceedings，2012：1767- 1771．

［10］S?rensen J H，Popovski P，Ostergaard J．Feedback in LT codes for prioritized and non-prioritized data［C］∥Proc.of the Vehicular Technology Conference，2012：1- 5．

［11］Yue G S，Uppal M，Wang X D．Doped LT decoding with application to wireless broadcast service［C］∥Proc.of the IEEE International Conference on Communications，2011：1- 5．

［12］Zhang L，Liao J X，Wang J Y，et al．Diversified SLT codes based on feedback for communication over wireless networks［C］∥Proc. of the Global Information Infrastructure Symposium，2013：1- 6．

［13］Zhu H J．Research on encoding and decoding of fountain codes and their applications［D］．Beijng：Tsinghua University，2009．（朱宏杰．噴泉碼編譯碼技術與應用研究［D］．北京：清華大學，2009．）

［14］Liu X J，Sun X J．Design of short length system Luby transform code of high rate in concatenated scheme［J］．Systems Engineering and Electronics，2013，35（3）：634- 637．（劉曉健，孫曉鈞．級聯碼中的高碼率短碼長SLT碼設計［J］．系統工程與電子技術，2013，35（3）：634- 637．）

［15］Niu F L，Zhang X，Wang D X．A scheme of joint networkchannel erasure correction decoding with binary for wireless communication［J］．Journal of Wuhan University（Natural Science Edition），2013，59（6）：567- 572．（牛芳琳，張興，王冬霞．無線通信中二進制網絡-信道聯合刪除譯碼法［J］．武漢大學學報（理學版），2013，59（6）：567- 572．）

MP decoder with error correction codes based on single feedback SLT codes

NIU Fang-lin1，2，WANG Hong-yu1，ZHU Kai-yan3
（1.School of Information and Communication Engineering，Dalian University of Technology，Dalian 116023，China；2.School of Electron&Information Engineering，Liaoning University of Technology，Jinzhou 121001，China；3.Institute of Information Engineering，Dalian Ocean University，Dalian 116023，China）

Shifted Luby transform（SLT）codes are the kind of digital fountain codes whose data packets are encoded with the LT codes by the feedback information in order to decrease the number of the encoded packets at the receiver end．This paper proposes an expand shifted robust soliton distribution（ESRSD）function through modified shifted robust soliton distribution（SRSD）for the scheme of message propagation（MP）decoder with error correction codes based on the single feedback information in order to get the encoded packets recovered those error packets at the end．To compare ESRSD with SRSD，experimental results show that the number of packets by using ESRSD is the least，compared with the other methods in LT codes or using the SLT codes with the SRSD．

shifted Luby transform（SLT）codes；error correction code；robust soliton distribution（RSD）；message propagation（MP）decoder

TN 911．21

A

10．3969／j．issn．1001-506X．2015．01．28

牛芳琳（1971-），女，講師，博士研究生，主要研究方向為信息論、數字噴泉碼編碼技術。

E-mail：niufanglin＠sina．com

王洪玉（1968-），男，教授，博士研究生導師，博士，主要研究方向為無線協作通信技術、自組織網絡及無線傳感器網絡技術。

E-mail：whyu＠dlut．edu．cn

祝開艷（1980-），女，講師，博士研究生，主要研究方向為協作通信、網絡編碼技術、數字噴泉碼編碼技術。

E-mail：zhukaiyan＠dlou．edu．cn

1001-506X（2015）01-0175-05

網址：www．sys-ele．com

2014- 02- 26；

2014- 05- 29；網絡優先出版日期：2014- 07- 08。

網絡優先出版地址：http：／／w ww．cnki．net／kcms／detail／11．2422．TN．20140708．1717．003．html

國家自然科學基金（61172058）；錦州市科學技術計劃項目（13B1D13）資助課題