Energy Consumption of Error Control Coding Circuits

The energy complexity of error control coding circuits is analyzed within the Thompson VLSI model. It is shown that fully-parallel encoding and decoding schemes with asymptotic block error probability that scales as $O\left(f\left(N\right)\right)$ where $N$ is block length (called $f(N)$-coding schemes) have energy that scales as $\Omega\left(\sqrt{\ln f\left(N\right)}N\right)$. As well, it is shown that the number of clock cycles (denoted $T\left(N\right)$) required for any encoding or decoding scheme that reaches this bound must scale as $T\left(n\right)\ge\sqrt{\ln f\left(N\right)}$. Similar scaling results are extended to serialized computation. 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 \emph{almost sure} $\Omega(N^{2}/d^2_{\mathrm{max}})$ scaling rule for the energy of directly-implemented LDPC decoder circuits for codes with maximum node degree $d_{\mathrm{max}}$. It also implies an $\Omega(N^{3/2}/d_{\mathrm{max}})$ lower bound for serialized LDPC decoders. It is also shown that \emph{all} (as opposed to almost all) capacity-approaching, directly-implemented non-split-node LDPC decoding circuits, have energy, per iteration, that scales as $\Omega\left(\chi^2\ln^3 \chi\right)$, where $\chi=(1-R/C)^{-1}$ is the reciprocal gap to capacity, $R$ is code rate and $C$ is channel capacity. It is shown that all polar encoding schemes of rate $R>\frac{1}{2}$ of block length $N$ implemented according to the Thompson VLSI model must take energy $E\ge\Omega\left(N^{3/2}\right)$. This lower bound is achievable up to polylogarithmic factors using a mesh network topology defined by Thompson and the encoding algorithm defined by Ar{\i}kan. A general class of circuits that compute successive cancellation decoding adapted from Ar{\i}kan's butterfly network algorithm is defined. It is shown that such decoders implemented on a rectangle grid for codes of rate $R>2/3$ must take energy $E\ge\Omega(N^{3/2})$, and this can also be reached up to polylogarithmic factors using a mesh network. Capacity approaching sequences of energy optimal polar encoders and decoders, as a function of reciprocal gap to capacity $\chi = (1-R/C)^{-1}$, have energy that scales as $\Omega\left(\chi^{5.3685}\right)\le E \le O\left(\chi^{7.071}\log^{4}\left(\chi\right)\right)$. It is shown that all sufficiently large communication graphs of algorithms of bounded degree can be implemented on a mesh network with routing conflicts of size at most $\log(N)$. This implies, conditioned on an assumption, that for all $f(N)Ph.D