Decoding Turbo-Like Codes via Linear Programming

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.

Authors

• Jon Feldman
• David R. Karger

Keywords

• Linear programming
• Maximum likelihood decoding
• Error probability
• Turbo codes
• Iterative decoding
• Computer science
• Error analysis
• Laboratories
• Contracts
• Polynomials
• Random Noise
• Probabilistic Analysis
• Codeword
• Error Bounds
• Code Length
• Code Representation
• Minimum Cost Flow
• Minimum Distance
• Less Than Or Equal
• Efficient Algorithm
• Binary String
• Information Bits
• Hamming Distance
• Normal Flow
• Forward Error Correction
• Simple Graph
• Simple Cycle
• Types Of Codes
• Decoding Algorithm
• Low-density Parity-check Codes
• Code Examples
• Codeword Length
• Input String
• Cost Path
• Even Parity
• Low-density Parity-check
• Interesting Open Question
• Convolutional Codes