高效低復(fù)雜度的QC-LDPC碼全并行分層結(jié)構(gòu)譯碼器

吳 淼，邱麗鵬，周 林,2，賀玉成,2

(1.華僑大學(xué) 廈門市移動(dòng)多媒體通信重點(diǎn)實(shí)驗(yàn)室，福建 廈門 361021；2.西安電子科技大學(xué) 綜合業(yè)務(wù)網(wǎng)理論及關(guān)鍵技術(shù)國家重點(diǎn)實(shí)驗(yàn)室，西安 710071)

0 引 言

低密度奇偶校驗(yàn)碼是一類可逼近香農(nóng)限的信道編碼技術(shù)，由Gallager教授于上世紀(jì)60年代首次提出。偽隨機(jī)低密度奇偶校驗(yàn)(low-density parity-check，LDPC)碼由于缺乏結(jié)構(gòu)性編碼方法，長期未能在硬件實(shí)現(xiàn)上獲得突破。一方面，準(zhǔn)循環(huán)低密度奇偶校驗(yàn) (quasi-cyclic low-density parity-check，QC-LDPC)碼[1]的提出為LDPC碼在硬件實(shí)現(xiàn)上獲得突破提供了可能；另一方面，傳統(tǒng)LDPC碼譯碼器大多采用串行結(jié)構(gòu)和全并行結(jié)構(gòu)，但這2種結(jié)構(gòu)都各自存在明顯的缺陷。隨著QC-LDPC碼研究的不斷深入，人們提出了部分并行結(jié)構(gòu)，這種結(jié)構(gòu)充分利用碼的準(zhǔn)循環(huán)特性，使譯碼器在吞吐量與資源消耗之間獲得平衡。近幾年，一種新的分層譯碼結(jié)構(gòu)(layered decoding，LD)及其算法[2-3]被提出。分層譯碼結(jié)構(gòu)與傳統(tǒng)部分并行結(jié)構(gòu)相比較，有著收斂速度更快、結(jié)構(gòu)更為簡單等優(yōu)點(diǎn)，從而改善了譯碼器實(shí)現(xiàn)有效性。

LDPC碼原始的2種譯碼算法包括：基于硬判決的比特翻轉(zhuǎn)譯碼算法(bit flipping，BF)和基于軟判決的置信度傳播迭代譯碼算法(belief propagation，BP)。軟判決譯碼是基于后驗(yàn)概率(a posteriori probability，APP)測度，通過反復(fù)迭代來提高LDPC碼的譯碼性能，并使其逼近香農(nóng)限。最小和算法(min-sum algorithm，MSA)是基于BP的簡化算法，雖然該算法犧牲了一定的性能，但極大地降低了計(jì)算復(fù)雜度，便于硬件實(shí)現(xiàn)。歸一化最小和算法(normalized min-sum algorithm，NMSA)是一種改進(jìn)的MSA，通過增加一個(gè)修正因子在一定程度上補(bǔ)償因簡化計(jì)算而導(dǎo)致的性能損失。根據(jù)消息傳遞機(jī)制，軟判決譯碼算法又可分為TDMP(turbo decoding message passing)[3]算法和TPMP(two-phase message passing)[4]算法。TPMP算法又稱雙向迭代消息傳遞算法，該算法包含2個(gè)清晰的迭代過程:水平迭代和垂直迭代。上述提到的BP算法、MSA和NMSA均屬于TPMP算法。與雙向迭代消息傳遞機(jī)制不同，TDMP算法在迭代過程中，當(dāng)某個(gè)分層完成校驗(yàn)節(jié)點(diǎn)的更新后，立即將更新的消息傳遞給下一分層，完成垂直方向上的消息傳遞；下一分層在接收到上一分層的后驗(yàn)消息后，結(jié)合上次迭代產(chǎn)生的校驗(yàn)消息而完成更新；直到所有分層都完成更新，一輪迭代才結(jié)束。這種類似于Turbo碼串行迭代的更新方式，消除了水平迭代和垂直迭代的更新等待時(shí)間，加快了譯碼的收斂速度。文獻(xiàn)[5]中實(shí)現(xiàn)TDMP算法，與傳統(tǒng)TPMP算法的LDPC譯碼器相比，在吞吐率上實(shí)現(xiàn)了2倍的提升。

隨著大規(guī)模集成電路的快速發(fā)展，實(shí)現(xiàn)高效的LDPC碼編譯碼器成為一項(xiàng)重要研究內(nèi)容。2005年，L. Yang[6]完成了工作頻率112 MHz、吞吐率為127 Mbit/s的(3,6)規(guī)則LDPC碼譯碼器的現(xiàn)場可編程門陣列(field programmable gate array，F(xiàn)PGA)實(shí)現(xiàn)；2012年，袁瑞佳[7]設(shè)計(jì)出一種基于FPGA的LDPC碼編譯碼器聯(lián)合設(shè)計(jì)方法，所設(shè)計(jì)的編碼器和譯碼器可并行工作，有效提升了硬件工作效率；2013年，姚遠(yuǎn)[8]實(shí)現(xiàn)了基于IEEE 802.16e標(biāo)準(zhǔn)的并行分層譯碼算法的LDPC譯碼器硬件設(shè)計(jì)；同年，周健等[9]實(shí)現(xiàn)了面向磁記錄信道的原模圖LDPC碼譯碼器的FPGA設(shè)計(jì)；2015年，張順根等[10]提出了一種基于FPGA的隨機(jī)構(gòu)造QC-LDPC分層譯碼器設(shè)計(jì)方法。上述LDPC譯碼器設(shè)計(jì)普遍存在不同程度的實(shí)現(xiàn)復(fù)雜度問題，為此，本文充分利用QC-LDPC碼的準(zhǔn)循環(huán)結(jié)構(gòu)特點(diǎn)，提出一種改進(jìn)的可降低實(shí)現(xiàn)復(fù)雜度的全并行分層譯碼器結(jié)構(gòu)。

1 QC-LDPC碼及其分層譯碼算法

1.1 QC-LDPC碼簡介

QC-LDPC碼是一種有準(zhǔn)循環(huán)結(jié)構(gòu)的LDPC碼，其實(shí)質(zhì)上是將LDPC碼的校驗(yàn)矩陣劃分成多個(gè)子塊，每個(gè)子塊由全零矩陣或非零的具有循環(huán)特性的置換矩陣構(gòu)成。QC-LDPC碼實(shí)現(xiàn)復(fù)雜度低，便于硬件實(shí)現(xiàn)。

1.2 分層譯碼算法

本文使用的國際空間數(shù)據(jù)系統(tǒng)咨詢委員會(consultative committee for space data system，CCSDS)標(biāo)準(zhǔn)下的(8 192,4 096)碼，它由通過循環(huán)移位單位矩陣產(chǎn)生的子矩陣，這樣的結(jié)構(gòu)非常適合水平分層譯碼算法，因?yàn)槊總€(gè)子矩陣的列重為1。在水平分層譯碼中，可以將基矩陣的每一行作為一個(gè)層，共分為12層，來自當(dāng)前層的變量節(jié)點(diǎn)消息將垂直傳遞給屬于同一個(gè)變量節(jié)點(diǎn)的所有其他未處理的層。在每次迭代中，從頂層到底層按順序處理。

在非分層算法中，雙向互相傳遞的信息，稱作變量節(jié)點(diǎn)信息與校驗(yàn)節(jié)點(diǎn)信息，由單獨(dú)的處理單元更新并迭代地相互傳遞，變量節(jié)點(diǎn)會等待校驗(yàn)節(jié)點(diǎn)全部更新完畢才會進(jìn)行更新，反之亦然。而在分層譯碼算法中，各個(gè)層逐層參與譯碼操作，某個(gè)層完成了校驗(yàn)節(jié)點(diǎn)更新之后，立刻將更新的信息傳遞給下一層進(jìn)行處理，當(dāng)所有層都完成一次循環(huán)之后，即為完成一次迭代。分層譯碼算法相比于非分層譯碼算法，顯著減少譯碼迭代計(jì)算的等待時(shí)間，加快譯碼迭代速率。硬件實(shí)現(xiàn)方面，在非分層算法中，校驗(yàn)節(jié)點(diǎn)和變量節(jié)點(diǎn)之間頻繁的消息傳遞需要一個(gè)復(fù)雜的布線網(wǎng)絡(luò)，而分層譯碼算法將變量節(jié)點(diǎn)部分退化成一個(gè)存儲器，簡化了非分層譯碼算法中過于復(fù)雜的內(nèi)部連接網(wǎng)絡(luò)，降低了控制模塊的設(shè)計(jì)復(fù)雜度。同時(shí)，在實(shí)現(xiàn)分層譯碼算法時(shí)，相比于非分層譯碼算法，迭代次數(shù)明顯降低，迭代速度顯著提高。

目前，用于FPGA實(shí)現(xiàn)的LDPC碼主流譯碼算法是MSA及其改進(jìn)算法。本文采用分層最小和譯碼算法(layered min-sum decoding algorithm，LMSDA)，也是基于MSA的一種改進(jìn)算法，其算法主要描述為

qj,nj=Λnj-rj,nj

(1)

(2)

(3)

LMSDA的具體工作流程如下。

步驟1對后驗(yàn)概率信息Λnj和校驗(yàn)節(jié)點(diǎn)信息進(jìn)行初始化。

Λnj=2y2/σ2,rj,nj=0

(4)

(4)式中：y為接收信息；σ2為噪聲方差。

步驟2第k次迭代，第j層。

更新變量節(jié)點(diǎn)信息

(5)

更新校驗(yàn)節(jié)點(diǎn)信息

(6)

步驟3更新后驗(yàn)概率信息，表達(dá)式為

(7)

步驟4譯碼判決：當(dāng)Λnj>0時(shí)，輸出判決Znj=0；否則Znj=1。若譯碼結(jié)果Z滿足ZHT=0或達(dá)到最大迭代次數(shù)lmax，則停止迭代，輸出Z；否則，k=k+1，并跳轉(zhuǎn)至步驟2繼續(xù)下一次迭代。

在LMSDA中，將變量節(jié)點(diǎn)更新模塊簡化成一個(gè)存儲單元，變量節(jié)點(diǎn)與校驗(yàn)節(jié)點(diǎn)之間信息的傳遞，由一個(gè)校驗(yàn)節(jié)點(diǎn)更新(check node update，CNU)模塊來完成。由于省去了變量節(jié)點(diǎn)，垂直方向上的消息傳遞則根據(jù)校驗(yàn)矩陣H中循環(huán)子矩陣偏移值的差值通過校驗(yàn)節(jié)點(diǎn)與校驗(yàn)節(jié)點(diǎn)之間來互相傳遞。但校驗(yàn)矩陣H中，同一列位置上可能有多個(gè)相同的偏移值或其差值小于12(假設(shè)一個(gè)CNU計(jì)算延遲為12個(gè)時(shí)鐘周期)。偏移值的差值過小會造成嚴(yán)重不利影響：比如某時(shí)刻t，當(dāng)前校驗(yàn)節(jié)點(diǎn)Cj未計(jì)算完更新值，另一個(gè)與Cj在同一列上有非零元素的校驗(yàn)節(jié)點(diǎn)Ck將開始讀取Cj的更新值，會導(dǎo)致譯碼失敗。因此，本文根據(jù)文獻(xiàn)[11]的方法對校驗(yàn)矩陣H中循環(huán)子矩陣的偏移值進(jìn)行了修正，如圖1所示。

圖1 修正偏移值的(8 192,4 096) LDPC碼的校驗(yàn)矩陣Fig.1 Offset correction value check matrix of the (8 192,4 096) LDPC code

本文修正后的校驗(yàn)矩陣滿足同一超列上的非零偏移值之間的差值大于等于12，這個(gè)數(shù)值是CNU模塊所保留的計(jì)算空間，即一個(gè)CNU單元最大延遲為12個(gè)時(shí)鐘周期。垂直方向上消息傳遞的規(guī)則可總結(jié)為：每一超行數(shù)據(jù)處理完畢后，傳遞給偏移值較小的超行，最后，偏移值最小的超行傳給最大偏移值的超行。以第20超列中的6個(gè)超行為例，其傳遞規(guī)則為：340→302→108→40→28→12→340。本文修正后的校驗(yàn)矩陣與原校驗(yàn)矩陣的性能比較如圖2所示，由圖2可知，修正后的校驗(yàn)矩陣在誤碼率性能上有微小損失，幾乎可以忽略不計(jì)。而修正后的校驗(yàn)矩陣使得分層的并行度得到了較大幅度的提升，可以進(jìn)一步提升譯碼器的吞吐量。為驗(yàn)證LMSDA的性能，本文采用CCSDS標(biāo)準(zhǔn)下的(8 192,4 096)LDPC碼，經(jīng)仿真實(shí)驗(yàn)和優(yōu)化，量化位數(shù)設(shè)定為6 bit，最大迭代次數(shù)設(shè)定為10次，并與其他幾種譯碼算法進(jìn)行性能比較，結(jié)果如圖3所示。10次迭代的LMSDA的性能與20次迭代的最小和算法相近，即在相同誤碼率的條件下，LMSDA的收斂速度明顯優(yōu)于最小和算法，可有效降低譯碼器迭代次數(shù)。

圖2 校驗(yàn)矩陣修正前后的性能比較Fig.2 Comparison of performance before and after check matrix correction

圖3 不同算法的誤碼率性能比較Fig.3 Comparison of Bit-Error-Rate performance of different algorithm

2 譯碼器設(shè)計(jì)與實(shí)現(xiàn)

本文選擇CCSDS標(biāo)準(zhǔn)的(8 192,4 096)LDPC碼來設(shè)計(jì)全并行分層最小和(parallel layered min-sum，PLMS)譯碼器。本文設(shè)計(jì)主要特點(diǎn)有：①采用狀態(tài)切割技術(shù)，使譯碼器的整體延時(shí)縮短，并提升了同步性能；②采用共用存儲器結(jié)構(gòu)，大大降低了硬件資源的消耗；③優(yōu)化設(shè)計(jì)五級流水線結(jié)構(gòu)，能夠有效提高譯碼器工作頻率。本文設(shè)計(jì)的QC-LDPC碼譯碼器系統(tǒng)框圖如圖4所示。

圖4 全并行分層LDPC碼譯碼器結(jié)構(gòu)框圖Fig.4 Structure diagram of Full-Parallel-Layered decoder of QC-LDPC codes

本譯碼器采用一種基于TDMP算法和NMSA相結(jié)合的譯碼算法，該算法具備TDMP算法的快收斂性，同時(shí)又擁有NMSA的低復(fù)雜度。通過對校驗(yàn)矩陣偏移值的修正，譯碼器支持全并行分層譯碼，克服了TDMP算法吞吐量低的缺點(diǎn)。本設(shè)計(jì)譯碼器由接收信道信息(Rec_Dat)、信息存儲器(APP_Memory，CTV_Memory和DEC_BIT_RAM)、消息處理單元(message processing unit，MPU)、譯碼輸出(Dec_BIT_Output)以及迭代譯碼控制(Dec_Ctrl)等幾個(gè)主要模塊組成。下面主要介紹譯碼器幾個(gè)具有特色部分的設(shè)計(jì)。

2.1 狀態(tài)切割技術(shù)

傳統(tǒng)的譯碼器設(shè)計(jì)方法將所有的控制信號、地址信號集成在一個(gè)控制模塊和一個(gè)地址生成器之中，容易導(dǎo)致延時(shí)較長，同步的能差的缺陷。本設(shè)計(jì)采用了狀態(tài)切割技術(shù)，將控制狀態(tài)機(jī)分成3個(gè)相對獨(dú)立的小狀態(tài)機(jī)，分別是接收狀態(tài)機(jī)、MPU狀態(tài)機(jī)和輸出狀態(tài)機(jī)。接收狀態(tài)機(jī)與輸出狀態(tài)機(jī)用于控制信息的輸入與輸出，MPU狀態(tài)機(jī)負(fù)責(zé)控制迭代過程。與傳統(tǒng)的方法相比，本設(shè)計(jì)優(yōu)點(diǎn)在于延時(shí)較低且能提高工作頻率。本文狀態(tài)切割如圖5所示。

2.2 信息存儲模塊及共用存儲器結(jié)構(gòu)

信息存儲模塊包括APP_Memory模塊、CTV_Memory模塊和譯碼判決模塊(DEC_BIT_RAM)。其中，APP_Memory模塊儲存初始化信息和每次迭代產(chǎn)生的后驗(yàn)信息(垂直信息)，CTV_Memory模塊儲存上一次迭代過程中的校驗(yàn)節(jié)點(diǎn)更新的信息(水平信息)，RAM_DEC_BIT模塊用于存儲每次迭代結(jié)束后的譯碼結(jié)果。

圖5 狀態(tài)切割技術(shù)示意圖Fig.5 State segmentation diagram

2.2.1 APP_Memory模塊

本文選用修正后的(8 192,4 096)QC-LDPC碼，利用其校驗(yàn)矩陣的準(zhǔn)循環(huán)特性，只需有非零元素的子矩陣位置上配置一個(gè)memory單元，儲存該位置變量節(jié)點(diǎn)更新的值，最大限度地節(jié)省空間。信道信息的初始化過程與迭代過程不是同時(shí)進(jìn)行，因此，信道初始化信息與變量節(jié)點(diǎn)更新信息可以共用一個(gè)存儲器。存儲器由二選一選擇器選擇存儲的信息，初始化階段Ln被選通，而迭代更新階段則CTV被選通，本設(shè)計(jì)可以降低資源消耗，提升硬件資源利用率。本文設(shè)計(jì)共用存儲器的結(jié)構(gòu)如圖6所示。

圖6 APP_Memory模塊結(jié)構(gòu)Fig.6 APP_Memory module structure

圖6中，Mem1-9表示該單元儲存第1層第9個(gè)子矩陣所在的變量節(jié)點(diǎn)的迭代信息，Mem2-18指向第2層第18個(gè)子矩陣，以此類推。每一層的memory個(gè)數(shù)與H矩陣的列重相等，例如Layer1的列重為3，memory也為3個(gè)；Layer12的列重為6，memory也為6個(gè)。圖1所示校驗(yàn)矩陣共60個(gè)非零子矩陣，因此，APP_Memory模塊共有60個(gè)memory單元。每個(gè)memory單元采用乒乓存儲結(jié)構(gòu)，即當(dāng)前幀參與本次迭代譯碼的同時(shí)，可對下一幀的信道初始化信息進(jìn)行接收。memory單元采用簡單雙端口RAM設(shè)計(jì)，存儲深度設(shè)置為2倍循環(huán)陣的大小，即512×2=1 024。前512個(gè)RAM劃分為高位存儲區(qū)，儲存當(dāng)前幀的迭代更新信息，后512個(gè)低位存儲區(qū)用于儲存下一幀數(shù)據(jù)的初始化信息，高低位存儲區(qū)由Rec_Dat模塊Ln數(shù)據(jù)地址高位信號“wraddr_ln_high”控制。當(dāng)wraddr_ln_high=‘0’時(shí)，Ln數(shù)據(jù)被寫入高位存儲區(qū)，反之，Ln數(shù)據(jù)寫入低位存儲區(qū)。

2.2.2 CTV_Memory模塊

CTV_Memory模塊完成校驗(yàn)節(jié)點(diǎn)信息的存儲，本文修正的(8 192,4 096)LDPC碼校驗(yàn)矩陣最大可分為12層，每層配置一個(gè)校驗(yàn)節(jié)點(diǎn)，共需要12個(gè)RAM單元。由于每次水平更新時(shí)MPU只讀取一次校驗(yàn)信息，也就是說，CTV_Memory模塊只需要存儲上一次迭代的校驗(yàn)信息，不需要乒乓存儲結(jié)構(gòu)。所以，CTV_Memory直接采用簡單雙端口RAM實(shí)現(xiàn)即可，存儲深度為512。

2.2.3 譯碼結(jié)果存儲模塊

每一次迭代結(jié)束后得到的譯碼結(jié)果，將被輸入到譯碼結(jié)果存儲器(DEC_BIT_RAM)中暫存。暫存的數(shù)據(jù)可用作輸出校驗(yàn)，若譯碼正確則停止迭代，并輸出最終的譯碼結(jié)果，否則繼續(xù)進(jìn)行下一次迭代。本文選取的LDPC碼碼長為8 192，碼率為0.5，信息長度為4 096。因此，譯碼結(jié)果存儲器僅需要一個(gè)深度為8 192的RAM單元。同樣地，DEC_BIT_RAM存儲器也是乒乓緩存結(jié)構(gòu)，支持連續(xù)輸出。綜上，譯碼器共消耗60×6+12×3+8=404 kbit，節(jié)省了存儲信道初始化信息所需8 192×6 bit=48 kbit的空間。

2.3 消息處理單元MPU模塊及五級流水線結(jié)構(gòu)

在LMSDA中，變量節(jié)點(diǎn)更新模塊退化成一個(gè)存儲單元，變量節(jié)點(diǎn)與校驗(yàn)節(jié)點(diǎn)之間信息的傳遞，由一個(gè)消息處理單元MPU模塊來完成。因此，MPU模塊成為算法中的核心處理單元，其整體電路結(jié)構(gòu)如圖7所示。

圖7 MPU模塊整體電路結(jié)構(gòu)Fig.7 MPU module integrated circuit structure

模塊內(nèi)部配置了2個(gè)狀態(tài)機(jī)和1個(gè)地址生成器，用于簡化頂層控制模塊的設(shè)計(jì)復(fù)雜度。讀狀態(tài)機(jī)與寫狀態(tài)機(jī)分別產(chǎn)生CTV_Memory和APP_Memory存儲器的讀地址和寫地址及相應(yīng)的控制信號。地址生成器根據(jù)2個(gè)狀態(tài)機(jī)的控制信號，完成地址的初始化，之后的每一拍令地址自加1并輸出即可。整個(gè)MPU模塊的啟動(dòng)、終止信號由控制模塊(Dec_Ctrl)產(chǎn)生。

每個(gè)MPU通過讀取與之相連的變量節(jié)點(diǎn)所對應(yīng)APP_Memory上的值，在模塊內(nèi)部首先完成垂直信息的更新，再經(jīng)過CNU模塊進(jìn)行分離、比較運(yùn)算得出水平信息的更新值。最后將垂直信息和水平信息疊加得到后驗(yàn)信息，才完成一次迭代。本設(shè)計(jì)中，減法器組模塊為流水線結(jié)構(gòu)的第1級，CNU模塊包含了3個(gè)級，分別是符號幅值分離模塊、求最小值模塊、合成模塊，最后由加法器組模塊作為流水線結(jié)構(gòu)的第5級。五級流水線的優(yōu)點(diǎn)在于可以有效地提高工作頻率。下面以行重為8的校驗(yàn)節(jié)點(diǎn)為例，MPU模塊的五級流水線結(jié)構(gòu)如圖8所示。

圖8中，CTV為上一次迭代校驗(yàn)節(jié)點(diǎn)傳給變量節(jié)點(diǎn)的信息，APP為上一次迭代的后驗(yàn)信息。減法器組模塊為流水線結(jié)構(gòu)的第1級，完成LMSDA的第1步，即垂直信息的更新。MPU模塊每一拍分別向APP_Memory和CTV_Memory模塊讀取上一次迭代的水平信息和后驗(yàn)概率信息，并完成8次并行的減法運(yùn)算。為了避免溢出，將減法器經(jīng)過一個(gè)限幅器(Limit)進(jìn)行限幅，然后將數(shù)據(jù)傳入第2級進(jìn)行CNU更新。為了方便計(jì)算，譯碼器內(nèi)部信息均采用二進(jìn)制補(bǔ)碼表示。第2—4級流水線為CNU模塊，這部分實(shí)現(xiàn)了垂直信息的分離、比選以及合并工作，完成水平信息的更新。圖8中的第2—4級是以校驗(yàn)矩陣第1列為例，行重為3的CNU電路結(jié)構(gòu)。其中，“Abs_sign”模塊實(shí)現(xiàn)符號位與幅值分離的功能；“<”模塊實(shí)現(xiàn)輸入數(shù)據(jù)的比較并輸出最小值；“D”代表D觸發(fā)器；“x?2-x”模塊實(shí)現(xiàn)最小值歸一化因子α的乘積；第2級進(jìn)行符號與幅值分離的工作，第3級將符號位延時(shí)并比較求出最大值與最小值，第4級將符號與幅值合并。對比文獻(xiàn)[11]，本文設(shè)計(jì)省去了比較與選擇部分，節(jié)約了硬件資源開銷，有效減少了關(guān)鍵路徑延時(shí)，提高了工作頻率。此外，還融入了歸一化最小和因子的計(jì)算，可以進(jìn)一步節(jié)省硬件資源，且不需要額外增加控制信號。第5級流水線為加法器組模塊，將第1級減法器組輸出的垂直信息和第2—4級輸出的水平信息進(jìn)行累加，完成(3)式的計(jì)算，即后驗(yàn)概率信息的更新。整個(gè)流水線第1級需要1拍，第2—4級需要8拍，第5級需要1拍，又由于加入了2個(gè)Limit模塊來限幅，而一個(gè)Limit占用一拍，所以整個(gè)流水線需要12拍。本文選用的校驗(yàn)矩陣共有12層，即12個(gè)MPU模塊并行更新一次完整的迭代過程需要12個(gè)時(shí)鐘周期。這也是前面提到的修正后校驗(yàn)矩陣時(shí)，同一列位置上偏移值的差必須滿足不小于12的原因。文獻(xiàn)[10]中所提到的校驗(yàn)節(jié)點(diǎn)更新結(jié)構(gòu)中，一次校驗(yàn)節(jié)點(diǎn)的更新迭代就需要16個(gè)時(shí)鐘周期，對比文獻(xiàn)[10]的結(jié)構(gòu)，本文將修正因子運(yùn)算過程嵌入至第2—4級之中，由于本文五級流水線結(jié)構(gòu)上的優(yōu)勢，一次消息更新迭代僅需要12個(gè)時(shí)鐘周期，加快了收斂速度。

3 譯碼器性能及實(shí)現(xiàn)復(fù)雜度

本文設(shè)計(jì)譯碼器的實(shí)現(xiàn)方案以Xilinx公司Virtex系列開發(fā)板XC7VX485T芯片為硬件實(shí)現(xiàn)平臺，ISE 14.2為開發(fā)環(huán)境，使用Verilog HDL語言編程實(shí)現(xiàn)了 (8 192,4 096) 全并行分層QC-LDPC碼譯碼器的設(shè)計(jì)。譯碼器整體的時(shí)序仿真圖如圖9所示。

圖9 譯碼器整體時(shí)序仿真圖Fig.9 Decoder overall timing simulation

對譯碼器進(jìn)行綜合優(yōu)化及靜態(tài)時(shí)序分析，驗(yàn)證了譯碼器的正確性和高效性。表1為本文所設(shè)計(jì)譯碼器的實(shí)現(xiàn)復(fù)雜度。

模塊的關(guān)鍵路徑的延時(shí)為3.304 ns，則系統(tǒng)的工作頻率為302.7 MHz。譯碼速度，即吞吐量，計(jì)算式為

(8)

(8)式中：f為工作頻率；N為碼長；m為循環(huán)子矩陣大??；t為一次迭代消耗的時(shí)鐘周期數(shù)；iter為最大迭代次數(shù)。經(jīng)計(jì)算，最大迭代次數(shù)為10時(shí)，譯碼器的吞吐量可達(dá)473.2 Mbit/s。其他譯碼器的性能比較如表2所示。

表1 譯碼器實(shí)現(xiàn)復(fù)雜度Tab.1 Decoder implementation complexity

表2 譯碼器性能比較Tab.2 Decoder performance comparison

表2的性能對比證明了本文設(shè)計(jì)譯碼器的優(yōu)越性。與同類譯碼器[12-14]相比，資源消耗可以降低50%以上，吞吐量提升了2～3倍，無論是譯碼吞吐量、工作頻率還是資源消耗方面，本設(shè)計(jì)譯碼器都更為突出。相比于文獻(xiàn)[15]，在工作頻率以及資源消耗上占據(jù)明顯優(yōu)勢。

4 結(jié) 論

本文采用全并行分層最小和算法，提出了一種具有較高吞吐量、較低復(fù)雜度的分層譯碼器結(jié)構(gòu)，并在FPGA平臺上實(shí)現(xiàn)了基于CCSDS標(biāo)準(zhǔn)的 (8 192,4 096) LDPC碼譯碼器。本譯碼器主要具有以下優(yōu)點(diǎn)：①關(guān)鍵模塊MPU采用五級流水線結(jié)構(gòu)化設(shè)計(jì)，內(nèi)部的CNU單元同樣是一個(gè)流水線的更新過程，提高了系統(tǒng)工作頻率;②控制模塊狀態(tài)機(jī)被劃分為3個(gè)具有特定功能的小狀態(tài)機(jī)，嵌入到接收信道信息模塊、譯碼輸出模塊以及MPU模塊中，降低了控制模塊的設(shè)計(jì)復(fù)雜度，同時(shí)，每個(gè)模塊的路徑延遲得到了縮短，提高了整個(gè)系統(tǒng)的工作頻率;③優(yōu)化了模塊和存儲單元，使得譯碼器硬件資源有較高的利用率;④全并行的分層譯碼結(jié)構(gòu)，加快了譯碼器收斂速度，提高了譯碼吞吐量。表2的性能對比證明了本文設(shè)計(jì)譯碼器的優(yōu)越性。本文實(shí)現(xiàn)了碼長為8 192，碼率為1/2的QC-LDPC碼譯碼器，在Virtex7開發(fā)板上驗(yàn)證表明，吞吐量可達(dá)473.2 Mbit/s，存儲資源消耗僅為傳統(tǒng)部分并行結(jié)構(gòu)譯碼器的1/4。因此，本文提出的分層全并行結(jié)構(gòu)的QC-LDPC碼譯碼器同時(shí)具備高效、低復(fù)雜度、吞吐量大、收斂快等性能，一定程度解決了譯碼器吞吐量與資源消耗的矛盾。

參考文獻(xiàn)：

[1] KOU Yu, LIN Shu, FOSSORIER M P C. Low-density parity-check codes based on finite geometries: a rediscovery and new results[J].IEEE Transactions on Information Theory, 2001, 47(7): 2711-2736.

[2] ZHANG Kai, HUANG Xinming, WANG Zhongfeng. An area-efficient LDPC decoder architecture and implementation for CMMB systems[C]∥2009 20th IEEE International Conference on Application-specific Systems, Architectures and Processors.Boston:IEEE Press,2009:235-238.

[3] MANSOUR M M. A turbo-decoding message-passing algorithm for sparse parity-check matrix codes[J].IEEE Transactions on Signal Processing,2006,54(11):4376-4392.

[4] MANSOUR M M, SHANBHAG N R. High-Thoughput LDPC Decoders[J]. IEEE Transactions on Very Large Scale Integration Systems, 2003, 11(6): 976-996.

[5] LIAO Ruochen, FU Yuzhuo, LIU Ting. FPGA-Based High Throughput TDMP LDPC Decoder[J]. Computer Engineering and Technology, 2016(666): 94-101.

[6] YANG Lei, SHEN Manyuan, LIU Hui, et al. An FPGA implementation of low-density parity-check code decoder with multi-rate capability[C]∥Proceedings of the ASP-DAC 2005. Asia and South Pacific Design Automation Conference, 2005.Shanghai:IEEE Press, 2005: 760-763.

[7] 袁瑞佳, 白寶明. 基于FPGA的LDPC碼編譯碼器聯(lián)合設(shè)計(jì)[J]. 電子與信息學(xué)報(bào), 2012, 34(1): 38-44.

YUAN Ruijia, BAI Baoming. FPGA-based Joint Design of LDPC Encoder and Decoder[J]. Journal of Electrics & Information Technology, 2012, 34(1):38-44.

[8] 姚遠(yuǎn). 基于并行分層譯碼算法的LDPC譯碼器設(shè)計(jì)[D]. 上海：復(fù)旦大學(xué), 2013.

YAO Yuan. Design of LDPC Decoder Based on Parallel Layered Decoding Algorithm[D].Shanghai: Fudan University, 2013.

[9] 周健, 呂毅博, 洪少華，等.面向磁記錄信道的原模圖LDPC碼譯碼器的FPGA設(shè)計(jì)[J].重慶郵電大學(xué)學(xué)報(bào)：自然科學(xué)版, 2013, 25(6): 788-794.

ZHOU Jian, LV Yibo, HONG Shaohua,et al. Protograph-based LDPC Decoder Applied to Magnetic Recording Channel [J]. Journal of Chongqing University of Posts and Telecommunications: Natural Science Edition, 2013, 25(6): 788-794.

[10] 張順根, 仰楓帆. 基于FPGA的隨機(jī)構(gòu)造QC-LDPC分層譯碼器設(shè)計(jì)[J].無線電通信技術(shù), 2015, 41(1): 41-45.

ZHANG Shungen,YANG Fengfan.Design on Randomly Constructed QC-LDPC Layered Decoder Based on FPGA[J].Radio Communications Technology,2015, 41(1):41-45.

[11] ZHANG Kai, HUANG Xinming, WANG Zhongfeng. High-throughput layered decoder implementation for quasi-cyclic LDPC codes[J]. IEEE Journal on Selected Areas in Communications, 2009, 27(6)：985-994.

[12] 彭陽陽, 仰楓帆. 基于FPGA的QC-LDPC碼分層譯碼器設(shè)計(jì)[J]. 無線電工程, 2014, 44(1): 17-20.

PENG Yangyang, YANG Fengfan. Design on QC-LDPC Layered Decoder Based on FPGA[J]. Radio Engineering, 2014, 44(1):17-20.

[13] DING Hong, YANG Shuai, LUO Wu, et al. Design and implementation for high speed LDPC decoder with layered decoding[C]∥International Conference on Communications and Mobile Computing. Kunming: IEEE Press, 2009: 156-160.

[14] 云飛龍, 杜鋒, 朱宏鵬，等. 一種高吞吐量QC-LDPC碼譯碼器的FPGA實(shí)現(xiàn)[C]∥第七屆中國衛(wèi)星導(dǎo)航學(xué)術(shù)年會論文集.長沙：中國衛(wèi)星導(dǎo)航學(xué)術(shù)年會, 2016.

YUN Feilong, DU Feng, ZHU Hongpeng, et al. FPGA Implementation of a High-throughput QC-LDPC[C]∥The Seventh China Satellite Navigation Academic Annual Proceedings.Changsha, China: The Seventh Annual Meeting of China Satellite Navigation, 2016.

[15] SWAPNIL M, DAVID U, HOJEE K,et al. High-Throughput FPGA-based QC-LDPC Decoder Architecture[C]∥Vehicular Technology Conference. Boston, MA, USA :IEEE Press,2015：1-5.