一種面向FPGA實現(xiàn)的LDPC編碼可配置并行架構(gòu)設(shè)計*

張雪，姜泉江，梁廣，余金培

(中國科學(xué)院上海微系統(tǒng)與信息技術(shù)研究所， 上海 200050；上海微小衛(wèi)星創(chuàng)新研究院， 上海 201203；上?？萍即髮W(xué)信息科學(xué)與技術(shù)學(xué)院， 上海 201210；中國科學(xué)院大學(xué)， 北京 100049)

隨著航天技術(shù)的不斷進步以及信息的高度數(shù)字化，空間探測、光學(xué)遙感等衛(wèi)星應(yīng)用承載了更廣泛、更精確的空間任務(wù)[1]。以空間數(shù)據(jù)源遙感衛(wèi)星為例，高分辨率、高光譜成像技術(shù)的日益更新使得數(shù)據(jù)量大幅提升，與此同時，用于氣象預(yù)報、災(zāi)害預(yù)警等領(lǐng)域的遙感數(shù)據(jù)具有更高的實時性需求[2]。由此可見，海量數(shù)據(jù)的高效利用需要高速率的數(shù)據(jù)傳輸系統(tǒng)來支持。在星地數(shù)據(jù)傳輸中，需要考慮在低信噪比環(huán)境、可用頻帶資源和發(fā)射功率有限、系統(tǒng)設(shè)計復(fù)雜度和成本造價等內(nèi)外因素條件下，保證數(shù)據(jù)信息的高速有效傳輸。采用高性能和高收斂速率的信道編碼是提高數(shù)傳系統(tǒng)傳輸效率的有效途徑。

低密度奇偶校驗碼(low density parity check, LDPC)于1962年由麻省理工學(xué)院Gallager首次提出[3]，是一類具有稀疏校驗矩陣的線性分組碼，1999年MacKay證明LDPC長碼可達到接近Shannon限的性能,同樣也有更低的線性譯碼復(fù)雜度和可并行譯碼的結(jié)構(gòu)特性，可克服Turbo碼的長碼延時缺陷[4]。雖然LDPC碼具有良好的誤碼性能，但工程上要實現(xiàn)LDPC碼并非易事。為降低工程實現(xiàn)的復(fù)雜度，文獻[5]提出一種由循環(huán)子矩陣構(gòu)成的校驗矩陣，由此產(chǎn)生的碼字成為準循環(huán)LDPC(quasi-cyclic LDPC, QC-LDPC)碼。由于其突出的可實現(xiàn)性，QC-LDPC碼被應(yīng)用于眾多研究領(lǐng)域并被納入相關(guān)標準[6-7]，其中最常用的7/8碼率(8 176，7 154)LDPC碼就是由國際空間數(shù)據(jù)系統(tǒng)咨詢委員會(Consultative Committee for Space Data Systems，CCSDS)提供的[6]。該碼作為近地空間和深空通信的信道編碼方式，構(gòu)造了具有準循環(huán)特性的校驗矩陣和系統(tǒng)碼結(jié)構(gòu)單位生成矩陣，譯碼收斂速率較快且便于硬件工程實現(xiàn)。但隨著對衛(wèi)星通信數(shù)據(jù)傳輸速率需求的不斷增長，串行編碼方式的吞吐量遠遠不能滿足應(yīng)用需求。

目前，關(guān)于LDPC碼低復(fù)雜度編碼器的實現(xiàn)，國學(xué)外學(xué)者已開展了大量研究[8-12]。文獻[8]提出一種CCSDS標準下基于遞歸卷積的并行編碼器，在將資源利用率保持在較低水平的同時，實現(xiàn)理想的吞吐量性能;文獻[9]充分利用QC-LDPC校驗矩陣的循環(huán)特性和行重相同的特點提出一種CMMB標準下基于block-row-cycle的LDPC編碼器;文獻[10]根據(jù)IEEE 802.22無線區(qū)域網(wǎng)絡(luò)(wireless regional area network, WRAN)標準，提出全串行編碼器和串并混合編碼器的設(shè)計能夠在84種碼率的組合下實現(xiàn)低功耗和低資源占用。國內(nèi)Li等[11]提出3種高效的QC-LDPC硬件編碼結(jié)構(gòu)：第1種是移位寄存器累加(shift-register-adder-accumulator, SRAA)的串行編碼結(jié)構(gòu)，但不適用于高速編碼需求；第2種是SRAA的并行編碼結(jié)構(gòu)，但組幀延時較高、同比例所需的寄存器較多；第3種是兩級編碼TWO-STAGE結(jié)構(gòu)，但需要校驗矩陣滿秩。文獻[12]對上述第1種SRAA的串行編碼給出并行編碼算法，但并行度的選取受制于準循環(huán)子矩陣階數(shù)的整數(shù)因子分解情況，當階數(shù)為素數(shù)時，不能應(yīng)用該編碼算法來實現(xiàn)并行編碼，因此并行度的通用化有待研究。

本文針對文獻[11] 中低延時與并行度可配置的應(yīng)用研究需求，根據(jù)第1種SRAA串行編碼結(jié)構(gòu)的并行優(yōu)化方案，提出一種基于FPGA可動態(tài)配置的N位并行LDPC編碼器設(shè)計，推導(dǎo)論證N與速率的制約關(guān)系，并使用Xilinx系列在ISE平臺上實現(xiàn)了8位并行編碼，吞吐量可達2.5 Gbps。

1 準循環(huán)LDPC的CCSDS標準應(yīng)用

1.1 CCSDS標準

CCSDS標準近地空間應(yīng)用中，LDPC碼字結(jié)構(gòu)為7/8碼率(8 176，7 154)的系統(tǒng)分組碼，也是一組典型的QC-LDPC碼。其校驗矩陣H是由2×16個準循環(huán)子矩陣構(gòu)成的維度為1 022×8 176的準循環(huán)矩陣，如下所示

(1)

其中，Ai,j是階數(shù)為511×511的循環(huán)移位子矩陣(i=1,2;j=1,2,…,16)，每個Ai,j行重和列重均為2(即每行、每列有兩個“1”)。圖1為校驗矩陣H的散點圖(“1”的位置)，可直觀看到其稀疏和循環(huán)特性。

圖1 奇偶校驗矩陣散點圖Fig.1 Scatter chart of parity check matrix

生成矩陣G同樣是具有準循環(huán)特性的大小為7 154×8 176的矩陣

(2)

(3)

1.2 編碼原理

LDPC編碼算法主要分為兩類：基于生成矩陣的直接相乘編碼算法和基于近似下三角矩陣RU(Richardson-Urbanke)編碼算法。CCSDS標準中7/8碼率的系統(tǒng)碼(8 176，7 154)采用生成矩陣直接相乘的編碼算法，其中7 154為待編碼信息向量n

(4)

將待編碼信息向量n與生成矩陣G作如下運算，得到LDPC系統(tǒng)碼U

U=n·G,

(5)

(6)

輸入7 154位待編碼信息n，經(jīng)編碼后輸出8 176位系統(tǒng)碼，其中前7 154位為原編碼信息位，后1 022位為生成的奇偶校驗位c。

2 高速編碼器FPGA結(jié)構(gòu)實現(xiàn)方案

2.1 串行編碼方案

Li等在文獻[11]中推導(dǎo)了由校驗矩陣求得具有系統(tǒng)碼結(jié)構(gòu)特性生成矩陣的算法，由此生成矩陣利用SRAA串行編碼結(jié)構(gòu)(如圖2)可實現(xiàn)低復(fù)雜度的串行編碼。

圖2 SRAA串行編碼結(jié)構(gòu)Fig.2 SRAA serial coding structure

串行編碼方案即利用生成矩陣的準循環(huán)特性，以B1,j和B2,j兩個計算單元為一組，共14組(j=1,2,…,14)進行運算。并將待編碼信息向量n如下對應(yīng)分為14個子向量。

(7)

編碼步驟如下：

1)硬件初始化時，累加器1、2復(fù)位，將B1,1和B1,2第1行數(shù)據(jù)分別讀入511位移位寄存器A和B。

2)對于待編碼信息向量m1，第1個時鐘時，將m1向量的第一比特數(shù)據(jù)n1依次與移位寄存器A和B中的數(shù)據(jù)做相與運算，得到的結(jié)果再與累加器中的對應(yīng)數(shù)據(jù)相異或，最后結(jié)果分別存入累加器1和2中。

同理可得，在2～511個時鐘內(nèi)，每個時鐘到來時，移位寄存器A和B所有比特數(shù)據(jù)右移一位，與待編碼信息向量m1的n2～n511數(shù)據(jù)重復(fù)第1個時鐘的操作。直到第511個時鐘完成后，涉及待編碼信息向量m1以及生成矩陣的第1組計算單元B1,1和B1,2的運算完成。并將移位寄存器A和B中的數(shù)據(jù)更換讀入B2,1和B2,2的第1行數(shù)據(jù)。

3)對于待編碼信息向量m2至m14，重復(fù)上述向量m1的運算過程，直到第14×511個時鐘到來時，所有7 154位待編碼信息完成編碼，通過累加器1和2組合得到1 022位校驗信息，將7 154位緩存信息與這1 022位校驗信息結(jié)合最終得到8 176位系統(tǒng)碼。

2.2 高速并行編碼設(shè)計方案

串行編碼設(shè)計方案雖然結(jié)構(gòu)簡單，節(jié)約資源，但也存在高時延，速率低的弊端。隨著超寬帶衛(wèi)星通信高速率、高品質(zhì)應(yīng)用需求的日益顯著，并行編碼方案是實現(xiàn)空間高速數(shù)據(jù)傳輸?shù)挠行侄巍?/p>

本文根據(jù)準循環(huán)LDPC碼的結(jié)構(gòu)特點以CCSDS標準7/8碼率為例，基于SRAA串行編碼方案提出N位可配置高速并行的編碼架構(gòu)，并以8位并行為例加以分析和實現(xiàn)。

當并行度為N，準循環(huán)子矩陣階數(shù)為511時，首先對公式(7)的待編碼信息做補零處理以滿足N位并行的結(jié)構(gòu)特性。設(shè)511除以N，余數(shù)為r(r=511modN,且r

(8)

(9)

其中，當l+(511+k-N)>511時，nl+(511+k-N)=0。

(10)

(11)

除此之外，為了解決串行編碼方案中高時延、速率低這兩個主要弊端，本文在結(jié)構(gòu)上不僅做出了并行調(diào)整，同時也將存放待編碼信息位的輸入緩存單元換為延時單元，待編碼信息在并行輸入添“0”單元的同時也并行送至延時單元，經(jīng)相應(yīng)時鐘延遲后并行輸出，這樣既能減少輸入緩存模塊的資源占用也大大減小了待編碼信息由輸入到輸出的延時周期。以N=8為例，具體結(jié)構(gòu)如圖3所示。

圖3 基于SRAA結(jié)構(gòu)的8位并行編碼結(jié)構(gòu)Fig.3 8-bit parallel coding structure based on SRAA structure

待編碼的7 154位編碼信息分8位依次送至延時單元和輸入信息添“0”單元，延時單元根據(jù)編碼矩陣單元的周期作相應(yīng)延時輸出，輸入信息添“0”單元每隔511位進行一次添“0”操作。隨后將8位并行數(shù)據(jù)輸入編碼矩陣單元，8組(共16個)移位寄存器同串行編碼過程類似，經(jīng)過每個時鐘8 bit移位、異或和累加運算，在14×64個時鐘后產(chǎn)生1 022位校驗信息。最后與延時單元的待編碼信息位在輸出數(shù)據(jù)處理單元進行合并，輸出編碼后LDPC系統(tǒng)碼。

3 編碼器復(fù)雜度分析與資源評估

針對文獻[11]提出的前兩種編碼方案以及本文的優(yōu)化方案,表1給出這3種編碼算法復(fù)雜度的分析對照。由此可見，本文方案所占用的邏輯門數(shù)量與并行N成正比，而隨著N的增加，編碼所用周期成比例減少；當SRAA并行方案與本文方案的編碼速率(編碼周期)相同(N=7)時，SRAA并行方案所用觸發(fā)器數(shù)量為7 154，本文所需觸發(fā)器數(shù)量僅為2 920。綜上所述，SRAA串行方案復(fù)雜度較低，但編碼速率有限；而對于SRAA并行方案，在相同編碼速率情況下，本文并行方案較SRAA并行方案復(fù)雜度更低。

表1 3種編碼算法速率與復(fù)雜度比較Table 1 Comparison of rate and complexity among three coding algorithms

本文根據(jù)所提出的可配置并行架構(gòu)，在FPGA開發(fā)平臺上，基于ISE的集成開發(fā)環(huán)境采用Xilinx公司C4VSX55系列的12ff1148型實現(xiàn)了8位并行編碼。通過表2與串行方案的資源對比可知，并行方案不僅比串行方案節(jié)省9%的資源占用，且最大工作頻率達到330 MHz，8位并行吞吐率可達2.5 Gbps。

表2 串行與8位并行編碼算法資源占用比較Table 2 Comparison of resource occupancy between serial and 8-bit parallel coding algorithms

4 結(jié)論

本文針對準循環(huán)LDPC碼，為更好地應(yīng)對衛(wèi)星超寬帶通信系統(tǒng)中高速率、低時延的應(yīng)用需求，提出一種基于FPGA可動態(tài)配置的N位并行LDPC編碼器設(shè)計，并推導(dǎo)論證并行度N與編碼速率間的制約關(guān)系。主要具有如下優(yōu)點：1)通過編碼前信息預(yù)處理，解決了并行度受限于循環(huán)矩陣位數(shù)的問題；2)將存放待編碼信息位的輸入緩存單元換為延時單元，大大減小編碼的延時周期；3)相較于SRAA并行方案復(fù)雜度更低。最后以7/8碼率的LDPC為例，對8位并行編碼方案仿真，吞吐量達到2.5 Gbps，實現(xiàn)了高速數(shù)據(jù)傳輸?shù)膽?yīng)用需求。本方案的并行度可根據(jù)實際情況作以調(diào)整，具有更好的工程實現(xiàn)背景。