A Decoding Approach to Reed–Solomon Codes from Their Definition
Maria Bras-Amorós · American Mathematical Monthly · 2018
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 Gorenstein, D., Zierler, N. (1961). A class of error-correcting codes in pm symbols. J. Soc. Indust. Appl. Math. 9: 207–214.[Crossref] , [Google Scholar]] and [20 Peterson, W. W. (1960). Encoding and error-correction procedures for the Bose-Chaudhuri codes. IRE Trans. Inform. Theory. IT-6: 459–470. [Google Scholar]]).