LDPC碼數(shù)據(jù)分配通用模塊設(shè)計(jì)方案

王 健，李集林，戰(zhàn)勇杰

（北京衛(wèi)星信息工程研究所 北京 100083）

近幾年，人們對(duì)可靠高效的信息傳輸和存儲(chǔ)技術(shù)提出了越來(lái)越高的要求。差錯(cuò)控制編碼作為一種糾正由信道噪聲帶來(lái)傳輸錯(cuò)誤的有效方式，被廣泛應(yīng)用與數(shù)字通信和存儲(chǔ)等領(lǐng)域。 Low-Density Parity-Check（LDPC）碼[1-3]發(fā)明于上世紀(jì) 60年代初期，它是一類(lèi)性能接近香農(nóng)極限的差錯(cuò)控制編碼，采用置信傳播的譯碼方式進(jìn)行譯碼[4]。隨著VLSI和計(jì)算機(jī)技術(shù)革命性進(jìn)步的到來(lái)，LDPC碼的實(shí)現(xiàn)成為了可能，并且由于在AWGN信道下的極佳誤碼性能和高并行度實(shí)現(xiàn)引起了人們的強(qiáng)烈關(guān)注[5]。目前，LDPC碼的普及程度大大增加，很多標(biāo)準(zhǔn)也都將LDPC碼納入進(jìn)來(lái)，這都導(dǎo)致了與LDPC碼譯碼的相關(guān)課題與日俱增，隨之而來(lái)的問(wèn)題是大量的重復(fù)性的開(kāi)發(fā)工作，因此需要將一些共性的開(kāi)發(fā)工作進(jìn)行通用的模塊化設(shè)計(jì)，以提高開(kāi)發(fā)效率。

1 傳統(tǒng)的譯碼方案在通用性方面的不足

在LDPC碼的實(shí)現(xiàn)過(guò)程中，水平運(yùn)算結(jié)果利用4維定位方法，存儲(chǔ)了最小值、次小值、最小值位置和符號(hào)位。然而像CCSDS近地通信碼[6-7]這樣的LDPC碼的校驗(yàn)矩陣中的每個(gè)循環(huán)子矩陣都有兩組1，它們都按照準(zhǔn)循環(huán)的方式排列，如圖1所示。

圖中所示Q為校驗(yàn)矩陣的一個(gè)列重為2的循環(huán)子矩陣，該矩陣可以拆分成兩個(gè)列重為1的循環(huán)子矩陣Q1和Q2，這一結(jié)構(gòu)對(duì)下文所述的數(shù)據(jù)分配策略和改進(jìn)的垂直運(yùn)算過(guò)程有決定性的影響。

圖2中給出了一個(gè)循環(huán)子矩陣數(shù)據(jù)讀取的示意圖。從該圖中可以看出，在實(shí)線所示的初始狀態(tài)時(shí)，讀取的數(shù)據(jù)順序是存儲(chǔ)器1中數(shù)據(jù)在前而存儲(chǔ)器2中的數(shù)據(jù)在后，但是到了虛線所示的時(shí)刻，讀取的數(shù)據(jù)順序變成了存儲(chǔ)器2中的數(shù)據(jù)在前，存儲(chǔ)器1中的數(shù)據(jù)在后。

圖1 CCSDS近地通信標(biāo)準(zhǔn)子矩陣示意圖Fig.1 Matrix diagram of the CCSDS near earthcommunication standard

圖2 循環(huán)子矩陣行數(shù)據(jù)讀取順序變化圖Fig.2 Order of reading data from cyclic submatrix in row order

在每個(gè)循環(huán)子矩陣中只有一組1或沒(méi)有1的情況下，只需要按照存儲(chǔ)器中數(shù)據(jù)存儲(chǔ)的順序讀取，然后進(jìn)行水平運(yùn)算即可，然而若循環(huán)子矩陣中的1不止一組的時(shí)候，數(shù)據(jù)的讀取就會(huì)發(fā)生混亂，有時(shí)存儲(chǔ)器1的數(shù)據(jù)在前，而有時(shí)存儲(chǔ)器2中的數(shù)據(jù)在前，這對(duì)判斷最小值屬于哪個(gè)存儲(chǔ)器極為不利。

因此需要開(kāi)發(fā)一種通用化的辨識(shí)數(shù)據(jù)先后順序的模塊，該模塊附著在校驗(yàn)矩陣中的每一個(gè)列塊上，對(duì)輸出的數(shù)據(jù)自動(dòng)做好標(biāo)識(shí)，使得水平運(yùn)算的結(jié)果能夠精確的反應(yīng)數(shù)據(jù)的來(lái)源。

2 文中所采用的范例碼

基于 EG（歐式幾何）的 QC（準(zhǔn)循環(huán)）LDPC碼屬于 QC LDPC碼，該類(lèi)碼的構(gòu)造是基于歐式幾何有限域分解的。（8176，7154）LDPC碼最初是為NASA設(shè)計(jì)的，它是一個(gè)規(guī)則的 QC LDPC 碼，行重 32，列重 4。 目前（8176，7154）LDPC 碼是CCSDS推薦的近地通信碼，它具有很好的規(guī)則性，目前已被應(yīng)用于遙感衛(wèi)星等航天器的近地通信領(lǐng)域。

本部分內(nèi)容給出的 CCSDS近地通信 （8176，7154）QCLDPC碼的譯碼方法，同樣適用于其他的每個(gè)循環(huán)子矩陣中有1組或2組1的QC-LDPC碼情況。

3 文中所采用的譯碼算法

LDPC碼的譯碼算法主要分為軟譯碼算法和硬譯碼算法，軟譯碼算法主要是指Gallager最早提出的LDPC碼概率譯碼算法、BP算法以及BP算法的改進(jìn)型最小和算法；硬譯碼算法主要是指BF算法。

采用軟譯碼算法譯碼獲得的編碼增益比較高，在絕大多數(shù)情況下，眾多軟譯碼算法中具備實(shí)現(xiàn)價(jià)值的譯碼方法之一仍是BP算法的改進(jìn)算法之一，最小和算法。傳統(tǒng)最小和算法的水平運(yùn)算公式。

垂直運(yùn)算公式

判決公式

后來(lái)人們改進(jìn)了最小和算法，提出了Normalized BP和Offset BP兩種算法，這兩種算法在本質(zhì)上是等價(jià)的，都極大地改進(jìn)了最小和算法的譯碼精度，使得最小和算法的編碼增益更加接近傳統(tǒng)的BP算法，目前這兩種算法中以Normalized BP算法應(yīng)用較為廣泛。文中采用了Normalized BP算法，圖3給出了Normalized BP的參數(shù)選擇情況，如圖所示，在參數(shù)值為1.25時(shí)得到了最小和算法的最好修正結(jié)果，但是通常在實(shí)現(xiàn)過(guò)程中，為了利于硬件功能的實(shí)現(xiàn)，會(huì)將（1/λk）的值設(shè)為0.75，這樣便于硬件乘法的實(shí)現(xiàn)。

圖3 Normalized BP的參數(shù)選擇Fig.3 Selection of parameter in Normalized BP

硬件實(shí)現(xiàn)的過(guò)程中該參數(shù)的實(shí)現(xiàn)手段如圖4所示。

圖4 Normalized BP算法參數(shù)的硬件實(shí)現(xiàn)方案Fig.4 Parameter of Normalized BP in hardware implementation

經(jīng)過(guò)對(duì)原數(shù)值的兩次移位，得到該數(shù)值的四分值，通過(guò)減法達(dá)到（1/λk）為 0.75 的目的。

4 通用化模塊設(shè)計(jì)

下面的討論不失一般性，以每個(gè)循環(huán)子矩陣中有3組1為例進(jìn)行說(shuō)明。

如圖 5所示。A，B，C 3條線從“初始列號(hào)”開(kāi)始向右側(cè)進(jìn)行 編 排 ， 由 于 C線 的 ver_pos_C（ver_pos_A、ver_pos_B、ver_pos_C分別指循環(huán)子矩陣中每組1的列初始位置）值最大，即C線在最右端，這也就意味著在經(jīng)過(guò)511－1－ver_pos_C（511是每個(gè)循環(huán)子矩陣的大?。┬械倪\(yùn)算之后，C線首先將要從最左邊重新開(kāi)始循環(huán)。因此，下面進(jìn)行的數(shù)據(jù)初始化順序從 A，B，C，變?yōu)?C，A，B，以此類(lèi)推。

圖5 循環(huán)子矩陣1位置排列圖Fig.5 Position of“1” in cyclic submatrix

總而言之，每當(dāng)排在最右側(cè)的一條線到達(dá)最右側(cè)的列時(shí)，下一步的CNU運(yùn)算就將其變?yōu)楸咀泳仃嚨淖钕忍幚淼臄?shù)據(jù)。因?yàn)橛羞@樣的運(yùn)行規(guī)律，于是形象的稱這種運(yùn)行方式為“反彈”。即，每當(dāng)排在最右側(cè)的線碰撞到循環(huán)子矩陣的右側(cè)壁時(shí)便發(fā)生“反彈”，橫向處理數(shù)據(jù)的順序便進(jìn)行一次向右的循環(huán)移位，將最右側(cè)線的數(shù)據(jù)移到最左邊，其他的數(shù)據(jù)順序不變。

如此循環(huán)，直到把該循環(huán)子矩陣中所有的“1”位置全部處理完畢。每當(dāng)循環(huán)子矩陣中發(fā)生一次“碰壁”后“定位位”就加1。

想要知道每條線橫向的先后順序就需要用到前面提到的“穿越”方法。首先確定3條水平直線，3條水平直線位于hor_pos_A，hor_pos_B，hor_pos_C 位置上， 記為 hor_A，hor_B，hor_C，如圖 5所示。A，B，C 3條線從“初始行號(hào)”位置開(kāi)始向右側(cè)進(jìn)行編排，A，B，C中的每條線，每當(dāng)穿越hor_A，hor_B，hor_C中的直線時(shí)，A，B，C的橫向計(jì)數(shù)便加1，因?yàn)槊看┰揭淮纬旧碇獾木€時(shí)，在它左邊就多一條線。因此本方法稱之為“穿越”。

先以C線為例進(jìn)行說(shuō)明。C線從hor_pos_C點(diǎn)開(kāi)始，向右側(cè)移動(dòng)，當(dāng)C線的行號(hào)“穿越”第一個(gè)除hor_C以外的水平直線hor_B的時(shí)候，此時(shí)C線上數(shù)據(jù)的編號(hào)加1。

5 加入通用化模塊的高速譯碼實(shí)現(xiàn)方案

從上面的分析的出結(jié)論，當(dāng)存儲(chǔ)器內(nèi)的數(shù)據(jù)進(jìn)行向右側(cè)的循環(huán)移位的時(shí)候，每當(dāng)?shù)竭_(dá)最右側(cè)，通用定位模塊檢測(cè)到這一信息便將通用定位模塊的輸出加1。存儲(chǔ)在定位位內(nèi)。具體說(shuō)明參見(jiàn)如圖6所示。

圖6 加入通用定位模塊后的數(shù)據(jù)組成Fig.6 Construction of data after accumulating generalized module

該圖說(shuō)明了加入通用化定位模塊后的數(shù)據(jù)組成。仍以圖2所述矩陣為例，而且列初始位置小的一組1的數(shù)據(jù)從存儲(chǔ)器1中讀出，列初始位置大的一組1從存儲(chǔ)器2中讀出。當(dāng)數(shù)據(jù)初始化到兩個(gè)存儲(chǔ)器內(nèi)之后，進(jìn)行水平運(yùn)算的時(shí)候，首先提取第0行的數(shù)據(jù)以實(shí)線表示，此時(shí)的通用定位模塊的定位位輸出是0，輸出到CNU進(jìn)行運(yùn)算的數(shù)據(jù)前端的定位位也是0。隨著數(shù)據(jù)讀取的進(jìn)行，當(dāng)進(jìn)行到以虛線表示的第2行進(jìn)行數(shù)據(jù)讀取的時(shí)候，存儲(chǔ)器1對(duì)應(yīng)那組1達(dá)到了存儲(chǔ)器的還沒(méi)有到達(dá)存儲(chǔ)器的最右側(cè)，而此時(shí)從存儲(chǔ)器2中讀出的數(shù)據(jù)已經(jīng)經(jīng)過(guò)了該存儲(chǔ)器的最右側(cè)，開(kāi)始重新從最左邊讀數(shù)，因此定位位被通用定位模塊加1，變?yōu)?。

這樣進(jìn)行數(shù)據(jù)的讀取工作，直到讀完該循環(huán)子矩陣中所有的數(shù)據(jù)，所有讀出的數(shù)據(jù)都在首位增加了一個(gè)“定位位”，然后被送往CNU參與水平運(yùn)算。

增加了通用定位模塊對(duì)CNU的結(jié)構(gòu)也有所影響。文獻(xiàn)[6－10]中曾給出CNU運(yùn)算結(jié)果的四維存儲(chǔ)方法，存儲(chǔ)的信息包括最小值，次小值，最小值的位置和符號(hào)位，該存儲(chǔ)方法大大節(jié)約了存儲(chǔ)器開(kāi)銷(xiāo)。然而當(dāng)每個(gè)循環(huán)子矩陣中不止有一組1的時(shí)候，采用了通用化的定位模塊，從存儲(chǔ)器中讀出的數(shù)據(jù)也增加了一位“定位位”，此時(shí)的CNU結(jié)構(gòu)需要發(fā)生改變，來(lái)適應(yīng)做出的調(diào)整。具體變化如圖7所示。

圖中的輸入端數(shù)據(jù)的頭部都加入了一位“定位位”，該位不參與CNU的比較運(yùn)算過(guò)程，因此單獨(dú)將改為取出，在圖中最下方標(biāo)記出來(lái)。

若每個(gè)循環(huán)子矩陣中有兩組1，使用圖 7中的CNU進(jìn)行運(yùn)算的時(shí)候，CNU的輸入端總是把每個(gè)列塊對(duì)應(yīng)的兩個(gè)M存儲(chǔ)器中的存儲(chǔ)器1連接在比較器的上方接口，存儲(chǔ)器2連接在比較器的下方接口，例如D000連接第一列塊的存儲(chǔ)器1，D001連接第一列塊的存儲(chǔ)器2。這樣進(jìn)行的排列在“位置標(biāo)記”模塊的輸出端可以得到最小值的位置是在D000～D111中的哪一個(gè)。然后將這一輸出前加上該列塊的“定位位”信息進(jìn)行存儲(chǔ)，這一行數(shù)據(jù)的其他“定位位”信息全部刪除。

圖7 加入通用定位模塊后的CNU結(jié)構(gòu)Fig.7 Construction of CNU after accumulating generalized module

在垂直運(yùn)算的過(guò)程中，需要利用上述信息確定求列和時(shí)參與運(yùn)算數(shù)據(jù)的具體位置。列運(yùn)算的實(shí)現(xiàn)方案如圖8所示?，F(xiàn)在假設(shè)進(jìn)行循環(huán)子矩陣的第一列的列運(yùn)算，需要得到的信息是第1列兩個(gè)數(shù)據(jù)的值。下面以第2行第1列的數(shù)據(jù)為例進(jìn)行說(shuō)明。

圖8 列運(yùn)算中數(shù)據(jù)的讀取與識(shí)別過(guò)程Fig.8 Construction of data after accumulating generalized module

第2行的數(shù)據(jù)經(jīng)過(guò)水平運(yùn)算后存儲(chǔ)在R存儲(chǔ)器中的對(duì)應(yīng)位置上，該位置存儲(chǔ)信息的格式如圖中最左側(cè)所示。若水平運(yùn)算求得的最小值不在該子矩陣的列塊范圍內(nèi)，那么該子矩陣中所有的數(shù)據(jù)全部以該行最小值輸出參與垂直運(yùn)算。

但是若水平運(yùn)算求得的最小值在該子矩陣的列塊內(nèi)，那么就需要用“穿越”的方法確定所需數(shù)據(jù)在該列塊中是水平方向上的第幾個(gè)數(shù)據(jù)。確定了這一點(diǎn)后，就能夠利用水平運(yùn)算的結(jié)果中的“定位位”來(lái)判斷該值是最小值還是次小值了。

從整個(gè)實(shí)現(xiàn)過(guò)程中可以看出，該通用模塊引入之后，可以通過(guò)流水的操作來(lái)消除對(duì)速度的影響，而且該模塊的引入沒(méi)有對(duì)存儲(chǔ)資源構(gòu)成任何多余的消耗。

另外從該方法的實(shí)現(xiàn)過(guò)程可以看出，該方法適用于BP算法、最小和算法以及最小和算法的改進(jìn)算法，所以該方法也具有良好的算法通用性。

通過(guò)ISE中Xinlin公司V5-330芯片上的仿真可以看出該方法的資源消耗情況。時(shí)鐘頻率120 MHz。

6 結(jié)束語(yǔ)

本章還介紹了通用化模塊的設(shè)計(jì)方法，針對(duì)循環(huán)子矩陣中不止有一組1的情況，利用了校驗(yàn)矩陣中循環(huán)子矩陣的自身特點(diǎn)，設(shè)計(jì)了能夠自動(dòng)識(shí)別1排列情況的模塊，以利于垂直運(yùn)算過(guò)程中自動(dòng)調(diào)用水平運(yùn)算的結(jié)果。該模塊的加入不會(huì)對(duì)譯碼速度和存儲(chǔ)資源造成任何消耗，而且有助于未來(lái)成熟高效地開(kāi)發(fā)高速譯碼設(shè)備。

表1 實(shí)現(xiàn)資源數(shù)據(jù)Tab.1 Im plem entation resource data

[1]Gallager R G.Low-density parity-check codes[J].IRE Transactions on Information Theory，1962（IT8）：21-28.

[2]MacKay D J C，Neal R M.Near Shannon limit performance of low density parity check codes[J].Electro Lett，1996，32（18）：96-99.

[3]Zhang T.Efficient VLSI architectures for error-correction coding[D].University of Minnesota，2002.

[4]LIU Z，Pados D A.A decoding algorithm for finite-geometry LDPC codes[J].IEEE Trans.Commun.，2005，53（3）：415-421.

[5]JJANG M，ZHAO C，SHI Z，et al.An improvement on the modified weighted bit-flipping decoding algorithm for LDPC codes[J].IEEE Commun.Lett.，2005（9）：814-816.

[6]CCSDS標(biāo)準(zhǔn) 131.1-O-2[S]， 2007.

[7]SHU Lin.Channel Codes Classical and Modern[M].Cambridge University Press，2009.

[8]CUI Zhi-qiang.Low-Complexity High-Speed VLSI Design of Low-Density Parity-Check Decoders.[D].Oregon State University，2007.

[9]LAN L，ZENG L-Q，TAI Y Y，et al.Construction of quasicyclic LDPC codes for AWGN and binary erasure channels:a finite field approach[J].IEEE Trans.Inf.Theory，2007，53（7）：2429-2458.

[10]陳旭燦.改進(jìn)的LDPC譯碼算法研究[J].電子科技大學(xué)學(xué)報(bào)，2010，5（7）：31-38.CHEN Xu-can.Research of modified LDPC decoding arithmetic[J].Journal of University of Electronic Science and Technology of China，2010，5（7）：31-38.

[11]Smarandache R，Vontobel P.Pseudo-codeword analysis of tanner graphs from projective and euclidean planes[J].IEEE Trans.Inf.Theory，2007，53（7）：2376-2393.

[12]LIU L，SHI C-J.Sliced message passing:high throughput overlapped decoding of high-rate low-density parity-check codes[J].IEEE Trans.Circuits and Syst.I，2008，545（11）：3697-3710.