×

Channel decomposition for multilevel codes over multilevel and partial erasure channels. (English) Zbl 1414.94897

Summary: We introduce the Multilevel Erasure Channel (MEC) for binary extension field alphabets. The channel model is motivated by applications such as non-volatile multilevel read storage channels. Like the recently proposed \(q\)-ary partial erasure channel (QPEC), the MEC is designed to capture partial erasures. The partial erasures addressed by the MEC are determined by erasures at the bit level of the \(q\)-ary symbol representation. In this paper we derive the channel capacity of the MECand give a multistage decoding scheme on the MEC using binary codes. We also present a low complexity multistage \(p\)-ary decoding strategy for codes on the QPEC when \(q = p^k\).We show that for appropriately chosen component codes, capacity on the MEC and QPEC may be achieved.

MSC:

94A40 Channel models (including quantum) in information and communication theory
94B35 Decoding
94A15 Information theory (general)
94B60 Other types of codes
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] K. A. S. Abdel-Ghaffar; M. Hassner, Multilevel error-control codes for data storage channels, IEEE Trans. Inf. Theory, 37, 735-741 (1991)
[2] S. Borade; B. Nakiboğlu; L. Zheng, Unequal error protection: an information-theoretic perspective, IEEE Trans. Inf. Theory, 55, 5511-5539 (2009) · Zbl 1367.94126
[3] Y. Cai, E. F. Haratsch, O. Mutlu and K. Mai, Error patterns in MLC NAND flash memory: Measurement, characterization and analysis in Des. Autom. Test Europ. Conf. Exhib. (DATE), 2012.
[4] A. R. Calderbank; N. Seshadri, Multilevel codes for unequal error protection, IEEE Trans. Inf. Theory, 39, 1234-1248 (1993) · Zbl 0801.94019
[5] R. Cohen; Y. Cassuto, Iterative decoding of LDPC codes over the \(\begin{document}q\end{document} \)-ary partial erasure channel, IEEE Trans. Inf. Theory, 62, 2658-2672 (2016) · Zbl 1359.94840
[6] D. Declercq; M. Fossorier, Decoding algorithms for nonbinary LDPC codes over \(\begin{document}\text{GF}(q)\end{document} \), IEEE Trans. Commun., 55, 633-643 (2007)
[7] R. Gabrys; E. Yaakobi; L. Dolecek, Graded bit-error-correcting codes with applications to flash memory, IEEE Trans. Inf. Theory, 59, 2315-2327 (2013) · Zbl 1364.94752
[8] R. Gabrys, E. Yaakobi, L. Grupp, S. Swanson and L. Dolecek, Tackling intracell variability in TLC flash through tensor product codes in Proc. IEEE Int. Symp. Inf. Theory, Cambridge, 2012.
[9] R. G. Gallager, Low Density Parity Check Codes, MIT Press, 1963. · Zbl 0107.11802
[10] K. Haymaker; C. A. Kelley, Structured bit-interleaved LDPC codes for MLC flash memory, IEEE J. Sel. Areas Commun., 32, 870-879 (2014)
[11] J. Huber, U. Wachsmann and R. Fischer, Coded modulation by multilevel-codes: Overview and state of the art in ITG-Fachberichte Conf. Rec., Aachen, 1998.
[12] H. Imai; S. Hirakawa, A new multilevel coding method using error-correcting codes, IEEE Trans. Inf. Theory, 23, 371-377 (1977) · Zbl 0352.94012
[13] M. Moser and P. Chen, A Student’s Guide to Coding and Information Theory, Cambridge Univ. Press, Cambridge, 2012. · Zbl 1245.94002
[14] T. Richardson; A. Shokrollahi; R. Urbanke, Design of capacity-approaching irregular low-density parity-check codes, IEEE Trans. Inf. Theory, 47, 619-637 (2001) · Zbl 1019.94034
[15] T. J. Richardson; R. L. Urbanke, The capacity of low-density parity-check codes under message passing decoding, IEEE Trans. Inf. Theory, 47, 599-618 (2001) · Zbl 1019.94033
[16] R. M. Tanner, A recursive approach to low complexity codes, IEEE Trans. Inf. Theory, 27, 533-547 (1981) · Zbl 0474.94029
[17] T. Tao and V. H. Vu, Additive Combinatorics, Cambridge Univ. Press, 2006. · Zbl 1127.11002
[18] U. Wachsmann; R. F. H. Fischer; J. B. Huber, Multilevel codes: Theoretical concepts and practical design rules, IEEE Trans. Inf. Theory, 45, 1361-1391 (1999) · Zbl 0960.94013
[19] Z. Zhang, W. Xiao, N. Park and D. J. Lilja, Memory module-level testing and error behaviors for phase change memory in IEEE 30th Int. Conf. Comp. Des. (ICCD), 2012.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.