LT碼的一種非階梯化高斯消元譯碼算法

賀 亮，雷 菁，黃 英

(國防科技大學 電子科學學院，湖南 長沙 410073)

0 引言

為了避免多播系統中，多個終端向發端反饋重傳信息時的反饋風暴，相關學者提出了噴泉碼的編碼方案[1-3]，通過噴泉編碼，可以生成理論上無窮多個編碼符號，因此噴泉碼也被稱為無碼率碼。Luby提出的LT碼[4]是首個可以具體實現的噴泉碼，其編碼符號是信息符號的線性組合。Shokrollahi提出Raptor碼[5],通過在LT碼前加上固定碼率的信道編碼，使其能夠在噪聲信道下發揮更出色的性能。目前噴泉碼在數字視頻廣播標準[6]以及3GPP中都有應用。

LT碼最初建立在二元刪除信道(BEC)上，其譯碼屬于硬判決譯碼，主流的2種算法是置信傳播(BP)算法和高斯消元(GE)算法。原始的高斯消元并沒有實現實時譯碼，在文獻[7-9]中相關學者進一步提出了可漸進實現的高斯消元算法。針對BP算法譯碼開銷大的問題，有學者提出BP算法與高斯消元結合的方法[10-12]，國內有人提出了增強型BP算法[13]，以及一種BP與最大似然譯碼結合的BPMLE算法[14]。

高斯消元算法是LT碼的一種最大似然譯碼方法，能夠最小化譯碼開銷，但其復雜度也較高。提出一種可以降低復雜度的高斯消元算法，在LT譯碼的過程中，使用該方法進行矩陣化簡，不需要實現階梯化，同時結合BP算法，使其能夠實時漸進的譯碼。

1 LT碼的硬譯碼

1.1 編碼原理

LT編碼器將固定數量的信息符號生成理論上無窮數目的編碼符號。編碼符號的度分布是設計LT碼的關鍵，符號的度，即該符號擁有的連接的數目。度分布可以用多項式表示為

(1)

G·sT=yT。

(2)

1.2譯碼原理

通常假定接收端已知編碼的生成矩陣，那么譯碼就是在接收到編碼符號的情況下，恢復出信息符號的過程。兩大主要方法為BP譯碼和高斯消元(GE)譯碼。

1.2.1 BP譯碼

在接收的編碼符號中，找到一個度數為1的符號yi，將其值賦給唯一相鄰的信息符號sj，即sj=yi，則該信息符號得到恢復，并將對應的這條連接刪除。此后，所有與sj相連的編碼符號與sj異或，并隨后將連接刪除。在這之后，繼續在編碼符號中尋找度數為1的，重復上述步驟，若不存在度為1的編碼符號，則接收端需要更多的編碼符號，將接收到的符號與已經恢復的信息符號異或更新后刪除連接，再按上述步驟進行度數1符號搜索，使BP譯碼能夠繼續進行，直至所有信息符號恢復。

1.2.2 GE譯碼

高斯消元譯碼首先對生成矩陣和接收符號構成的增廣矩陣進行三角化，若成功，則回代方程組可求解出信息符號。三角化是將增廣矩陣轉化為上三角形式，若該過程失敗，說明需要更多的編碼符號，然后三角化需要重新進行。原始的GE失敗后，并不保留處理后的矩陣，實際上，文獻[7]中增量的高斯消元算法(incGE)才是實用的高斯消元譯碼。設信息符號的數目為k，增量高斯消元在剛接收到k個編碼符號后，僅執行一次三角化，將原始的生成矩陣G簡化為G′，若三角化不完全，譯碼失敗，但保留G′。在G′中，“優行”指那些最左方“1”在對角線上的行，“劣行”則是不符合該情況的行。首次三角化中以及之后在接收更多編碼符號時，增量高斯消元通過行變換，盡可能地將劣行轉換為優行。當接收到足夠多的符號時，三角化將完全實現，此時再對方程回代，即可恢復出所有的信息符號。

定義譯碼開銷

ε=1-n/k，

(3)

式中，n為譯碼成功時接收的編碼符號數目。實驗驗證已經表明，對于任意的k，incGE算法的譯碼開銷均明顯大于BP算法，且其開銷隨著k的增大收斂于0的速度更快。在譯碼復雜度方面，BP算法的較低，為O(klb(k))，incGE的復雜度則相當于一次高斯消元，為O(k2)。

1.3 非階梯化高斯消元

本文提出的高斯消元是一種非行階梯化的消除方法，非階梯化高斯消元(NEGE)在BP算法遇到停止集時，將所有未消除連接符號對應的矩陣，進行矩陣簡化，簡化符號之間的連接，使得簡化后的矩陣有再次進行BP譯碼的可能。

（2）高校教師數據知識。根據調查結果顯示：數據基礎知識掌握方面，利用統計數據進行相關知識的教學占比76.6%，經常、偶爾通過書籍等渠道了解或者專門學習數據如何分析占比分別為63.3%與20%；對于數據工具使用情況，60%的高校教師使用數據分析工具超過三個，而Excel、SPSSS 使用率高達63%以上，相反地，SAS、R、Python、Stata 等軟件使用極低，其中最高占比16.7%。從這兩方面來看，內蒙古高校教師使用統計軟件的能力較弱，使用工具較單一。但數據基礎知識方面情況良好，單這一方面可看出，內蒙古高校教師數據知識在逐步積累。

該算法在矩陣層面的實現是：譯碼開始時首先應用BP算法，找到權重為1的行，對應的編碼符號的值將被賦予給其唯一的鄰接信息符號，此后這些行上的1置0，表示連接刪除；而這些新恢復的信息符號，將要與它們的鄰接編碼符號異或，進一步刪除這些連接，即將1置0；然后，將在尋找權重為1的行重復上述步驟。當找不到權重為1的行時，再利用高斯消元，完畢后尋找權重為1的行，進行BP譯碼。若經過上述所有步驟，信息未完全恢復，則接收更多的編碼符號，將接收的符號與已經恢復的編碼符號之間可能存在的連接消除，并更新編碼符號，依上面步驟進行BP和高斯消元的聯合譯碼。非階梯化高斯消元算法如下：

其中，M(i,j)表示M的第i行第j列元素，用“：”表示對矩陣或向量整行、整列的引用。函數isemtpy(·)判斷變量是否為空，為空則返回1，“～”表示邏輯非，’row’代表按行求和，函數size(·)為返回矩陣的行列數，sum(·)為求和函數。

所提的NEGE相比原始的方法在復雜度上有明顯的降低。首先，選取某一行對其他行作消除時，采用了選取權重最小行的策略。在高斯消元過程中，對行的處理是從頂行到底行進行，對列則是從最左至最右。傳統的高斯消元，在選取基準行對其他行做消除時，選取是均勻隨機的。而所提的NEGE則選取權重最低的作為基準，這樣可以降低其他行在消除后的權重，進而減少行操作的次數。其次，由于高斯消元后會應用BP譯碼，因此行階梯的特點可以舍棄。原始的高斯消元使得每行最左方的1依次呈階梯狀，這樣就需要對基準行進行行交換。NEGE在選取基準行后，保持其位置不變，可以避免行交換操作。

NEGE譯碼示例如圖1所示。

圖1 NEGE譯碼示例

以Tanner圖表示符號之間的連接關系，圓形為信息符號，方形為編碼符號。在圖1(a)中，Y1，Y2，Y6是新接收到的符號，S6，S7是已經恢復的信息符號。新符號首先與S6，S7異或更新連接，然后進行BP譯碼直到圖1(b)遇到停止集BP無法繼續。提取剩余連接，進行NEGE如圖1(c)所示。在圖1(d)中，可以觀察到符號之間的連接已經簡化，BP譯碼可以再次展開。

2 仿真結果

不失一般性，令1個符號代表1 bit。仿真信道為二元刪除信道，同樣假設信道刪除率為0。本節給出BP算法、incGE算法以及NEGE算法的仿真結果。度分布采用文獻[4]中的魯棒孤子分布(RSD)，RSD的δ參數設置為0.05,所有結果都在1 000次蒙特卡洛仿真下平均得到。

圖2給出了3種算法的開銷ε與信息符號長度k的關系，且RSD的c參數有3個不同值0.01,0.1,0.5。可以看出，NEGE的譯碼開銷與incGE相同，因為二者都最大限度地利用了生成矩陣。此外，NEGE和incGE隨著k的增大開銷趨于0的收斂速度顯著快于BP算法。在c=0.01及c=0.1的情況下，BP算法2條曲線的差距顯著大于NEGE之間的，且BP算法最上方的曲線在k較小時還出現了波動。因此NEGE算法的性能對度分布的選擇敏感性遠遠小于BP算法的，若選擇NEGE算法，度分布的精細設計可以在較大程度上忽略。

圖2 RSD下不同參數c的開銷

圖3給出了3種算法的復雜度，以異或操作、行交換的總數作為指標，RSD的參數選為δ=0.05，c=0.1。3種算法均在剛接收到符號時就開始譯碼。可以看出，BP算法的復雜度是最低的，與k成線性增長。而incGE的復雜度最高，相比之下，NEGE的復雜度明顯降低。若對于接收方來說，計算能力能夠支持高斯消元的負擔，同時最大限度地降低譯碼開銷，那么提出的NEGE是一個不錯的選擇。

圖3 BP,incGE,NEGE的復雜度

3 結束語

提出了非階梯化的高斯消元算法，在選擇某一行作為基準行對其他行進行消除時，采取了選擇權重最小行的策略，該策略減小了后續行操作的數量，相比原始的高斯消元，復雜度大大減小。當BP算法遇到停止集無法繼續進行時，提取出未處理的符號，進行非階梯化高斯消元，簡化后的連接關系使得再次BP譯碼成為可能。從而對LT碼譯碼，能夠顯著降低譯碼開銷，使得度分布的設計在該算法下居于次要。在接收端計算能力能夠保證的前提下，NEGE算法是一種較好的選擇。