2015/03/19 by Sian-Jheng Lin, Tareq Y. Al-Naffouri, Lin, Sian-Jheng +3
Computer Science · #Advanced Data Storage Technologies #Coding theory and cryptography #Cryptography and Residue Arithmetic #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Information Theory (cs.IT)
paper · pdf · doi:10.48550/arxiv.1503.05761
openalex publication_date 2015/03/19 · openalex created_date 2016/09/16 · openalex updated_date 2026/08/01
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(n)), where n is the number of points evaluated in FFT. In this work, we reformulate this FFT algorithm such that it can be easier understood and be extended to develop frequency-domain decoding algorithms for (n=2m,k) systematic Reed-Solomon~(RS) codes over \mathbbF2m,m∈ ℤ+, 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(n)\lg\lg(n)), 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-Tucky 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 \mathbbF216.