Minimizing the Alphabet Size in Codes With Restricted Error Sets
- 10 January 2024
- journal article
- research article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Information Theory
- Vol. 70 (6) , 3891-3902
Abstract
This paper focuses on the study of the minimum possible alphabet size of codes in a generalized setting where the coding scheme is required to handle a pre-specified set of erasure or error patterns, naturally represented by a hypergraph. The need for such codes arises in many settings of practical interest, including wireless communication and flash memory systems. In many such settings, a smaller field size is achievable than that offered by MDS and other standard codes. We establish a connection between the minimum alphabet size of codes in this generalized setting and the combinatorial properties of the hypergraph that represents the pre-specified collection of erasure or error patterns. We also establish connections between error and erasure correcting codes in our generalized setting. Finally, we consider a variation of the problem that allows a small probability of decoding error and relate it to an approximate version of hypergraph coloring.Keywords
Funding Information
- Israel Science Foundation (1218/20)
- NSF (1909451)
This publication has 13 references indexed in Scilit:
- On the Weights of General MDS CodesIEEE Transactions on Information Theory, 2020
- Codes for Graph ErasuresIEEE Transactions on Information Theory, 2019
- A study of DRAM failures in the field2012
- On sets of vectors of a finite vector space in which every subset of basis size is a basisJournal of the European Mathematical Society, 2012
- Novel Burst Error Correction Algorithms for Reed-Solomon CodesIEEE Transactions on Information Theory, 2012
- Error characterization and coding schemes for flash memories2010
- The Hardness of 3-Uniform Hypergraph ColoringCombinatorica, 2005
- Detection of prescribed error events: application to perpendicular recording2005
- Strong Colorings of HypergraphsLecture Notes in Computer Science, 2005
- Curve razionali normali ek-archi negli spazi finitiAnnali di Matematica Pura ed Applicata (1923 -), 1955