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

Advances in Mathematics of Communications

Error bounds for repeat-accumulate codes decoded via linear programming

Idan Goldenberg, David Burshtein

Published Jan 1, 2011• 7 citations
Publisher

Abstract

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.

DOI
10.3934/amc.2011.5.555

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

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

Nissim Halabi, Guy Even

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.

IEEE Transactions on Information Theory•Jan 1, 2005•20 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

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

Irregular repeat accumulate codes

Hao Jin

In this paper we will introduce an ensemble of codes called irregular repeat-accumulate (IRA) codes. IRA codes are a generalization of the repeat-accumulate codes introduced in [1], and as such have a natural linear time encoding algorithm. We shall prove that on the binary erasure channel, IRA codes can be decoded reliably in linear time, using iterater] sum-product decoding,a# ra#SJ a#SJ8T a#SJ8 close tocha#T36 ca pa#J464 Asimila# resulta#u ea#S to be true on the AWGN channel, although we have no proof of this. We illustrate our results with numerical and experimenta# examples.

•Jan 1, 2000•580 citations
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.
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 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.
In this paper we will introduce an ensemble of codes called irregular repeat-accumulate (IRA) codes. IRA codes are a generalization of the repeat-accumulate codes introduced in [1], and as such have a natural linear time encoding algorithm. We shall prove that on the binary erasure channel, IRA codes can be decoded reliably in linear time, using iterater] sum-product decoding,a# ra#SJ a#SJ8T a#SJ8 close tocha#T36 ca pa#J464 Asimila# resulta#u ea#S to be true on the AWGN channel, although we have no proof of this. We illustrate our results with numerical and experimenta# examples.