Linear Programming-Based Decoding of Turbo-Like Codes and its Relation to Iterative Approaches
In recent work (Feldman and Karger [8]), we introduced a new a pproach to decoding turbo-like codes based on linear programming (LP). We gave a precise characterization of the noise patterns that cause decoding error under the binar y symmetric and additive white Gaussian noise channels. We used this characterization to p rove that the word error rate is bounded by an inverse polynomial in the code length. Furth ermore, for any turbo-like code, our algorithm has the ML certificateproperty: whenever it outputs a code word, it is guaranteed to be the maximum-likelihood (ML) code word. In this paper we extend these results and give an iterative de coder whose output is equivalent to that of the LP decoder. We also extend the ML cer tifi ate property to the more efficient iterativetree reweighted max-product message-passing algorithm developed by Wainwright, Jaakkola, and Willsky [13]: we show that whenev er this algorithm converges to a code word, it must be the ML code word. Finally, we demonstrate experimentally that the noise patt erns that cause decoding error in the LP decoder also cause decoding error in the stand ard iterative sum-product and max-product (min-sum) message-passing algorithms. Conse quently, the deterministically constructible interleaver used by the LP decoder to achieve its bounds on error rate is useful in practice not only for the LP decoder, but for these s tandard iterative decoders as