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 Transactions on Information Theory

Improved Bounds on the Word Error Probability of $RA(2)$ Codes With Linear-Programming-Based Decoding

Nissim Halabi, Guy Even

Published Jan 1, 2005• 20 citations
Publisher

Abstract

This paper deals with the linear-programming-based decoding algorithm of Feldman and Karger for repeat-accumulate "turbo-like" codes. We present a new structural characterization that captures the event that decoding fails. Based on this structural characterization, we develop polynomial algorithms that, given an RA(2) code, compute upper and lower bounds on the word error probability P/sub w/ for the binary-symmetric and the additive white Gaussian noise (AWGN) channels. Our experiments with an implementation of these algorithms for bounding P/sub w/ demonstrate in many interesting cases an improvement in the upper bound on the word error probability by a factor of over 1000 compared to the bounds by Feldman et al.. The experiments also indicate that the improvement in upper bound increases as the codeword length increases and the channel noise decreases. The computed lower bounds on the word error probability in our experiments are roughly ten times smaller than the upper bound.

DOI
10.1109/tit.2004.839509

Related papers

Error bounds for repeat-accumulate codes decoded via linear programming

Idan Goldenberg, David Burshtein

We examine regular and irregular repeat-accumulate (RA) codes with repetition degrees which are all even. For these codes and with a particular choice of an interleaver, we give an upper bound on the decoding error probability of a linear-programming based decoder which is an inverse polynomial in the block length. Our bound is valid for any memoryless, binary-input, output-symmetric (MBIOS) channel. This result generalizes the bound derived by Feldman et al., which was for regular RA(2) codes.

International Symposium on Turbo Codes and Iterative Information Processing•Sep 1, 2010•4 citations

Error Bounds for Repeat-Accumulate Codes Decoded via Linear Programming

Idan Goldenberg, David Burshtein

We examine regular and irregular repeat-accumulate (RA) codes with repetition degrees which are all even. For these codes and with a particular choice of an interleaver, we give an upper bound on the decoding error probability of a linear-programming based decoder which is an inverse polynomial in the block length. Our bound is valid for any memoryless, binary-input, output-symmetric (MBIOS) channel. This result generalizes the bound derived by Feldman et al., which was for regular RA(2) codes.

arXiv:0904.1692•Apr 10, 2009•2 citations

Error bounds for repeat-accumulate codes decoded via linear programming

Idan Goldenberg, David Burshtein

We examine regular and irregular repeat-accumulate (RA) codes with repetition degrees which are all even. For these codes and with a particular choice of an interleaver, we give an upper bound on the decoding error probability of a linear-programming based decoder which is an inverse polynomial in the block length. Our bound is valid for any memoryless, binary-input, output-symmetric (MBIOS) channel. This result generalizes the bound derived by Feldman et al., which was for regular RA($2$) codes.

Advances in Mathematics of Communications•Jan 1, 2011•7 citations

Decoding turbo-like codes via linear programming

J. Feldman, David Ron Karger

We introduce a novel algorithm for decoding turbo-like codes based on linear programming. We prove that for the case of repeat-accumulate (RA) codes, under the binary symmetric channel with a certain constant threshold bound on the noise, the error probability of our algorithm is bounded by an inverse polynomial in the code length. Our linear program (LP) minimizes the distance between the received bits and binary variables representing the code bits. Our LP is based on a representation of the code where code words are paths through a graph. Consequently, the LP bears a strong resemblance to the min-cost flow LP. The error bounds are based on an analysis of the probability, over the random noise of the channel, that the optimum solution to the LP is the path corresponding to the original transmitted code word.

Annual Symposium on Foundations of Computer Science•Jun 26, 2003•22 citations

Bounds on Error-Correction Coding Performance

Martin Tomlinson, Cen Jung Tjhai, Marcel Ambroze +2 more

The theoretical performance of binary codes for the additive white Gaussian noise (AWGN) channel is discussed. In particular, Gallager’s coding theorem for binary codes is treated extensively. By assuming a binomial weight distribution for linear codes, it is shown that the decoder error probability performance of some of the best, known linear, binary codes is the same as the average performance of the ensemble of all randomly chosen, binary nonlinear codes having the same length and dimension. Assuming a binomial weight distribution, an upper bound is determined for the erasure performance of any code, and it is shown that this can be translated into an upper bound for code performance in the AWGN channel. Finally, theoretical bounds on the construction of error-correction codes are discussed. These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.

Signals and communication technology•Jan 1, 2017•2 citations

Lower Bounds on the Error Probability of Block Codes Based on Improvements on de Caen's Inequality

A. Cohen, Neri Merhav

New lower bounds on the error probability of block codes with maximum-likelihood decoding are proposed. The bounds are obtained by applying a new lower bound on the probability of a union of events, derived by improving on de Caen's lower bound. The new bound includes an arbitrary function to be optimized in order to achieve the tightest results. Since the optimal choice of this function is known, but leads to a trivial and useless identity, we find several useful approximations for it, each resulting in a new lower bound. For the additive white Gaussian noise (AWGN) channel and the binary-symmetric channel (BSC), the optimal choice of the optimization function is stated and several approximations are proposed. When the bounds are further specialized to linear codes, the only knowledge on the code used is its weight enumeration. The results are shown to be tighter than the latest bounds in the current literature, such as those by Seguin (1998) and by Keren and Litsyn (2001). Moreover, for the BSC, the new bounds widen the range of rates for which the union bound analysis applies, thus improving on the bound to the error exponent compared with the de Caen-based bounds.

IEEE Transactions on Information Theory•Feb 1, 2004•41 citations
Improved Bounds on the Word Error Probability of RA(2)RA(2)RA(2) Codes With Linear-Programming-Based Decoding
This paper deals with the linear-programming-based decoding algorithm of Feldman and Karger for repeat-accumulate "turbo-like" codes. We present a new structural characterization that captures the event that decoding fails. Based on this structural characterization, we develop polynomial algorithms that, given an RA(2) code, compute upper and lower bounds on the word error probability P/sub w/ for the binary-symmetric and the additive white Gaussian noise (AWGN) channels. Our experiments with an implementation of these algorithms for bounding P/sub w/ demonstrate in many interesting cases an improvement in the upper bound on the word error probability by a factor of over 1000 compared to the bounds by Feldman et al.. The experiments also indicate that the improvement in upper bound increases as the codeword length increases and the channel noise decreases. The computed lower bounds on the word error probability in our experiments are roughly ten times smaller than the upper bound.
We examine regular and irregular repeat-accumulate (RA) codes with repetition degrees which are all even. For these codes and with a particular choice of an interleaver, we give an upper bound on the decoding error probability of a linear-programming based decoder which is an inverse polynomial in the block length. Our bound is valid for any memoryless, binary-input, output-symmetric (MBIOS) channel. This result generalizes the bound derived by Feldman et al., which was for regular RA(222) codes.
We introduce a novel algorithm for decoding turbo-like codes based on linear programming. We prove that for the case of repeat-accumulate (RA) codes, under the binary symmetric channel with a certain constant threshold bound on the noise, the error probability of our algorithm is bounded by an inverse polynomial in the code length. Our linear program (LP) minimizes the distance between the received bits and binary variables representing the code bits. Our LP is based on a representation of the code where code words are paths through a graph. Consequently, the LP bears a strong resemblance to the min-cost flow LP. The error bounds are based on an analysis of the probability, over the random noise of the channel, that the optimum solution to the LP is the path corresponding to the original transmitted code word.
The theoretical performance of binary codes for the additive white Gaussian noise (AWGN) channel is discussed. In particular, Gallager’s coding theorem for binary codes is treated extensively. By assuming a binomial weight distribution for linear codes, it is shown that the decoder error probability performance of some of the best, known linear, binary codes is the same as the average performance of the ensemble of all randomly chosen, binary nonlinear codes having the same length and dimension. Assuming a binomial weight distribution, an upper bound is determined for the erasure performance of any code, and it is shown that this can be translated into an upper bound for code performance in the AWGN channel. Finally, theoretical bounds on the construction of error-correction codes are discussed. These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
New lower bounds on the error probability of block codes with maximum-likelihood decoding are proposed. The bounds are obtained by applying a new lower bound on the probability of a union of events, derived by improving on de Caen's lower bound. The new bound includes an arbitrary function to be optimized in order to achieve the tightest results. Since the optimal choice of this function is known, but leads to a trivial and useless identity, we find several useful approximations for it, each resulting in a new lower bound. For the additive white Gaussian noise (AWGN) channel and the binary-symmetric channel (BSC), the optimal choice of the optimization function is stated and several approximations are proposed. When the bounds are further specialized to linear codes, the only knowledge on the code used is its weight enumeration. The results are shown to be tighter than the latest bounds in the current literature, such as those by Seguin (1998) and by Keren and Litsyn (2001). Moreover, for the BSC, the new bounds widen the range of rates for which the union bound analysis applies, thus improving on the bound to the error exponent compared with the de Caen-based bounds.