Electrical Engineering
      and Computer Sciences

Electrical Engineering and Computer Sciences


UC Berkeley


2009 Research Summary

Power-Consumption, Rate, and Complexity for Codes with Message-Passing Decoding

View Current Project Information

Anant Sahai, Pulkit Grover and Harikrishna R Palaiyanur

Decoding architectures based on sparse-graphs are of interest because of their low complexity and ability to work close to the information theoretic limits. 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 (and hence power-consumption) scales at least as fast as 2log(1/gap) for bounded degree decoders, where gap = C - R. For short-range applications, this effect demonstrates that codes should not operate close to capacity.

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.

We are investigating the implications for multiuser systems as well as more general decoding architectures.