DocumentCode :
46784
Title :
On the Average Complexity of Reed–Solomon List Decoders
Author :
Cassuto, Yuval ; Bruck, Jehoshua ; McEliece, R.J.
Author_Institution :
Dept. of Electr. Eng., Technion - Israel Inst. of Technol., Haifa, Israel
Volume :
59
Issue :
4
fYear :
2013
fDate :
Apr-13
Firstpage :
2336
Lastpage :
2351
Abstract :
The number of monomials required to interpolate a received word in an algebraic list decoder for Reed-Solomon codes depends on the instantaneous channel error, and not only on the decoder design parameters. The implications of this fact are that the decoder should be able to exhibit lower decoding complexity for low-weight errors and, consequently, enjoy a better average-case decoding complexity and a higher decoding throughput. On the analytical side, this paper studies the dependence of interpolation costs on instantaneous errors, in both hard- and soft-decision decoders. On the algorithmic side, it provides an efficient interpolation algorithm, based on the state-of-the-art interpolation algorithm, that enjoys reduced running times for reduced interpolation costs.
Keywords :
Reed-Solomon codes; algebraic codes; codecs; decoding; interpolation; Reed-Solomon codes; Reed-Solomon list decoders; algebraic list decoder; decoder design parameters; decoding complexity; decoding throughput; hard-decision decoders; instantaneous channel error; interpolation algorithm; interpolation costs; low-weight errors; monomials; received word; running times; soft-decision decoders; Complexity theory; Decoding; Interpolation; Polynomials; Reed-Solomon codes; Standards; Upper bound; Algebraic list decoding; Kötter–Vardy soft decoding; Reed–Solomon (RS) codes; bivariate interpolation;
fLanguage :
English
Journal_Title :
Information Theory, IEEE Transactions on
Publisher :
ieee
ISSN :
0018-9448
Type :
jour
DOI :
10.1109/TIT.2012.2235522
Filename :
6451269
Link To Document :
بازگشت