基于修正正態(tài)分布的噴泉編碼

張茗茗，周 詮

（西安空間無線電技術(shù)研究所 空間微波技術(shù)國家級重點實驗室，陜西 西安 710100）

1998年噴泉碼概念由Michael Luby提出，2002年他又提出了第一個實用的噴泉碼 LT（Luby Transform）碼[1]，在 LT碼的基礎(chǔ)上，2005年Mohammad Amin Shokrollahi提出了以LDPC碼為內(nèi)碼，LT碼為外碼的級聯(lián)噴泉碼—Raptor碼[2]，目前噴泉碼的研究已逐漸展開。

噴泉編碼因其無碼率的特點，在刪除信道和低信噪比下的高斯信道中性能優(yōu)異[3-4]，性能優(yōu)于LDPC碼等傳統(tǒng)糾錯碼，特別適合于互聯(lián)網(wǎng)的傳輸和干擾下的無線通信，在深空通信中也有著巨大的潛力，目前已經(jīng)成為3GPP視頻流傳輸?shù)臉?biāo)準(zhǔn)，并在4G通信協(xié)議LTE中廣泛應(yīng)用[5]，華為、三星等通信巨頭在噴泉編碼領(lǐng)域已經(jīng)申請了大量專利。

由于噴泉編碼出現(xiàn)較晚，關(guān)于噴泉編碼的性能方面有大量的研究，主要分為三類。一類是針對預(yù)編碼部分的高碼率LDPC進行優(yōu)化，由最初的Gallager的校驗矩陣，到后來的Mackay的去四環(huán)的校驗矩陣和PEG算法的校驗矩陣，雖然后來通過非規(guī)則碼性能有了一點提升，但是在高碼率過程中，仍然不可避免的出現(xiàn)四環(huán)現(xiàn)象，影響譯碼效率，在高斯信道中尤為突出[6]。另一類是在初始端再級聯(lián)一個常規(guī)的糾錯碼，例如擴展?jié)h明碼或者RS碼[7]，這樣性能雖然在有些碼率和碼長有一些改進，在有些碼長還會出現(xiàn)誤碼率增大的情況，而且還會增加編譯碼的計算量。最后一種是對LT碼進行度分布的優(yōu)化，LT碼的度分布也在針對各種碼長進行調(diào)整，由ideal到robust再到后來的weaken分布，最近又在碼的結(jié)構(gòu)和度分布有大量研究[8-9]，都是為了使編碼分組的度分布更為均衡，這樣譯碼效率有所提高，在長碼長的情況下，由于大樣本使得度分布性能優(yōu)化不明顯，但是短碼長差異較大，始終與理想性能有所差距[10]。本文將從原始分組角度，進行度分布的修正規(guī)劃，使得每一個原始分組對于編譯碼的貢獻趨于一致，避免有些原始分組欠利用和過利用，最終達到較好的譯碼性能。

1 噴泉編譯碼的度分布

LT碼是噴泉編碼的核心，后來為了改善性能將碼率0.95-0.9的LDPC碼進行級聯(lián)，由于碼率較高，LDPC對于譯碼的提升有限，LT碼起關(guān)鍵作用。當(dāng)終端接收到的編碼數(shù)據(jù)包的數(shù)量略大于K個數(shù)據(jù)包時，譯碼器就能夠以高概率成功地恢復(fù)出發(fā)送源數(shù)據(jù)分組。而度分布決定著LT碼碼組如何選擇，對于編譯碼有著至關(guān)重要的作用。

在LT碼的編碼中，度是指與編碼數(shù)據(jù)分組相連的源數(shù)據(jù)分組的個數(shù)，如圖1所示，s為源數(shù)據(jù)分組，r為編碼數(shù)據(jù)分組。

圖1 度值示意圖Fig.1 Diagram of degree value

如圖1所示，給出了LT碼的編碼過程，編碼度分布Ω=（Ω1，Ω2，Ω3，…，Ωk）表示隨機選到整數(shù) d 的概率為 Ωd，為了便于數(shù)學(xué)處理，一般用度分布函數(shù)的形式表示為：

度概率分布函數(shù)ρ（d）是度即d=i的數(shù)據(jù)分組在總數(shù)據(jù)分組中占的比例。

理想孤子分布的隨機度生成方法，即隨機度按照以下概率分布規(guī)律確定：

孤立子分布為了保證每次譯碼過程中，度為1的集合不為0，為一個固定的值，為了提高譯碼成功率，Luby提出了一種修正的度分布（Robust Soliton Distribution，RSD）。他首先引入了兩個參數(shù)c和δ，其中c為一個常數(shù)，δ為譯碼失敗概率的上界，并定義

其中，c=0.1，delta（δ）=0.5。

為了簡化計算量，Amin Shokrollahi提出 Raptor碼，將LDPC碼和LT碼級聯(lián)，但是LT碼使用弱化的weaken分布，度分布函數(shù)滿足：

Ω（x）=0.008x+0.494x2+0.166x3+0.076x4+0.083x5+0.056x8+0.037x9+0.056x19+0.025x65+0.003x66（5）

關(guān)于3種度分布的關(guān)系如圖2所示，其中原始碼長K為100，編碼長度N為200。ideal分布在度為2時達最大值，然后迅速下降，weaken分布在度為20時有一個上升，其它與ideal分布近似，weaken分布只是在固定的幾個點有值，其它點處為0。

圖2 度分布圖Fig.2 Diagram of degree distribution

度分布在很大程度上決定譯碼所需的分組數(shù)量，譯碼過程中實際度值為1的集合一直不為空，在一個恒定的范圍，能夠保證譯碼一直進行。

傳統(tǒng)的LT編碼只對度進行分配，雖然每個編碼分組是相互獨立的，但是所選擇的是哪些原始分組沒有考慮，這樣導(dǎo)致只注重編碼分組對于原始分組如何利用，而對于實際中由于隨機選擇原始分組給編碼帶來的貢獻差異沒有考慮，也沒有對于原始分組的分布進行研究。本文將在原有編碼基礎(chǔ)上提出修正度分布，從原始分組角度進行度的二次選擇。

2 本文所提的噴泉編碼算法

本文將編碼分組作為原始分組，將原始分組作為編碼分組，逆向進行統(tǒng)計，得到原始度分布的置信區(qū)間，以此作為二次度分配的依據(jù)。

2.1 模型建立

假設(shè)在LT編碼過程中，K個原始分組被編碼成N個編碼分組，根據(jù)度分布 ρ={ρ1，ρ2，…ρs}，其 N 個編碼分組相應(yīng)地

通過度分布被重新劃分為 num={num1，num2，…nums}，滿足

在逆向過程中，本文建立了ping模型和quan模型，分別進行統(tǒng)計。在ping模型中，對于生成矩陣G（K×N），統(tǒng)計原始分組中參與編碼的個數(shù)，[1 0 1 1 1]

例如G=0 0 1 1 0，K=3，N=5， 平均統(tǒng)計模型得到0 1 1 0 1 ping=[4，2，3]，即原始分組1被調(diào)用了4次，分組2被調(diào)用了2次，分組3被調(diào)用了3次。

在quan模型中，對于生成矩陣 G（K×N），統(tǒng)計原始分組占該度分布下的權(quán)重，在矩陣G（K×N）中，加權(quán)統(tǒng)計模型得到quan=[7/3，5/6，11/6]，如表 1 所示。

表1 quan模型計算值Tab.1 Com putation value in model ping

ping模型說明被調(diào)用的次數(shù)，次數(shù)越多，說明參與編碼的次數(shù)多，在譯碼過程中可以得到的信息源越多，避免局部編碼分組出現(xiàn)污染而影響譯碼的判決。quan模型說明原始分組在編碼過程中的影響能力，quan值越大，說明該原始分組起的作用越明顯。例如對于編碼分組1和2，分別只調(diào)用了原始分組1和3，只有原始分組1和3對編碼分組1和2起作用，在得到編碼分組1和2時，可以很順利地將原始分組1和3解出，而對于原始分組2，譯碼起來就顯得有些困難，需要得到編碼分組1和4的信息才能將其解出。

ping模型適合于高斯信道，能夠在低信噪比的情況下正確得到原始信息，但是譯碼起來需要很多次的迭代，在時間復(fù)雜度上開銷很大，而且在刪除信道下，在迭代過程中存在實際度值為1的集合為空的情況。quan模型適合于刪除信道，可以在只獲取超過原始分組數(shù)目一點的情況下正確譯碼，但是在刪除概率增大的情況下，會出現(xiàn)原始分組沒有編碼分組對應(yīng)和起始譯碼度值為1的集合為空的情況，導(dǎo)致譯碼失敗。

本算法將巧妙結(jié)合這兩種模型，使得LT碼既適合高斯信道也適合刪除信道，性能有了明顯提升。

2.2 修正分布的閾值確立

在ping模型中，對于每一個編碼分組，其度值全部都按照度分布 ρ={ρ1，ρ2，…ρs}的概率選擇集合 num={num1，num2，…nums}，模型可以簡化為s維伯努利分布函數(shù)，而每一個原始分組是從編碼分組中均等概率地選擇出來。以weaken分布為例，如表2所示。

在ideal、robust和weaken分布中，維度和概率均不相等，但是都滿足維度較多，樣本較大的情況，這樣多維伯努利分布可以簡化為正態(tài)分布，當(dāng)編碼分組為N時，模型可以認為是N次正態(tài)獨立事件，其期望為：以weaken分布為例，其期望值為Expectation=

表2 集合與度分布關(guān)系表Tab.2 Ralationship between sets and degree distributions

2×5.701 =11.738由于不同的度分布，每個原始分組的ping與期望的偏差pingi-Expectation的絕對值和方差不盡相同，本文采取實驗的方法，取K=1 000，N=2 000，對3種分布仿真1 000次進行統(tǒng)計，得到表3所示。

表3 ping模型期望方差表Tab.3 Expectation and variance in model ping

可以看到，3個模型的期望值差別很大，很難有一個統(tǒng)一的標(biāo)準(zhǔn)，標(biāo)準(zhǔn)差差別不大，在3-4之間，所以本文選擇3作為ping模型的閾值。

在quan模型中，對于每一個編碼分組，首先全部都按照度分布 ρ={ρ1，ρ2，…ρs}的概率選擇 num={num1，num2，…nums}選定一個度值numi，如果隨機選中原始分組，其quan值為1/numi，模型可以看做是度分布 ρ={ρ1，ρ2，…ρs}的取值為 num={1/num1，1/num2，…1/nums}的 N 次 s維伯努利分布，任意原始分組期望度值為unmi/K，相對于該編碼分組的平均度期望Expe_degree=·numi，quan 模 型 中 原 始 分 組 quani=，原始分組中quan模型的期望為：

這樣對于不同度分布，其quan模型的期望值與度分布沒有關(guān)系，只與K值和N值有關(guān)。但是方差仍然依賴于分布函數(shù)，下面是對3種分布的1000次仿真統(tǒng)計，得到表4。

表4 quan模型期望方差表Tab.4 Expectation and variance in model quan

可以看到，在quan模型中，期望值偏差和方差差距都不明顯，所以本文以0.7作為quan模型的閾值較為合適。

兩個模型和閾值建立起來，首先隨機地進行編碼，每生成一個編碼分組，統(tǒng)計被選中的原始分組的ping值和quan值，當(dāng)滿足條件：

該原始分組被拋棄，在以后的編碼過程中不被選擇。這樣一來，絕大多數(shù)的原始分組都落在了Expectation_ping和Expectation_quan附近，整個編碼得到了優(yōu)化。

2.3 m ing置亂算法的提出

而在實際的編碼中，由于存在最后階段沒有足夠的原始分組可供選擇，所以設(shè)定閾值，當(dāng)0.95K都被拋棄時，此時已編碼M個編碼分組，最后N-M個編碼分組采用原來的編碼算法。前M個和后來的N-M個采用的是兩種編碼算法，顯然前者的效果更好，需要對編碼分組和編碼矩陣進行置亂，使得能夠更好地體現(xiàn)在刪除和高斯信道的性能，本文對于1×N維矩陣和N×N維矩陣提出ming置亂算法，其步驟如下：

1）選取Logistic方程作為模型的混沌序列發(fā)生器：xn+1=μxn（1+xn），這樣每一個隨機數(shù)都在 0和 1之間。

2）選取N×N維單位陣I，將第一個隨機數(shù)乘以N得到操作數(shù)x，然后對x做[x]運算，將[x]列與第N列進行交換。

3）將第二個隨機數(shù)乘以 N-1，然后對操作數(shù)做[x]運算，將[x]列與第N-1列進行交換。

4）重復(fù)第2個步驟，直至剩下最后1列為止。

這樣能夠保證每一個編碼分組都能等概隨機地排列在最后傳輸分組的任意位置。

3 新算法的實現(xiàn)

3.1 確定度分布

將原始數(shù)據(jù)等分為K個數(shù)據(jù)分組 （最后一個分組可以補0后成等分），根據(jù)輸入碼長K和輸出碼長N，選擇weaken分布作為原始分布，計算出ping模型的期望和quan模型的期望。

3.2 第一階段編碼

根據(jù)設(shè)計的度分布Ω，隨機地選取編碼數(shù)據(jù)分組的度d，對每一個編碼分組，從K個輸入數(shù)據(jù)包中，等概率地隨機選取d個不同的原始數(shù)據(jù)分組，計算這d個原始分組的ping值和quan值。當(dāng)有原始分組滿足公式（8）時，該分組舍去，從剩下的原始分組中隨機選取不滿足公式（8）的分組，直至d個原始分組都被選取，將這d個原始分組模二加，生成一個編碼數(shù)據(jù)分組。

重復(fù)上述過程，統(tǒng)計已經(jīng)滿足公式（8）的原始分組個數(shù)，當(dāng)其已經(jīng)達到0.95K時，此編碼過程結(jié)束，記下已經(jīng)編碼的編碼分組個數(shù)M。

3.3 第二階段編碼

將剩下的N-M個未編碼分組按照原先的編碼方式編碼，選取度分布值d，根據(jù)d隨機選取原始d個原始分組，將這d個原始分組模二加，生成一個編碼數(shù)據(jù)分組。

當(dāng)N-M個編碼分組編完后，將所有N個編碼分組ming置亂，選擇Logistic方程作為混沌方程，設(shè)定初始值μ，得到隨機數(shù)列，進而得到置亂矩陣，對編碼分組進行置亂，得到最終的傳輸分組。

3.4 譯 碼

當(dāng)收到傳輸分組，首先根據(jù)初始值通過Logistic方程得到隨機數(shù)列，對傳輸分組反置亂。

這里譯碼采用BP算法，所不同的是刪除信道采用硬判決的BP算法，而高斯信道采用的是log-BP的軟判決算法。譯碼算法根據(jù)編碼數(shù)據(jù)分組與輸入數(shù)據(jù)分組的對應(yīng)關(guān)系建立二部圖。在硬判決譯碼的每一步，譯碼器都在編碼集合中尋找度為1的分組，這些分組組成的集合稱為輸出可譯集合，具體譯碼如圖3所示。log-BP的軟判決算法相對復(fù)雜，本文就不再贅述。

圖3 BP硬判決譯碼圖Fig.3 Diagram of BP hard decision decoding

在數(shù)據(jù)傳輸?shù)倪^程中，會由于各種各樣的原因發(fā)生數(shù)據(jù)分組的丟失和干擾，在常規(guī)的糾錯編碼中，當(dāng)一個大的數(shù)據(jù)流發(fā)生超過其糾錯能力的時候，會發(fā)生整個數(shù)據(jù)無法解碼出來，但是噴泉碼還會在一定程度上將一定數(shù)量的分組解碼出來，本算法使得噴泉碼在這兩種信道性能進一步增強。

4 實驗結(jié)果與討論

本文分別進行LT編碼和Raptor編碼，原始分組長度K值取1 000，編碼分組長度N值取2 000，為方便起見，每個分組只是0，1比特，置亂選擇 Logistic方程，初始值 μ為 0.37，每個仿真節(jié)點仿真100次。

在 LT編碼中，LT度分布采用 ideal、robust和 weaken分布，當(dāng)有950個原始分組都已經(jīng)達到要求被拋棄時，本文所采取的編碼算法自動終止，采用原來的編碼算法將剩下的編碼分組全部編完，然后用ming算法將編碼分組和編碼矩陣進行置亂。

在Raptor碼中，LT度分布采用weaken分布，首先進行LDPC預(yù)編碼，將1 000個分組編碼為1 050個分組，碼率為0.95，然后將1 050個中間分組噴泉編碼為2 000編碼分組。

在LDPC預(yù)編碼中，采用PEG的非規(guī)則編碼，校驗矩陣H的列的度分布函數(shù)為：

f（x）=0.283 54x+0.242 37x2+0.474 09x3（9）

當(dāng)有1 000個中間分組滿足條件被拋棄時，本文算法終止，采用原來的編碼算法將剩下的編碼分組全部編完，最后用ming算法將編碼分組和編碼矩陣置亂得到傳輸分組。

圖4 ping模型分布圖Fig.4 Distribution diagram ofmodel ping

圖5 quan模型分布圖Fig.5 Distribution diagram ofmodel quan

如圖4所示，在ping模型中，通過閾值設(shè)定，通過對比，原始分組明顯向期望值11.7靠近，每一個原始分組對于編譯碼的貢獻趨于一致。當(dāng)0.95個原始分組被使用完，表明沒有足夠的原始分組可供利用，在ping值兩端，會出現(xiàn)原有算法得到的ping，由于最后的編碼數(shù)很少，對編譯碼沒有太大的影響。

如圖5所示，在quan模型中，通過閾值設(shè)定，原始分組向期望值2靠近，說明每一個原始分組的貢獻也是一致的，這樣能夠避免在譯碼過程中由于信道的影響帶來糾錯性能的下降。

本文通過BEC信道和AWGN信道進行測試，其中BEC信道采用0.025的比例步長，刪除概率從0.3到0.5進行測試，AWGN信道采用1db的信噪比步長，信噪比從-5db到0db進行測試，文獻[9]的結(jié)果作為BEC信道的對比，而文獻[10]的結(jié)果作為AWGN信道的對比。

圖6 BEC信道誤碼率顯示圖Fig.6 Chart of BER in the BEC channel

圖7 AWGN信道誤碼率顯示圖Fig.7 Chart of BER in the AWGN channel

測試結(jié)果如圖6和圖7所示，在高的刪除概率下，本文采用的算法誤碼率明顯降低，而且在零誤碼率的情況下所需的分組數(shù)也小于常規(guī)的方法。在低信噪比下，本文采用的算法比LT和Raptor常規(guī)的方法在相同的信噪比下誤碼率低，而且達到的誤碼率所需的信噪比也低于原來的方法。

5 結(jié) 論

本文通過對噴泉碼原始分組的構(gòu)成分析，提出ping模型和quan模型，使原始分組對于編碼的貢獻趨于一致，對中短碼長的隨機特性予以約束，避免原始分組被欠利用和過利用，這樣提高了編碼的效率，進而加強了抵抗干擾的能力，使得在干擾較強的情況下仍然有較低的誤碼率。由于閾值已經(jīng)設(shè)定好，所以實現(xiàn)起來較為簡單，保證絕大多數(shù)的原始分組的ping值和quan值都在期望附近，最后又提出ming置亂算法，使得每一個編碼分組所攜帶的信息更為均衡。這樣在降低復(fù)雜度的同時，又進一步提高了噴泉碼的糾錯能力。

[1]Luby M.LT codes[C]//Proceedings of the 43rd Annual IEEE Symposium on Foundations of Computer Science,2002,271-280.

[2]Shokrollahi A.Raptor codes[J].IEEE Transactions on Information，2006，52（6）:2551-2567.

[3]MacKay D J C.Fountain codes[J].IEE Proceedings on Communications，2005，152（6）:1062-1068.

[4]Palanki R，Yedidia Jonathan S.Rateless codes on noisy channels[C]//Proceedings of International Symposium on the Information Theory，2014:27-37.

[5]Singhal C，De S，Gupta H.M.User heterogeneity and priority adaptive multimedia broadcast over wireless[C]//Proceedings of 2014 IEEE International Conference on Communications，2014:1699-1704.

[6]Jing Yue，Zihuai Lin，Vucetic B，et al.Performance Analysis of Distributed Raptor Codes in Wireless Sensor Networks[J].IEEE Transactions on Communications，2013，61（10）:4357-4368.

[7]Sejdinovic D，Piechocki R J，Doufexi A，Ismail M.Fountain code design for datamulticastwith side information[J].IEEE Transactions on Wireless Communications，2009，8 （10）:5155-5165.

[8]Talari A，Rahnavard N.LT-AF codes:LT codes with Alternating Feedback [C]//Proceedings of 2013 IEEE International Symposium on Information Theory，2013:2646-2650.

[9]Zhu Zhiliang，Liu Sha，Zhang Jiawei，Zhao Yuli，Yu Hai.Performance Analysis of LT Codes with Different Degree Distribution [C]//Proceedings of 2012 Fifth International Workshop on Chaos-Fractals Theories and Applications（IWCFTA），2012:142-146.

[10]Haifeng Lu，F(xiàn)eng Lu，JianfeiCai，ChuanHengFoh.LT-W:Improving LT Decoding With WiedemannSolver[J].IEEE Transactionson Information Theory，2013，59（12）:7887-7897.