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

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

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

0 引言

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

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

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

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

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

1 LT碼

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

1.1 LT碼編碼算法

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

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

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

重復以上步驟就可以源源不斷地產生任意數量的編碼數據包。若記k個原始數據包為x=[x1,x2,…,xk]，n個編碼數據包為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部分即為譯出的原始數據包。

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

(2)

2 傳統LT碼性能界分析

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

1)若n

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

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

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

(3)

(4)

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

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

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

Pfail=1-(1-Pb)k

(5)

由此，很容易得到結論2。

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

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

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

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

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

3 基于概率轉移的LT碼性能分析

傳統方法雖然給出了LT碼字在高斯消元算法下性能的上、下界，但是存在著不足與缺陷：一是性能界十分寬松，并不能很好地指導實踐應用；二是計算表達式十分復雜，無法利用到實際過程中的碼字優化設計當中。基于上述考慮，本文基于譯碼過程中編碼數據包與生成矩陣秩之間的必然聯系，給出了基于概率轉移的LT碼性能分析方法。

3.1 基于概率轉移的LT碼性能分析

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

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

(6)

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

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

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

Ω(x)=x

(7)

即：

(8)

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

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

(9)

證明

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

當m

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

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

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

(11)

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

(12)

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

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

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

3.3 隨機線性碼字性能分析

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

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

(13)

即：

(14)

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

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

(15)

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

當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個原始數據包，生成向量共有2k-1種(所有組合共2k個，生成向量必須除掉全0向量)，根據矩陣秩的定義，當生成矩陣的秩為r時，2k-1種生成向量中，其中2r-1種能夠由生成矩陣的列線性生成，剩余2k-2r種則不能由生成矩陣的列線性生成，而隨機線性碼每種生成向量的產生概率相同，則有：

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

(17)

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

(18)

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

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

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

3.4 一般性LT碼字性能分析

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

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

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

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

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

定理3給出了Pr_Same的計算表達式。

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

(19)

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

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

4 仿真驗證

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

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

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

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

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

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

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

Tab. 1 Simulation parameters

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

表2 譯碼失敗概率Pfail與等同概率Pr_Same對應關系

5 結語

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