Modified Euclidean Algorithms for Decoding Reed-Solomon Codes

Understand

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.