Beta-Expansion: A Theoretical Framework for Fast and Recursive Construction of Polar Codes

TLDR

The authors introduce β‑expansion, a number‑theoretic concept, as a theoretical framework for fast polar‑code construction using the recursive universal partial order and polarization‑weight algorithms. They recursively construct polar codes from the universal partial order by solving polynomial equations at each step, extracting a β interval that, when used in a closed‑form β‑expansion ranking, preserves nested frozen sets and enables low‑complexity construction. For AWGN channels, the β interval converges to approximately 1.1892 as block length grows, and both asymptotic analysis and simulations confirm the theoretical predictions.

Abstract

In this work, we introduce β-expansion, a notion borrowed from number theory, as a theoretical framework to study fast construction of polar codes based on a recursive structure of universal partial order (UPO) and polarization weight (PW) algorithm. We show that polar codes can be recursively constructed from UPO by continuously solving several polynomial equations at each recursive step. From these polynomial equations, we can extract an interval for β, such that ranking the synthetic channels through a closed- form β-expansion preserves the property of nested frozen sets, which is a desired feature for low- complex construction. In an example of AWGN channels, we show that this interval for β converges to a constant close to 1.1892 when the code block-length trends to infinity. Both asymptotic analysis and simulation results validate our theoretical claims.