噴泉碼中不定幀長LT碼及其生成矩陣的優(yōu)化

趙旦峰，錢晉希，吳宇平

(哈爾濱工程大學信息與通信工程學院，黑龍江哈爾濱150001)

數(shù)字噴泉碼是Luby M.等人于1998年提出的一種編碼思想，主要是為了解決通信當中的數(shù)據(jù)反饋重傳，使得接收端通過雜亂無章的編碼分組數(shù)據(jù)包就可以高概率譯碼.LT(Luby transform)碼是2002年由Luby M.提出的第一種可行的噴泉碼方案［1］，它是無碼率的前向糾錯編碼.但是近年研究發(fā)現(xiàn)LT碼在編碼時需要從給定的度數(shù)分布中，隨機的選取原始數(shù)據(jù)進行編碼，使得編碼結果不唯一;在譯碼時存在事先給定的譯碼失敗概率門限δ，而且需要接收足夠多的編碼分組，數(shù)據(jù)量較大，使得其有效性和可靠性較差.

為了能更好地利用LT碼，本文運用極限條件對LT碼度數(shù)進行分析，得出了LT碼在極限條件下的結論，并根據(jù)該結論，提出了編碼效率較高的不定幀長LT(variable frame length LT，VFLLT)碼，然后將熵編碼技術適當?shù)匾氲絍FLLT碼的生成矩陣中，按packet分別對其熵壓縮編碼，得出了數(shù)據(jù)量較少的VFLLT碼系統(tǒng)，較大提高了噴泉碼的性能.

1 極限條件下的LT碼模型

對于LT碼的度數(shù)分布，通常采用M.Luby提出的魯棒孤子分布(robust soliton distribution，RSD)［2］，本節(jié)詳細討論了RSD在極限分布下的情況.

1.1 魯棒孤子分布

RSD來源于理想孤子分布(ideal soliton distribution，ISD).其表達式為

式中:

式中:

S為得到的編碼分組中度數(shù)為1的編碼分組個數(shù)的期望值.Luby M.等［2－3］給出當譯碼端或接收端收到

個編碼分組時，能以高概率恢復原始數(shù)據(jù).

1.2 極限情況下S和K'討論

已知S和K'關系如式(5)、(6).理想情況下，希望以盡可能少的冗余得到盡可能大的譯碼成功概率，且編譯碼算法是K的線性函數(shù)［2，4］.由此，可以得到

因為S＞0，δ＞0，所以式(7)只能是第2項趨于0.可得

至此，可以得出魯棒孤子分布中c和δ的極限值分別為

由式(9)，本文可以得出如下極限結論:

1)在極限情況下，若想δ＜1，則需K＜e，說明在K較小時，LT碼的性能較好，并且隨著K的愈發(fā)減小，δ也在減小.于是證明了，原始數(shù)據(jù)越少時，LT碼譯碼準確度越高.

2)在δ非常小即δ?11時，極限情況下，S也可以取非常小的數(shù)值就能夠以非常高的概率1－δ譯碼，此時，對度數(shù)1及冗余的要求大大減小，可以大幅提高譯碼準確度以及減小譯碼時間.

3)隨著K的增加，尤其是在數(shù)值超過e后，編碼分組中度數(shù)1的個數(shù)S和譯碼需要獲得的編碼個數(shù)K'都非線性的迅速增長，使譯碼效率和譯碼準確度都非線性迅速減小.

2 VFLLT碼設計

2.1 設計原則

本文根據(jù)LT碼在極限情況下的特點，采取如下設計原則:針對不同的性能要求，如誤碼率、速率等，將原始數(shù)據(jù)非均勻分成若干組，每組數(shù)量不定.本文將每組的信息數(shù)稱為幀長，則整個原始數(shù)據(jù)被傳送時，幀長不確定并且不相等.由此，可以將原始數(shù)據(jù)分為“輕重緩急”，如圖1所示某原始數(shù)據(jù)，對“輕”要求不高，誤碼率和碼速率都有較寬范圍，則將其正常LT編碼傳送;而中間的“重”對誤碼率有較高要求，則對這部分分幀長傳送，能提高譯碼準確度和抗噪聲性能;第3段數(shù)據(jù)的碼速率要求范圍較寬，誤碼率沒有要求，設計時可在較寬的碼速率范圍內盡量降低誤碼率;而最后一組信息對碼速率要求較高，需對該組數(shù)據(jù)進行分幀長傳輸，但不必像對要求誤碼率時那么嚴格.在以上的分析中，可以看出采取不同的設計方案，得到的效果不同，均能夠滿足系統(tǒng)某一方面性能的要求.

圖1 原始數(shù)據(jù)不定幀長編碼設計Fig.1 Variable frame length code design of original data

2.2 系統(tǒng)實現(xiàn)方案

在傳統(tǒng) LT碼中，得到的編譯碼復雜度為Kln(K/δ)，平均度數(shù)為lnK.其中K是原始數(shù)據(jù)長度.而在VFLLT碼中，如圖1.圖1假設原始數(shù)據(jù)K分成8組，其中“輕”為k1，“重”為{k2，k3}，“緩”為{k4，k5，k6}，“急”為{k7，k8}，且k1=mk2，滿足

由假設條件，則VFLLT碼的復雜度Qv為

已提出的LT編碼復雜度為Q:

由于mk＜(m+7)7，m＜(m+7)，從而有mk× ln(m/δ)＜(m+7)kln((m+7)/δ)，于是可知Qv＜Q.

上式雖然是在假設情況下得出的結論，但可以推廣到普遍情況.綜上，可以得出VFLLT碼的編譯碼復雜度小于已提出的LT碼編譯碼復雜度.

VFLLT碼平均度數(shù)值Dv計算如下:

而已提出的LT碼的平均度數(shù)D計算為

而m＞0，k＞0，可得m1/8＜(m+7)，即Dv＜D.同理，此式可推廣到普遍情況，可以得出不定幀長LT碼的平均度數(shù)小于已提出的LT碼平均度數(shù).VFLLT碼和已提出的LT碼的編譯碼復雜度和平均度數(shù)的比較如圖2所示.VFLLT碼的復雜度和平均度數(shù)都小于已提出的LT碼平均度數(shù)，有利于提高譯碼成功概率.

圖2 已提出的LT碼和VFLLT碼復雜度和平均度數(shù)比較Fig.2 Comparison of the complexity and average degree of existing LT code and VFLLT code

3 生成矩陣G的熵編碼優(yōu)化

3.1 矩陣G的生成

設s(s1，s2，s3，…，sN)為原始信息序列，t(t1，t2，t3，…，tM)為編碼后序列，LT編碼過程可以由下式表示為

式中:G為隨機生成的N×M的(0，1)矩陣，LT編碼時，G的生成步驟如下:

步驟1:從合適的度數(shù)分布當中，隨機地選擇一個值d，d為該次編碼分組的度數(shù);

步驟2:從原始數(shù)據(jù)分組(比特)當中隨機的選擇d個數(shù)據(jù)，將該d個數(shù)據(jù)進行模2和;

步驟3:從第一列開始，在G的對應列中將步驟2中被選擇的原始數(shù)據(jù)的對應位置置1;

步驟4:重復上述步驟，直至完成.

3.2 熵編碼及方案

當某稀疏矩陣中連續(xù)的0或者連續(xù)的1較多時，可以采用熵編碼對矩陣中個數(shù)較少的元素進行操作，編碼過程中要求保存信息熵，這種編碼叫熵編碼，是根據(jù)消息出現(xiàn)概率的分布特性而進行的［5－6］.熵編碼是一種無損數(shù)據(jù)壓縮編碼，一般用于信源編碼，本文將其引用到噴泉碼這種信道編碼方案中.因為G中的每列相當于噴泉碼傳送過程中的一個數(shù)據(jù)包，為了不破壞噴泉碼的特性，本文對矩陣G進行按列熵編碼，減少數(shù)據(jù)的占用空間，提高譯碼準確度.

本文經過分析，矩陣G有如下特點:1)元素只可能為0或1;2)稀疏矩陣，即G中大部分元素是0.

根據(jù)如上2個特點，能夠確定一套熵編碼方法，步驟如下:

步驟1:由編碼原理，生成矩陣G;

步驟2:提取出G中每列中所有元素1的位置，即行位置和列位置;

步驟3:將行位置和列位置用二進制數(shù)表示;

步驟4:將以上列位置相同的一系列行位置保存成一個數(shù)據(jù)包;

步驟5:重復以上步驟，直至完成.

因為G在編碼過程中生成時不是固定的，所以二進制數(shù)表示的行位置和列位置是隨著G變化的.

假設用數(shù)組a和b保存行位置二進制表示和列位置二進制表示，且G為N×M矩陣，N表示原始信息比特位數(shù)，M表示得到的編碼數(shù)據(jù)位數(shù).因為1出現(xiàn)的位置可能在G中的任何一行和任何一列，所以a需要包括N種可能性且b包括M種可能性，必須滿足以下2個式子:

式中:x和y分別表示一個數(shù)據(jù)有多少位二進制數(shù)來表示，即比特位數(shù).則熵編碼壓縮比可定義為熵碼后數(shù)據(jù)量與熵編碼前數(shù)據(jù)量的比值:

當采用壓縮技術后，使得G矩陣需保存的數(shù)據(jù)量大幅減少，且數(shù)組a、b當中的位置值由更多二進制數(shù)表示，同時可以降低其誤碼率.如現(xiàn)設原始數(shù)據(jù)有362位，需要編碼為2 048位，且x=9，y=11，將原來直接錯一位的概率等同于現(xiàn)在9位錯一位或者11位錯一位，很大程度的提高了譯碼準確度.

在分析了系統(tǒng)的編譯碼復雜度與平均度數(shù)，以及應用了上述熵編碼后，可以確定圖3為生成矩陣優(yōu)化了的VFLLT碼系統(tǒng)方案框圖.系統(tǒng)的方案是通過幀長確定器、LT子編譯碼器、熵編譯碼器、數(shù)據(jù)包區(qū)分器、分時分幀器以及合并器構成.在發(fā)送端，將原始數(shù)據(jù)直接輸入幀長確定器，幀長確定器根據(jù)不同性能要求，通過LT子編碼器對每段子數(shù)據(jù)進行編碼，然后進行熵編碼，最后由合并器分時的將編碼數(shù)據(jù)疊加;在接收端，先進行相應的分時分幀長和熵譯碼，數(shù)據(jù)包區(qū)分器通過查看生成矩陣確定幀長，然后交由相應的LT子譯碼器譯碼，最后由合并器完成完整譯碼結果.

圖3 不定幀長LT碼編譯碼系統(tǒng)方案Fig.3 System scheme of VFLLT code

4 系統(tǒng)仿真與結果分析

本文的系統(tǒng)仿真平臺是WindowsXP系統(tǒng)，CPU為1.80GHz，內存為1G，采用C++語言.在幀長K為不同值情況下，其熵編碼效果如表1所示.從表中可以看出:在熵編碼之前，為了高概率譯碼，所需編碼分組數(shù)據(jù)量非常大，而通過熵編碼后，能在保證數(shù)據(jù)包個數(shù)不變時，將編碼分組的數(shù)據(jù)量大大減少，而且原始信息位越多時，效果越好，壓縮比平均小于10－3左右.

圖4是VFLLT碼系統(tǒng)和已提出的LT碼的編譯碼時間、譯碼準確度的比較，仿真時的參數(shù)均為c= 0.2，δ=0.5，將原始信息分成8組，每組幀長逐漸增加.限于篇幅，部分原始數(shù)據(jù)測試幀長如表2所示，其中，1)FL(frame length)為幀長，單位是bit，第1到第8組不同的幀長表示為:FL1～FL8;2)SDL (source data length)為原始數(shù)據(jù)長度，單位是bit，原始數(shù)據(jù)長度從512～3 328 bits.

表1 熵編碼情況(初始條件:c=0.2，δ=0.01)Table 1 Record of the entropy coding initial condition (c=0.2，δ=0.01)

表2 測試時的幀長數(shù)據(jù)Table 2 Frame length while testing

圖4 已提出LT碼與VFLLT碼編譯碼的時間和譯碼概率比較Fig.4 Comparison of the encoding＆decoding time and decoding probability of existing LT code and VFLLT code

從圖4中可以看出:隨著原始數(shù)據(jù)長度的增長，已提出的 LT碼的編譯碼時間增加非常大，而VFLLT碼系統(tǒng)的編譯碼時間增加相對較緩，能夠較大改善編碼系統(tǒng)的效率，增加編譯碼速率;而且，隨著原始數(shù)據(jù)長度的增加，VFLLT系統(tǒng)和已提出的LT碼系統(tǒng)的譯碼概率均有下降，但是已提出的LT碼下降非常迅速，甚至在碼長較短時，出現(xiàn)不能譯碼的情況，而VFLLT碼系統(tǒng)下降較緩，而且當原始數(shù)據(jù)長度達到1 000后，其譯碼概率下降非常平緩，基本保持不變.綜合以上，在實際應用時，可綜合考慮通信的有效性和可靠性以及編譯碼復雜度，折中選取最佳幀長組合方案.

5 結束語

數(shù)字噴泉碼在應用時不需要反饋信道，但是譯碼時需要接收非常多的編碼分組，使得其延時較大，且需要大量內存空間.而且LT碼的生成矩陣數(shù)據(jù)量非常大，造成噴泉碼難于在實際系統(tǒng)中應用.本文研究表明，對不同長度的原始數(shù)據(jù)進行噴泉編碼時，其性能有著較大差異，使得可以通過對其進行不定幀長的設計來提高性能，并且利用噴泉碼編碼分組之間的無關性，可以采取按數(shù)據(jù)包進行熵編碼的方法減少數(shù)據(jù)量.仿真結果表明:所提出的VFLLT碼，當原始數(shù)據(jù)固定時，可以在不增加額外運算量的情況下，一方面縮短編譯碼時間，提高譯碼速率;另一方面提高譯碼準確度;而且將生成矩陣進行熵編碼優(yōu)化后，其數(shù)據(jù)量和譯碼錯誤概率都大大減少，提高了LT碼在實際應用時的可行性.

［1］MACKAY D J C.Fountain codes［J］.IEEE Proc Commun，2005，152(6):1062－1068.

［2］Luby M.LT codes［C］//Proceedings of the 43r Annual IEEE Symposium on Foundations of Computer Science.Berkeley，USA，2002:1－10.

［3］SEJDINOVI＇D，PIECHOCKI R J，DOUFEXI A.And－or tree analysis of distributed LT codes［C］//ITW 2009.Volos，Greece，2009:10－12.

［4］FENG Lu，CHUAN Hengfoh，CAI Jianfei，et al.LT codes decoding:design and analysis［C］//International Conference on Information Society and Information Technology.Novo Mesto，Slovenia，2009:2492－2496.

［5］薩洛蒙.數(shù)據(jù)壓縮原理與應用［M］.吳樂南，譯.北京:電子工業(yè)出版社，2003:531－534.

SALOMON David.Principles and applications of data compression［M］.Beijing:Electronic Industry Press，2003:531－534.

［6］袁玫，袁文.數(shù)據(jù)壓縮技術及其應用［M］.北京:電子工業(yè)出版社，1995:9－14.

YUAN Mei，YUAN Wen.Data compression technology and its application［M］.Beijing:Electronic Industry Press，1995:9－14.

［7］SUBRAMANIAN V G，LEITH D J.On a class of optimal rateless codes［C］//Forty－Sixth Annual Allerton Conference Allerton House.Urbana，USA，2008:23－26.

［8］HAGEDORN A，AGARWAL S，STAROBINSKI D，et al.Rateless coding with feedback［C］//IEEE INFOCOM Proceedings.Rio de Janeiro，Brazil，2009:1797－1799.

［9］TIRRONEN T，VIRTAMO J.Finding fountain codes for realtime data by fixed point method［C］//International Symposium on Information Theory and its Applications.Auckland，New Zealand，2008:1－6.

［10］ERYILMAZ A，OZDAGLAR A，MéDARD M，et al.On the delay and throughput gains of coding in unreliable networks［J］.IEEE Transactiongs on Information Theory，2008，54(12):5511－5524.