Bounds on the Tradeoff Between Decoding Complexity and Rate for Sparse-Graph Codes

Khandekar and McEliece suggested the problem of per bit decoding complexity for capacity achieving sparse-graph codes as a function of their gap from the channel capacity. We consider the problem for the case of the binary symmetric channel. We derive a lower bound on this complexity for some codes on graphs for Belief Propagation decoding. For bounded degree LDPC and LDGM codes, any concatenation of the two, and punctured bounded-degree LDPC codes, this reduces to a lower bound of O (log (1/isin-)). The proof of this result leads to an interesting necessary condition on the code structures which could achieve capacity with bounded decoding complexity over BSC: the average edge-degree must converge to infinity while the average node-degree must be bounded. That is, one of the node degree distributions must have a finite mean and an infinite variance.