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: |
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.
![]() |
Subchannel for
Subchannel for
Subchannel for
Subchannel for