Generic Reed-Solomon Codes Achieve List-Decoding Capacity
Joshua Brakensiek, Sivakanth Gopi, Visu Makam
Abstract
In a recent paper, Brakensiek, Gopi and Makam introduced higher order MDS codes as a generalization of MDS codes. An order-ℓ MDS code, denoted by MDS(ℓ), has the property that any ℓ subspaces formed from columns of its generator matrix intersect as minimally as possible. An independent work by Roth defined a different notion of higher order MDS codes as those achieving a generalized singleton bound for list-decoding. In this work, we show that these two notions of higher order MDS codes are (nearly) equivalent.
Topics & Concepts
Generator matrixList decodingReed–Solomon error correctionDecoding methodsGeneralizationComputer scienceConcatenated error correction codeReed–Muller codeOrder (exchange)Block codeDiscrete mathematicsMathematicsArithmeticAlgorithmFinanceMathematical analysisEconomicsCoding theory and cryptographygraph theory and CDMA systemsCooperative Communication and Network Coding