高斯消元譯碼下LT碼性能分析

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

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

0 引言

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

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

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

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

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

1 LT碼

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

1.1 LT碼編碼算法

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

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

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

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

y=xGk×n

(1)

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

1.2 LT碼高斯消元譯碼算法

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

步驟1 判斷生成矩陣Gk×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是否可逆，可以通過計算Gk×n的秩rank(Gk×n)進行判斷，則可以得到以下結(jié)論：

1)若n

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

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

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

(3)

(4)

證明 見參考文獻[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，這里不作贅述。

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

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

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

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

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

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

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

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

(6)

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

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

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

Ω(x)=x

(7)

即：

(8)

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

定理1 對于全1度分布有：

(9)

證明

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

當(dāng)m

當(dāng)m≥r>1時，由于1個編碼數(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個編碼數(shù)據(jù)包時生成矩陣秩為r條件下m個編碼數(shù)據(jù)包時生成矩陣秩為r；Pr{(m,r)|(m-1,r-1)}為條件概率，表示m-1個編碼數(shù)據(jù)包時生成矩陣秩為r-1條件下m個編碼數(shù)據(jù)包時生成矩陣秩為r。

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

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)，即可計算獲得全1度分布碼字精確的譯碼失敗概率。

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

3.3 隨機線性碼字性能分析

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

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

(13)

即：

(14)

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

定理2 對于隨機線性碼有：

(15)

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

當(dāng)m≥r>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)}

(16)

k個原始數(shù)據(jù)包，生成向量共有2k-1種(所有組合共2k個，生成向量必須除掉全0向量)，根據(jù)矩陣秩的定義，當(dāng)生成矩陣的秩為r時，2k-1種生成向量中，其中2r-1種能夠由生成矩陣的列線性生成，剩余2k-2r種則不能由生成矩陣的列線性生成，而隨機線性碼每種生成向量的產(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)，即可計算獲得隨機線性碼精確的譯碼失敗概率。

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

3.4 一般性LT碼字性能分析

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

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

根據(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的計算表達式。

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

(19)

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

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

4 仿真驗證

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

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

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

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

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

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

圖2 隨機線性LT碼性能分析

Tab. 1 Simulation parameters

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

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

5 結(jié)語

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