蘭亞柱 楊海鋼 林 郁

?

面向DVB-S2標(biāo)準(zhǔn)LDPC碼的高效編碼結(jié)構(gòu)

蘭亞柱①②楊海鋼*①林 郁①

①(中國(guó)科學(xué)院電子學(xué)研究所可編程芯片與系統(tǒng)研究室 北京 100190),②(中國(guó)科學(xué)院大學(xué) 北京 100049)

面向DVB-S2標(biāo)準(zhǔn)LDPC碼，該文旨在實(shí)現(xiàn)一種基于FPGA的高效編碼結(jié)構(gòu)，提出一種快速流水線并向遞歸編碼算法，可以顯著提高編碼數(shù)據(jù)信息吞吐率。同時(shí)，通過(guò)并向移位運(yùn)算和并向異或運(yùn)算的處理結(jié)構(gòu)計(jì)算編碼中間變量及校驗(yàn)位信息，在提高編碼并行度的同時(shí)可有效減少存儲(chǔ)資源的消耗。此外，針對(duì)動(dòng)態(tài)自適應(yīng)編碼的情況優(yōu)化了LDPC碼編碼存儲(chǔ)結(jié)構(gòu)，有效復(fù)用了數(shù)據(jù)存儲(chǔ)單元和RAM地址發(fā)生器，進(jìn)一步提高FPGA的硬件邏輯資源利用率。針對(duì)DVB-S2標(biāo)準(zhǔn)LDPC碼，基于Stratix IV系列FPGA的驗(yàn)證結(jié)果表明，所提編碼結(jié)構(gòu)在系統(tǒng)時(shí)鐘為126.17 MHz時(shí)，編碼數(shù)據(jù)信息吞吐率達(dá)20 Gbps以上。

LDPC碼；編碼結(jié)構(gòu)；DVB-S2標(biāo)準(zhǔn)； FPGA

1 引言

2004年提出的第2代衛(wèi)星數(shù)字視頻廣播通信標(biāo)準(zhǔn)(DVB-S2)革新性地采用低密度奇偶校驗(yàn)(Low Density Parity Check , LDPC)碼作為前向糾錯(cuò)編碼解決方案[1]。20世紀(jì)60年代初，GALLAGER[2]首次提出LDPC碼。此后，除Tanner圖論外，LDPC碼很少有實(shí)質(zhì)性研究成果。在90年中后期，在Turbo碼廣泛應(yīng)用的背景下，文獻(xiàn)[3,4]通過(guò)創(chuàng)新性研究，促使LDPC碼成為信道編碼領(lǐng)域的研究熱點(diǎn)。

針對(duì)深空通信的特點(diǎn)，DVB-S2標(biāo)準(zhǔn)對(duì)LDPC碼有完善的規(guī)范，包括理論編碼算法、兩種碼長(zhǎng)及多種碼率[5,6]。深空通信中，LDPC碼編碼需要長(zhǎng)期保證正常工作。此情況下，設(shè)計(jì)實(shí)現(xiàn)滿足深空通信中不同編碼環(huán)境的高效編碼結(jié)構(gòu)有很強(qiáng)的現(xiàn)實(shí)意義。

國(guó)內(nèi)，文獻(xiàn)[10]提出基于DVB-S2的高速多碼率LDPC編碼的FPGA設(shè)計(jì)與實(shí)現(xiàn)，采用兩路并行的編碼結(jié)構(gòu)，可使編碼數(shù)據(jù)信息吞吐率達(dá)到328 Mbps。文獻(xiàn)[11]提出基于FPGA的DVB-S2通用LDPC編碼設(shè)計(jì)與實(shí)現(xiàn)，使LDPC編碼能夠針對(duì)多碼長(zhǎng)多碼率實(shí)現(xiàn)有效編碼。文獻(xiàn)[12]針對(duì)DVB-S2標(biāo)準(zhǔn)LDPC碼編碼，提出一種基于FPGA的通用LDPC碼編碼器設(shè)計(jì)，編碼數(shù)據(jù)信息吞吐率可達(dá)63.371 Mbps。

國(guó)外，文獻(xiàn)[13]基于DVB-S2標(biāo)準(zhǔn)LDPC-IRA碼的特點(diǎn)，實(shí)現(xiàn)了LDPC碼并行編碼并保證編碼數(shù)據(jù)信息吞吐率最小可達(dá)5.93 Gpbs。文獻(xiàn)[14]采用并行編碼結(jié)構(gòu)，取得了在碼長(zhǎng)64800碼率1/2的情況下，接近10 Gbps的編碼數(shù)據(jù)信息吞吐率。國(guó)外在DVB-S2標(biāo)準(zhǔn)LDPC碼編碼研究方面，在數(shù)據(jù)信息吞吐率上具有明顯的領(lǐng)先優(yōu)勢(shì)[15]。

為滿足深空通信需求，針對(duì)DVB-S2標(biāo)準(zhǔn)LDPC碼結(jié)構(gòu)，本文提出快速流水線并向遞歸編碼算法，并設(shè)計(jì)滿足多碼長(zhǎng)碼率的高效編碼結(jié)構(gòu)。通過(guò)增加適量的復(fù)雜度，消耗部分額外的硬件邏輯資源，該高效編碼結(jié)構(gòu)使數(shù)據(jù)信息吞吐率明顯提高，可適應(yīng)深空通信需求。

2 核心算法

2.1 DVB-S2標(biāo)準(zhǔn)LDPC碼結(jié)構(gòu)

DVB-S2標(biāo)準(zhǔn)LDPC碼屬于IRA-LDPC碼，其結(jié)構(gòu)特點(diǎn)如式(1)所示。

2.2 基本編碼算法

LDPC碼校驗(yàn)矩陣是稀疏矩陣，但其生成矩陣一般不會(huì)是稀疏矩陣?；揪幋a算法如下：

第1步 初始化校驗(yàn)位：

第2步 計(jì)算信息位對(duì)奇偶校驗(yàn)位的貢獻(xiàn), 計(jì)算公式如式(4)：

第3步 按式(5)計(jì)算，獲得最終的奇偶校驗(yàn)位：

2.3 快速流水線并向遞歸編碼算法

結(jié)合便于硬件邏輯實(shí)現(xiàn)的流水線處理方法，依據(jù)基本編碼算法，本文提出快速流水線并向遞歸編碼算法，具體步驟如下：

(6)將求出的校驗(yàn)位與信息位相結(jié)合就可以得到系統(tǒng)形式的碼字為：

3 編碼結(jié)構(gòu)

基于快速流水線并向遞歸編碼算法，本文采用碼長(zhǎng)碼率的動(dòng)態(tài)自適應(yīng)來(lái)優(yōu)化編碼結(jié)構(gòu)，以使其具有高效性、靈活性及普適性?；趧?dòng)態(tài)自適應(yīng)優(yōu)化的編碼結(jié)構(gòu)如圖1，主要包括校驗(yàn)位存儲(chǔ)RAM、地址表儲(chǔ)存ROM、校驗(yàn)位中間信息計(jì)算模塊、校驗(yàn)位異或處理模塊、輸出模塊和編碼參數(shù)控制單元。

3.1 存儲(chǔ)管理與設(shè)計(jì)

LDPC碼編碼結(jié)構(gòu)中，存儲(chǔ)管理主要分為校驗(yàn)地址信息存儲(chǔ)分塊、信息分塊存儲(chǔ)及中間信息分塊存儲(chǔ)。

校驗(yàn)地址信息存儲(chǔ)分塊以不同碼長(zhǎng)碼率的校驗(yàn)節(jié)點(diǎn)地址為基準(zhǔn)，采用指針式分級(jí)ROM存儲(chǔ)。不同碼率對(duì)應(yīng)的校驗(yàn)節(jié)點(diǎn)地址，指針式分級(jí)存儲(chǔ)通過(guò)動(dòng)態(tài)加載模塊。編譯時(shí)，針對(duì)不同設(shè)置參數(shù)進(jìn)行不同綜合適配，生成針對(duì)用戶設(shè)定的可執(zhí)行文件。當(dāng)用戶設(shè)置兩種或兩種以上碼率時(shí)，指針式分級(jí)存儲(chǔ)會(huì)保證編碼會(huì)在不同碼率之間動(dòng)態(tài)自適應(yīng)調(diào)整，提高編碼靈活性。

編碼信息分塊存儲(chǔ)和編碼中間信息存儲(chǔ)主要在快速流水線并向遞歸編碼算法流程中，為了縮短編碼周期，需要將信息節(jié)點(diǎn)的信息分塊存儲(chǔ)和校驗(yàn)節(jié)點(diǎn)的編碼中間信息分塊存儲(chǔ)按照?qǐng)D1所示的結(jié)構(gòu)存儲(chǔ)。為了通過(guò)數(shù)據(jù)信息的并向存儲(chǔ)，便于快速流水線并向遞歸編碼算法式處理，使兩種節(jié)點(diǎn)數(shù)據(jù)信息具有同步處理及存儲(chǔ)的特性，以便提高編碼效率。為了流水化式處理，編碼結(jié)構(gòu)采用雙端口RAM存儲(chǔ)編碼過(guò)程中的有效數(shù)據(jù)信息，實(shí)現(xiàn)信息節(jié)點(diǎn)及校驗(yàn)節(jié)點(diǎn)信息的周期性流水線并向存儲(chǔ)。

圖1 基于動(dòng)態(tài)自適應(yīng)優(yōu)化的編碼結(jié)構(gòu)

在保證數(shù)據(jù)信息按照快速流水線并向遞歸編碼算法并向存儲(chǔ)后，為保證編碼動(dòng)態(tài)自適應(yīng)，需要硬件邏輯可對(duì)不同碼長(zhǎng)的各類數(shù)據(jù)信息存儲(chǔ)。此情況下，本文采用分布式存儲(chǔ)，以360為基本單位的RAM存儲(chǔ)方式，通過(guò)整體RAM讀寫(xiě)調(diào)度模塊電路，對(duì)所有RAM進(jìn)行讀寫(xiě)管理，使系統(tǒng)時(shí)鐘得到優(yōu)化。

3.2 快速流水線并向遞歸電路

快速流水線并向遞歸編碼進(jìn)程中，并向遞歸電路包括并向遞歸移位運(yùn)算和并向遞歸異或運(yùn)算。并向遞歸移位運(yùn)算是針對(duì)校驗(yàn)地址信息的數(shù)值，完成對(duì)信息分塊和中間信息分塊的旋轉(zhuǎn)移位調(diào)整。并向遞歸移位運(yùn)算主要完成快速流水線并向遞歸編碼算法中步驟(2)，步驟(3)。并向異或運(yùn)算針對(duì)中間信息分塊的數(shù)據(jù)信息，完成快速流水線并向遞歸編碼算法中的步驟(4)，步驟(5)。其中，由步驟(4)的核心算式(7)可知，共涉及360組中間信息的異或處理。

為縮短時(shí)延，本文用組合邏輯結(jié)構(gòu)來(lái)實(shí)現(xiàn)式(7)。該結(jié)構(gòu)以消耗部分硬件邏輯資源為代價(jià)，有效提高快速流水線并向遞歸編碼時(shí)序。面對(duì)快速流水線并向遞歸編碼算法中的步驟(5)，并向異或運(yùn)算采用可循環(huán)并向異或結(jié)構(gòu)，結(jié)構(gòu)并向度為360，保證最小延時(shí)，完成對(duì)中間信息的異或運(yùn)算。

3.3 動(dòng)態(tài)配置電路

為保證靈活性，本文采用碼率碼長(zhǎng)的動(dòng)態(tài)自適應(yīng)進(jìn)行編碼結(jié)構(gòu)的優(yōu)化，主要由動(dòng)態(tài)配置電路來(lái)實(shí)現(xiàn)。當(dāng)用戶設(shè)置不同碼長(zhǎng)碼率時(shí)，通過(guò)動(dòng)態(tài)配置電路對(duì)編碼結(jié)構(gòu)進(jìn)行控制。動(dòng)態(tài)配置電路需要按照指令對(duì)分級(jí)存儲(chǔ)的地址信息進(jìn)行讀取，而且保證編碼結(jié)構(gòu)間的協(xié)調(diào)關(guān)系。動(dòng)態(tài)配置電路可以有效保證編碼進(jìn)程在不同碼率之間動(dòng)態(tài)地自適應(yīng)調(diào)整，提高編碼靈活性。

4 驗(yàn)證與分析

4.1 編碼結(jié)構(gòu)的實(shí)現(xiàn)分析

本文編碼結(jié)構(gòu)的硬件邏輯實(shí)現(xiàn)，基于EP4 SGX230KF40C4 FPGA，使用Quartus II 13.0邏輯綜合、布局布線及時(shí)序分析，ModelSim 10.0b仿真，硬件資源占用如表1所示。

表1 編碼結(jié)構(gòu)的硬件資源耗用(Cf: Combinational functions)

文獻(xiàn)[11-14]只是單一碼長(zhǎng)碼率的硬件邏輯實(shí)現(xiàn)，本文則是可以動(dòng)態(tài)適應(yīng)多碼長(zhǎng)碼率的編碼結(jié)構(gòu)。這得益于通過(guò)本文提出動(dòng)態(tài)配置電路，用戶可以基于編碼環(huán)境因子變化，對(duì)編碼結(jié)構(gòu)碼長(zhǎng)碼率進(jìn)行適應(yīng)性控制。

本文消耗寄存器和存儲(chǔ)資源比文獻(xiàn)[11,12]多。由于本文是并向遞歸編碼，文獻(xiàn)[11,12]為串行編碼。同樣并向編碼，文獻(xiàn)[13,14]與本文消耗相當(dāng)。與文獻(xiàn)[13,14]相比，本文寄存器、存儲(chǔ)資源消耗較多一些。主要由于：(1)為適應(yīng)多碼長(zhǎng)碼率編碼，本文需要對(duì)多種碼長(zhǎng)碼率對(duì)應(yīng)的校驗(yàn)地址信息存儲(chǔ)；(2)為提高快速流水線并向遞歸編碼算法實(shí)現(xiàn)的并行度，本文采用最大備份編碼策略，消耗額外寄存器及存儲(chǔ)資源，來(lái)提高編碼數(shù)據(jù)信息吞吐率。

編碼通用性及靈活性，并向編碼情況，本文比文獻(xiàn)[13,14]具有明顯優(yōu)勢(shì)。不僅可以動(dòng)態(tài)自適應(yīng)不同碼長(zhǎng)碼率，而且可通過(guò)動(dòng)態(tài)配置電路，對(duì)編碼自適應(yīng)范圍進(jìn)行調(diào)整。本文可以保證編碼在通用性、靈活性與硬件邏輯資源消耗之間獲得可控的動(dòng)態(tài)平衡。

硬件存儲(chǔ)資源RAM消耗，本文較文獻(xiàn)[13]所需RAM資源更少，但與文獻(xiàn)[14]相比則多一些。這是由于文獻(xiàn)[14]對(duì)校驗(yàn)向量的計(jì)算不需要任何RAM來(lái)緩存中間結(jié)果，而本文則要求對(duì)中間變量的結(jié)果作緩存處理，但該處理方式使得編碼結(jié)構(gòu)中不再需要大量的移位寄存器。在RAM利用率角度，本文比文獻(xiàn)[13,14]更具優(yōu)勢(shì)。

4.2 編碼結(jié)構(gòu)的性能分析

LDPC碼編碼結(jié)構(gòu)的性能主要體現(xiàn)為編碼數(shù)據(jù)信息吞吐率的大小。借助TimeQuest工具，對(duì)本文編碼結(jié)構(gòu)進(jìn)行評(píng)估。經(jīng)分析，編碼結(jié)構(gòu)數(shù)據(jù)吞吐率計(jì)算如式(9)：

碼長(zhǎng)為64800時(shí)，編碼結(jié)構(gòu)數(shù)據(jù)吞吐率如表2所示。其中，每種碼率組合進(jìn)行10次綜合編譯得出系統(tǒng)時(shí)鐘平均值作為式(3)中的系統(tǒng)時(shí)鐘。分析可知，(1)系統(tǒng)時(shí)鐘隨著碼率變多而有所下降，影響僅約為10 MHz；(2)編碼結(jié)構(gòu)數(shù)據(jù)吞吐率最大為22.71 Gbps，最小為19.97 Gbps；(3)隨著碼長(zhǎng)增大，編碼結(jié)構(gòu)吞吐率會(huì)有所降低。同理，碼長(zhǎng)為16200時(shí)，編碼結(jié)構(gòu)吞吐率最小為19.97 Gbps，最大為22.71 Gbps。

表2 編碼結(jié)構(gòu)的數(shù)據(jù)吞吐率T (Gbps)

注：灰度區(qū)表示無(wú)數(shù)據(jù)。

以上是并行編碼結(jié)構(gòu)數(shù)目為1的情況。如需提高吞吐率，可增加編碼結(jié)構(gòu)數(shù)目。雖然可通過(guò)硬件配置實(shí)現(xiàn)，但是其受到硬件邏輯資源的限制。此情況下，式(9)可修正為

為了公平性，本文選用Marco Gomes和InKi Lee提出的高速LDPC碼編碼結(jié)構(gòu)，取碼長(zhǎng)64800碼率1/2時(shí)的實(shí)現(xiàn)為對(duì)象，進(jìn)行對(duì)比得到表3。

表3 本文與相關(guān)文獻(xiàn)編碼吞吐率性能比較(Gbps)(碼長(zhǎng)為64800)