Concatenated Coding for Multilevel Flash Memory with Low Error Correction Capabilities in Outer Stage
Keywords:
Concatenated Code, Barnes-Wall Lattices, Reed-Solomon Code, Multilevel Flash Memory, Decoding Error Probability, Decoding ComplexityAbstract
One of the approaches to organization of error correcting coding for multilevel flash memory is based on concatenated construction, in particular, on multidimensional lattices for inner coding. A characteristic feature of such structures is the dominance of the complexity of the outer decoder in the total decoder complexity. Therefore the concatenated construction with low-complexity outer decoder may be attractive since in practical applications the decoder complexity is the crucial limitation for the usage of the error correction coding.
We consider a concatenated coding scheme for multilevel flash memory with the Barnes-Wall lattice based codes as an inner code and the Reed-Solomon code with correction up to 4…5 errors as an outer one.
Performance analysis is fulfilled for a model characterizing the basic physical features of a flash memory cell with non-uniform target voltage levels and noise variance dependent on the recorded value (input-dependent additive Gaussian noise, ID-AGN). For this model we develop a modification of our approach for evaluation the error probability for the inner code. This modification uses the parallel structure of the inner code trellis which significantly reduces the computational complexity of the performance estimation. We present numerical examples of achievable recording density for the Reed-Solomon codes with correction up to four errors as the outer code for wide range of the retention time and number of write/read cycles.
References
1. Micheloni R., Marelli A., Ravasio R. Error Correction Codes for Non-Volatile Memories. Springer Science & Business Media. 2008. 338 p.
2. Choi H., Liu W., Sung W. VLSI implementation of BCH error correction for multilevel cell NAND flash memory. IEEE Transactions on Very Large Scale Integration (VLSI) Systems. 2010. vol. 18. no. 5. pp. 843–847.
3. Freudenberger J., Spinner J. A configurable Bose-Chaudhuri-Hocquenghem codec architecture for flash controller applications. Journal of Circuits Systems and Computers. 2014. vol. 23. no. 02. pp. 1450019.
4. Cho S., Kim D., Choi J., Ha J. Block-wise concatenated BCH codes for NAND flash memories. IEEE Transactions on Communications. 2014. vol. 62. no. 4. pp. 1164–1177.
5. Marelli A., Micheloni R. BCH and LDPC Error Correction Codes for NAND Flash Memories. 3D Flash Memories. 2016. pp. 281–320.
6. Sun F., Rose K., Zhang T. On the Use of Strong BCH Codes for Improving Multilevel NAND Flash Memory Storage Capacity. IEEE Workshop on Signal Processing Systems (SiPS): Design and Implementation. 2006. 5 p.
7. Haratsch E.F. LDPC Code Concepts and Performance on High-Density Flash Memory. Proceedings of Flash Memory Summit. 2014. vol. 5. no. 5.2. pp. 5.5.
8. Haymaker K., Kelley C.A. Structured bit-interleaved LDPC codes for MLC flash memory. IEEE Journal on Selected Areas in Communications. 2014. vol. 32. no. 5. pp. 870–879.
9. Lin X. et al. Joint non-uniform detection and low-complexity decoding for multi-level cell NAND flash memory. 2016 IEEE International Conference on Consumer Electronics-China (ICCE-China). 2016. pp. 1–6.
10. Oh J., Ha J., Moon J., Ungerboeck G. RS-enhanced TCM for multilevel flash memories. IEEE Transactions on Communications. 2013. vol. 61. no. 5. pp. 1674–1683.
11. Kurkoski B.M. Coded modulation using lattices and Reed-Solomon codes, with applications to flash memories. IEEE Transactions on Selected Areas in Communications. 2014. vol. 32. no. 5. pp. 900–908.
12. Spinner J., Rajab M., Freudenberger J. Construction of high-rate generalized concatenated codes for applications in non-volatile flash memories. 2016 IEEE 8th International Memory Workshop (IMW). 2016. pp. 1–4.
13. Spinner J., Freudenberger J., Shavgulidze S. A Soft Input Decoding Algorithm for Generalized Concatenated Codes. IEEE Transactions on Communications. 2016. vol. 64. no. 9. pp. 3585–3595.
14. Taubin F.A.,Trofimov A.N. [Concatenated Reed–Solomon/lattice coding for multilevel flash memory]. Trudy SPIIRAN – SPIIRAS Proceedings. 2018. vol. 2(57). pp. 75–103. (In Russ.).
15. Chatzigeorgiou I., Demosthenous A., Rodrigues M.R., Wassell I.J. Performance-complexity tradeoff of convolutional codes for broadband fixed wireless access systems. IET Communications. 2010. vol. 4. no. 4. pp. 419–427.
16. Lee H. A high-speed low-complexity Reed-Solomon decoder for optical communications. IEEE Transactions on Circuits and Systems II: Express Briefs. 2005. vol. 52. no. 8. pp. 461–465.
17. Yang C., Emre Y., Chakrabarti C. Product code schemes for error correction in MLC NAND flash memories. IEEE Transactions on Very Large Scale Integration (VLSI) Systems. 2012. vol. 20. no. 12. pp. 2302–2314.
18. Samanta J. et al. RS (255, 249). Codec Based on All Primitive Polynomials Over GF(28). Proceedings of International Conference on Communication, Devices, and Computing (ICCDC). 2017. pp. 69–81.
19. Forney G.D. Coset Codes. I. Introduction and Geometrical Classification. IEEE Transactions on Information Theory. 1988. vol. 34. no. 5. pp. 1152–1187.
20. Taranalli V., Uchikawa H., Siegel P.H. Channel models for multilevel cell flash memories based on empirical error analysis. IEEE Transactions on Communications. 2016. vol. 64. no. 8. pp. 3169–3181.
21. Yassine H., Coon J., Ismail M., Fletcher H. Towards an analytical model of NAND flash memory and the impact on channel decoding. 2016 IEEE International Conference on Communications (ICC). 2016. pp. 1–6.
22. Korkotsides S., Bikas G., Eftaxiadis E., Antonakopoulos T. BER analysis of MLC NAND Flash memories based on an asymmetric PAM model. 2014 6th International Symposium on Communications, Control and Signal Processing. 2014. pp. 558–561.
23. Lin S., Kasami T., Fujiwara T., Fossorier M. Trellises and Trellis-Based Decoding Algorithms for Linear Block Codes. Kluwer Academic Publishers.1998. 288 p.
24. Vardy A. Trellis structure of codes. Handbook of Coding Theory. 1998. vol. 2. pp. 1985–2117.
25. Calderbank A.R. The Art of Signaling: Fifty Years of Coding Theory. IEEE Transactions on Information Theory. 1998. vol. 44. no 6. pp. 2561–2595.
26. Clark Jr. G.C., Cain J.B. Error-Correcting Coding for Digital Communications. Plenum Press. 1982. 432 p. (Russ. ed.: Klark Dzh., Kejn Dzh. Kodirovanie s ispravleniem oshibok v sistemah cifrovoj svyazi. M.: Radio i svyaz'. 1987).
27. Tomlinson M. et al. Error-Correction Coding and Decoding. Springer. 2017. 522 p.
28. Bentoutou Y. Performance Comparison of Real Time EDAC Systems for Applications On-Board Small Satellites. International Journal of Computer, Electrical, Automation, Control and Information Engineering. 2011. vol. 5. no. 5. pp. 466–469.
29. Trofimov A.N., Taubin F.A. [Information theory analysis of multilevel flash memory. Part 1: Channel model and random coding bounds]. Informacionno-upravljajushhie sistemy – Information and control systems. 2016. Issue 81. no. 2. pp. 49–59. (In Russ.).
2. Choi H., Liu W., Sung W. VLSI implementation of BCH error correction for multilevel cell NAND flash memory. IEEE Transactions on Very Large Scale Integration (VLSI) Systems. 2010. vol. 18. no. 5. pp. 843–847.
3. Freudenberger J., Spinner J. A configurable Bose-Chaudhuri-Hocquenghem codec architecture for flash controller applications. Journal of Circuits Systems and Computers. 2014. vol. 23. no. 02. pp. 1450019.
4. Cho S., Kim D., Choi J., Ha J. Block-wise concatenated BCH codes for NAND flash memories. IEEE Transactions on Communications. 2014. vol. 62. no. 4. pp. 1164–1177.
5. Marelli A., Micheloni R. BCH and LDPC Error Correction Codes for NAND Flash Memories. 3D Flash Memories. 2016. pp. 281–320.
6. Sun F., Rose K., Zhang T. On the Use of Strong BCH Codes for Improving Multilevel NAND Flash Memory Storage Capacity. IEEE Workshop on Signal Processing Systems (SiPS): Design and Implementation. 2006. 5 p.
7. Haratsch E.F. LDPC Code Concepts and Performance on High-Density Flash Memory. Proceedings of Flash Memory Summit. 2014. vol. 5. no. 5.2. pp. 5.5.
8. Haymaker K., Kelley C.A. Structured bit-interleaved LDPC codes for MLC flash memory. IEEE Journal on Selected Areas in Communications. 2014. vol. 32. no. 5. pp. 870–879.
9. Lin X. et al. Joint non-uniform detection and low-complexity decoding for multi-level cell NAND flash memory. 2016 IEEE International Conference on Consumer Electronics-China (ICCE-China). 2016. pp. 1–6.
10. Oh J., Ha J., Moon J., Ungerboeck G. RS-enhanced TCM for multilevel flash memories. IEEE Transactions on Communications. 2013. vol. 61. no. 5. pp. 1674–1683.
11. Kurkoski B.M. Coded modulation using lattices and Reed-Solomon codes, with applications to flash memories. IEEE Transactions on Selected Areas in Communications. 2014. vol. 32. no. 5. pp. 900–908.
12. Spinner J., Rajab M., Freudenberger J. Construction of high-rate generalized concatenated codes for applications in non-volatile flash memories. 2016 IEEE 8th International Memory Workshop (IMW). 2016. pp. 1–4.
13. Spinner J., Freudenberger J., Shavgulidze S. A Soft Input Decoding Algorithm for Generalized Concatenated Codes. IEEE Transactions on Communications. 2016. vol. 64. no. 9. pp. 3585–3595.
14. Taubin F.A.,Trofimov A.N. [Concatenated Reed–Solomon/lattice coding for multilevel flash memory]. Trudy SPIIRAN – SPIIRAS Proceedings. 2018. vol. 2(57). pp. 75–103. (In Russ.).
15. Chatzigeorgiou I., Demosthenous A., Rodrigues M.R., Wassell I.J. Performance-complexity tradeoff of convolutional codes for broadband fixed wireless access systems. IET Communications. 2010. vol. 4. no. 4. pp. 419–427.
16. Lee H. A high-speed low-complexity Reed-Solomon decoder for optical communications. IEEE Transactions on Circuits and Systems II: Express Briefs. 2005. vol. 52. no. 8. pp. 461–465.
17. Yang C., Emre Y., Chakrabarti C. Product code schemes for error correction in MLC NAND flash memories. IEEE Transactions on Very Large Scale Integration (VLSI) Systems. 2012. vol. 20. no. 12. pp. 2302–2314.
18. Samanta J. et al. RS (255, 249). Codec Based on All Primitive Polynomials Over GF(28). Proceedings of International Conference on Communication, Devices, and Computing (ICCDC). 2017. pp. 69–81.
19. Forney G.D. Coset Codes. I. Introduction and Geometrical Classification. IEEE Transactions on Information Theory. 1988. vol. 34. no. 5. pp. 1152–1187.
20. Taranalli V., Uchikawa H., Siegel P.H. Channel models for multilevel cell flash memories based on empirical error analysis. IEEE Transactions on Communications. 2016. vol. 64. no. 8. pp. 3169–3181.
21. Yassine H., Coon J., Ismail M., Fletcher H. Towards an analytical model of NAND flash memory and the impact on channel decoding. 2016 IEEE International Conference on Communications (ICC). 2016. pp. 1–6.
22. Korkotsides S., Bikas G., Eftaxiadis E., Antonakopoulos T. BER analysis of MLC NAND Flash memories based on an asymmetric PAM model. 2014 6th International Symposium on Communications, Control and Signal Processing. 2014. pp. 558–561.
23. Lin S., Kasami T., Fujiwara T., Fossorier M. Trellises and Trellis-Based Decoding Algorithms for Linear Block Codes. Kluwer Academic Publishers.1998. 288 p.
24. Vardy A. Trellis structure of codes. Handbook of Coding Theory. 1998. vol. 2. pp. 1985–2117.
25. Calderbank A.R. The Art of Signaling: Fifty Years of Coding Theory. IEEE Transactions on Information Theory. 1998. vol. 44. no 6. pp. 2561–2595.
26. Clark Jr. G.C., Cain J.B. Error-Correcting Coding for Digital Communications. Plenum Press. 1982. 432 p. (Russ. ed.: Klark Dzh., Kejn Dzh. Kodirovanie s ispravleniem oshibok v sistemah cifrovoj svyazi. M.: Radio i svyaz'. 1987).
27. Tomlinson M. et al. Error-Correction Coding and Decoding. Springer. 2017. 522 p.
28. Bentoutou Y. Performance Comparison of Real Time EDAC Systems for Applications On-Board Small Satellites. International Journal of Computer, Electrical, Automation, Control and Information Engineering. 2011. vol. 5. no. 5. pp. 466–469.
29. Trofimov A.N., Taubin F.A. [Information theory analysis of multilevel flash memory. Part 1: Channel model and random coding bounds]. Informacionno-upravljajushhie sistemy – Information and control systems. 2016. Issue 81. no. 2. pp. 49–59. (In Russ.).
Published
2019-10-01
How to Cite
Taubin, F., & Trofimov, A. (2019). Concatenated Coding for Multilevel Flash Memory with Low Error Correction Capabilities in Outer Stage. SPIIRAS Proceedings, 18(5), 1149-1181. https://doi.org/10.15622/sp.2019.18.5.1149-1181
Section
Information Security
Copyright (c) 2019 Андрей Николаевич Трофимов
This work is licensed under a Creative Commons Attribution 4.0 International License.
Authors who publish with this journal agree to the following terms: Authors retain copyright and grant the journal right of first publication with the work simultaneously licensed under a Creative Commons Attribution License that allows others to share the work with an acknowledgement of the work's authorship and initial publication in this journal. Authors are able to enter into separate, additional contractual arrangements for the non-exclusive distribution of the journal's published version of the work (e.g., post it to an institutional repository or publish it in a book), with an acknowledgement of its initial publication in this journal. Authors are permitted and encouraged to post their work online (e.g., in institutional repositories or on their website) prior to and during the submission process, as it can lead to productive exchanges, as well as earlier and greater citation of published work (See The Effect of Open Access).