MLC存儲信道下的雙層LDPC碼優(yōu)化設(shè)計

侯文濤，張順外，孔令軍

(1.南京郵電大學 通信與信息工程學院，江蘇 南京 210003;2.金陵科技學院 網(wǎng)絡(luò)與通信工程學院，江蘇 南京 211169)

0 引言

近年來，大數(shù)據(jù)和云存儲的發(fā)展給信息領(lǐng)域帶來了諸多風險和挑戰(zhàn)，傳統(tǒng)的存儲技術(shù)不能適應當前高集成度、低功耗快速集成電路技術(shù)的發(fā)展。非易失存儲(Non-Volatile Memeory,NVM)技術(shù)尤其NAND存儲技術(shù)具有高讀寫速度、高集成度和體積小等優(yōu)點，成為當前研究的熱點[1]。

多層式存儲(Multi-level Cell，MLC)高密度技術(shù)憑借存儲容量大、單位存儲成本低及功耗小等特點受到廣泛的關(guān)注。然而，隨著存儲密度的增大和單元尺寸的減小，導致MLC型NAND閃存的可靠性降低。簡單來說，一個閃存單元的重復編程次數(shù)是有限的，如果超過某個特定次數(shù)，閃存單元就不能執(zhí)行寫入操作。未來將會不斷地縮小閃存單元的尺寸，也會加入更多的信息比特到每個存儲單元中，因此有效的P/E循環(huán)次數(shù)會不斷地降低，同時在存儲數(shù)據(jù)進行讀取判決時更容易出現(xiàn)錯誤。因此，解決讀寫時延加長、P/E次數(shù)減少等主要問題以及實現(xiàn)數(shù)據(jù)的可靠性存儲正成為現(xiàn)階段存儲領(lǐng)域研究的重點[2]。

當閃存單元的擦除次數(shù)達到一定閾值后，其存儲數(shù)據(jù)的性能急劇下降，此時糾錯功能顯得尤為重要。傳統(tǒng)的糾錯碼受限于其糾錯能力，無法滿足MLC型NAND閃存中數(shù)據(jù)可靠性存儲的要求。本文結(jié)合MLC存儲信道的特性，設(shè)計了一種適用于MLC閃存中雙層低密度奇偶校驗(Low-Density Parity-Check，LDPC)碼的編譯碼算法，提升MLC存儲使用期內(nèi)不同階段的系統(tǒng)性能，實現(xiàn)延遲控制，提高系統(tǒng)的存儲效率。仿真結(jié)果表明，所提出的方法相比于常規(guī)的糾錯算法有更好的性能，降低了譯碼算法的復雜度。

1 相關(guān)工作

1.1 存儲信道下的糾錯碼

信道編碼可有效地改善存儲可靠性、延長其使用壽命[3]。博斯—喬赫里—霍克文黑姆(Bose-Chaudhuri-Hocquenghem,BCH)碼,因為編譯碼算法復雜度較低、糾錯能力良好，在可靠性存儲中得到了很好的應用[4-6]。為了進一步提升BCH碼的性能，一些學者也提出了通過級聯(lián)的方法[7]和平面優(yōu)化算法[8]來降低復雜度，都取得了很好的性能提升。然而，隨著TLC等高階存儲器的出現(xiàn)，傳統(tǒng)的糾錯碼受限于其糾錯性能及高復雜度，無法進一步滿足數(shù)據(jù)可靠性存儲的要求。因此，容量限可達的極化碼(Polar codes)以及逼近香農(nóng)限的LDPC 碼憑借更強的糾錯性能在MLC型NAND閃存中的應用引起了廣泛的關(guān)注[9-15]。

LDPC碼是一種基于稀疏校驗矩陣的線性分組碼，由Gallager于1962年首次發(fā)現(xiàn)。其校驗矩陣中的1遠小于 0的數(shù)目，其譯碼復雜度和最小碼距都只隨碼長呈現(xiàn)線性增加，且相同碼率下，LDPC碼的糾錯性能優(yōu)于BCH碼[16]，使得LDPC碼在MLC型NAND閃存中的應用成為當前研究的熱點。文獻[11-12]針對LDPC的實現(xiàn)工作致力于減少由細粒度內(nèi)存感知精度引起的延遲開銷，為了解決潛在的BP解碼的延遲，Aslam等[13-15]提出了幾種改進的BP算法，降低了復雜度和收斂性能。

與通信領(lǐng)域不同，面向Flash存儲的基于信道編碼理論，借助差錯控制技術(shù)可以保證存儲系統(tǒng)的數(shù)據(jù)可靠性。LDPC碼不僅要求在保證高編碼率的同時達到低誤碼率，還要求編譯碼盡可能簡單以能夠在VLSI中實現(xiàn)。QC-LDPC作為一種結(jié)構(gòu)化的LDPC碼，由于其生成矩陣的循環(huán)性，硬件實現(xiàn)簡單，成為存儲領(lǐng)域中比較受歡迎的一種LDPC碼。文獻[17]通過減少奇偶校驗矩陣中權(quán)重為2的列的數(shù)量和優(yōu)化代碼圖的結(jié)構(gòu)，提升了糾錯性能。文獻[18]構(gòu)建了一種基本矩陣，是根據(jù)NAND閃存改進的外部信息傳輸(EXIT)圖方法優(yōu)化的度序列的QC-LDPC碼，具有低復雜度的QC編碼器結(jié)構(gòu)和易于并行化的原型圖解碼器結(jié)構(gòu)，可以方便地生成速率兼容的原型LDPC碼族。

1.2 雙層LDPC碼

雙層LDPC碼最早在DF中繼通信系統(tǒng)中提出[18]。Peyman提出了2類雙層LDPC碼：雙層刪減碼和雙層加長碼，分別用于源節(jié)點向目的節(jié)點的信道以及中繼節(jié)點向目的節(jié)點的信道中使用。源節(jié)點向目的節(jié)點傳輸信息，利用中繼節(jié)點輔助源節(jié)點向目的端傳輸額外的校驗位，在目的端譯碼時借助2組校驗位進行譯碼，該方法能夠提高系統(tǒng)的整體性能。將存儲系統(tǒng)與中繼系統(tǒng)進行類比。由于單元間干擾對MLC不同頁之間的影響不同，導致其同一單元不同頁受到的噪聲影響也不同。因此，可以將上頁和下頁分別等效為中繼通信系統(tǒng)的源節(jié)點與中繼節(jié)點。在下頁中加入額外校驗位對上頁譯碼進行輔助，使噪聲干擾較強的上頁獲得更好的譯碼性能。

2 主要任務(wù)

2.1 MLC閃存信道模型

NAND閃存的基本數(shù)據(jù)存儲單元是浮置柵單元，簡稱為存儲單元(Cell)。通過對浮置柵單元進行充電，使其電壓值達到不同的閾值范圍以表示不同的數(shù)據(jù)來進行數(shù)據(jù)存儲。對MLC閃存中2 bit/Cell的單元，閾值電壓被分成4個電壓區(qū)間，電壓層級分別為1，2，3，4，每個電壓層級對應的數(shù)據(jù)分別用11，10，00，01表示。每個存儲單元中存放的數(shù)據(jù)由2個比特聯(lián)合組成，分別為最高有效比特(Most Significant Bit,MSB)和最低有效比特(Least Significant Bit,LSB)。閃存以塊(Block)為最小單位執(zhí)行擦除操作，而讀寫操作的最小單位為頁(Page)。MSB構(gòu)成閃存存儲的下頁(Lower Page,LP)，上頁(Upper Page,UP)則由相應的LSB組成。MLC型NAND閃存的電壓層級如圖1所示。

圖1 MLC型NAND閃存的電壓層級Fig.1 Voltage level of MLC NAND flash

由于各種電路級噪聲的影響，所期望的閾值電壓信號受到嚴重干擾，帶來嚴重的數(shù)據(jù)可靠性問題。本文將編程噪聲、隨機電報噪聲(RTN)、數(shù)據(jù)駐留噪聲和小區(qū)間干擾作為主要的信號退化成分，對MLC閃存信道進行建模，如圖2所示。

圖2 閃存信道模型Fig.2 Flash memory channel model

其閾值電壓表示為：

V=VP+{nu+np+I+nRTN+nret} ，

(1)

式中，VP∈{Vs11,Vs10,Vs00,Vs01}為目標電壓水平集合；Vs11為擦除狀態(tài)電壓；Vs10，Vs00，Vs01表示編程狀態(tài)的3個電壓；nu，np分別為理想編程操作后出現(xiàn)的與狀態(tài)相關(guān)的編程噪聲分量，其中與狀態(tài)相關(guān)的ISPP噪聲nu只對編程化的狀態(tài)存儲單元產(chǎn)生影響，在迭代編程與驗證方法下，通過一系列程序和驗證電壓脈沖，將每個編程狀態(tài)配置為各自的驗證電壓級別VP，這些電壓脈沖被應用于電池的控制門。采用這種編程方式，程控狀態(tài)存儲單元對應的閾值電壓信號在[0,Vpp]趨向于均勻分布[16]：

(2)

式中，Vpp表示采用ISPP技術(shù)對每一次編程操作閾值電壓的增加值。

編程噪聲同時影響擦除狀態(tài)和編程狀態(tài)的單元，主要由NAND閃存制造工藝變化造成，可以用高斯分布函數(shù)[17]來表示:

(3)

式中，σp，σe為噪聲方差參數(shù)。

I表示單元間干擾，由相鄰存儲單元間的寄生耦合電容的存在而產(chǎn)生，由CCI導致的電壓改變量VCCI可以表示為[18]：

(4)

nRTN表示隨機電報噪聲，由于反復出現(xiàn)的P/E循環(huán)產(chǎn)生了陷阱，這些陷阱位點捕獲帶點粒子產(chǎn)生了閾值電壓的波動，這種無意識的電壓信號波動增加了NAND閃存通道的噪聲方差。這種電路級閾值電壓失真稱為隨機電報噪聲(RTN)。本文用零均值高斯分布函數(shù)對RTN進行建模：

(5)

式中，σw隨PE周期變化。

nret表示數(shù)據(jù)駐留噪聲隨時間的變化，由存儲單元中數(shù)據(jù)的變化而導致。數(shù)據(jù)駐留錯誤與P/E和存儲數(shù)據(jù)的停留時間有關(guān)，其閾值電壓分布函數(shù)如下：

(6)

式中，方差σrs和均值urs如下：

urs=(VP-x0)×[At(PE)αi×Bt(PE)αo]×ln (1+T)，

(7)

σrs=0.3|urs|，

(8)

式中，At，Bt，αi，αo，x0為常數(shù)分布參數(shù)。

2.2 雙層LDPC碼的設(shè)計

面向Flash存儲的LDPC碼不僅要求在保證高編碼率的同時達到低誤碼率，還要求編譯碼盡可能簡單以能夠在VLSI中實現(xiàn)。本文采用QC-LDPC碼作為MLC型NAND閃存信道的信道編碼方案。為保證雙層LDPC碼的譯碼性能，在設(shè)計時要求校驗矩陣中無短環(huán)的存在。雙層LDPC碼的Tanner圖如圖3所示。

圖3 雙層LDPC碼的Tanner圖Fig.3 Tanner graph of Bilayer LDPC code

圖3所示的雙層LDPC的Tanner圖可以用(Uα∪Lβ∪Vv)來表示，其中，Uα={u1,u2,…,uk1},是上層子圖的校驗節(jié)點,Lβ={l1,l2,…,lk2}是下層子圖的校驗節(jié)點，Vv={v1,v2,…,vN}是變量節(jié)點。虛線表示為雙層LDPC碼的短環(huán)，構(gòu)造雙層LDPC碼，要確保雙層LDPC碼的Htwo無短環(huán)、無停止距離，使Hup|K2*N,Hlow|K1*(N-K2)也滿足無短環(huán)。

給定一個QC-LDPC碼的移位索引矩陣:

(9)

式中，Ps,t=asbt∈GF(p),0≤s≤j-1,0≤t≤k-1,a≠b∈{2,3…p-1}。參數(shù)a,b,p,j,k確定后，一個QC-LDPC碼的校驗矩陣就可以生成，根據(jù)如下判決公式，可得到無短環(huán)的充要條件[19]：

(10)

式中，1≤s≤j-2,2≤s′≤j-1,1≤t≤k-2,2≤t′≤j-1,s

2.3 雙層LDPC碼的編、譯碼

雙層LDPC碼的編碼需借助上層矩陣Hup及下層矩陣Hlow分別獲取校驗比特K1及額外校驗比特K2。式(11)中，Htwo為雙層LDPC碼的校驗矩陣，Hup和Hlow分別為上層矩陣和下層矩陣，N為雙層LDPC碼的碼長，K1和K2分別表示上層LDPC碼和下層LDPC碼的校驗比特長度，X為雙層LDPC碼的碼字：

(11)

式中，Hzero|K1*K2為全0矩陣，用于匹配雙層LDPC長度。

(12)

(13)

由式(12)可得：

(14)

(15)

下層LDPC碼的額外比特K2為：

[x1,x2,…,x(N-K1-K2),c1,c2,…,cK1]T。

(16)

針對MLC信道的特性，需對MLC閃存的上下2頁數(shù)據(jù)分別進行編碼，具體步驟如下：

① MLC上頁數(shù)據(jù)編碼。使用雙層LDPC校驗矩陣Htwo的上層矩陣Hup對上頁數(shù)據(jù)bitup進行編碼，得上頁校驗比特K1。

② MLC上頁數(shù)據(jù)額外校驗比特編碼。使用雙層LDPC校驗矩陣Htwo的下層矩陣Hlow對上頁數(shù)據(jù)bitup+上頁校驗比特K1進行編碼，得到上頁額外校驗比特K2，存放至MLC下頁。

③ MLC下頁數(shù)據(jù)編碼。為保證MLC上下頁碼長相同，需對下頁數(shù)據(jù)進行編碼，得到下頁數(shù)據(jù)的校驗比特K3,其長度為|K1-K2|。

④ 對MLC的上、下頁數(shù)據(jù)進行MLC閃存編碼，得到對應電壓閾值。

編碼過程及各部分長度如圖4所示。

經(jīng)過MLC閃存信道后，其譯碼過程由兩部分組成：閾值電壓向碼字的映射及碼字的譯碼，具體如下。

① 對MLC信道電壓進行門限電壓的感測，根據(jù)電壓值判定上下頁數(shù)據(jù)的似然比。初次判定時采用低精度電壓感測，以降低讀取系統(tǒng)的延遲。

② 對MLC下頁進行譯碼，得到MLC下頁數(shù)據(jù)及額外校驗比特K2的譯碼值。若譯碼失敗，感測精度后再次譯碼，直到預定精度或譯碼成功。若成功，存儲額外校驗比特K2信息。

③ 用上層校驗矩陣Hup對MLC上頁數(shù)據(jù)進行譯碼。若譯碼成功則輸出結(jié)果，否則讀取存儲的額外校驗比特K2。

④ 對讀取額外校驗比特K2的MLC上頁數(shù)據(jù)進行雙層LDPC碼譯碼，若失敗則提高感測精度直到預定精度，否則譯碼成功。

圖4 MLC信道雙層LDPC編碼流程Fig.4 Bilayer LDPC encoding process in MLC channel

需要注意的是，以上是在單獨的MLC上頁譯碼失敗后才進行雙層LDPC碼的使用，因此系統(tǒng)的復雜度并不會因為引入額外校驗比特后而急劇上升，其具體流程如圖5所示。

圖5 MLC信道雙層LDPC譯碼流程Fig.5 Bilayer LDPC decoding process in MLC channel

3 算法仿真

3.1 仿真參數(shù)及矩陣設(shè)計

本文對提出的MLC信道下雙層QC-LDPC碼優(yōu)化算法進行數(shù)值仿真，以驗證方法的有效性。重點評估加入額外校驗比特位的上頁傳輸性能。在解碼過程中，共同使用來自MLC上頁的碼字信息和下頁中正確譯出的額外校驗比特位。需要特別注意的是，仿真認為上頁譯碼時能夠完全正確地從下頁中獲取額外校驗比特。

選取的LDPC碼的碼長N=2 808,碼率R1=3/4，R2=5/6。采用BP譯碼算法，設(shè)置最大迭代次數(shù)為25和50，具體參數(shù)如表1所示。

表1 仿真參數(shù)

根據(jù)式(10)，a=3，b=11，p=234，經(jīng)驗證，符合無短環(huán)條件。

(17)

(18)

式中，

(19)

(20)

(21)

(22)

最終譯碼雙層LDPC矩陣形式如下：

(23)

3.2 性能分析

圖6和圖7分別為不同迭代次數(shù)下碼率R為3/4，5/6的MLC閃存上層信息的誤碼率和誤幀率性能比較。可以看出，擦除次數(shù)P/E較低時，同一碼率的情況下采用本文算法的雙層QC-LDPC相較于傳統(tǒng)的單層QC-LDPC碼，誤碼率與誤幀率得到顯著提高。在10-5的誤碼率時，能夠獲得約額外4 000次的擦除周期，大大提高了MLC閃存的使用壽命。然而，隨著P/E擦除次數(shù)的增多，信道內(nèi)干擾加強，本算法與單層LDPC碼算法性能相近。

(a) MLC閃存上層誤碼率(N=2 808,iter=25)

(a) MLC閃存上層誤幀率(N=2 808,iter=25)

為了比較本算法設(shè)計的雙層LDPC碼對BP譯碼算法延遲復雜度的影響，圖8和圖9分別提供了碼率R=5/6時最大迭代次數(shù)為25次和50次時的性能對比和平均迭代次數(shù)曲線。

圖8 不同迭代次數(shù)下MLC閃存上層誤碼率 (N=2 808,R=5/6)Fig.8 BER of upper layer of MLC flash with different iterations (N=2 808,R=5/6)

圖9 MLC閃存上層平均迭代次數(shù) (N=2 808,R=5/6)Fig.9 Average iteration numbers of upper layer of MLC flash (N=2 808,R=5/6)

由圖8和圖9可以看出，在擦除次數(shù)較低時，相同的最大迭代次數(shù)下，本文所提出的雙層LDPC碼相比于單層LDPC碼，平均迭代次數(shù)顯著降低，大大降低了譯碼的復雜度和延時。此外，提高最大迭代次數(shù)，雙層LDPC碼的性能提升優(yōu)于單層LDPC碼，且平均迭代次數(shù)的增加較少。綜上所述，本文提出的算法在復雜度和性能上都優(yōu)于常規(guī)的單層LDPC碼。

4 結(jié)束語

本文提出了一種基于雙層LDPC的MLC信道下的編碼方案，通過添加額外校驗比特的方式提高MLC閃存的譯碼性能和降低譯碼復雜度，并通過合理地設(shè)計QC-LDPC碼的校驗矩陣，在避免短環(huán)的前提下，獲得具有更大的最小距離的QC-LDPC矩陣。仿真結(jié)果表明，所提出的算法與單層LDPC碼相比，在誤碼率為10-5時，能夠獲得約額外4 000次擦除周期的提升。此外，本算法要求額外校驗比特能夠完全正確譯出，在實現(xiàn)上存在一定困難。下一步將尋找合適的下頁譯碼算法來保證獲取到額外校驗比特的正確性以及高碼率下無短環(huán)的校驗矩陣的參數(shù)。