A simple algorithm for decoding Reed-Solomon codes and its relation to the Welch-Berlekamp algorithm

A simple and natural Gao algorithm for decoding algebraic codes is described. Its relation to the Welch-Berlekamp and Euclidean algorithms is given

• Publication year

  2005

• Venue

  IEEE Transactions on Information Theory

• Publication date

  2005-01-06

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.1109/TIT.2004.842738arXiv cs/0501011
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Correction to "A Simple Algorithm for Decoding Reed-Solomon Codes and Its Relation to the Welch-Berlekamp Algorithm"

  2006cited by this paper
• A Method for Fast Computation of the Fourier Transform over a Finite Field

  2003cited by this paper
• A New Algorithm for Decoding Reed-Solomon Codes

  2003influential reference
• Solution of Welch-Berlekamp key equation by Euclidean algorithm

  1993cited by this paper
• Generalized key-equation of remainder decoding algorithm for Reed-Solomon codes

  1992cited by this paper
• Highly Resilient Correctors for Polynomials

  1992cited by this paper
• Decoding of redundant residue polynomial codes using Euclid's algorithm

  1988influential reference
• A fast algorithm for the Fourier transform over finite fields and its VLSI implementation

  1988cited by this paper
• Theory and practice of error control codes

  1986cited by this paper
• Fast Algorithms for Digital Signal Processing

  1985cited by this paper
• On the complexity of decoding Reed-Solomon codes (Corresp.)

  1976cited by this paper
• A Method for Solving Key Equation for Decoding Goppa Codes

  1975cited by this paper
• The Design and Analysis of Computer Algorithms

  1974cited by this paper
• Fast computation of GCDs

  1973cited by this paper
• Theory of Error-correcting Codes

  year unknowninfluential reference

• Implications of Power Allocation Factors on the Performance of Ergodic Sum Rate in Cooperative Device-to-Device Systems with NOMA

  2023cites this paper
• A Spectral Algorithm for Decoding Systematic BCH Codes

  2022cites this paper
• A Decoding Approach to Reed–Solomon Codes from Their Definition

  2017cites this paper
• Performance Analysis of DRA Based OFDM Data Transmission With Respect to Novel High Speed RS Decoding

  2015cites this paper
• Performance Analysis of OFDM Data Transmission With Respect to Novel High Speed RS Decoding With VLSI Implementation

  2014cites this paper
• Decoding of block and convolutional codes in rank metric

  2014cites this paper
• A partial-inverse approach to decoding Reed-Solomon codes and polynomial remainder codes

  2014cites this paper
• Decoding of Block and Convolutional Codes in Rank Metric

  2013cites this paper
• T HÈSE / UNIVERSITÉ DE RENNES 1 sous le sceau de l'Université Européenne de Bretagne En Cotutelle Internationale avec l'Université d'Ulm, Allemagne pour le grade de DOCTEUR DE L'UNIVERSITÉ DE RENNES 1 Mention : Mathématiques et applications

  2013cites this paper
• An error/erasure decoding algorithm of (2m,2m−3) extended RS codes

  2013cites this paper
• A Unified View on Known Algebraic Decoding Algorithms and New Decoding Concepts

  2013cites this paper
• Direct Erasure-only Decoding for Generalized Reed-Solomon codes

  2012cites this paper
• On Polynomial Remainder Codes

  2012cites this paper
• On efficient decoding for the Fuzzy Vault scheme

  2012cites this paper
• Simple algorithms for decoding systematic Reed–Solomon codes

  2012cites this paper
• Exploiting Rateless Coding in Structured Overlays to Achieve Persistent Storage. (L'Exploitation de Codes Fontaines pour un Stockage Persistant des Données dans les Réseaux d'Overlay Structurés)

  2012cites this paper
• A Future Simplification of Procedure for Decoding Nonsystematic Reed-Solomon Codes Using the Berlekamp-Massey Algorithm

  2011cites this paper
• List Decoding of Generalized Reed-Solomon Codes by Using a Modified Extended Key Equation Algorithm

  2011cites this paper
• Decoding nonsystematic Reed-Solomon codes using the Berlekamp-Massey algorithm

  2011cites this paper
• Simplified procedure for decoding nonsystematic reed-solomon codes over gf(2m) using euclid's algorithm and the fast fourier transform

  2009cites this paper
• A simple algorithm for decoding both errors and erasures of Reed-Solomon codes

  2009cites this paper
• Modified decoding of binary Quadratic Residue codes by using Euclidean algorithm

  2009cites this paper
• Complexity Analysis of Reed-Solomon Decoding over GF(2m) without Using Syndromes

  2008cites this paper
• Efficient Interpolation in the Guruswami–Sudan Algorithm

  2008cites this paper
• Towards a practical and secure biometric authentication system

  2008cites this paper
• Simplified procedure for decoding reed-solomon codes using Euclid’s algorithm and the fast fourier transform over GF(2m)

  2007cites this paper
• Correction to "A Simple Algorithm for Decoding Reed-Solomon Codes and Its Relation to the Welch-Berlekamp Algorithm"

  2006cites this paper
• Decoding of the ( 41 , 21 , 9 ) Quadratic Residue Code Using the Gao ’ s Algorithm

  year unknowncites this paper