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

arXiv:2501.13021 · IEEE International Symposium on Information Theory (ISIT)

Extension of the Poltyrev Bound to Binary Memoryless Symmetric Channels

Tal Philosof, Ariel Doubchak, Amit Berman, Uri Erez

Published Jun 22, 2025• 0 citations
arXivHTMLPDF

Abstract

The Poltyrev bound provides a very tight upper bound on the decoding error probability when using binary linear codes for transmission over the binary symmetric channel and the additive white Gaussian noise channel, making use of the code's weight spectrum. In the present work, the bound is extended to symmetric binary-input memoryless channels with a discrete output alphabet. The derived bound is demonstrated on a hybrid BSC-BEC channel. Additionally, a reduced-complexity bound is introduced at the cost of some loss in tightness.

DOI
10.1109/isit63088.2025.11195432

Related papers

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

Estimates of the bit error probabilities for linear block codes and symmetric binary-input memoryless channels

Vladimir B. Balakirsky

A coset representation of the bit error probabilities for binary linear block codes and arbitrary symmetric memoryless channels is derived. Such a representation leads to simple upper bounds on the bit error probabilities for code components expressed via 2n code spectra, where n is the code length, and to a "bounded distance decoding" algorithm. The performance of the algorithm is illustrated for the (23,12) Golay code and a particular channel having non-binary output alphabet where it attains a sub-optimum performance.

IEEE Information Theory Workshop (ITW)•Aug 27, 2003•1 citation

On the Weight Spectrum of Good Linear Binary Codes

R. Liu, Predrag Spasojević, Emina Soljanin

The weight spectrum of sequences of binary linear codes that achieve arbitrarily small word error probability on a class of noisy channels at a nonzero rate is studied. We refer to such sequences as good codes. The class of good codes includes turbo, low-density parity-check, and repeat-accumulate codes. We show that a sequence of codes is good when transmitted over a memoryless binary-symmetric channel (BSC) or an additive white Gaussian noise (AWGN) channel if and only if the slope of its spectrum is finite everywhere and its minimum Hamming distance goes to infinity with no requirement on its rate growth. The extension of these results to code ensembles in probabilistic terms follows in a direct manner. We also show that the sufficient condition holds for any binary-input memoryless channel.

IEEE Transactions on Information Theory•Nov 22, 2005•10 citations

Parity-check density versus performance of binary linear block codes over memoryless symmetric channels

Igal Sason, Rudiger L. Urbanke

We derive lower bounds on the density of parity-check matrices of binary linear codes which are used over memoryless binary-input output-symmetric (MBIOS) channels. The bounds are expressed in terms of the gap between the rate of these codes for which reliable communications is achievable and the channel capacity; they are valid for every sequence of binary linear block codes if there exists a decoding algorithm under which the average bit-error probability vanishes. For every MBIOS channel, we construct a sequence of ensembles of regular low-density parity-check (LDPC) codes, so that an upper bound on the asymptotic density of their parity-check matrices scales similarly to the lower bound. The tightness of the lower bound is demonstrated for the binary erasure channel by analyzing a sequence of ensembles of right-regular LDPC codes which was introduced by Shokrollahi, and which is known to achieve the capacity of this channel. Under iterative message-passing decoding, we show that this sequence of ensembles is asymptotically optimal (in a sense to be defined in this paper), strengthening a result of Shokrollahi. Finally, we derive lower bounds on the bit-error probability and on the gap to capacity for binary linear block codes which are represented by bipartite graphs, and study their performance limitations over MBIOS channels. The latter bounds provide a quantitative measure for the number of cycles of bipartite graphs which represent good error-correction codes.

IEEE Transactions on Information Theory•Jun 23, 2003•121 citations

LP Decoding of Regular LDPC Codes in Memoryless Channels

Nissim Halabi, Guy Even

We study error bounds for linear programming decoding of regular LDPC codes. For memoryless binary-input output-symmetric channels, we prove bounds on the word error probability that are inverse doubly-exponential in the girth of the factor graph. For memoryless binary-input AWGN channel, we prove lower bounds on the threshold for regular LDPC codes whose factor graphs have logarithmic girth under LP-decoding. Specifically, we prove a lower bound of $σ=0.735$ (upper bound of $\frac{Eb}{N_0}=2.67$dB) on the threshold of $(3,6)$-regular LDPC codes whose factor graphs have logarithmic girth. Our proof is an extension of a recent paper of Arora, Daskalakis, and Steurer [STOC 2009] who presented a novel probabilistic analysis of LP decoding over a binary symmetric channel. Their analysis is based on the primal LP representation and has an explicit connection to message passing algorithms. We extend this analysis to any MBIOS channel.

arXiv:1002.3117•Feb 16, 2010•0 citations

LP decoding of regular LDPC codes in memoryless channels

Nissim Halabi, Guy Even

We study error bounds for linear programming decoding of regular LDPC codes. For memoryless binary-input output-symmetric channels, we prove bounds on the word error probability that are inverse doubly-exponential in the girth of the factor graph. For memoryless binary-input AWGN channels, we derive lower bounds on the thresholds for regular LDPC codes under LP decoding. Specifically, we prove a lower bound of σ = 0.735 on the threshold of (3, 6)-regular LDPC codes with logarithmic girth.

IEEE International Symposium on Information Theory (ISIT)•Jun 1, 2010•6 citations
The Poltyrev bound provides a very tight upper bound on the decoding error probability when using binary linear codes for transmission over the binary symmetric channel and the additive white Gaussian noise channel, making use of the code's weight spectrum. In the present work, the bound is extended to symmetric binary-input memoryless channels with a discrete output alphabet. The derived bound is demonstrated on a hybrid BSC-BEC channel. Additionally, a reduced-complexity bound is introduced at the cost of some loss in tightness.
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.
A coset representation of the bit error probabilities for binary linear block codes and arbitrary symmetric memoryless channels is derived. Such a representation leads to simple upper bounds on the bit error probabilities for code components expressed via 2n code spectra, where n is the code length, and to a "bounded distance decoding" algorithm. The performance of the algorithm is illustrated for the (23,12) Golay code and a particular channel having non-binary output alphabet where it attains a sub-optimum performance.
The weight spectrum of sequences of binary linear codes that achieve arbitrarily small word error probability on a class of noisy channels at a nonzero rate is studied. We refer to such sequences as good codes. The class of good codes includes turbo, low-density parity-check, and repeat-accumulate codes. We show that a sequence of codes is good when transmitted over a memoryless binary-symmetric channel (BSC) or an additive white Gaussian noise (AWGN) channel if and only if the slope of its spectrum is finite everywhere and its minimum Hamming distance goes to infinity with no requirement on its rate growth. The extension of these results to code ensembles in probabilistic terms follows in a direct manner. We also show that the sufficient condition holds for any binary-input memoryless channel.
We derive lower bounds on the density of parity-check matrices of binary linear codes which are used over memoryless binary-input output-symmetric (MBIOS) channels. The bounds are expressed in terms of the gap between the rate of these codes for which reliable communications is achievable and the channel capacity; they are valid for every sequence of binary linear block codes if there exists a decoding algorithm under which the average bit-error probability vanishes. For every MBIOS channel, we construct a sequence of ensembles of regular low-density parity-check (LDPC) codes, so that an upper bound on the asymptotic density of their parity-check matrices scales similarly to the lower bound. The tightness of the lower bound is demonstrated for the binary erasure channel by analyzing a sequence of ensembles of right-regular LDPC codes which was introduced by Shokrollahi, and which is known to achieve the capacity of this channel. Under iterative message-passing decoding, we show that this sequence of ensembles is asymptotically optimal (in a sense to be defined in this paper), strengthening a result of Shokrollahi. Finally, we derive lower bounds on the bit-error probability and on the gap to capacity for binary linear block codes which are represented by bipartite graphs, and study their performance limitations over MBIOS channels. The latter bounds provide a quantitative measure for the number of cycles of bipartite graphs which represent good error-correction codes.
We study error bounds for linear programming decoding of regular LDPC codes. For memoryless binary-input output-symmetric channels, we prove bounds on the word error probability that are inverse doubly-exponential in the girth of the factor graph. For memoryless binary-input AWGN channel, we prove lower bounds on the threshold for regular LDPC codes whose factor graphs have logarithmic girth under LP-decoding. Specifically, we prove a lower bound of σ=0.735σ=0.735σ=0.735 (upper bound of EbN0=2.67\frac{Eb}{N_0}=2.67N0​Eb​=2.67dB) on the threshold of (3,6)(3,6)(3,6)-regular LDPC codes whose factor graphs have logarithmic girth. Our proof is an extension of a recent paper of Arora, Daskalakis, and Steurer [STOC 2009] who presented a novel probabilistic analysis of LP decoding over a binary symmetric channel. Their analysis is based on the primal LP representation and has an explicit connection to message passing algorithms. We extend this analysis to any MBIOS channel.