“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.