# Emmanuel Abbe: Erdal Arıkan’s Polar Codes

Let us consider the simplest setting. Let $X_1,...,X_n$ be i.i.d. Bernoulli($p$) and assume that $n$ is a power of 2. Define $G_n$ to be the matrix obtained by taking $\log_2(n)$ Kronecker products of $G_2=\begin{pmatrix}1&0\\1&1\\\end{pmatrix}$, and multiply $X=(X_1,...,X_n)$ with $G_n$ over $GF(2)$ to get $U=(U_1,...,U_n)$. Note that $U$ has same entropy as $X$, since $G_n$ is invertible (its inverse is itself). However, if the entropy of $X$ is uniformly spread out over its components, i.e., $H(X)=nH(X_1)$, the entropy of $U$ may not be, since its components are correlated. In any case, we can write $H(U)= \sum_i H(U_i|U^{i-1})$ where $U^{i-1}=(U_1,...,U_{i-1})$ are the `past components’. The polarization phenomenon then says that, except for a vanishing fraction of indices $i$ (w.r. to $n$), each term $H(U_i|U^{i-1})$ tends to either 0 or 1.