Channel decomposition for multilevel codes over multilevel and partial erasure channels

Carolyn Mayer; Kathryn Haymaker; Christine A. Kelley

doi:10.3934/amc.2018010

Article Contents

2018, Volume 12, Issue 1: 151-168. Doi: 10.3934/amc.2018010

This issue Previous Article On the spectrum for the genera of maximal curves over small fields Next Article On

${{\mathbb{Z}}}_{p^r}{{\mathbb{Z}}}_{p^s}$

-additive cyclic codes

Channel decomposition for multilevel codes over multilevel and partial erasure channels

1.
Department of Mathematics, University of Nebraska-Lincoln, Lincoln, Nebraska 68588-0130, USA
2.
Department of Mathematics & Statistics, Villanova University, Villanova, PA 19085, USA

* Corresponding author: Carolyn Mayer.
* Corresponding author: Carolyn Mayer.

Received: October 2016

Published: February 2018

Abstract / Introduction Full Text(HTML) Figure(7) Related Papers Cited by

Abstract

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.

Keywords:

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

Citation:

Full Text(HTML)

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

Download: Full-size image PowerPoint slide

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

Download: Full-size image PowerPoint slide

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

Download: Full-size image PowerPoint slide

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

Download: Full-size image PowerPoint slide

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

Download: Full-size image PowerPoint slide

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

Download: Full-size image PowerPoint slide

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

Download: Full-size image PowerPoint slide

Related Papers

Cited by

References

	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.