On Asymptotic Strategies for GMD Decoding with Arbitrary Error-Erasure Tradeoff
Abstract. Consider a block code C of length n with Hamming distance d. Assume we have a decoder Φ, which corrects e errors and t erasures, as soon as λe + t ≤ d − 1, where the real number 1 < λ ≤ 2 is the error-erasure tradeoff of the decoder Φ. In the classical case of bounded minimum distance decoder we have λ = 2, while smaller values of λ arise in decoding, e.g., interleaved or folded Reed–Solomon codes, as well as in algebraic decoding algorithms like Sudan or Guruswami–Sudan.
Given a word r with reliabilities of symbols, the goal of generalized minimum distance (GMD) decoding is to find a nearest codeword c ∈ C in generalized Hamming metric, defined by these reliabilities. We use multi-trial GMD Forney’s decoder, which at every trial applies Φ to decode r, where some low reliable symbols are erased. We investigate different erasing strategies based on either erasing a fraction of the received symbols or erasing all symbols whose reliability values are below a certain threshold.
The erasing strategy may be either static or adaptive, where adaptive means that the erasing parameters are a function of the reliabilities. For every strategy we propose an optimal set of parameters and evaluate the error-correction radius of m-trial GMD decoder defined by each strategy.
We use an asymptotic approach, i.e., large n, which drastically simplifies the analysis and presentation of the results over existing literature.
Book / Congress title:
Ninth International Workshop on Coding and Cryptography (WCC)