On the VLSI Energy Complexity of LDPC Decoder Circuits

Sequences of randomly generated bipartite configurations are analyzed; under mild conditions almost surely such configurations have minimum bisection width proportional to the number of vertices. This implies an almost sure Ω(n2/dmax2) scaling rule for the energy of directlyimplemented low-density parity-check (LDPC) decoder circuits for codes of block length n and maximum node degree dmax. It also implies an Ω(n3/2/dmax) lower bound for serialized LDPC decoders. It is also shown that all (as opposed to almost all) capacity-approaching, directly-implemented non-split-node LDPC decoding circuits, have energy, per iteration, that scales as Ω(χ2ln3χ), where χ = (1 - R/C)-1is the reciprocal gap to capacity, R is code rate, and C is channel capacity.