Title :
Modified Euclidean algorithms for decoding Reed-Solomon codes
Author :
Sarwate, Dilip V. ; Yan, Zhiyuan
Author_Institution :
Dept. of Electr. & Comput. Eng., Univ. of Illinois at Urbana-Champaign, Urbana, IL, USA
fDate :
June 28 2009-July 3 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.
Keywords :
BCH codes; Reed-Solomon codes; iterative decoding; BCH decoding; Reed-Solomon codes; extended Euclidean algorithm; stopping rule; Application software; Circuits; Consumer electronics; DVD; Equations; Hardware; Humans; Iterative decoding; Polynomials; Reed-Solomon codes;
Conference_Titel :
Information Theory, 2009. ISIT 2009. IEEE International Symposium on
Conference_Location :
Seoul
Print_ISBN :
978-1-4244-4312-3
Electronic_ISBN :
978-1-4244-4313-0
DOI :
10.1109/ISIT.2009.5205901