一種高吞吐率的系統(tǒng)Raptor碼并行譯碼方法

任雁鵬，管 武，梁利平

(1. 中國科學(xué)院微電子研究所 北京 朝陽區(qū) 100029；2. 中國科學(xué)院大學(xué)微電子學(xué)院 北京 懷柔區(qū) 100049)

數(shù)字噴泉碼技術(shù)以其高性能的糾錯能力，得到廣泛的青睞。其中的低復(fù)雜度碼型——系統(tǒng)Raptor碼[1-2]，更是廣泛應(yīng)用于無線傳輸領(lǐng)域[3-5]。系統(tǒng)Raptor碼在編碼時(shí)，對源數(shù)據(jù)包增加少量冗余包；在譯碼時(shí)，通過接收到的源數(shù)據(jù)包和冗余包糾正傳輸過程中的丟包，實(shí)現(xiàn)數(shù)據(jù)恢復(fù)。這種以包為單位的糾錯方法，具有較高的吞吐率和較低的復(fù)雜度，在高速數(shù)據(jù)傳輸中優(yōu)勢明顯。

隨著超高清、3D視頻以及海量數(shù)據(jù)的高速傳輸，未來無線數(shù)據(jù)傳輸吞吐率將達(dá)到1 Gbps以上。然而，當(dāng)前3GPP標(biāo)準(zhǔn)(3rdgeneration partnership project)中采用的系統(tǒng)Raptor碼技術(shù)，速率還在100 Mbps量級，已經(jīng)無法滿足高速傳輸?shù)男枨?。需要更高速率的系統(tǒng)Raptor碼編碼譯碼技術(shù)。

目前，許多學(xué)者都在進(jìn)行系統(tǒng)Raptor碼的改進(jìn)和優(yōu)化。文獻(xiàn)[6]發(fā)現(xiàn)系統(tǒng)Raptor碼運(yùn)算耗時(shí)最大的部分為譯碼中的高斯消元運(yùn)算，其占整個(gè)譯碼總時(shí)間的91%以上；并提出優(yōu)化失活譯碼高斯消元算法，將傳統(tǒng)高斯消元算法中矩陣求逆的計(jì)算復(fù)雜度由O(L3)降低至O(L)，其中L為與源數(shù)據(jù)包數(shù)量相關(guān)的參數(shù)。矩陣遞歸求逆譯碼算法[7]和矩陣降維快速譯碼算法[8]基于系統(tǒng)Raptor碼的部分碼——系統(tǒng)RaptorQ碼，實(shí)現(xiàn)了軟件優(yōu)化，但速率較低。文獻(xiàn)[9]采用CPU(central processing unit)+GPU(graphics processing unit)的模式進(jìn)行系統(tǒng)Raptor碼并行加速，使無線數(shù)據(jù)傳輸吞吐率達(dá)到21 Mbps。文獻(xiàn)[10-11]則采用FPGA(filed programmable gate array)進(jìn)行高斯消元運(yùn)算的硬件加速，進(jìn)一步提升吞吐率。

上述方案針對高斯消元運(yùn)算的改進(jìn)和優(yōu)化，使譯碼性能得到了提升。但是，其譯碼過程中，高斯消元運(yùn)算需要譯碼出所有源數(shù)據(jù)包，譯碼運(yùn)算復(fù)雜度大、串行依賴度高，無法大幅降低譯碼延時(shí)，提高譯碼吞吐率。實(shí)際上，數(shù)據(jù)傳輸中僅存在少量丟包；如果能夠只對丟失的少量數(shù)據(jù)包進(jìn)行譯碼，則可大大降低譯碼復(fù)雜度。本文經(jīng)過對譯碼過程的分解，提出了一種低復(fù)雜度的降維譯碼算法。該算法僅對丟失的數(shù)據(jù)包進(jìn)行譯碼，并采用全并行的硬件加速結(jié)構(gòu)，實(shí)現(xiàn)低延時(shí)高吞吐率的系統(tǒng)Raptor碼譯碼器。

1 系統(tǒng)Raptor碼編譯碼原理

系統(tǒng)Raptor碼的編譯碼原理如圖1所示。發(fā)送端，編碼器對源數(shù)據(jù)分別進(jìn)行預(yù)編碼和LT(Luby transform)編碼，生成編碼數(shù)據(jù)。編碼數(shù)據(jù)包含所有源數(shù)據(jù)和少量冗余數(shù)據(jù)。編碼數(shù)據(jù)經(jīng)物理信道發(fā)送給接收端。物理信道呈刪除信道的特征，會有少量編碼數(shù)據(jù)的丟失。接收端，譯碼器對接收到的數(shù)據(jù)包進(jìn)行預(yù)譯碼和LT譯碼，糾正信道中丟失的數(shù)據(jù)包，恢復(fù)出所有的源數(shù)據(jù)包[1]。

圖1 系統(tǒng)Raptor碼編譯碼原理圖

1.1 系統(tǒng)Raptor碼編碼

系統(tǒng)Raptor碼編碼時(shí)，首先，源數(shù)據(jù)包T=[t0, t1,…,tK-1]和零矩陣Z1×(S+H)構(gòu)成預(yù)編碼輸入矢量D=[Z1×(S+H), T]T，其中K為源數(shù)據(jù)包的數(shù)量，S和H分別為預(yù)編碼參數(shù)，由K計(jì)算得出。輸入矢量D與預(yù)編碼矩陣的逆矩陣A-1進(jìn)行二進(jìn)制乘法，生成L個(gè)預(yù)編碼碼字C=[c0, c1,…, cL-1]T，其中L=K+S+H：

然后，進(jìn)行LT編碼，生成編碼碼字E=[e0, e1, …,eN-1]T：

式中，GLT是一個(gè)N×L的矩陣，N＞K；碼字E包含K個(gè)源數(shù)據(jù)包和N－K個(gè)冗余包。

1.2 系統(tǒng)Raptor碼譯碼

接收端，首先進(jìn)行預(yù)譯碼。譯碼端接收到Nr個(gè)碼字E′=[e′0,e′1,…,e′Nr-1](K＜Nr≤N)。E′和零矩陣Z1×(S+H)構(gòu)成預(yù)譯碼輸入矢量D′=[Z1×(S+H), E′]T。根據(jù)接收碼字的ESI(encoding symbol ID，編碼符號索引號)，重建與E′對應(yīng)的預(yù)譯碼矩陣A′M×L，其中M=Nr+S+H。A′M×L的行數(shù)M跟列數(shù)L不相等，無法進(jìn)行求逆運(yùn)算。在計(jì)算預(yù)譯碼碼字C'=[c′0, c′1,…, c′L-1]T時(shí)，需通過高斯消元法進(jìn)行運(yùn)算：

然后，進(jìn)行LT譯碼，得到所有源數(shù)據(jù)包T：

式中，GL′T是一個(gè)K×L的矩陣，根據(jù)已接收冗余包的ESI構(gòu)建。

傳統(tǒng)系統(tǒng)Raptor碼的譯碼結(jié)構(gòu)如圖2所示。接收端首先接收編碼碼字，并根據(jù)ESI構(gòu)建 AM′×L和GL′T。然后執(zhí)行高斯消元的預(yù)譯碼和LT譯碼，得到所有源數(shù)據(jù)包。預(yù)譯碼和LT譯碼串行執(zhí)行。

圖2 系統(tǒng)Raptor碼譯碼串行執(zhí)行結(jié)構(gòu)

在譯碼過程中，高斯消元需經(jīng)過逐行列的遞進(jìn)處理，串行依賴性高，運(yùn)算復(fù)雜度為O(L3)[12]。即使采用硬件加速，也只能對局部運(yùn)算并行實(shí)現(xiàn)，降低譯碼延時(shí)的效果有限。而且隨著K的增大，高斯消元運(yùn)算的復(fù)雜度大幅增長，嚴(yán)重影響譯碼延時(shí)和吞吐率。

2 系統(tǒng)Raptor碼降維譯碼算法

傳統(tǒng)系統(tǒng)Raptor碼譯碼延時(shí)大，無法滿足未來無線傳輸高吞吐率的需求。在實(shí)際中，接收數(shù)據(jù)僅存在少量丟包。只要譯碼出丟包數(shù)據(jù)，即可完成糾錯。本節(jié)對傳統(tǒng)系統(tǒng)Raptor碼譯碼算法進(jìn)行分解，結(jié)合系統(tǒng)Raptor碼編碼的已知矩陣，提出低復(fù)雜度的降維譯碼方案，降低譯碼延時(shí)。

根據(jù)式(1)與式(2)，系統(tǒng)Raptor碼的編碼可表示為：

經(jīng)過刪除信道丟包后，接收端共收到Nr個(gè)編碼包，其中包含Kr(Kr≤K)個(gè)源數(shù)據(jù)包Tr=[t′0, t′1,…,t′Kr-1]和Nr-Kr個(gè)冗余包R=[r0, r1,…, rNr-Kr-1]。丟失的K-Kr個(gè)源數(shù)據(jù)包記為Tx=[tx0, tx1,…, txK-Kr-1]。

在式(5)中，當(dāng)有丟包時(shí)，實(shí)際接收的數(shù)據(jù)包構(gòu)成E ′。根據(jù)實(shí)際接收冗余包的ESI重新構(gòu)建LT矩陣為GLT″。輸入矢量Drx由零矩陣Z(S+H)×1，TrT和TxT構(gòu)成，其中Tr和Tx中的各元素根據(jù)ESI置于Drx的相應(yīng)位置。式(5)變換為：

式中，GL′′T是一個(gè)Nr×L的矩陣；Drx是一個(gè)L×1的矩陣。

式(6)對輸入矢量Drx中的源數(shù)據(jù)包進(jìn)行分解，拆分成兩個(gè)輸入矢量Dr0和D0x。Dr0和D0x都是L×1的矩陣。Dr0包含所有已接收的源數(shù)據(jù)包，其中丟包的地址用0填充。D0x為待求的丟包矩陣，D0x中對應(yīng)已接收數(shù)據(jù)包的地址都為0。式(6)分解為：

進(jìn)一步變換，得出系統(tǒng)Raptor碼的降維譯碼公式為：

當(dāng)網(wǎng)絡(luò)丟包率較低時(shí)，丟包數(shù)量遠(yuǎn)小于源數(shù)據(jù)包數(shù)量K。D0x中待求的丟包元素很少，求解D0x可實(shí)現(xiàn)系統(tǒng)Raptor碼的降維運(yùn)算。另外，在式(8)的運(yùn)算中，使用預(yù)編碼逆矩陣A-1替代預(yù)譯碼矩陣A′M×L，避免了對A′M×L的高斯消元運(yùn)算，大幅降低運(yùn)算復(fù)雜度和譯碼延時(shí)。

對式(8)的各項(xiàng)進(jìn)一步分解：

其中：

由式(9)可以看出，根據(jù)實(shí)際接收的數(shù)據(jù)E′、參數(shù)A″和Y，即可求解出丟失的數(shù)據(jù)D0x。在譯碼過程中，對于給定的K值，A-1為已知矩陣；對于A″和Y，可根據(jù)已接收的源數(shù)據(jù)包Dr0和冗余包進(jìn)行并行運(yùn)算得到。

經(jīng)過對傳統(tǒng)系統(tǒng)Raptor碼算法的分解，僅對丟失的數(shù)據(jù)包進(jìn)行譯碼，實(shí)現(xiàn)降維運(yùn)算。運(yùn)算中使用已知的預(yù)編碼矩陣A-1替換原始的預(yù)譯碼矩陣A′M×L，避免了復(fù)雜的高斯消元運(yùn)算。實(shí)現(xiàn)了低復(fù)雜度的降維譯碼，降低了譯碼延時(shí)。

3 系統(tǒng)Raptor碼降維并行譯碼實(shí)現(xiàn)

結(jié)合系統(tǒng)Raptor碼的降維譯碼算法，本節(jié)給出低延時(shí)的降維并行譯碼結(jié)構(gòu)，如圖3所示。譯碼主要包括3個(gè)運(yùn)算模塊：源數(shù)據(jù)包處理模塊、冗余包處理模塊和丟包計(jì)算模塊。源數(shù)據(jù)包處理模塊對式(12)進(jìn)行運(yùn)算。根據(jù)已接收的源數(shù)據(jù)包，計(jì)算得出矩陣X中的元素。冗余包處理模塊根據(jù)已接收的冗余包構(gòu)建LT譯碼矩陣GL′′T，并計(jì)算式(10)和式(11)中 ′′A和Y中的元素。然后根據(jù)式(9)計(jì)算丟包D0x，完成整個(gè)譯碼過程。在該結(jié)構(gòu)中，所有接收到的源數(shù)據(jù)包和冗余包并行處理，降低運(yùn)算延時(shí)，提高譯碼吞吐率。

圖3 系統(tǒng)Raptor碼降維并行譯碼結(jié)構(gòu)

根據(jù)圖3的降維并行譯碼結(jié)構(gòu)，設(shè)計(jì)系統(tǒng)Raptor碼的全并行硬件結(jié)構(gòu)，如圖4所示。在系統(tǒng)Raptor碼中，對于給定K值，其A-1為確定的，可以將A-1預(yù)先存儲在寄存器中。冗余包處理模塊處理接收到的冗余包，源數(shù)據(jù)包處理模塊處理接收到的源數(shù)據(jù)包，最后計(jì)算丟包。所有接收的數(shù)據(jù)包存入寄存器中。下面對各模塊的運(yùn)算做具體說明。

圖4 系統(tǒng)Raptor碼全并行降維譯碼硬件結(jié)構(gòu)

3.1 源數(shù)據(jù)包處理模塊

首先將接收數(shù)據(jù)包根據(jù)ESI存儲到E′的對應(yīng)位置。發(fā)送端發(fā)送完一組數(shù)據(jù)后，接收端根據(jù)ESI查詢源數(shù)據(jù)。如果全部接收則不需譯碼；如果存在丟包，則保存丟包的ESI并等待恢復(fù)。

然后利用接收的源數(shù)據(jù)包計(jì)算矩陣X。根據(jù)接收包的ESI查找A-1對應(yīng)的矩陣行，將A-1與接收包進(jìn)行與和異或運(yùn)算，得出X中該ESI對應(yīng)的值。所有源數(shù)據(jù)包的運(yùn)算并行執(zhí)行，降低譯碼延時(shí)。

3.2 冗余包處理模塊

根據(jù)冗余包的ESI查找生成矩陣表GLT，將GLT中ESI對應(yīng)的行組合在一起重新構(gòu)建LT譯碼矩陣GL′T。然后根據(jù)式(10)和式(11)計(jì)算 A ′ 和Y。 GL′T為稀疏矩陣，A-1和 GL′T矩陣都為0～1矩陣。在硬件實(shí)現(xiàn)中，將 GL′T矩陣中1對應(yīng)的地址與A-1中的值進(jìn)行與和異或運(yùn)算，計(jì)算出譯碼逆矩陣 A ′ 。同理， GL′T與矩陣X進(jìn)行運(yùn)算得到矩陣Y。

該結(jié)構(gòu)可以對所有冗余包并行處理，不需采用串行處理的模式，這樣就避免了類似高斯消元中逐行列串行處理的耗時(shí)。

3.3 丟包計(jì)算模塊

接收端收到Nr個(gè)接收包時(shí)，查詢ESI并確定丟包位置，計(jì)算丟包。根據(jù)式(9)，使用矩陣Y、 A′′和E′計(jì)算丟包矩陣D0x。

在系統(tǒng)Raptor碼全并行的降維譯碼硬件結(jié)構(gòu)中，所有已接收的源數(shù)據(jù)包和冗余包并行運(yùn)算，源數(shù)據(jù)包處理模塊和冗余包處理模塊并行執(zhí)行，可以在很少的時(shí)鐘周期內(nèi)計(jì)算出所有丟包，大幅降低了譯碼延時(shí)，提高譯碼吞吐率。

4 性能仿真及比較

結(jié)合本文提出的全并行降維譯碼方案，在Xilinx Kintex-7系列的410T FPGA芯片實(shí)現(xiàn)系統(tǒng)Raptor碼譯碼器。源數(shù)據(jù)包數(shù)量K取216，網(wǎng)絡(luò)丟包率為10-2量級，單個(gè)數(shù)據(jù)包的位寬W為4 Byte。采用Xilinx軟件平臺進(jìn)行硬件綜合和功耗估計(jì)，結(jié)果如表1所示。其中邏輯單元需67 539個(gè)，占芯片總資源的26.5%，最高運(yùn)行時(shí)鐘為128.2 MHz，功耗為1 155 mW。

表1 系統(tǒng)Raptor碼譯碼器的硬件開銷與性能

4.1 譯碼延時(shí)比較

在本文提出的降維譯碼方案中，當(dāng)K為216時(shí)，根據(jù)網(wǎng)絡(luò)丟包率得出編碼包數(shù)N為230。經(jīng)仿真，對源數(shù)據(jù)包和冗余包的并行處理，最多僅需N個(gè)時(shí)鐘周期。對丟包的計(jì)算，僅需6個(gè)時(shí)鐘周期。即完成一次系統(tǒng)Raptor碼譯碼共需N+6個(gè)時(shí)鐘周期。

與之相比，如表2所示。文獻(xiàn)[11]的譯碼器采用圖2的串行譯碼結(jié)構(gòu)。源數(shù)據(jù)包數(shù)量K為12，需延時(shí)79個(gè)時(shí)鐘周期完成高斯消元運(yùn)算和LT譯碼，而且隨著K的增大，譯碼延時(shí)大幅增長。本文在K取12時(shí)，根據(jù)丟包率計(jì)算N為14，僅需20個(gè)時(shí)鐘周期可完成譯碼。而且本文的譯碼延時(shí)隨K的變化很小，有效降低了譯碼延時(shí)。

表2 系統(tǒng)Raptor碼譯碼延時(shí)比較

4.2 傳輸吞吐率比較

結(jié)合上邊的仿真結(jié)果，當(dāng)系統(tǒng)運(yùn)行時(shí)鐘fClk取128.2 MHz時(shí)，每秒可以完成的系統(tǒng)Raptor碼譯碼次數(shù)S為：

則數(shù)據(jù)吞吐率為：式中，W為每個(gè)源數(shù)據(jù)包的字節(jié)數(shù)。本文采用W為4字節(jié)的Raptor碼，譯碼數(shù)據(jù)吞吐率可達(dá)3.75 Gbps。

本文的硬件方案與相關(guān)文獻(xiàn)的硬件加速方案的性能比較結(jié)果如表3所示。其中文獻(xiàn)[9]采用3 GHz的i7 CPU與732 MHz的GPU聯(lián)合平臺，文獻(xiàn)[10-11]采用FPGA硬件平臺，主要對高斯消元法進(jìn)行硬件加速實(shí)現(xiàn)。

表3 系統(tǒng)Raptor碼譯碼性能比較

從表3可以看出，本文的降維譯碼方案，僅對丟包進(jìn)行譯碼，并且采用已知的預(yù)編碼矩陣，替代需進(jìn)行高斯消元的預(yù)譯碼矩陣，避免了對所有源數(shù)據(jù)包譯碼的高斯消元運(yùn)算，實(shí)現(xiàn)了低復(fù)雜度的降維譯碼。在全并行降維譯碼的硬件結(jié)構(gòu)中，所有已接收的源數(shù)據(jù)包和冗余包并行運(yùn)算，大幅降低了譯碼延時(shí)。在單位時(shí)間內(nèi)完成更多次的譯碼運(yùn)算，實(shí)現(xiàn)了高吞吐率的譯碼和傳輸。

5 結(jié) 束 語

本文對系統(tǒng)Raptor碼高復(fù)雜度的高斯譯碼算法進(jìn)行改進(jìn)，提出了一種低復(fù)雜度的降維譯碼算法。在該算法中，僅對少量丟包進(jìn)行譯碼，替代傳統(tǒng)譯碼算法中對全部源數(shù)據(jù)包譯碼的高斯消元運(yùn)算，實(shí)現(xiàn)譯碼維度的大幅降低。并采用全并行的結(jié)構(gòu)實(shí)現(xiàn)降維譯碼算法，最終在Xilinx FPGA XC7K410T上實(shí)現(xiàn)了該譯碼器。測試結(jié)果表明，當(dāng)網(wǎng)絡(luò)丟包率在10-2以下時(shí)，譯碼器譯碼延時(shí)大幅降低；其譯碼吞吐率可達(dá)到3.5 Gbps，是相同平臺下采用高斯消元譯碼的80倍以上。該方案有效提高了系統(tǒng)Raptor碼的譯碼效率，降低了譯碼延時(shí)，提高了數(shù)據(jù)傳輸吞吐率。