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

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

關(guān)鍵詞：NAND閃存;LDPC碼;分層算法;最小和算法

DOI：10. 11907/rjdk. 182762 開放科學(xué)（資源服務(wù)）標(biāo)識碼（OSID）：

中圖分類號：TP312文獻(xiàn)標(biāo)識碼：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-），男，杭州電子科技大學(xué)通信工程學(xué)院碩士研究生，研究方向為微電子、數(shù)據(jù)存儲。

0 引言

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

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

1 LDPC碼基本概念

1.1 基本概念

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

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

[H=100011010101001110]

其對應(yīng)的Tanner圖如圖1所示。

圖1 H矩陣Tanner圖

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

1.2 LDPC譯碼算法

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

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

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

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

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

（2）迭代處理。

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

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

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

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

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

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

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

（3）迭代停止判斷。若[HcT=0]或達(dá)到最大迭代次數(shù)，則運算結(jié)束，否則返回進(jìn)行下一次迭代。

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

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

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

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

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

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

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

圖2 變量節(jié)點并行傳遞信息到校驗節(jié)點

圖3 校驗節(jié)點并行傳遞信息到變量節(jié)點

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

為了達(dá)到更高的吞吐量，本文采取行分層的消息傳遞結(jié)構(gòu)，即每完成一行的行運算，立即變更變量節(jié)點信息，并采用新的變量節(jié)點信息進(jìn)行下一行的行運算。

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

[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）

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

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

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

3 仿真結(jié)果與分析

3.1 仿真條件

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

3.2 性能比較

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

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

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

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

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

4 結(jié)語

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

參考文獻(xiàn)：

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

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

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

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

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

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

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

[8] 張旋，慕建君，焦曉鵬. 一種MLC閃存存儲系統(tǒng)的比特翻轉(zhuǎn)譯碼算法[J]. 西安電子科技大學(xué)學(xué)報：自然科學(xué)版，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碼的低復(fù)雜度分層迭代譯碼器[J]. 通信技術(shù)，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] 王啟瑋，戰(zhàn)興群，嚴(yán)凱. LDPC碼的編譯碼設(shè)計與研究[J]. 計算機測量與控制，2013，21（3）：728-731.

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

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

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

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

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

[19] 倪俊楓，甘小鶯，張海濱，等. 改進(jìn)的分層修正最小和LDPC譯碼算法及譯碼器設(shè)計[J]. 系統(tǒng)工程與電子技術(shù)，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.

（責(zé)任編輯：黃 健）