Complexity Analysis of Reed-Solomon Decoding over GF(2^m) Without Using Syndromes

Details Complexity Analysis of Reed-Solomon Decoding over GF(2^m) Without Using Syndromes Complexity Analysis of Reed-Solomon Decoding over GF(2^m) Without Using Syndromes

2008-03-05

arxiv.org/abs/0803.0731v2

Computer Science

Information Theory

11 pages, submitted to EURASIP Journal on Wireless Communications and Networking

Scientific paper

For the majority of the applications of Reed-Solomon (RS) codes, hard decision decoding is based on syndromes. Recently, there has been renewed interest in decoding RS codes without using syndromes. In this paper, we investigate the complexity of syndromeless decoding for RS codes, and compare it to that of syndrome-based decoding. Aiming to provide guidelines to practical applications, our complexity analysis differs in several aspects from existing asymptotic complexity analysis, which is typically based on multiplicative fast Fourier transform (FFT) techniques and is usually in big O notation. First, we focus on RS codes over characteristic-2 fields, over which some multiplicative FFT techniques are not applicable. Secondly, due to moderate block lengths of RS codes in practice, our analysis is complete since all terms in the complexities are accounted for. Finally, in addition to fast implementation using additive FFT techniques, we also consider direct implementation, which is still relevant for RS codes with moderate lengths. Comparing the complexities of both syndromeless and syndrome-based decoding algorithms based on direct and fast implementations, we show that syndromeless decoding algorithms have higher complexities than syndrome-based ones for high rate RS codes regardless of the implementation. Both errors-only and errors-and-erasures decoding are considered in this paper. We also derive tighter bounds on the complexities of fast polynomial multiplications based on Cantor's approach and the fast extended Euclidean algorithm.

Affiliated with

Also associated with

No associations

Rating

Complexity Analysis of Reed-Solomon Decoding over GF(2^m) Without Using Syndromes does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Complexity Analysis of Reed-Solomon Decoding over GF(2^m) Without Using Syndromes, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Complexity Analysis of Reed-Solomon Decoding over GF(2^m) Without Using Syndromes will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-161779