LDPC短碼的對(duì)數(shù)域譯碼算法的FPGA實(shí)現(xiàn)研究*

李春騰 蔣宇中 楊光輝

(海軍工程大學(xué)電子工程學(xué)院 武漢 430033)

LDPC短碼的對(duì)數(shù)域譯碼算法的FPGA實(shí)現(xiàn)研究*

李春騰 蔣宇中 楊光輝

(海軍工程大學(xué)電子工程學(xué)院 武漢 430033)

LDPC碼不僅在保證通信的安全上占據(jù)重要的優(yōu)勢(shì),并且在信道環(huán)境相對(duì)較差的條件下展現(xiàn)出的巨大應(yīng)用前景。因此,有理由相信對(duì)LDPC碼進(jìn)行深入的研究有助于進(jìn)一步改善通信的質(zhì)量。文中重點(diǎn)闡述了隨機(jī)構(gòu)造的LDPC短碼的FPGA實(shí)現(xiàn)過(guò)程,采用復(fù)雜度較高的對(duì)數(shù)域譯碼算法來(lái)獲取較優(yōu)的譯碼性能。并且在實(shí)現(xiàn)的過(guò)程中,使用狀態(tài)機(jī)控制譯碼的各個(gè)模塊,并通過(guò)Modelsim軟件仿真獲取譯碼單元對(duì)應(yīng)的時(shí)序波形圖。

LDPC短碼; 對(duì)數(shù)域譯碼; FPGA

Class Number TP301

1 引言

隨著科技的不斷進(jìn)步,無(wú)線通信對(duì)信息傳輸速率的要求也逐步提高,因此逐漸將研究的重點(diǎn)轉(zhuǎn)移到LDPC的硬件實(shí)現(xiàn)上。目前,針對(duì)LDPC碼的各種譯碼芯片均已問(wèn)世。比如Flarion公司中引入的基于ASIC的V-LDPC方案,可以使譯碼器的吞吐量達(dá)10Gbps,這足以滿足實(shí)際通信中的要求。此外,FPGA中含有豐富的邏輯單元和存儲(chǔ)器資源,適合LDPC碼的硬件實(shí)現(xiàn),故在以FPGA作為L(zhǎng)DPC碼的主要硬件實(shí)現(xiàn)工具的研究上也有很大的發(fā)展[1～8]。

目前,針對(duì)LDPC碼的譯碼的硬件實(shí)現(xiàn),業(yè)內(nèi)普遍采用復(fù)雜度較低的最小和算法[9],特別是碼長(zhǎng)較長(zhǎng)的系統(tǒng)中,這樣做可以減少硬件資源的開(kāi)銷(xiāo),提高運(yùn)行速度。但如果在短碼中也采用這種算法,由于信息交換的頻次受限,再加上最小和算法中的簡(jiǎn)化運(yùn)算帶來(lái)的損失,會(huì)嚴(yán)重影響譯碼性能。本文研究隨機(jī)構(gòu)造的LDPC短碼的對(duì)數(shù)域譯碼算法[10],在運(yùn)算環(huán)節(jié)上有效地避免了性能損失。雖然該算法具有較高的復(fù)雜度,占用了較大的資源,但由于是短碼,仍然可以在通用的FPGA芯片上很好地工作,達(dá)到和C語(yǔ)言實(shí)現(xiàn)的對(duì)數(shù)域算法基本接近的性能。

2 譯碼實(shí)現(xiàn)的總體設(shè)計(jì)

譯碼的核心硬件控制關(guān)系示意圖如圖1所示,譯碼的實(shí)現(xiàn)過(guò)程如圖2所示。Decode模塊實(shí)際上也是通過(guò)控制狀態(tài)機(jī)State Machine來(lái)實(shí)現(xiàn)的,包括初始化單元(Initialization Unit,INU),校驗(yàn)點(diǎn)更新單元(Check Node processing Unit,CNU),變量點(diǎn)更新單元(Variable Node processing Unit,VNU),判決單元(Decision Unit,DEU)。ROM模塊起到地址轉(zhuǎn)換的作用,將順序地址轉(zhuǎn)換成譯碼過(guò)程所需的地址順序,h_p_ALG模塊是水平方向校驗(yàn)點(diǎn)的更新,v_p_ALG模塊是垂直方向變量點(diǎn)的更新,lratio表示初始化似然比,lr表示檢驗(yàn)點(diǎn)更新值,pr表示變量點(diǎn)更新值,LLR表示判決值。INU、CNU、VNU、DEU這四個(gè)模塊的主體分別是四個(gè)存儲(chǔ)器RAM,各個(gè)RAM所包含的要素與編碼存儲(chǔ)器的相同。h_p_ALG、v_p_ALG模塊實(shí)際上是更新節(jié)點(diǎn)模塊,調(diào)用更新所需的函數(shù)。下面根據(jù)圖2所示的流程圖對(duì)運(yùn)算處理模塊中的四個(gè)步驟進(jìn)行詳細(xì)說(shuō)明。

3 初始化單元(INU)和判決單元(DEU)

鑒于在編程時(shí),外部對(duì)lratio進(jìn)行初始化,待完成后轉(zhuǎn)入至譯碼運(yùn)算中,用lratio來(lái)對(duì)變量節(jié)點(diǎn)pr賦值,從而完成變量節(jié)點(diǎn)的初始化。因此,該譯碼初始化過(guò)程實(shí)際包含2個(gè)狀態(tài),即外部初始化狀態(tài)和變量節(jié)點(diǎn)初始化狀態(tài)。State Machine通過(guò)外部發(fā)送的Reset信號(hào),使譯碼過(guò)程首先進(jìn)入外部初始化狀態(tài)IDLE_STATE。在該狀態(tài)下,進(jìn)行譯碼相關(guān)信號(hào)的初始化:控制在DSP中還是譯碼模塊中操作的InitTestMem_Run信號(hào)置為高電平,迭代次數(shù)Iter置為0,控制算法開(kāi)始與結(jié)束的ALG_Stop信號(hào)置為低電平,初始化是否完成的Init_Finished信號(hào)置為低電平,進(jìn)行初始化還是運(yùn)算的Init_Iter信號(hào)置為低電平以及迭代是否結(jié)束的Iter_End信號(hào)置為低電平。當(dāng)外部所發(fā)送的InitTest_Run信號(hào)為低電平時(shí),說(shuō)明此時(shí)DSP正在進(jìn)行初始化；一旦該信號(hào)轉(zhuǎn)換為高電平,立即將Init_Finished信號(hào)置成高電平,以便跳出初始化的循環(huán)圈,結(jié)束外部初始化,狀態(tài)轉(zhuǎn)換為變量節(jié)點(diǎn)初始化狀態(tài)IDLE_STATE2。

在IDLE_STATE2下,設(shè)定InitTestMem_Run信號(hào)為低電平,轉(zhuǎn)入譯碼模塊中操作,該狀態(tài)下要為將初始化后的數(shù)據(jù)lratio賦值給pr作準(zhǔn)備,將lratio存儲(chǔ)器中的讀寫(xiě)控制信號(hào)Run_MemWriteRead_lratio置為低電平,pr存儲(chǔ)器中的讀寫(xiě)控制信號(hào)置為高電平,其中存儲(chǔ)器中的讀寫(xiě)控制信號(hào)的低電平代表讀狀態(tài),高電平代表寫(xiě)狀態(tài),初始化地址Run_LocAddr_lratio和變量點(diǎn)地址Run_LocAddr_pr均置為0,狀態(tài)轉(zhuǎn)換為初始化pr的狀態(tài)；由于校驗(yàn)矩陣的列重為3,故以3個(gè)數(shù)據(jù)為一組通過(guò)Run_LocAddr_pr進(jìn)行賦值,所以初始化pr的狀態(tài)其實(shí)包含3個(gè)子狀態(tài)。在第3個(gè)子狀態(tài)中增加判斷語(yǔ)句Run_LocAddr_pr是否小于校驗(yàn)矩陣總的節(jié)點(diǎn)個(gè)數(shù),判斷是否所有變量的pr值都初始化完畢。如果沒(méi)有,則返回第1個(gè)子狀態(tài)繼續(xù)操作,反之,則轉(zhuǎn)到CNU,進(jìn)行水平方向校驗(yàn)點(diǎn)的更新。

為了便于對(duì)INU單元在譯碼初始化狀態(tài)下的理解,通過(guò)Modelsim仿真得到該單元內(nèi)各信號(hào)的時(shí)序波形圖如圖3所示。從波形圖中可以清楚地看到譯碼初始化的兩個(gè)過(guò)程,圖中的紅線代表在此狀態(tài)下無(wú)效。

4 校驗(yàn)點(diǎn)更新單元(CNU)

在該單元下,主要完成校驗(yàn)節(jié)點(diǎn)的更新,與此過(guò)程緊密相關(guān)的是水平運(yùn)算單元h_p_ALG,下面先對(duì)該運(yùn)算單元進(jìn)行詳細(xì)介紹。

由校驗(yàn)節(jié)點(diǎn)的更新公式可知,算法原來(lái)是除本身節(jié)點(diǎn)外其他相關(guān)節(jié)點(diǎn)的雙曲tanh函數(shù)值的乘積,不利于硬件的實(shí)現(xiàn)。此處,采用將每個(gè)相關(guān)節(jié)點(diǎn)的雙曲函數(shù)取對(duì)數(shù)變換后再相加,之后再取指數(shù)運(yùn)算,避免了復(fù)雜的求積運(yùn)算。并且在對(duì)初始化概率進(jìn)行量化處理時(shí),已構(gòu)建一張64位的ROM,可以很容易得到相應(yīng)的對(duì)數(shù)和指數(shù)值。

從上述過(guò)程可以看到水平運(yùn)算單元主要包含2個(gè)模塊:第1個(gè)模塊為符號(hào)提取、雙曲變換取對(duì)數(shù)模塊(STL),第2個(gè)模塊為指數(shù)模塊。第1個(gè)模塊的功能關(guān)系圖如圖4所示。輸入節(jié)點(diǎn)的初始化概率值后,經(jīng)過(guò)該模塊,分別得到符號(hào)值和對(duì)數(shù)雙曲變換值。指數(shù)模塊就是指單純的指數(shù)變換。

下面采用校驗(yàn)節(jié)點(diǎn)的度數(shù)均為6的校驗(yàn)矩陣,將公式轉(zhuǎn)換成實(shí)現(xiàn)中的算法,水平運(yùn)算單元h_p_ALG的整體實(shí)現(xiàn)過(guò)程如圖5所示,其中名稱(chēng)相同的代表兩者之間存在連接關(guān)系。

由于在設(shè)計(jì)的過(guò)程中,考慮了迭代次數(shù)這一因素。因此,在第2次之后的迭代運(yùn)算,對(duì)校驗(yàn)節(jié)點(diǎn)更新的輸入為前一次運(yùn)算更新后的變量節(jié)點(diǎn)值(該過(guò)程即為譯碼下一步要進(jìn)行的變量節(jié)點(diǎn)的更新)。

在變量節(jié)點(diǎn)初始化結(jié)束狀態(tài)時(shí),對(duì)校驗(yàn)點(diǎn)更新做準(zhǔn)備工作,將pr存儲(chǔ)器中的Run_MemWriteRead_pr信號(hào)設(shè)為低電平,Run_LocAddr_pr信號(hào)設(shè)為0,Init_Iter信號(hào)設(shè)為高電平,代表進(jìn)入迭代運(yùn)算狀態(tài),控制水平和垂直運(yùn)算的Sel_vh_vp信號(hào)設(shè)為高電平,代表進(jìn)入水平方向校驗(yàn)節(jié)點(diǎn)的運(yùn)算,狀態(tài)轉(zhuǎn)換為校驗(yàn)節(jié)點(diǎn)運(yùn)算狀態(tài)。由于所采用的校驗(yàn)矩陣是行重為6的正則矩陣,所以在進(jìn)行校驗(yàn)點(diǎn)運(yùn)算時(shí),采用以6個(gè)數(shù)據(jù)為一組的方式進(jìn)行操作,并且采取邊運(yùn)算邊存儲(chǔ)數(shù)據(jù)的方法進(jìn)行,故校驗(yàn)節(jié)點(diǎn)運(yùn)算狀態(tài)其實(shí)包括20個(gè)子狀態(tài)。

前6個(gè)子狀態(tài)為從CPU中讀取初始化后的數(shù)據(jù)pr參與運(yùn)算。

子狀態(tài)7～9為等待狀態(tài),由于RAM可能會(huì)使讀取的數(shù)據(jù)發(fā)生延時(shí),故設(shè)置等待狀態(tài)待h_p_ALG模塊運(yùn)算結(jié)束。

第10個(gè)子狀態(tài)將Run_MemWriteRead_lr信號(hào)設(shè)為高電平,地址信號(hào)Run_LocAddr_lr設(shè)為0,并在此狀態(tài)下將h_p_ALG模塊的運(yùn)算結(jié)果提取至寄存器reg_lr_out(1…6)中,為下一步將更新后的lr數(shù)據(jù)寫(xiě)回DSP中作準(zhǔn)備,狀態(tài)轉(zhuǎn)移至第11個(gè)子狀態(tài)。

子狀態(tài)11～16為將寄存器reg_lr_out(1…6)中的數(shù)據(jù)仍然以6個(gè)為一組寫(xiě)回DSP中。

第17個(gè)子狀態(tài)為通過(guò)校驗(yàn)節(jié)點(diǎn)的地址信號(hào)Run_LocAddr_lr是否小于校驗(yàn)矩陣總的節(jié)點(diǎn)個(gè)數(shù)來(lái)判斷是否寫(xiě)完。如果沒(méi)有,則轉(zhuǎn)到等待子狀態(tài)18和19,待等待結(jié)束后返回子狀態(tài)10繼續(xù)進(jìn)行操作,如果寫(xiě)完則轉(zhuǎn)移子狀態(tài)20,繼續(xù)進(jìn)行垂直方向變量節(jié)點(diǎn)的更新。

為了便于對(duì)CNU單元在校驗(yàn)節(jié)點(diǎn)運(yùn)算狀態(tài)下的理解,通過(guò)Modelsim仿真得到該單元內(nèi)各信號(hào)的時(shí)序波形圖如圖6所示。圖中的紅線代表在此狀態(tài)下無(wú)效。

5 變量點(diǎn)更新單元(VNU)

鑒于在譯碼運(yùn)算中考慮了迭代次數(shù)這一因素,在表2中已介紹了該單元下所使用的部分信號(hào)功能。下面重點(diǎn)敘述與變量節(jié)點(diǎn)更新相關(guān)的是垂直運(yùn)算單元v_p_ALG。

由變量節(jié)點(diǎn)的更新公式可知,更新的變量節(jié)點(diǎn)值是指初始化概率值和與該節(jié)點(diǎn)相關(guān)的更新校驗(yàn)節(jié)點(diǎn)值之和。由判決公式可知,最終的判決結(jié)果為更新的變量節(jié)點(diǎn)值與該節(jié)點(diǎn)更新的校驗(yàn)節(jié)點(diǎn)值之和。下面采用變量節(jié)點(diǎn)的度數(shù)均為3的校驗(yàn)矩陣,將垂直運(yùn)算單元v_p_ALG的整體實(shí)現(xiàn)過(guò)程呈現(xiàn)如圖7所示。

下面詳細(xì)闡述VNU單元的實(shí)現(xiàn)過(guò)程,該單元的硬件連接關(guān)系如圖10所示。由于校驗(yàn)矩陣的列重為3,故在該單元下是以3個(gè)數(shù)據(jù)為一組進(jìn)行操作。在變量點(diǎn)運(yùn)算過(guò)程中,并不像校驗(yàn)點(diǎn)運(yùn)算那樣利用存儲(chǔ)器中的順序地址,而是需要調(diào)用ROM模塊將順序地址Run_LocAddr_pr轉(zhuǎn)換成變量點(diǎn)更新所需的運(yùn)算地址v_p_pr_addre。變量點(diǎn)運(yùn)算狀態(tài)包括8個(gè)子狀態(tài)。

第1個(gè)子狀態(tài)為準(zhǔn)備狀態(tài),將初始化Run_MemWriteRead_lratio信號(hào)置為低電平,將Run_MemWriteRead_lr信號(hào)置為低電平,Run_MemWriteRead_pr信號(hào)置為高電平,判決存儲(chǔ)器中的讀寫(xiě)控制信號(hào)Run_MemWriteRead_LLR置為高電平,Run_LocAddr_lratio、Run_LocAddr_lr、Run_LocAddr_pr以及判決地址Run_LocAddr_LLR均置為0,Sel_vh_vp信號(hào)置為低電平,表明進(jìn)入垂直運(yùn)算。

第2個(gè)子狀態(tài)到第4個(gè)子狀態(tài)為從DSP中讀取更新后的lr值參與v_p_ALG模塊的運(yùn)算,這3個(gè)狀態(tài)中僅進(jìn)行l(wèi)ratio及更新后的lr值的讀操作。

第5個(gè)子狀態(tài)為將運(yùn)算后的數(shù)據(jù)提取至寄存器reg_pr_out(1…3)中,為下一步將更新后的pr值寫(xiě)回DSP作準(zhǔn)備,同時(shí)Run_LocAddr_LLR進(jìn)行加1運(yùn)算。

子狀態(tài)6～8通過(guò)v_p_pr_addre地址將子狀態(tài)2～4下得到的reg_pr_out(1…3)中的pr值寫(xiě)回DSP,仍然是以3個(gè)數(shù)據(jù)為一組,同時(shí)繼續(xù)讀取lratio及更新后的lr值參與v_p_ALG模塊的運(yùn)算；在第8個(gè)子狀態(tài)下,通過(guò)v_p_pr_addre地址將子狀態(tài)6～8下得到的pr值提取至寄存器reg_pr_out(1…3)中,并且判決存儲(chǔ)器通過(guò)Run_LocAddr_LLR亦寫(xiě)回DSP中存儲(chǔ),同時(shí)增加判斷語(yǔ)句:通過(guò)Run_LocAddr_pr是否小于校驗(yàn)矩陣總的節(jié)點(diǎn)個(gè)數(shù)來(lái)判斷是否寫(xiě)完。如果沒(méi)有,則返回子狀態(tài)6繼續(xù)邊運(yùn)算邊存數(shù)據(jù),如果寫(xiě)完則轉(zhuǎn)移到測(cè)試狀態(tài),同時(shí)將迭代次數(shù)Iter進(jìn)行加1操作,ALG_Stop信號(hào)置為高電平。

在該組狀態(tài)下,同時(shí)完成了DEU的操作,將v_p_ALG模塊運(yùn)算后得到的LLR數(shù)據(jù)寫(xiě)回DSP中。在向DSP寫(xiě)的過(guò)程中,鑒于所采用的校驗(yàn)矩陣的列重為3,因此最終得到的每個(gè)變量的最大可能取值即LLR數(shù)據(jù)的個(gè)數(shù)是總的節(jié)點(diǎn)個(gè)數(shù)的三分之一,故每隔3個(gè)子狀態(tài)提取一個(gè)LLR數(shù)據(jù)。

在變量節(jié)點(diǎn)運(yùn)算狀態(tài)下,不僅完成了變量節(jié)點(diǎn)的更新,還得到了譯碼的最終實(shí)現(xiàn)結(jié)果,下面將該狀態(tài)下的時(shí)序波形圖呈現(xiàn)于圖8中。

波形圖中的紅線代表在此狀態(tài)下無(wú)效,通過(guò)ALG_Stop信號(hào)從低電平變成高電平,可以清楚地看到譯碼過(guò)程結(jié)束。將上述譯碼實(shí)現(xiàn)過(guò)程的狀態(tài)轉(zhuǎn)移圖呈現(xiàn)于圖9所示。在譯碼的測(cè)試狀態(tài)中,設(shè)置判斷語(yǔ)句,判斷Iter信號(hào)是否達(dá)到預(yù)設(shè)的最大迭代次數(shù)。若尚未達(dá)到,則返回校驗(yàn)節(jié)點(diǎn)運(yùn)算狀態(tài),繼續(xù)進(jìn)行下一次迭代運(yùn)算；反之,將Iter_End信號(hào)置為高電平,代表譯碼過(guò)程結(jié)束。

6 結(jié)語(yǔ)

本文主要研究隨機(jī)構(gòu)造的LDPC短碼,從通信的安全性角度出發(fā),采用犧牲復(fù)雜度來(lái)?yè)Q取較優(yōu)性能的對(duì)數(shù)域譯碼算法對(duì)其實(shí)現(xiàn)。在譯碼算法的校驗(yàn)節(jié)點(diǎn)和變量節(jié)點(diǎn)的更新過(guò)程中,采取邊運(yùn)算邊存儲(chǔ)的方法,取代之前全部算完之后再存儲(chǔ),加快了運(yùn)算效率。同時(shí),通過(guò)Modelsim軟件得到的時(shí)序波形圖可以清晰的看到譯碼的各個(gè)狀態(tài)過(guò)程。下一步將尋求新的譯碼算法,爭(zhēng)取在獲取較優(yōu)性能的同時(shí)保證較少的運(yùn)算量。

[1] Chen X H, Kang J Y, Lin S. Memory system optimization for FPGA-based implementation of quasi-cyclic LDPC codes decoders[J]. IEEE Transactions on Circuits and Systems I:Regular Papers,2011,58(1):98-111.

[2] Chen X H, Lin S, Akelli A V. QSN-a simple circular-shift network for reconfigurable quasi-cyclic LDPC decoders[J]. IEEE:Transactions on Circuits and Systems II:Express Briefs,2010,57(10):782-786.

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

[4] Chen Y, Chen X H, Zhao Y, et al. Design and implementation of multi-mode QC-LDPC decoder[C]//2010 12th IEEE International Conference on Communication Technology,Nanjing:2010:1145-1148.

[5] 管武,喬華,董明科,等. LDPC碼高速譯碼器的設(shè)計(jì)與實(shí)現(xiàn)[J].電子與系統(tǒng)學(xué)報(bào),2009,14(2):1-6.

[6] Darabiha A, Carusone A C, Kschischang F R. Multi-Gbit/sec low density parity check decoders with reduced interconnect complexity[C]//IEEE International Symposium on Circuits and Systems(ISCAS).2005,5194-5197.

[7] Hocevar D E. A reduced complexity decoder architecture via layered decoding of LDPC codes[C]//IEEE Workshop on Signal Processing Systems. USA. Oct. 2004,107-112.

[8] Chen X H,Kang J Y,Lin S. Accelerating FPGA-based emulation of quasi-cyclic LDPC codes with vector processing[C]//Proceedings of the Conference on Design Automation and Test. Apr. 2009,1530-1535.

[9] 野曉東,馬林華,王為民.整數(shù)運(yùn)算的LDPC碼最小和譯碼算法[J].通信學(xué)報(bào),2010,31(6):106-111.

[10] 袁東風(fēng),張海剛.LDPC碼理論與應(yīng)用[M].北京:北京人民郵電出版社,2008.

FPGA Implementation of Log-Domain Decoding Algorithm about LDPC Short Codes

LI Chunteng JIANG Yuzhong YANG Guanghui

(College of Electronic Engineering, Naval University of Engineering, Wuhan 430033)

LDPC codes not only play an important role in ensuring the security of communication, but also show a great prospect in the relatively poor channel environment. Therefore, there is reason to believe that further research on LDPC codes will help to improve the quality of communication. In this paper, the FPGA implementation of LDPC shortcodes with random structure is focused on, and the logarithm domain decoding algorithm with higher complexity is adopted to obtain better decoding performance. And in the process of realization, the state machine is used to control the decoded modules, and the corresponding sequential waveform of the decoding unit are obtained by Modelsim software.

LDPC shortcodes, log-domain decoding, FPGA

2016年10月8日,

2016年11月15日

李春騰,男,碩士研究生,研究方向:通信信號(hào)處理。蔣宇中,男,教授,研究方向:通信信號(hào)處理。楊光輝,男,碩士研究生,研究方向:通信信號(hào)處理。

TP301

10.3969/j.issn.1672-9730.2017.04.011