Modified Euclidean Algorithms for Decoding Reed-Solomon Codes

Zhiyuan Yan, Dilip V. Sarwate

Publication date: 22 June 2009

Abstract: The extended Euclidean algorithm (EEA) for polynomial greatest common divisors is commonly used in solving the key equation in the decoding of Reed-Solomon (RS) codes, and more generally in BCH decoding. For this particular application, the iterations in the EEA are stopped when the degree of the remainder polynomial falls below a threshold. While determining the degree of a polynomial is a simple task for human beings, hardware implementation of this stopping rule is more complicated. This paper describes a modified version of the EEA that is specifically adapted to the RS decoding problem. This modified algorithm requires no degree computation or comparison to a threshold, and it uses a fixed number of iterations. Another advantage of this modified version is in its application to the errors-and-erasures decoding problem for RS codes where significant hardware savings can be achieved via seamless computation.

Has companion code repository: https://github.com/pooruse/reed_solomon

This page was built for publication: Modified Euclidean Algorithms for Decoding Reed-Solomon Codes

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6214429)