張茗茗,周 詮
(西安空間無(wú)線(xiàn)電技術(shù)研究所 空間微波技術(shù)國(guó)家級(jí)重點(diǎn)實(shí)驗(yàn)室,陜西 西安 710100)
1998年噴泉碼概念由Michael Luby提出,2002年他又提出了第一個(gè)實(shí)用的噴泉碼 LT(Luby Transform)碼[1],在 LT碼的基礎(chǔ)上,2005年Mohammad Amin Shokrollahi提出了以L(fǎng)DPC碼為內(nèi)碼,LT碼為外碼的級(jí)聯(lián)噴泉碼—Raptor碼[2],目前噴泉碼的研究已逐漸展開(kāi)。
噴泉編碼因其無(wú)碼率的特點(diǎn),在刪除信道和低信噪比下的高斯信道中性能優(yōu)異[3-4],性能優(yōu)于LDPC碼等傳統(tǒng)糾錯(cuò)碼,特別適合于互聯(lián)網(wǎng)的傳輸和干擾下的無(wú)線(xiàn)通信,在深空通信中也有著巨大的潛力,目前已經(jīng)成為3GPP視頻流傳輸?shù)臉?biāo)準(zhǔn),并在4G通信協(xié)議LTE中廣泛應(yīng)用[5],華為、三星等通信巨頭在噴泉編碼領(lǐng)域已經(jīng)申請(qǐng)了大量專(zhuān)利。
由于噴泉編碼出現(xiàn)較晚,關(guān)于噴泉編碼的性能方面有大量的研究,主要分為三類(lèi)。一類(lèi)是針對(duì)預(yù)編碼部分的高碼率LDPC進(jìn)行優(yōu)化,由最初的Gallager的校驗(yàn)矩陣,到后來(lái)的Mackay的去四環(huán)的校驗(yàn)矩陣和PEG算法的校驗(yàn)矩陣,雖然后來(lái)通過(guò)非規(guī)則碼性能有了一點(diǎn)提升,但是在高碼率過(guò)程中,仍然不可避免的出現(xiàn)四環(huán)現(xiàn)象,影響譯碼效率,在高斯信道中尤為突出[6]。另一類(lèi)是在初始端再級(jí)聯(lián)一個(gè)常規(guī)的糾錯(cuò)碼,例如擴(kuò)展?jié)h明碼或者RS碼[7],這樣性能雖然在有些碼率和碼長(zhǎng)有一些改進(jìn),在有些碼長(zhǎng)還會(huì)出現(xiàn)誤碼率增大的情況,而且還會(huì)增加編譯碼的計(jì)算量。最后一種是對(duì)LT碼進(jìn)行度分布的優(yōu)化,LT碼的度分布也在針對(duì)各種碼長(zhǎng)進(jìn)行調(diào)整,由ideal到robust再到后來(lái)的weaken分布,最近又在碼的結(jié)構(gòu)和度分布有大量研究[8-9],都是為了使編碼分組的度分布更為均衡,這樣譯碼效率有所提高,在長(zhǎng)碼長(zhǎng)的情況下,由于大樣本使得度分布性能優(yōu)化不明顯,但是短碼長(zhǎng)差異較大,始終與理想性能有所差距[10]。本文將從原始分組角度,進(jìn)行度分布的修正規(guī)劃,使得每一個(gè)原始分組對(duì)于編譯碼的貢獻(xiàn)趨于一致,避免有些原始分組欠利用和過(guò)利用,最終達(dá)到較好的譯碼性能。
LT碼是噴泉編碼的核心,后來(lái)為了改善性能將碼率0.95-0.9的LDPC碼進(jìn)行級(jí)聯(lián),由于碼率較高,LDPC對(duì)于譯碼的提升有限,LT碼起關(guān)鍵作用。當(dāng)終端接收到的編碼數(shù)據(jù)包的數(shù)量略大于K個(gè)數(shù)據(jù)包時(shí),譯碼器就能夠以高概率成功地恢復(fù)出發(fā)送源數(shù)據(jù)分組。而度分布決定著LT碼碼組如何選擇,對(duì)于編譯碼有著至關(guān)重要的作用。
在LT碼的編碼中,度是指與編碼數(shù)據(jù)分組相連的源數(shù)據(jù)分組的個(gè)數(shù),如圖1所示,s為源數(shù)據(jù)分組,r為編碼數(shù)據(jù)分組。
圖1 度值示意圖Fig.1 Diagram of degree value
如圖1所示,給出了LT碼的編碼過(guò)程,編碼度分布Ω=(Ω1,Ω2,Ω3,…,Ωk)表示隨機(jī)選到整數(shù) d 的概率為 Ωd,為了便于數(shù)學(xué)處理,一般用度分布函數(shù)的形式表示為:
度概率分布函數(shù)ρ(d)是度即d=i的數(shù)據(jù)分組在總數(shù)據(jù)分組中占的比例。
理想孤子分布的隨機(jī)度生成方法,即隨機(jī)度按照以下概率分布規(guī)律確定:
孤立子分布為了保證每次譯碼過(guò)程中,度為1的集合不為0,為一個(gè)固定的值,為了提高譯碼成功率,Luby提出了一種修正的度分布(Robust Soliton Distribution,RSD)。他首先引入了兩個(gè)參數(shù)c和δ,其中c為一個(gè)常數(shù),δ為譯碼失敗概率的上界,并定義
其中,c=0.1,delta(δ)=0.5。
為了簡(jiǎn)化計(jì)算量,Amin Shokrollahi提出 Raptor碼,將LDPC碼和LT碼級(jí)聯(lián),但是LT碼使用弱化的weaken分布,度分布函數(shù)滿(mǎn)足:
Ω(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所示,其中原始碼長(zhǎng)K為100,編碼長(zhǎng)度N為200。ideal分布在度為2時(shí)達(dá)最大值,然后迅速下降,weaken分布在度為20時(shí)有一個(gè)上升,其它與ideal分布近似,weaken分布只是在固定的幾個(gè)點(diǎn)有值,其它點(diǎn)處為0。
圖2 度分布圖Fig.2 Diagram of degree distribution
度分布在很大程度上決定譯碼所需的分組數(shù)量,譯碼過(guò)程中實(shí)際度值為1的集合一直不為空,在一個(gè)恒定的范圍,能夠保證譯碼一直進(jìn)行。
傳統(tǒng)的LT編碼只對(duì)度進(jìn)行分配,雖然每個(gè)編碼分組是相互獨(dú)立的,但是所選擇的是哪些原始分組沒(méi)有考慮,這樣導(dǎo)致只注重編碼分組對(duì)于原始分組如何利用,而對(duì)于實(shí)際中由于隨機(jī)選擇原始分組給編碼帶來(lái)的貢獻(xiàn)差異沒(méi)有考慮,也沒(méi)有對(duì)于原始分組的分布進(jìn)行研究。本文將在原有編碼基礎(chǔ)上提出修正度分布,從原始分組角度進(jìn)行度的二次選擇。
本文將編碼分組作為原始分組,將原始分組作為編碼分組,逆向進(jìn)行統(tǒng)計(jì),得到原始度分布的置信區(qū)間,以此作為二次度分配的依據(jù)。
假設(shè)在LT編碼過(guò)程中,K個(gè)原始分組被編碼成N個(gè)編碼分組,根據(jù)度分布 ρ={ρ1,ρ2,…ρs},其 N 個(gè)編碼分組相應(yīng)地
通過(guò)度分布被重新劃分為 num={num1,num2,…nums},滿(mǎn)足
在逆向過(guò)程中,本文建立了ping模型和quan模型,分別進(jìn)行統(tǒng)計(jì)。在ping模型中,對(duì)于生成矩陣G(K×N),統(tǒng)計(jì)原始分組中參與編碼的個(gè)數(shù),[1 0 1 1 1]
例如G=0 0 1 1 0,K=3,N=5, 平均統(tǒng)計(jì)模型得到0 1 1 0 1 ping=[4,2,3],即原始分組1被調(diào)用了4次,分組2被調(diào)用了2次,分組3被調(diào)用了3次。
在quan模型中,對(duì)于生成矩陣 G(K×N),統(tǒng)計(jì)原始分組占該度分布下的權(quán)重,在矩陣G(K×N)中,加權(quán)統(tǒng)計(jì)模型得到quan=[7/3,5/6,11/6],如表 1 所示。
表1 quan模型計(jì)算值Tab.1 Com putation value in model ping
ping模型說(shuō)明被調(diào)用的次數(shù),次數(shù)越多,說(shuō)明參與編碼的次數(shù)多,在譯碼過(guò)程中可以得到的信息源越多,避免局部編碼分組出現(xiàn)污染而影響譯碼的判決。quan模型說(shuō)明原始分組在編碼過(guò)程中的影響能力,quan值越大,說(shuō)明該原始分組起的作用越明顯。例如對(duì)于編碼分組1和2,分別只調(diào)用了原始分組1和3,只有原始分組1和3對(duì)編碼分組1和2起作用,在得到編碼分組1和2時(shí),可以很順利地將原始分組1和3解出,而對(duì)于原始分組2,譯碼起來(lái)就顯得有些困難,需要得到編碼分組1和4的信息才能將其解出。
ping模型適合于高斯信道,能夠在低信噪比的情況下正確得到原始信息,但是譯碼起來(lái)需要很多次的迭代,在時(shí)間復(fù)雜度上開(kāi)銷(xiāo)很大,而且在刪除信道下,在迭代過(guò)程中存在實(shí)際度值為1的集合為空的情況。quan模型適合于刪除信道,可以在只獲取超過(guò)原始分組數(shù)目一點(diǎn)的情況下正確譯碼,但是在刪除概率增大的情況下,會(huì)出現(xiàn)原始分組沒(méi)有編碼分組對(duì)應(yīng)和起始譯碼度值為1的集合為空的情況,導(dǎo)致譯碼失敗。
本算法將巧妙結(jié)合這兩種模型,使得LT碼既適合高斯信道也適合刪除信道,性能有了明顯提升。
在ping模型中,對(duì)于每一個(gè)編碼分組,其度值全部都按照度分布 ρ={ρ1,ρ2,…ρs}的概率選擇集合 num={num1,num2,…nums},模型可以簡(jiǎn)化為s維伯努利分布函數(shù),而每一個(gè)原始分組是從編碼分組中均等概率地選擇出來(lái)。以weaken分布為例,如表2所示。
在ideal、robust和weaken分布中,維度和概率均不相等,但是都滿(mǎn)足維度較多,樣本較大的情況,這樣多維伯努利分布可以簡(jiǎn)化為正態(tài)分布,當(dāng)編碼分組為N時(shí),模型可以認(rèn)為是N次正態(tài)獨(dú)立事件,其期望為:以weaken分布為例,其期望值為Expectation=
表2 集合與度分布關(guān)系表Tab.2 Ralationship between sets and degree distributions
2×5.701 =11.738由于不同的度分布,每個(gè)原始分組的ping與期望的偏差pingi-Expectation的絕對(duì)值和方差不盡相同,本文采取實(shí)驗(yàn)的方法,取K=1 000,N=2 000,對(duì)3種分布仿真1 000次進(jìn)行統(tǒng)計(jì),得到表3所示。
表3 ping模型期望方差表Tab.3 Expectation and variance in model ping
可以看到,3個(gè)模型的期望值差別很大,很難有一個(gè)統(tǒng)一的標(biāo)準(zhǔn),標(biāo)準(zhǔn)差差別不大,在3-4之間,所以本文選擇3作為ping模型的閾值。
在quan模型中,對(duì)于每一個(gè)編碼分組,首先全部都按照度分布 ρ={ρ1,ρ2,…ρs}的概率選擇 num={num1,num2,…nums}選定一個(gè)度值numi,如果隨機(jī)選中原始分組,其quan值為1/numi,模型可以看做是度分布 ρ={ρ1,ρ2,…ρs}的取值為 num={1/num1,1/num2,…1/nums}的 N 次 s維伯努利分布,任意原始分組期望度值為unmi/K,相對(duì)于該編碼分組的平均度期望Expe_degree=·numi,quan 模 型 中 原 始 分 組 quani=,原始分組中quan模型的期望為:
這樣對(duì)于不同度分布,其quan模型的期望值與度分布沒(méi)有關(guān)系,只與K值和N值有關(guān)。但是方差仍然依賴(lài)于分布函數(shù),下面是對(duì)3種分布的1000次仿真統(tǒng)計(jì),得到表4。
表4 quan模型期望方差表Tab.4 Expectation and variance in model quan
可以看到,在quan模型中,期望值偏差和方差差距都不明顯,所以本文以0.7作為quan模型的閾值較為合適。
兩個(gè)模型和閾值建立起來(lái),首先隨機(jī)地進(jìn)行編碼,每生成一個(gè)編碼分組,統(tǒng)計(jì)被選中的原始分組的ping值和quan值,當(dāng)滿(mǎn)足條件:
該原始分組被拋棄,在以后的編碼過(guò)程中不被選擇。這樣一來(lái),絕大多數(shù)的原始分組都落在了Expectation_ping和Expectation_quan附近,整個(gè)編碼得到了優(yōu)化。
而在實(shí)際的編碼中,由于存在最后階段沒(méi)有足夠的原始分組可供選擇,所以設(shè)定閾值,當(dāng)0.95K都被拋棄時(shí),此時(shí)已編碼M個(gè)編碼分組,最后N-M個(gè)編碼分組采用原來(lái)的編碼算法。前M個(gè)和后來(lái)的N-M個(gè)采用的是兩種編碼算法,顯然前者的效果更好,需要對(duì)編碼分組和編碼矩陣進(jìn)行置亂,使得能夠更好地體現(xiàn)在刪除和高斯信道的性能,本文對(duì)于1×N維矩陣和N×N維矩陣提出ming置亂算法,其步驟如下:
1)選取Logistic方程作為模型的混沌序列發(fā)生器:xn+1=μxn(1+xn),這樣每一個(gè)隨機(jī)數(shù)都在 0和 1之間。
2)選取N×N維單位陣I,將第一個(gè)隨機(jī)數(shù)乘以N得到操作數(shù)x,然后對(duì)x做[x]運(yùn)算,將[x]列與第N列進(jìn)行交換。
3)將第二個(gè)隨機(jī)數(shù)乘以 N-1,然后對(duì)操作數(shù)做[x]運(yùn)算,將[x]列與第N-1列進(jìn)行交換。
4)重復(fù)第2個(gè)步驟,直至剩下最后1列為止。
這樣能夠保證每一個(gè)編碼分組都能等概隨機(jī)地排列在最后傳輸分組的任意位置。
將原始數(shù)據(jù)等分為K個(gè)數(shù)據(jù)分組 (最后一個(gè)分組可以補(bǔ)0后成等分),根據(jù)輸入碼長(zhǎng)K和輸出碼長(zhǎng)N,選擇weaken分布作為原始分布,計(jì)算出ping模型的期望和quan模型的期望。
根據(jù)設(shè)計(jì)的度分布Ω,隨機(jī)地選取編碼數(shù)據(jù)分組的度d,對(duì)每一個(gè)編碼分組,從K個(gè)輸入數(shù)據(jù)包中,等概率地隨機(jī)選取d個(gè)不同的原始數(shù)據(jù)分組,計(jì)算這d個(gè)原始分組的ping值和quan值。當(dāng)有原始分組滿(mǎn)足公式(8)時(shí),該分組舍去,從剩下的原始分組中隨機(jī)選取不滿(mǎn)足公式(8)的分組,直至d個(gè)原始分組都被選取,將這d個(gè)原始分組模二加,生成一個(gè)編碼數(shù)據(jù)分組。
重復(fù)上述過(guò)程,統(tǒng)計(jì)已經(jīng)滿(mǎn)足公式(8)的原始分組個(gè)數(shù),當(dāng)其已經(jīng)達(dá)到0.95K時(shí),此編碼過(guò)程結(jié)束,記下已經(jīng)編碼的編碼分組個(gè)數(shù)M。
將剩下的N-M個(gè)未編碼分組按照原先的編碼方式編碼,選取度分布值d,根據(jù)d隨機(jī)選取原始d個(gè)原始分組,將這d個(gè)原始分組模二加,生成一個(gè)編碼數(shù)據(jù)分組。
當(dāng)N-M個(gè)編碼分組編完后,將所有N個(gè)編碼分組ming置亂,選擇Logistic方程作為混沌方程,設(shè)定初始值μ,得到隨機(jī)數(shù)列,進(jìn)而得到置亂矩陣,對(duì)編碼分組進(jìn)行置亂,得到最終的傳輸分組。
當(dāng)收到傳輸分組,首先根據(jù)初始值通過(guò)Logistic方程得到隨機(jī)數(shù)列,對(duì)傳輸分組反置亂。
這里譯碼采用BP算法,所不同的是刪除信道采用硬判決的BP算法,而高斯信道采用的是log-BP的軟判決算法。譯碼算法根據(jù)編碼數(shù)據(jù)分組與輸入數(shù)據(jù)分組的對(duì)應(yīng)關(guān)系建立二部圖。在硬判決譯碼的每一步,譯碼器都在編碼集合中尋找度為1的分組,這些分組組成的集合稱(chēng)為輸出可譯集合,具體譯碼如圖3所示。log-BP的軟判決算法相對(duì)復(fù)雜,本文就不再贅述。
圖3 BP硬判決譯碼圖Fig.3 Diagram of BP hard decision decoding
在數(shù)據(jù)傳輸?shù)倪^(guò)程中,會(huì)由于各種各樣的原因發(fā)生數(shù)據(jù)分組的丟失和干擾,在常規(guī)的糾錯(cuò)編碼中,當(dāng)一個(gè)大的數(shù)據(jù)流發(fā)生超過(guò)其糾錯(cuò)能力的時(shí)候,會(huì)發(fā)生整個(gè)數(shù)據(jù)無(wú)法解碼出來(lái),但是噴泉碼還會(huì)在一定程度上將一定數(shù)量的分組解碼出來(lái),本算法使得噴泉碼在這兩種信道性能進(jìn)一步增強(qiáng)。
本文分別進(jìn)行LT編碼和Raptor編碼,原始分組長(zhǎng)度K值取1 000,編碼分組長(zhǎng)度N值取2 000,為方便起見(jiàn),每個(gè)分組只是0,1比特,置亂選擇 Logistic方程,初始值 μ為 0.37,每個(gè)仿真節(jié)點(diǎn)仿真100次。
在 LT編碼中,LT度分布采用 ideal、robust和 weaken分布,當(dāng)有950個(gè)原始分組都已經(jīng)達(dá)到要求被拋棄時(shí),本文所采取的編碼算法自動(dòng)終止,采用原來(lái)的編碼算法將剩下的編碼分組全部編完,然后用ming算法將編碼分組和編碼矩陣進(jìn)行置亂。
在Raptor碼中,LT度分布采用weaken分布,首先進(jìn)行LDPC預(yù)編碼,將1 000個(gè)分組編碼為1 050個(gè)分組,碼率為0.95,然后將1 050個(gè)中間分組噴泉編碼為2 000編碼分組。
在LDPC預(yù)編碼中,采用PEG的非規(guī)則編碼,校驗(yàn)矩陣H的列的度分布函數(shù)為:
f(x)=0.283 54x+0.242 37x2+0.474 09x3(9)
當(dāng)有1 000個(gè)中間分組滿(mǎn)足條件被拋棄時(shí),本文算法終止,采用原來(lái)的編碼算法將剩下的編碼分組全部編完,最后用ming算法將編碼分組和編碼矩陣置亂得到傳輸分組。
圖4 ping模型分布圖Fig.4 Distribution diagram ofmodel ping
圖5 quan模型分布圖Fig.5 Distribution diagram ofmodel quan
如圖4所示,在ping模型中,通過(guò)閾值設(shè)定,通過(guò)對(duì)比,原始分組明顯向期望值11.7靠近,每一個(gè)原始分組對(duì)于編譯碼的貢獻(xiàn)趨于一致。當(dāng)0.95個(gè)原始分組被使用完,表明沒(méi)有足夠的原始分組可供利用,在ping值兩端,會(huì)出現(xiàn)原有算法得到的ping,由于最后的編碼數(shù)很少,對(duì)編譯碼沒(méi)有太大的影響。
如圖5所示,在quan模型中,通過(guò)閾值設(shè)定,原始分組向期望值2靠近,說(shuō)明每一個(gè)原始分組的貢獻(xiàn)也是一致的,這樣能夠避免在譯碼過(guò)程中由于信道的影響帶來(lái)糾錯(cuò)性能的下降。
本文通過(guò)BEC信道和AWGN信道進(jìn)行測(cè)試,其中BEC信道采用0.025的比例步長(zhǎng),刪除概率從0.3到0.5進(jìn)行測(cè)試,AWGN信道采用1db的信噪比步長(zhǎng),信噪比從-5db到0db進(jìn)行測(cè)試,文獻(xiàn)[9]的結(jié)果作為BEC信道的對(duì)比,而文獻(xiàn)[10]的結(jié)果作為AWGN信道的對(duì)比。
圖6 BEC信道誤碼率顯示圖Fig.6 Chart of BER in the BEC channel
圖7 AWGN信道誤碼率顯示圖Fig.7 Chart of BER in the AWGN channel
測(cè)試結(jié)果如圖6和圖7所示,在高的刪除概率下,本文采用的算法誤碼率明顯降低,而且在零誤碼率的情況下所需的分組數(shù)也小于常規(guī)的方法。在低信噪比下,本文采用的算法比LT和Raptor常規(guī)的方法在相同的信噪比下誤碼率低,而且達(dá)到的誤碼率所需的信噪比也低于原來(lái)的方法。
本文通過(guò)對(duì)噴泉碼原始分組的構(gòu)成分析,提出ping模型和quan模型,使原始分組對(duì)于編碼的貢獻(xiàn)趨于一致,對(duì)中短碼長(zhǎng)的隨機(jī)特性予以約束,避免原始分組被欠利用和過(guò)利用,這樣提高了編碼的效率,進(jìn)而加強(qiáng)了抵抗干擾的能力,使得在干擾較強(qiáng)的情況下仍然有較低的誤碼率。由于閾值已經(jīng)設(shè)定好,所以實(shí)現(xiàn)起來(lái)較為簡(jiǎn)單,保證絕大多數(shù)的原始分組的ping值和quan值都在期望附近,最后又提出ming置亂算法,使得每一個(gè)編碼分組所攜帶的信息更為均衡。這樣在降低復(fù)雜度的同時(shí),又進(jìn)一步提高了噴泉碼的糾錯(cuò)能力。
[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.