2020/05/14 by Mira Gonen, Gonen, Mira, Ishay Haviv +5
Engineering · Computer Science · #graph theory and CDMA systems #Coding theory and cryptography #Algorithms and Data Compression
paper · pdf · doi:10.48550/arxiv.2005.06947
A Maximum Distance Separable code over an alphabet F is defined via an\nencoding function C:Fk \→ Fn that allows to retrieve a message m\n\∈ Fk from the codeword C(m) even after erasing any n-k of its symbols.\nThe minimum possible alphabet size of general (non-linear) MDS codes for given\nparameters n and k is unknown and forms one of the central open problems in\ncoding theory. The paper initiates the study of the alphabet size of codes in a\ngeneralized setting where the coding scheme is required to handle a\npre-specified subset of all possible erasure patterns, naturally represented by\nan n-vertex k-uniform hypergraph. We relate the minimum possible alphabet\nsize of such codes to the strong chromatic number of the hypergraph and analyze\nthe tightness of the obtained bounds for both the linear and non-linear\nsettings. We further consider variations of the problem which allow a small\nprobability of decoding error.\n