Conference: Symposium about Applied Mathematics


Linear-Programming Decoding of Nonbinary Linear Codes

{{_Ltalk:R}} Dr. Vitaly Skachek
Date: 17.12.09   Time: 16.00 - 17.00   Room: Y27H35/36

Abstract: Decoding of binary LDPC codes using linear-programming (LP) decoder was proposed by J. Feldman et al. The connections between LP decoding and classical message-passing decoding were established in that paper. In our work, we extend the above approach to nonbinary coded modulations, in particular to codes over rings mapped to nonbinary modulation signals. In both cases, the principal advantage of the linear-programming framework is its mathematical tractability.

We define two alternative polytope representations, which offer a smaller number of variables and constraints for many classes of nonbinary codes. These polytope representations, when used with the respective nonbinary LP problems, lead to polynomial-time decoders for a wide variety of classical nonbinary codes.

Finally, we present an LP decoder for nonbinary expander codes. We show that that this decoder corrects any pattern of errors of a relative weight up to approximately $1/4 \delta_A \delta_B$ (where $\delta_A$ and $\delta_B$ are the relative minimum distances of the constituent codes).