Bilayer LDPC Codes Combined with Perturbed Decoding for MLC NAND Flash Memory
<p>A Tanner graph for a bilayer LDPC code.</p> "> Figure 2
<p>Schematic diagram of perturbation decoding.</p> "> Figure 3
<p>Schematic diagram of the bilayer LDPC encoding process in an MLC NAND flash channel.</p> "> Figure 4
<p>A flow chart of the bilayer LDPC decoding process in an MLC NAND flash channel.</p> "> Figure 5
<p>Block diagram of the perturbed decoding algorithm for a bilayer LDPC code.</p> "> Figure 6
<p>The BER performances of the proposed bilayer LDPC codes with different extra parity-check bits over different P/E cycles (where <math display="inline"><semantics> <mrow> <mi>N</mi> <mo>=</mo> <mn>1404</mn> </mrow> </semantics></math> and <math display="inline"><semantics> <mrow> <mi>R</mi> <mo>=</mo> <mn>0.75</mn> </mrow> </semantics></math>).</p> "> Figure 7
<p>The FER performances of the proposed bilayer LDPC codes with different extra parity-check bits over different P/E cycles (<math display="inline"><semantics> <mrow> <mi>N</mi> <mo>=</mo> <mn>1404</mn> </mrow> </semantics></math> and <math display="inline"><semantics> <mrow> <mi>R</mi> <mo>=</mo> <mn>0.75</mn> </mrow> </semantics></math>).</p> "> Figure 8
<p>The average number of iterations of the proposed bilayer LDPC codes with different extra parity-check bits over different P/E cycles (<math display="inline"><semantics> <mrow> <mi>N</mi> <mo>=</mo> <mn>1404</mn> </mrow> </semantics></math> and <math display="inline"><semantics> <mrow> <mi>R</mi> <mo>=</mo> <mn>0.75</mn> </mrow> </semantics></math>).</p> "> Figure 9
<p>The BER performances of the proposed bilayer LDPC codes with different extra parity-check bits over different P/E cycles (<math display="inline"><semantics> <mrow> <mi>N</mi> <mo>=</mo> <mn>1404</mn> </mrow> </semantics></math> and <math display="inline"><semantics> <mrow> <mi>R</mi> <mo>=</mo> <mn>0.83</mn> </mrow> </semantics></math>).</p> "> Figure 10
<p>The FER performances of the proposed bilayer LDPC codes with different extra parity-check bits over different P/E cycles (<math display="inline"><semantics> <mrow> <mi>N</mi> <mo>=</mo> <mn>1404</mn> </mrow> </semantics></math> and <math display="inline"><semantics> <mrow> <mi>R</mi> <mo>=</mo> <mn>0.83</mn> </mrow> </semantics></math>).</p> "> Figure 11
<p>The average number of iterations of the proposed bilayer LDPC codes with different extra parity-check bits over different P/E cycles (<math display="inline"><semantics> <mrow> <mi>N</mi> <mo>=</mo> <mn>1404</mn> </mrow> </semantics></math> and <math display="inline"><semantics> <mrow> <mi>R</mi> <mo>=</mo> <mn>0.83</mn> </mrow> </semantics></math>).</p> "> Figure 12
<p>The BER performances of the proposed bilayer LDPC codes with perturbed decoding algorithm over different P/E cycles (<math display="inline"><semantics> <mrow> <mi>N</mi> <mo>=</mo> <mn>1404</mn> </mrow> </semantics></math> and <math display="inline"><semantics> <mrow> <mi>R</mi> <mo>=</mo> <mn>0.75</mn> </mrow> </semantics></math>).</p> "> Figure 13
<p>The FER performances of the proposed bilayer LDPC codes with perturbed decoding algorithm over different P/E cycles (<math display="inline"><semantics> <mrow> <mi>N</mi> <mo>=</mo> <mn>1404</mn> </mrow> </semantics></math> and <math display="inline"><semantics> <mrow> <mi>R</mi> <mo>=</mo> <mn>0.75</mn> </mrow> </semantics></math>).</p> "> Figure 14
<p>The average number of iterations of the proposed bilayer LDPC codes with a perturbed decoding algorithm over different P/E cycles (<math display="inline"><semantics> <mrow> <mi>N</mi> <mo>=</mo> <mn>1404</mn> </mrow> </semantics></math> and <math display="inline"><semantics> <mrow> <mi>R</mi> <mo>=</mo> <mn>0.75</mn> </mrow> </semantics></math>).</p> ">
Abstract
:1. Introduction
- A coding scheme based on bilayer LDPC codes is designed for an MLC NAND flash memory channel, which stores the extra parity-check bits in the lower pages with relatively good channel conditions. To the best of our knowledge, this is the first bilayer LDPC coding scheme that has been successfully designed for an MLC flash channel. The bilayer LDPC decoding algorithm is activated only when the decoding of the upper layer fails. Hence, the decoding complexity increases only slightly at low P/E cycle regions.
- To further improve the decoding performance, the GA is applied to the proposed bilayer LDPC coding scheme, which produces the genetic noises that rapidly draw the received sequences back to their error-correctable decoding space. The reliability of the storage system is improved as a consequence.
2. Related Works
2.1. Bilayer LDPC Codes
2.2. Perturbation Theory
3. Bilayer LDPC Codes Applied with a Perturbed Decoding Algorithm
3.1. Bilayer LDPC Code Design for an MLC Flash Channel
- Upper Page Encoding: The upper page information sequence is encoded using the matrix to obtain the parity-check vector of length of the upper page from Equation (3).
- Generation of the Extra Parity-Check Bits: Specifically, the upper page information bits and the corresponding parity-check bits generated in Step 1 are jointly encoded using the matrix to obtain the extra parity-check bits of length , which are stored on the lower page.
- Lower Page Encoding: Jointly encode the lower page information sequence and the extra parity-check bits of length from the upper page to generate the lower page parity-check bits via a separate channel coding scheme (which is not within the scope of this paper).
- MLC Programming: The corresponding lower and upper bits are converted into voltages through an iterative incremental pulse programming method. The details of the bilayer LDPC encoding processes are shown in Figure 3.
- Read Operation: The voltage in the MLC flash memory is quantified using the soft sensing method. We used the soft-decision storage sensing approach, in which more than one quantization level is used between two adjacent storage states. Thus, the soft information of the code word corresponding to the threshold voltage of each memory cell is obtained.
- Lower Page Decoding: The lower page information bits and the extra parity-check bits of length are estimated. The information on the extra parity-check bits is stored for use in the bilayer LDPC decoding.
- Upper Page Decoding: The upper page is decoded using the matrix . If the decoding is successful, the decoding result is output and the decoding process is finished; otherwise, the information on the extra parity-check bits is read from the lower page and the bilayer decoding is carried out in the next step.
- Bilayer Decoding: The bilayer decoding is performed until the decoding is successful or re-decoded with high-precision quantization.
3.2. GA-Based Perturbed Decoding Algorithm
- Initialization: In the initialization process, a group of noises with Gaussian distribution is randomly generated by the noise generator as the initialization population. Compared with the channel noise, the artificially added perturbation noise power can be neglected. Genetic noise with a standard deviation between 0 and 0.385 is usually used. It should be noted that the length of the perturbed noise sequence is the same as that of the received sequence, which conforms to the coded form of the population. Hence, no additional coding operation is required for the population.
- Crossover and mutation: By generating new individuals, the crossover and mutation operations expand the scope of the solution space and increase the diversity of the individuals—which are provided in the form of the ‘crossover’ function and ’mutation’ function, respectively—in Algorithm 1. Suppose two parents have chromosomes represented by and , respectively, then—via crossover manipulation—the related children can be represented as
- Fitness assessment and selection: A fitness evaluation is the only basis for the GA to update the population. The population’s fitness value is calculated by the fitness function, and the next generation is reproduced based on the fitness probability. An individual i’s fitness score is computed by
Algorithm 1: Perturbed decoding algorithm. |
Input: // The received signal of the upper page // Parity-check matrix of the bilayer LDPC code M // Population size T // Maximum number of iterations // Genetic noise // Population // Crossover probability // Mutation probability // Extra parity-check bits from the lower page // Perturbed bits Output: // Estimated code word
|
4. Simulation Results
4.1. Results of the Bilayer LDPC codes
4.2. Perturbed Decoding Algorithm Results
5. Conclusions
Author Contributions
Funding
Institutional Review Board Statement
Data Availability Statement
Conflicts of Interest
References
- Cai, Y.; Ghose, S.; Haratsch, E.F.; Luo, Y.; Mutlu, O. Error characterization, mitigation, and recovery in flash-memory-based solid-state drives. Proc. IEEE 2017, 105, 1666–1704. [Google Scholar] [CrossRef]
- Aritome, S.; Shirota, R.; Hemink, G.; Endoh, T.; Masuoka, F. Reliability issues of flash memory cells. Proc. IEEE 1993, 81, 776–788. [Google Scholar] [CrossRef]
- Huang, M.; Liu, Z.; Qiao, L.; Wang, Y.; Shao, Z. An endurance-aware metadata allocation strategy for MLC NAND flash memory storage systems. IEEE Trans. Comput.-Aided Design Integr. Circuits Syst. 2016, 35, 691–694. [Google Scholar] [CrossRef]
- Aslam, C.A.; Guan, Y.L.; Cai, K. Read and write voltage signal optimization for multi-level-cell (MLC) NAND flash memory. IEEE Trans. Commun. 2016, 64, 1613–1623. [Google Scholar] [CrossRef]
- Yu, X.; He, J.; Li, Q.; Zhang, B.; Wang, X.; Wang, Q.; Huo, Z. DMMC: A polar code construction method for improving performance in TLC nand flash. IEEE Embed. Syst. Lett. 2023. early access. [Google Scholar] [CrossRef]
- Hareedy, A.; Lanka, C.; Dolecek, L. A general non-binary LDPC code optimization framework suitable for dense flash memory and magnetic storage. IEEE J. Sel. Areas Commun. 2016, 34, 2402–2415. [Google Scholar] [CrossRef]
- Vakilinia, K.; Divsalar, D.; Wesel, R.D. Optimized degree distributions for binary and non-binary LDPC codes in flash memory. In Proceedings of the 2014 International Symposium on Information Theory and Its Applications, Melbourne, Australia, 26–29 October 2014; pp. 6–10. [Google Scholar]
- Kabatiansky, G.; Kruglik, S. On codes correcting constant number of errors in l1 metric. In Proceedings of the Information Technology and Systems (ITaS), Sochi, Russia, 7–11 September 2015; pp. 152–157. [Google Scholar]
- Jiang, A.; Li, H.; Wang, Y. Error scrubbing codes for flash memories. In Proceedings of the 11th Canadian Workshop on Information Theory, Ottawa, ON, Canada, 13–15 May 2009; pp. 32–35. [Google Scholar]
- Sun, H.; Zhao, W.; Lv, M.; Dong, G.; Zheng, N.; Zhang, T. Exploiting intra-cell bit error characteristics to improve min-sum LDPC decoding for MLC NAND Flash based storage in mobile device. IEEE Trans. Very Large Scale Int. Sys. 2016, 24, 2654–2664. [Google Scholar] [CrossRef]
- Hu, Y.; Song, S.; Xiao, S.; Xu, Q.; Xiao, N.; Qin, Z. A dominating error region strategy for improving the bit-flipping LDPC decoder of SSDs. IEEE Trans. Circ. Sys. II Express Briefs 2015, 62, 578–582. [Google Scholar] [CrossRef]
- Kong, L.; Liu, Y.; Liu, H.; Zhao, S. Protograph QC-LDPC and rate-adaptive polar codes design for MLC NAND flash memories. IEEE Access 2019, 7, 37131–37140. [Google Scholar] [CrossRef]
- Kay, S. Can detectability be improved by adding noise? IEEE Signal Process. Lett. 2000, 7, 8–10. [Google Scholar] [CrossRef]
- Sutera, A. Stochastic perturbation of a pure connective motion. J. Atmos. Sci. 2010, 37, 245–249. [Google Scholar] [CrossRef]
- Xiao, D.; Gu, Z. Dynamic perturbation decoding of polar-CRC cascaded code. In Proceedings of the IEEE International Wireless Communications, and Mobile Computing, Limassol, Cyprus, 5–19 June 2020; pp. 42–45. [Google Scholar]
- Lee, H.; Kil, Y.S.; Jang, M.; Kim, S.H.; Park, O.S.; Park, G. Multi-round belief propagation decoding with impulsive perturbation for short LDPC codes. IEEE Wirel. Commun. Lett. 2020, 9, 1491–1494. [Google Scholar] [CrossRef]
- Arli, A.; Gazi, O. Noise-aided belief propagation list decoding of polar codes. IEEE Commun. Lett. 2019, 23, 1285–1288. [Google Scholar] [CrossRef]
- Gerrar, N.K.; Zhao, S.; Kong, L. A CRC-aided perturbed decoding of polar codes. In Proceedings of the 14th International Conference on Wireless Communications, Networking and Mobile Computing (WiCOM 2018), Chongqing, China, 18–20 September 2018. [Google Scholar]
- Kong, L.; Liu, H.; Hou, W.; Dai, B. Improving decodability of polar Codes by adding noise. Symmetry 2022, 14, 1156. [Google Scholar] [CrossRef]
- Kong, L.; Kim, K.J.; Kwak, K.S. Design of bilayer QC-LDPC codes for decode-and forward based cooperative relaying communication. In Proceedings of the IEEE International Conference on Communications (ICC), Ottawa, ON, Canada, 10–15 June 2012; pp. 4717–4721. [Google Scholar]
- Ram, E.; Cassuto, Y. Design of bilayer and multi-layer LDPC ensembles from Individual degree distributions. IEEE Trans. Inf. Theory 2021, 67, 7096–7109. [Google Scholar] [CrossRef]
- Fang, Y.; Bi, G.; Guan, Y.L.; Lau, F.C.M. A survey on protograph LDPC codes and their applications. IEEE Commun. Surv. Tuts. 2015, 17, 1989–2016. [Google Scholar] [CrossRef]
- Benzi, R.; Sutera, A.; Vulpiani, A. The mechanism of stochastic resonance. J. Phys. A Math. Gen. 1981, 14, L453–L457. [Google Scholar] [CrossRef]
- McDonnell, M.D.; Abbott, D. What is stochastic resonance? definitions, misconceptions, debates, and its relevance to biology. PLoS Comput. Biol. 2009, 5, e1000348. [Google Scholar] [CrossRef]
- Chen, H.; Varshney, P.K.; Michels, J.H.; Kay, S. Approaching near optimal detection performance via stochastic resonance. In Proceedings of the IEEE International Conference on Acoustics Speech and Signal Processing Proceedings (ICASSP), Toulouse, France, 14–19 May 2006; p. III. [Google Scholar]
- Shih, K.; Shiu, D. Perturbed decoding algorithm for concatenated error correcting and detecting codes system. In Proceedings of the IEEE International Symposium on Personal, Indoor and Mobile Radio Communications (PIMRC), Helsinki, Finland, 11–14 September 2006; pp. 1–5. [Google Scholar]
- Wang, W.; Shiu, D. The theory behind perturbed decoding algorithm. In Proceedings of the IEEE International Symposium on Personal, Indoor and Mobile Radio Communications (PIMRC), Athens, Greece, 3–7 September 2007; pp. 1–5. [Google Scholar]
- Nishikawa, M.; Nakamura, Y.; Kanai, Y.; Osawa, H.; Okamoto, Y. A study on iterative decoding with LLR modulator by neural network using adjacent track information in SMR system. IEEE Trans. Magn. 2019, 55, 1–5. [Google Scholar] [CrossRef]
- Petrović, V.L.; Marković, M.M.; El Mezeni, D.M.; Saranovac, L.V.; Radošević, A. Flexible high throughput QC-LDPC decoder with perfect pipeline conflicts resolution and efficient hardware utilization. IEEE Trans. Circuits Syst. I Regul. Pap. 2020, 67, 5454–5467. [Google Scholar] [CrossRef]
- Wang, X.; Ma, Q.; Li, J.; Zhang, H.; Xu, W. An improved SC flip decoding algorithm of polar codes based on genetic algorithm. IEEE Access 2020, 8, 222572–222583. [Google Scholar] [CrossRef]
- Elkelesh, A.; Ebada, M.; Cammerer, S.; Brink, S.T. Decoder-tailored polar code design using the genetic algorithm. IEEE Trans. Commun. 2019, 67, 4521–4534. [Google Scholar] [CrossRef]
- Duffy, K.R.; An, W.; Médard, M. Ordered reliability bits guessing random additive noise decoding. IEEE Trans. Signal Process. 2022, 70, 4528–4542. [Google Scholar] [CrossRef]
Parameters | Values |
---|---|
Code word length N | 1404 |
Length of extra parity-check bits | 0/117/311 |
Code rate R | 0.75/0.83 |
Maximum number of BP iterations | 20 |
Disclaimer/Publisher’s Note: The statements, opinions and data contained in all publications are solely those of the individual author(s) and contributor(s) and not of MDPI and/or the editor(s). MDPI and/or the editor(s) disclaim responsibility for any injury to people or property resulting from any ideas, methods, instructions or products referred to in the content. |
© 2024 by the authors. Licensee MDPI, Basel, Switzerland. This article is an open access article distributed under the terms and conditions of the Creative Commons Attribution (CC BY) license (https://creativecommons.org/licenses/by/4.0/).
Share and Cite
Kong, L.; Liu, H.; Hou, W.; Meng, C. Bilayer LDPC Codes Combined with Perturbed Decoding for MLC NAND Flash Memory. Entropy 2024, 26, 54. https://doi.org/10.3390/e26010054
Kong L, Liu H, Hou W, Meng C. Bilayer LDPC Codes Combined with Perturbed Decoding for MLC NAND Flash Memory. Entropy. 2024; 26(1):54. https://doi.org/10.3390/e26010054
Chicago/Turabian StyleKong, Lingjun, Haiyang Liu, Wentao Hou, and Chao Meng. 2024. "Bilayer LDPC Codes Combined with Perturbed Decoding for MLC NAND Flash Memory" Entropy 26, no. 1: 54. https://doi.org/10.3390/e26010054
APA StyleKong, L., Liu, H., Hou, W., & Meng, C. (2024). Bilayer LDPC Codes Combined with Perturbed Decoding for MLC NAND Flash Memory. Entropy, 26(1), 54. https://doi.org/10.3390/e26010054