  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.
