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

International Conference on Communications

Tangential Sphere Bounds on the Ensemble Performance of ML Decoded Gallager Codes via Their Exact Ensemble Distance Spectrum

Sheng Tong

Published Jan 1, 2008• 8 citations
Publisher

Abstract

An efficient numerical approach to the exact ensemble distance spectrum of Gallager codes has been developed by evaluating powers of polynomials. With the exact ensemble distance spectrum of Gallager codes, tangential sphere upper bounds on their maximum likelihood (ML) decoding performance over binary input AWGN channels are investigated. Numerical results indicate improved bounds have been obtained, better than Sason and Shamai's results (which are based on Gallager's upper bound on the ensemble distance spectrum), especially in the error floor region. Furthermore, some critical properties of Gallager codes, including typical minimum distance and the performance tradeoff in the waterfall and error floor regions, have been considered.

DOI
10.1109/icc.2008.224

Related papers

On the Error Exponents of Improved Tangential Sphere Bounds

Moshe Twitto, Igal Sason

The performance of maximum-likelihood (ML) decoded binary linear block codes over the additive white Gaussian noise (AWGN) channel is addressed via the tangential sphere bound (TSB) and two of its recent improved versions. The correspondence is focused on the derivation of the error exponents of these bounds. Although it was shown that some recent improvements of the TSB tighten this bound for finite-length codes, it is demonstrated in this correspondence 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

arXiv:cs/0607004•IEEE Transactions on Information Theory•Mar 1, 2007•13 citations

On the Error Exponents of Improved Tangential-Sphere Bounds

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.

IEEE Convention of Electrical and Electronics Engineers in Israel•Nov 1, 2006•0 citations

A New Upper Bound on the ML DecodingError Probability of Linear Binary Block Codes in AWGN Interference

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.

IEEE Transactions on Information Theory•Nov 30, 2004•44 citations

Gallager bounds for linear codes in binary-input output-symmetric memoryless channels

Alfonso García Martínez, Albert Guillén i Fàbregas, Giuseppe Caire

This paper presents a general methodology to extend Gallager bounds on the maximum-likelihood decoding error probability to arbitrary binary-input output-symmetric memoryless channels. Based on the log-likelihood ratios, a new space is constructed in which the signals naturally lie on a sphere, and for which geometric analysis is straightforward. In particular, we focus on Poltyrev's tangential-sphere bound, and we illustrate its connections with the Engdahl-Zigangirov bound. Approximations to these bounds are shown to be very tight.

IEEE International Symposium on Information Theory (ISIT)•Jan 1, 2005•0 citations

Performance Analysis of Linear Codes under Maximum-Likelihood Decoding: A Tutorial

Igal Sason, Shlomo Shitz Shamai

Performance Analysis of Linear Codes under Maximum-Likelihood Decoding: A Tutorial focuses on the performance evaluation of linear codes under optimal maximum-likelihood (ML) decoding. Though the ML decoding algorithm is prohibitively complex for most practical codes, their performance analysis under ML decoding allows to predict their performance without resorting to computer simulations. It also provides a benchmark for testing the sub-optimality of iterative (or other practical) decoding algorithms. This analysis also establishes the goodness of linear codes (or ensembles), determined by the gap between their achievable rates under optimal ML decoding and information theoretical limits. In Performance Analysis of Linear Codes under Maximum-Likelihood Decoding: A Tutorial, upper and lower bounds on the error probability of linear codes under ML decoding are surveyed and applied to codes and ensembles of codes on graphs. For upper bounds, we discuss various bounds where focus is put on Gallager bounding techniques and their relation to a variety of other reported bounds. Within the class of lower bounds, we address de Caen's based bounds and their improvements, and also consider sphere-packing bounds with their recent improvements targeting codes of moderate block lengths. Performance Analysis of Linear Codes under Maximum-Likelihood Decoding: A Tutorial is a comprehensive introduction to this important topic for students, practitioners and researchers working in communications and information theory.

now publishers, Inc. eBooks•Jan 1, 2006•172 citations

Performance of ML decoding for ensembles of binary and nonbinary regular LDPC codes of finite lengths

Irina E. Bocharova, Boris D. Kudryashov, Vitaly Skachek

The Gallager ensembles of binary regular LDPC codes and binary images of nonbinary regular LDPC codes are studied. Recurrent procedure for computing average spectra for these two ensembles is presented. By using the existing bounding techniques, estimates on the error probability of the maximum-likelihood (ML) decoding over an AWGN channel with BPSK signaling for short codes from different ensembles of LDPC codes are obtained. The numerical results show performance of the ML decoding for different code ensembles. Conclusions drawn based on the average code spectra are then verified by near-ML decoding simulations for both randomly selected and the best known short codes. The asymptotic ML decoding thresholds for AWGN and BSC channels are calculated. As expected, codes with the ML decoding performance superior to that of the average code in the ensemble, are easy to find. However, comparison of the the presented results with simulation results for belief propagation (BP) decoding shows that the ML decoding performance should not be used as a target for searching for good iteratively decodable codes.

IEEE International Symposium on Information Theory (ISIT)•Jun 1, 2017•9 citations
An efficient numerical approach to the exact ensemble distance spectrum of Gallager codes has been developed by evaluating powers of polynomials. With the exact ensemble distance spectrum of Gallager codes, tangential sphere upper bounds on their maximum likelihood (ML) decoding performance over binary input AWGN channels are investigated. Numerical results indicate improved bounds have been obtained, better than Sason and Shamai's results (which are based on Gallager's upper bound on the ensemble distance spectrum), especially in the error floor region. Furthermore, some critical properties of Gallager codes, including typical minimum distance and the performance tradeoff in the waterfall and error floor regions, have been considered.
The performance of maximum-likelihood (ML) decoded binary linear block codes over the additive white Gaussian noise (AWGN) channel is addressed via the tangential sphere bound (TSB) and two of its recent improved versions. The correspondence is focused on the derivation of the error exponents of these bounds. Although it was shown that some recent improvements of the TSB tighten this bound for finite-length codes, it is demonstrated in this correspondence 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
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.
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.
This paper presents a general methodology to extend Gallager bounds on the maximum-likelihood decoding error probability to arbitrary binary-input output-symmetric memoryless channels. Based on the log-likelihood ratios, a new space is constructed in which the signals naturally lie on a sphere, and for which geometric analysis is straightforward. In particular, we focus on Poltyrev's tangential-sphere bound, and we illustrate its connections with the Engdahl-Zigangirov bound. Approximations to these bounds are shown to be very tight.
Performance Analysis of Linear Codes under Maximum-Likelihood Decoding: A Tutorial focuses on the performance evaluation of linear codes under optimal maximum-likelihood (ML) decoding. Though the ML decoding algorithm is prohibitively complex for most practical codes, their performance analysis under ML decoding allows to predict their performance without resorting to computer simulations. It also provides a benchmark for testing the sub-optimality of iterative (or other practical) decoding algorithms. This analysis also establishes the goodness of linear codes (or ensembles), determined by the gap between their achievable rates under optimal ML decoding and information theoretical limits. In Performance Analysis of Linear Codes under Maximum-Likelihood Decoding: A Tutorial, upper and lower bounds on the error probability of linear codes under ML decoding are surveyed and applied to codes and ensembles of codes on graphs. For upper bounds, we discuss various bounds where focus is put on Gallager bounding techniques and their relation to a variety of other reported bounds. Within the class of lower bounds, we address de Caen's based bounds and their improvements, and also consider sphere-packing bounds with their recent improvements targeting codes of moderate block lengths. Performance Analysis of Linear Codes under Maximum-Likelihood Decoding: A Tutorial is a comprehensive introduction to this important topic for students, practitioners and researchers working in communications and information theory.
The Gallager ensembles of binary regular LDPC codes and binary images of nonbinary regular LDPC codes are studied. Recurrent procedure for computing average spectra for these two ensembles is presented. By using the existing bounding techniques, estimates on the error probability of the maximum-likelihood (ML) decoding over an AWGN channel with BPSK signaling for short codes from different ensembles of LDPC codes are obtained. The numerical results show performance of the ML decoding for different code ensembles. Conclusions drawn based on the average code spectra are then verified by near-ML decoding simulations for both randomly selected and the best known short codes. The asymptotic ML decoding thresholds for AWGN and BSC channels are calculated. As expected, codes with the ML decoding performance superior to that of the average code in the ensemble, are easy to find. However, comparison of the the presented results with simulation results for belief propagation (BP) decoding shows that the ML decoding performance should not be used as a target for searching for good iteratively decodable codes.