Low-Complexity Detection and Decoding Scheme for LDPC-Coded MLC NAND Flash Memory

Xusheng Lin, Guojun Han,＊, Shijie Ouyang, Yanfu Li, Yi Fang,2

1 School of Information Engineering, Guangdong University of Technology, Guangzhou 510006, China

2 National Mobile Communications Research Laboratory, Southeast University, Nanjing 210096, China

I. INTRODUCTION

In the past five years, NAND flash memory has been widely applied in a large number of electronic products [1]. Based on the multi-level cell (MLC) storage technology[2], NAND flash memory can store more than one bit in each memory cell. Because of its obvious advantages in terms of storage density and low cost, MLC NAND flash memory now largely dominates global flash memory market [3]. However, with the density increasing,cell-to-cell interference (CCI) becomes more serious and hence causes an increase in the raw bit error rate of data stored in the cells.

To ensure the reliability of storage data,error-correction codes (ECCs) have been gradually applied in MLC NAND flash memory.In [4] and [5], some traditional hard-decision ECCs such as BCH codes and RS codes have been used for NAND Flash memory. With regard to other ECCs, soft-decision error correction codes such as low-density parity-check (LDPC) codes have been adopted in MLC NAND flash memory [6] thanks to its outstanding error correction performance. In a general way, the sum-product algorithm (SPA)[7] is considered as the most well-known decoding algorithm based on iterative soft-decision. However, its complexity is large. In order to reduce the complexity of decoding,some simplified decoding algorithms, e.g.,soft reliability-based iterative majority-logic decoding (SRBI-MLGD) algorithm and Minsum algorithm over AWGN channel have been presented in [8] and [9], which can greatly reduce the decoding complexity while keeping the relative good error correction performance.

In this paper, taking the trade-off between the performance and complexity into consideration, we adopt a non-uniform detection(N-UD) to detect the threshold voltage of the NAND flash memory cell. The N-UD can improve the log likelihood ratio (LLR) accuracy because the LLR calculation is related to the threshold voltage. To keep the lower detection complexity and latency, we just set two soft-decision reference voltages in the overlap area of threshold voltage, and the achieving average maximum mutual information [10]is used to select the value of the soft-decision reference voltages of N-UD. Furthermore, to reduce the decoding complexity and improve the decoding performance, we adopt a modified SRBI-MLGD (MSRBI-MLGD) algorithm to decode LDPC codes for MLC NAND flash memory. In this MSRBI-MLGD algorithm, anon-uniform quantizer based on power functionis used to quantize input LLRs. By joint the N-UD with the low complexity decoding,we can improve the overall detection performance of LDPC-coded MLC NAND flash memory.

This paper is organized as follows. In Section II, a brief introduction of the structure of MLC NAND flash memory as well as the CCI are presented. Besides, the LLR calculation of threshold voltage of NAND flash memory cells is also given. In Section III, we introduce the N-UD and the non-uniform quantization of LLR for MSRBI-MLGD algorithm over the MLC NAND flash memory channel. Simulation results and analysis are shown in Section IV and the conclusion is given in Section V.

In this paper, the authors adopt a N-UD method to obtain the threshold voltages through analyzing the characteristics of MLC NAND flash memory.

II. PRELIMINARIES OF MLC NAND FLASH MEMORY

In NAND flash memory, information bits are stored in the floating gate transistors which called NAND flash memory cells. The voltage of the floating gate is called as threshold voltage which varies with programming process.Different threshold voltage represents different bit information. Conventional single-level cell (SLC) has two storage states which means that it can only store one bit in each cell, while MLC has 2bstorage states and it can storebbits in each cell. Although MLC technology possesses relatively higher storage density, it is more vulnerable to raw bit error due to the parasitic capacitance coupling effect while programming.

2.1 Cell-to-cell interference

In previous research [11], [12], NAND flash memory can be modeled as a channel whose characteristic is similar with the normal communication channel. In this MLC NAND flash memory channel model, there are several types of noise which can influence the reliability of information stored on the chip. Among these interferences, CCI is the major noise. The threshold-voltage shift of one cell may influence the threshold voltage of its neighboring cells due to the parasitic capacitance coupling effect. With scaling down of the NAND flash memory, CCI will become more and more serious. The threshold-voltage shift of a victim cell affected by CCI ofnadjacent cells can be described as [11]

Fig. 1. All bit-line structure and coupling effect of victim cell.

whererepresents the threshold-voltage shift of one interfering cell which is programmed after the victim cell and γ(n)represents the coupling ratio.

At present, there are two major types of bitline structures of NAND flash memory, one is the even/odd bit-line structure, the other is all bit-line structure. Due to different programming order, the CCI is different. In all bitline structure, cells along each word line are programmed at the same time. Thus each cell was mainly affected by three neighboring cells as shown in figure 1. In this paper, we just consider the all bit-line structure. The threshold-voltage shift of a victim cell in all bit-line structure can be expressed specifically by

wherepandqrepresent the position of wordline and bit-line, respectively.?V(p,q)represents the threshold-voltage shift of the interfering cell at(p,q)position. As shown in figure 1, γyand γxyare coupling ratios of the floating gate in the vertical and diagonal direction, respectively.

Fig. 2. Shift of the probability density functions (PDFs) of the threshold voltage after CCI in a 2bit/cell NAND flash memory.

2.2 LLR calculation of MLC NAND flash memory cells

When LDPC codes are used to correct errors over MLC NAND flash memory channel, we need to calculate the LLR for each coded bit if the soft-decision decoding algorithms are adopted. LetVthrepresent the threshold voltage of a flash memory cell. We assume that the prior probability of 0 or 1 for each bitzof each flash memory cell is equal in the beginning. Thus, the LLR of theith bit of a flash memory cell can be calculated by [13].

Letbrepresent the number of bits stored in each flash memory cell. Hence, there areK=2bstorage states. Letpk(x) denote the probability density function of the threshold voltage of thekth storage state after interferences, where 0 ≤k≤K? 1.k=0 corresponds to the erased state andk>0 corresponds to the programmed state with the higher threshold voltage. LetSidenote the set of states whoseith bit is 1. Therefore, given the threshold voltage of a cell, we can calculate the LLR of each bit as [13].

We assume that the MLC NAND flash memory has only the CCI and the flash memory is all bit-line structure. μeand σedenote the mean and standard deviation of the erased state threshold voltage, respectively.The threshold voltage of the programmed state tends to have a uniform distribution over[Vp,Vp+?Vpp].Vpis the normalized verify voltages and ?Vppis the normalized program step voltage. Denote ?Vppand for thekth programmed state asand. Letpc(x)represent the probability density function of the threshold voltage of CCI. Letpe(x) rep-resent the probability density function of the threshold voltage of the erased state before interferences. Let(x) represent the probability density function of the threshold voltage of the programmed state before interferences.Whenk=0the probability density functionp(0)(x) is

and whenk＞0the probability density functionp(k)(x) is

where ? is the convolution calculation.

Figure 2 shows that the shift of the probability density functions (PDFs) of the threshold voltage after CCI in a 2 bits/cell NAND flash memory.

According to the probability density function of the threshold voltage presented in[13].p(0)(x) andp(k)(x) can be calculated as

where δ(x) represents the Dirac drlta function.

Assume that the threshold voltageVthof a cell falls into the range [Rl,Rr] (whereRlandRrare two adjacent reference voltages), we can ultimately calculate the LLR of each bit as

III. MSRBI-MLGD ALGORITHM FOR LDPC CODES IN NAND FLASH MEMORY WITH NON-UNIFORM DETECTION

3.1 Non-uniform detection for threshold voltage

Fig. 3. Uniform detection for threshold voltage of a 2 bits/cell NAND flash memory.

The uniform detection (UD) method often if xes several hard-decision reference voltages and these hard-decision reference voltages lie between each state. As illustrated in figure 3,Vthr,1,Vthr,2andVthr,3are the hard-decision reference voltages for a 2 bits/cell NAND flash memory. Such UD method can achieve good performance when the interference is weak. However, when the interference is serious, the performance of this detection is degraded due to the overlap of threshold voltage for each state. In such a case, the N-UD method can be used to improve the performance of detection according to [13]. With an aim to keep the lower detection complexity and latency, we just set two soft-decision reference voltages in the threshold voltage overlap to achieve N-UD as shown in figure 4 and the two soft-decision reference voltages can be set by using achieving average maximum mutual information (MI).qrepresents the difference between the soft-decision reference voltages and the hard-decision reference voltages.

Fig. 5. A hard-decision reference voltage reference and two soft-decision reference voltage ± q are set between two adjacent storage states.

Fig. 6. Equivalent discrete memoryless channel model for two adjacent storage stages.

As illustrated in figure 5 and figure 6, The two adjacent storage states can be equivalent to a discrete memoryless channel (DMC).Assuming the input isX∈{0, 1} and output isY∈{00, 0 1, 10, 11}, the MII(X;Y) can be calculated as [10]

3.2 Non-uniform quantization of llr based on power function for MSRBI-MLGD algorithm

Due to the particularity of MLC NAND flash memory channel, the calculation and quan-tization of LLR are quite different from that for conventional AWGN channel. In order to improve the decoding performance and consider the characteristic of MLC NAND flash memory channel, we present anon-uniform quantization based on power function.

Let: 1)mbe the quantitative level for the MSRBI-MLGD algorithm; 2)rbe the power of the power function for non-uniform quantization 3)bbe the number of bits that can be stored in each cell; 4)z=(z1,z2,...,zb) be the information sequence stored in each flash memory cell ; 5)L(zi) be the LLRinformation ofith bit in the flash memory cell, for 1≤i≤b.

Due to the maximum quantitative valueQmaxis 2m?1? 1 and the minimum quantitative valueQminis ?(2m?1?1), we can define a step increment of quantization as

According to ?Q, we can obtain each quantization valueQ. Given an initializedQ1,Qμ=Qμ?1+?Q, where μ ∈{2, 3,...}.

To the best of our knowledge, LLR information is unreliable when its value is close to 0 and it needs a higher precision quantization.Therefore, we use anon-uniform quantizer based on power functionfor the MSRBI-MLGD algorithm.

In this non-uniform quantization, assuming the absolute value of LLR information is| LLR|, then the maximum | LLR| of bit in all NAND flash memory cells corresponds to the maximum quantization valueQ2m/2.

As shown in figure 7, whenm=4 we can get 16 quantization values.Q1,Q2, ... ,Q8are the quantization values which are bigger than 0.We setLth8=max(|LLR|) andLth8=Q8rthen the power

In order to ensure the power function can be set as an increasing function thatr>1, we will magnify all the values of | LLR| of bit to make the value of the maximum |LLR| of bit is bigger thanQ2m/2, which the magnification times β( β ＞ 0) is based on the value of the maximum |LLR| of bit andQ2m/2. This magnification step will not change real LLR information of bit.

The threshold values of |LLR| of bit for the NAND flash memory cells can be set as

for 1≤j≤8.

By means of the comparison betweenLthjand |L(zi)|, we can set the quantization value forL(zi) as the initial information φiofzito decode by

for 2≤j≤8.

By using thisnon-uniform quantizer based on power function, the LLR information which its value is close to 0 has a higher precision quantization and the LLR information which its value is far away from 0 has a lower precision quantization.

Non-Uniform Quantization of LLR and Initialization for MSRBI-MLGD Algorithm(MSRBI-MLGD Algorithm for MLC NAND Flash Memory):

Fig. 7. The quantitative value Q and the threshold value of |LLR| of bit in the non-uniform quantization based on power function when quantitative level m=4.

? Non-uniform detection: detect the threshold voltage of each MLC NAND flash memory cell.

? Obtain LLR information: calculate LLR information of each bit in each flash memory cell.

1) Set the quantitative level m and get the each quantization valueQaccording to step increment ?Q.

2) According to maximum |LLR|, determine the value of the powerrand set the threshold values of |LLR| of the flash cellLthj, for 1 ≤j≤ 2m/2.

otherwise, φiis other quantization valueQaccording to the range of the threshold values of |LLR| that |L(zi)| locates.

4) Use the SRBI-MLGD algorithm to decode.

Since the initial information of each bit in each flash cell is an integer, and its extrinsic-information [9] is also an integer in each iteration, so its computational modification of reliability information is an integer too. As a result, the MSRBI-MLGD algorithm only needs the logical operations and integer addition as in the SRBI-MLGD algorithm, which greatly reduces the computational complexity of decoding as compared to SPA and Min-sum algorithm.

Fig. 8. The BER performance of the (504,2331) QC-LDPC code over the 3bits/cell NAND flash memory channel with the N-UD and UD and decoded with SRBI-MLGD algorithm as well as the Min-sum algorithm. The maximum number of iteration is 100.

IV. SIMULATION

The performance of a binary LDPC-coded NAND flash memory system detected and decoded with our proposed joint detection and decoding scheme is presented in this section.We adopt a NAND flash memory that can store 3 bits in a cell. The binary LDPC code is a rate-0.784 length-2331 (504, 2331) quasi-cyclic (QC) LDPC code. This code is constructed by using algebraic approaches [14] and has 56 variable-nodes with degree 7 and the other variable-nodes with degree 8, and a constant check-node degree 36.We set μeand σeof the erased state as 1.4 and 0.4, respectively.For the seven programmed state, ?Vppis set to 0.2, and Vp are set to 2.7, 3.4, 4.1, 4.8, 5.5,6.2 and 6.9, respectively. We adopt a parameter s called cell-to-cell coupling strength factor[3], and γyand γxyequal 0.08s and 0.0064s,respectively.

We perform Monte-Carlo simulation over the 3 bits/cell NAND flash memory channel with differentsto determine the two soft-decision reference voltages. By using achieving maximum mutual information, wefixq=0.06V for different value ofs.

Figure 8 shows the bit error ratio (BER)of the (504, 2331) QC-LDPC code over the 3 bits/cell NAND flash memory channel with the N-UD and UD and decoded with the SRBI-MLGD algorithm as well as the Min-sum algorithm. The quantization level for SRBI-MLGD algorithm ism=6. The maximum number of iterations is 100. Fromfigure 8 we see that the N-UD can achieve better performance than the UD. We also see that the performance of the SRBI-MLGD algorithm withm=6 is relatively close to that of the Min-sum algorithm under both the N-UD and UD.

Figure 9 shows the BER performance of the (504, 2331) QC-LDPC code over the 3 bits/cell flash memory channel with the N-UD and UD and decoded with the MSRBI-MLGD algorithm as well as the SRBI-MLGD algorithm. In order to achieve a better performance, we set maximum |LLR|=6.5 and β=100 after a lot of simulations. We observe that with thenon-uniform quantizer based on power function, the performance of the MSRBI-MLGD algorithm is better than SRBI-MLGD algorithm.

Figure 10 shows the BER performance of the (504, 2331) QC-LDPC code over the 3 bits/cell flash memory channel with N-UD and decoded by the MSRBI-MLGD algorithm with different quantization levels. We observe that with the increase of the quantization levels, the performance of the MSRBI-MLGD algorithm can be gradually improved. However, this improvement becomes smaller and smaller whenm>5.

Figure 11 shows the BER performance of the (504,2331) QC-LDPC code and (128,1152)Richardson LDPC code over the 3 bits/cell NAND flash memory channel with the N-UD and UD and decoded with the MSRBI-MLGD algorithm (m=6). The Richardson LDPC code is a rate-0.888 length-1152 (128,1152) binary LDPC code. The variable-nodes of this code has different degree such as 2, 3, 6, 7, 9, 10,and the check-node degree is 52. We can find that the MSRBI-MLGD algorithm is suitable for LDPC codes with different code length and code rate.

The BER performance of the (504,2331)QC-LDPC code over the 3 bits/cell flash memory channel vs. the number of iterations when decoded with the MSRBI-MLGD algorithm and SRBI-MLGD algorithm is shown in figure 12.sis set to 1.05. We see that the performance of the MSRBI-MLGD algorithm outperforms the SRBI-MLGD algorithm when the number of iterations is bigger than 15.With the increase of the number of iterations,the performance of the MSRBI-MLGD algorithm can be gradually improved when the number of iterations exceeds 30. This means that we can achieve a trade-off between the performance and the complexity for the MSRBI-MLGD algorithm by adjusting the maximum number of iterations.

V. CONCLUSIONS

Fig. 10. The BER performance of the (504,2331) QC-LDPC code over the 3bits/cell NAND flash memory channel with N-UN and decoded by the MSRBI-MLGD algorithm with different quantization levels. The maximum number of iterations is 100.

In this paper, we adopt a N-UD method to obtain the threshold voltages through analyzing the characteristics of MLC NAND flash memory, which can remarkably improve the LLR accuracy of each bit in MLC NAND flash memory cells. The N-UD is formulated by using achieving average maximum mutual information of NAND flash memory cells.Although N-UD increases a little latency relatively, it can effectively improve the detection performance. Besides, in order to reduce the decoding complexity and improve the decoding performance, we develop a MSRBI-MLGD algorithm by using anon-uniformquantizer based on power functionto decode LDPC codes. Simulation results and analysis prove that our design can offer the better performance and lower complexity for high-column-weight LDPC-coded MLC NAND flash memory.

Fig. 11. The BER performance of the (504,2331) QC-LDPC code and (128,1152)Richardson LDPC code over the 3bits/cell NAND flash memory channel with the N-UD and UD and decoded with the MSRBI-MLGD algorithm(m=6).The maximum number of iterations is 100.

Fig. 12. The BER performance of the (504,2331)QC-LDPC code over the 3bits/cell NAND flash memory channel vs.the number of iterations when decoded with the MSRBI-MLGD algorithm and SRBI-MLGD algotithm. The cell-to-cell coupling strength factor s=1.05.

ACKNOWLEDGEMENT

This work was supported in part by the NSF of China (61471131, 61771149, 61501126), NSF of Guangdong Province 2016A030310337, the open research fund of National Mobile Communications Research Laboratory, Southeast University (No. 2018D02), and the Guangdong Province Universities and Colleges Pearl River Scholar Funded Scheme (2017-ZJ022).

[1] S. Ou, G. Han, Y. Fang, and W. Liu, “LLR-distribution-based nonuniform quantization for RBI-MSD algorithm in MLC flash memory,”IEEE Commun. Lett., vol.22, no.1, pp. 45--48, Dec.2017.

[2] Y. Cai, S. Ghose, E. F. Haratsch, Y. Luo, and O.Mutlu, ``Error characterization, mitigation, and recovery in flash-memory-based solid-state drives,’ inProc. IEEE, vol.105, no.9, pp. 1666--17048, Sep. 2017.

[3] G. Dong, N. Xie and T. Zhang, ``Techniques for embracing intra-cell unbalanced bit error characteristics in MLC NAND flash memory,’ inProc.IEEE GC Workshops, Dec. 2010, pp. 1915-1920.

[4] W. Liu, J. Rho and W. Sung, ``Low-power high-throughput BCH error correction VLSI design for multi-level cell NAND Flash memories,’inProc. IEEE Workshop. Signal Process Syst, Oct.2006, pp. 303--308.

[5] R. Micheloni, et al, ``A 4Gb 2b/cell NAND flash memory with embedded5b BCH ECC for 36MB/s system read throughput,’ inProc. ISSCC Dig.Tech. Papers, Feb. 2006, pp. 497--506.

[6] Y. Maeda and H. Kaneko, ``Error control coding for multilevel cell flash memories using nonbinary low-density parity-check codes,’ inProc.4th IEEE International Symposium on Defect andFault Tolerance in VLSI Systems, Oct. 2009,pp. 367--375.

[7] T. J. Richardson, M. A. Shokrollahi and R. L. Urbanke, ``Design ofcapacity-approaching irregular low-density parity-check codes,’IEEE. Trans.Inform. Theory, vol.47, no.2, pp. 619--637, Feb.2001.

[8] H. Chen, K. Zhang. Ma and B. Bai, ``Comparisons between reliability-based iterative min-sum and majority-logic decoding algorithms for LDPC codes,’IEEE Trans. Commun, vol.59, no.7, pp.1766--1771, July. 2011

[9] Q. Huang, J. Kang, L. Zhang, S. lin and K. Abdel-Ghaffar, ``Two reliability-based iterative majority-logic decoding algorithms for LDPC codes,’IEEE Trans. Commun, vol.57, no.12, pp.3597--3606, Dec. 2009.

[10]J. Wang, K. Vakilinia and T. Chen, ``Enhanced precision through multiple reads for LDPC decoding in flash memories,’IEEE J.Sel. Areas.Commun, vol.32, no.5, pp. 880--891, May. 2014.

[11] X. Wang, G. Dong, L. Pan and R. Zhou, ``Error correction codes and signal processing in flash memory},’ emph{Flash Memories. InTech, Prof.Igor Stievano (Ed.), ISBN: 978-953-307-272-2.

[12] C. A. Aslam, Y. Guan and K. Cai, ``Read and write voltage signal optimization for multi-level-cell(MLC) NAND flash memory,’IEEE Trans. Commun, vol.64, no.4, pp. 1613--1623, Feb. 2016.

[13] G. Dong, N. Xie and T. Zhang, ``On the use of soft-decision error-correction codes in NAND flash memory,’IEEE Trans. Circuits and Systems I: Regular Papers, vol.58, no.2, pp. 429--439,Feb. 2011.

[14] S. Song, B. Zhou, S. Lin and K. Abdel-Ghaffar, ``A unified approach to the construction of binary and nonbinary quasi-cyclic LDPC codes based on finite fields,’IEEE Trans. Commun, vol. 57, no.1, pp. 84-93, Jan. 2