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

IEEE International Symposium on Information Theory (ISIT)

Generalized minimum-distance decoding in Euclidean-space: performance analysis

D. Agrawal, A. Vardy

Published Nov 22, 2002• 1 citation
Publisher

Abstract

Detailed geometric analysis of decoding regions for GMD decoding is presented. We show that GMD decoding regions are non-convex in essentially all cases of interest. We also prove that these regions are always bounded by hyperplane segments. For d-erasure GMD decoding, we establish the presence of a large number of bounding hyperplanes at distance /spl les/d+1. These results invalidate the estimates of performance derived from the union bound in the case of (multistage) GMD decoding. Alternative probabilistic estimates of, and upper bounds upon, the performance of GMD decoding are developed. Simulation results, for both low-dimensional and high-dimensional sphere packings, are in remarkably close agreement with our probabilistic approximations.

DOI
10.1109/isit.1997.613230

Related papers

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

Geometrical and performance analysis of GMD and Chase decoding algorithms

Eran Fishler, Ofer Amrani, Yair Be'ery

The overall number of nearest neighbors in bounded distance decoding (BDD) algorithms is given by N/sub 0,eff/=N/sub 0/+N/sub BDD/. Where NBDD denotes the number of additional, non-codeword, neighbors that are generated during the (suboptimal) decoding process. We identify and enumerate the nearest neighbors associated with the original generalized minimum distance (GMD) and Chase (1972) decoding algorithms. After careful examination of the decision regions of these algorithms, we derive an approximated probability ratio between the error contribution of a noncodeword neighbor (one of N/sub BDD/ points) and a codeword nearest neighbor. For Chase algorithm 1 it is shown that the contribution to the error probability of a noncodeword nearest neighbor is a factor of 2/sup d-1/ less than the contribution of a codeword, while for Chase algorithm 2 the factor is 2/sup [d/2]-1/, d being the minimum Hamming distance of the code. For Chase algorithm 3 and GMD, a recursive procedure for calculating this ratio, which turns out to be nonexponential in d, is presented. This procedure can also be used for specifically identifying the error patterns associated with Chase algorithm 3 and GMD. Utilizing the probability ratio, we propose an improved approximated upper bound on the probability of error based on the union bound approach. Simulation results are given to demonstrate and support the analytical derivations.

IEEE Transactions on Information Theory•Jul 1, 1999•10 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

Chase-type and GMD coset decodings

M.P.C. Fossorier, Shu Lin

In this letter, Chase decoding algorithms are generalized into a family of bounded distance decoding algorithms, so that the conventional Chase algorithm-2 and Chase algorithm-3 become the two extremes of this family. Consequently, more flexibility in the tradeoffs between error performance and decoding complexity is provided by this generalization, especially for codes with large minimum distance. Finally this approach is extended to decoding with erasures.

IEEE Transactions on Communications•Mar 1, 2000•31 citations
Detailed geometric analysis of decoding regions for GMD decoding is presented. We show that GMD decoding regions are non-convex in essentially all cases of interest. We also prove that these regions are always bounded by hyperplane segments. For d-erasure GMD decoding, we establish the presence of a large number of bounding hyperplanes at distance /spl les/d+1. These results invalidate the estimates of performance derived from the union bound in the case of (multistage) GMD decoding. Alternative probabilistic estimates of, and upper bounds upon, the performance of GMD decoding are developed. Simulation results, for both low-dimensional and high-dimensional sphere packings, are in remarkably close agreement with our probabilistic approximations.
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.
The overall number of nearest neighbors in bounded distance decoding (BDD) algorithms is given by N/sub 0,eff/=N/sub 0/+N/sub BDD/. Where NBDD denotes the number of additional, non-codeword, neighbors that are generated during the (suboptimal) decoding process. We identify and enumerate the nearest neighbors associated with the original generalized minimum distance (GMD) and Chase (1972) decoding algorithms. After careful examination of the decision regions of these algorithms, we derive an approximated probability ratio between the error contribution of a noncodeword neighbor (one of N/sub BDD/ points) and a codeword nearest neighbor. For Chase algorithm 1 it is shown that the contribution to the error probability of a noncodeword nearest neighbor is a factor of 2/sup d-1/ less than the contribution of a codeword, while for Chase algorithm 2 the factor is 2/sup [d/2]-1/, d being the minimum Hamming distance of the code. For Chase algorithm 3 and GMD, a recursive procedure for calculating this ratio, which turns out to be nonexponential in d, is presented. This procedure can also be used for specifically identifying the error patterns associated with Chase algorithm 3 and GMD. Utilizing the probability ratio, we propose an improved approximated upper bound on the probability of error based on the union bound approach. Simulation results are given to demonstrate and support the analytical derivations.
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.