logo

Journals Books
Advanced Search
Sign in Register

中文

SCIENCE CHINA Information Sciences
Download PDF
SCIENCE CHINA Information Sciences, Volume 61 , Issue 10 : 102307(2018) https://doi.org/10.1007/s11432-017-9394-y

Polar-coded forward error correction for MLC NAND flash memory

Haochuan SONG 1,2,3, Jen-Chien FU 4, Shih-Jia ZENG 4, Jin SHA 5, Zaichen ZHANG 2,3, Xiaohu YOU 3, Chuan ZHANG 1,2,3,*
More info
  • ReceivedDec 5, 2017
  • AcceptedFeb 27, 2018
  • PublishedAug 21, 2018
Previous Table of Contents Next
Share
Rating

Abstract


Acknowledgment

This work was supported in part by National Natural Science Foundation of China (NSFC) (Grant Nos. 61501116, 61571105), Jiangsu Provincial NSF for Excellent Young Scholars (Grant No. BK20140636), Huawei HIRP Flagship (Grant No. YB201504), Fundamental Research Funds for the Central Universities, SRTP of Southeast University, State Key Laboratory of ASIC System (Grant No. 2016KF007), ICRI for MNC, and Project Sponsored by the SRF for the Returned Overseas Chinese Scholars of MoE.


Supplement

Appendix

Proof for Gray code mapping scheme

Lemma A1 Gray code can achieve best coding gain compared with any other mapping schemes.

proof As mentioned in Subsection sect. 3.1, we have noticed that most raw errors happen when a voltage is mistaken for its adjacent levels. Therefore, we can focus on overlapped regions when talking about mapping schemes. For the convenience of discussion, we use $4$ column vectors to indicate $4$ different states in a $2$-bit memory cell namely

$$A = \left( \begin{array}{l}0\\0\end{array} \right), B = \left( \begin{array}{l}1\\0\end{array} \right), C = \left( \begin{array}{l}1\\1\end{array} \right), D = \left( \begin{array} {l} 0\\1\end{array} \right).$$

By making a full permutation for these states, we get 24 different schemes as shown in Table tab:Gray~total.

Each scheme has $2$ rows and if $1$ bit is different from its neighbouring bits in a row, we will call it a change. For example, the combination $ABCD$ indicates the mapping scheme shown in Table AA2. In this case, the number of changes is $3$. The statistical results are shown in Table tab:Gray~total . We can conclude by enumeration that the number of changes is $3$ if and only if the mapping scheme is in Gray code. Other alternatives' number of changes are $4$ or $5$.

We have already known that raw errors usually happen in overlapped regions. For a $2$-bit cell, there remains $3$ overlapped regions. Assume the raw error probability for each region is $P_1$, $P_2$ and $P_3$, respectively. Therefore, the expectation of raw errors $N_G$ of mapping schemes using Gray code is

\begin{equation} N_G=P_1+P_2+P_3, \tag{23}\end{equation}

whereas the expectation of all other alternatives is

\begin{equation} \begin{aligned} N_A = \alpha {P_1} + \beta {P_2} + \gamma {P_3} (\alpha + \beta + \gamma = 4\text{ or }5, \alpha \beta \gamma\neq 0). \end{aligned} \tag{24}\end{equation}

$N_A$ is absolutely bigger than $N_G$. In other words, we can tell that Gray code is the best choice for mapping schemes.

Calculation of boundaries in quantized-soft decoder

In Subsection sect. 3.5 we have mentioned that the derivation for (13) is wrong in [9]. This section will re-derive (12).

Since $p^{k}(x)$ is a Gaussian distribution, $p^{(k)}(B_l^{(k)})$ and $p^{(k+1)}(B_l^{(k)})$ are

\begin{equation}\left\{ \begin{aligned} & {p^{(k)}}\left(B_l^{(k)}\right)= \dfrac{1}{{{\sigma _k}\sqrt {2\pi } }}\exp \left( - \dfrac{{{{(B_l^{(k)} - {\mu _k})}^2}}}{{2\sigma _k^2}}\right), \\ & {p^{(k + 1)}}\left(B_l^{(k)}\right) =\dfrac{1}{{{\sigma _{k + 1}}\sqrt {2\pi } }}\exp \left( - \dfrac{{{{(B_l^{(k)} - {\mu _{k + 1}})}^2}}}{{2\sigma _{k + 1}^2}}\right). \end{aligned} \right. \end{equation}

Therefore, the fraction in the left will be expanded below

\begin{equation}\frac{{{\sigma _k}}}{{{\sigma _{k + 1}}}}R = \exp \left( - \frac{{{{(B_l^{(k)} - {\mu _k})}^2}}}{{2\sigma _k^2}} + \frac{{{{(B_l^{(k)} - {\mu _{k + 1}})}^2}}}{{2\sigma _{k + 1}^2}}\right).\end{equation}

Take the log of both sides of the equation, we get

\begin{equation}\log\left(\frac{{{\sigma _k}}}{{{\sigma _{k + 1}}}}R\right) = - \frac{{{{(B_l^{(k)} - {\mu _k})}^2}}}{{2\sigma _k^2}} + \frac{{{{(B_l^{(k)} - {\mu _{k + 1}})}^2}}}{{2\sigma _{k + 1}^2}}.\end{equation}

Multiply $\sigma~_k^2\sigma~_{k~+~1}^2$ on both sides to remove the denominator, then we have

\begin{equation*}2{\sigma _k^2\sigma _{k + 1}^2}\log \left(\frac{{{\sigma _k}}}{{{\sigma _{k + 1}}}}R\right) = - \sigma _{k + 1}^2{({B_l}^{(k)} - {\mu _k})^2}+ \sigma _k^2{({B_l}^{(k)} - {\mu _{k + 1}})^2},\end{equation*}

 as shown in (13).

The other fraction can be derived in the same way.


References

[1] Li S, Zhang T. Improving multi-level NAND flash memory storage reliability using concatenated BCH-TCM coding. IEEE Trans VLSI Syst, 2010, 18: 1412-1420 CrossRef Google Scholar

[2] Kim J, Sung W. Low-energy error correction of NAND flash memory through soft-decision decoding. EURASIP J Adv Signal Process, 2012, 2012: 195 CrossRef ADS Google Scholar

[3] Grupp L M, Davis J D, Swanson S. The bleak future of NAND flash memory. In: Proceedings of the 10th USENIX Conference on File and Storage Technologies, San Jose, 2012. Google Scholar

[4] Bellorado J, Yaakobi E. Signal processing and coding for non-volatile memories. Non-Volatile Memory Workshop, 2013. http://faculty.cs.tamu.edu/ajiang/NVMW_Tutorial.pdf. Google Scholar

[5] Li Y, Lee S, Fong Y. A 16 Gb 3-Bit per cell (X3) NAND flash memory on 56 nm technology with 8 MB/s write rate. IEEE J Solid-State Circ, 2009, 44: 195-207 CrossRef ADS Google Scholar

[6] Shibata N, Maejima H, Isobe K. A 70 nm 16 Gb 16-level-cell NAND flash memory. IEEE J Solid-State Circ, 2008, 43: 929-937 CrossRef ADS Google Scholar

[7] Trinh C, Shibata N, Nakano T, et al. A 5.6 MB/s 64 Gb 4b/cell NAND flash memory in 43 nm CMOS. In: Proceedings of IEEE International Solid-State Circuits Conference, San Francisco, 2009. 246--247. Google Scholar

[8] Ho K C, Chen C L, Liao Y C, et al. A 3.46 Gb/s (9141, 8224) LDPC-based ECC scheme and on-line channel estimation for solid-state drive applications. In: Proceedings of IEEE International Symposiuim on Circuits and Systems, Lisbon, 2015. 1450--1453. Google Scholar

[9] Dong G Q, Xie N D, Zhang T. On the use of soft-decision error-correction codes in NAND flash memory. IEEE Trans Circ Syst I, 2011, 58: 429-439 CrossRef Google Scholar

[10] Kim J, Lee D, Sung W. Performance of rate 0.96 (68254, 65536) EG-LDPC code for NAND flash memory error correction. In: Proceedings of IEEE International Conference on Communications, Ottawa, 2012. 7029--7033. Google Scholar

[11] Cui Z Q, Wang Z F, Huang X M. Multilevel error correction scheme for MLC flash memory. In: Proceedings of IEEE International Symposium on Circuits and Systems, Melbourne, 2014. 201--204. Google Scholar

[12] Chen B N, Zhang X M, Wang Z F. Error correction for multi-level NAND flash memory using Reed-Solomon codes. In: Proceedings of IEEE Workshop on Signal Processing Systems, Washington, 2008. 94--99. Google Scholar

[13] Xu Q Y, Pan Z W, Liu N. A complexity-reduced fast successive cancellation list decoder for polar codes. Sci China Inf Sci, 2018, 61: 022309 CrossRef Google Scholar

[14] Chen Z, Yin L G, Pei Y K. CodeHop: physical layer error correction and encryption with LDPC-based code hopping. Sci China Inf Sci, 2016, 59: 102309 CrossRef Google Scholar

[15] Zhang C, Parhi K K. A network-efficient nonbinary QC-LDPC decoder architecture. IEEE Trans Circ Syst I, 2012, 59: 1359-1371 CrossRef Google Scholar

[16] Zhang C, Wang Z F, Sha J. Flexible LDPC decoder design for multigigabit-per-second applications. IEEE Trans Circ Syst I, 2010, 57: 116-124 CrossRef Google Scholar

[17] Arikan E. Channel polarization: a method for constructing capacity-achieving codes for symmetric binary-input memoryless channels. IEEE Trans Inf Theory, 2009, 55: 3051-3073 CrossRef Google Scholar

[18] Zhang C, Yuan B, Parhi K K. Reduced-latency sc polar decoder architectures. In: Proceedings of IEEE International Conference on Communications, Ottawa, 2012. 3471--3475. Google Scholar

[19] Zhang C, Parhi K K. Low-latency sequential and overlapped architectures for successive cancellation polar decoder. IEEE Trans Signal Process, 2013, 61: 2429-2441 CrossRef ADS Google Scholar

[20] Zhang C, Parhi K K. Latency analysis and architecture design of simplified SC polar decoders. IEEE Trans Circ Syst II, 2014, 61: 115-119 CrossRef Google Scholar

[21] Zhang C, You X, Sha J. Hardware architecture for list successive cancellation polar decoder. In: Proceedings of IEEE International Symposium on Circuits and Systems, Melbourne, 2014. 209--212. Google Scholar

[22] Zhang C, Yang J, You X, et al. Pipelined implementations of polar encoder and feed-back part for SC polar decoder. In: Proceedings of IEEE International Symposiuim on Circuits and Systems, Lisbon, 2015. 3032--3035. Google Scholar

[23] AccelerComm. BLER performance of list decoding for enhanced turbo codes. 3GPP TSG RAN WG1 Meeting #87, 2016. https://eprints.soton.ac.uk/404002/1/R1-1612308.pdf. Google Scholar

[24] Li Y, Alhussien H, Haratsch E, et al. A study of polar codes for MLC NAND flash memories. In: Proceedings of International Conference on Computing, Networking and Communications, Garden Grove, 2015. 608--612. Google Scholar

[25] Atwood G, Fazio A, Mills D, et al. Intel strataflash memory technology overview. Intel Technol J, 1997, 4: 1--8. Google Scholar

[26] Cai Y, Haratsch E F, Mutlu O, et al. Error patterns in MLC NAND flash memory: measurement, characterization, and analysis. In: Proceedings of the Conference on Design, Automation and Test in Europe, Dresden, 2012. 521--526. Google Scholar

[27] Leroux C, Tal I, Vardy A, et al. Hardware architectures for successive cancellation decoding of polar codes. In: Proceedings of IEEE International Conference on Acoustics, Speech and Signal Processing, Czech, 2011. 1665--1668. Google Scholar

[28] Song H C, Zhang C, Zhang S Q, et al. Polar code-based error correction code scheme for NAND flash memory applications. In: Proceedings of International Conference on Wireless Communications and Signal Processing, Yangzhou, 2016łinebreakvspace*-3.5 mm. Google Scholar

[29] Wang J D, Courtade T, Shankar H, et al. Soft information for LDPC decoding in flash: mutual-information optimized quantization. In: Proceedings of IEEE Global Telecommunications Conference, Kathmandu, 2011. Google Scholar

[30] Wang J D, Dong G Q, Zhang T, et al. Mutual-information optimized quantization for LDPC decoding of accurately modeled flash data. 2012,. arXiv Google Scholar

[31] Mielke N, Marquart T, Wu N, et al. Bit error rate in NAND flash memories. In: Proceedings of IEEE International Reliability Physics Symposium, Phoenix, 2008. 9--19. Google Scholar

[32] Takeuchi K. Novel co-design of NAND flash memory and NAND flash controller circuits for sub-30 nm low-power high-speed solid-state drives (SSD). IEEE J Solid-State Circ, 2009, 44: 1227-1234 CrossRef ADS Google Scholar

[33] Blankenship Y, Kuffner S. LDPC decoding for 802.22 standard. IEEE P802.22, 2007. Google Scholar