摘要:上世紀60年代初,香農(nóng)的學生Gallager在他的博士畢業(yè)論文中首次提出了LDPC碼的概念和完整的譯碼方法,但是直到上世紀末期,隨著LDPC碼譯碼理論的進步和計算機技術的發(fā)展,LDPC碼才以其優(yōu)良的誤碼性能和良好的可實現(xiàn)性成為人們研究的焦點。針對QC類LDPC碼進行研究的時候,注意到很多碼的循環(huán)子矩陣中不只有一組1,這就產(chǎn)生了水平運算后判斷運算結果屬于哪個存儲模塊的問題;另外,由于校驗矩陣中每個循環(huán)子矩陣的列初始位置都是不同的,而且通常LDPC碼的校驗矩陣的循環(huán)子矩陣的數(shù)目都是非常龐大的,因此如果通過程序固化的方法,不但容易出現(xiàn)不易排查的錯誤,而且開發(fā)效率會大大下降。為解決該問題,并將解決方案通用化,文中以校驗矩陣中循環(huán)子矩陣中1的排列特點為研究對象,找到引起變化的量之間的共性特征,從而實現(xiàn)通用化模塊的設計。
關鍵詞:LDPC;通用;準循環(huán);數(shù)據(jù)分配
近幾年,人們對可靠高效的信息傳輸和存儲技術提出了越來越高的要求。差錯控制編碼作為一種糾正由信道噪聲帶來傳輸錯誤的有效方式,被廣泛應用與數(shù)字通信和存儲等領域。Low-Density Parity-Check(LDPC)碼發(fā)明于上世紀60年代初期,它是一類性能接近香農(nóng)極限的差錯控制編碼,采用置信傳播的譯碼方式進行譯碼。隨著VLSI和計算機技術革命性進步的到來,LDPC碼的實現(xiàn)成為了可能,并且由于在AWGN信道下的極佳誤碼性能和高并行度實現(xiàn)引起了人們的強烈關注。目前,LDPC碼的普及程度大大增加,很多標準也都將LDPC碼納入進來,這都導致了與LDPC碼澤碼的相關課題與日俱增,隨之而來的問題是大量的重復性的開發(fā)工作,因此需要將一些共性的開發(fā)工作進行通用的模塊化設計,以提高開發(fā)效率。
1 傳統(tǒng)的譯碼方案在通用性方面的不足
在LDPC碼的實現(xiàn)過程中,水平運算結果利用4維定位方法,存儲了最小值、次小值、最小值位置和符號位。然而像CCSDS近地通信碼這樣的LDPC碼的校驗矩陣中的每個循環(huán)子矩陣都有兩組1,它們都按照準循環(huán)的方式排列,如圖1所示。
圖中所示0為校驗矩陣的一個列重為2的循環(huán)子矩陣,該矩陣可以拆分成兩個列重為1的循環(huán)子矩陣Q1和Q2,這一結構對下文所述的數(shù)據(jù)分配策略和改進的垂直運算過程有決定性的影響。
圖2中給出了一個循環(huán)子矩陣數(shù)據(jù)讀取的示意圖。從該圖中可以看出,在實線所示的仞始狀態(tài)時,讀取的數(shù)據(jù)順序是存儲器1中數(shù)據(jù)在前而存儲器2中的數(shù)據(jù)在后,但是到了虛線所示的時刻,讀取的數(shù)據(jù)順序變成了存儲器2中的數(shù)據(jù)在前,存儲器1中的數(shù)據(jù)在后。
在每個循環(huán)子矩陣中只有一組1或沒有1的情況下,只需要按照存儲器中數(shù)據(jù)存儲的順序讀取,然后進行水平運算即可,然而若循環(huán)子矩陣中的1不止一組的時候,數(shù)據(jù)的讀取就會發(fā)生混亂,有時存儲器1的數(shù)據(jù)在前,而有時存儲器2中的數(shù)據(jù)在前,這對判斷最小值屬于哪個存儲器極為不利。
因此需要開發(fā)一種通用化的辨識數(shù)據(jù)先后順序的模塊,該模塊附著在校驗矩陣中的每一個列塊上,對輸出的數(shù)據(jù)自動做好標識,使得水平運算的結果能夠精確的反應數(shù)據(jù)的來源。
2 文中所采用的范例碼
基于EG(歐式幾何)的QC(準循環(huán))LDPC碼屬于QCLDPC碼,該類碼的構造是基于歐式幾何有限域分解的。(8176,7154)LDPC碼最初是為NASA設計的,它是一個規(guī)則的QC LDPC碼,行重32,列重4。目前(8176,7154)LDPC碼是CCSDS推薦的近地通信碼,它具有很好的規(guī)則性,目前已
被應用于遙感衛(wèi)星等航天器的近地通信領域。
本部分內(nèi)容給出的CCSDS近地通信(8176,7154)QC-LDPC碼的譯碼方法,同樣適用于其他的每個循環(huán)子矩陣中有1組或2組1的OC-LDPC碼情況。
3 文中所采用的譯碼算法
LDPC碼的譯碼算法主要分為軟譯碼算法和硬譯碼算法,軟譯碼算法主要是指Gallager最早提出的LDPC碼概率譯碼算法、BP算法以及BP算法的改進型最小和算法;硬譯碼算法主要是指BF算法。
采用軟譯碼算法澤碼獲得的編碼增益比較高,在絕大多數(shù)情況下,眾多軟譯碼算法中具備實現(xiàn)價值的譯碼方法之一仍是BP算法的改進算法之一,最小和算法。傳統(tǒng)最小和算法的水平運算公式。
后來人們改進了最小和算法,提出了Normalized BP和Offset BP兩種算法,這兩種算法在本質(zhì)上是等價的,都極大地改進了最小和算法的譯碼精度,使得最小和算法的編碼增益更加接近傳統(tǒng)的BP算法,目前這兩種算法中以NormalizedBP算法應用較為廣泛。文中采用了Norma lized BP算法,圖3給出了Normalized BP的參數(shù)選擇情況,如圖所示,在參數(shù)值為1.25時得到了最小和算法的最好修正結果,但是通常在實現(xiàn)過程中,為了利于硬件功能的實現(xiàn),會將(1/λk)的值設為0.75,這樣便于硬件乘法的實現(xiàn)。
硬件實現(xiàn)的過稃中該參數(shù)的實現(xiàn)手段如圖4所示。
經(jīng)過對原數(shù)值的兩次移位,得到該數(shù)值的四分值,通過減法達到(1/λk)為0.75的目的。
4 通用化模塊設計
下面的討論不失一般性,以每個循環(huán)子矩陣巾有3組1為例進行說明。
如圖5所示。A,B,C 3條線從“初始列號”開始向右側(cè)進行編排,由于C線的ver_pos_C(ver_pos_A、ver_pos_B、ver_pos_C分別指循環(huán)子矩陣中每組1的列初始位置)值最大,即C線在最右端.這也就意味著在經(jīng)過511—1—ver_pos_C(511是每個循環(huán)子矩陣的大小)行的運算之后,C線首先將要從最左邊重新開始循環(huán)。因此,下面進行的數(shù)據(jù)初始化順序從A,B,C,變?yōu)镃,A,B,以此類推。
總而言之,每當排在最右側(cè)的一條線到達最右側(cè)的列時,下一步的CNU運算就將其變?yōu)楸咀泳仃嚨淖钕忍幚淼臄?shù)據(jù)。因為有這樣的運行規(guī)律,于是形象的稱這種運行方式為“反彈”。即,每當排在最右側(cè)的線碰撞到循環(huán)子矩陣的右側(cè)壁時便發(fā)生“反彈”,橫向處理數(shù)據(jù)的順序便進行一次向右的循環(huán)移位,將最右側(cè)線的數(shù)據(jù)移到最左邊,其他的數(shù)據(jù)順序不變。
如此循環(huán),直到把該循環(huán)子矩陣中所有的“1”位置全部處理完畢。每當循環(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條線從“初始行號”位置開始向右側(cè)進行編排,A,B,C中的每條線,每當穿越hor_A,hor_B,hor_C中的直線時,A,B,C的橫向計數(shù)便加1,因為每穿越一次除它本身之外的線時,在它左邊就多一條線。因此本方法稱之為“穿越”。
先以C線為例進行說明。C線從hor_pos_C點殲始,向右側(cè)移動,當C線的行號“穿越”第一個除hor_C以外的水平直線hor_B的時候.此時C線上數(shù)據(jù)的編號加1。
5 加入通用化模塊的高速譯碼實現(xiàn)方案
從上面的分析的出結論,當存儲器內(nèi)的數(shù)據(jù)進行向右側(cè)的循環(huán)移位的時候,每當?shù)竭_最右側(cè),通用定位模塊檢測到這一信息便將通用定位模塊的輸出加1。存儲在定位位內(nèi)。具體說明參見如圖6所示。
該圖說明了加入通用化定位模塊后的數(shù)據(jù)組成。仍以圖2所述矩陣為例,而且列初始位置小的一組1的數(shù)據(jù)從存儲器1中讀出,列初始位置大的一組1從存儲器2中讀出。當數(shù)據(jù)初始化到兩個存儲器內(nèi)之后,進行水平運算的時候,首先提取第0行的數(shù)據(jù)以實線表示,此時的通用定位模塊的定位位輸出是0,輸出到CNU進行運算的數(shù)據(jù)前端的定位位也是0。隨著數(shù)據(jù)讀取的進行,當進行到以虛線表示的第2行進行數(shù)據(jù)讀取的時候,存儲器1對應那組1達到了存儲器的還沒有到達存儲器的最右側(cè),而此時從存儲器2中讀出的數(shù)據(jù)已經(jīng)經(jīng)過了該存儲器的最右側(cè),開始重新從最左邊讀數(shù),因此定位位被通用定位模塊加1,變?yōu)?。
這樣進行數(shù)據(jù)的讀取工作,直到讀完該循環(huán)子矩陣中所有的數(shù)據(jù),所有讀出的數(shù)據(jù)都在首位增加了一個“定位位”,然后被送往CNU參與水平運算。
增加了通用定位模塊對CNU的結構也有所影響。文獻中曾給出CNU運算結果的四維存儲方法,存儲的信息包括最小值,次小值,最小值的位置和符號位,該存儲方法大大節(jié)約了存儲器開銷。然而當每個循環(huán)子矩陣中不止有一組1的時候,采用了通用化的定位模塊,從存儲器中讀出的數(shù)據(jù)也增加了一位“定位位”,此時的CNU結構需要發(fā)生改變,來適應做出的調(diào)整。具體變化如圖7所示。
圖中的輸入端數(shù)據(jù)的頭部都加入了一位“定位位”,該位不參與CNU的比較運算過程,因此單獨將改為取出,在圖中最下方標記出來。
若每個循環(huán)子矩陣中有兩組1,使用圖7中的CNU進行運算的時候,CNU的輸入端總是把每個列塊對應的兩個M存儲器中的存儲器1連接在比較器的上方接口,存儲器2連接在比較器的下方接口,例如D000連接第一列塊的存儲器1,D001連接第一列塊的存儲器2。這樣進行的排列在“位置標記”模塊的輸出端可以得到最小值的位置是在D000~D111中的哪一個。然后將這一輸出前加上該列塊的“定位位”信息進行存儲,這一行數(shù)據(jù)的其他“定位位”信息全部刪除。
在垂直運算的過程中,需要利用上述信息確定求列和時參與運算數(shù)據(jù)的具體位置。列運算的實現(xiàn)方案如圖8所示。現(xiàn)在假設進行循環(huán)子矩陣的第一列的列運算,需要得到的信息是第1列兩個數(shù)據(jù)的值。下面以第2行第1列的數(shù)據(jù)為例進行說明。
第2行的數(shù)據(jù)經(jīng)過水平運算后存儲在R存儲器中的對應位置上,該位置存儲信息的格式如圖中最左側(cè)所示。若水平運算求得的最小值不在該子矩陣的列塊范圍內(nèi),那么該子矩陣中所有的數(shù)據(jù)全部以該行最小值輸出參與垂直運算。
但是若水平運算求得的最小值在該子矩陣的列塊內(nèi),那么就需要用“穿越”的方法確定所需數(shù)據(jù)在該列塊中是水平方向上的第幾個數(shù)據(jù),確定了這一點后,就能夠利用水平運算的結果中的“定位位”來判斷該值是最小值還是次小值了。
從整個實現(xiàn)過程中可以看出,陔通用模塊引入之后,可以通過流水的操作來消除對速度的影響,而且該模塊的引入沒有對存儲資源構成任何多余的消耗。
另外從該方法的實現(xiàn)過程可以看出,該方法適用于BP算法、最小和算法以及最小和算法的改進算法,所以該方法也具有良好的算法通用性。
通過ISE中Xinlin公司V5-330芯片上的仿真可以看出該方法的資源消耗情況。時鐘頻率120 MHz。
6 結束語
本章還介紹了通用化模塊的設計方法,針對循環(huán)子矩陣中不止有一組1的情況,利用了校驗矩陣中循環(huán)子矩陣的自身特點,設計了能夠自動識別1排列情況的模塊,以利于垂直運算過程中自動調(diào)用水平運算的結果。該模塊的加入不會對譯碼速度和存儲資源造成任何消耗,而且有助于未來成熟高效地開發(fā)高速譯碼設備。