RaptorQ噴泉碼編譯碼算法分析及優(yōu)化

馬夢(mèng)宇, 羅長(zhǎng)洲, 梁春瑞, 王 杰

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

0 引 言

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

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

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

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

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

1 RaptorQ編譯碼算法分析

1.1 LT碼編譯碼算法

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

G×F=E

(1)

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

從整體的編譯碼算法角度觀察LT噴泉碼,其編譯碼算法較為簡(jiǎn)單,計(jì)算復(fù)雜度與碼長(zhǎng)K呈現(xiàn)非線性關(guān)系:

O(KlgK)

譯碼失敗的錯(cuò)誤下限較高,為了較好地覆蓋到所有原始信息,增加成功解碼概率,需要設(shè)置一定數(shù)量的度值較高的編碼符號(hào),這增加了系統(tǒng)的異或計(jì)算次數(shù),一定程度上增加了編譯碼復(fù)雜程度。為解決上述LT噴泉碼高誤差下限問題,降低編解碼復(fù)雜度并實(shí)現(xiàn)線性編解碼,在此基礎(chǔ)上設(shè)計(jì)增加了預(yù)編碼手段,即Raptor碼。

1.2 Raptor碼編譯碼算法

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

O(Klg 1/ε)

式中:ε為譯碼冗余。

1.3 RaptorQ碼編譯碼算法

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

q=pn

(2)

式中:p是素?cái)?shù);n是大于0的整數(shù)。

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

(3)

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

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

1.3.1 RaptorQ的編譯碼流程

圖1為RaptorQ噴泉碼編繹碼的數(shù)據(jù)流圖。

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

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

首先以補(bǔ)零的方式將K個(gè)源符號(hào)拓展為K′,該擴(kuò)展的目的在于最小化編譯碼過程中信息的存儲(chǔ)量,加快編譯碼速度,以K′為輸入,計(jì)算得到構(gòu)建預(yù)編碼生成矩陣A的一系列參數(shù)。

預(yù)編碼階段,A矩陣行列值的數(shù)量關(guān)系由K′決定,在參數(shù)初始化體現(xiàn),滿足如下關(guān)系:

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

(4)

使A矩陣成為L(zhǎng)×L的方陣。根據(jù)圖2中的RaptorQ譯碼公式,A矩陣代表中間符號(hào)C向量與源符號(hào)D向量的線性關(guān)系,利用A矩陣和源符號(hào)向量D兩個(gè)已知條件,即可解出中間符號(hào)向量C。

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

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

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

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

1.3.2 失活解碼GE法

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

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

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

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

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

需要注意的是:

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

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

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

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

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

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

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

圖5 碼長(zhǎng)不同時(shí)3種算法的總異或次數(shù)對(duì)比Fig.5 Comparison of total XOR times of three algorithms with different code length

為進(jìn)一步對(duì)比驗(yàn)證3種算法的編譯碼復(fù)雜程度,進(jìn)行信道隨機(jī)刪除概率為0.1、譯碼冗余為0.15、試驗(yàn)次數(shù)為105、碼長(zhǎng)從128～2 048變化的仿真試驗(yàn)。統(tǒng)計(jì)3種算法的平均編解碼時(shí)長(zhǎng),實(shí)驗(yàn)結(jié)果如圖6所示。

圖6 碼長(zhǎng)不同時(shí)3種算法的編譯碼時(shí)間對(duì)比Fig.6 Comparison of encoding and decoding time of three algorithms with different code lengths

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

從圖5可以看出,RaptorQ碼的異或計(jì)算次數(shù)高于Raptor碼和LT碼,其次為L(zhǎng)T碼,最次為Raptor碼。這是因?yàn)镽aptor碼采用預(yù)編碼方式,規(guī)避了高連接度值的情況,減少了系統(tǒng)的總異或次數(shù)。RaptorQ碼對(duì)碼長(zhǎng)進(jìn)行了0拓展處理以及對(duì)生成矩陣的元素進(jìn)行了改變,增加了碼長(zhǎng)以及生成矩陣維度,進(jìn)而增加了編譯碼過程中的總異或次數(shù)。

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

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

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

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

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

根據(jù)實(shí)驗(yàn)結(jié)果所示:同等條件LT碼需要6～9個(gè)譯碼冗余才能基本實(shí)現(xiàn)無誤碼解碼,Raptor碼需要2～4個(gè)譯碼,而RaptorQ碼僅需1個(gè)譯碼冗余,就能實(shí)現(xiàn)極高概率的成功解碼。

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

3 RaptorQ碼編譯碼算法優(yōu)化

根據(jù)仿真及理論分析,RaptorQ噴泉碼是性能最好的噴泉碼,但也是編譯碼復(fù)雜度最高的噴泉碼,在RFC6330設(shè)計(jì)的RaptorQ噴泉碼編譯碼算法基礎(chǔ)上,基于失活解碼GE法,提出一個(gè)優(yōu)化版本,針對(duì)一部分編解碼步驟進(jìn)行改進(jìn)。

(1) 固定生成矩陣

第1節(jié)詳細(xì)闡述了RaptorQ碼的編譯碼流程,發(fā)現(xiàn)預(yù)編碼生成矩陣A僅由參數(shù)K決定;譯碼生成矩陣RecA由K以及接收到的編碼符號(hào)數(shù)量決定,RecA矩陣與A矩陣僅在第三層是不同的,前兩層完全一致。在實(shí)際應(yīng)用背景下,數(shù)據(jù)傳輸?shù)拈L(zhǎng)度K都是提前設(shè)置好的,這也就意味著在編譯過程中可以提前固定A矩陣以及RecA矩陣的前兩層,節(jié)省生成時(shí)間。

(2) 提前列變換

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

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

(3) 去稀疏化

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

圖11 優(yōu)化后的譯碼流程Fig.11 Optimized decoding process

4 編譯碼算法優(yōu)化前后仿真驗(yàn)證

為對(duì)比驗(yàn)證優(yōu)化前后RaptorQ編譯碼算法的性能變化,進(jìn)行信道刪除概率為0.1、試驗(yàn)次數(shù)為105、碼長(zhǎng)K=128、譯碼冗余變化的仿真試驗(yàn),實(shí)驗(yàn)結(jié)果如圖12所示。

圖12 優(yōu)化前后算法誤碼率對(duì)比Fig.12 Comparison of bit error rate before and after optimization

為對(duì)比驗(yàn)證優(yōu)化前后RaptorQ碼編譯碼復(fù)雜程度,進(jìn)行信道刪除概率為0.1、譯碼冗余為0.15、試驗(yàn)次數(shù)為105、碼長(zhǎng)從128～2 048變化的仿真試驗(yàn)。統(tǒng)計(jì)3種算法的總異或次數(shù),實(shí)驗(yàn)結(jié)果如圖13所示。

圖13 優(yōu)化前后算法異或次數(shù)對(duì)比Fig.13 Comparison of XOR times before and after optimization

為對(duì)比驗(yàn)證優(yōu)化前后RaptorQ碼編譯碼復(fù)雜程度,進(jìn)行信道刪除概率為0.1、譯碼冗余為0.15、試驗(yàn)次數(shù)為105、碼長(zhǎng)從128～2 048變化的仿真試驗(yàn)。統(tǒng)計(jì)3種算法的平均編解碼時(shí)長(zhǎng),實(shí)驗(yàn)結(jié)果如圖14所示。

圖14 優(yōu)化前后算法編譯碼時(shí)間對(duì)比Fig.14 Comparison of encoding and decoding time before and after algorithm optimization

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

5 結(jié) 論

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