Research Projects

Tradeoff between Rate and Complexity for Sparse Graph Codes

Anant Sahai and Pulkit Grover

Sparse-graph codes are of interest because of their low decoding complexity and high rates. We investigate whether the two can be achieved simultaneously. In other words, we explore whether increasing the rate R of sparse-graph codes necessitates an increased decoding complexity as well. We derive a lower bound on the decoding complexity of the code sequence, given rate R and channel capacity C. We show that the decoding complexity scales as O(log(1/gap)) for bounded degree constructions, where gap = C - R.

The result is applicable to a wide variety of sparse-graph codes, including LDPC codes, LDGM codes, punctured LDPC codes, concatenation of LDPC and LDGM codes, IRA codes, ARA codes etc., and all memoryless binary input output-symmetric channels.