Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

Globecom

Reduced GMD decoding of concatenated codes

Jos H. Weber, Khaled Abdel-Ghaffar

Published Nov 13, 2002• 0 citations
Publisher

Abstract

We present a general version of the generalized minimum distance (GMD) decoding algorithm (see Forney, G.D., Jr, 1966) that accommodates different erasing strategies. This version is called reduced GMD decoding since, depending on the erasing strategy used, it can offer a reduction in complexity over Forney's GMD decoding. We apply reduced GMD decoding to concatenated codes. In particular, we study the error correction capability and the unsuccessful decoding probability of concatenated codes with reduced GMD decoding.

DOI
10.1109/glocom.2001.965549

Related papers

Concatenated Codes

Ron M. Roth

In this chapter, we continue the discussion on concatenated codes, which was initiated in Section 5.4. The main message to be conveyed in this chapter is that by using concatenation, one can obtain codes with favorable asymptotic performance—in a sense to be quantified more precisely—while the complexity of constructing these codes and decoding them grows polynomially with the code length. We first present a decoding algorithm for concatenated codes, due to Forney. This algorithm, referred to as a generalized minimum distance (in short, GMD) decoder, corrects any error pattern whose Hamming weight is less than half the product of the minimum distances of the inner and outer codes (we recall that this product is a lower bound on the minimum distance of the respective concatenated code). A GMD decoder consists of a nearest-codeword decoder for the inner code, and a combined error–erasure decoder for the outer code. It then enumerates over a threshold value, marking the output of the inner decoder as erasure if that decoder returns an inner codeword whose Hamming distance from the respective received sub-word equals or exceeds that threshold. We show that under our assumption on the overall Hamming weight of the error word, there is at least one threshold for which the outer decoder recovers the correct codeword. If the outer code is taken as a GRS code, then a GMD decoder has an implementation with time complexity that is at most quadratic in the length of the concatenated code.

Cambridge University Press eBooks•Feb 23, 2006•0 citations

with Threshold Erasing

Khaled A. S. Abdel-Ghaffarl, Jos H. Weber

The error-correction capability and the performance of generalized minimum distance decod- ing based on threshold erasing is studied as a function of the number of decoding trials and of the allowable reliability values. Generalized Minimum Distance (GMD) decoding, as intro- duced by Forney (l), is a multitrial decoding algorithm that combines reliability information, represented by numbers in the closed interval (0,1), with algebraic decoding algorithms for error correction. In each trial, a fixed number of the most unreliable symbols in the received sequence is erased. If a cer- tain distance criterion is satisfied, Forney has shown that the transmitted codeword can be retrieved in at most (d/2) trials, where d is the Hamming distance of the code. In this work, we study a variation on Forney's scheme where, in each trial, symbols whose reliabilities are below a certain threshold are erased, and hence there is no need to sort the received symbols according to reliability values be- fore erasing as in Forney's GMD decoding. Furthermore, we consider limiting the allowable reliability values to the set R, = u~=mo/2'{1 - 2i/m}, where m = 1,2,3,. . .. This covers the simple cases of taking only hard decisions (m = l), allow- ing erasures (m = 2), or accommodating the full range (0,1) of reliability values as in Forney's GMD decoding (m + 00). Limiting the reliability values may be of importance since, in any digital implementation, the reliability values need to be quantized. Moreover, in some applications, e.g., GMD decod- ing of concatenated codes over discrete channels, the reliabil- ity values are discrete in nature (2). The maximum number of trials is kept as a parameter. Limiting the reliability values and the number of trials leads to the concept of reduced GMD decoding.

•Jan 1, 2001•0 citations

An improvement to GMD-like decoding algorithms

H. Tokushiga, Takuya Koumoto, Tadao Kasami

For binary linear block codes, we introduce a multiple generalized minimum distance (GMD) decoding algorithm, where GMD-like decoding is iterated around a few appropriately selected search centers. Compared with the original GMD decoding by Forney (1966), this decoding algorithm provides better error performance by increasing the number of iterations of erasure and error correction moderately. To reduce the number of iterations, we derive new effective sufficient conditions on the optimality of decoded codewords.

IEEE International Symposium on Information Theory (ISIT)•Nov 7, 2002•1 citation

On Asymptotic Strategies for GMD Decoding with Arbitrary Error-Erasure Tradeoff

Joschi Brauchle, Vladimir R. Sidorenko

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.

•Apr 13, 2015•0 citations

List decoding of concatenated codes: improved performance estimates

Alexander Barg, Andrew McGregor

An improved bound is proved on the list-decoding radius of a concatenated code relying upon a combination of (soft-decision) algebraic list decoding and generalized minimum distance (GMD) decoding in the outer level. This bound is further improved if the inner code is a random linear code.

IEEE International Symposium on Information Theory (ISIT)•Dec 23, 2004•0 citations

On combining Chase-2 and GMD decoding algorithms for nonbinary block codes

H. Tang, Y. Liu, M.P.C. Fossorier +1 more

In this letter, a class of algorithms that combines Chase-2 and GMD (generalized minimum distance) decoding algorithms is presented for nonbinary block codes. This approach provides additional trade-offs between error performance and decoding complexity. Reduced-complexity versions of the algorithms with practical interests are then provided and simulated.

IEEE Communications Letters•May 1, 2001•55 citations
We present a general version of the generalized minimum distance (GMD) decoding algorithm (see Forney, G.D., Jr, 1966) that accommodates different erasing strategies. This version is called reduced GMD decoding since, depending on the erasing strategy used, it can offer a reduction in complexity over Forney's GMD decoding. We apply reduced GMD decoding to concatenated codes. In particular, we study the error correction capability and the unsuccessful decoding probability of concatenated codes with reduced GMD decoding.
In this chapter, we continue the discussion on concatenated codes, which was initiated in Section 5.4. The main message to be conveyed in this chapter is that by using concatenation, one can obtain codes with favorable asymptotic performance—in a sense to be quantified more precisely—while the complexity of constructing these codes and decoding them grows polynomially with the code length. We first present a decoding algorithm for concatenated codes, due to Forney. This algorithm, referred to as a generalized minimum distance (in short, GMD) decoder, corrects any error pattern whose Hamming weight is less than half the product of the minimum distances of the inner and outer codes (we recall that this product is a lower bound on the minimum distance of the respective concatenated code). A GMD decoder consists of a nearest-codeword decoder for the inner code, and a combined error–erasure decoder for the outer code. It then enumerates over a threshold value, marking the output of the inner decoder as erasure if that decoder returns an inner codeword whose Hamming distance from the respective received sub-word equals or exceeds that threshold. We show that under our assumption on the overall Hamming weight of the error word, there is at least one threshold for which the outer decoder recovers the correct codeword. If the outer code is taken as a GRS code, then a GMD decoder has an implementation with time complexity that is at most quadratic in the length of the concatenated code.
The error-correction capability and the performance of generalized minimum distance decod- ing based on threshold erasing is studied as a function of the number of decoding trials and of the allowable reliability values. Generalized Minimum Distance (GMD) decoding, as intro- duced by Forney (l), is a multitrial decoding algorithm that combines reliability information, represented by numbers in the closed interval (0,1), with algebraic decoding algorithms for error correction. In each trial, a fixed number of the most unreliable symbols in the received sequence is erased. If a cer- tain distance criterion is satisfied, Forney has shown that the transmitted codeword can be retrieved in at most (d/2) trials, where d is the Hamming distance of the code. In this work, we study a variation on Forney's scheme where, in each trial, symbols whose reliabilities are below a certain threshold are erased, and hence there is no need to sort the received symbols according to reliability values be- fore erasing as in Forney's GMD decoding. Furthermore, we consider limiting the allowable reliability values to the set R, = u~=mo/2'{1 - 2i/m}, where m = 1,2,3,. . .. This covers the simple cases of taking only hard decisions (m = l), allow- ing erasures (m = 2), or accommodating the full range (0,1) of reliability values as in Forney's GMD decoding (m + 00). Limiting the reliability values may be of importance since, in any digital implementation, the reliability values need to be quantized. Moreover, in some applications, e.g., GMD decod- ing of concatenated codes over discrete channels, the reliabil- ity values are discrete in nature (2). The maximum number of trials is kept as a parameter. Limiting the reliability values and the number of trials leads to the concept of reduced GMD decoding.
For binary linear block codes, we introduce a multiple generalized minimum distance (GMD) decoding algorithm, where GMD-like decoding is iterated around a few appropriately selected search centers. Compared with the original GMD decoding by Forney (1966), this decoding algorithm provides better error performance by increasing the number of iterations of erasure and error correction moderately. To reduce the number of iterations, we derive new effective sufficient conditions on the optimality of decoded codewords.
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.