存儲器中QC—LDPC編譯碼算法的改進與實現

摘 要：與傳統存儲信道編碼相比，低密度奇偶校驗碼（LDPC）能夠充分利用軟信息，在信噪比較差的情況下，具有更優秀的糾錯能力。其中，準循環低密度奇偶校驗碼（QC-LDPC）因具有準循環特性而易于實現，近年來已成為研究熱點，但其實現的復雜度與硬件開銷依然很大，尤其是在存儲控制器中，仍未得到實現并商業化使用。本文在分析BP譯碼算法和log-BP譯碼算法的基礎上對譯碼算法做了進一步的改進，通過取最小值和求和的方式進行校驗節點和信息節點的更新，并使用Verilog HDL語言將其實現。最終設計完成的QC-LDPC譯碼器，數據吞吐率達到了20Mbps。

關鍵詞：低密度奇偶校驗碼；譯碼器；部分并行

中圖分類號：TN911.22 文獻標識碼：A 文章編號：1674-7712 （2014） 16-0000-01

基于Flash閃存技術的SSD（固態硬盤）存儲器的誕生，有效地克服了傳統機械硬盤的諸多弱點，在讀寫速度和功耗上都取得了極大的進步，但是其可靠性比較低。在提高存儲的可靠性方面，我們通常所采用的方法是存儲信道編碼技術[1]。傳統的存儲信道編碼多采用BCH碼，而BCH碼的性能有限[2]，要達到較高的數據可靠性必須降低碼率，這樣就浪費了SSD本來就不高的存儲容量。此外，最新的基于自旋電子學的新型存儲器（磁性隨機存取存儲器MRAM）的發現，對編碼性能提出了更高的要求。

基于以上矛盾，將性能更優的，接近香農極限的LDPC碼用于存儲信道已經成為急需解決的問題，但是LDPC編碼的硬件實現復雜度極高[3，4]，目前仍未商業化使用。

QC-LDPC是準循環LDPC編碼，其特點是生成矩陣和校驗矩陣具有分塊循環特性[5，6]。所以在硬件實現過程中可以利用循環特性來降低硬件的實現復雜度[7-9]。而經過合理的設計，QC-LDPC碼在糾錯性能上也不遜于隨機LDPC碼[4]。

本文分析了傳統BP譯碼算法、log-BP譯碼算法，并對QC-LDPC譯碼算法做了進一步改進。通過取最小值和求和的方式進行校驗節點和信息節點的更新。在幾乎不影響糾錯能力的前提下，可以降低實現的復雜度。同時對改進的算法，進行了硬件實現，并達到了20Mbps的數據吞吐率。

一、譯碼算法分析

（一）BP算法分析

所謂BP譯碼算法是指基于概率迭代的置信傳播算法，對長碼具有較好的譯碼性能。

令qxmn為從除了第m個校驗方程之外的其他校驗方程處得到的關于接受序列y的第n位為 的概率；rxmn為接受序列y的第n個比特取x時第m個校驗方程得到滿足的概率；Ixn表示從接受序列 中得到的關于第n個比特的取值為x的概率；Txn表示每次迭代后得到的關于第n個比特的取值為x的后驗概率。

對于二進制的LDPC碼，上述x∈﹛0，1﹜，且rxmn的計算公式為：

r1mn=1/2[1-Πn∈N（m）＼n（qmn0-qmn1）] （1）

r0mn=1/2[1+Πn∈N（m）＼n（qmn0-qmn1）] （2）

則二進制的LDPC碼的概率與BP譯碼算法的步驟為：

（1）初始化：（根據特定的信道計算信息比特的先驗概率），對每個變量節點n=1，2…，N，計算Ixn，并令qxmn=Ixn；

（2）迭代過程：更新校驗節點傳送的消息rxmn：對每個校驗節點m=1，2…，M，n∈N（n），根據（1）和（2）式計算r1mn和r0mn。更新變量節點傳送的消息qxmn：對每個變量節點n=1，2…，N，m∈M（n），計算：

qxmn=amnIxnΠm∈M（n）＼mrxmn （3）

其中amn為歸一化因子，使q0mn+q1mn=1；

（3）嘗試判決：先對每一個變量節點n=1，2…，N，m∈M（n），計算：

Txmn=anIxnΠm∈M（n）＼mrxmn （4）

如果T1n>T0n，則令 ；否則 。這樣得到的臨時結果 ，如果滿足 ，則譯碼成功結束， 為最終的譯碼結果；否則若迭代次數還沒有達到設定的最大迭代次數，則重復迭代；若已經達到最大迭代次數，則宣告譯碼失敗。

（二）log-BP算法分析

BP譯碼算的一個顯著缺陷是在譯碼迭代過程中有大量的乘積運算。這使得譯碼算法的硬件實現難度大幅度提升。log-BP譯碼算法的提出將大量的乘積運算變成了加法運算，從而降低了硬件的實現復雜度和實現成本。

設P0n表示第n組輸入是0的概率，P1n表示第n組輸入為1的概率信息。則初始信道信息用γn=log（P0n/P1n）來表示。

在后續的一系列乘積運算也都相應的做了log對數運算。這樣就將整個算法中乘法運算換成了加法運算。這就大大降低了算法實現的硬件復雜度。但是在算法中又引入了一個對數運算φ=log（1+e-|x|/1-e-|x|）。針對對數運算，大部分算法采用的解決方法是通過LUT（查表法）來解決。但查表法必然會增加硬件對存儲的消耗，而且還會存在降低運算的精度、譯碼速度等缺點。

（三）改進算法

針對log-BP譯碼算法的不足，我們首先分析了φ運算的特點。經過Mat lab仿真， 由函數曲線圖我們可以分析出，φ運算當自變量較小的時候，輸出結果非常的大，隨著自變量的增大，輸出結果急劇減小。

我們還發現φ運算的逆運算是其自己本身。利用這個特點，我們得出了如下結論。

（5）

φ（∑i'φ（βi'j））≈φ（φ（mini'βi'j）） （6）

（7）

（8）

所以，校驗節點的更新我們可以采用直接取絕對值最小值的方式，變量節點更新采用直接求和的方法。

二、QC-LDPC碼的硬件實現

（一）QC-LDPC編碼器設計

先簡單的介紹一下目前的U盤存儲器的主要組成部分如圖1所示。QC-LDPC的編碼和譯碼模塊分別對應于實現U盤存儲器中的編碼和譯碼模塊的功能。

圖1 U盤組成部分

圖2 VNU計算單元說明

圖3 CNU計算單元說明

圖4 譯碼判決模塊

數據流從USB口輸入，經過編碼模塊編碼后傳輸給讀寫控制器，寫入Flash芯片。讀取工作方向正好相反。要經過讀寫控制器從flash芯片中讀出，然后經過譯碼模塊譯碼后，從USB接口傳出。

QC-LDPC編碼就是將輸入的信息序列和生成矩陣G相乘的過程。雖然設計簡單，但要想達到工程設計的具體要求，需要消耗的硬件資源較大。原始的輸入信息長度為7154bits，每組8bit傳入，總共分成895組傳入。傳入時間為895 cycle。所以在實現過程中還要進行具體優化。

因為該QC-LDPC編碼是為了存儲信道設計的。在每個時鐘周期內，USB接口會提供8bit的待編碼原始信息。最理想的狀態是能在一個cycle中完成8bit信息的編碼工作。

考慮到編碼工作的實現復雜度并不高，但是硬件消耗資源非常大的特點，本文嘗試采用了Catapult C軟件進行了相關Verilog HDL代碼的合成，并取得了不錯的效果。每個時鐘周期完成8bit數據流的編碼工作，正好與USB傳輸度匹配。使用Catapult軟件對Block循環進行了平行度為8的部分展開。經過測試，模塊在50MHz的晶振頻率下可以實現376Mbit/s的編碼速率，達到了U盤的工程設計要求。

（二）QC-LDPC譯碼器結構設計

在LDPC譯碼器設計方面，譯碼過程的核心部分是比特節點和校驗節點的更新。每個比特節點和校驗節點的更新過程可以看成是相對獨立的運算單元，彼此之間互不影響。每個更新單元都可以看成是一個獨立的處理器。譯碼器的性能好壞就取決于比特節點運算單元和校驗節點運算單元的數量的多少。當比特節點和校驗節點的更新處理單元越多時，則譯碼速率越快。對于完全串行的解決方案，我們可以認為比特節點運算單元和校驗節點運算單元各有一個，部分并行的解決方案，可以認為比特節點和校驗節點的運算單元數量為m（m>1）和（n>1）。當然m和n的數量越大效率越高。當m等于比特節點數量，n等于校驗節點數量時，就變成了完全并行的譯碼器。

對于完全串行的解決方案，這個實現比較簡單，硬件消耗最低，但是譯碼時間過長。在本例中比特節點數量有8176個，校驗節點有1022個，如果完全串行，在每個時鐘周期內只更新一個比特節點或更新一個校驗節點則完全不能達到工程的要求。

對于完全并行的解決方案，就要設計8176個比特運算處理器，1022個校驗節點更新處理器器。這樣的譯碼器譯碼效率非常高，可以認為每兩個時鐘周期就能完成一次迭代。但是硬件資源的消耗使這個設計方案幾乎是完全不可實現的。

根據比特節點和校驗節點的數量關系和比例特點，最終本文確定了m=56，n=7的解決方案。譯碼速率比串行解決方案極大的提升，而且硬件資源的要求也滿足要求，實現了資源和效率的平衡。

VNU比特節點計算單元的計算工作是計算出所有與之相連的校驗節點發給的概率信息之和但是要去掉發來方向的校驗信息，然后廣播回去，如圖2所示。

CNU校驗節點計算單元的工作內容是計算有輸入結果的絕對值的最小值，但是除了發來方向的信息節點的值不予考慮，符號要有其他的幾個符號的乘積決定，如圖3所示。

迭代譯碼判決模塊，就是求所有輸入的比特節點的和再加上原有的初始信道信息。根據求出的和比較一下和0的大小關系，當比0大的時候輸出0比0小的時候輸出1，如圖4所示。

綜上所述，將VNU和CNU單元連在一起，構成了整個譯碼器模塊的譯碼電路圖，與tanner圖一致。這樣在不斷的循環和迭代的過程中就完成了譯碼的工作。

譯碼器的結束方式有兩種方案：第一種方式是在不斷的迭代過程中，每次譯碼結束后都用校驗矩陣H去驗證輸出的結果是否正確，如果正確了，則將譯碼結果輸出。如果不正確則繼續重復迭代工作，直到得出正確的譯碼結果。但是如果迭代次數達到了最大迭代次數以后仍然無法譯出正確結果，則放棄譯碼。第二種方法直接迭代最大譯碼次數，然后強制輸出。不做譯碼結構的檢查工作。

第一種方法是在計算機軟件仿真過程中所使用的具體設計方式。但是如果使用第一種方法的會給譯碼工作帶來巨大的壓力。因為譯碼的檢查工作耗費了巨大的硬件資源，而且耗時。所以我們在硬件實現的具體方案中采用的是第二種方法，既讓硬件強制迭代30次，然后強制輸出。經過最終的仿真結果可以看出，譯碼結果與實際然間仿真結果相似。達到了預期的目的。經過測試譯碼模塊的數據吞吐率達到了20Mbit/s的數量級。

三、結束語

QC-LDPC碼以其良好的糾錯性能，優越的內在規律性，獲得了越來越多的關注[10，11]。本文對經典的log-BP譯碼算法進行了改進，通過取最小值和簡單求和的方式進行校驗節點和信息節點的更新操作。在不影響糾錯能力的前提下，大幅度降低了硬件的實現成本和復雜度。通過Catapult C完成QC-LDPC編碼模塊的設計。根據QC-LDPC編碼校驗矩陣的代數結構特點，確定了QC-LDPC碼譯碼器的硬件實現方案。譯碼器采用了部分并行的譯碼結構。利用FPGA完成了QC-LDPC譯碼器的性能測試。達到了20Mbit/s的譯碼數據吞吐率。

接下來工作首要解決存儲器的選擇問題，目前所采用的主要存儲方式是寄存器，但是如果大規模的采用寄存器必然會使最終的硬件實現遇到瓶頸。整個譯碼模塊受到硬件資源的限制而無法繼續擴大。碼字目前也存在一些問題，因為本QC-LDPC編碼是為了存儲信道進行設計的。目前的QC-LDPC編碼為（8176，7154）編碼，這個編碼是無法在目前的flash存儲器中使用的。不能達到設計的要求。最理想的存儲信道編碼是（4608，4096）。所以，有關碼字的構造方面[12]還需要進一步的研究。

參考文獻：

[1]林舒.差錯控制編碼（第二版）[M].北京：機械工業出版社，2007.

[2]傅祖蕓，趙建中.信息論與編碼[M].北京：電子工業出版社，2006.

[3]莊夢溪.高速LDPC碼編譯碼器的研究與實現[D].西安電子科技大學，2012.

[4]袁瑞佳.LDPC碼的高效編譯碼實現技術研究[D].西安電子科技大學，2012.

[5]Li Z，Chen L，Zeng L.Efficient Encoding of Quasi Cyclic Low Density Parity Check Codes[J].Communications，IEEE Transactions on，2006（01）：71-81.

[6]江濤.QC-LDPC碼設計和分層譯碼器的FPGA實現[D].南京航空航天大學，2012.

[7]林智強.高速光通信系統中NB-QC-LDPC碼的研究[D].北京交通大學，2013.

[8]陳赟，陳翔，趙明.多碼率QC-LDPC譯碼器設計與實現[J].通信技術，2011（02）：34-35+38.

[9]田雨，馬林華，林志國.QC-LDPC碼的高性能譯碼器實現[J].計算機工程，2011（01）：235-237.

[10]何慶濤，周正，葛建華.準循環LDPC碼譯碼器的FPGA實現[J].空間電子技術，2009（01）：40-43+102.

[11]彭立，朱光喜.QC-LDPC碼的置換矩陣循環移位次數設計[J].電子學報，2010（04）：786-790.

[12]崔俊云.LDPC碼的構造及其譯碼算法研究[D].西安電子科技大學，2012.

[作者簡介]張博（1990，05-），男，碩士研究生在讀，研究方向：存儲器編碼。