American Institute of Mathematical Sciences

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

Channel decomposition for multilevel codes over multilevel and partial erasure channels

Carolyn Mayer 1,, , Kathryn Haymaker 2, and  Christine A. Kelley 1,

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.

Keywords: Partial erasure channels, multilevel codes, multistage decoding, storage channels.
Mathematics Subject Classification: Primary: 94A40, 94B35; Secondary: 94A15.
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

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

Download full-size image

Download as PowerPoint slide

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

Download full-size image

Download as PowerPoint slide

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

Download full-size image

Download as PowerPoint slide

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

Download full-size image

Download as PowerPoint slide

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

Download full-size image

Download as PowerPoint slide

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

Download full-size image

Download as PowerPoint slide

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

Download full-size image

Download as PowerPoint slide

[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]

Julia Lieb, Raquel Pinto. A decoding algorithm for 2D convolutional codes over the erasure channel. Advances in Mathematics of Communications, 2021  doi: 10.3934/amc.2021031
[3]

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
[4]

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
[5]

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
[6]

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
[7]

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
[8]

Carlos E. Kenig. The method of energy channels for nonlinear wave equations. Discrete & Continuous Dynamical Systems, 2019, 39 (12) : 6979-6993. doi: 10.3934/dcds.2019240
[9]

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
[10]

Kwankyu Lee. Decoding of differential AG codes. Advances in Mathematics of Communications, 2016, 10 (2) : 307-319. doi: 10.3934/amc.2016007
[11]

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
[12]

Daniele Andreucci, Dario Bellaveglia, Emilio N.M. Cirillo, Silvia Marconi. Effect of intracellular diffusion on current--voltage curves in potassium channels. Discrete and Continuous Dynamical Systems - Series B, 2014, 19 (7) : 1837-1853. doi: 10.3934/dcdsb.2014.19.1837
[13]

Jorge P. Arpasi. On the non-Abelian group code capacity of memoryless channels. Advances in Mathematics of Communications, 2020, 14 (3) : 423-436. doi: 10.3934/amc.2020058
[14]

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
[15]

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
[16]

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
[17]

Filippo Giuliani. Transfers of energy through fast diffusion channels in some resonant PDEs on the circle. Discrete & Continuous Dynamical Systems, 2021, 41 (11) : 5057-5085. doi: 10.3934/dcds.2021068
[18]

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
[19]

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
[20]

Ali Tebbi, Terence Chan, Chi Wan Sung. Linear programming bounds for distributed storage codes. Advances in Mathematics of Communications, 2020, 14 (2) : 333-357. doi: 10.3934/amc.2020024

2020 Impact Factor: 0.935

Tools

Metrics

  • PDF downloads (294)
  • HTML views (191)
  • Cited by (0)

Other articles
by authors

[Back to Top]

Copyright © 2021 American Institute of Mathematical Sciences