MLC型NAND閃存中基于MI異構(gòu)的Polar碼優(yōu)化

張司琪， 孔令軍， 張順外， 張 南

1.南京郵電大學(xué)通信與信息工程學(xué)院，南京210003

2.中國航天系統(tǒng)科學(xué)與工程研究院工程科技發(fā)展戰(zhàn)略研究所，北京100048

近年來，固態(tài)硬盤以其讀寫速度快、輕便等優(yōu)點(diǎn)在NAND Flash 中應(yīng)用廣泛，同時也為大數(shù)據(jù)開辟了新的發(fā)展之路[1].多級單元（multi-level-cell, MLC）型NAND Flash 技術(shù)的出現(xiàn)一方面增大了存儲密度，單位比特的成本降低；另一方面閃存封裝尺寸的減小也縮短了存儲單元間的距離，單元間干擾（cell-to-cell interference，CCI）的影響會降低閃存存儲系統(tǒng)的可靠性.而傳統(tǒng)的糾錯碼——BCH 碼無法滿足MLC 型閃存的差錯控制需求，因此利用新型糾錯碼改善高密度存儲系統(tǒng)中數(shù)據(jù)的耐久度與可靠性成為現(xiàn)階段閃存研究的重點(diǎn)之一[2].

Polar 碼由Arikan 于2009 年提出，是目前唯一一種能被嚴(yán)格證明在編譯碼復(fù)雜度較低的情況下達(dá)到香農(nóng)極限的線性分組碼[3]，因其具有容量限可達(dá)、構(gòu)造方式明確等優(yōu)點(diǎn)而成為最優(yōu)信道編碼方案的候選之一，為MLC 型NAND 閃存的差錯控制技術(shù)開辟了一個新的方向.然而，關(guān)于MLC 型NAND 閃存信道的polar 碼構(gòu)造優(yōu)化的研究不多[4-5].文獻(xiàn)[4]提出了一種稱為自校驗(yàn)的高效多策略ECC 方案，其中硬解碼器設(shè)計用于校正MLC 閃存初始階段的大多數(shù)錯誤碼字，而軟解碼器旨在糾正包含大量錯誤的碼字.文獻(xiàn)[5]將polar 碼應(yīng)用于MLC型NAND 閃存信道的多策略預(yù)編碼方案，并比較polar 碼的二進(jìn)制輸入硬判決譯碼、量化軟判決譯碼和軟判決譯碼三種譯碼算法的性能，然后提出了一種利用逐步最大互信息量來獲取量化邊界值的方案.文獻(xiàn)[6]提出了一種基于多級存儲閾值電壓的polar 設(shè)計方法，并與傳統(tǒng)的polar 碼構(gòu)造方法進(jìn)行了比較.本文在對MLC 型NAND 閃存信道特性的深入分析基礎(chǔ)上，利用MLC 型NAND 閃存信道和AWGN（additive white Gausian noise）信道的差異性，將LLR 轉(zhuǎn)換成互信息量（mutual information, MI），獲取閃存信道下等效的方差，然后基于先前的巴氏參數(shù)法構(gòu)造polar.同時在一定的碼長和碼率下，分析了polar 碼的不同構(gòu)造法對MLC型NAND 閃存信道的誤碼性能.

1 MLC 型NAND 閃存信道模型

一個NAND 閃存芯片由多個塊構(gòu)成，每個塊有多個頁，每頁包含若干個存儲單元.NAND 閃存中的存儲單元可表現(xiàn)出擦除態(tài)或編程態(tài)，其閾值電壓被分成多個量化級來表示數(shù)據(jù).MLC 型閃存采用格雷映射表示存儲單元的4 個狀態(tài)，MLC 型存儲單元中4 個不同的閾值電壓Vmin、V1、V2、Vmax分別表示數(shù)據(jù)符號“11”“10”“00”“01”,Vmin和Vmax分別為處于擦除狀態(tài)和最高寫入電壓對應(yīng)的編程狀態(tài)的存儲單元閾值電壓平均值.MLC 型存儲單元中用bi（i ∈{0,1}）表示第i個比特，b0為最低有效位（least significant bit, LSB），b1為最高有效位（most significant bit, MSB）.

將基于編程干擾（programming noise, PN）、單元間干擾以及數(shù)據(jù)駐留噪聲（data retention noise, DRN）對MLC 型NAND 閃存信道進(jìn)行建模[7-9].在理想狀況下，經(jīng)過擦除和編程操作之后得到MLC 型閃存單元閾值電壓分布的統(tǒng)計如圖1(a)所示.

1.1 MLC 閾值電壓模型

在多級存儲單元中，擦除態(tài)存儲單元的閾值電壓分布P11(v)可以擬合成高斯分布，有

式中，Vmin和σe分別為存儲單元閾值電壓的平均值和標(biāo)準(zhǔn)方差，v為已知閾值電壓.閃存存儲不同的數(shù)據(jù)是通過不同的閾值電壓映射得到的，一般采用逐步增量脈沖編程（incremental step pulse programming, ISPP）技術(shù)來精準(zhǔn)控制存儲單元的電壓值.編程操作以頁為單位，每進(jìn)行一次編程操作，閃存單元的閾值電壓增加Vpp，其閾值電壓不斷逼近校驗(yàn)電壓Vp.因此，編程狀態(tài)的MLC 型NAND 存儲單元閾值電壓Pu(v)呈現(xiàn)出均勻分布，建模公式為

式中，Vp={V1,V2,Vmax}，Vpp的值設(shè)為0.3.

除此之外，編程狀態(tài)的閾值電壓也會受到編程干擾的影響，編程干擾Ppn(v)可擬合成高斯分布，即

式中，σpn為編程干擾的標(biāo)準(zhǔn)方差，編程狀態(tài)的閾值電壓Pp(v)可以看成是式(2)和(3)的卷積，即

式中，Pp={P10,P00,P01}，經(jīng)過PN 干擾后MLC 閃存單元閾值電壓的統(tǒng)計圖如圖1(b)所示.

1.2 單元間干擾（CCI）

單元間干擾是由相鄰單元之間的寄生電容耦合產(chǎn)生的，而由CCI 導(dǎo)致的電壓改變量VCCI可以表示為

式中，?Vk為相鄰單元閾值電壓的偏移量，γk為電容耦合率.MLC NAND 閃存中采用奇偶位線結(jié)構(gòu)，偶字線的MLC 單元會受到5 個相鄰單元的CCI 影響，而奇字線的MLC 單元會受到3 個相鄰單元的CCI 影響[10]，其中垂直方向的電容耦合系數(shù)γy=0.080，水平方向的電容耦合系數(shù)γx=0.100，對角線方向的電容耦合系數(shù)γxy=0.006.文獻(xiàn)[11]利用單元預(yù)編碼技術(shù)可以消除CCI，但是這種技術(shù)對處于擦除態(tài)的存儲單元效果不大.擦除態(tài)存儲單元的建模近似采用高斯擬合，其閾值電壓的平均值由Vmin轉(zhuǎn)化成

1.3 數(shù)據(jù)駐留噪聲

數(shù)據(jù)駐留噪聲與PE 及存儲數(shù)據(jù)的停留時間有關(guān)，其閾值電壓分布函數(shù)可以表示成[12]

其中平均值為

標(biāo)準(zhǔn)方差為

式中，ur={ur11,ur10,ur00,ur01}，σr={σr11,σr10,σr00,σr01},Vs={Vmin,V1,V2,Vmax},x0,Xt,Yt,θi,θ0是參數(shù)，T表示數(shù)據(jù)駐留時間，P表示閃存的編程/擦除循環(huán)次數(shù).數(shù)據(jù)駐留噪聲對存儲單元的閾值電壓分布影響為

存儲單元其他狀態(tài)的閾值電壓Pi(v)為

式中，Pi ∈{P10,P00,P01}，Vi ∈{V1,V2,Vmax}，σi ∈{σ10,σ00,σ01}，v為已知閾值電壓，經(jīng)過DRN 干擾后MLC 型閃存單元閾值電壓的統(tǒng)計圖如圖1(c)所示.

2 Polar 碼編譯碼原理

Polar 碼是一種被證明可達(dá)香農(nóng)極限的線性新型糾錯碼.對于N=2n個獨(dú)立的二進(jìn)制輸入信道W（其中n為自然數(shù)），polar 碼對其進(jìn)行信道組合操作和信道分離操作，從而得到N個相互依賴的極化信道.當(dāng)N →∞時，一部分信道的容量將會趨于1（即通過該部分信道傳輸?shù)谋忍匾欢〞徽_接收），而其余信道的容量將趨于0（即完全無法在信道上可靠地傳輸比特），基于此理論，通信過程中選擇容量趨于1 的信道上傳輸承載信息的自由比特，而在容量趨于0 的信道上傳輸對收發(fā)端都已知的固定比特（即凍結(jié)比特）.

2.1 Polar 碼編碼

依照polar 碼P(N,K,A,uAc) 的參數(shù)形式，N為碼長，碼率可以表示為K/N，設(shè)A是集合{1,··· ,N}的長度為N的子集，uA用來存放信息位；Ac是A的補(bǔ)集，uAc用于描述已知的凍結(jié)比特，一般都取0.長度為N的polar 碼的編碼過程由待傳輸?shù)男畔⑿蛄?(u1,u2,··· ,uN)與生成矩陣GN相乘完成[13]，即

式中，GN=BNF?n，F(xiàn)?n是核心矩陣的n次Kronecker 張量積.式(11)可進(jìn)一步表示為

式中，GN(A)是由集合A對應(yīng)生成矩陣GN的行向量所構(gòu)成的子矩陣.

圖1 各種干擾情況下的MLC 閃存單元閾值電壓統(tǒng)計Figure 1 MLC flash cell threshold voltage statistics with different noise interference

2.2 Polar 碼譯碼

Polar 碼的凍結(jié)位對于編譯碼兩端是已知的，因此polar 碼譯碼實(shí)際上是對信息位的譯碼.polar 碼的譯碼算法主要有連續(xù)消除（successive cancellation, SC）算法，置信傳播（belief propagation, BP）算法[14]等.其中BP 算法是基于Tanner 圖實(shí)現(xiàn)具體譯碼過程的，詳細(xì)步驟如下：

步驟1初始化.

步驟2傳遞與更新.首先每個校驗(yàn)節(jié)點(diǎn)與子節(jié)點(diǎn)分別傳遞消息給父節(jié)點(diǎn)，各個父節(jié)點(diǎn)利用接收到的消息更新本節(jié)點(diǎn)的消息；然后父節(jié)點(diǎn)將更新后的消息又傳遞給子節(jié)點(diǎn)，各個子節(jié)點(diǎn)繼續(xù)更新本身的消息.

步驟3迭代終止.子、父節(jié)點(diǎn)根據(jù)收到的消息將每次迭代后的最終消息進(jìn)行硬判決，譯碼成功則不再迭代，否則進(jìn)行下一次迭代直至最大迭代次數(shù).

BP 算法具有并行運(yùn)算的優(yōu)點(diǎn)，與SC 譯碼算法相比，譯碼速度較快，因此本文采取BP算法作為polar 碼的譯碼算法.

3 基于MI 異構(gòu)的polar 碼優(yōu)化

本文借助蒙特卡羅方法，利用大量隨機(jī)信息建立MLC 型閃存的概率模型，經(jīng)過噪聲（CCI、DRN 等）的干擾，統(tǒng)計MLC 存儲單元各個狀態(tài)的閾值電壓分布.將一隨機(jī)序列經(jīng)過MLC 型閃存信道后的LLR 值?計算出：和P(?|x=1)=1?P(?|x=0)，通過式(13)得到其對應(yīng)的互信息量I(?,X)

然后在傳統(tǒng)的AWGN 信道中以互信息量I(?,X)得到等價的方差δe.本文正是利用所獲得的新方差計算存儲單元比特的巴氏參數(shù)值實(shí)現(xiàn)一對polar 碼的構(gòu)造.巴氏參數(shù)可用來衡量極化后存儲單元比特的存儲可靠性，定義為

式中，巴氏參數(shù)越小，該存儲單元比特的數(shù)據(jù)可靠性就越高.每存儲單元比特的巴氏參數(shù)值計算公式為

本文采用一種近似的方法計算巴氏參數(shù)的迭代初始值

式中，δe為LLR 分布的等效方差，C(δe)是根據(jù)已知δe利用Ungerboeck 集分割方式并計算存儲單元比特的容量.

已知碼率R和碼長N，將提出的polar 碼構(gòu)造方法應(yīng)用到MLC 型NAND 閃存信道中，其詳細(xì)算法如下.

算法1基于MI 異構(gòu)的polar 構(gòu)造算法

輸入：碼率R，碼長N，最大迭代次數(shù)Nite-max，隨機(jī)信息l

初始化計算凍結(jié)比特數(shù)K ←N(1?R)；

將隨機(jī)信息l傳送至MLC 閃存信道，得到LLR 值?；

由式(13)計算I(?,X)；

基于MI 重新擬合使?在AWGN 信道下服從高斯分布，得到其在AWGN 信道下等效的方差δe；

基于式(15)～(16)以及新方差δe可獲取所有存儲單元比特的巴氏參數(shù)值；

將得到的進(jìn)行降級排序，選取前K個單元比特作為凍結(jié)比特位來實(shí)現(xiàn)對polar 碼的優(yōu)化構(gòu)造.

該polar 碼優(yōu)化方法通過利用MLC 閃存信道的特性，與傳統(tǒng)的AWGN 信道之間建立聯(lián)系，以MI 來重新擬合信道的LLR 信息并使其呈現(xiàn)高斯分布，而MLC 閃存信道與AWGN 信道間的差異性能用MI重新擬合方法來計算，因此傳統(tǒng)的polar 碼構(gòu)造方法不再適用于MLC閃存信道.

文獻(xiàn)[5]中采用的基于最大互信息的優(yōu)化方法利用最大化MLC 存儲信道的輸入與輸出之間的互信息量，其中根據(jù)MLC 閃存單元的最高有效位和最低有效位計算互信息量來獲取讀取電壓值RN.而本文提出的優(yōu)化方法[15]采用非均勻量化，在靠近閾值電壓分布的交疊處（即易發(fā)生錯誤的區(qū)域）設(shè)置感知電壓，并且通過閾值電壓來計算熵值H(v)，公式為

然后設(shè)置熵值H(RN)=θ(θ ∈[0,1])，獲取重疊區(qū)的讀取電壓RN，提高易發(fā)生錯誤區(qū)感知電壓的精度并實(shí)現(xiàn)良好的polar 碼糾錯能力.

4 仿真結(jié)果

為了研究MLC 型閃存信道中存儲數(shù)據(jù)的耐久度和可靠性，本文以提出的基于MI 異構(gòu)的polar 碼構(gòu)造方案進(jìn)行數(shù)據(jù)仿真，來驗(yàn)證其BER(bit error rate)和FER(frame error rate)性能.其中polar 碼碼長N= 2 048，采用BP 譯碼算法并且設(shè)置最大迭代次數(shù)Nitemax= 50.本文中MLC 型閃存信道噪聲考慮CCI、PN 和DRN 干擾，設(shè)置如下參數(shù)：Vmin= 1.40，σe=0.35，V1= 2.60，V2= 3.20，Vmax= 3.93，σpn= 0.05，x0= 1.4，Xt= 0.000 055，Yt=0.000 235，θi=0.62，θ0=0.32，T=6 h.

圖2 為碼率R= 0.75 的polar 碼基于不同的構(gòu)造方法的BER 性能曲線，同時與文獻(xiàn)[5]進(jìn)行了實(shí)驗(yàn)對比.高斯近似法構(gòu)造的polar 碼性能最差，當(dāng)誤碼率BER=1×10?5時，本文優(yōu)化的polar 碼比巴氏參數(shù)法構(gòu)造的polar 碼能增加1 000 次的擦除次數(shù).相比于文獻(xiàn)[5]中方法構(gòu)造的polar 碼，本文提出的方法構(gòu)造的polar 碼在誤碼率性能上有1 個數(shù)量級的提升.

圖3 和4 分別為碼率R=0.80 的polar 碼基于不同的構(gòu)造方法的BER 和FER 性能曲線.圖3 表明當(dāng)誤碼率約為2×10?5時，新構(gòu)造的polar 碼擁有23 200 次的擦除次數(shù)，比巴氏參數(shù)法構(gòu)造的polar 碼和蒙特卡羅法優(yōu)化的polar 碼分別增加2 000 和6 800 的擦除次數(shù).圖4 顯示當(dāng)P= 2.1×104時，本文優(yōu)化的polar 碼比巴氏參數(shù)法構(gòu)造的polar 碼和蒙特卡羅法構(gòu)造的polar 碼在誤碼率上分別有1 個和2 個數(shù)量級的提升.當(dāng)P <2.5×104時，本文提出的優(yōu)化方法構(gòu)造的polar 碼比文獻(xiàn)[5]優(yōu)化方法構(gòu)造的polar 碼在誤碼率性能上至少提升半個數(shù)量級.

比較圖5 和6 可以看出，當(dāng)碼率R增長至0.85，本文提出的polar 碼仍優(yōu)于其他方法構(gòu)造的polar 碼.當(dāng)P >1.5×104時，改進(jìn)的polar 碼至少比巴氏參數(shù)法構(gòu)造的polar 在性能上有1 個數(shù)量級的提升，而蒙特卡羅法優(yōu)化的polar 碼也會優(yōu)于巴氏參數(shù)構(gòu)造的polar 碼.本文提出的優(yōu)化方法構(gòu)造的polar 碼比文獻(xiàn)[5]優(yōu)化方法構(gòu)造的polar 碼在誤碼率性能上的表現(xiàn)趨于吻合.

圖2 MLC 型NAND 閃存信道中碼率R=0.75 的polar 碼BER 性能比較Figure 2 BER performance comparison of polar codes in MLC NAND flash channel(R=0.75)

圖3 MLC 型NAND 閃存信道中碼率R=0.80 的polar 碼BER 性能比較Figure 3 BER performance comparison of polar codes in MLC NAND flash channel(R=0.80)

圖4 MLC 型NAND 閃存信道中碼率R=0.80 的polar 碼FER 性能比較Figure 4 FER performance comparison of polar codes in MLC NAND flash channel(R=0.80)

圖5 MLC 型NAND 閃存信道中碼率R=0.85 的polar 碼BER 性能比較Figure 5 BER performance comparison of polar codes in MLC NAND flash channel(R=0.85)

圖6 MLC 型NAND 閃存信道中R=0.85 的polar 碼FER 性能比較Figure 6 FER performance comparison of polar codes in MLC NAND flash channel(R=0.85)

從圖2～6 可以看出，隨著碼率的增加，本文提出的優(yōu)化方法構(gòu)造的polar 碼與文獻(xiàn)[5]中的優(yōu)化方法構(gòu)造的polar 碼在誤碼率性能上趨于一致.當(dāng)碼率升高時，MLC 閃存單元的交疊區(qū)發(fā)生錯誤的比特數(shù)增加，polar 碼的糾錯能力也會下降.

5 結(jié) 語

根據(jù)MLC 閃存信道的特性，本文提出了一種基于MI 異構(gòu)的polar 優(yōu)化方法.該方法基于MI 對MLC 閃存信道的LLR 分布重新擬合，得到與閃存信道等效的方差從而進(jìn)行polar 碼的優(yōu)化構(gòu)造.仿真結(jié)果表明本文構(gòu)造的polar 碼性能優(yōu)于傳統(tǒng)方法構(gòu)造的polar 碼，且比蒙特卡羅法構(gòu)造的polar 碼有多達(dá)2 個數(shù)量級的性能提升.此外，本文提出的優(yōu)化方法也可以應(yīng)用到3 層存儲單元（trinary-level-cell, TLC）閃存、4 比特單元（quad-level-cell, QLC）閃存等高密度存儲系統(tǒng)中.