SpringerOpen Newsletter

Receive periodic news and updates relating to SpringerOpen.

This article is part of the series Advances in Error Control Coding Techniques.

Open Access Research Article

Complexity Analysis of Reed-Solomon Decoding over GF without Using Syndromes

Ning Chen and Zhiyuan Yan*

Author Affiliations

Department of Electrical and Computer Engineering, Lehigh University, Bethlehem, PA 18015, USA

For all author emails, please log on.

EURASIP Journal on Wireless Communications and Networking 2008, 2008:843634  doi:10.1155/2008/843634

The electronic version of this article is the complete one and can be found online at: http://jwcn.eurasipjournals.com/content/2008/1/843634

Received:15 November 2007
Revisions received:29 March 2008
Accepted:6 May 2008
Published:14 May 2008

© 2008 The Author(s).

This is an open access article distributed under the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.


There has been renewed interest in decoding Reed-Solomon (RS) codes without using syndromes recently. In this paper, we investigate the complexity of syndromeless decoding, and compare it to that of syndrome-based decoding. Aiming to provide guidelines to practical applications, our complexity analysis focuses on RS codes over characteristic-2 fields, for which some multiplicative FFT techniques are not applicable. Due to moderate block lengths of RS codes in practice, our analysis is complete, without big notation. In addition to fast implementation using additive FFT techniques, we also consider direct implementation, which is still relevant for RS codes with moderate lengths. For high-rate RS codes, when compared to syndrome-based decoding algorithms, not only syndromeless decoding algorithms require more field operations regardless of implementation, but also decoder architectures based on their direct implementations have higher hardware costs and lower throughput. We also derive tighter bounds on the complexities of fast polynomial multiplications based on Cantor's approach and the fast extended Euclidean algorithm.

Publisher note

To access the full article, please see PDF