Tightened Upper Bounds on the ML Decoding Error Probability of Binary Linear Block Codes and Applications

Mingoo Kim, Jae Hong Lee

Shahram Yousefi, Amir Keyvan Khandani

Performance evaluation of maximum-likelihood (ML) soft-decision-decoded binary block codes is usually carried out using bounding techniques. Many tight upper bounds on the error probability of binary codes are based on the so-called Gallager's first bounding technique (GFBT). The tangential sphere bound (TSB) of Poltyrev which has been believed for many years to offer the tightest bound developed for binary block codes is an example. Within the framework of the TSB and GFBT, we apply a new method referred to as the "added-hyper-plane" (AHP) technique, to the decomposition of the error probability. This results in a bound developed upon the application of two stages of the GFBT with two different Gallager regions culminating in a tightened upper bound beyond the TSB. The proposed bound is simple and only requires the spectrum of the binary code.

Marco Frego

Tadao Kasami, Shu Lin, Torleiv Kløve

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.

Moshe Twitto, Igal Sason

The performance of maximum-likelihood (ML) decoded binary linear block codes over the AWGN channel is addressed via the tangential-sphere bound (TSB) and two of its recent improved versions. Although it was exemplified that some recent improvements of the TSB tighten this bound for finite-length codes, it is demonstrated in this paper that their error exponents coincide. For an arbitrary ensemble of binary linear block codes, the common value of these error exponents is explicitly expressed in terms of the asymptotic growth rate of the average distance spectrum.