Energy Consumption of VLSI Decoders

Thompson's model of VLSI computation relates the energy of a computation to the product of the circuit area and the number of clock cycles needed to carry out the computation. It is shown that for any sequence of increasing-block -length decoder circuits implemented according to this model, if the probability of block error is asymptotically less than $\half$ then the energy of the computation scales at least as $\Omega\left(n\sqrt{\log n}\right)$, and so the energy of decoding per bit must scale at least as $\Omega\left(\sqrt{\log n}\right)$. This implies that the average energy per decoded bit must approach infinity for any sequence of decoders that approaches capacity. The analysis techniques used are then extended to show that for any sequence of increasing-block-length serial decoders if the asymptotic block error probability is less than $\half$ then the energy scales at least as fast as $\Omega\left(n\log n\right)$. In a very general case that allows for the number of output pins to vary with block length, it is shown that the energy must scale as $\Omega\left(n\left(\log n\right)^{\fifth}\right)$. A simple example is provided of a class of circuits performing low-density parity-check decoding whose energy complexity scales as $O\left(n^2 \log \log n\right)$.This work was sponsored by the Natural Sciences and Engineering Research Council of Canada, through a Discovery Grant