Decoding turbo-like codes via linear programming

J FELDMAN

Fan Jiang, Eric T. Psota, Lance C. Pérez

The turbo iterative decoding algorithm only performs well for turbo codes with relatively small memories. Moreover, its decoding complexity becomes prohibitively large when the turbo encoders have very large memories. The sum-product and linear programming decoding algorithms are based on the parity-check matrices of the codes. They are widely used to decode low-density parity-check codes. These algorithms do not suffer the limitations of the turbo iterative decoding algorithm. In order to apply them to the turbo codes, the parity-check matrices of turbo codes must be found. By treating turbo codes as serially concatenated codes, the generator and parity-check matrices of the turbo codes are derived in this paper. Turbo codes with low-density parity-check matrices are then designed based on the derived results. Provided these matrices, turbo codes are decoded using the sum-product algorithms. Preliminary results show that the sum-product decoding of turbo codes performs slightly worse than sum-product decoding of conventional low-density parity-check codes. However, since the encoding of turbo codes has less complexity than the straightforward encoding of low-density parity-check codes, this loss in performance may be justified by the drastically decreased encoding complexity. The availability of the parity-check matrices of turbo codes also makes them ready to be decoded by the linear programming decoding algorithm which is optimum for the given linear constraints.

Martin Bossert, F. Hergert

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.

Kenny Barrese

Michael Helmling

The formulation of the decoding problem for linear block codes as an integer program (IP) with a rather tight linear programming (LP) relaxation has made a central part of channel coding accessible for the theory and methods of mathematical optimization, especially integer programming, polyhedral combinatorics and also algorithmic graph theory, since the important class of turbo codes exhibits an inherent graphical structure. We present several novel models, algorithms and theoretical results for error-correction decoding based on mathematical optimization. Our contribution includes a partly combinatorial LP decoder for turbo codes, a fast branch-and-cut algorithm for maximum-likelihood (ML) decoding of arbitrary binary linear codes, a theoretical analysis of the LP decoder's performance for 3-dimensional turbo codes, compact IP models for various heuristic algorithms as well as ML decoding in combination with higher-order modulation, and, finally, first steps towards an implementation of the LP decoder in specialized hardware. The scientific contributions are presented in the form of seven revised reprints of papers that appeared in peer-reviewed international journals or conference proceedings. They are accompanied by an extensive introductory part that reviews the basics of mathematical optimization, coding theory, and the previous results on LP decoding that we rely on afterwards.