索龍龍，張更新，邊東明，謝智東，田 湘

(1.解放軍陸軍工程大學(xué) 通信工程學(xué)院，南京210007； 2.南京郵電大學(xué) 通信與信息工程學(xué)院，南京210003)(*通信作者電子郵箱bian_dm@163.com)

0 引言

通信，核心問(wèn)題就是保證信息能夠準(zhǔn)確無(wú)誤且高效地從信源發(fā)送到目的節(jié)點(diǎn)，因而數(shù)據(jù)的可靠傳輸策略備受關(guān)注。

在空間通信環(huán)境下，星地間信道由于受到遠(yuǎn)距離、天氣變化及遮擋等因素的影響，數(shù)據(jù)傳輸時(shí)延長(zhǎng)且丟包率較高，使得地面成熟的傳輸控制協(xié)議(Transmission Control Protocol, TCP)中端到端確認(rèn)重發(fā)機(jī)制性能急劇下降[1-4]，尤其是在多用戶量的廣播系統(tǒng)。例如，當(dāng)一個(gè)系統(tǒng)有很多用戶時(shí)，高的丟包率會(huì)導(dǎo)致系統(tǒng)在較短時(shí)間內(nèi)接收到大量的數(shù)據(jù)重傳請(qǐng)求，降低系統(tǒng)的傳輸性能。與此同時(shí)，空間系統(tǒng)長(zhǎng)的傳輸時(shí)延以及大量數(shù)據(jù)重傳的共同作用將使得全部數(shù)據(jù)包成功可靠傳輸?shù)臅r(shí)延變長(zhǎng)，往往使得用戶無(wú)法忍受。

LT碼通常采用兩種譯碼算法：置信傳播(Belief Propagation， BP)[11-12]以及高斯消元(Gaussian Elimination, GE)[13-14]。其中BP算法譯碼復(fù)雜度低，但成功譯碼所需的編碼數(shù)據(jù)包較多；與BP相反，GE算法譯碼所需碼字冗余較少，但復(fù)雜度略高。隨著時(shí)代發(fā)展的進(jìn)步，GE算法逐步得到很大程度的應(yīng)用，一方面是硬件水平的提高，使得算法復(fù)雜度已經(jīng)不再成為主要矛盾；另一方面是對(duì)實(shí)時(shí)性要求較高的應(yīng)用，例如話音、流媒體等，要求采用短碼字、譯碼冗余少以保證成功傳輸所需的時(shí)延盡可能地短。

盡管高斯消元算法得到了比較廣泛的研究與應(yīng)用，但針對(duì)高斯消元算法下LT碼字性能的理論分析仍然不盡完善。文獻(xiàn)[15-16]也只是給出了十分寬松的上、下界，而且計(jì)算表達(dá)式十分復(fù)雜，并不能很好地指導(dǎo)實(shí)踐應(yīng)用以及實(shí)際過(guò)程中的碼字優(yōu)化設(shè)計(jì)。

針對(duì)文獻(xiàn)[15-16]提出的LT碼性能分析方法計(jì)算復(fù)雜且準(zhǔn)確度不高這一問(wèn)題，本文從高斯消元譯碼算法的本質(zhì)出發(fā)，對(duì)LT碼的性能展開研究分析，給出了基于概率轉(zhuǎn)移的性能計(jì)算表達(dá)式以及一種簡(jiǎn)單有效的性能衡量指標(biāo)。

1 LT碼

為克服傳統(tǒng)差錯(cuò)控制策略的不足，Luby等[7]于2002年提出來(lái)第一種實(shí)用的數(shù)字噴泉碼編碼方案——LT碼。LT碼是一種隨機(jī)編碼，沒(méi)有固定碼率，可以由原始的數(shù)據(jù)包產(chǎn)生任意數(shù)量的編碼數(shù)據(jù)包。

1.1 LT碼編碼算法

步驟1 根據(jù)LT碼預(yù)先設(shè)計(jì)的度的概率分布{Ω1,Ω2,…,Ωk}，隨機(jī)采樣得到一個(gè)度值d(1≤d≤k)。

步驟2 均勻隨機(jī)選擇d個(gè)不同的原始數(shù)據(jù)包。

步驟3 選取的d個(gè)不同的原始數(shù)據(jù)包進(jìn)行異或編碼生成編碼包，選取的d個(gè)原始數(shù)據(jù)包稱作該編碼包的鄰居。

重復(fù)以上步驟就可以源源不斷地產(chǎn)生任意數(shù)量的編碼數(shù)據(jù)包。若記k個(gè)原始數(shù)據(jù)包為x=[x1,x2,…,xk]，n個(gè)編碼數(shù)據(jù)包為y=[y1,y2,…,yn]，則編碼算法又可以寫成矩陣形式：

y=xGk×n

(1)

其中Gk×n為碼字的生成矩陣[8,17]。

1.2 LT碼高斯消元譯碼算法

高斯消元譯碼，也被稱作最大似然的譯碼，主要步驟如下。

步驟1 判斷生成矩陣Gk×n是否可逆，如果是，則可以進(jìn)行譯碼；如果不是，則譯碼停止。

步驟2 如果Gk×n可逆，將生成矩陣Gk×n和編碼包y組成的分塊矩陣[Gk×n,y]變換為[I,x]，則x部分即為譯出的原始數(shù)據(jù)包。

高斯消元算法主要思想是求解線性方程組，若生成矩陣Gk×n可逆，則可成功譯碼。其數(shù)學(xué)思想即求解方程：

(2)

2 傳統(tǒng)LT碼性能界分析

高斯消元譯碼算法能否成功譯碼取決于生成矩陣Gk×n是否可逆，可逆則譯碼成功；否則譯碼失敗。而Gk×n是否可逆，可以通過(guò)計(jì)算Gk×n的秩rank(Gk×n)進(jìn)行判斷，則可以得到以下結(jié)論：

1)若n

2)若n≥k，則存在可能rank(Gk×n)=k，若rank(Gk×n)=k，則Gk×n可逆，譯碼成功。

文獻(xiàn)[15-16]給出了LT碼在高斯消元算法下譯碼失敗概率的上、下界。

結(jié)論1 對(duì)于LT碼LT(Ω(x),k,n)，若記編碼冗余為γ=n-k，任意一個(gè)原始數(shù)據(jù)包譯碼失敗的概率為Pb，則：

(3)

(4)

證明 見參考文獻(xiàn)[15-16]，這里不再贅述。

為表述方便，記PbMIN≤Pb≤PbMAX。

若記譯碼失敗的概率Pfail，則有：

Pfail=1-(1-Pb)k

(5)

由此，很容易得到結(jié)論2。

結(jié)論2 1-(1-PbMIN)k≤Pfail≤1-(1-PbMAX)k。

證明 根據(jù)式(5)以及邊界關(guān)系，很容易得到結(jié)論2，這里不作贅述。

因?yàn)槭?5)不涉及循環(huán)計(jì)算，其計(jì)算復(fù)雜度為O(1)，因而文獻(xiàn)[15-16]提出的性能分析方法復(fù)雜度主要由式(3)、(4)決定。

式(3)計(jì)算Pb上界時(shí)有三層循環(huán)求和運(yùn)算，由內(nèi)及外的求和運(yùn)算分別是s=0,2,…,2?d/2」，d=1,2,…,k，w=1,2,…,k，因而由加法帶來(lái)的運(yùn)算次數(shù)是O(k3)，與此同時(shí)，式(5)還存在組合運(yùn)算與冪運(yùn)算，其中組合運(yùn)算復(fù)雜度為O(k)，冪運(yùn)算復(fù)雜度為O(n)，因此式(3)的計(jì)算復(fù)雜度為O(nk4)。

式(4)計(jì)算Pb下界時(shí)只有一層循環(huán)求和運(yùn)算和冪運(yùn)算，其中求和運(yùn)算復(fù)雜度為O(k)，冪運(yùn)算復(fù)雜度為O(n)，因而式(4)的計(jì)算復(fù)雜度為O(nk)。

3 基于概率轉(zhuǎn)移的LT碼性能分析

傳統(tǒng)方法雖然給出了LT碼字在高斯消元算法下性能的上、下界，但是存在著不足與缺陷：一是性能界十分寬松，并不能很好地指導(dǎo)實(shí)踐應(yīng)用；二是計(jì)算表達(dá)式十分復(fù)雜，無(wú)法利用到實(shí)際過(guò)程中的碼字優(yōu)化設(shè)計(jì)當(dāng)中?；谏鲜隹紤]，本文基于譯碼過(guò)程中編碼數(shù)據(jù)包與生成矩陣秩之間的必然聯(lián)系，給出了基于概率轉(zhuǎn)移的LT碼性能分析方法。

3.1 基于概率轉(zhuǎn)移的LT碼性能分析

高斯消元譯碼算法其能否成功譯碼取決于生成矩陣的秩是否為滿秩，譯碼器接收到一個(gè)編碼數(shù)據(jù)包就會(huì)使得原有生成矩陣秩發(fā)生變化，秩加1或保持不變。基于此，本文提出基于概率轉(zhuǎn)移的LT碼性能分析方法，表述如下。

對(duì)于LT碼字LT(Ω(x),k,n)，譯碼失敗概率為n個(gè)編碼數(shù)據(jù)包時(shí)所有生成矩陣Gk×n秩小于k概率的和，若記Pr(n,r)為n個(gè)編碼數(shù)據(jù)包時(shí)生成矩陣Gk×n秩為r的概率，則有譯碼失敗概率Pfail：

(6)

3.2 全1度分布碼字性能分析

全1度分布是LT碼字最簡(jiǎn)單的形式，也是LT碼字最基本的樣式。

定義1 全1度分布函數(shù)Ω(x)如式(6)所示：

Ω(x)=x

(7)

即：

(8)

為分析全1度分布碼字性能，本文給出定理1。

定理1 對(duì)于全1度分布有：

(9)

證明

當(dāng)有1個(gè)編碼數(shù)據(jù)包，生成矩陣Gk×1為k×1的，則Pr(1,1)=1；

當(dāng)m

當(dāng)m≥r>1時(shí)，由于1個(gè)編碼數(shù)據(jù)包，只能使得生成矩陣多1列，生成矩陣的秩就只能保持不變或加1，因而

Pr(m,r)=Pr(m-1,r)·Pr{(m,r)|(m-1,r)}+

Pr(m-1,r-1)·Pr{(m,r)|(m-1,r-1)}

(10)

其中：Pr{(m,r)|(m-1,r)}為條件概率，表示m-1個(gè)編碼數(shù)據(jù)包時(shí)生成矩陣秩為r條件下m個(gè)編碼數(shù)據(jù)包時(shí)生成矩陣秩為r；Pr{(m,r)|(m-1,r-1)}為條件概率，表示m-1個(gè)編碼數(shù)據(jù)包時(shí)生成矩陣秩為r-1條件下m個(gè)編碼數(shù)據(jù)包時(shí)生成矩陣秩為r。

由于每次生成的編碼數(shù)據(jù)包度均為1，即生成矩陣的每一列的權(quán)重為1，因而有且只有當(dāng)新的列與所有其他列不同時(shí)，會(huì)使得原有生成矩陣的秩增加，即：

Pr{(m,r)|(m-1,r)}=r/k

(11)

Pr{(m,r)|(m-1,r-1)}=(k-r+1)/k

(12)

聯(lián)立式(9)～(11)，定理1得證。

聯(lián)立式(6)、(9)，即可計(jì)算獲得全1度分布碼字精確的譯碼失敗概率。

式(6)只含有一層循環(huán)加法運(yùn)算，因而復(fù)雜度為O(k)；利用式(9)計(jì)算Pr(n,r)為迭代運(yùn)算，需要迭代計(jì)算所有Pr(nn≤n,rr≤r≤k)，由于每次迭代不涉及循環(huán)計(jì)算(復(fù)雜度為O(1))，因而式(9)計(jì)算Pr(n,r)的復(fù)雜度為O(nk)，則全1度分布碼字精確的譯碼失敗概率Pfail計(jì)算復(fù)雜度為O(nk2)。

3.3 隨機(jī)線性碼字性能分析

隨機(jī)線性碼字指的是生成矩陣中元素0、1均為等概出現(xiàn)，也代表著每一個(gè)編碼數(shù)據(jù)包也是等概率出現(xiàn)。

定義2 隨機(jī)線性碼度分布函數(shù)如式(13)所示：

(13)

即：

(14)

與全1度分布類似，隨機(jī)線性碼性能分析如下。

定理2 對(duì)于隨機(jī)線性碼有：

(15)

證明 其中Pr(1,1)=1，以及當(dāng)m

當(dāng)m≥r>1時(shí)，同理有：

Pr(m,r)=Pr(m-1,r)·Pr{(m,r)|(m-1,r)}+

Pr(m-1,r-1)·Pr{(m,r)|(m-1,r-1)}

(16)

k個(gè)原始數(shù)據(jù)包，生成向量共有2k-1種(所有組合共2k個(gè)，生成向量必須除掉全0向量)，根據(jù)矩陣秩的定義，當(dāng)生成矩陣的秩為r時(shí)，2k-1種生成向量中，其中2r-1種能夠由生成矩陣的列線性生成，剩余2k-2r種則不能由生成矩陣的列線性生成，而隨機(jī)線性碼每種生成向量的產(chǎn)生概率相同，則有：

Pr{(m,r)|(m-1,r)}=(2r-1)/(2k-1)

(17)

Pr{(m,r)|(m-1,r-1)}=(2k-2r)/(2k-1)

(18)

聯(lián)立式(16)～(18)，定理2得證。

聯(lián)立式(6)、(15)，即可計(jì)算獲得隨機(jī)線性碼精確的譯碼失敗概率。

與全1度分布類似，隨機(jī)線性碼的譯碼失敗概率Pfail計(jì)算復(fù)雜度主要由式(6)、(15)決定。其中式(6)只含有一層循環(huán)加法運(yùn)算，因而復(fù)雜度為O(k)；利用式(15)計(jì)算Pr(n,r)為迭代運(yùn)算，需要迭代計(jì)算所有Pr(nn≤n,rr≤r≤k)，與全1度分布不同的是，每次迭代包含冪運(yùn)算(復(fù)雜度為O(k))，因而式(15)計(jì)算Pr(n,r)的復(fù)雜度為O(nk2)，則全1度分布碼字精確的譯碼失敗概率Pfail計(jì)算復(fù)雜度為O(nk3)。

3.4 一般性LT碼字性能分析

對(duì)于一般性LT碼，度分布的不均勻性會(huì)使得不同生成向量的產(chǎn)生概率不同，生成矩陣Gk×m與Gk×(m+1)之間秩的變化十分復(fù)雜且不具有規(guī)律性，因此很難像全1度分布以及隨機(jī)線性碼那樣，通過(guò)計(jì)算生成矩陣秩的變化來(lái)獲得精確的譯碼失敗概率。為解決一般性碼字性能衡量的難題，本文給出了一種新的指標(biāo)參數(shù)——等同概率Pr_Same。

定義3 等同概率Pr_Same是指LT碼LT(Ω(x),k,n)任意產(chǎn)生兩個(gè)相同編碼數(shù)據(jù)包(等同于兩個(gè)相同生成向量)的概率。

根據(jù)定義，結(jié)合高斯譯碼原理(生成矩陣Gk×n可逆)，可以得到結(jié)論3。

結(jié)論3Pr_Same越大，碼字譯碼失敗概率Pfail越大；反之Pr_Same越小，Pfail越小。

證明Pr_Same越大，則生成矩陣Gk×n中任意兩列相同的概率越大，Gk×n中相同列的數(shù)目越大，Gk×n可逆的概率越小，則碼字譯碼失敗概率Pfail越大；反之亦然。

定理3給出了Pr_Same的計(jì)算表達(dá)式。

定理3 對(duì)于LT碼LT(Ω(x),k,n)

(19)

證明 任意兩個(gè)編碼數(shù)據(jù)包相同意味著：1)兩者的度相同；2)度的連接關(guān)系一致，即編碼數(shù)據(jù)包的鄰居相同。

等同概率Pr_Same計(jì)算復(fù)雜度主要由式(19)決定。式(19)只涉及一層循環(huán)加法運(yùn)算以及組合運(yùn)算，因而其復(fù)雜度為O(k2)。

4 仿真驗(yàn)證

本文分別對(duì)全1度分布、隨機(jī)線性碼以及一般性LT碼的性能衡量方法進(jìn)行了仿真驗(yàn)證，其中全1度分布、隨機(jī)線性碼與文獻(xiàn)[15-16]的方法作了比較，一般性LT碼采用了經(jīng)典的魯棒孤波分布(Robust Soliton Distribution， RSD)以及理想孤波分布(Ideal Soliton Distribution， ISD)。值得說(shuō)明的是：每個(gè)數(shù)據(jù)包大小為20 bit，譯碼失敗概率通過(guò)500次Monte-Carlo仿真計(jì)算所得；對(duì)于任意碼字LT(Ω(x),k,n)，仿真圖、表中采用的譯碼冗余為(n-k)/k。

圖1給出了對(duì)于全1度分布LT碼，基于概率轉(zhuǎn)移方法與文獻(xiàn)[15-16]的方法對(duì)碼字性能評(píng)價(jià)的對(duì)比曲線。結(jié)果表明，基于概率轉(zhuǎn)移方法可以精確表征碼字的譯碼失敗概率，性能分析最大殘差降低到0.004 3。與之對(duì)比，文獻(xiàn)[15-16]方法給出了性能曲線的上下界，但是上、下界曲線比較寬松，性能分析最大殘差為0.215 7，無(wú)法準(zhǔn)確衡量碼字譯碼性能。

圖2給出了對(duì)于隨機(jī)線性碼字，基于概率轉(zhuǎn)移方法與文獻(xiàn)[15-16]的方法對(duì)碼字性能評(píng)價(jià)的對(duì)比曲線。結(jié)果表明，基于概率轉(zhuǎn)移方法依然可以精確表征碼字的譯碼失敗概率，性能分析最大殘差降低到0.012 4；但是此刻傳統(tǒng)方法給出的性能的上、下界曲線，都比較寬松，性能分析最大殘差為0.893 2，無(wú)法準(zhǔn)確衡量碼字譯碼性能。

結(jié)合圖1～2結(jié)果可知，文獻(xiàn)[15-16]方法盡管給出了碼字性能的上、下界，但是無(wú)法準(zhǔn)確衡量碼字性能；相反，基于概率轉(zhuǎn)移方法能夠準(zhǔn)確計(jì)算全1度分布LT碼、隨機(jī)線性LT碼的性能。

為證明等同概率Pr_Same與譯碼失敗概率Pfail間的正比關(guān)系，文章仿真了不同類型LT碼字(具體參數(shù)如表1所示)的譯碼概率Pfail，對(duì)比計(jì)算了等同概率Pr_Same。

圖1 全1度分布LT碼性能分析曲線

圖2 隨機(jī)線性LT碼性能分析

Tab. 1 Simulation parameters

表2分別給出了原始數(shù)據(jù)包個(gè)數(shù)為100、300時(shí)，等同概率Pr_Same與譯碼失敗概率Pfail間的對(duì)應(yīng)關(guān)系。表2結(jié)果表明，隨著等同概率Pr_Same的遞增，譯碼失敗概率Pfail也隨之上升，即一定程度上表明兩者存在正比關(guān)系。同時(shí)也說(shuō)明等同概率可以作為一個(gè)衡量LT碼性能的指標(biāo)，等同概率越小，譯碼失敗概率越小，碼字性能越好。

表2 譯碼失敗概率Pfail與等同概率Pr_Same對(duì)應(yīng)關(guān)系

5 結(jié)語(yǔ)

本文對(duì)LT的性能進(jìn)行了理論分析，推導(dǎo)了準(zhǔn)確計(jì)算全1分布以及隨機(jī)線性LT碼性能的數(shù)學(xué)表達(dá)式；同時(shí)，針對(duì)一般碼字的復(fù)雜情況，給出了一種性能評(píng)價(jià)指標(biāo)體系——等同概率。理論分析以及仿真結(jié)果表明，相比已有方法，提出的新的性能計(jì)算方法準(zhǔn)確度高，評(píng)價(jià)指標(biāo)體系簡(jiǎn)單有效。本文的局限性在于一般性碼字性能的準(zhǔn)確衡量還有待進(jìn)一步研究。下一步工作主要可以從兩方面展開：一是進(jìn)一步研究碼字性能的準(zhǔn)確衡量；二是立足于現(xiàn)有結(jié)論可以對(duì)碼字的優(yōu)化設(shè)計(jì)展開研究。