LP decoding excess over symmetric channels

Abstract

We consider the problem of Linear Programming (LP) decoding of binary linear codes. The LP excess lemma was introduced by the first author, B. Ghazi, and R. Urbanke (IEEE Trans. Inf. Th., 2014) as a technique to trade crossover probability for "LP excess" over the Binary Symmetric Channel. We generalize the LP excess lemma to discrete, binary-input, Memoryless, Symmetric and LLR-Bounded (MSB) channels. As an application, we extend a result by the first author and H. Audah (IEEE Trans. Inf. Th., 2015) on the impact of redundant checks on LP decoding to discrete MSB channels.

To appear in IEEE Communications Letters