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

Wave Electronics and its Application in Information and Telecommunication Systems (WECONF)

To the Question of Almost Maximum-Likelihood Decoding

Mikhail Afanasev, Andrei A. Ovchinnikov

Published Jun 1, 2020• 1 citation
Publisher

Abstract

Evseev’s lemma claims that if we use the decoding by a standard array and use coset leaders having the weight not greater than Gilbert-Varshamov distance then the probability of error decoding will become not greater than the probability of error decoding of maximum-likelihood multiplied by two. However, the estimation of tightness of this bound is an open problem. In this work we perform the estimation of the accuracy of Evseev’s lemma on the example of several linear random codes by simulating them in a binary-symmetric channel.

DOI
10.1109/weconf48837.2020.9131476

Related papers

On the complete decoding of binary linear codes (Corresp.)

Michele Elia, G. Prati

Complete decoding of systematic linear block codes by standard arrays with coset leaders not necessarily of minimal weight gives, in several interesting cases on the binary symmetric channel with error probabilityp, a smaller symbol error probability than decoding using the coset leaders of minimum weight. The proposed choice of the coset leaders allows for the classes of uniformly packed and nearly perfect binary codes to achieve a lower information bit error probability, at least forpsufficiently near zero.

IEEE Transactions on Information Theory•Jul 1, 1985•8 citations

Bounds on the maximum-likelihood decoding error probability of low-density parity-check codes

G. Miller, David Burshtein

We derive both upper and lower bounds on the decoding error probability of maximum-likelihood (ML) decoded low-density parity-check (LDPC) codes. The results hold for any binary-input symmetric-output channel. Our results indicate that for various appropriately chosen ensembles of LDPC codes, reliable communication is possible up to channel capacity. However, the ensemble averaged decoding error probability decreases polynomially, and not exponentially. The lower and upper bounds coincide asymptotically, thus showing the tightness of the bounds. However, for ensembles with suitably chosen parameters, the error probability of almost all codes is exponentially decreasing, with an error exponent that can be set arbitrarily close to the standard random coding exponent.

IEEE Transactions on Information Theory•Jan 1, 2001•157 citations

A lower bound on the probability of decoding error over a BSC channel

Osnat Keren, Simon N. Litsyn

For a code C of length n and size |C, we estimate the error probability of the maximum likelihood decoding. In this paper we address this problem for the binary symmetric channel (BSC) defined by its transition probability p. We discuss the case when we know the distance distribution of the code. We also assume that the code is regular in the sense that the distribution of the distances from a codeword to other codewords does not depend on the choice of the initial codeword.

IEEE Convention of Electrical and Electronics Engineers in Israel•Nov 11, 2002•7 citations

On the asymptotic accuracy of the union bound

Alexander Barg

A new lower bound on the error probability of maximum likelihood decoding of a binary code on a binary symmetric channel was proved in Barg and McGregor (2004, cs.IT/0407011). It was observed in that paper that this bound leads to a new region of code rates in which the random coding exponent is asymptotically tight, giving a new region in which the reliability of the BSC is known exactly. The present paper explains the relation of these results to the union bound on the error probability.

arXiv:cs/0412111•Dec 24, 2004•3 citations

Maximum Likelihood Decoding of Codes on the Z-channel

Ángela I. Barbero, Pål Gunnar Ellingsen, Susanna Spinsante +1 more

The aim of this paper is to extend some basic concepts related to the Maximum Likelihood decoding of codes on the Z-channel, which is a particular, but very important, example of an asymmetric channel. We study distance properties of linear codes over the Z-channel, in order to define a suitable metric for the implementation of a Maximum Likelihood decoder on the channel. A combinatorial expression for an approximation on the probability of incorrect Maximum Likelihood decoding is also provided, and comparisons are given to evaluate the tightness of the estimation, when a Hamming code, a Turbo code and an LDPC code are used for communicating over the Z-channel.

International Conference on Communications•Jan 1, 2006•5 citations

LDPC Codes Over the BEC: Bounds and Decoding Algorithms

Irina E. Bocharova, Boris D. Kudryashov, Vitaly Skachek +2 more

The performance of maximum-likelihood (ML) decoding on the binary erasure channel for finite-length low-density parity-check (LDPC) codes from two random ensembles is studied. A tightened union-type upper bound on the ML decoding error probability based on the precise coefficients of the average weight spectrum is presented. For LDPC codes from the Gallager ensemble and the Richardson-Urbanke ensemble, new upper bounds on the ML decoding performance based on computing the rank of submatrices of the code parity-check matrix are derived. A new lower bound on the ML decoding threshold followed from the latter error probability bound is obtained. An improved lower bound on the error probability for codes with a known estimate on the minimum distance is presented as well. A new low-complexity near-ML decoding algorithm for quasi-cyclic LDPC codes is proposed and simulated. Its performance is compared to the simulated belief propagation and ML decoding performance and simulated performance of the best known improved iterative decoding techniques, as well as, with the derived upper bounds on the ML decoding performance and with decoding thresholds obtained by the density evolution technique.

IEEE Transactions on Communications•Nov 6, 2018•5 citations
Evseev’s lemma claims that if we use the decoding by a standard array and use coset leaders having the weight not greater than Gilbert-Varshamov distance then the probability of error decoding will become not greater than the probability of error decoding of maximum-likelihood multiplied by two. However, the estimation of tightness of this bound is an open problem. In this work we perform the estimation of the accuracy of Evseev’s lemma on the example of several linear random codes by simulating them in a binary-symmetric channel.
Complete decoding of systematic linear block codes by standard arrays with coset leaders not necessarily of minimal weight gives, in several interesting cases on the binary symmetric channel with error probabilityp, a smaller symbol error probability than decoding using the coset leaders of minimum weight. The proposed choice of the coset leaders allows for the classes of uniformly packed and nearly perfect binary codes to achieve a lower information bit error probability, at least forpsufficiently near zero.
We derive both upper and lower bounds on the decoding error probability of maximum-likelihood (ML) decoded low-density parity-check (LDPC) codes. The results hold for any binary-input symmetric-output channel. Our results indicate that for various appropriately chosen ensembles of LDPC codes, reliable communication is possible up to channel capacity. However, the ensemble averaged decoding error probability decreases polynomially, and not exponentially. The lower and upper bounds coincide asymptotically, thus showing the tightness of the bounds. However, for ensembles with suitably chosen parameters, the error probability of almost all codes is exponentially decreasing, with an error exponent that can be set arbitrarily close to the standard random coding exponent.
The aim of this paper is to extend some basic concepts related to the Maximum Likelihood decoding of codes on the Z-channel, which is a particular, but very important, example of an asymmetric channel. We study distance properties of linear codes over the Z-channel, in order to define a suitable metric for the implementation of a Maximum Likelihood decoder on the channel. A combinatorial expression for an approximation on the probability of incorrect Maximum Likelihood decoding is also provided, and comparisons are given to evaluate the tightness of the estimation, when a Hamming code, a Turbo code and an LDPC code are used for communicating over the Z-channel.
The performance of maximum-likelihood (ML) decoding on the binary erasure channel for finite-length low-density parity-check (LDPC) codes from two random ensembles is studied. A tightened union-type upper bound on the ML decoding error probability based on the precise coefficients of the average weight spectrum is presented. For LDPC codes from the Gallager ensemble and the Richardson-Urbanke ensemble, new upper bounds on the ML decoding performance based on computing the rank of submatrices of the code parity-check matrix are derived. A new lower bound on the ML decoding threshold followed from the latter error probability bound is obtained. An improved lower bound on the error probability for codes with a known estimate on the minimum distance is presented as well. A new low-complexity near-ML decoding algorithm for quasi-cyclic LDPC codes is proposed and simulated. Its performance is compared to the simulated belief propagation and ML decoding performance and simulated performance of the best known improved iterative decoding techniques, as well as, with the derived upper bounds on the ML decoding performance and with decoding thresholds obtained by the density evolution technique.