Figure 1.
$4$ -ary partial erasure channel (QPEC) with $M=2$ . Here, the binary representation of each $4$ -ary symbol is shown.
-
Previous Article
On ${{\mathbb{Z}}}_{p^r}{{\mathbb{Z}}}_{p^s}$-additive cyclic codes
- AMC Home
- This Issue
-
Next Article
On the spectrum for the genera of maximal curves over small fields
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 |
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:
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.
|
| [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.
|
| [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.
|
| [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. |
| [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. |
| [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.
|
| [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.
|
| [16] |
R. M. Tanner,
A recursive approach to low complexity codes, IEEE Trans. Inf. Theory, 27 (1981), 533-547.
|
| [17] |
T. Tao and V. H. Vu,
Additive Combinatorics,
Cambridge Univ. Press, 2006. |
| [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.
|
| [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.
|
| [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.
|
| [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.
|
| [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. |
| [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. |
| [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.
|
| [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.
|
| [16] |
R. M. Tanner,
A recursive approach to low complexity codes, IEEE Trans. Inf. Theory, 27 (1981), 533-547.
|
| [17] |
T. Tao and V. H. Vu,
Additive Combinatorics,
Cambridge Univ. Press, 2006. |
| [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.
|
| [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 2.
$4$ -ary multilevel erasure channel with erasure probability $\varepsilon$ and bit error probability $\gamma$ .
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$ .
| [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] |
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 |
| [13] |
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 |
| [14] |
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 |
| [15] |
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 |
| [16] |
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 |
| [17] |
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 |
| [18] |
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 |
| [19] |
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 |
| [20] |
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 |
2019 Impact Factor: 0.734
Tools
Metrics
Other articles
by authors
[Back to Top]