© 2026 Aqora Quantum S.A.S.

Terms Privacy Legal Notice

with Threshold Erasing

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

Published Jan 1, 2001• 0 citations

Abstract

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.

Related papers

Reduced GMD decoding of concatenated codes

Jos H. Weber, Khaled Abdel-Ghaffar

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.

Globecom•Nov 13, 2002•0 citations

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

clidean-Space e inimurn-Distance Decodi

G. David Forney

It is shown that multistage generalized minimum- distance (GMD) decoding of Euclidean-space codes and lattices can provide an excellent tradeoff between performance and com- plexity. We introduce a reliability metric for Gaussian channels that is easily computed from an inner product, and prove that a multistage GMD decoder using this metric is a bounded- distance decoder up to the true packing radius. The effective error coefficient of multistage GMD decoding is determined. Two simple modifications in the GMD decoding algorithm that drastically reduce this error coefficient are proposed. It is shown that with these modifications GMD decoding achieves the error coefficient of maximum-likelihood decoding for block codes and for generalized Construction A lattices. Multistage GMD decod- ing of the lattices Dg, Ea, K12, BW16, and A24 is investigated in detail. For 1<12,BW~, and A24, the GMD decoders have considerably lower complexity than the best known maximum- likelihood or bounded-distance decoding algorithms, and appear to be the most practically attractive decoders available. For high-dimensional codes and lattices (2 64 dimensions) maximum- likelihood decoding becomes infeasible, while GMD decoding algorithms remain quite practical. As an example, we devise a multistage GMD decoder for a 128-dimensional sphere packing with a nominal coding gain of 8.98 dB that attains an effective error coefficient of 1 365 760. This decoder requires only about 400 real operations, in addition to algebraic errors-and-erasures decoding of certain BCH and Hamming codes. It therefore ap- pears to be practically feasible to implement algebraic multistage GMD decoders for high-dimensional sphere packings, and thus achieve high effective coding gains.

•Jan 1, 1996•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•2 citations

An Algorithm For Soft Decoding Of Block Codes

Jan Nilsson

A well known soft decoding algorithm that can make use of algebraic decoding techniques is the GMD algorithm introduced by Forney. This algorithm is based on several error-erasure decoding trails where unreliable positions are successively erased. Chase proposed a closely related family of algorithms for binary codes where unreliable positions are switched', i.e. different estimates for the positions are used in intermediate steps during the decoding process. In our algorithm, suitable for non binary codes, we try to combine erasures and switchings in a favourable way. A version of the algorithm comparable in complexity with the GMD algorithm is investigated. Simulations show that our algorithm in many cases has a somewhat better error correcting capability then the GMD algorithm.

IEEE International Symposium on Information Theory (ISIT)•Aug 24, 2005•1 citation

Optimal thresholds for GMD decoding with ℓ+1 over ℓ-extended Bounded Distance decoders

Christian Senger, Vladimir R. Sidorenko, Martin Bossert +1 more

We investigate threshold-based multi-trial decoding of concatenated codes with an inner Maximum-Likelihood decoder and an outer error/erasure ℓ+1/ℓ-extended Bounded Distance decoder, i.e. a decoder which corrects ε errors and τ erasures if ℓ+1/ ℓε+τ≤ do-1, where dois the minimum distance of the outer code and ℓ ∈ ℕ\{0}. This is a generalization of Forney's GMD decoding, which was considered only for ℓ = 1, i.e. outer Bounded Minimum Distance decoding. One important example for ℓ+1/ℓ-extended Bounded Distance decoders is decoding of ℓ-Interleaved Reed-Solomon codes. Our main contribution is a threshold location formula, which allows to optimally erase unreliable inner decoding results, for a given number of decoding trials and parameter ℓ. Thereby, the term optimal means that the residual codeword error probability of the concatenated code is minimized. We give an estimation of this probability for any number of decoding trials.

arXiv:1001.1106•IEEE International Symposium on Information Theory (ISIT)•Jun 1, 2010•4 citations

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.

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.

It is shown that multistage generalized minimum- distance (GMD) decoding of Euclidean-space codes and lattices can provide an excellent tradeoff between performance and com- plexity. We introduce a reliability metric for Gaussian channels that is easily computed from an inner product, and prove that a multistage GMD decoder using this metric is a bounded- distance decoder up to the true packing radius. The effective error coefficient of multistage GMD decoding is determined. Two simple modifications in the GMD decoding algorithm that drastically reduce this error coefficient are proposed. It is shown that with these modifications GMD decoding achieves the error coefficient of maximum-likelihood decoding for block codes and for generalized Construction A lattices. Multistage GMD decod- ing of the lattices Dg, Ea, K12, BW16, and A24 is investigated in detail. For 1<12,BW~, and A24, the GMD decoders have considerably lower complexity than the best known maximum- likelihood or bounded-distance decoding algorithms, and appear to be the most practically attractive decoders available. For high-dimensional codes and lattices (2 64 dimensions) maximum- likelihood decoding becomes infeasible, while GMD decoding algorithms remain quite practical. As an example, we devise a multistage GMD decoder for a 128-dimensional sphere packing with a nominal coding gain of 8.98 dB that attains an effective error coefficient of 1 365 760. This decoder requires only about 400 real operations, in addition to algebraic errors-and-erasures decoding of certain BCH and Hamming codes. It therefore ap- pears to be practically feasible to implement algebraic multistage GMD decoders for high-dimensional sphere packings, and thus achieve high effective coding gains.

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.

A well known soft decoding algorithm that can make use of algebraic decoding techniques is the GMD algorithm introduced by Forney. This algorithm is based on several error-erasure decoding trails where unreliable positions are successively erased. Chase proposed a closely related family of algorithms for binary codes where unreliable positions are switched', i.e. different estimates for the positions are used in intermediate steps during the decoding process. In our algorithm, suitable for non binary codes, we try to combine erasures and switchings in a favourable way. A version of the algorithm comparable in complexity with the GMD algorithm is investigated. Simulations show that our algorithm in many cases has a somewhat better error correcting capability then the GMD algorithm.

We investigate threshold-based multi-trial decoding of concatenated codes with an inner Maximum-Likelihood decoder and an outer error/erasure ℓ+1/ℓ-extended Bounded Distance decoder, i.e. a decoder which corrects ε errors and τ erasures if ℓ+1/ ℓε+τ≤ do-1, where dois the minimum distance of the outer code and ℓ ∈ ℕ\{0}. This is a generalization of Forney's GMD decoding, which was considered only for ℓ = 1, i.e. outer Bounded Minimum Distance decoding. One important example for ℓ+1/ℓ-extended Bounded Distance decoders is decoding of ℓ-Interleaved Reed-Solomon codes. Our main contribution is a threshold location formula, which allows to optimally erase unreliable inner decoding results, for a given number of decoding trials and parameter ℓ. Thereby, the term optimal means that the residual codeword error probability of the concatenated code is minimized. We give an estimation of this probability for any number of decoding trials.