Abstract
We prove that, for the binary erasure channel (BEC), the polar-coding paradigm gives rise to codes that not only approach the Shannon limit but do so under the best possible scaling of their block length as a function of the gap to capacity. This result exhibits the first known family of binary codes that attain both optimal scaling and quasi-linear complexity of encoding and decoding. Our proof is based on the construction and analysis of binary polar codes with large kernels. When communicating reliably at rates within $\varepsilon > 0$ of capacity, the code length $n$ often scales as $O(1/\varepsilon^{\mu})$, where the constant $\mu$ is called the scaling exponent. It is known that the optimal scaling exponent is $\mu=2$, and it is achieved by random linear codes. The scaling exponent of conventional polar codes (based on the $2\times 2$ kernel) on the BEC is $\mu=3.63$. This falls far short of the optimal scaling guaranteed by random codes. Our main contribution is a rigorous proof of the following result: for the BEC, there exist $\ell\times\ell$ binary kernels, such that polar codes constructed from these kernels achieve scaling exponent $\mu(\ell)$ that tends to the optimal value of $2$ as $\ell$ grows. We furthermore characterize precisely how large $\ell$ needs to be as a function of the gap between $\mu(\ell)$ and $2$. The resulting binary codes maintain the recursive structure of conventional polar codes, and thereby achieve construction complexity $O(n)$ and encoding/decoding complexity $O(n\log n)$.
Introduction
In information theory, the ultimate goal is to design codes that reach Shannon capacity—the maximum rate of error-free communication—with minimal computational overhead. While random linear codes are known to reach this limit with "optimal scaling," they are computationally intractable for large block lengths.
Arıkan’s polar codes, introduced in 2009, were a breakthrough as the first explicit codes to reach capacity with efficient $O(n \log n)$ encoding and decoding. However, they suffer from a sub-optimal scaling exponent ($\mu$). To communicate within a gap $\epsilon$ of capacity, the block length $n$ must scale as $O(1/\epsilon^\mu)$. For random codes, $\mu = 2$, but for standard polar codes using the $2 \times 2$ kernel, $\mu \approx 3.63$ on the binary erasure channel (BEC). This research proves that polar codes can achieve the optimal $\mu = 2$ by utilizing larger polarization kernels.
The Polarization Framework
The core of the polar coding paradigm is the recursive application of a polarization kernel. By moving away from the standard $2 \times 2$ kernel and instead utilizing large $\ell \times \ell$ kernels, the authors demonstrate that the rate of polarization can be significantly improved.
As shown in the figure above, the input bits $U_i$ are transformed via the Kronecker power of a kernel $K^{\otimes m}$ into code bits $X_i$, which are then transmitted over independent channels $W$. The authors prove that if an $\ell \times \ell$ non-singular binary matrix is selected uniformly at random, it will, with high probability, act as a near-optimal polarization kernel as $\ell$ increases.
Scaling and Sharp Transitions
The primary driver of improved scaling is the creation of "sharp transitions" in the bit-channels. As the kernel size $\ell$ or the number of recursions increases, the individual bit-channels transform from being completely noisy to perfectly clean much more abruptly.
This transition is visualized in the performance plots above, where increasing the block length $N$ results in a steeper drop-off in error probability ($P_e$). By characterizing exactly how large the kernel $\ell$ must be to reach a specific scaling exponent, the authors establish a rigorous mathematical relationship between kernel size and the gap to optimality.
Key Results and Complexity
The study provides the first known family of binary codes that simultaneously achieves the information-theoretic "gold standard" for scaling ($\mu \to 2$) and the computer science "gold standard" for complexity ($O(n \log n)$).
Key findings include:
- Optimal Scaling: For the BEC, there exist $\ell \times \ell$ kernels such that the scaling exponent $\mu(\ell)$ approaches 2 as $\ell$ increases.
- Efficiency: These codes retain the recursive structure of conventional polar codes, ensuring construction complexity remains $O(n)$ and encoding/decoding remains $O(n \log n)$.
- Quantitative Bounds: For any $\delta > 0$, a sufficiently large $\ell$ can be chosen to ensure $\mu \leq 2 + \delta$.
Limitations and Future Outlook
While theoretically significant, a practical gap remains. The kernel size $\ell$ required to approach $\mu = 2$ is extremely large, and while the complexity is $O(n \log n)$ in terms of block length, the hidden constant factor scales exponentially with the kernel size ($2^\ell$). Future work will focus on finding moderately sized kernels (e.g., $16 \times 16$) that provide scaling gains without prohibitive computational overhead, and extending these proofs beyond the Binary Erasure Channel to more general symmetric channels.
Summary updated