基于FPGA 的LDPC 編譯碼的高速并行化設(shè)計(jì)與實(shí)現(xiàn)*

吳文俊，張 銳，程敏敏

（中國電科第五十研究所，上海 200331）

0 引言

低密度單奇偶校驗(yàn)碼（Low-Density Parity-Check，LDPC）具有接近香農(nóng)限的性能[1-4]，碼率具有很大的靈活性，能夠在不進(jìn)行打孔的條件下得到合適的碼率，以降低系統(tǒng)性能的損失。LDPC 譯碼速度快，適用于高吞吐量和低時(shí)延系統(tǒng)，但是對硬件資源需求開銷較大。此外，全并行化的譯碼結(jié)構(gòu)對計(jì)算單元和存儲單元的需求都很大。根據(jù)硬件資源量，可以選擇不同的并行實(shí)現(xiàn)層次，以滿足高速率需求，實(shí)現(xiàn)資源和速率上的平衡。本文采用可配置的并行化LDPC 譯碼實(shí)現(xiàn)結(jié)構(gòu)，根據(jù)不同的芯片和速率需求對其進(jìn)行應(yīng)用。

1 LDPC 編譯碼器實(shí)現(xiàn)結(jié)構(gòu)

1.1 LDPC 碼基礎(chǔ)知識

LDPC 碼定義為具有如下結(jié)構(gòu)特性的奇偶校驗(yàn)矩陣H的零空間：

（1）每一行含有ρ個(gè)1；

（2）每一列含有γ個(gè)1；

（3）任何兩列之間位置相同的1 的個(gè)數(shù)不大于1；

（4）與碼長和H的行數(shù)相比，ρ和γ都較小。

對于一個(gè)(n,k)的LDPC 碼，編碼長度為n，信息數(shù)為k，校驗(yàn)為r=n-k個(gè)比特，以使得碼字滿足H×CT=0，H為一個(gè)(n-k)×n的校驗(yàn)矩陣。每個(gè)校驗(yàn)矩陣可以分為大小為b×b的循環(huán)子矩陣，這種子矩陣為單位矩陣的循環(huán)矩陣或者零矩陣。

8×8 的單位循環(huán)矩陣實(shí)例為：

1.2 準(zhǔn)循環(huán)QC_LDPC 碼

確定性結(jié)構(gòu)的LDPC 碼也稱為準(zhǔn)循環(huán)碼（Quasi-Cyslic Low-Density Parity-Check，QC-LDPC）。相對于隨機(jī)結(jié)構(gòu)的矩陣，人們很容易獲得確定性結(jié)構(gòu)矩陣，使得矩陣可以通過更少的參數(shù)來定義LDPC碼[5]。QC-LDPC 碼是一種特殊結(jié)構(gòu)化的LDPC 碼，校驗(yàn)矩陣Hqc形式如下：

校驗(yàn)矩陣由大小相同的循環(huán)子矩陣構(gòu)成。循環(huán)矩陣是一個(gè)方陣，且每行都是前一行的循環(huán)右移動(dòng)，每列都是前一列的循環(huán)下移。它的行重和列重都相同。這種循環(huán)矩陣的信息便于實(shí)現(xiàn)后續(xù)的編譯碼。

1.3 LDPC 編碼器設(shè)計(jì)及實(shí)現(xiàn)

1.3.1 編碼器基本結(jié)構(gòu)

本文中LDPC 支持的編碼速率、信息塊長度以及編碼塊長度如表1 所示。

表1 LDPC 編碼參數(shù)

通信系統(tǒng)的編碼器對實(shí)時(shí)性要求較高，本文根據(jù)QC_LDPC 準(zhǔn)循環(huán)矩陣采用全并行化的處理實(shí)現(xiàn)方式，信息段按照8 bit 位寬進(jìn)入編碼器，碼字長度按照8 位劃分即為輸入的信息長度，編碼后的碼字也按照8 bit 位寬送出。

編碼預(yù)處理可以通過軟件將生成矩陣提前寫入FPGA 的緩存區(qū)，根據(jù)不同的編碼速率調(diào)用不同的生成矩陣。由于是準(zhǔn)循環(huán)矩陣，根據(jù)處理流程的規(guī)格化方式相同，可將可以同時(shí)計(jì)算的內(nèi)容進(jìn)行并行化處理。圖2 為實(shí)現(xiàn)的編碼器結(jié)構(gòu)。

圖2 FPGA 實(shí)現(xiàn)編碼器結(jié)構(gòu)

根據(jù)準(zhǔn)循環(huán)矩陣的特性，基于不同碼率的需求，LDPC 編碼的碼長較長，如果存儲整個(gè)生成矩陣會(huì)造成巨大的資源開銷，也會(huì)增大處理延時(shí)。因此，編碼器根據(jù)生成矩陣需進(jìn)行并行化處理。按照64路并行化處理方式，只存儲非零元素的位置信息，存儲信息量小于原矩陣的1/64，極大地降低了存儲資源消耗。本文中針對（1 536，1 024）2/3 碼率、（1 024，512）1/2 碼率和（2 048，1 280）5/8 碼率3 種不同碼率進(jìn)行實(shí)現(xiàn)。

圖3 為實(shí)現(xiàn)時(shí)調(diào)用的生成矩陣，編碼塊（2 048，1 280）。

圖3 存儲簡化的編碼矩陣塊

編碼器的實(shí)現(xiàn)流程描述如下。

（1）將需要編碼的信息按照每段8 bit 位寬進(jìn)行劃分即u=(u0,u1,…,uk/b-1)，其中ui=(u(i-1)b+1,u(i-1)b+2,…,uib)。編碼后的碼字為v=(u,p1,p2,…,pr)，r=n-k為校驗(yàn)位，其中pj=(pj,1,pj,2,…,pj,b)。

（2）預(yù)先通過軟件將矩陣寫入緩沖區(qū)，待編碼使用。由于QC-LDPC 的循環(huán)特性，只需存儲原矩陣信息的1/64，大大降低了對資源的占用。

（3）根據(jù)輸入比特位寬，通過移位寄存器實(shí)現(xiàn)校驗(yàn)位的輸出，編碼電路如圖4 所示。

圖4 編碼電路

對編碼速率（2 048，1 280）進(jìn)行詳細(xì)分析。編碼塊矩陣為2 048×1 280，根據(jù)描述的矩陣存儲規(guī)則，存儲矩陣大小為20×12（行數(shù)=n/64，列數(shù)=r/64），輸入信號位寬為8 bit。圖4 中B 是一個(gè)反饋移位寄存器，A 是普通寄存器。開始編碼時(shí)，通過讀取ROM 中的預(yù)存矩陣因子，B 載入第一個(gè)8 bit 的生成因子，A 開始依次輸入第一個(gè)8 bit 信息段。根據(jù)預(yù)先存儲好的對應(yīng)信息段，每個(gè)比特的生成因子循環(huán)移位，同時(shí)進(jìn)行8 bit 信息的編碼操作，矩陣以64 長度為循環(huán)劃分，每載入8 個(gè)8 bit 數(shù)據(jù)，加載下一個(gè)矩陣因子。12 行操作同時(shí)并行進(jìn)行，完成20 次列操作，最終生成對應(yīng)信息的編碼數(shù)據(jù)。該編碼實(shí)現(xiàn)結(jié)構(gòu)簡單速度快、效率高且可復(fù)用性強(qiáng)。

1.3.2 編碼器的FPGA 仿真

為提高編碼效率，按照數(shù)據(jù)位寬8 bit 進(jìn)行64路并行化處理。編碼器資源情況如圖5 所示，編碼時(shí)序圖和仿真結(jié)果如圖6 和圖7 所示。根據(jù)不同的碼率，只需根據(jù)參數(shù)調(diào)用不同的生成矩陣，即可快速完成編碼，適用于實(shí)時(shí)性要求較高的通信系統(tǒng)。

從圖5 編碼器資源使用情況可以看出，該編碼器的資源占用率較低，所以具有很強(qiáng)的適用性。根據(jù)編碼實(shí)現(xiàn)流程進(jìn)行數(shù)據(jù)仿真分析，圖6 是編碼處理過程中的矩陣載入情況，按照每64 位循環(huán)載入，輸入數(shù)據(jù)從0～159 共8×160=1 280 bit 編碼，wea_done_out_o 是編碼輸出使能信號，地址從160開始到255 都是編碼校驗(yàn)位的輸出。可以看出，待編碼數(shù)據(jù)輸入完畢后，8 個(gè)clk 開始輸出校驗(yàn)結(jié)果。由于是線性分組碼，前面輸出數(shù)據(jù)個(gè)數(shù)和輸入編碼數(shù)據(jù)一致，后面輸出增加校驗(yàn)位r（r=n-k）。本文所實(shí)現(xiàn)的編碼方案針對不同速率速度快且效率高。

圖5 編碼器資源情況

圖6 矩陣載入

圖7 編碼仿真實(shí)例

1.4 LDPC 譯碼算法及譯碼器結(jié)構(gòu)

譯碼器算法采用最小和積算法MSPA（Min-Sum Product Algorithm），通過分層的并行化來實(shí)現(xiàn)譯碼功能[6]。具體算法步驟如下。

（1）初始化信息。根據(jù)校驗(yàn)矩陣H中1 的位置信息(i,j)，初始化對應(yīng)變量qi,j為輸入的待譯碼信息源。

（2）校驗(yàn)節(jié)點(diǎn)計(jì)算。本文中采用分層修正的最小和譯碼算法，所以對應(yīng)的計(jì)算校驗(yàn)信息ri,j為：

其中?參數(shù)用來減小迭代過程中的擺幅，且在每次完成校驗(yàn)節(jié)點(diǎn)計(jì)算后更新似然比，然后參與下一次校驗(yàn)計(jì)算。

（3）比特節(jié)點(diǎn)計(jì)算。對于校驗(yàn)矩陣H中的每一列中的非零項(xiàng)，計(jì)算變量信息qi,j：

（4）迭代譯碼。對于校驗(yàn)矩陣H中的每一列，任取一個(gè)非零元素(i,j)，則第j個(gè)比特的對數(shù)似然比為llrj=qi,j+ri,j。根據(jù)似然比得到碼字的硬判結(jié)果，如果，則通過校驗(yàn)或者達(dá)到最大迭代次數(shù)，譯碼結(jié)束；否則，繼續(xù)進(jìn)行校驗(yàn)節(jié)點(diǎn)計(jì)算。

1.4.1 譯碼器基本結(jié)構(gòu)

首先解調(diào)后的數(shù)據(jù)通過硬判和軟判結(jié)果送入譯碼模塊，譯碼模塊根據(jù)需求選擇待譯碼數(shù)據(jù)源，然后進(jìn)入分層修正最小和計(jì)算模塊開始進(jìn)行最大迭代次數(shù)的迭代計(jì)算。譯碼器結(jié)構(gòu)如圖8 所示。

分層修正最小和計(jì)算的內(nèi)部實(shí)現(xiàn)模塊如圖9 所示。核心計(jì)算模塊中存儲校驗(yàn)矩陣的行重信息和每行中1 所在的位置信息。通過訪問這兩個(gè)模塊，核心計(jì)算模塊可以計(jì)算出校驗(yàn)信息。R_MATRIX 中存儲的是校驗(yàn)信息ri,j，APP_BUF 中存儲的是所有信息的對數(shù)似然比llrj，即為后驗(yàn)概率。

核心計(jì)算模塊首先通過讀取校驗(yàn)矩陣H相應(yīng)行1 的位置，通過式（6）計(jì)算該行變量信息qi,j；其次，通過式（5）計(jì)算得到校驗(yàn)信息ri,j；再次，計(jì)算第j個(gè)比特的對數(shù)似然比為llrj=qi,j+ri,j，更新相應(yīng)的APP_BUF 中的數(shù)值。最后，當(dāng)校驗(yàn)矩陣遍歷一遍后，迭代次數(shù)加1，重復(fù)上述過程，直至完成譯碼或者達(dá)到最大迭代次數(shù)。

圖8 譯碼器結(jié)構(gòu)

圖9 分層修正最小和計(jì)算模塊內(nèi)部

1.4.2 譯碼器的擴(kuò)展結(jié)構(gòu)

本文基于最小和譯碼算法設(shè)計(jì)了一種可配置并行化的層次譯碼器結(jié)構(gòu)，具體算法采用分層模式，但是對數(shù)據(jù)處理按照并行化方式進(jìn)行，即一次迭代同時(shí)對N個(gè)待譯碼數(shù)據(jù)進(jìn)行計(jì)算，以提高吞吐量。

為滿足多種速率需求，將不同速率的校驗(yàn)矩陣按照64 間隔劃分，并通過外部接口寫入內(nèi)部存儲，需要時(shí)從緩沖區(qū)中讀取校驗(yàn)矩陣，節(jié)省資源，提高靈活度。

存儲譯碼需要H矩陣時(shí)，利用準(zhǔn)循環(huán)矩陣的循環(huán)特性，只存儲矩陣信息的1/64 以及對應(yīng)的行重，并且采取全并行化實(shí)現(xiàn)。李江林等人實(shí)現(xiàn)的并行化方案按照單位矩陣為粒度進(jìn)行[7]，實(shí)現(xiàn)靈活度較低，且根據(jù)不同的碼率還需要重新修改代碼。該方式依據(jù)準(zhǔn)循環(huán)矩陣的特性以及其正交性，只需獲知極少的有效信息便可進(jìn)行譯碼操作，極大地降低了資源存儲的消耗，根據(jù)不同的碼率調(diào)用不同的矩陣即可。經(jīng)過仿真驗(yàn)證對比，在處理速度上碼率的影響并不是很大，只有不同的并行化方式對處理速度影響較大。本例中依據(jù)（2 048，1 280）碼率進(jìn)行分析，根據(jù)校驗(yàn)矩陣H，在FPGA 中預(yù)先存儲行重以及每一行中1 的位置，如表2 所示。

本文在FPGA 實(shí)現(xiàn)中采用了軟判決和硬判決都可選的譯碼方式。硬判決是對信道的輸出做出是0還是1 的判決；軟判決不作出0、1 判決，只輸出有關(guān)信息，如0、1 的后驗(yàn)概率。具體應(yīng)用中，可根據(jù)需求可以選擇不同的譯碼判決方式進(jìn)行對比。硬判決譯碼算法是通過傳遞比特信息進(jìn)行解碼，如比特翻轉(zhuǎn)譯碼算法。雖然它具有譯碼算法簡單的優(yōu)勢，但是達(dá)不到最佳的譯碼性能。軟信息是譯碼算法傳遞和后驗(yàn)信息相關(guān)的置信度信息，通過置信傳播譯碼具有優(yōu)秀的糾錯(cuò)性能。

表2 校驗(yàn)矩陣

1.4.3 譯碼器實(shí)現(xiàn)結(jié)構(gòu)比較

本文中譯碼器實(shí)現(xiàn)采用了16 路、32 路、64 路并行的3 種并行化實(shí)現(xiàn)方式，通過在模塊外部配置參數(shù)，改變#defineN的值來改變并行化處理路數(shù)模式，從而實(shí)現(xiàn)3 種并行化可選。圖10～圖13 依次列出了16 路并行實(shí)現(xiàn)方式的仿真結(jié)果，包括資源使用情況、16 路矩陣、一次譯碼迭代時(shí)間以及一次譯碼成功時(shí)間。仿真條件：時(shí)鐘頻率61.44 MHz，編碼速率（2 048，1 280），譯碼數(shù)據(jù)錯(cuò)誤率50%以下均可譯碼成功。

圖10 譯碼器資源使用情況

圖11 16 路矩陣

圖12 一次譯碼迭代時(shí)間（12 μs）

圖13 一次譯碼成功時(shí)間（45.7 μs）

同時(shí)，本文對3 種并行化實(shí)現(xiàn)方式的結(jié)果進(jìn)行對比，如表3 和表4 所示。

表3 資源使用情況對比

表4 譯碼時(shí)間對比

通過ModelSim 仿真對比分析可以看出，資源使用和譯碼效率成反比，需根據(jù)需求選擇不同的譯碼方式。該實(shí)現(xiàn)方式能夠滿足多種速率的需求，提高波形的靈活性和可靠性。實(shí)際驗(yàn)證平臺中，模塊的工作時(shí)鐘是61.44 MHz，編碼方式（2 048，1 280），譯碼最大迭代次數(shù)16 次，并行方式為64路，最長譯碼時(shí)間為98 μs；同試驗(yàn)平臺原糾錯(cuò)方案RS 編解碼實(shí)現(xiàn)相比有2 dB 左右的編碼增益，意味著采用該實(shí)現(xiàn)方式后可以大大提高系統(tǒng)的抗干擾性能和糾錯(cuò)性能。

2 LDPC 碼和Turbo 碼性能比較

LDPC 的譯碼算法是一種基于稀疏矩陣的并行迭代譯碼算法，運(yùn)算量低于Turbo 碼的譯碼算法。由于結(jié)構(gòu)并行的特點(diǎn)，在硬件實(shí)現(xiàn)上比較容易。因此，在大容量通信應(yīng)用中，LDPC 碼更具有優(yōu)勢。LDPC 的碼率具有很大的靈活性，而Turbo 需要打孔來提高碼率，導(dǎo)致選擇打孔圖案的十分謹(jǐn)慎，否則會(huì)造成較大的性能損失。

3 結(jié)語

本文基于xilinx-A7 平臺實(shí)現(xiàn)了基于LDPC 的編譯碼器的并行化可配置的設(shè)計(jì)與實(shí)現(xiàn)，并在ModelSim的仿真環(huán)境下對該實(shí)現(xiàn)進(jìn)行仿真。對（1 536，1 024）、（1 024，512）、（2 048，1 280） 這3 種碼率進(jìn)行編譯碼仿真聯(lián)試，主要針對0.625 碼率的（2 048，1 280）進(jìn)行編譯碼分析，結(jié)果顯示編碼器占用資源開銷較小，譯碼器在高度并行化、較高吞吐量情況下占用資源較多，但是具有較高的數(shù)據(jù)吞吐量，能夠達(dá)到40 MHz，滿足不同速率的編譯碼需求和靈活的資源利用率。根據(jù)設(shè)計(jì)需求，采用不同的譯碼器并行實(shí)現(xiàn)結(jié)構(gòu)應(yīng)用于不同場景，證明本文的設(shè)計(jì)具有較高的靈活性。最后，通過試驗(yàn)驗(yàn)證了本文編譯碼算法實(shí)現(xiàn)的有效性，它在高速率傳輸中具有很好的可靠性和優(yōu)越性。