A Decoding Approach to Reed–Solomon Codes from Their Definition

Abstract

Because of their importance in applications and their quite simple definition, Reed–Solomon codes can be explained in any introductory course on coding theory. However, decoding algorithms for Reed–Solomon codes are far from being simple and it is difficult to fit them in introductory courses for undergraduates. We introduce a new decoding approach, in a self-contained presentation, which we think may be appropriate for introducing error correction of Reed–Solomon codes to nonexperts. In particular, we interpret Reed–Solomon codes by means of the degree of the interpolation polynomial of the code words and from this derive a decoding algorithm. Compared to the classical algorithms, our algorithm appears to arise more naturally from definitions and to be easier to understand. It is related to the Peterson–Gorenstein–Zierler algorithm (see [10] and [20]).

MSC:

• Primary 12Y05
• Secondary 94B35

Acknowledgments

The author would like to thank the anonymous referees for deeply reading the manuscript and for making very useful comments. She would especially like to thank the editor Susan Jane Colley for her careful reading.

Additional information

Notes on contributors

Maria Bras-Amorós

MARIA BRAS-AMORÓS is an associate professor at Universitat Rovira i Virgili, where she mainly develops her research. She also collaborates regularly at San Diego State University in California and Chosun University in Korea. Her research areas include coding theory, discrete mathematics, data privacy, and numerical semigroups; she also has some incursions into scientometrics. She has authored more than 40 publications, according to ISI-WOS, in the most relevant journals in all these fields.

She is the main researcher of the research group COPRICA (Codes, Privacy, and Algebraic Combinatorics) in Universitat Rovira i Virgili. She is a member of the Spanish research networks on Symbolic and Algebraic Computation and Applications, the research network Mathematics in the Information Society (which she led between 2009 and 2014), and was one of the founders of the Spanish network on Monoids and Applications.Universitat Rovira i Virgili, Av. Països Catalans 26, 43007 Tarragona, Catalonia [email protected]