Каскадное кодирование для многоуровневой флэш-памяти с исправлением ошибок малой кратности во внешней ступени
Ключевые слова:
каскадный код, решетки Барнса-Уолла, код Рида-Соломона, многоуровневая flash память, вероятность ошибки декодирования, сложность декодирования.Аннотация
Один из эффективных подходов к организации помехоустойчивого кодирования в многоуровневой флэш-памяти связан с использованием каскадных конструкций на основе многомерных целочисленных решеток, используемых для построения внутреннего кода. Характерной особенностью таких каскадных конструкций является доминирование доли сложности внешнего декодера в общей сложности каскадного декодера. Учитывая, что в практических приложениях сложность декодирования, как правило, ключевое ограничение, определяющее возможность использования помехоустойчивого кодирования для многоуровневой флэш-памяти, каскадные конструкции со сравнительно малой сложностью внешнего декодера могут оказаться привлекательным решением в рамках обменного соотношения «плотность записи — сложность декодирования». Рассмотрена каскадная схема кодирования для многоуровневой флэш-памяти, в которой в качестве внутренней ступени используются коды на основе решеток Барнса — Уолла, а в качестве внешней ступени используется код Рида — Соломона с исправлением малого числа ошибок — не более 4…5.
Анализ помехоустойчивости предложенной каскадной схемы выполнен применительно к модели, отражающей основные физические особенности ячейки флэш-памяти с неравномерно расположенными целевыми уровнями напряжения в ячейке и дисперсией шума, зависящей от записанного значения (input-dependent additive Gaussian noise, ID-AGN). Для этой модели в работе развита модификация ранее предложенного авторами подхода к оценке вероятности ошибки декодирования внутреннего кода, основанная на использовании параллельной структуры кодовой решетки внутреннего кода, что позволяет существенно понизить сложность вычислений и ускорить получение окончательного результата. Приведены численные результаты, иллюстрирующие степень снижения достижимой плотности записи при введении ограничения на число исправляемых кодом Рида — Соломона ошибок — не более 4 — для широкого диапазона значений времени хранения данных и числа циклов перезаписи.
Литература
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. Таубин Ф.А., Трофимов А.Н. Каскадное кодирование на основе многомерных решеток и кодов Рида-Соломона для многоуровневой флэш-памяти // Труды СПИИРАН. 2018. Вып. 2(57). С. 75–103.
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. Кларк Дж., Кейн Дж. Кодирование с исправлением ошибок в системах цифровой связи // М.: Радио и связь. 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. Трофимов А.Н., Таубин Ф.А. Теоретико-информационный анализ многоуровневой flash-памяти. Часть 1. Модель канала и границы случайного кодирования. // Информационно-управляющие системы. 2016. Т. 81. № 2. С. 49–59.
Опубликован
Как цитировать
Раздел
Copyright (c) 2019 Андрей Николаевич Трофимов
Это произведение доступно по лицензии Creative Commons «Attribution» («Атрибуция») 4.0 Всемирная.
Авторы, которые публикуются в данном журнале, соглашаются со следующими условиями: Авторы сохраняют за собой авторские права на работу и передают журналу право первой публикации вместе с работой, одновременно лицензируя ее на условиях Creative Commons Attribution License, которая позволяет другим распространять данную работу с обязательным указанием авторства данной работы и ссылкой на оригинальную публикацию в этом журнале. Авторы сохраняют право заключать отдельные, дополнительные контрактные соглашения на неэксклюзивное распространение версии работы, опубликованной этим журналом (например, разместить ее в университетском хранилище или опубликовать ее в книге), со ссылкой на оригинальную публикацию в этом журнале. Авторам разрешается размещать их работу в сети Интернет (например, в университетском хранилище или на их персональном веб-сайте) до и во время процесса рассмотрения ее данным журналом, так как это может привести к продуктивному обсуждению, а также к большему количеству ссылок на данную опубликованную работу (Смотри The Effect of Open Access).