LP Decoding of Regular LDPC Codes in Memoryless Channels

DOI10.1109/TIT.2010.2094830zbMATH Open1366.94702arXiv1002.3117MaRDI QIDQ5281081FDOQ5281081

Authors: Nissim Halabi, Guy Even 

Publication date: 27 July 2017

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

Abstract: We study error bounds for linear programming decoding of regular LDPC codes. For memoryless binary-input output-symmetric channels, we prove bounds on the word error probability that are inverse doubly-exponential in the girth of the factor graph. For memoryless binary-input AWGN channel, we prove lower bounds on the threshold for regular LDPC codes whose factor graphs have logarithmic girth under LP-decoding. Specifically, we prove a lower bound of $sigma=0.735$ (upper bound of $fracEb{N}_0=2.67$dB) on the threshold of $(3,6)$-regular LDPC codes whose factor graphs have logarithmic girth. Our proof is an extension of a recent paper of Arora, Daskalakis, and Steurer [STOC 2009] who presented a novel probabilistic analysis of LP decoding over a binary symmetric channel. Their analysis is based on the primal LP representation and has an explicit connection to message passing algorithms. We extend this analysis to any MBIOS channel.

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

Mathematics Subject Classification ID

Applications of graph theory (05C90) Decoding (94B35)

Cited In (2)

• Reweighted LP Decoding for LDPC Codes
• Majority-Based Tracking Forecast Memories for Stochastic LDPC Decoding

This page was built for publication: LP Decoding of Regular LDPC Codes in Memoryless Channels

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