RaptorQ噴泉碼編譯碼算法分析及優化

馬夢宇, 羅長洲, 梁春瑞, 王 杰

(1. 北京控制與電子技術研究所, 北京 100038; 2. 中國航天科工集團二院研究生院, 北京 100854)

0 引 言

噴泉碼作為一種新興的前向糾錯碼,其優勢體現在“無碼率性”[1-2]、“魯棒性”和“獨立于信道刪除概率特性”。噴泉碼的編碼器如源源不斷產生編碼數據包流的“噴泉”,譯碼器接收到一定數量的編碼數據包后,就可以以極高的成功率恢復出源碼信息。從理論上講,編碼端可以源源不斷地產生編碼數據包,而譯碼端沒有固定的接收編碼數據包的數量,所以稱噴泉碼具有無碼率特性。噴泉碼數據結構靈活,可以根據信道狀態調整編碼包生成數量和接收端的實際接收需要,具備很好的魯棒性[3-4]。噴泉碼能否成功譯碼只取決于譯碼端收集到的“噴泉”的數量,與“噴泉”在信道上的損失無關,其獨立于信道刪除概率特性,使噴泉碼能夠自適應于時變信道狀態的變化,在信道狀態未知的數據傳輸[5]和多媒體分發網絡中具備良好的傳輸性能。

噴泉碼設計的初衷是解決刪除信道上的數據分組傳輸問題,隨著研究的逐漸深入,噴泉碼的應用場景也在逐漸拓展。除了刪除信道,噴泉碼在加性高斯白噪聲和衰落信道下也能發揮很好的性能。噴泉碼已經被廣泛應用于各類場景中[6-8]。

自2002年LT(Luby transform)碼被提出,在其基礎上依次出現了Raptor[9-10]碼和RaptorQ[11]碼,并在高通公司的推廣下分別將Raptor碼和RaptorQ碼寫入國際標準RFC5053和RFC6330,噴泉碼的編譯碼算法[12-14]是重要的研究方向之一。由于在實際應用中,噴泉碼的符號長度存在上限,文獻[15]就LT碼的設計及其有限長度進行了分析;度的分布計算同樣影響噴泉碼算法的性能,諸多學者[16-19]對噴泉碼的度分布計算方法展開了研究;文獻[20]推導了以最大似然解碼算法為基礎的Raptor碼解碼失敗概率的上限和下限。

RaptorQ碼是以LT碼和Raptor碼為基礎進一步發展的最新研究成果,針對RaptorQ碼的研究是這3類噴泉碼研究中最少的,整理后發現,RaptorQ碼的性能在噴泉碼中沒有清晰的定位和評估,對于RaptorQ碼復雜度較高這一問題,也沒有相對合理的解決方案。文獻[21]利用降維變換,將需要計算的逆矩陣轉化為維度更小的矩陣求逆,以此簡化RaptorQ碼的譯碼復雜度,但該算法需要在刪除概率較小(小于0.2)的信道中才能發揮作用;文獻[22]提出基于消元方式的編碼算法來規避編碼過程中需要的矩陣乘法,但是其推出的矩陣預先求逆算法僅適用于編碼時A矩陣為方陣的情況,對于算法消耗時間占比很大的譯碼端來說并不適用;文獻[23]提出一種模式選擇解碼算法,需要提前對信道的狀態進行探究,而模式選擇器的設計策略也將影響噴泉碼編譯碼算法的效率,在一定程度上弱化了噴泉碼的自適應能力。

基于上述分析,本文從LT、Raptor及RaptorQ碼的角度,采用理論分析加仿真驗證的方法將三者進行橫向對比,以此對RaptorQ碼的性能和編譯碼復雜程度進行全面的評估。針對RaptorQ碼編譯碼復雜度高的問題,以RFC6330編譯碼方案為基礎,在保證性能不變的前提下,通過固定生成矩陣A,通過提前列變換和去稀疏化對其編譯碼算法進行優化,并通過仿真實驗和對比分析驗證了方法的可行性和有效性。

1 RaptorQ編譯碼算法分析

1.1 LT碼編譯碼算法

LT碼是第一種實用數字噴泉碼,其具體編譯碼過程如下:在每產生一個編碼符號之前,先由度分布函數生成該編碼符號的度d,隨后根據度值,隨機選取d個原始的信息位進行異或運算,運算結果即為所要傳輸的編碼符號。待接收端接收到編碼符號之后,一般采用高斯消元(Gaussian elimination, GE)法譯碼,即GE譯碼算法,將編碼符號與原始信息位之間的關系用矩陣的形式表現出來。由于每個編碼符號通過原始信息位異或生成,對應于生成矩陣,就是在該行相應的位置置1,將原始信息位和接收到的編碼符號以列向量的形式表示出來,就可以得到以下關系式:

G×F=E

(1)

式中:G是生成矩陣,矩陣元素僅由0和1組成;F為原始信息位組成的列向量;E為接收到的編碼符號組成的列向量。譯碼問題轉化為已知G和E,求解線性方程組解出F的問題。采用GE法,將G矩陣轉化為單位矩陣,得到原始信息位的值,即譯碼成功。

從整體的編譯碼算法角度觀察LT噴泉碼,其編譯碼算法較為簡單,計算復雜度與碼長K呈現非線性關系:

O(KlgK)

譯碼失敗的錯誤下限較高,為了較好地覆蓋到所有原始信息,增加成功解碼概率,需要設置一定數量的度值較高的編碼符號,這增加了系統的異或計算次數,一定程度上增加了編譯碼復雜程度。為解決上述LT噴泉碼高誤差下限問題,降低編解碼復雜度并實現線性編解碼,在此基礎上設計增加了預編碼手段,即Raptor碼。

1.2 Raptor碼編譯碼算法

Raptor碼可看作一種級聯編碼方式,是在LT碼的基礎上,增加了預編碼的過程。源碼首先以預編碼的方式生成帶有一部分冗余信息的中間符號,再將中間符號通過弱化的LT編碼產生編碼符號。所謂弱化的LT編碼,是指規避上述LT碼產生高連接度值的編碼符號,盡量弱化由中間符號生成編碼符號過程的度值,這樣做的好處是減少異或計算次數,后果是導致譯碼過程中,由于對中間符號覆蓋度不高,無法完整地恢復所有中間符號,不過未被恢復的中間符號只占一小部分,且中間符號在生成時就具有一部分冗余位,可根據預編碼的糾錯能力,將完整的原始信息從中間符號中恢復出來。Raptor碼以預編碼加弱化的LT編碼形式,加強了噴泉碼的糾錯能力,減少了計算復雜程度,同時實現了線性編解碼,其編解碼算法復雜度為

O(Klg 1/ε)

式中:ε為譯碼冗余。

1.3 RaptorQ碼編譯碼算法

RaptorQ噴泉碼是在Raptor碼基礎上的進一步提升,在預編碼和譯碼算法等方面均采取了更為復雜的計算方式,旨在將譯碼冗余信息減少到最低限度,同時拓展噴泉碼的使用條件:RaptorQ碼最大源符號長度從Raptor碼的8 192 拓展到了56 403;可產生編碼符號數量的上限也從216拓展為224,增加了256倍;生成矩陣A的元素從0和1變為0～256;運算范圍從伽羅華域(Galois field,GF)(2)變為GF(256)。根據有限域GF(q)的分析,有:

q=pn

(2)

式中:p是素數;n是大于0的整數。

在GF(q)的任意有限域上,噴泉碼的解碼性能存在如下理論極限:

(3)

式中:Psuccess為成功解碼概率的理論極限;O為譯碼冗余。

可以看到,在譯碼冗余相同的條件下,q越大,成功解碼概率的理論極限越高。但是編譯碼復雜程度也在隨之增加,即使RaptorQ很巧妙地將高效GF(256)算法和低復雜度GF(2)算法結合起來,盡可能減小GF(256)的輻射范圍,降低編碼時的計算復雜度,譯碼時算法復雜度的急劇增加仍不可避免。采用了優化失活高斯譯碼算法的RaptorQ編譯碼復雜度為O(L2),其中L為RaptorQ碼產生的編碼符號的長度。

1.3.1 RaptorQ的編譯碼流程

圖1為RaptorQ噴泉碼編繹碼的數據流圖。

圖1 RaptorQ編譯碼流程Fig.1 RaptorQ encoding and decoding flowchart

RaptorQ噴泉碼編譯碼步驟分為3步:參數初始化、預編碼和編碼。

首先以補零的方式將K個源符號拓展為K′,該擴展的目的在于最小化編譯碼過程中信息的存儲量,加快編譯碼速度,以K′為輸入,計算得到構建預編碼生成矩陣A的一系列參數。

預編碼階段,A矩陣行列值的數量關系由K′決定,在參數初始化體現,滿足如下關系:

L=S+H+K′=B+S+U+H

(4)

使A矩陣成為L×L的方陣。根據圖2中的RaptorQ譯碼公式,A矩陣代表中間符號C向量與源符號D向量的線性關系,利用A矩陣和源符號向量D兩個已知條件,即可解出中間符號向量C。

圖2 RaptorQ譯碼公式Fig.2 Formula of RaptorQ decoding

中間符號向量C為預編碼階段的輸出,將其成功解碼的前提條件為生成矩陣為列滿秩矩陣。將其進行LT編碼,得到最終輸出的編碼符號,該編碼符號由源碼與修復碼組成。編碼符號的數量N可根據所需的速率和預期的信道丟包概率提前設置。

譯碼是編碼的逆過程,編碼符號經過信道后,譯碼器整理好接收到的編碼符號,再次進行參數初始化和預編碼階段處理,對于譯碼階段的預編碼矩陣RecA,除第3層GENC矩陣的行數外,其他參數與編碼階段生成的矩陣A一致。

在RaptorQ編譯碼中,最核心也是計算復雜度最高的部分是利用A和RecA矩陣通過解線性方程組求取中間符號的這一過程,在RFC6330中采用優化失活GE解碼法,通過將矩陣分塊,將GE過程限定在較小的范圍內,分5個階段將生成矩陣處理為單位矩陣,將中間符號向量和源符號向量進行相應的變換,則變換后的中間符號的值即為源符號的值。接下來以譯碼時M×L的生成矩陣RecA為例,詳述失活解碼GE法。

1.3.2 失活解碼GE法

圖3所示為RaptorQ失活解碼GE法的流程圖。

圖3 RaptorQ失活解碼GE法Fig.3 RaptorQ deactivation decoding GE method

失活解碼GE法共分為5個階段,首先根據非負參數i和u,以及RecA的行列值M、L,將RecA矩陣在概念上劃分為多個子矩陣,進行第一階段(即算法核心階段的操作)由尋找標準行和GE兩部分組成,值得注意的是,高密度奇偶校驗(high density parity check, HDPC)行不在標準行的選取范圍之中,這也是RFC6330設計標準行選取的原因所在,除HDPC行之外的所有行均定義在GF(2)上,選取GF(2)以及非零元素個數最小的行作為GE的標準行,就能最大限度地降低GE的計算次數。在第一階段開始之前,將RecA矩陣復制,設其為X矩陣,直到GE過程之前,保持與RecA矩陣相同的操作。

第二階段是使用Uupper子矩陣對Ulower子矩陣進行GE的過程,將Ulower矩陣的前u行消元為單位矩陣。

由于Uupper子矩陣非零元素較為密集,RFC6330設計第三階段對Uupper子矩陣進行稀疏化,對于在第一階段生成的矩陣X,取其前i行i列的稀疏下三角方陣Xi,與RecA矩陣的前i行進行相乘,將Uupper子矩陣稀疏化。

需要注意的是:

(1) 譯碼算法只是聚焦于RecA矩陣上,對于在RecA矩陣上的行列變換及消元等操作,中間符號向量C和源符號向量D要進行相應的變換;

(2) 不同于基本的矩陣運算,RFC6330中矩陣運算基于有限域GF(256)的運算法則,以異或、查表等操作對應于實數集的加減乘除運算法則。

2 噴泉碼編譯碼算法仿真分析

噴泉碼基于增加冗余位原理來對抗信道干擾,以增加譯碼開銷的方法提高可靠性,所以,在同等條件下,保證相同誤碼率所需要的譯碼開銷數量成為衡量噴泉碼性能的重要指標。從LT碼發展為Raptor碼再到RaptorQ碼的出現,噴泉碼以降低譯碼開銷為核心思想不斷改進和優化,在實現這一核心思想的過程中,很可能造成噴泉碼編譯碼算法復雜程度的提高,造成噴泉碼性能和系統處理時延的相互制約。

為對比驗證3種編譯碼算法的性能優劣,基于Intel(R) Core(TM) i5-3470 CPU @ 3.20 GHz～3.2 GHz和Matlab R2016b環境(本文實驗均以此環境為背景)進行信道隨機刪除,刪除概率為0.1;試驗次數為105;碼長K=128;譯碼冗余變化的仿真試驗,實驗結果如圖4所示。

圖4 譯碼冗余不同時3種算法的誤碼率對比Fig.4 Comparison of bit error rate of three algorithms with different decoding redundancy

噴泉碼最耗時的操作為對生成矩陣求逆,據統計,碼長K=4時,求逆過程耗時占用了整個編解碼過程耗時的99%,碼長K=1 024時,求逆過程耗時占用了整個編解碼過程耗時的95%。而在求逆過程中,異或運算是運行次數最多、最核心的運算。為對比驗證3種算法的編譯碼復雜程度,設置信道隨機刪除概率為0.1;譯碼冗余為0.15;試驗次數為105;通過碼長從128～2 048變化的仿真試驗,統計3種算法程序的總異或次數。仿真實驗結果如圖5所示。

圖5 碼長不同時3種算法的總異或次數對比Fig.5 Comparison of total XOR times of three algorithms with different code length

為進一步對比驗證3種算法的編譯碼復雜程度,進行信道隨機刪除概率為0.1、譯碼冗余為0.15、試驗次數為105、碼長從128～2 048變化的仿真試驗。統計3種算法的平均編解碼時長,實驗結果如圖6所示。

圖6 碼長不同時3種算法的編譯碼時間對比Fig.6 Comparison of encoding and decoding time of three algorithms with different code lengths

從圖4可以看出,在相同的譯碼冗余條件下,LT編碼的系統誤碼率最高,若達到相同的誤碼率,采用LT編碼所需的譯碼冗余是最多的,且其誤差下限較高;其次是Raptor碼;所需譯碼冗余最少的為RaptorQ碼。仿真數據表明,譯碼冗余在0.11以上時,RaptorQ碼就可以達到99%以上的成功解碼概率。

從圖5可以看出,RaptorQ碼的異或計算次數高于Raptor碼和LT碼,其次為LT碼,最次為Raptor碼。這是因為Raptor碼采用預編碼方式,規避了高連接度值的情況,減少了系統的總異或次數。RaptorQ碼對碼長進行了0拓展處理以及對生成矩陣的元素進行了改變,增加了碼長以及生成矩陣維度,進而增加了編譯碼過程中的總異或次數。

從圖6可以看出,在碼長相同時,RaptorQ碼的編譯碼時間遠遠高于LT碼和Raptor碼,這一結論與理論分析一致,三者的編譯碼復雜度依次為:O(KlgK)、O(Klg 1/ε)、O(L2)。在碼長K增加時,RaptorQ碼耗時曲線上升幅度最大,編譯碼耗時急劇增加。另一方面,RaptorQ中的異或運算的元素為GF(256)域中的元素,異或運算時間遠遠高于GF(2)域中的元素異或運算時間,以至于相比于LT碼和Raptor碼,RaptorQ碼的編譯碼耗時與二者存在數量級的差距。三者比較,編譯碼用時最少的是Raptor算法,相同條件下Raptor噴泉碼較LT碼成功譯碼所需的譯碼冗余更少,且編譯碼耗時更少,是各方面都較為成熟的算法。RaptorQ碼更像雙刃劍,在追求性能極致的同時,編譯碼復雜度犧牲最大。

由于在信道刪除的情況下,譯碼端需要接收K個編碼符號和額外的譯碼冗余(修復符號)才能成功解碼,為進一步驗證RaptorQ碼的性能,使用3種算法分別進行刪除概率為0.1、0.3、0.5,碼長為32、512、1024的仿真試驗;設置譯碼端收到的譯碼冗余從0開始逐漸增加,直到譯碼端收到K個編碼符號加此譯碼冗余后,進行105次試驗,直至平均誤碼率小于5×10-5時停止,此時認為排除信道隨機刪除的不確定影響,噴泉碼基本實現無誤碼。由于刪除概率為0.1、0.3和0.5所取得的試驗結果一致,選取刪除概率為0.1的實驗結果如圖7～圖9所示。

圖7 K=32時3種算法所需譯碼冗余Fig.7 Redundancy of decoding required by three algorithms when K=32

圖8 K=512時3種算法所需譯碼冗余Fig.8 Redundancy of decoding required by three algorithms when K=512

圖9 K=1 024時3種算法所需譯碼冗余Fig.9 Redundancy of decoding required by three algorithms when K=1 024

根據實驗結果所示:同等條件LT碼需要6～9個譯碼冗余才能基本實現無誤碼解碼,Raptor碼需要2～4個譯碼,而RaptorQ碼僅需1個譯碼冗余,就能實現極高概率的成功解碼。

排除仿真實驗的不確定性概率,可以看出,無論是LT碼、Raptor碼或是RaptorQ碼,在信道刪除概率為0.1、0.3、0.5以及碼長為32、512、1 024條件下成功解碼所需的譯碼冗余幾乎相同,說明噴泉碼的解碼性能與信道刪除概率無關,與碼長K幾乎無關,驗證了噴泉碼的“獨立于信道刪除概率特性”。

3 RaptorQ碼編譯碼算法優化

根據仿真及理論分析,RaptorQ噴泉碼是性能最好的噴泉碼,但也是編譯碼復雜度最高的噴泉碼,在RFC6330設計的RaptorQ噴泉碼編譯碼算法基礎上,基于失活解碼GE法,提出一個優化版本,針對一部分編解碼步驟進行改進。

(1) 固定生成矩陣

第1節詳細闡述了RaptorQ碼的編譯碼流程,發現預編碼生成矩陣A僅由參數K決定;譯碼生成矩陣RecA由K以及接收到的編碼符號數量決定,RecA矩陣與A矩陣僅在第三層是不同的,前兩層完全一致。在實際應用背景下,數據傳輸的長度K都是提前設置好的,這也就意味著在編譯過程中可以提前固定A矩陣以及RecA矩陣的前兩層,節省生成時間。

(2) 提前列變換

研究表明,在整個噴泉碼編譯碼算法中,根據生成矩陣和原始信息位求解中間符號的過程是最耗時的操作,將占用整個過程92%～95%的時間,所以優化的重點也聚焦于譯碼過程,如圖10所示。譯碼過程的第一階段通過選擇標準行和GE法實現,最終形式是在RecA的左上角形成一個單位矩陣。仔細觀察生成矩陣的格式,矩陣第一層在G_LDPC,1,G_LDPC,2之間是單位矩陣IS。在選取標準行之前,提前進行列變換,將單位矩陣IS所在列移到生成矩陣的最前方,并將單位矩陣IS固定為前S個標準行,就可以省去S個掃描矩陣行列變換尋找標準行的過程。

圖10 提前列變換Fig.10 Advance column transformation

(3) 去稀疏化

為將Uupper子矩陣稀疏化,RFC6330采取將Xi矩陣與其相乘的方法。X矩陣由生成矩陣復制而來,需要與生成矩陣進行同樣的標準行選擇等復雜計算;其次,采用Xi矩陣稀疏化的過程需要用到矩陣乘法,而且破壞了原生成矩陣左上角單位矩陣的格式,需要在第五階段再次消元,這些都增加了譯碼過程的計算量。在第二階段結束時,生成矩陣中Ulower子矩陣已經化為單位矩陣,所以去掉稀疏化這一步驟,直接用單位矩陣Iu將Uupper子矩陣消元為0矩陣,將生成矩陣直接轉化為單位矩陣,將原譯碼方案的五個階段也縮減為三個階段,在一定程度上減少了計算量,優化后的譯碼流程如圖11所示。

圖11 優化后的譯碼流程Fig.11 Optimized decoding process

4 編譯碼算法優化前后仿真驗證

為對比驗證優化前后RaptorQ編譯碼算法的性能變化,進行信道刪除概率為0.1、試驗次數為105、碼長K=128、譯碼冗余變化的仿真試驗,實驗結果如圖12所示。

圖12 優化前后算法誤碼率對比Fig.12 Comparison of bit error rate before and after optimization

為對比驗證優化前后RaptorQ碼編譯碼復雜程度,進行信道刪除概率為0.1、譯碼冗余為0.15、試驗次數為105、碼長從128～2 048變化的仿真試驗。統計3種算法的總異或次數,實驗結果如圖13所示。

圖13 優化前后算法異或次數對比Fig.13 Comparison of XOR times before and after optimization

為對比驗證優化前后RaptorQ碼編譯碼復雜程度,進行信道刪除概率為0.1、譯碼冗余為0.15、試驗次數為105、碼長從128～2 048變化的仿真試驗。統計3種算法的平均編解碼時長,實驗結果如圖14所示。

圖14 優化前后算法編譯碼時間對比Fig.14 Comparison of encoding and decoding time before and after algorithm optimization

圖12實驗結果表明,優化前后RaptorQ碼在譯碼冗余相同時,系統誤碼率基本一致,排除信道刪除的不確定性影響,說明優化后RaptorQ碼沒有影響原RaptorQ碼的解碼性能;由圖13、圖14得知,優化后的RaptorQ編譯碼流程中的異或運算次數有所減少,同等條件下優化后RaptorQ碼所需的編譯碼時間相比原編譯碼耗時減少,其編譯碼復雜程度得到了一定程度的優化。不過將4種算法編譯碼耗時進行對比,發現即使優化后,RaptorQ碼的耗時仍大于Raptor碼,其編譯碼算法仍存在改進的空間。在實際應用中,可根據系統對性能和編譯碼復雜度的需求選擇合適的算法。

5 結 論

針對RaptorQ噴泉碼性能和編譯碼復雜度的評估不夠全面清晰的問題,本文在RaptorQ的編譯碼算法層面,通過理論論證和仿真對比的方式對RaptorQ噴泉碼進行全面分析,并針對RaptorQ碼編譯碼復雜度過高這一弊端,以RFC6330所設計的RaptorQ碼編譯碼算法為基礎,通過固定生成矩陣、提前列變換和去稀疏化,提出一種RaptorQ碼編譯碼算法的優化版本。通過仿真試驗得知,該優化版本在保持原有RaptorQ噴泉碼性能的基礎上,簡化了編譯碼復雜度,減少了算法中重要運算的計算量,降低了系統處理時間,其有效性和可行性得到了驗證。