Minimizing the Alphabet Size in Codes With Restricted Error Sets

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.