# American Institute of Mathematical Sciences

February  2018, 12(1): 151-168. doi: 10.3934/amc.2018010

## 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.

Received  October 2016 Published  March 2018

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.

Citation: Carolyn Mayer, Kathryn Haymaker, Christine A. Kelley. Channel decomposition for multilevel codes over multilevel and partial erasure channels. Advances in Mathematics of Communications, 2018, 12 (1) : 151-168. doi: 10.3934/amc.2018010
##### References:
 [1] K. A. S. Abdel-Ghaffar and M. Hassner, Multilevel error-control codes for data storage channels, IEEE Trans. Inf. Theory, 37 (1991), 735-741. Google Scholar [2] S. Borade, B. Nakiboğlu and L. Zheng, Unequal error protection: an information-theoretic perspective, IEEE Trans. Inf. Theory, 55 (2009), 5511-5539. Google Scholar [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.Google Scholar [4] A. R. Calderbank and N. Seshadri, Multilevel codes for unequal error protection, IEEE Trans. Inf. Theory, 39 (1993), 1234-1248. Google Scholar [5] 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. Google Scholar [6] D. Declercq and M. Fossorier, Decoding algorithms for nonbinary LDPC codes over $\text{GF}(q)$, IEEE Trans. Commun., 55 (2007), 633-643. Google Scholar [7] 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. Google Scholar [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.Google Scholar [9] R. G. Gallager, Low Density Parity Check Codes, MIT Press, 1963.Google Scholar [10] K. Haymaker and C. A. Kelley, Structured bit-interleaved LDPC codes for MLC flash memory, IEEE J. Sel. Areas Commun., 32 (2014), 870-879. Google Scholar [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. Google Scholar [12] H. Imai and S. Hirakawa, A new multilevel coding method using error-correcting codes, IEEE Trans. Inf. Theory, 23 (1977), 371-377. Google Scholar [13] M. Moser and P. Chen, A Student's Guide to Coding and Information Theory, Cambridge Univ. Press, Cambridge, 2012. Google Scholar [14] 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. Google Scholar [15] 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. Google Scholar [16] R. M. Tanner, A recursive approach to low complexity codes, IEEE Trans. Inf. Theory, 27 (1981), 533-547. Google Scholar [17] T. Tao and V. H. Vu, Additive Combinatorics, Cambridge Univ. Press, 2006. Google Scholar [18] 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. Google Scholar [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.Google Scholar

show all references

##### References:
 [1] K. A. S. Abdel-Ghaffar and M. Hassner, Multilevel error-control codes for data storage channels, IEEE Trans. Inf. Theory, 37 (1991), 735-741. Google Scholar [2] S. Borade, B. Nakiboğlu and L. Zheng, Unequal error protection: an information-theoretic perspective, IEEE Trans. Inf. Theory, 55 (2009), 5511-5539. Google Scholar [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.Google Scholar [4] A. R. Calderbank and N. Seshadri, Multilevel codes for unequal error protection, IEEE Trans. Inf. Theory, 39 (1993), 1234-1248. Google Scholar [5] 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. Google Scholar [6] D. Declercq and M. Fossorier, Decoding algorithms for nonbinary LDPC codes over $\text{GF}(q)$, IEEE Trans. Commun., 55 (2007), 633-643. Google Scholar [7] 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. Google Scholar [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.Google Scholar [9] R. G. Gallager, Low Density Parity Check Codes, MIT Press, 1963.Google Scholar [10] K. Haymaker and C. A. Kelley, Structured bit-interleaved LDPC codes for MLC flash memory, IEEE J. Sel. Areas Commun., 32 (2014), 870-879. Google Scholar [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. Google Scholar [12] H. Imai and S. Hirakawa, A new multilevel coding method using error-correcting codes, IEEE Trans. Inf. Theory, 23 (1977), 371-377. Google Scholar [13] M. Moser and P. Chen, A Student's Guide to Coding and Information Theory, Cambridge Univ. Press, Cambridge, 2012. Google Scholar [14] 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. Google Scholar [15] 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. Google Scholar [16] R. M. Tanner, A recursive approach to low complexity codes, IEEE Trans. Inf. Theory, 27 (1981), 533-547. Google Scholar [17] T. Tao and V. H. Vu, Additive Combinatorics, Cambridge Univ. Press, 2006. Google Scholar [18] 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. Google Scholar [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.Google Scholar
$4$-ary partial erasure channel (QPEC) with $M=2$. Here, the binary representation of each $4$-ary symbol is shown.
$4$-ary multilevel erasure channel with erasure probability $\varepsilon$ and bit error probability $\gamma$.
$I(X;Y)$ as a function of $\varepsilon$, given a uniform input distribution.
Subchannel for $X_1$ on $4$-ary multilevel erasure channel with parameters $\varepsilon,\gamma$.
Subchannel for $X_2$ on $4$-ary multilevel erasure channel with parameters $\varepsilon,\gamma$.
Subchannel for $X_1$ on 4-ary partial erasure channel (QPEC) with erasure probability $\varepsilon$.
Subchannel for $X_2$ on 4-ary partial erasure channel (QPEC) with erasure probability $\varepsilon$.
 [1] Joan-Josep Climent, Diego Napp, Raquel Pinto, Rita Simões. Decoding of $2$D convolutional codes over an erasure channel. Advances in Mathematics of Communications, 2016, 10 (1) : 179-193. doi: 10.3934/amc.2016.10.179 [2] Washiela Fish, Jennifer D. Key, Eric Mwambene. Partial permutation decoding for simplex codes. Advances in Mathematics of Communications, 2012, 6 (4) : 505-516. doi: 10.3934/amc.2012.6.505 [3] Holger Boche, Rafael F. Schaefer. Arbitrarily varying multiple access channels with conferencing encoders: List decoding and finite coordination resources. Advances in Mathematics of Communications, 2016, 10 (2) : 333-354. doi: 10.3934/amc.2016009 [4] Tobias Sutter, David Sutter, John Lygeros. Capacity of random channels with large alphabets. Advances in Mathematics of Communications, 2017, 11 (4) : 813-835. doi: 10.3934/amc.2017060 [5] JiYoon Jung, Carl Mummert, Elizabeth Niese, Michael Schroeder. On erasure combinatorial batch codes. Advances in Mathematics of Communications, 2018, 12 (1) : 49-65. doi: 10.3934/amc.2018003 [6] Nadia Bedjaoui, Erik Weyer, Georges Bastin. Methods for the localization of a leak in open water channels. Networks & Heterogeneous Media, 2009, 4 (2) : 189-210. doi: 10.3934/nhm.2009.4.189 [7] Carlos E. Kenig. The method of energy channels for nonlinear wave equations. Discrete & Continuous Dynamical Systems - A, 2019, 39 (12) : 6979-6993. doi: 10.3934/dcds.2019240 [8] Shiqiu Liu, Frédérique Oggier. On applications of orbit codes to storage. Advances in Mathematics of Communications, 2016, 10 (1) : 113-130. doi: 10.3934/amc.2016.10.113 [9] Kwankyu Lee. Decoding of differential AG codes. Advances in Mathematics of Communications, 2016, 10 (2) : 307-319. doi: 10.3934/amc.2016007 [10] Sara D. Cardell, Joan-Josep Climent. An approach to the performance of SPC product codes on the erasure channel. Advances in Mathematics of Communications, 2016, 10 (1) : 11-28. doi: 10.3934/amc.2016.10.11 [11] Daniele Andreucci, Dario Bellaveglia, Emilio N.M. Cirillo, Silvia Marconi. Effect of intracellular diffusion on current--voltage curves in potassium channels. Discrete & Continuous Dynamical Systems - B, 2014, 19 (7) : 1837-1853. doi: 10.3934/dcdsb.2014.19.1837 [12] Juan C. Moreno, V. B. Surya Prasath, João C. Neves. Color image processing by vectorial total variation with gradient channels coupling. Inverse Problems & Imaging, 2016, 10 (2) : 461-497. doi: 10.3934/ipi.2016008 [13] David Karpuk, Anne-Maria Ernvall-Hytönen, Camilla Hollanti, Emanuele Viterbo. Probability estimates for fading and wiretap channels from ideal class zeta functions. Advances in Mathematics of Communications, 2015, 9 (4) : 391-413. doi: 10.3934/amc.2015.9.391 [14] Virginia González-Vélez, Amparo Gil, Iván Quesada. Minimal state models for ionic channels involved in glucagon secretion. Mathematical Biosciences & Engineering, 2010, 7 (4) : 793-807. doi: 10.3934/mbe.2010.7.793 [15] Elisa Gorla, Felice Manganiello, Joachim Rosenthal. An algebraic approach for decoding spread codes. Advances in Mathematics of Communications, 2012, 6 (4) : 443-466. doi: 10.3934/amc.2012.6.443 [16] Alexander Barg, Arya Mazumdar, Gilles Zémor. Weight distribution and decoding of codes on hypergraphs. Advances in Mathematics of Communications, 2008, 2 (4) : 433-450. doi: 10.3934/amc.2008.2.433 [17] Ali Tebbi, Terence Chan, Chi Wan Sung. Linear programming bounds for distributed storage codes. Advances in Mathematics of Communications, 2019, 0 (0) : 0-0. doi: 10.3934/amc.2020024 [18] Marta Lewicka, Mohammadreza Raoofi. A stability result for the Stokes-Boussinesq equations in infinite 3d channels. Communications on Pure & Applied Analysis, 2013, 12 (6) : 2615-2625. doi: 10.3934/cpaa.2013.12.2615 [19] Tehuan Chen, Chao Xu, Zhigang Ren. Computational optimal control of 1D colloid transport by solute gradients in dead-end micro-channels. Journal of Industrial & Management Optimization, 2018, 14 (3) : 1251-1269. doi: 10.3934/jimo.2018052 [20] Yoora Kim, Gang Uk Hwang, Hea Sook Park. Feedback limited opportunistic scheduling and admission control for ergodic rate guarantees over Nakagami-$m$ fading channels. Journal of Industrial & Management Optimization, 2009, 5 (3) : 553-567. doi: 10.3934/jimo.2009.5.553

2018 Impact Factor: 0.879