TY - GEN
T1 - Optimal threshold-based multi-trial error/erasure decoding with the Guruswami-Sudan algorithm
AU - Senger, Christian
AU - Sidorenko, Vladimir R.
AU - Bossert, Martin
AU - Zyablov, Victor V.
PY - 2011
Y1 - 2011
N2 - Traditionally, multi-trial error/erasure decoding of Reed-Solomon (RS) codes is based on Bounded Minimum Distance (BMD) decoders with an erasure option. Such decoders have error/erasure tradeoff factor λ= 2, which means that an error is twice as expensive as an erasure in terms of the code's minimum distance. The Guruswami-Sudan (GS) list decoder can be considered as state of the art in algebraic decoding of RS codes. Besides an erasure option, it allows to adjust to λ values in the range 1 < λ ≤ 2. Based on previous work [1], we provide formulae which allow to optimally (in terms of residual codeword error probability) exploit the erasure option of decoders with arbitrary λ, if the decoder can be used z ≥ 1 times. We show that BMD decoders with zBMD decoding trials can result in lower residual codeword error probability than GS decoders with zGS trials, if zBMD is only slightly larger than zGS. This is of practical interest since BMD decoders generally have lower computational complexity than GS decoders.
AB - Traditionally, multi-trial error/erasure decoding of Reed-Solomon (RS) codes is based on Bounded Minimum Distance (BMD) decoders with an erasure option. Such decoders have error/erasure tradeoff factor λ= 2, which means that an error is twice as expensive as an erasure in terms of the code's minimum distance. The Guruswami-Sudan (GS) list decoder can be considered as state of the art in algebraic decoding of RS codes. Besides an erasure option, it allows to adjust to λ values in the range 1 < λ ≤ 2. Based on previous work [1], we provide formulae which allow to optimally (in terms of residual codeword error probability) exploit the erasure option of decoders with arbitrary λ, if the decoder can be used z ≥ 1 times. We show that BMD decoders with zBMD decoding trials can result in lower residual codeword error probability than GS decoders with zGS trials, if zBMD is only slightly larger than zGS. This is of practical interest since BMD decoders generally have lower computational complexity than GS decoders.
UR - https://www.scopus.com/pages/publications/80054821913
U2 - 10.1109/ISIT.2011.6034255
DO - 10.1109/ISIT.2011.6034255
M3 - Conference contribution
AN - SCOPUS:80054821913
SN - 9781457705953
T3 - IEEE International Symposium on Information Theory - Proceedings
SP - 845
EP - 849
BT - 2011 IEEE International Symposium on Information Theory Proceedings, ISIT 2011
PB - Institute of Electrical and Electronics Engineers Inc.
T2 - 2011 IEEE International Symposium on Information Theory, ISIT 2011
Y2 - 31 July 2011 through 5 August 2011
ER -