Linear Programming Decoding of Spatially Coupled Codes

DOI10.1109/TIT.2014.2325903MaRDI QIDQ2986213zbMATH OpenFDO

Authors Louay Bazzi, Badih Ghazi, Ruediger Urbanke

Publication date 16 May 2017

Published in IEEE Transactions on Information Theory (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1301.6410

Mathematics Subject Classification ID

Linear programming (90C05) Decoding (94B35)

Abstract: For a given family of spatially coupled codes, we prove that the LP threshold on the BSC of the graph cover ensemble is the same as the LP threshold on the BSC of the derived spatially coupled ensemble. This result is in contrast with the fact that the BP threshold of the derived spatially coupled ensemble is believed to be larger than the BP threshold of the graph cover ensemble as noted by the work of Kudekar et al. (2011, 2012). To prove this, we establish some properties related to the dual witness for LP decoding which was introduced by Feldman et al. (2007) and simplified by Daskalakis et al. (2008). More precisely, we prove that the existence of a dual witness which was previously known to be sufficient for LP decoding success is also necessary and is equivalent to the existence of certain acyclic hyperflows. We also derive a sublinear (in the block length) upper bound on the weight of any edge in such hyperflows, both for regular LPDC codes and for spatially coupled codes and we prove that the bound is asymptotically tight for regular LDPC codes. Moreover, we show how to trade crossover probability for "LP excess" on all the variable nodes, for any binary linear code.

Recommendations

• Decoding low-dimensional linear codes by linear programming
• Linear-Programming Decoding of Nonbinary Linear Codes
• Using linear programming to decode LDPC codes
• Decoding turbo-like codes via linear programming
• Multistep linear programming approaches for decoding low-density parity-check codes
• Efficient Implementation of Linear Programming Decoding
• A New Linear Programming Approach to Decoding Linear Block Codes
• Mathematical Programming Decoding of Binary Linear Codes: Theory and Algorithms

Cited in

(5)

• Error correcting codes and spatial coupling
• Constellation labeling for linear encoders
• On the Decoding Performance of Spatially Coupled LDPC Codes With Sub-Block Access
• Analog Product Codes Decodable by Linear Programming
• Coordination and discoordination in linear algebra, linear information theory, and coded caching

This page was built for publication: Linear Programming Decoding of Spatially Coupled Codes

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2986213)