Advanced Search
Article Contents
Article Contents

Channel decomposition for multilevel codes over multilevel and partial erasure channels

• * Corresponding author: Carolyn Mayer.
• 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.

Mathematics Subject Classification: Primary: 94A40, 94B35; Secondary: 94A15.

 Citation:

• Figure 1.  $4$-ary partial erasure channel (QPEC) with $M=2$. Here, the binary representation of each $4$-ary symbol is shown.

Figure 2.  $4$-ary multilevel erasure channel with erasure probability $\varepsilon$ and bit error probability $\gamma$.

Figure 3.  $I(X;Y)$ as a function of $\varepsilon$, given a uniform input distribution.

Figure 4.  Subchannel for $X_1$ on $4$-ary multilevel erasure channel with parameters $\varepsilon,\gamma$.

Figure 5.  Subchannel for $X_2$ on $4$-ary multilevel erasure channel with parameters $\varepsilon,\gamma$.

Figure 6.  Subchannel for $X_1$ on 4-ary partial erasure channel (QPEC) with erasure probability $\varepsilon$.

Figure 7.  Subchannel for $X_2$ on 4-ary partial erasure channel (QPEC) with erasure probability $\varepsilon$.

•  K. A. S. Abdel-Ghaffar  and  M. Hassner , Multilevel error-control codes for data storage channels, IEEE Trans. Inf. Theory, 37 (1991) , 735-741. S. Borade , B. Nakiboğlu  and  L. Zheng , Unequal error protection: an information-theoretic perspective, IEEE Trans. Inf. Theory, 55 (2009) , 5511-5539. 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. A. R. Calderbank  and  N. Seshadri , Multilevel codes for unequal error protection, IEEE Trans. Inf. Theory, 39 (1993) , 1234-1248. R. Cohen  and  Y. Cassuto , Iterative decoding of LDPC codes over the $q$-ary partial erasure channel, IEEE Trans. Inf. Theory, 62 (2016) , 2658-2672. D. Declercq  and  M. Fossorier , Decoding algorithms for nonbinary LDPC codes over $\text{GF}(q)$, IEEE Trans. Commun., 55 (2007) , 633-643. R. Gabrys , E. Yaakobi  and  L. Dolecek , Graded bit-error-correcting codes with applications to flash memory, IEEE Trans. Inf. Theory, 59 (2013) , 2315-2327. 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. R. G. Gallager, Low Density Parity Check Codes, MIT Press, 1963. K. Haymaker  and  C. A. Kelley , Structured bit-interleaved LDPC codes for MLC flash memory, IEEE J. Sel. Areas Commun., 32 (2014) , 870-879. 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. H. Imai  and  S. Hirakawa , A new multilevel coding method using error-correcting codes, IEEE Trans. Inf. Theory, 23 (1977) , 371-377. M. Moser and P. Chen, A Student's Guide to Coding and Information Theory, Cambridge Univ. Press, Cambridge, 2012. T. Richardson , A. Shokrollahi  and  R. Urbanke , Design of capacity-approaching irregular low-density parity-check codes, IEEE Trans. Inf. Theory, 47 (2001) , 619-637. T. J. Richardson  and  R. L. Urbanke , The capacity of low-density parity-check codes under message passing decoding, IEEE Trans. Inf. Theory, 47 (2001) , 599-618. R. M. Tanner , A recursive approach to low complexity codes, IEEE Trans. Inf. Theory, 27 (1981) , 533-547. T. Tao and V. H. Vu, Additive Combinatorics, Cambridge Univ. Press, 2006. U. Wachsmann , R. F. H. Fischer  and  J. B. Huber , Multilevel codes: Theoretical concepts and practical design rules, IEEE Trans. Inf. Theory, 45 (1999) , 1361-1391. 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.

Figures(7)

Article Metrics

HTML views(523) PDF downloads(480) Cited by(0)

Other Articles By Authors

• on this site
• on Google Scholar

Catalog

/

DownLoad:  Full-Size Img  PowerPoint