“The Impact of Redundant Checks on the LP Decoding Thresholds of LDPC Codes”
Beirut campus, Byblos campus
The Department of Computer Science and Mathematics is hosting a seminar titled “The Impact of Redundant Checks on the LP Decoding Thresholds of LDPC Codes,” to be given by guest speaker Dr. Louay Bazzi, Associate Professor in the Department of Electrical and Computer Engineering at the American University of Beirut. The event will be available to students in Nicol 222 on the Beirut campus and in Jamil Iskandar on the Byblos campus.
Abstract: Feldman et al. (2005) 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 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 Tanner graph has bounded check-degree and satisfies a condition which we call asymptotic strength, thenincluding 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 $\delta>0$, there is aconstant $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 checksof 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 thresholdof 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. (2007) and its recent improvement by Viderman (2013), 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 checknodes 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$, rigidityis 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.
All are welcome to attend.