Using the Thompson circuit complexity model, it is shown that fully parallel encoding and decoding schemes with asymptotic block error probability that scales as O( f (n)) have energy that scales as Ω(n- ln f (n)1/2). In addition, it is shown that the number of clock cycles [T(n)] required for any encoding or decoding scheme that reaches this bound must scale as T(n) ≥ - ln f (n)1/2. Similar scaling results are extended to serialized computation. A similar approach is extended to three dimensions by generalizing the Grover information-friction energy model. Within this model, it is shown that encoding and decoding schemes with probability of block error Pe(n) consume at least Ω(n(- ln Pe(n))(1/3)) energy.

It is shown that all polar encoding schemes using a standard encoding matrix with rate R>1/2 and block length N have energy within the Thompson circuit model that scales at least as E ≥ Ω (N3/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). The energy of a Mead memory architecture and a mesh network memory architecture are analyzed and it is shown that a processor architecture using these memory elements can reach the decoding energy lower bounds to within a polylogarithmic factor. Similar scaling rules are derived for polar list decoders and belief propagation decoders. Capacity approaching sequences of energy optimal polar encoders and decoders, as a function of reciprocal gap to capacity χ = (1- R/C)-1(where R is rate C and is channel capacity), have energy that scales as Ω (χ5.3685) ≤ E ≤ O (χ7.071log4(χ)). Known results in constant depth circuit complexity theory imply that no polynomial size classical circuits can compute polar encoding, but this is possible in quantum circuits that include a constant depth quantum fan-out gate.

It is now well known that using a long and complicated error correcting code (ECC) designed for the worst-case error probability requirement wastes excessive total system energy (transmit + circuit energy) when the error probability requirement is much higher than the worst case. We propose a novel adaptive polar coding strategy that adjusts the decoder circuit to consume minimal decoding circuit energy at each given target error requirement. By combining Thompson's VLSI theory and scaling analysis of polar codes, we provide upper bounds on energy, area, and time complexity of polar decoding circuits in terms of target block error probability. The upper bounds are derived from an explicit construction of decoder circuit based on mesh-network structure. Our comparison shows that the proposed energy-adaptive coding strategy has a scaling-sense gain in decoding energy with little circuit area overhead when there is a large gap between the worst-case and typical target error rate requirements.

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.

Sequences of VLSI circuits implemented according to the Thompson VLSI model that compute encoding and decoding functions, called coding schemes, are classified according to the rate at which their associated block error probability scales with block length N. It is shown that coding schemes for binary symmetric channels with probability of error that scales as O(f(N)) must have encoding and decoding energy that scales at least as Ω(N√(-ln f (N))). Polar coding schemes of rate greater than 1/2 are shown to have encoding and decoding energy that scales at least as Ω(N3/2). This lower bound is achievable up to polylogarithmic factors on a mesh-network.

A standard VLSI model is used to derive universal lower bounds on the energy of decoder circuits. In the circuit model used, the product of the circuit area and number of clock cycles, or the area-time complexity is proportional to the energy of computation. Lower bounds as a function of block length n are presented for three different circuit paradigms. Firstly, for circuits that compute in parallel, an Ω(n(logn)1/2) scaling rule is shown. Secondly, for circuits that compute serially, an Ω(nlogn) lower bound is presented. Thirdly, for a sequence of decoding circuits in which the number of output pins grows arbitrarily with block length, the energy is shown to grow as Ω(n(logn)1/5). In addition, it is shown that the energy complexity of almost all LDPC decoders that can get close to capacity and whose Tanner graphs are generated according to a uniform standard configuration model must take Ω(n2) area to implement directly.

Thompson's model of very large scale integration 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 1/2 then the energy of the computation scales at least as Ω(n(log n)1/2), and so the energy of decoding per bit must scale at least as Ω(log n)1/2. 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 1/2 then the energy scales at least as fast as Ω(n log n). 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 Ω(n(log n)1/5). A simple example is provided of a class of circuits performing low-density parity-check decoding whose energy complexity scales as O(n2loglogn).