Feldman et al. [11] asked whether the performance of the linear programming (LP) decoder can be improved by adding redundant parity checks to tighten the LP relaxation. We prove in this paper that for low-density parity-check codes, even if we include all redundant parity checks, asymptotically there is no gain in the LP decoder threshold on the binary symmetric channel under certain conditions on the base Tanner graph. First, we show that if the Tanner graph has bounded check-degree and satisfies a condition which we call asymptotic strength, then including high degree redundant parity checks in the LP does not significantly improve the threshold of the LP decoder in the following sense. For each constant δ > 0, there is a constant k > 0 such that the threshold of the LP decoder containing all redundant checks of degree at most k improves by at most δ upon adding to the LP all redundant checks of degree larger thank. We conclude that if the graph satisfies an additional condition which we call rigidity, then including all redundant checks does not improve the threshold of the base LP. We call the graph asymptotically strong if the LP decoder corrects a constant fraction of errors even if the log-likelihood-ratios of the correct variables are arbitrarily small. By building on a construction due Feldman et al. [9] and its recent improvement by Viderman [24], we show that asymptotic strength follows from sufficiently large variable-to-check expansion. We also give a geometric interpretation of asymptotic strength in terms pseudocodewords. We call the graph rigid if the minimum weight of a sum of check nodes involving a cycle tends to infinity as the block length tends to infinity. Under the assumptions that the graph girth is logarithmic and the minimum check degree is at least 3, rigidity is equivalent to the nondegeneracy property that adding at least logarithmically many checks does not give a constant weight check. We argue that nondegeneracy is a typical property of random check-regular Tanner graphs.
Feldman et al. [11] asked whether the performance of the linear programming (LP) decoder can be improved by adding redundant parity checks to tighten the LP relaxation. We prove in this paper that for low-density parity-check codes, even if we include all redundant parity checks, asymptotically there is no gain in the LP decoder threshold on the binary symmetric channel under certain conditions on the base Tanner graph. First, we show that if the Tanner graph has bounded check-degree and satisfies a condition which we call asymptotic strength, then including high degree redundant parity checks in the LP does not significantly improve the threshold of the LP decoder in the following sense. For each constant δ > 0, there is a constant k > 0 such that the threshold of the LP decoder containing all redundant checks of degree at most k improves by at most δ upon adding to the LP all redundant checks of degree larger thank. We conclude that if the graph satisfies an additional condition which we call rigidity, then including all redundant checks does not improve the threshold of the base LP. We call the graph asymptotically strong if the LP decoder corrects a constant fraction of errors even if the log-likelihood-ratios of the correct variables are arbitrarily small. By building on a construction due Feldman et al. [9] and its recent improvement by Viderman [24], we show that asymptotic strength follows from sufficiently large variable-to-check expansion. We also give a geometric interpretation of asymptotic strength in terms pseudocodewords. We call the graph rigid if the minimum weight of a sum of check nodes involving a cycle tends to infinity as the block length tends to infinity. Under the assumptions that the graph girth is logarithmic and the minimum check degree is at least 3, rigidity is equivalent to the nondegeneracy property that adding at least logarithmically many checks does not give a constant weight check. We argue that nondegeneracy is a typical property of random check-regular Tanner graphs.
Feldman et al. [1] asked whether the performance of the Linear Programming (LP) decoder can be improved by adding redundant parity checks to tighten the LP relaxation. We prove in this paper that for LDPC codes, even if we include all redundant parity checks, asymptotically there is no gain in the LP decoder threshold on the Binary Symmetric Channel (BSC) under certain conditions on the base Tanner graph. First, we show that if the base Tanner graph has bounded check-degree and satisfies a condition which we call asymptotic strength, then including high degree redundant parity checks in the LP does not significantly improve the threshold of the LP decoder in the following sense: for each constant δ > 0, there is a constant k > 0 such that the threshold of the LP decoder containing all redundant checks of degree at most k improves by at most δ upon adding to the LP all redundant checks of degree larger than k. We conclude that if the graph satisfies an additional condition which we call rigidity, then including all redundant checks does not improve the threshold of the base LP. We call the graph asymptotically strong if the LP decoder corrects a constant fraction of errors even if the log-likelihood-ratios of the correct variables are arbitrarily small. By building on a construction due Feldman et al. [2] and its recent improvement by Viderman [3], we show that asymptotic strength follows from sufficiently large variable-to-check expansion. We also give a geometric interpretation of asymptotic strength in terms pseudocodewords. We call the graph rigid if the minimum weight of a sum of check nodes involving a cycle tends to infinity as the block length tends to infinity. Under the assumptions that the graph girth is logarithmic and the minimum check degree is at least 3, rigidity is equivalent to the nondegeneracy property that adding at least logarithmically many checks does not give a constant weight check. We argue that nondegeneracy is a typical property of random check-regular Tanner graphs.
Feldman et al.(2005) asked whether the performance of the LP decoder can be improved by adding redundant parity checks to tighten the LP relaxation. We prove that for LDPC codes, even if we include all redundant checks, asymptotically there is no gain in the LP decoder threshold on the BSC under certain conditions on the base Tanner graph. First, we show that if the graph has bounded check-degree and satisfies a condition which we call asymptotic strength, then including high degree redundant checks in the LP does not significantly improve the threshold in the following sense: for each constant delta>0, there is a constant k>0 such that the threshold of the LP decoder containing all redundant checks of degree at most k improves by at most delta upon adding to the LP all redundant checks of degree larger than k. We conclude that if the graph satisfies a rigidity condition, then including all redundant checks does not improve the threshold of the base LP. We call the graph asymptotically strong if the LP decoder corrects a constant fraction of errors even if the LLRs of the correct variables are arbitrarily small. By building on the work of Feldman et al.(2007) and Viderman(2013), we show that asymptotic strength follows from sufficiently large expansion. We also give a geometric interpretation of asymptotic strength in terms pseudocodewords. We call the graph rigid if the minimum weight of a sum of check nodes involving a cycle tends to infinity as the block length tends to infinity. Under the assumptions that the graph girth is logarithmic and the minimum check degree is at least 3, rigidity is equivalent to the nondegeneracy property that adding at least logarithmically many checks does not give a constant weight check. We argue that nondegeneracy is a typical property of random check-regular graphs.
In this correspondence, we study the minimum pseudoweight and minimum pseudocodewords of low-density parity-check (LDPC) codes under linear programming (LP) decoding. First, we show that the lower bound of Kelley, Sridhara, Xu, and Rosenthal on the pseudoweight of a nonzero pseudocodeword of an LDPC code whose Tanner graph has girth greater than is tight if and only if this pseudocodeword is a real multiple of a codeword. Then, the lower bound of Kashyap and Vardy on the stopping distance of an LDPC code is proved to be also a lower bound on the pseudoweight of a nonzero pseudocodeword of an LDPC code whose Tanner graph has girth , and this lower bound is tight if and only if this pseudocodeword is a real multiple of a codeword. Using these results we further obtain that for some LDPC codes, there are no other minimum pseudocodewords except the real multiples of minimum weight codewords. This means that the LP decoding for these LDPC codes is asymptotically optimal in the sense that the ratio of the probabilities of decoding errors of LP decoding and maximum-likelihood decoding approaches as the signal-to-noise ratio (SNR) tends to infinity. Finally, some LDPC codes are listed to illustrate these results.
We show that for low-density parity-check (LDPC) codes whose Tanner graphs have sufficient expansion, the linear programming (LP) decoder of Feldman, Karger, and Wainwright can correct a constant fraction of errors. A random graph will have sufficient expansion with high probability, and recent work shows that such graphs can be constructed efficiently. A key element of our method is the use of a dual witness: a zero-valued dual solution to the decoding linear program whose existence proves decoding success. We show that as long as no more than a certain constant fraction of the bits are flipped by the channel, we can find a dual witness. This new method can be used for proving bounds on the performance of any LP decoder, even in a probabilistic setting. Our result implies that the word error rate of the LP decoder decreases exponentially in the code length under the binary-symmetric channel (BSC). This is the first such error bound for LDPC codes using an analysis based on "pseudocodewords." Recent work by Koetter and Vontobel shows that LP decoding and min-sum decoding of LDPC codes are closely related by the "graph cover" structure of their pseudocodewords; in their terminology, our result implies that that there exist families of LDPC codes where the minimum BSC pseudoweight grows linearly in the block length
Ever since the publication of Shannon's seminal work in 1948, the search for capacity achieving codes has led to many interesting discoveries in channel coding theory. Low-density parity-check (LDPC) codes originally proposed in 1963 were largely forgotten and rediscovered recently. The significance of LDPC codes lies in their capacity approaching performance even when decoded using low complexity sub-optimal decoding algorithms. Iterative decoders are one such class of decoders that work on a graphical representation of a code known as the Tanner graph. Their properties have been well understood in the asymptotic limit of the code length going to infinity. However, the behavior of various decoders for a given finite length code remains largely unknown.An understanding of the failures of the decoders is vital for the error floor analysis of a given code. Broadly speaking, error floor is the abrupt degradation in the frame error rate (FER) performance of a code in the high signal-to-noise ratio domain. Since the error floor phenomenon manifests in the regions not reachable by Monte-Carlo simulations, analytical methods are necessary for characterizing the decoding failures. In this work, we consider hard decision decoders for transmission over the binary symmetric channel (BSC).For column-weight-three codes, we provide tight upper and lower bounds on the guaranteed error correction capability of a code under the Gallager A algorithm by studying combinatorial objects known as trapping sets. For higher column weight codes, we establish bounds on the minimum number of variable nodes that achieve certain expansion as a function of the girth of the underlying Tanner graph, thereby obtaining lower bounds on the guaranteed error correction capability. We explore the relationship between a class of graphs known as cage graphs and trapping sets to establish upper bounds on the error correction capability.We also propose an algorithm to identify the most probable noise configurations, also known as instantons, that lead to error floor for linear programming (LP) decoding over the BSC. With the insight gained from the above analysis techniques, we propose novel code construction techniques that result in codes with superior error floor performance.
We study peeling decoding on the binary erasure channel when redundant parity checks may be added without restriction in number, but each check is subject to a row-weight constraint. For random simple binary regular low-density parity-check (LDPC) codes, we consider the parity-check matrix formed by all nonzero dual codewords up to a prescribed weight. We show that, throughout an explicit logarithmic row-weight range, this complete family of redundant checks has the same asymptotic normalized-residual threshold as peeling with the original LDPC matrix. In the same range, with probability tending to one over the random code, it still has a linear-size stopping set that is uniquely decodable. Consequently, every parity-check representation whose peeling decoder succeeds on every uniquely decodable erasure pattern must contain checks above this logarithmic scale, and the supports of those heavier checks must collectively contain a linear number of coordinates. Thus row weight remains an asymptotic limitation even when the number and selection of redundant checks are unrestricted.