Energy Consumption of Error Control Coding Circuits

Abstract

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 (f (N)) where N is block length (called f(N)-coding schemes) have energy that scales as Ω(√ln f (N)N. As well, it is shown that the number of clock cycles (denoted T (N)) required for any encoding or decoding scheme that reaches this bound must scale as T (n) ≥ √ln f (N). 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 almost sure Ω(N2/d 2max scaling rule for the energy of directly-implemented LDPC decoder circuits for codes with maximum node degree d max. 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)-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>½ of block length N implemented according to the Thompson VLSI model must take energy E≥Ω(N 3/2. This lower bound is achievable up to polylogarithmic factors using a mesh network topology defined by Thompson and the encoding algorithm defined by Arιkan. A general class of circuits that compute successive cancellation decoding adapted from Arι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≥Ω( N3/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 χ = (1-R/C)-1, have energy that scales as Ω(χ 5.3685)≤ E ≤ O(χ 7.071log4(χ)). 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) < e—O(N). The Grover information-friction energy model is generalized to three dimensions and the optimal energy of encoding or decoding schemes with probability of block error Pe is shown to be at least Ω( N(ln Pe(N))1/3 ).