一種適用于NAND閃存的LDPC譯碼算法

摘 要：由于NAND閃存具有讀寫速度快、效率高、功耗低等特點，因此被廣泛應用于存儲領域。為了提高閃存存儲的可靠性，提出一種適用于NAND閃存的LDPC譯碼算法對其進行糾錯?；贚DPC碼的BP譯碼簡化算法，結合分層算法與歸一化最小和（NMS）算法，提出一種改進的行分層最小和算法。仿真結果表明，改進譯碼算法在不降低譯碼性能的前提下，減少了迭代次數，加快了譯碼收斂速度，更有利于硬件電路的實現。

關鍵詞：NAND閃存;LDPC碼;分層算法;最小和算法

DOI：10. 11907/rjdk. 182762 開放科學（資源服務）標識碼（OSID）：

中圖分類號：TP312文獻標識碼：A 文章編號：1672-7800（2019）007-0084-04

LDPC Decoding Algorithm for NAND Flash Memory

YU Bin

（School of Communication Engineering， Hangzhou Dianzi University， Hangzhou 310018， China）

Abstract： NAND flash memory is widely used in the field of storage due to its characteristics of fast read and write speed， high efficiency and low power consumption. A LDPC decoding algorithm for NAND flash memory is proposed in this paper， the aim is to improve the reliability of flash memory storage. An improved line hierarchical minimization algorithm is proposed. Its based on BP decoding algorithm， combined with hierarchical algorithm and normalization minimization algorithm， and BP decoding algorithm based on LDPC code. Simulation results show that the improved decoding algorithm without reducing the decoding performance can reduce the number of iterations， speed up the decoding convergence and is more suitable for the implementation of hardware circuits.

Key Words： NAND flash memory; LDPC code; layered algorithm; min-sum algorithm

作者簡介：于彬（1993-），男，杭州電子科技大學通信工程學院碩士研究生，研究方向為微電子、數據存儲。

0 引言

近年來，存儲技術得到了飛速發展，閃速存儲器[1]（Flash Memory）由于具有非易失性、低能耗、抗震動、存儲容量大、壽命長等特性得到了廣泛應用。NAND 閃存作為存儲介質的固態盤（Solid-State Drive，SSD），具有高性能、低功耗等特點[2]，已逐步應用于軍事、航空等多個領域，是存儲系統發展的主要趨勢之一。然而，隨著Flash工藝深入到25nm甚至以下，且內部結構從SLC發展到MLC與TLC，雖然單位存儲容量越來越大，但數據差錯率也越來越高，需要重點研究如何保障NAND閃存的可靠性[3]。因此，低密度奇偶校驗（Low-Density-Parity-Check，LDPC）碼開始進入人們視野[4]。LDPC碼具有很強的隨機糾錯能力，以及并行快速譯碼等特點，但與通信領域的應用特點不同，存儲領域需要更高的編碼率，且譯碼收斂速度更快、硬件空間有限，為LDPC碼在存儲領域的應用帶來了很大挑戰。因此，尋找適用于NAND閃存的LDPC碼具有重要意義[5]。

近年來，研究人員將加權比特翻轉（WBF）譯碼算法應用于閃存糾錯領域[6]，但在復雜度降低的情況下，譯碼性能也損失嚴重，之后又通過將翻轉標志引入WBF譯碼算法，實現并行加權比特翻轉譯碼[7]，解決了不易正確收斂的問題，但譯碼性能仍達不到標準。與LDPC比特翻轉譯碼算法相比，采用最小和算法可以提升譯碼性能，更適用于對閃存的糾錯[8]。本文在歸一化最小和（NMS）算法基礎上[9]，設計一種基于行分層的分層修正最小和算法[10]，在不增加復雜度的前提下，提高了譯碼收斂速度，并提升了解碼器吞吐率。

1 LDPC碼基本概念

1.1 基本概念

LDPC碼[11]是線性分組碼的一種，主要由[（n-k）×n]的校驗矩陣H 確定，再根據校驗矩陣得到[k×n]的生成矩陣G。其中，k表示信息比特長度，n表示碼長。校驗矩陣H是低密度奇偶校驗碼，矩陣中1的數目遠小于0的數目，且占比很少。根據每行與每列中1的數目可以將LDPC碼種類分為規則和非規則的LDPC碼。如果每行與每列中1的數目都為固定整數，則稱為規則LDPC碼，否則為非規則LDPC碼。

LDPC碼可以用稀疏校驗矩陣表示，也可以用Tanner圖[12]表示。例如[（6，2，3）]規則碼的校驗矩陣H為：

[H=100011010101001110]

其對應的Tanner圖如圖1所示。

圖1 H矩陣Tanner圖

Tanner圖中存在環，即從某個節點出發再回到該節點構成的閉合路徑，所經過邊的數目即為環長。其中最短環長稱為LDPC碼的圍長（girth）。短環（如四環和六環）的存在會降低LDPC譯碼性能，即糾錯性能，主要由于環的存在破壞了消息傳遞的獨立性，造成某節點信息被多次重復利用，減緩了譯碼收斂速度，從而降低了性能，環長越小則性能越差。因此，在構造校驗矩陣時，一般圍長不能太小[13]。

1.2 LDPC譯碼算法

LDPC碼誤碼率較低，但譯碼器復雜，占用面積相對較大。當其應用于NAND閃存時，LDPC碼的譯碼算法應具備較快的譯碼速度與較低的計算復雜度。

在軟判決譯碼算法中，置信傳播（Belief Propagation）算法[14]最為典型，其譯碼性能相比傳統糾錯碼得到了大幅提高，其結果接近香農極限。在BP算法中，變量節點與校驗節點之間傳遞的信息是個概率的LLR（Log Likelihood Ratio）值[15]。例如：[L（Pi）]表示比特i的信道初始化數據，也即對數似然比，[L（rji）]表示校驗節點外的信息數據，[L（qij）]表示變量節點外的信息數據，[L（Qi）]表示變量節點i的后驗概率數據[16]。

對數域BP算法譯碼迭代具體步驟如下：

（1）初始化。計算信道傳遞給變量節點的初始化概率似然比消息[L（Pi）]，i=1，2，…，n，對于每一個變量節點i及其相鄰的校驗節點[j∈C（i）]，[C（i）]表示與變量節點i相連的校驗節點集合[Ci={j：hji=1}]。設定變量節點傳向校驗節點的初始消息：

[L（0）（qij）=L（Pi）] （1）

（2）迭代處理。

步驟1：校驗節點消息處理。對于所有校驗節點j及其相鄰的變量節點[i∈R（j）]，[R（j）]表示與校驗節點j相連的變量節點集合[Rj=i：hji=1]。第l次迭代時，計算變量節點傳向校驗節點的消息。

[L（l）（rji）=2tanh-1i′∈Rj＼itanh12L（l-1）（qij）]? （2）

步驟2：變量節點消息處理。對于所有的節點變量i及其相鄰的校驗節點[j∈C（i）]，第l次迭代時，計算校驗節點傳向變量節點的消息。

[L（l）（qij）=L（Pi）+j′∈Ci/jL（l）（rji）]? （3）

步驟3：譯碼判決。對所有變量節點計算硬判決消息。

[L（l）（Qi）=L（Pi）+j∈CiL（l）（rji）]? （4）

若[L（l）（Qi）>0]，則[ci=0]，否則[ci=1]。

（3）迭代停止判斷。若[HcT=0]或達到最大迭代次數，則運算結束，否則返回進行下一次迭代。

雖然LLR-BP算法對BP算法作了相當程度的簡化處理，但在每次迭代的校驗節點更新過程中仍需要進行乘法、指數和對數運算，導致計算量較大，硬件實現過程復雜。最小和（Min-Sum，MS）算法[17]采用求最小值與相加操作替換了LLR-BP算法中非線性雙曲函數的反函數計算，降低了BP算法復雜度，減少了計算量，易于進行軟件仿真與硬件設計。

LLR-BP算法中對檢驗節點的處理可表示為：

[L（rji）=2tanh-1i∈Rj/itanh12L（qij）=]

[i∈Rj/isgn（L（qij））？mini∈Rj/iL（qij）]? （5）

然而，最小和算法在簡化計算的同時，在性能上也造成了一定損失。因此，提出兩種修正最小和算法解決該問題，分別是引入歸一化因子的歸一化最小和（Normalized MS，NMS）算法，以及引入偏移因子的偏移最小和（Offset MS，OMS）算法[18]。這兩種修正算法能夠在不顯著增加計算復雜度的前提下獲得接近BP算法的性能。譯碼其它過程不變，而是僅對校驗節點消息處理的計算公式作了修正，分別如式（6）、式（7）所示。

[L（rji）=α？i∈Rj/isgn（L（qij））？mini∈Rj/iL（qij）] （6）

[L（rji）=i∈Rj/isgn（L（qij））？maxmini∈Rj/iL（qij）-β，0] （7）

式（6）中，[α] 為歸一化因子，[0<α<1];式（7）中，[β]為偏移因子，[0<β<0.5]。

2 行分層最小和算法（RLMS）

上文所述算法都是非常經典的LDPC譯碼算法，但其通常收斂速度較慢，為了獲得較高帶寬，需要付出很大的硬件代價。因此，為了平衡帶寬、性能、面積等方面，本文采用Layer算法[19]。RLMS（Row-Layer Min-Sum）算法即是其中一個典型，其屬于串行算法，在相同帶寬下硬件代價較小，同時在運算中利用計算出的新LLR代替舊的LLR值，從而獲得更快的收斂速度，并且性能上與NMS算法相比幾乎沒有損失。

LDPC碼通過變量節點和校驗節點進行消息傳遞與迭代譯碼。在上述傳統軟判決譯碼算法中，信息傳遞是以矩陣為整體進行并行傳遞的[20]。先計算完成所有行的行運算，一起傳遞到變量節點并更新信息，如圖2所示，然后進行列運算，將更新的信息并行地傳給變量節點，如圖3所示。

圖2 變量節點并行傳遞信息到校驗節點

圖3 校驗節點并行傳遞信息到變量節點

這種并行傳遞方法無法及時更新變量節點信息，因而使信息利用時間滯后，導致迭代收斂速度變慢，增加了迭代次數。對于硬件電路模塊而言，迭代次數多，也即意味著一次譯碼所需時間更長，吞吐率下降。

為了達到更高的吞吐量，本文采取行分層的消息傳遞結構，即每完成一行的行運算，立即變更變量節點信息，并采用新的變量節點信息進行下一行的行運算。

如圖4所示，該結構可大大降低信息反饋的滯后，從而增加收斂速度，使平均迭代次數下降20%～50%。采用分層消息傳遞結構后，對式（3）、（4）、（6）進行修改，分層譯碼算法如下：

[L（l）（qij）=L（l-1）（Qi）-L（l-1）（rji）]? （8）

[L（l）（rji）=α？i∈Rj/isgn（L（l）（qij））？mini′∈Rj/iL（l）（qij）] （9）

[L（l）（Qi）=L（l）（Pi）+L（l）（rji）] （10）

分層算法的信息計算順序與傳統譯碼算法有一定差別，首先更新變量節點，然后對校驗節點進行更新并計算后驗LLR值，之后再判決后驗LLR。因為RLMS算法對行結構并未造成影響，只對列結構造成了影響，所以沒有影響譯碼迭代中的校驗節點，只需對變量節點進行更新，并對后驗LLR值進行修改即可。

[L（Qi）]信息減去[L（rji）]信息即得到更新前的[L（qij）]信息，對[L（qij）]信息進行校驗節點更新，得到更新后的[L（rji）]信息，再用更新后的[L（rji）]信息加上更新前的[L（qij）]信息，得到更新后的后驗[L（Qi）]信息。

RLMS算法增加了變量節點更新次數，從而提高了譯碼進程的收斂速度與譯碼速度。該算法不需要存儲變量節點到校驗節點的信息，從而節省了存儲器空間，更適用于對NAND閃存的糾錯[21]。

3 仿真結果與分析

3.1 仿真條件

本文采用PEG隨機構造法[22]構造準循環（Quasi-Cyclic，QC）LDPC碼，該碼的H矩陣結構具有一定規律性，同時還具備優良的糾錯性能。該結構可以簡化硬件電路實現過程[23]，提高并行速度，并加快譯碼收斂速度，更適用于對NAND閃存的糾錯。

3.2 性能比較

本文構造的校驗矩陣為[（256×7）×（256×72）]的矩陣，即為（18432，16640）碼，基于Matlab仿真將本文提出的RLMS算法與傳統歸一化最小和算法的輸出誤幀率（Frame-Error Rate，FER）進行比較，如圖5所示。在具有相同輸入信噪比（Signal Noise Ratio，SNR）的情況下，輸出的FER遠小于歸一化因子[α=0.875]的最小和算法，略大于[α=0.75]的最小和算法，在更有利于硬件電路實現的情況下，糾錯性能并沒有明顯下降。

RMLS算法在具備優良譯碼糾錯性能的同時，收斂速度更快，譯碼平均迭代次數顯著減少。在Matlab仿真平臺下，對以上3種譯碼算法進行迭代次數對比，如圖6所示。在具有相同輸入信噪比的情況下，RLMS算法的平均迭代次數明顯減少，也即意味著解碼器電路的吞吐率得到了明顯提升。

根據以上仿真結果可以得到，RLMS串行算法在不增加譯碼復雜度且不損失譯碼性能的條件下，加快了收斂速度，提升了解碼器硬件電路吞吐率，更適用于對吞吐率要求較高的NAND閃存中。

圖5 不同譯碼算法下的輸出誤幀率

圖6 不同譯碼算法下的平均迭代次數

4 結語

綜上所述，基于分層算法與最小和算法改進的行分層最小和算法適用于硬件電路的實現，可減少迭代次數，加快譯碼收斂速度，以提升解碼器硬件電路的吞吐率，滿足NAND閃存對高吞吐率的要求。未來可對最小和算法的歸一化因子進行優化，如加入兩個因子進行校正、根據迭代中傳輸信息值的變化動態規定[α]因子大小等。

參考文獻：

[1] 趙啟鵬. 基于NAND閃存的安全U盤FTL算法研究[J]. 軟件導刊，2017，16（4）：38-41.

[2] MICHELONI R，MARELLI A，ESHGHI K. Inside solid state drives （SSDs）[M]. Berlin：Springer， 2013.

[3] 周天偉. NAND閃存的軟硬判決糾錯碼應用研究[D]. 西安：西安電子科技大學，2014.

[4] 李芳苑. 用于NAND閃存的LDPC碼研究[D]. 廣州：華南理工大學，2013.

[5] 彭福來，于治樓，陳乃闊， 等. 面向NAND Flash存儲的糾錯編碼技術概述[J]. 計算機與現代化，2017（11）：35-40.

[6] 劉曉健，趙春明，吳曉富.? 改進型并行比特翻轉算法[J].? 東南大學學報：英文版，2009，25（4）：423-426.

[7] 劉原華，張美玲. LDPC碼的改進迭代比特翻轉譯碼算法[J]. 電訊技術，2012，52（4）：488-491.

[8] 張旋，慕建君，焦曉鵬. 一種MLC閃存存儲系統的比特翻轉譯碼算法[J]. 西安電子科技大學學報：自然科學版，2017，44（5）：75-80，146.

[9] FOSSORIER M P C，MIHALJEVIC M，IMAI H. Reduced complexity iterative decoding of low-density parity check codes based on belief propagation[J]. IEEE Transactions on Communications，1999，47（5）：673-680.

[10] 云飛龍，朱宏鵬，呂晶，等. 一種基于QC-LDPC碼的低復雜度分層迭代譯碼器[J]. 通信技術，2015，48（11）：1228-1233.

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

[12] TANNER R M. A recursive approach to low complexity codes[M].? Piscataway：IEEE Press，1981.

[13] 王啟瑋，戰興群，嚴凱. LDPC碼的編譯碼設計與研究[J]. 計算機測量與控制，2013，21（3）：728-731.

[14] 詹尹，李宏偉，梁丹亞. 一種LDPC碼改進型BP譯碼算法[J]. 科學技術與工程，2013，13（31）：9366-9370.

[15] 張春生，蘇開友，付靜. LDPC碼在高速移動環境下的編譯碼實現[J]. 軟件導刊，2013，12（2）：46-48.

[16] 姜超. NAND閃存的LDPC碼比特翻轉譯碼算法研究[D].? 西安：西安電子科技大學，2017.

[17] 陳正康，張會生，李立欣， 等. LDPC 碼最小和譯碼算法的整數量化[J]. 系統工程與電子技術，2015 （10）：2371-2375.

[18] 馬匯淼，馬林華，張嵩，等. 基于整數運算的LDPC碼改進最小和譯碼算法[J]. 電視技術，2013，37（17）：197-199，235.

[19] 倪俊楓，甘小鶯，張海濱，等. 改進的分層修正最小和LDPC譯碼算法及譯碼器設計[J]. 系統工程與電子技術，2008，30（12）：2531-2535.

[20] KIM J， CHO J， SUNG W. A high-speed layered min-sum LDPC decoder for error correction of NAND Flash memories[C]. IEEE International Midwest Symposium on Circuits & Systems，2011：1-4.

[21] JUNG Y，CHUNG C， KIM J， et al. 7.7 Gbps encoder design for IEEE 802.11 n/ac QC-LDPC codes[C]. 2012 International SoC Design Conference （ISOCC），2012： 215-218.

[22] HU X Y， ELEFTHERIOU E， ARNOLD D M. Regular and irregular progressive edge-growth tanner graphs[J].? IEEE Transactions on Information Theory， 2005， 51（1）：386-398.

[23] ZIED S A， SAYED A T， GUINDI R. Configurable low complexity decoder architecture for quasi-cyclic LDPC codes[C]. Primosten：International Conference on Software，Telecommunications and Computer Networks， 2013.

（責任編輯：黃 ?。?/p>