Upper and Lower Bounds on the Computational Complexity of Polar Encoding and Decoding.

It is shown that all polar encoding schemes using a standard encoding matrix with rate $R>\frac {1}{2}$ and block length $N$ have energy within the Thompson circuit model that scales at least as $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ı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\ge \Omega (N^{3/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 $\chi = (1-R/C)^{-1}$ (where $R$ is rate and $C$ is channel capacity), 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)$. 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. [ABSTRACT FROM AUTHOR]