\section{Introduction}
\IEEEPARstart {C}{ontinuing} recent work on the energy of VLSI error control circuits
\cite{GroverInfoFriction,groverFundamental,blakeConstantPePaper,BlakeLDPCAlmostSure,blakeKschischangEnergyLatencyReliabilityTradeoffs, ganesanPaper},
in this paper we provide lower and upper bound scaling rules
on the energy of VLSI implementations of polar encoders and decoders.
In particular, we show that all polar encoders of constant switching activity factor for codes of rate $R>1/2$
have energy that scales at least as $\Omega\left(N^{3/2}\right)$.
 We describe a class of circuits based on the polar decoding algorithm suggested by Arikan
in \cite{ArikanPolar}. We show that circuits of this type for polar codes of rate $R>2/3$ must take at least $\Omega(N^{3/2})$
energy when its output nodes are arranged on a rectangular
grid. The mesh network topology can also reach this lower bound up
to polylogarithmic factors by using circuits with switching activity factor that decreases with increasing block length.

In a companion paper \cite{blakeKschischangEnergyLatencyReliabilityTradeoffs}, we analyze the tradeoffs in the number of clock cycle, energy, and block error probability for encoder and decoder circuits. For sequences of circuits with variable switching activity factor, Grover \cite{GroverInfoFriction} showed similar scaling rules for the energy of encoders and decoders as a function of block error probability. In particular, these results show that coding schemes with block error probability that scales exponentially in block length $N$ must have energy that scales as $\Omega(N^{3/2})$, and our paper \cite{blakeKschischangEnergyLatencyReliabilityTradeoffs} shows that schemes with constant switching activity factor that reach this lower bound must have number of clock cycles $T\ge \Omega (\sqrt N)$. There exist generalized polar decoders with asymptotic block error probability that scale as $\Theta(e^{-N^{1-\epsilon}})$ for any $\epsilon>0$ \cite{HassaniAlishahiUrbanke} (that is, very close to $O(e^{-N})$), and in this paper we discuss how the energy of polar decoders for such codes implemented on a mesh network can get very close to the $\Omega (N^{3/2})$ energy lower bound implied by Grover \cite{GroverInfoFriction}, implying that the energy lower bound is close to tight. However, this requires decoders with switching activity factor that scales as $\Theta(1/N)$, and number of clock cycles that scales close to $\Theta(N^{3/2})$, in contrast to the clock cycle lower bound of \cite{blakeKschischangEnergyLatencyReliabilityTradeoffs}. This is because of the difficulty of parallelization of the successive cancellation decoding algorithm.

In Section~\ref{sec:priorRelated} we discuss how the results of this paper build upon prior work. In Section~\ref{sec:Computational-Model} we discuss the computational
model we will use and present some basic definitions that will be
used. In Section \ref{sec:Polar-Encoders-Lower} we present one of
the main technical results of this paper, showing a lower bound on
the VLSI energy complexity of polar encoding. We discover a similar
lower bound for the complexity of decoding using VLSI circuits derived
from Arikan's successive cancellation decoding algorithm in Section \ref{sec:Arikan-Successive-Cancellation}.
Upper bounds that reach the lower bounds of the previous two sections
are presented in Section \ref{sec:Upper-Bounds-mesh-network} where
the mesh network used by Thompson for sorting and fast Fourier transform
is applied to the polar encoding and decoding algorithms. In Section~\ref{sec:generalizedOnMesh} we study how some of these results can be extended to polar coding with more general generating matrices. In Section
\ref{sec:Energy-Scaling-as-function-gap-to-capacity} we show how
these upper and lower bound results, when combined with finite length
analysis of polar coding, results in upper and lower bounds for the
energy of polar decoding as a function of gap to capacity. Finally,
in Section \ref{sec:Future-Work} we discuss some open questions and
areas of future work.

\emph{Notation:} We use standard Bachmann-Landau
notation in our discussions. The statement $f(x)=O(g(x))$ means that for
sufficiently large $x$, $f(x)\le cg(x)$ for some positive constant
$c$. The statement $f(x)=\Omega(g(x))$ means that for sufficiently
large $x$, $f(x)\ge cg(x)$ again for some positive constant $c$.
The statement $f(x)=\Theta(g(x))$ means that there are two positive
constants $b$ and $c$ such that $b\le c$ and for sufficiently large
$x$, $bg(x)\le f(x)\le cg(x)$. The statement $f(x)=o(g(x))$ means that for sufficiently large $x$ and all $c>0$, $f(x) < cg(x)$.

We let the symbol $[N]=\{1,2,\ldots , N\}$ denote the set of integers from $1$ to $N$.

 Given a set of indices
$X,Y\subseteq [N]$, and a vector $V$ of length $N$, we define
the notation $V(X)$ to be the subvector of $V$ formed by the indices in
$X$. As well, given an $N\times N$ matrix $A$, the notation $A(X,Y)$
refers to the submatrix formed by the rows with indices in $X$ and
columns with indices in $Y$. The notation $A(X)$ refers to the submatrix of $A$ formed by the rows with indices in $X$ and all the columns.

\section{Prior Related Work}\label{sec:priorRelated}

This paper analyzes the VLSI complexity of polar encoders and decoders. It was recently discovered that the general technique of polar coding was first discovered by Stolte in \cite{stoltePhDThesis}, though these results were never published and the author did not conjecture that this construction reaches capacity. Arikan \cite{ArikanPolar} independently discovered this technique and proved that such codes can reach capacity. Our work in Sections \ref{sec:Arikan-Successive-Cancellation} and \ref{sec:Upper-Bounds-mesh-network} take inspiration from polar encoding and decoding graphs presented in the Arikan paper.

Our work in Section \ref{sec:Polar-Encoders-Lower} involves a lower bound for circuits that compute polar-encoding functions. The lower bounding technique comes from Thompson \cite{ThompsonThesis}. The key lemma needed is Lemma~\ref{lem:All-rectangle-pairs}, which is analogous to a property of the discrete Fourier transform (DFT) matrix proved by Valiant in \cite[Lemma 4]{valiant76} and by Tompa in \cite[Lemma 3]{tompaTimeSpaceTradeoffs}, though we use a different technique to derive this property.

In Section~\ref{sec:Arikan-Successive-Cancellation} we study the butterfly network graph proposed by Arikan \cite{ArikanPolar} for polar decoding. Our key lemma shows that the minimum bisection width of this graph's output nodes is $N$. This result is similar to the result of \cite{BornsteinBisectionButterfly} which shows that the minimum bisection width of \emph{all} the nodes the butterfly network graph is $2(\sqrt{2}-1)N+o(N)\approx 0.82 N$. Because of our circuit lower bounding technique, the minimum bisection width of the output nodes is required, and not all the nodes of the graph, motivating our approach.

In Section~\ref{sec:Upper-Bounds-mesh-network} we show how a mesh network can achieve our encoding and decoding energy lower bounds up to polylogarithmic factors. A mesh network DFT algorithm was proposed by Stevens \cite{StevensFourierSubroutine} and shown by Thompson \cite{ThompsonThesis} to reach the DFT VLSI complexity lower bounds.

There have been a number of papers on practical VLSI implementations of polar encoders and decoders \cite{DizdarArikanPolarCodeImplementation, BalatsoukasRaymondGrossBurg,AlamdarKschischang,lerouxTalVardyGrossPolar}, though a theoretical analysis of how the energy of such circuits scale has not been performed. However, these results show that practical polar coding circuits compete well with other error control codes, motivating our theoretical analysis.

\section{Computational Model\label{sec:Computational-Model}}

The model we will use in this paper, which we call the Thompson VLSI model, is adapted from Thompson in \cite{ThompsonThesis}. The precise
model we will use is defined in \cite{blakeConstantPePaper}, with a few minor differences. In the previous model, lower bounds were presented in terms of wire width and a technology constant. In this paper, since we are concerned with scaling rules, to avoid unnecessary notation, we will let these constants be $1$. As well, in this paper, we let the symbol $q$ represent the switching activity factor (that is, the fraction of the circuit that is active on average per clock cycle). In the previous paper $q$ was implicitly $1$. The key circuit parameters we will use are $A$, the circuit area, and $T$, the number of clock cycles. Then, the circuit energy is given by $E=qAT$.

  Note that in this model circuit nodes can be considered
the vertices of a graph, and in a circuit's graph two edges connect
a vertex if and only if there is a wire between the two corresponding
nodes.

\begin{defn}
A\emph{ bisection} of a set of vertices $X$ of a graph $G=\left(V,E\right)$
is a set of edges such that their removal bisects the vertices $X$;
that is, they divide the graph into two disconnected components with
vertices $V_{1}$ and $V_{2}$ such that $\left|\left|X\cap V_{1}\right|-\left|X\cap V_{2}\right|\right|\le1$.
The \emph{minimum bisection width} (MBW) of a set of vertices $X$ is the
size of the bisection of these vertices that is minimal over all such
bisections.
\end{defn}
An important lemma relates the minimum bisection width of a graph
to its circuit area:
\begin{lem}[Thompson]\label{lem:ThompsonLemma} All circuits whose
corresponding graph has MBW $\omega$ have area
bounded by:
\[
A\ge\frac{\omega^{2}}{4}.
\]
\end{lem}
\begin{IEEEproof}
See \cite{ThompsonThesis}.\end{IEEEproof}
\begin{defn}
A \emph{coding scheme} is a sequence of error control codes of increasing
block length $N$, together with a sequence of \emph{encoding circuits}
and \emph{decoding circuits.} It is associated with a particular channel.
\end{defn}
Let $P_{\mathrm{e}}(N)$ be the block error probability for the code in the scheme with block length $N$. Then we can define the following:
\begin{defn} \cite{blakeKschischangEnergyLatencyReliabilityTradeoffs}
An $f(N)$-coding scheme is a coding scheme in which for sufficiently
large $N$, $P_{\mathrm{e}}(N)\le f(N)$.

Note that this definition classifies coding schemes in terms of their
block error probabilities. A ``good'' coding scheme should thus
have this $f(N)$ scale quickly to $0$. Using the result of \cite{ArikanTeletareRateOfPolarization}
we can see that for every $\epsilon>0$, there exists an $e^{-N^{1/2-\epsilon}}$-
coding schemes using polar codes.
\end{defn}

\section{Polar Encoders Lower Bound\label{sec:Polar-Encoders-Lower}}

In this section we will prove that all polar encoders of rate greater
than $1/2$ must have energy that scales as $\Omega\left(N^{3/2}\right)$.
The main technical result will be Lemma \ref{lem:All-rectangle-pairs},
in which we show a property about the rank of rectangle
pairs of the polar encoding generator matrix.

\subsection{Rectangle Pairs}
We will consider an $N\times N$ matrix $G$. We let $R,C\subseteq[N] $.
\begin{defn}
Let $G(R,C)$ be the submatrix of $G$ formed by selecting the rows
with indices in $R$ and the columns with indices in
$C$. We call such an object a \emph{rectangle} of $G$.\end{defn}
\begin{example}
\label{exa:RectangleExample}Let
\[
G=\left[\begin{array}{cccc}
1 & 2 & 3 & 4\\
5 & 6 & 7 & 8\\
9 & 10 & 11 & 12\\
13 & 14 & 15 & 16
\end{array}\right],R=\left\{ 1,3\right\} ,C=\left\{ 2,4\right\}
\]
 then
\[
G\left(R,C\right)=\left[\begin{array}{cc}
2 & 4\\
10 & 12
\end{array}\right].
\]
\end{example}
\begin{defn}
If $A\subseteq [N] $, we let the \emph{relative complement} of $A$ be
$\bar{A}=[N] \backslash A$, that is, those
elements in $\left\{ 1,2,\ldots N\right\} $ that are not in $A$.
The relevant value of $N$ will depend on context, and when in doubt
will be specified clearly.
\end{defn}
Again, let $R,C\subseteq\left\{ 1,2,\ldots,N\right\} $ and $G$ be
an $N\times N$ matrix.
\begin{defn}
A\emph{ rectangle pair} is an ordered pair of submatrices of a given
matrix $G$, associated with two sets $R$ and $C,$ defined as $\left(G(R,C),G(\bar{R},\bar{C})\right)$.\end{defn}
\begin{example}\label{exa:rectanglePair}
If $G,$$R,$ and $C$ are defined as in Example~\ref{exa:RectangleExample},
then the rectangle pair associated with $R$ and $C$ is:

\[
\left(\left[\begin{array}{cc}
2 & 4\\
10 & 12
\end{array}\right],\left[\begin{array}{cc}
5 & 7\\
13 & 15
\end{array}\right]\right)
\]

\end{example}

We shall also define:
\begin{defn}
	A \emph{$k$-row-reduced rectangle pair} of a matrix $G$ is an ordered
	pair of matrices $(X,Y)$. It is formed by starting with any rectangle
	pair $(A,B)$ of $G$ and deleting $a$ rows from $A$ to form
	$X$ and $b$ rows from $B$ to form $Y$ such that $a+b=k$.\end{defn}
\begin{example}
	A $1$-row-reduced rectangle pair of the matrix $G$ from Example~\ref{exa:rectanglePair} is
	\[
	\left(\left[\begin{array}{cc}
	10 & 12\end{array}\right],\left[\begin{array}{cc}
	5 & 7\\
	13 & 15
	\end{array}\right]\right).
	\]
	which is formed by deleting a row from the first matrix in the rectangle
	pair
	\[
	\left(\left[\begin{array}{cc}
	2 & 4\\
	10 & 12
	\end{array}\right],\left[\begin{array}{cc}
	5 & 7\\
	13 & 15
	\end{array}\right]\right)
	\]
	of $G$.\end{example}
We will consider the structure of the polar encoding matrix by considering
its rectangle pairs.

\subsection{Universal Polar Coding Generator Matrix Properties}
\begin{defn}\label{def:recursiveFn}
The \emph{universal polar coding generator matrix}  $G_{n}$ is a matrix defined recursively
by Arikan \cite{ArikanPolar}. Let:
\[
F_{1}=\left[\begin{array}{cc}
1 & 0\\
1 & 1
\end{array}\right]
\]
and
\[
F_{n}=\left[\begin{array}{cc}
F_{n-1} & 0\\
F_{n-1} & F_{n-1}
\end{array}\right].
\]
Then
\[
G_{n}=B_{n}F_{n}
\]
where $B_{n}$ is a permutation matrix interpreted as the bit-reversal
operator.
\end{defn}
The structure of $B_{n}$ (other than it being a matrix that permutes
the rows of $F_{n}$) will not matter in the proofs that follow.

We will prove a theorem showing that the sum of the ranks (over the
field $\mathbb{F}_{2}$) of the entries of any rectangle pair of $G_{N}$ is
at least $N/2$. This will imply high VLSI complexity for sufficiently
high rate VLSI polar encoders.

We will first consider the ranks of rectangle pairs of $F_{n}$. Note
that $F_{n}$ and $G_{n}$ are $N\times N$ matrices, where $N=2^{n}$.
\begin{lem}
	\label{lem:LemmaForRecursion}Let $X$ be a matrix with entries
	in a field partitioned as
	\[
	X=\left[\begin{array}{c|c}
	A & 0\\\hline
	C & B
	\end{array}\right],
	\]
	where $0$ is a zero submatrix.

	Then $\rank(X)\ge \rank(A)+\rank(B)$.\end{lem}
\begin{IEEEproof}
	There are $\rank(A)$ linearly
	independent rows of $A$, and $\rank(B)$ linearly independent rows
	of $B$. The $\rank(A)+\rank(B)$ rows of $X$ corresponding to these rows are also linearly independent.
\end{IEEEproof}

\begin{lem}
\label{lem:All-rectangle-pairs} All rectangle pairs $\left(A_{n},B_{n}\right)$
of $F_{n}$ have $\rank(A_{n})+\rank(B_{n})\ge\frac{N}{2}$.
\end{lem}
\begin{IEEEproof}
We will use mathematical induction. Note that \[F_{1}=\left[\begin{array}{cc}
1 & 0\\
1 & 1
\end{array}\right],\]
and checking all the possible rectangle pairs $\left(A_{1},B_{1}\right)$
of $F_{1}$ we have that $\rank(A_{1})+\rank(B_{1})\ge1=\frac{N}{2}$.
Now, we assume that for all $k\le n-1$, for all rectangle pairs of
$F_{k}$ denoted $(A_{k},B_{k})$:
\begin{equation}
\rank(A_{k})+\rank(B_{k})\ge\frac{2^{k}}{2}.\label{eq:inductionHypothesis}
\end{equation}

Consider a rectangle pair $\left(A_{n},B_{n}\right)$ of $F_n$. Note that $A_{n}$ can be written as:
\begin{equation}
A_{n}=\left[\begin{array}{cc}
P & 0\\
Q & S
\end{array}\right].\label{eq:AnNotCompact}
\end{equation}
and $B_n$ can be written as:
\[
B_{n}=\left[\begin{array}{cc}
L & 0\\
M & J
\end{array}\right].
\]
where $(P, L)$ and $(S, J)$ are rectangle pairs of $F_{n-1}$.

Observe that, by Lemma~\ref{lem:LemmaForRecursion}
\begin{equation}
\rank(A_{n})\ge \rank(P)+\rank(S)\label{eq:rankOfAn}
\end{equation}
and
\begin{equation}
\rank(B_{n})\ge \rank(L)+\rank(J).\label{eq:rankOfBn}
\end{equation}
Since $(P,L)$ and $(S,J)$ are rectangle pairs of $F_{n-1}$, by the induction hypothesis (\ref{eq:inductionHypothesis}):
\begin{equation}
\rank(P)+\rank(L)\ge\frac{N}{4}\label{eq:rankLplusrankP}
\end{equation}
and
\begin{equation}
\rank(S)+\rank(J)\ge\frac{N}{4}.\label{eq:rankJplusrankT}
\end{equation}
Thus, by combining (\ref{eq:rankOfAn}) and (\ref{eq:rankOfBn}):
\begin{eqnarray*}
	\rank(A_{n})+\rank(B_{n}) & \ge\\
	\rank(P)+\rank(S)+\rank(L)+\rank(J)
\end{eqnarray*}
By rearranging the right side of this inequality and directly substituting the bounds of (\ref{eq:rankLplusrankP}) and (\ref{eq:rankJplusrankT}) we get:
\[
\rank(A_{n})+\rank(B_{n})\ge\frac{N}{4}+\frac{N}{4}=\frac{N}{2}.
\]
\end{IEEEproof}
\begin{cor}
\label{cor:sumOfRanksOfGn}For any rectangle pair of $G_{n}$ denoted
$(A,B)$:
\[
\rank(A)+\rank(B)\ge\frac{N}{2}.
\]
\end{cor}
\begin{IEEEproof}
This Corollary follows by observing that \cite{ArikanPolar} $G_{n}=B_{n}F_{n}$
where $B_{n}$ is a permutation matrix that permutes the rows of $F_{n}$.
For every rectangle pair of $F_{n}$ there is an equivalent rectangle
pair of $G_{n}$, selected by choosing the same columns and choosing
the rows as permuted by $B_{n}$. The rectangles forming such a rectangle
pair will have the same rows, simply permuted. Thus they have the
same row space and thus the same rank.
\end{IEEEproof}

\subsection{Encoder Circuit Lower Bounds}
We consider below a circuit that computes a polar encoding function.
Such a function is associated with a set $\mathcal{A}$ of free indices. We
denote the vector of free indices $u({\mathcal{A}})\in\{0,1\}^{\left|\mathcal{A}\right|}$.
It is also associated with a vector of frozen indices $u({\bar{\mathcal{A}}})\in\{0,1\}^{N-\left|\mathcal{A}\right|}$.
\begin{defn}\cite{ArikanPolar}
A\emph{ polar encoding function} $f:\{0,1\}^{\left|\mathcal{A}\right|}\rightarrow\{0,1\}^{N}$
associated with free indices $\mathcal{A}$ and frozen vector $u(\bar{\mathcal{A}})$
is defined as
\[
f(u(\mathcal{A}))=u(\mathcal{A})G_{n}(\mathcal{A})+u(\bar{\mathcal{A}})G_{n}(\bar{\mathcal{A}})
\]
where $G_{n}(\mathcal{A})$ is the submatrix of $G_{n}$ formed by
the rows with indices in $\mathcal{A}$, and addition is performed in $\mathbb{F}_2^N$. Such a function is an encoding
function for a code with block length $N=2^{n}$ and rate $R=\frac{\left|\mathcal{A}\right|}{N}$.
\end{defn}

\begin{thm}\label{encodingLowerBoundTheorem}
The area $A$ and the number of clock cycles $T$ for a circuit that
computes a polar encoding function of rate $R$ greater than $\frac{1}{2}$
has area $A$ and number of clock cycles $T$ bounded by

\begin{equation}
AT^{2}\ge\frac{N^{2}\left(1-2R\right)^{2}}{64}=\Omega\left(N^{2}\right)\label{eq:ATsquaredBound}
\end{equation}
and, if such a circuit has switching activity factor $q$, its energy is bounded by
\begin{equation}
E\ge q\frac{N^{3/2}(1-2R)}{8}=\Omega\left(N^{3/2}\right).\label{eq:ATbound}
\end{equation}
\end{thm}
\begin{IEEEproof}
We will follow a similar line of reasoning used by Thompson in analyzing
the complexity of Fourier transform circuits \cite{Thompson}. There
are $N$ output bits of the encoder. We label the indices
of the output nodes on one side of the bisection $L$ (the left side),
and the others $R$ (the right side). The subcircuit containing the
output nodes $L$ will have some inputs bits, labelled
$L_{i}$. Similarly, label the input bits on the right side $R_{i}$.
We denote the vector of inputs on the left side $u(L_i)$, on the right side $u(R_i)$, and the frozen vector $u(\bar {\mathcal A})$.
By simply expanding the vector matrix multiplication, we see that
the left side of the circuit must compute the vector:

\begin{eqnarray*}
	y(L) & = & u(L_{i})G_{n}(L_{i},L)+u(R_{i})G_{n}\left(R_{i},L\right)\\
	&  & +u(\bar{\mathcal{A}})G_{n}\left(\bar{\mathcal{A}},L\right)
\end{eqnarray*}
and similarly the right side must compute the vector:
\begin{eqnarray*}
	y(R) & = & u(L_{i})G_{n}(L_{i},R)+u(R_{i})G_{n}\left(R_{i},R\right)\\
	&  & +u(\bar{\mathcal{A}})G_{n}\left(\bar{\mathcal{A}},R\right).
\end{eqnarray*}
The subcircuits must compute these values only with the input bits
injected into their own input nodes and the bits communicated to them
from the other subcircuit (which of course has access to the other input
nodes). Note that
$\left(G_{n}\left(R_{i},L\right),G_{n}(L_{i},R)\right)$ is an
$\left|\bar{\mathcal{A}}\right|$-row-reduced rectangle pair of $G_{n}$.
Observe from Corollary~\ref{cor:sumOfRanksOfGn} that the sum of the
ranks of these matrices must be at least
$\frac{N}{2}-\left|\bar{\mathcal{A}}\right|=\frac{N}{2}-(1-R)N$, which is greater than $0$ because $R>1/2$.  Thus,
at least $\frac{N}{2}-(1-R)N$ bits must be communicated across this
bisection during the computation. If the circuit has MBW of output bits $\omega$, since
at each clock cycle at most $2\omega$ bits can be communicated across
the bisection:
\begin{equation}
T\ge\frac{\frac{N}{2}-(1-R)N}{2\omega}.\label{eq:TboundInTermsOfOmega}
\end{equation}
By Lemma~\ref{lem:ThompsonLemma}, we have $A\ge\frac{\omega^{2}}{4}$
and thus, combining this with (\ref{eq:TboundInTermsOfOmega})
implies
\begin{equation}
AT^{2}\ge\frac{N^{2}\left(2R-1\right)^{2}}{64}.\label{eq:ATsquaredbound}
\end{equation}
Also note that
\[
A\ge N
\]
and thus, combining this inequality with (\ref{eq:ATsquaredbound}) and taking the square root we get
\[
E=qAT\ge q\frac{N^{1.5}(2R-1)}{8}.
\]

\end{IEEEproof}

\section{Arikan Successive Cancellation Polar Decoding Scheme\label{sec:Arikan-Successive-Cancellation}}

In Arikan's original paper on polar coding \cite{ArikanPolar}, the
author presented a Turing-time complexity $O(N\log N)$ algorithm
for computing successive cancellation decoding of polar codes. In
this section, we provide a definition of a polar decoder based on
Arikan's \cite{ArikanPolar} paper, and show that such circuits, when
implemented with output nodes arranged in a rectangular grid, take
energy at least $\Omega(N^{3/2})$.

\subsection{Decoding Complexity Lower Bound}

Below we consider a generalization of the minimum bisection width
of a set of vertices, where instead of dividing the set of vertices
into two sets of equal size, instead we divide the vertices of a set
into two sets, where the size of one of these sets is fixed.
\begin{defn}
Given a graph $G=\left(V,E\right)$, an $m$\emph{-partition} of a
set of vertices $X\subseteq V$ is an ordered pair $(A,V\backslash A)$
in which $A\subseteq V$ and $\left|A\cap X\right|=m$. The \emph{width}
of this partition is the size of the set of edges connecting the vertices
in $A$ with $V\backslash A$. The $m$\emph{-section width} of a
set $X$ of vertices of a graph $G$ is the minimum width over all
the graph's $m$-partitions of $X$.

In Figure~\ref{fig:mSectionWidth} we give an simple example of a $2$-partition of a
subset of edges of a graph.

\begin{figure}
	\centering
	\includegraphics{mSectionWidth}
	\caption{Example of a graph with a $2$-partition of the shaded nodes.
		The labelled partitioning line is also a $1$-partition of the white
		nodes. Inspection shows that such $m$-partitions are minimal. Therefore,
		the $2$-section width of the shaded nodes in this graph is $2$,
		as is the $1$-section width of the white nodes. } \label{fig:mSectionWidth}
\end{figure}

\end{defn}
Note that if a graph $G=(V,E)$ has $2m$ vertices, then the $m$-section
width of $V$ is the same as the graph's minimum bisection width.
\begin{defn}
An $n$\emph{-polar decoding graph,} denoted $P_{n}$, is a generalization
of the graph presented by Arikan in \cite{ArikanPolar} describing
the communication graph of a polar decoding algorithm. It is defined
recursively in Figures \ref{fig:decoderGraphBase} and \ref{fig:decoderGraph}. For the base case, the $1$-polar decoding
graph is the bowtie shaped graph given in Figure~\ref{fig:decoderGraphBase}. An $n$-polar
decoding graph consists of $2^{n}$ nodes called \emph{symbol nodes}
connected to two copies of the $\left(n-1\right)$-polar decoding
graphs as shown in Figure~\ref{fig:decoderGraph}.
\end{defn}
\begin{figure}
	\centering
	\includegraphics{P1DecodingGraph}
	\caption{The base case: the decoding graph $P_{1}$.} \label{fig:decoderGraphBase}
\end{figure}

\begin{figure}
	\centering
	\includegraphics[width=2.8 in]{decoderGraph}

	\caption{A diagram of the recursive structure of a polar decoding
		graph $P_{n}$. The vertices on the left (outlined in a shaded ellipse and labelled $A$) indicate the symbol nodes
		of the graph. The vertices on the right in the two boxes indicate
		the symbol nodes of the two subgraphs (outlined and labelled $B$ and $C$) which are the smaller polar
		decoding graphs $P_{n-1}$.  An example of a
		subgraph that is a bowtie is indicated with edges drawn with a thick,
		dashed line.
		} \label{fig:decoderGraph}
\end{figure}

We shall study the structure of an $m$-partition of a polar decoding
graph.

We call the nodes in the left-most column in the graph of Figure~\ref{fig:decoderGraph} \emph{symbol nodes}. Note that for any $n$-polar decoding graph, there exist $2^{n}$
symbol nodes, as well as symbol nodes of the two $(n-1$)-polar decoding
subgraphs that form the graph. Let the set of symbol nodes of the
larger graph be labelled $A$, the symbol nodes of one of the subgraphs
be $B$, and the other symbol nodes $C$. This labelling of sets is visible in Figure~\ref{fig:decoderGraph}.

Note by inspection that that the bipartite subgraph connecting the
nodes of $A$ with $B\cup C$ consists of \emph{bowties}, subgraphs
containing two vertices from $A$ and a vertex from $B$ and $C$.
An example bowtie is labelled in Figure~\ref{fig:decoderGraph}. A bowtie object
is a subgraph of the polar decoding graph associated with a particular partition. We classify
these bowties according to how the particular partitioning line divides the nodes in the graph.

We now consider a minimum $m$-partition of $A$. Such a partition divides the set of vertices into
two subsets, which we will call the top half and the bottom half.
We can consider how the $2^{n-1}$ bowties connecting $A$ with $B$
and $C$ are split by the $m$-partition. We divide such bowties into
three categories: split bowties, contained bowties, and crossing bowties.
\begin{defn}
A \emph{split bowtie} is a bowtie in which one element of $A$ is
in the upper half, and one in the lower half. Two examples are given in Fig.~\ref{fig:splitBowties}.
\end{defn}
Note that a split bowtie has $2$ edges crossing the $m$-partition.

\begin{figure}

	\begin{subfigure}{0.38\textwidth}
		\includegraphics[width=1.5 in]{splitBowties}\includegraphics[width=1.5 in]{splitBowties2}
		\caption{Two examples of split bowties. Split bowties are bowties in which the two nodes in $A$ are on opposite sides of the partition line. It does not matter where the other nodes lie.} \label{fig:splitBowties}
	\end{subfigure}

	\begin{subfigure}{0.38\textwidth}
		\centering

		\includegraphics[width=1.5 in]{containedBowtie}
		\caption{An example of a contained bowtie. Such a bowtie occurs when all the
			nodes of a bowtie are on the same side of the partition. } \label{fig:containedBowtie}
	\end{subfigure}
	\begin{subfigure}{0.38\textwidth}
\centering
		\includegraphics[width=1.5 in]{crossingBowtie1}\includegraphics{crossingBowtie2}
		\caption{Two examples of crossing bowties. In such bowties the two nodes in $A$ are on the same side of the partition, and at least one of the other nodes in the bowtie is on the other side.} \label{fig:crossingBowties}
	\end{subfigure}
	\caption{Diagrams of split, contained, and crossing bowties. Note that a bowtie is an object associated with a polar decoding graph and a particular partition. In each figure, the nodes labelled $a_1$ and $a_2$ are nodes from the set $A$. Similarly, the nodes labelled $b_1$ are nodes from the set $B$ and those labelled $c_1$ are from the set $C$. The dashed line indicates the relative position of the partitioning line.} \label{fig:1}
\end{figure}

\begin{defn}
A \emph{contained bowtie} is one in which all vertices are either
in the top or bottom half. An example is given in Figure~\ref{fig:containedBowtie}.
\end{defn}
Note that a contained bowtie has no edges crossing the $m$-secting
cut.
\begin{defn}
A \emph{crossing bowtie has two nodes of $A$ on  one side of the
partition line, and at least one of the nodes in $B$ or $C$ on the
other side of the partition line.}
\end{defn}
It should be clear that for any partition of the polar decoding graph, all bowties are either split, contained, or crossing bowties.

We let $G$ be an arbitrary polar decoding graph.
\begin{lem}
\label{lem:OnlySplitandcontainedbowties}Consider an $n$-polar decoder
graph, and let $0\le m\le2^{n-1}$. Such a graph has a minimum $m$-section
partition of the symbol nodes of $G$ which contains only split bowties
and contained bowties.\end{lem}
\begin{IEEEproof}
We provide an exchange argument. For a particular minimal $m$-partition, we argue that nodes in a crossing bowtie can be moved to another side, resulting in a contained bowtie without increasing the number of edges crossing the partition line.  By examining the left side of Figure~\ref{fig:crossingBowties}, there are $4$ edges crossing the partition
line. For crossing bowties of this type, moving vertices $b_1$ and $c_1$ to the side containing the vertices in $A$ decreases the
edges of this bowtie crossing the partitioning line by $4$. The degree
of any vertex in this graph is at most $4$, thus this can, at worst,
result in $4$ new edges crossing the partition (which would result
from the two extra edges each on vertices $b_1$ and $c_1$ now crossing
the partition line). A similar argument can be made for crossing bowties
like those in the right side of Figure~\ref{fig:crossingBowties}. Thus, any minimum $m$-section partition of the output
nodes containing crossing bowties can be modified to one that contains
no crossing bowties.
\end{IEEEproof}
We shall prove a lemma regarding the $m$-section width of an $N$-polar
decoding communication graph.
\begin{lem}
\label{lem:LemmamSectionWidth}Let $0\le m\le2^{n-1}$. Then the $m$-section
width of the symbol nodes of an $n$-polar decoding graph is at least
$2m$.\end{lem}
\begin{IEEEproof}
We shall prove this by induction. For the base case, the $n=1$ polar
decoding graph given in Figure~\ref{fig:decoderGraphBase} can be shown by inspection to satisfy
the lemma by simply checking the width of all $0$ and $1$-partitions.

We shall assume that the $m$-section width, where $0\le m\le2^{k-2}$
, of a $\left(k-1\right)$-polar decoding graph is $2m$.

We consider a minimal $m$-partition that contains only split and contained bowties that exists by Lemma~\ref{lem:OnlySplitandcontainedbowties}. Denote one half of the partition
the upper half and the other the lower half. Without loss of generality
we assume the upper half contains $m$ nodes of $A$.  Let the number
of contained bowties in the upper half be $C_{\mathrm{upper}}$, and
the number in the lower half $C_{\mathrm{lower}}$. Let the number
of split bowties be $S$. Since the upper half contains $m$ nodes
of $A$, then
\begin{equation}
2C_{\mathrm{upper}}+S=m.\label{eq:mInTermsOfCupperandS}
\end{equation}
Note that the number of contained bowties on the lower half must at least equal the number on the upper half, since the number of symbol nodes on the lower half must equal or exceed the number in the upper half. Thus, there must be at least $m$ elements of $B$ and $m$ elements of $C$ on both side of the partition. As well,   at least one of these sides cannot have more than $N/4$ elements (since each of these sets contains only $N/2$ elements in total). Thus, there is an
$x$-partition of both $B$ and $C$ induced by the partition, where
$C_{\mathrm{upper}} \le x\le N/4$.  Thus, each of these partitions must have
at least $2C_{\mathrm{upper}}$ edges crossing the partition line
by the induction hypothesis. In addition, there are $2$ edges crossing
the partition line for each split bowtie (easily observed by inspecting
Figure~\ref{fig:splitBowties}). Thus, the number of edges crossing the partition line
is at least
\[
\mathrm{Edges\ crossing}\ge4C_{\mathrm{upper}}+2S=2m
\]
where we have applied (\ref{eq:mInTermsOfCupperandS}), proving the theorem.\end{IEEEproof}

We will consider algorithms whose communication graph is based on the polar decoding graph. However, bits corresponding to certain symbol nodes which are frozen obviously do not need to have their own node in a communication graph. Thus we consider a frozen-bit polar decoding graph.

\begin{defn} An  $n$-\emph{frozen bit polar decoding graph} associated with frozen bit indices $\mathcal{\bar{A}}$ is a graph obtained by deleting the symbol nodes corresponding to   $\mathcal{\bar{A}}$ from $P_n$ and also the edges to which they are connected. The symbol nodes that remain are called the \emph{unfrozen nodes}. Such a graph is a decoding graph for a rate $R=1-\frac{|\mathcal{\bar{A}}|}{N}$ code.
	\end{defn}
	Note that this is a natural simplification of the polar decoding graph once frozen bits are considered. However, this is not the only possible simplification. In this paper we only consider simplifications that involve deletion of the nodes corresponding to the frozen bits.

	Once the symbol nodes corresponding to frozen bits are deleted, we then consider the bisection width of the remaining symbol nodes.

\begin{cor}\label{cor:unfrozenSymbolNodesMBW} The minimum bisection width $\omega$ of the unfrozen nodes of any $n$-frozen bit polar decoding graph in which $R>2/3$ is at least:
	\[ \omega \ge N(3R-2)
	\]
	\end{cor}
\begin{IEEEproof}
	Suppose not. Then, consider the unfrozen symbol nodes minimal bisection with $W<N(3R-2)$ nodes crossing it. Now, add the frozen symbol nodes and their edges back to this graph. There are at most $(1-R)N$ such nodes to be added, and thus they can increase the number of edges in the graph by at most $2(1-R)N$. At most all these edges can cross the partition line, and thus this partition line can have at most $W+2(1-R)<RN$ edges crossing it. Note that the partition line forms an $m$-partition of all the symbol nodes, where $m\ge RN/2$, But, by Lemma~\ref{lem:LemmamSectionWidth}, any such $m$-partition must have at least $RN$ edges crossing it, resulting in a contradiction.
	\end{IEEEproof}

\subsection{Decoder VLSI Lower Bounds}

 Note that a Thompson circuit
is associated with a graph. In the course of a computation, messages
will be passed from node to node in the circuit. Each binary message
passed corresponds to another edge in the computation's \emph{communication
graph}. We will define a polar decoder (a type of circuit) in terms
of a circuit's communication graph.

 We first define contracting vertices
and subdividing edges.
\begin{defn}
Any two vertices of a graph $u$ and $v$  can be \emph{contracted} by joining two vertices
together, resulting in a new vertex $v'$. The vertex $v'$ will have all the edges corresponding to both $u$ and $v$ with the exception of any edges that joined $u$ and $v$ in the original graph, which are deleted.
\end{defn}

\begin{defn}
	An edge of a graph can be \emph{subdivided} by being replaced by two edges with a vertex in the middle.
\end{defn}

Consider a frozen polar decoding graph. Such a graph has $RN$ symbol nodes. Now, consider a process in which vertices and edges are added to this graph, and some edges are subdivided and some vertices are contracted, but no two symbol nodes are contracted.

\begin{defn}
	Such a graph is called a \emph{polar decoding communication graph}. Obviously, such a graph has $RN$ symbol nodes, which are the nodes that correspond to the symbol nodes of the original frozen polar decoding graph. We call these nodes the graph's \emph{output nodes.}
\end{defn}

\begin{lem}
\label{lem:mergingOutputNodes} All polar decoding communication graphs obtained from a rate $R>2/3$ frozen polar decoding graph have minimum bisection width of output nodes at least $N(3R-2)$.
\end{lem}
\begin{proof}
	First, observe from Corollary~\ref{cor:unfrozenSymbolNodesMBW} that the minimum bisection width of the symbol nodes of the original frozen polar decoding graph is at least $N(3R-2)$. Suppose that the polar decoding communication graph obtained from this graph has minimum bisection width less than this. Then consider the partition with $W<N(3R-2)$ edges crossing the partition line. We can reverse the operations that obtained the the communication graph and this can only decrease the number of edges crossing the partition line, resulting in a bisection of less than $N(3R-2)$ for the original frozen polar decoding graph, a contradiction.
	To see this, consider what happens when a vertex $v'$ that was contracted has this operation reversed, resulting in two vertices with $u$ and $v$ with (possibly) an edge between them. Place $u$ and $v$ on the same side of the partition previously occupied by $v'$. It is then obvious that any edge between them cannot increase the width of this partition. It is also obvious that deleting any vertices and edges that were added can only decrease the the number of edges crossing the partition line. The same is true for reversing a subdividing process.
\end{proof}

\begin{defn}
	An \emph{Arikan polar decoding circuit} is a circuit whose associated communicaiton graph is also a polar decoding communication graph.
\end{defn}

Note that in our model, a Thompson circuit is created by placing nodes and edges each in a grid of squares of side length $1$.  Consider placing a  grid of (possibly larger) squares with integer side length on top of any Thompson circuit and with sides aligned to the smaller grid of squares defining the VLSI circuit. Then each square in the grid will contain some output nodes.
\begin{defn}
	A \emph{rectangle grid output circuit} with $N$ output nodes is a circuit in which there is a grid of squares that can be placed upon the circuit, and there is a $\sqrt N \times \sqrt N$ array of larger grid squares, each which contains exactly one output node.
\end{defn}
\begin{example}
	The mesh network defined in Section~\ref{sec:Upper-Bounds-mesh-network} is an example of a rectangle grid output circuit.
\end{example}
We suspect that our scaling rule lower bounds for polar decoders would extend to implementations that are not necessarily rectangle grid output circuits, however for simplicity we only present our results for such circuits. A generalization of the following lemma to a broader class of circuits would be sufficient:

\begin{lem}\label{lem:rectangleMBWEnergyLemma}
All rectangle grid output circuits with $\Theta (N)$ output nodes
and with a communication graph with minimum bisection width $\omega$
have energy $E\ge\Omega\left(\omega \sqrt{N}\right)$.\end{lem}
\begin{IEEEproof}
See Appendix~\ref{app:uniformOutputRectangleMBWLemma}.\end{IEEEproof}
Note that the above lemma does not assume a constant switching activity factor.
\begin{thm}\label{decoderLowerBoundTheorem}
All rectangle grid output, Arikan polar decoding circuits
have energy that scales at least as $\Omega\left(N^{3/2}\right)$.\end{thm}
\begin{IEEEproof}
This flows directly from Lemma~\ref{lem:mergingOutputNodes}
and Lemma~\ref{lem:rectangleMBWEnergyLemma}.
\end{IEEEproof}
It is now trivial to observe that this lower bound
can be reached up to a polylogarithmic factor on a mesh network which we discuss in the Section~\ref{sub:Decoding-Mesh-Network}.

\section{Upper Bounds\label{sec:Upper-Bounds-mesh-network}}

\subsection{Mesh Network}

We will show that, up to polylogarithmic factors, the lower bounds
on the energy of polar encoding and decoding complexity can be reached.
The mesh network topology that we present to meet these bounds derives
from Thompson \cite{ThompsonThesis}.

\begin{figure}
	\centering
	\includegraphics[width=2.8 in]{meshNetworkDiagram}
	\caption{Diagram of a mesh network. A mesh network consists of a grid of $\sqrt N \times \sqrt N$ processor nodes, each with area that scales as $\Theta ( \log^2 N)$. Each node is connected to its at most $4$ neighbors with $\Theta (\log N)$  wires. } \label{fig:meshNetworkDiagram}
\end{figure}

A mesh network consists of a grid of processor nodes. Each processor node is capable of sending and receiving messages to
its adjacent nodes. As shown in Figure \ref{fig:meshNetworkDiagram}, each node has area that scales as $\Theta(\log^2 N)$, and consists of a processor and memory. The processor takes area that remains constant with increasing circuit size, so the amount of memory in each node can scale as $\Theta (\log^2 N)$. Each processor node must also contain instructions on what each node is to compute. The length of the instructions obviously cannot be longer than $O(\log^2 N)$. As is clear from the diagram, each processor node is connected to up to $4$ other processor nodes with $\Theta (\log N )$ wires.

A computation on a mesh network consists of a message-passing procedure and the computation that the nodes are to perform on the messages they receive.  A typical message consists of an \emph{address},
an encoding of the node to which the message is to be sent, and its
\emph{content}, the information meant to be sent. Since there are $\Theta(N)$ processor nodes, an addressing scheme with $\Theta (\log N)$ bits per address is sufficient. As well, a constant-sized message and the address of the node to which the message is to be sent can be passed between adjacent nodes in a single clock cycle, because the width of the wires connecting such nodes also scales as $\Theta(\log N)$. (Actually, messages with size that scales logarithmically in $N$ can be sent).

Multiple messages may be sent simultaneously in a mesh network, but in order for an algorithm to be \emph{valid} for a mesh-network, it
must be that no computational node is required to store more than
$O(\log^{2}N)$ bits in its memory. As well, for an algorithm to be valid, it must also avoid message-passing \emph{conflicts:}
two messages cannot be passed to the same node at the same time. Thus,
given a mesh-network algorithm, we must show that its message passing
order does not result in any conflicts.

In the section below we provide a message-passing procedure for computing
polar encoding.

\subsection{Encoding}

\begin{figure}
	\centering
	\includegraphics{encodingGraphv3}
	\caption{ Example of an encoding graph for $N=2^{3}=8$ taken directly
		from Arikan \cite{ArikanPolar}. The leftmost column of nodes are the input bits, sending their bits to to their adjacent nodes. Upon receiving these bits, the nodes in the second column compute the $\mod 2$ sum of their inputs, and then pass this result to their adjacent nodes. This procedure naturally suits
		implementation on a mesh network. Such encoding reaches the energy complexity
		lower bounds in polar encoding up to polylogarithmic factors.}
	\label{fig:encodingGraph}
\end{figure}

Arikan provides a method for computing polar encoding that naturally
lends itself to implementation on a mesh network. See Figure~\ref{fig:decoderGraph} for
a graphical representation of the Arikan method. In the Arikan method, the input nodes are on the left side of the graph. As well, for polar encoding, some of these nodes represent frozen bits. In the encoding algorithm, messages move left to right. The input nodes (and frozen bit nodes) first pass their bits to the node to which they are connected in the adjacent column of nodes. The nodes in this column proceed to compute the modulo $2$ sum of their inputs, and pass the result to their adjacent nodes on the right. This continues until the final column is reached, resulting in the codeword.

In our proposed mesh-network implementation, each of the $N$ processor nodes corresponds to a row of nodes in the encoding graph of Figure~\ref{fig:encodingGraph}. Obviously, if each message (which corresponds to an edge in the graph) is to be sent one-by one, such an order of the message-passing procedure would avoid conflicts and would be easily be implementable on a mesh network. (In fact, this is the way we propose to do decoding). However, much of the computation for encoding can be done in parallel.  We show in Appendix~\ref{app:procedudeAvoidsConflicts} how a constant fraction of the messages corresponding to edges connecting nodes in adjacent columns can be sent simultaneously in a way that avoids conflicts. We suspect that most sufficiently sparse communication graphs can be implemented on a mesh network in a way that avoids conflicts, however a general analysis of this is beyond the scope of this paper.

\subsection{Analysis of Mesh Network Encoding Algorithm Complexity}

Note that there at $\Theta(\log_{2}N)$ stages. Suppose the number
of clock cycles used by an individual node for reading an address and computing which direction to send its message is $t_{R}$. Suppose that
the complexity for computing parity of the received bit with the current
bit is $t_{P}$. At each stage, the number of hops between processor nodes is at most $O(\sqrt{N}$). There are $\Theta (\log N)$ stages.
Thus, the number of clock cycles required is
\[
T=\Theta\left(\log N\left(\sqrt{N}T_{\mathrm{R}}+T_{\mathrm{P}}\right)\right)
\]
The computation of parity can obviously be done in time $\Theta(1)$. The
routing requires computing which direction to ``send'' the message:
up, right, or left. This can easily be accomplished in $\Theta\left(\log N\right)$
time (that is, proportional to the length of the address).

The proposed algorithm also uses roughly the same fraction of node
each clock cycle, so we can assume for scaling rules the switching
activity factor ($q$) is constant. The area of such a circuit scales as $A=\Theta(\log^2 N)$.  Thus:

\[
E=qAT=\Theta(N^{3/2}\log^{4}N)
\]

\subsection{Decoding Mesh Network\label{sub:Decoding-Mesh-Network}}

Clearly, because of the requirement of successively computing each
estimate in polar decoding, asymptotically the number of clock cycles
for a polar decoding scheme must scale at least as $\Omega(N)$. A
fully parallel polar decoder thus must have area-time complexity at
least $\Omega(N^{2})$.

However, the algorithm proposed by Arikan \cite{ArikanPolar} that
takes time complexity $O(N\log N)$ can easily be implemented on a
mesh network. Each node of the mesh network corresponds to a row of
nodes of the graph in Figure~\ref{fig:decoderGraph}. As described by Arikan \cite{ArikanPolar}, a depth first message-passing procedure
between the nodes of the graph can compute the polar decoding in Turing time complexity
$O(N\log N)$. The distance between any two nodes in a mesh network
is not greater than $O(N^{1/2})$. Thus, decoding on a mesh network
takes $A=\Theta\left(N\log^{2}N\right)$ and $T=\Theta(N^{3/2}\log^{2}N)$,
where the algorithm takes $O(N\log N)$ steps, and $O(N^{1/2}\log N)$
time to do the message passing. Since a fully
parallel decoding algorithm requires only a single processing node
to be active at a given time, the switching activity factor of this
scheme scales as $\Theta\left(1/N\right)$. Thus the energy of the
computation scales as $E=O\left(N^{3/2}\log^{4}N\right)$.

\section{Generalized Polar Coding on a Mesh Network}\label{sec:generalizedOnMesh}
Arikan \cite{ArikanPolar} proposes a generalization of polar codes in which the generator matrix is no longer $G_1$ as defined in Section~\ref{sec:Polar-Encoders-Lower}. Hassani \emph{et al.} \cite{HassaniAlishahiUrbanke} analyze such schemes and show that there exist generating matrices in which for sufficiently large $N$, $P_\mathrm{N}\le e^{-n^{1-\epsilon}}$ for any $\epsilon >0$. That is, they are $e^{-n^{1-\epsilon}}$-coding schemes. By \cite[Theorem 1]{GroverInfoFriction}, such circuits must have bit-meters energy that scales as $E\ge \Omega (N^{3/2-\epsilon/2})$.  Both \cite{ArikanPolar} and \cite{HassaniAlishahiUrbanke} argue that such schemes have $O(N\log N)$ time complexity algorithms for decoding. When implemented on a mesh network, such algorithms would take energy complexity $\Theta(N^{3/2}\log^4 N)$ for the same reasons described in Section~\ref{sub:Decoding-Mesh-Network}. Thus, we can say that the general lower bounds can be almost reached for such close-to-exponential coding schemes (that is, within a factor of $N^\epsilon \mathrm{polylog}(N)$). Such a scheme would have a switching activity factor $q$ that scales as $\Theta (1/N)$. Such a circuit would take number of clock cycles that scales as $T=\Theta (N^{3/2}\log^2 N)$. Note however that the Thompson complexity analysis of \cite{blakeKschischangEnergyLatencyReliabilityTradeoffs} suggests a lower bound $T(N)$ of $\Omega (N^{1/2})$, and thus this method does not simultaneously reach these energy and time lower bounds.

We conjecture that the Thompson model lower bounds for time and energy of \cite{blakeKschischangEnergyLatencyReliabilityTradeoffs} for encoding can be reached with polar encoding up to an $N^\epsilon \mathrm {polylog}(N)$ factor for small $\epsilon$. This is because parallelization of the encoding procedure is possible. However, such a parallel algorithm must avoid conflicts on the mesh network, so proving this remains an open question.

\section{Energy Scaling as Function of gap to Capacity\label{sec:Energy-Scaling-as-function-gap-to-capacity}}
In this section, we consider how the energy of polar codes scales as
capacity is approached.\begin{defn}For a particular code, let $\chi=\frac{1}{1-\frac{R}{C}}$ be the \emph{reciprocal gap to capacity}. \end{defn}
Note that as rate approaches capacity, $\chi$ approaches infinity.

Guruswami \emph{et al.} \cite{GuruswamiXia} show that as a function
of reciprocal gap to capacity, the block length required
to achieve a set probability of block error $P_{\mathrm{e}}$ for
polar codes scale as $N=O\left(\chi^{\mu}\right)$
for some value $\mu$; that is, the block length scales polynomially
in the reciprocal gap to capacity. Hassani \emph{et al.} \cite{HassaniAlishahiUrbanke}
show that $3.55\le\mu\le6$. Goldin \emph{et al. }\cite{GoldinBurshtein}
improve the upper bound on $\mu$ to $5.7$ and Mondelli \emph{et
al. }\cite{MondelliHassaniUrbanke} further improve the upper bound
to $4.7$. These bounds, combined with Theorems~\ref{encodingLowerBoundTheorem} and \ref{decoderLowerBoundTheorem} and the discussion in Section~\ref{sec:Upper-Bounds-mesh-network} that bound energy of encoding and decoding in terms of $N$ by:
\[
\Omega\left(N^{1.5}\right)\le E_{\mathrm{comp}}\le O\left(N^{1.5}\log^{4}N\right)
\]
imply an obvious corollary.
\begin{cor}
	The energy for polar encoders with reciprocal gap to capacity $\chi$ and
	a set probability of block error, in which $C>\frac{1}{2}$, is bounded
	by:
	\begin{equation}
	\Omega\left(\chi^{5.325}\right)\le E_{\mathrm{comp}}\le O\left(\chi^{7.05}\log^{4}\left(\chi\right)\right)\label{eq:fractionOfCapacityLowerBounds}
	\end{equation}
	with decoding energy bounded similarly.
\end{cor}
 Note that polar codes are $e^{-N^{\frac{1}{2}-\epsilon}}$-codes
\cite{arikanTeletarRateofPolarization} for any $\epsilon>0$. We can apply
the well known general lower bound on block length of any code as a
function of fraction of capacity \cite{Strassen} of $N\ge\Omega
(\chi^2)$ and the general lower bound of
\cite[Theorem 1]{blakeKschischangEnergyLatencyReliabilityTradeoffs} to show that all $e^{-N^{\frac{1}{2}-\epsilon}}$-encoding and decoding schemes have energy bounded by:
\[
E\ge\Omega\left(N^{\frac{5}{4}-\epsilon}\right)\ge\chi^{2.5}
\]
When contrasted with the lower bounds of (\ref{eq:fractionOfCapacityLowerBounds}), this
illuminates a gap between general lower bounds and that which is achievable
through polar coding.

\section{Future Work\label{sec:Future-Work}}

Extending the lower bound results to polar codes with rates less than
$1/2$ for encoder lower bounds and less than $2/3$ for decoding lower bounds is an obvious area of future work. Moreover, we have not actually implemented the mesh network topology analyzed in Section \ref{sec:Upper-Bounds-mesh-network}, so this also remains an area of future work.

Our decoding lower bounds are for algorithms based on graphs obtained from the butterfly network decoding graph suggested by Arikan \cite{ArikanPolar}. Our lower bound does not necessarily include all decoders based on successive cancellation decoding for polar codes. A particular challenge for generalizing this result is in defining precisely what a circuit that performs a polar decoding algorithm actually is, and thus this remains an area of future work.

Currently, our results apply to polar codes as defined in \cite{ArikanPolar}. Arikan
also suggested that other matrices can be used to generate polar codes
with similar decoding and encoding complexity. Korada \emph{et al.
} \cite{KoradoSasogluUrbanke} showed that there exist matrices which
generate polar codes that have block error probability close to $O(2^{-N})$.
Our work in \cite{blakeKschischangEnergyLatencyReliabilityTradeoffs} shows that such codes necessarily have encoding and
decoding energy that scales as $\Omega\left(n^{1.5}\right)$, and
implementation over a mesh network as described in Section~\ref{sec:Upper-Bounds-mesh-network} allows
for this encoding and decoding in a way that scales as $O(n^{1.5}\mathrm{polylog}\left(n\right)$).
Thus, this means polar codes are energy-optimal over all exponentially
low probability of error decoders.

However, a full understanding of VLSI complexity of polar encoding
should relate the generator matrix to their asymptotic VLSI complexity,
including energy, time, and area tradeoffs. Our lower bound approach
here works because of the structure of the $G_{1}$ matrix, allowing
us to derive Lemma \ref{lem:LemmaForRecursion}. This lemma is used
in a key step in the inductive proof showing that polar encoding has
high VLSI complexity. However, this approach does not seem to extend to different
generator matrices; thus we cannot rule out that there are some polarizing
matrices with encoding energy that scales better than $\Omega(n^{1.5})$.
These may possibly come at the cost of higher error probability. For
engineering purposes, however, this may be a worthwhile tradeoff,
and the analysis of polar coding may be a tool to characterize achievable
coding schemes that reach different points in this fundamental tradeoff.

\section{Appendix 1}

\appendices{}

\renewcommand{\thesubsection}{\Alph{subsection}}

\section{}\label{app:uniformOutputRectangleMBWLemma}

\begin{IEEEproof}
	(Of Lemma~\ref{lem:rectangleMBWEnergyLemma})
	Note that across any bisection
	of the communication graph of a given circuit, there are at least $\omega$
	edges that cross that bisection, with total length at least $\omega$.
	We can construct a single bisection with a line through the middle
	of the nodes. Then we can construct another bisection by shifting
	this line left one unit, and sweeping in a parallel line from the
	right. Such a bisection has half the nodes in between the two lines and half the nodes outside the two lines.
	We can then shift these two lines left one unit again. We can
	do this on the order of $\sqrt{N}$ times and each time the edges
	crossing the bisecting lines must be at least $\omega$, and each
	time the bisecting lines are in a different position, thus for each
	bisection the parts of the lines that cross the bisecting lines are
	different. In total there must be at least $\Omega\left(\sqrt{N}\omega\right)$
	total distance of the lines and thus this amount of total energy.
\end{IEEEproof}

\section{Mesh Network Encoding Procedure}\label{app:procedudeAvoidsConflicts}

\begin{figure}
	\centering
	\includegraphics{meshNetworkLabelling}
	\caption{The "raster-scan ordering" proposed for the nodes $i=1$ to $16$ for an $N=16$ polar
		encoding circuit. Note that for general $N$ these may not fit perfectly
		on a square. In that case, we propose using dimensions that are as
		close to square-like as possible. In Appendix~\ref{app:procedudeAvoidsConflicts} we show that labelling nodes like this and applying our proposed message-passing procedure for polar encoding avoids conflicts and thus is valid.}
	\label{fig:meshNodeOrdering}
\end{figure}

We implement the message-passing procedure on a mesh network using $n=\log N$ stages, one stage for each pair of adjacent columns in the encoding graph of Figure~\ref{fig:encodingGraph}. Label the input nodes of the encoding graph in order, starting from the top, from $1$ to $N$. For each input node $i$ of the encoding graph, associate a mesh network processor node $i$. This processor node is to perform all the computations and message passings of the graph nodes in the same row as its associated input node. Place the processor nodes on the $\sqrt N \times \sqrt N$ mesh network in the order shown in Figure.~\ref{fig:meshNodeOrdering}. We call such an ordering a \emph{raster scan ordering}. Note that by inspecting Figure~\ref{fig:encodingGraph}, in the $j$th stage of the procedure, each processor node $i$ must pass messages to node $i-2^{n-j}$.

There is some ambiguity in our definition of the operation of the mesh network: when a message is received by a processor node, in which direction should the message be sent? It is clear that if the message is located "above and to the left" of the node, the message should be passed either to the left or above. We shall adopt the convention that a node shall choose the relevant up or down direction before deciding to send the node left or right, which occurs at what we will call the \emph{target row} (that is, the row containing the computational node to which the message is sent).

We can label each row of the mesh network, and thus some  nodes will be on even rows, and some nodes will be on odd rows. In our proposed procedure, each stage of the encoding will be divided into two message-passing steps: the "even-row" passing step and the "odd-row" passing step. More precisely, at the $j$th stage of the encoding procedure, only  nodes $i$ on even rows that are to send their bits  to node $i-2^{n-j-1}$ shall do so. Then, the appropriate nodes on odd rows are to do the same. We claim this procedure avoid conflicts (that is, no two messages will be sent to the same node simultaneously).

\begin{defn} A \emph{constant send-back procedure} is a message passing procedure defined on a mesh network with nodes labelled according to the raster-scan ordering in which a set of nodes, indexed $i$, each simultaneously send a message to node $i-m$, for some $m>0$.
	\end{defn}
The "even row" sending step and the "odd row" sending step of the procedure we propose for polar encoding is obviously a special case of this procedure.

\begin{lem} \label{lem:sameRowNoConflicts}
	In any constant send-back procedure, conflicts can only occur with messages originating on different rows.\end{lem}
\begin{IEEEproof}
	Consider two messages originating on the same row. Since our convention is to send nodes "up" until deciding to send them left or right, a conflict between these two messages can only occur on the target row in which one message is sent left, and the other sent right. However, because of the ordering of the processor nodes, and the fact that we are considering a constant send-back procedure, upon reaching the target row, these messages must be sent in the same direction, otherwise they are not addressed to nodes a constant value less than their index. If these nodes do not have the same target rows, then the lemma flows trivially.
\end{IEEEproof}
\begin{lem} \label{lem:2RowsApart}
	Messages originating on rows spaced at least $2$ rows apart cannot
	have the same target rows and can not conflict.\end{lem}
\begin{IEEEproof}
	Let $x$ be the number of processor nodes in each row.
	Clearly, the spacing between two nodes at least $2$ rows apart is at least $x+1$ (occurring
	when the lesser indexed node is at the far right, and the greater indexed
	node is on the far left). Suppose their target node was on the same
	row. The spacing between these two target indices must at least be $x+1$,
	but there are only $x$ elements on each row. Those, messages on rows spaced two or more apart cannot conflict in their target rows. It may be possible for them to conflict where one message has reached a target row, and is travelling left or right, and another is travelling up. However, the message travelling up must have originated on a row below the left or right-going node. In a constant send-back procedure such a message cannot have a target row at the same level or higher than the other node, so this cannot occur.
\end{IEEEproof}

Since in each step, at each stage of our proposed procedure, no two simultaneously sent messages originating on adjacent rows, combining Lemmas~\ref{lem:sameRowNoConflicts} and \ref{lem:2RowsApart} confirms that our proposed procedure has no conflicts.

This particular message passing
ordering is done entirely to prove that the area-time complexity \emph{scaling} of
this mesh scheme is close to the lower bound. It is likely
that in any practical implementation a more efficient message passing
procedure exists (though it will likely be more efficient only up to some
constant factor).

\bibliographystyle{IEEEtran}


\section{The Glass Transition and the Shear Penetration Depth}
\subsection{Solids, Liquids, and Supercooled Liquids}
Liquids flow, solids do not. This is the fundamental distinction between the two states of matter. If a force is applied to a liquid, its constituents will rearrange until a new equilibrium state is reached. By contrast, a solid will deform elastically under small stresses, but large scale atomic rearrangements will not occur. The fundamental physical variable that quantifies this difference is the viscosity, a measure of a material's resistance to flow. The viscosity of a liquid is finite, wheareas the viscosity of a perfect crystal is infinite. In futher contrast with a liquid, a crystalline solid is characterized by time-independent elastic and shear moduli. The elastic forces that resist deformation in response to applied stresses and thermal fluctuations in a crystalline solid, are a consequence of the long range structural order. This structural order is acquired at the uniquely defined melting point where there is a thermodynamic driving force for structural change: the free energy of the system decreases through macroscopic atomic ordering.

Just above the melting temperature, as the liquid is coooled, its viscosity increases and is well approximated by an Arrhenius law,
\begin{equation}
\label{Arrhenius}
\centering
\eta(T)=\eta_0 e^{\frac{E}{k_B T}} ,
\end{equation}
where $\eta_0$ is the extrapolated value of viscosity at infinite temperature, $E$ is a nearly constant function of T (playing the role of activation energy of atomic rearrangement), and $k_B$ is the usual Boltzmann constant. Eventually, when the liquid is cooled to its melting temperature, $T_m$, a first order phase transition occurs, and the liquid becomes a crystalline solid. This process requires a finite amount of time, the nucleation time, however, and can therefore be thwarted. If a liquid is cooled sufficiently quickly, crystallization can be bypassed and the liquid enters a metastable state known as the supercooled liquid. As a supercooled liquid is further cooled, its viscosity begins to increase in an incredible fashion, by up to 16 decades over a temperature window as small as a few hundred Kelvin. A "glass transition" temperature, labeled $T_g$, is eventually reached at which point the viscosity is so great (~$10^{13}$ Poise) that any large scale atomic rearragnement (flow) ceases on physically meaningful timescales (order of ~ 100s). On daily time-scales, beneath $T_g$, the supercooled liquid responds rigidly to external perturbations and is deemed a glass. If the viscosity of the supercooled liquid continued to increase in an Arrhenius fashion down to $T_g$, the glass transition would not have been so mysterious. In such a case, there would exist a constant energy barrier to local rearrangement that would become exponentially harder to cross as kinetic energy is removed from the supercooled liquid on cooling. The supercooled liquid wouldn't flow on experimentally meaningful timescales and the apparent rigidity would be entirely kinetic in origin. However, for all supercooled liquids, a departure from Arrhenius dynamics is observed. For all liquids, there is an apparent temperature dependence to the activation energy \cite{7,8}, and the degree of departure from an Arrhenius viscosity is quantified in the fragility parameter of Angell \cite{7}. Despite a wide and rich phenomenology that cannot be enumerated here \cite{1,2,3,4,5,6}, understanding the underlying physical mechanism of the so-called super-Arrhenius viscosity and the appearance of rigidity without long range order are the fundamental challenges of glass science.

\begin{figure*}
\centering
\includegraphics[width=1 \columnwidth, height= .4 \textheight, keepaspectratio]{Penetration_Figure.png}
\caption{(Color Online) Representation of the proposed response of general supercooled fluid systems. The solid lines represent the original box shape before perturbation. The dashed regions represent the successive layers that respond to the perturbation at temperatures above and around Tg. At high temperatures only the layers experiencing the external stress move appreciably, but as temperature, T, is lowered and the cooperativity becomes pronounced, the perturbation is transmitted deeper into the material, reflecting increasing rigidity. Note that the extent to which the layers move as depicted, have been greatly exaggerated for clarity.}
\label{Depth.}
\end{figure*}
An activation barrier which grows with decreasing temperature is suggestive of cooperative particle motion in the supercooled liquid, and it is natural to suspect that this cooperativity likely arises due to structural changes accompanying supercooling. Conventional wisdom posits that growing timescales require growing lengthscales \cite{9}. Further, the possible, equilibrium vanishing of the configurational entropy and associated theoretical phase transition at finite temperature, $T_K$, known as the Kauzmann paradox is highly suggestive that structre plays a significant role in the glassy slowdown. In fact, many theories of the glass transition require the existence of a growing static structural lengthscale associated with the arrest at $T_g$ \cite{1,2,3,4,5,6,10,11,12,13,14,15,16,17,18}. However, structure factors and radial distribution functions show little change upon supercooling to $T_g$, so the identification of a universally accepted structural lengthscale has remained elusive \cite{1,2,3,4,5,6}. Previously, many structural lengthscales have been proposed and tested for but unfortunately none of these lengths have been satisfactably verified experimentally \cite{19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34, Glotzer, Busch}. To that end we have proposed the existence of a new lengthscale related to structural connectivity in the supercooled liquid, namely the shear penetration depth, which is defined as the depth to which a shear perturbation applied on a boundary would penetrate into a liquid. Using molecular dynamics simulations on a model metallic glassformer, we provide evidence that this lengthscale grows dramatically with supercooling, and marks a natural candidate to measure structural connectivity in supercooled liquids tied to their arrest. The shear penetration depth has the added benefit that it can be experimentally measured.

\subsection{Facets of the Shear Penetration Depth}
We have defined the shear penetration depth as the length over which a shear perturbation applied on a boundary will appreciably penetrate into a material. If a force is applied to the boundary layer of a high temperature liquid, only the atoms in the layers of the liquid near the boundary will experience an appreciable displacement due to the applied force. As the temperature is lowered and the viscosity increases, the shear force penetrates deeper into the material until the glass transition is reached. When the material is a glass, the shear perturbation entirely penetrates the material, diverging to the system size. This idealized behavior of the shear penetration depth is depicted in Figure (\ref{Depth.}). When a crystalline solid moves together in response to a shear force, it is because the long range order allows for the transmission of the force throughout the entire material. In a glass we expect that there is also a network of interconnectivity which grew and became more cohesive as the supercooled liquid was cooled toward $T_g$. The shear penetration depth serves not only as a lengthscale for the various theories that require one, but more importantly is intimately connected with structural connectivity and its existence and growth would provide strong evidence that structure underlies the slow kinetics of the glass transition.

\section{Model and Methodology}
To test for the existence of the shear penetration depth, we simulated a model metallic glass former, namely $NiZr_2$ ($T_g \approx 700 K$). This binary alloy system represents an exceptional example of a fragile glassformer, displaying a marked super-Arrhenius viscosity. Molecular dynamics simulations were performed using the LAMMPS package \cite{48} with a cubic simulation box and periodic boundary conditions in all three cartesian directions. A velocity verlet integration algorithm with a 5 fs timestep was employed, with the force generated from a semi-empirical Finnis-Sinclair type Embedded Atom Model potential developed by Mendelev et al \cite{49}. This potential was shown to very accurately reproduce the behavior of both the equilibrium liquid and supercooled liquid/glass.

Simulations were run with N=5000 atoms in the NPT ensemble with the target external pressure set to P=0. A Nose-Hoover thermostat and barostat were used to control the temperature and pressure, respectively. The initial positions of the atoms were generated randomly, and the system was then allowed to melt and come to equilibrium at an initial temperature of T=2200 K for 0.25 ns. Once the liquid had equilibrated, it was quenched to the desired target temperature (ranging from 300 K up to 1900 K) using a quench rate of $10^{13}$ K/s. Once the target temperature was reached, the system was allowed to evolve naturally for 0.1 ns. Next, an additional external force of 0.2 ev/A was applied in the x-direction to all atoms in the uppermost 4 angstrom layer of the simulation box. This force was left active for only 100 timesteps. This was meant to approximate an impulsive "kick" at the boundary layer of the system. After the application of the shear force, the system was left to evolve for an observation time of 16,000 timesteps. After the observation time had passed, displacement data was exported and examined. For T=300, 500, 600, 650, 700, 750, 800, and 1300 K, six independent starting configurations were employed  to provide for good statisitics.

\section{Results and Analysis}
\begin{figure*}
\centering
\includegraphics[width=1 \columnwidth, height= .4 \textheight, keepaspectratio]{Shear_Data.png}
\caption{(Color Online). Displacement data for three typical temperatures, with two above the glass transition temperature and one below.}
\label{Data.}
\end{figure*}
In order to quantify the penetration depth and extract its temperature dependence, we examine the displacement of the atoms in the shear direction as a function of their distance from the boundary layer at each of the target temperatures. Representative data is shown in Figure (\ref{Data.}). We define the shear direction (direction of applied shear) as the x-direction, and the vertical distance from the boundary layer as the z-direction (See Figure (\ref{Depth.})). The displacment is the net displacement of the atoms in the shear direction from the timestep immediately preceding the activation of the shear force to the end of the observation time, as defined above. The height of the atom is its z-coordinate at the observation time. Due to the periodic boundaries, only atoms falling within the range $z=\frac{L}{2}$ to $z=L$ are considered. Thermal and temporal effects do play a role, and make the response of the system more complicated than assumed here. This can be quantified, and a deeper analysis is saved for a separate work \cite{Me}. Because the system size is small and the applied shear force is weak (so as not to fracture the system in the glassy state), the displacement of the atoms, $\delta_x(z,T)$, as a function of height (z) can be linearized. To that end, we perform a linear regression to the data and get fits of the form,
\begin{equation}
\centering
\label{Linear}
\delta_x(z,T)=\mu *z + \delta_0.
\end{equation}
\begin{figure*}
\centering
\includegraphics[width=1 \columnwidth, height= .4 \textheight, keepaspectratio]{Average_Slope.png}
\caption{(Color Online) Plot of the average values of the inverse penetration depth $\overline{\mu}$ as computed by Eq. (\ref{Linear}) as a function of the temperature, $T$. As seen, $\overline{\mu}$ decreases dramatically as the temperature is lowered towards the glass transition. This signifies the divergence of the shear penetration depth upon supercooling.}
\label{Slope.}
\end{figure*}
For all temperatures where multiple independent runs were made, we average the values of $\mu$, and it is this average, $\bar{\mu}$, that we examine as a function of temperature. Figure (\ref{Slope.}) depicts this temperature dependence. The error bars are given by the standard deviation computed from the multiple runs. These correspond to thermal fluctuations and the different inherent structures the supecooled liquid/glass can be quenched into.

It is clear that there is a drastic, monotonic decrease in $\bar{\mu}$ as the temperature is decreased toward $T_g$. In the vicinity of $T_g$ and at all temperatures below it, the value of $\bar{\mu}$ with its associated error is indistinguishable from zero. This is consistent with total penetration of the shear. We can convert the decay of the displacement into a quantifiable length scale by defining the penetration depth as
\begin{equation}
\centering
\label{Penetration}
\xi \equiv \frac{1}{\bar{\mu}}.
\end{equation}
Due to the fluctuations at and below $T_g$, we can only assert that the length scale grows dramatically with decreasing temperature and diverges to beyond the system size at the glass transition. A bound on the shear penetration is provided by
\begin{equation}
\centering
\label{Lower}
\xi_{l} \equiv \frac{1}{\bar{\mu}+\sigma}.
\end{equation}
\begin{figure*}
\centering
\includegraphics[width=1 \columnwidth, height= .4 \textheight, keepaspectratio]{JSTAT_Length.png}
\caption{(Color Online) The lower bound $\xi_l$ of the penetration depth (Eq. (\ref{Lower})) as a function of temperature ($T$). An increase of the shear penetration depth begins at $T_A$, see text.}
\label{Length.}
\end{figure*}
$\xi_{l}$ represents an absolute lower bound on the behavior of the length scale with temperature and is displayed in Figure (\ref{Length.}). From the figure it is clear that the length scale grows dramatically as the glass transition is approached. It is also quite noticeable that appreciable growth of the lengthscale does not set in until a temperature close to $T_A$. Below this temperature (typically for all metallic glass formers $T_A \approx 2T_g$) \cite{46} super-Arrhenius growth of the relaxation time appears. Furthermore, below $T_A$, the Stokes-Einstein relation may break down, and solid-like properties begin to appear in the liquid \cite{51,52,53,54}. More significantly, below $T_A$, local structures begin to form and percolate throughout the system as seen in numerous molecular dynamics studies \cite{52,54,63,64,65,66,67}. This provides ample support to the notion that structure plays a significant role in the arrest at the glass transition. As the local structures interlock and interpenetrate, they begin to thread the system. As they grow further, and become increasingly cohesive, a backbone forms in the liquid which is stiff and rigid. This allows for the propagation of the shear force through the material, and leads to the arrested flow. The shear penetration depth is ultimately agnostic as to the exact form of propagating structural order and connectivity, but represents an exciting new method of possibly measuring this growing order without resorting to standard scattering methods which have been largely opaque to role of structure in the glass transition.

\section{Conclusion}
By taking advantage of simple physical reasoning derived from the main distinction between liquids and solids, in terms of their response to shear, we have identified a natural length scale relevant to the glass transition. This lengthscale, the shear penetration depth, has been shown through simulations, to grow dramatically as a liquid is supercooled toward $T_g$. Further, we have made a reasonable and physically meaningful connection with growing structural order and connectivity in the supercooled liquid. That the shear penetration depth begins to grow appreciably at $T_A$, is a strong indicator that structure plays a fundamental role in the kinetic phenomenology of the glass transition. Because the shear penetration depth is intimately related and sensitive to this connectivity and structural change, it marks an exceptional candidate for revealing the effect of structure in experiments.
\section{Acknowledgements}
NW and ZN were supported by the NSF DMR-1411229. ZN thanks the Feinberg foundation visiting faculty program at Weizmann Institute.


\section{CONCLUSION}
\label{sec:conclusions}

In this study of signer-independent and adapted ASL fingerspelling recognition, we have seen that fingerspelling has great variability in speed, hand appearance, and appearance of non-signing gestures.  We have improved performance on new signers via adaptation of DNNs in tandem and SCRF recognizers.  Several DNN adaptation approaches are successful, with the largest improvements coming from simple fine-tuning on adaptation data.  This approach improves letter accuracies from around 40\% (unadapted) to up to 69.7\% with weak word-level supervision and up to 82.7\% with ground-truth frame labels for the adaptation data.  While the models perform similarly, the best adapted model is a first-pass SCRF.  The main DNN improvements come from resolving confusions between actual letters and the non-signing (``silence'') class.  Future work will continue to improve the models and adaptation approaches, as well as address other types of variability that are needed to port the models to video data ``in the wild''.

\subsection{DNN adaptation}
\label{sec:dnn}
\vspace{-.05in}

\begin{figure*}[th]
\centering
\includegraphics[width=.8\linewidth]{dnn}
\vspace{-.1in}
\caption{Left:  Unadapted DNN classifier; middle:  adaptation via linear input network and output layer updating (LIN+UP); right: adaptation via linear input network and linear output network (LIN+LON).}
\label{fig:dnn-adapt}
\end{figure*}

The DNNs
are first trained in a signer-independent way on all but the test signer, using an L2-regularized cross-entropy loss.  The inputs are the image features concatenated over a multi-frame window,
which are fed through several fully connected layers followed by a softmax output layer.
Inspection of data such as Fig.~\ref{fig:ex} reveals the main sources of signer variation:  speed, hand appearance, and non-signing motion variation before/after signing.  The speed variation is large, with a factor of $1.8$ between the fastest and slowest signers.  In the absence of adaptation data, we consider a simple speed normalization:  We augment the training data with resampled image features, at 0.8x and 1.2x the original frame rate.

If we have access to some labeled data from the test signer, but not a sufficient amount for training full signer-specific DNNs, we can apply adaptation.  A number of DNN adaptation approaches have been developed (e.g.,~\cite{liao2013speaker,abdel2013fast,swietojanski2014learning,doddipatla2014speaker}).  We first consider two simple approaches based on linear input networks (LIN) and linear output networks (LON)~\cite{Neto_95a,Yao_12a,li2010}, shown in Fig.~\ref{fig:dnn-adapt}.  Most of the network parameters are fixed; only a limited set of weights at the input and output layers are learned.
In the first approach (LIN+UP in Fig.~\ref{fig:dnn-adapt}), we apply a single affine transformation $W_{\text{LIN}}$ to the
static features at each frame (before concatenation)
and feed the result to the trained signer-independent DNNs. We jointly learn $W_{\text{LIN}}$ and adapt the last (softmax) layer weights by minimizing the same cross-entropy loss
on the adaptation data,
and ``warm-start'' the softmax layer with the learned signer-independent weights.
The second approach (LIN+LON in Fig.~\ref{fig:dnn-adapt}) uses the same input adaptation layer, but rather than adapting the softmax weights, it removes the softmax output activation and adds a new softmax output layer $W_{\text{LON}}$ for the test signer,
trained jointly with the same cross-entropy loss. Finally, we also consider adaptation by fine-tuning; that is, updating all of the DNN weights on adaptation data starting from the signer-independent weights.  The adaptation can use either ground-truth frame-level letter labels (using human annotation as described in~\cite{kim2012}) or labels obtained by forced alignment if only word labels are available.

\section{EXPERIMENTS}
\label{sec:experiments}
\vspace{-.1in}

\input{table}
We use the ASL video data set of~\cite{kim2013}, comprising four signers each fingerspelling 600 word tokens consisting of two repetitions of a 300-word list, including common English words, names, and foreign words.
Annotators marked the peak of articulation of each letter, and the annotations were converted to a ``ground-truth'' frame labeling by assuming that the letter boundaries occur mid-way between peaks.  Following \cite{kim2013}, the hand portion of each image is extracted via hand detection and segmentation using a signer-specific Gaussian color model, followed by suppression of irrelevant pixels.  The extracted hand images are resized to 128 $\times$ 128 and Histogram of Gradient (HoG) \cite{hog} features are extracted using multiple spatial grids (4 $\times$ 4, 8 $\times$ 8, and 16 $\times$ 16), followed by dimensionality reduction with principal components analysis (PCA).

\vspace{-.15in}
\subsection{Frame classification}
\vspace{-.05in}

The initial unadapted signer-independent DNNs are trained on all but the test signer for each of the seven tasks (letters and the six phonological features).  The input is the $128$-dimensional HoG features
concatenated over a $21$-frame window, and the networks have three hidden layers of $3000$ ReLUs~\cite{Zeiler_13a}.  Cross-entropy training is done with a
weight decay penalty of $10^{-5}$ via stochastic gradient descent (SGD) over $100$-sample minibatches for up to $30$ epochs, with dropout~\cite{Srivas_14a} at a rate of $0.5$ at each hidden layer, fixed momentum of $0.95$, and initial learning rate of $0.01$, which is halved when held-out accuracy stops improving.  These hyperparameters were tuned on held-out (signer-independent) data in initial experiments, not reported here in the interest of space.  We pick the best-performing epoch on held-out data.

\begin{figure}\centering
\centering
\vspace{-.06in}
\hspace{-.2in}\includegraphics[width=0.92\linewidth]{figs/adapt_bar3b.eps}
\vspace{-.15in}
\caption{DNN frame accuracies with and without normalization/adaptation.  The horizontal axis labels indicate the amount of adaptation data (0, 1, 2, 3 = none, 5\%, 10\%, 20\% of the test signer's data, corresponding to no adaptation, $\sim29$, $\sim58$, and $\sim115$ words).  GT = ground truth labels; FA = forced alignment labels; FT = fine-tuning.}
\label{fig:adapt}
\end{figure}

We next consider DNN normalization and adaptation with different types and amounts of supervision.  For LIN+UP and LIN+LON, we adapt by running SGD over minibatches of $100$ samples with a fixed momentum of $0.9$ for up to $20$ epochs, with initial learning rate of $0.02$ (which is halved when accuracy stops improving on the adaptation data).  For fine-tuning, we use the same SGD procedure as for the signer-independent DNNs.  We pick the epoch with the highest accuracy on the adaptation data.
The resulting frame accuracies are given in Fig.~\ref{fig:adapt}.  In addition, Fig.~\ref{fig:adapt} includes the result of speed normalization for the case of letter classification.  Speed normalization provides consistent but very small improvements, while adaptation gives large improvements in all settings.
LIN+UP slightly outperforms LIN+LON, and fine-tuning outperforms both LIN+UP and LIN+LON. For letter sequence recognition in the next section, we adapt via fine-tuning using $20\%$ of the test signer's data.

Fig.~\ref{fig:confmat} further analyzes the DNNs via confusion matrices.  One of the main effects is the large number of incorrect predictions of the non-signing classes ($<$s$>$, $<$/s$>$).  We observe the same effect with the phonological feature classifiers.  This may be due to the previously mentioned fact that non-linguistic gestures are variable and easy to confuse with signing when given a new signer's image frames.  The confusion matrices show that, as the DNNs are adapted, this is the main type of error that is corrected.

\begin{figure*}[t]
\centering
\begin{tabular}{@{}c@{\hspace{0.02\linewidth}}c@{\hspace{0.01\linewidth}}c@{\hspace{0.01\linewidth}}c@{}}
No Adapt. & \caja{c}{c}{LIN+UP (Forced-Align.)} & \caja{c}{c}{LIN+UP (Ground Truth)} \\
\includegraphics[width=0.34\linewidth]{confusion_noadaptation_andy_task=letter.eps} &
\includegraphics[width=0.28\linewidth]{confusion_forced_aligned_adaptation_andy_task=letter.eps} &
\includegraphics[width=0.34\linewidth]{confusion_ground_truth_adaptation_andy_task=letter.eps} \\
\end{tabular}
\vspace{-.1in}
\caption{Confusion matrices of DNN classifiers for one test signer (Signer 1).  $20\%$ of the test signer's data (115 words) was used for adaptation, and a disjoint $70\%$ was used to compute confusion matrices.
Each matrix cell is the empirical probability of the predicted class (column) given the ground-truth class (row).  The diagonal has been zeroed out for clarity.}
\label{fig:confmat}
\end{figure*}

\subsection{Connected letter recognition}

In connected letter recognition, we measure performance via the letter accuracy, analogously to the word or phone accuracy in speech recognition.  Table~\ref{t:LER} shows the letter accuracies obtained with the tandem, rescoring SCRF, and first-pass SCRF models with DNN adaptation via fine-tuning, using different types of adaptation data.  For all models, we do not retrain the models with the adapted DNNs, but tune several hyperparameters\footnote{See~\cite{kim2012,kim2013,tang2015} for details of the tuning parameters.} on 10\% of the test signer's data.  The tuned models are evaluated on an unseen 10\% of the test signer's remaining data; finally, we repeat this for eight choices of tuning and test sets, covering the 80\% of the test signer's data that we do not use for adaptation, and report the mean letter accuracy over the test sets.

As shown in Table~\ref{t:LER}, without adaptation both tandem and SCRF models do poorly, achieving only roughly 40\% letter accuracies, with the rescoring SCRF slightly outperforming the others (recall that signer-dependent recognition achieves about 90\% letter accuracies~\cite{kim2013}).  With adaptation, however, performance jumps to up to 69.7\% letter accuracy with forced-alignment adaptation labels and up to 82.7\% accuracy with ground-truth adaptation labels.  All of the adapted models perform similarly, but interestingly, the first-pass SCRF is slightly worse than the others before adaptation and better (by 4.4\% absolute) after ground-truth adaptation.  One hypothesis is that the first-pass SCRF is more dependent on the DNN performance, while the tandem model uses the original image features and the rescoring SCRF uses the tandem model hypotheses and scores.  Once the DNNs are adapted, however, the first-pass SCRF outperforms the other models.

\section{INTRODUCTION}
\label{sec:intro}

Automatic sign language recognition is a nascent technology that has the potential to improve the ability of Deaf and hearing individuals to communicate, as well as Deaf individuals' ability to take full advantage of modern information technology.  For example, online sign language video blogs and news\footnote{E.g., \tt{http://ideafnews.com, http://aslized.org}.} are currently almost completely unindexed and unsearchable as they include little accompanying annotation.

Research on this problem has included both speech-inspired approaches and computer vision-based techniques, using either/both video and depth sensor input~\cite{dreuw,zaki,bowden,liw,theo,vog,kim2012,kim2013,forster2013improving}.
We focus on recognition from video, for applicability to existing recordings.  Before the technology can be applied ``in the wild'', it must overcome challenges posed by visual nuisance parameters (e.g., lighting, occlusions) and signer variation.  Annotated data sets for this problem are scarce, in part due to the need to recruit signers and skilled annotators.

We consider American Sign Language (ASL), in particular the fingerspelling component:  the spelling out of a word as a sequence of handshapes or hand trajectories corresponding to individual letters.
Fig.~\ref{fig:ex} gives example fingerspelling sequences.  Fingerspelling accounts for roughly 12-35\% of ASL~\cite{Padden} and is typically used for proper nouns or borrowings from English,
which can often be the most important content words.
Some aspects of fingerspelling can be characterized through the phonology of handshape~\cite{bren,john}, which can be described in terms of phonological features.
Most prior research on fingerspelling recognition has focused on constrained tasks such as single-letter or handshape classification or word recognition from a known vocabulary~\cite{athitsos2004boostmap,Ricco-Tomasi-09,Tsechpenakis-et-al-06-coupling,Bowden-Sarhadi-02,Goh-Holden-06,Roussos:JMLR.13,PugBow2011}.  For the unconstrained letter sequence recognition problem, Kim et al.~\cite{kim2012,kim2013} obtained $\sim90$\% average letter accuracies in a signer-dependent setting, using either tandem hidden Markov models (HMMs) or segmental conditional random fields (SCRFs), with features from neural network classifiers of letters and phonological features.  That work used the largest video data set of which we are aware containing unconstrained, connected fingerspelling, consisting of four signers each signing 600 word tokens for a total of $\sim350$k image frames.

In this paper we consider the problem of {\it signer-indepen-dence in unconstrained fingerspelling sequence recognition}, in the context of limited training data.
Prior work has address signer adaptation for large-vocabulary German Sign Language recognition~\cite{forster2013improving}, but to our knowledge this paper is the first to address adaptation for fingerspelling.  We
investigate approaches to signer-independence including speed normalization and neural network adaptation.  The adaptation techniques are largely borrowed from speech recognition research, but the application is quite different in that the overall amount of data is much smaller and the types of variation are different.  We find that the simple signer normalization is ineffective, while DNN adaptation is very effective.

\section{REFERENCES}

\clearpage
\begin{small}
\bibliographystyle{IEEEbib}

\section{METHODS}
\label{sec:method}
\vspace{-.1in}

\input{examplefig}

The task is to convert a video (a sequence of images), as in Fig.~\ref{fig:ex}, to a sequence of letters.  The segmentation into letters is unknown, so this is a sequence prediction task analogous to connected phone or word recognition.  We start with the recognition approaches that have achieved the best prior results on this task~\cite{kim2012,kim2013}, with updates for improved performance with deeper neural networks.  We next briefly describe the recognizers, the neural network classifiers and adaptation.

\vspace{-.2in}
\subsection{Recognizers}
\vspace{-.05in}
The first recognizer is a tandem model~\cite{ellis} based on~\cite{kim2012}.  Frame-level features are fed to neural network classifiers, one of which predicts the frame's letter label and six others which predict handshape phonological features.\footnote{See~\cite{bren,john,kim2012} for details of the phonological features.}  Classifier outputs are concatenated with the image features, after a dimensionality reduction, and input to a hidden Markov model (HMM) recognizer with Gaussian mixture observation densities.

The second recognizer is a segmental CRF (SCRF) model based on~\cite{kim2013}.  SCRFs~\cite{sarawagisemi,zweig} are conditional log-linear models with feature functions that can be based on variable-length segments of input frames, allowing for great flexibility in defining feature functions.
As in~\cite{kim2013}, we use an SCRF to rescore lattices produced by a baseline frame-based recognizer (in this case, the tandem model).  We use the same feature functions as in~\cite{kim2013}, which include language model features, a feature that measures agreement with the baseline recognizer, means of letter/phonological feature neural network classifier outputs over each segment, and ``peak detection'' features that measure the dynamics of each segment.

Finally, we also use a first-pass decoding SCRF from Tang {\it et al.}~\cite{tang2015}, which is independent of any frame-based recognizer.  We use the same feature functions as in~\cite{tang2015}, namely average DNN outputs over each segment, samples of DNN outputs within the segment, duration and bias, all lexicalized.

\input{dnn}