Please use this identifier to cite or link to this item: http://localhost/handle/Hannan/637987
Title: FFT Algorithm for Binary Extension Finite Fields and Its Application to Reed&x2013;Solomon Codes
Authors: Sian-Jheng Lin;Tareq Y. Al-Naffouri;Yunghsiang S. Han
subject: Reed-Solomon codes|Algorithm design and analysis|Galois fields
Year: 2016
Publisher: IEEE
Abstract: Recently, a new polynomial basis over binary extension fields was proposed, such that the fast Fourier transform (FFT) over such fields can be computed in the complexity of order O(n lg), where n is the number of points evaluated in FFT. In this paper, we reformulate this FFT algorithm, such that it can be easier understood and be extended to develop frequencydomain decoding algorithms for (n = 2m , k) systematic Reed-Solomon (RS) codes over F<sub>2m</sub>, m &#x2208; Z+ , with n- k a power of two. First, the basis of syndrome polynomials is reformulated in the decoding procedure so that the new transforms can be applied to the decoding procedure. A fast extended Euclidean algorithm is developed to determine the error locator polynomial. The computational complexity of the proposed decoding algorithm is O(n lg(n-k)+(n-k) lg2 (n-k)), improving upon the best currently available decoding complexity O(n lg2 lglg), and reaching the best known complexity bound that was established by Justesen in 1976. However, Justesen's approach is only for the codes over some specific fields, which can apply Cooley-Tukey FFTs. As revealed by the computer simulations, the proposed decoding algorithm is 50 times faster than the conventional one for the (216 , 215 ) RS code over F<sub>216</sub>.
URI: http://localhost/handle/Hannan/173325
http://localhost/handle/Hannan/637987
ISSN: 0018-9448
1557-9654
volume: 62
issue: 10
Appears in Collections:2016

Files in This Item:
File Description SizeFormat 
7543456.pdf414.43 kBAdobe PDFThumbnail
Preview File
Title: FFT Algorithm for Binary Extension Finite Fields and Its Application to Reed&x2013;Solomon Codes
Authors: Sian-Jheng Lin;Tareq Y. Al-Naffouri;Yunghsiang S. Han
subject: Reed-Solomon codes|Algorithm design and analysis|Galois fields
Year: 2016
Publisher: IEEE
Abstract: Recently, a new polynomial basis over binary extension fields was proposed, such that the fast Fourier transform (FFT) over such fields can be computed in the complexity of order O(n lg), where n is the number of points evaluated in FFT. In this paper, we reformulate this FFT algorithm, such that it can be easier understood and be extended to develop frequencydomain decoding algorithms for (n = 2m , k) systematic Reed-Solomon (RS) codes over F<sub>2m</sub>, m &#x2208; Z+ , with n- k a power of two. First, the basis of syndrome polynomials is reformulated in the decoding procedure so that the new transforms can be applied to the decoding procedure. A fast extended Euclidean algorithm is developed to determine the error locator polynomial. The computational complexity of the proposed decoding algorithm is O(n lg(n-k)+(n-k) lg2 (n-k)), improving upon the best currently available decoding complexity O(n lg2 lglg), and reaching the best known complexity bound that was established by Justesen in 1976. However, Justesen's approach is only for the codes over some specific fields, which can apply Cooley-Tukey FFTs. As revealed by the computer simulations, the proposed decoding algorithm is 50 times faster than the conventional one for the (216 , 215 ) RS code over F<sub>216</sub>.
URI: http://localhost/handle/Hannan/173325
http://localhost/handle/Hannan/637987
ISSN: 0018-9448
1557-9654
volume: 62
issue: 10
Appears in Collections:2016

Files in This Item:
File Description SizeFormat 
7543456.pdf414.43 kBAdobe PDFThumbnail
Preview File
Title: FFT Algorithm for Binary Extension Finite Fields and Its Application to Reed&x2013;Solomon Codes
Authors: Sian-Jheng Lin;Tareq Y. Al-Naffouri;Yunghsiang S. Han
subject: Reed-Solomon codes|Algorithm design and analysis|Galois fields
Year: 2016
Publisher: IEEE
Abstract: Recently, a new polynomial basis over binary extension fields was proposed, such that the fast Fourier transform (FFT) over such fields can be computed in the complexity of order O(n lg), where n is the number of points evaluated in FFT. In this paper, we reformulate this FFT algorithm, such that it can be easier understood and be extended to develop frequencydomain decoding algorithms for (n = 2m , k) systematic Reed-Solomon (RS) codes over F<sub>2m</sub>, m &#x2208; Z+ , with n- k a power of two. First, the basis of syndrome polynomials is reformulated in the decoding procedure so that the new transforms can be applied to the decoding procedure. A fast extended Euclidean algorithm is developed to determine the error locator polynomial. The computational complexity of the proposed decoding algorithm is O(n lg(n-k)+(n-k) lg2 (n-k)), improving upon the best currently available decoding complexity O(n lg2 lglg), and reaching the best known complexity bound that was established by Justesen in 1976. However, Justesen's approach is only for the codes over some specific fields, which can apply Cooley-Tukey FFTs. As revealed by the computer simulations, the proposed decoding algorithm is 50 times faster than the conventional one for the (216 , 215 ) RS code over F<sub>216</sub>.
URI: http://localhost/handle/Hannan/173325
http://localhost/handle/Hannan/637987
ISSN: 0018-9448
1557-9654
volume: 62
issue: 10
Appears in Collections:2016

Files in This Item:
File Description SizeFormat 
7543456.pdf414.43 kBAdobe PDFThumbnail
Preview File