2017 · 20 citations · 13 references
EngineeringComputer ScienceElectrical EngineeringAlgorithmsDigital CommunicationInformation TheoryChannel CodingCoding TheoryError Control CodingError-correcting CodesAsymptotic AnalysisAsymptotic PropertiesDecoding AlgorithmsDecoding ComplexityDecoding StrategiesReed-solomon CodesReed-solomon Coding
We propose a new partial decoding algorithm for m-interleaved Reed-Solomon (IRS) codes that can decode, with high probability, a random error of relative weight 1 - R <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">m</sup> / <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">m</sup> + <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">1</sup> at all code rates R, in time polynomial in the code length n. For m > 2, this is an asymptotic improvement over the previous state-of-the-art for all rates, and the first improvement for R > 1/3 in the last 20 years. The method combines collaborative decoding of IRS codes with power decoding up to the Johnson radius.
13
Improved decoding of Reed-Solomon and algebraic-geometric codes
Venkatesan Guruswami, Madhu Sudan · 2002 · 312 citations