Source-linked AI summary
$β$-expansion: A Theoretical Framework for Fast and Recursive Construction of Polar Codes
Gaoning He, Jean-Claude Belfiore, Xiaocheng Liu, Yiqun Ge, Ran Zhang, Ingmar Land, Ying Chen, Rong Li, Jun Wang, Ganghua Yang, Wen Tong
TL;DR
Fast polar-code construction is difficult because AWGN ranking methods are computationally expensive, while UPO alone cannot fully rank synthetic channels. The paper develops β-expansion over recursive UPO, showing that polynomial-equation intervals preserve nested frozen sets and converge near 1.1892 for AWGN channels.
Problem
Fast construction must rank synthetic channels efficiently, but UPO cannot fully rank them and DE/GA have high computational complexity for AWGN channels.
Method
The paper combines β-expansion with recursive UPO, solving polynomial equations at each step to obtain β intervals for closed-form synthetic-channel ranking.
Results
The β interval converges to a constant close to 1.1892 ≈ 2^(1/4) as block-length grows, with asymptotic analysis and numerical results confirming the method.
Takeaways & Limitations
The framework provides a low-complexity recursive construction that preserves nested frozen sets while ranking synthetic channels through β-expansion.
Abstract
from arXiv · showhide
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 \approx 2^{1/4}$ when the code block-length trends to infinity. Both asymptotic analysis and simulation results validate our theoretical claims.
I. INTRODUCTION
Polar-code construction requires efficiently ranking synthetic-channel reliabilities, but practical AWGN methods remain too complex. The paper addresses this through recursive UPO structure and β-expansion.
- Motivation: Polarization creates virtual channels approaching either extreme reliability, so information bits should occupy good positions and bad positions should be frozen.Efficiently identifying and ranking these positions is critical for construction.
- Motivation: Efficient construction was previously available only for BEC, while AWGN techniques such as DE and GA have complexity scaling linearly with block-length.This complexity is described as unacceptable for practical systems with varying parameters and low-latency implementation.
- Prior structure: Universal partial orders can reduce construction complexity because they are deterministic and channel-independent, but they do not by themselves fully rank all synthetic channels.The paper builds on this partial-order structure to seek a faster construction method.
- Contribution: The paper introduces β-expansion to exploit an inherent recursive structure in UPO and construct polar codes by choosing β at each recursive step.This framework connects UPO analysis with the polarization weight algorithm.
- Paper scope: The paper studies recursive UPO structure, β-expansion theory, fast construction, asymptotic analysis, and numerical results.These topics are presented across the paper’s sections.
A. Channel polarization
Channel polarization repeatedly splits a physical channel into synthetic channels whose reliabilities can be measured through mutual information or the Bhattacharyya parameter.
- Channel splitting: Channel polarization splits a physical channel W into paired channels W^0 and W^1 through repeated channel-splitting operations.The paper defines the resulting channels recursively from the original channel.
- Synthetic channels: After n splitting operations, the original channel produces N = 2^n synthetic channels.These channels are indexed through binary expansions and generated by repeated application of the splitting operation.
- Synthetic channels: A synthetic channel is defined from the n-bit binary expansion of its integer index, with each bit selecting one branch of the recursive construction.The branch operation is obtained from the channel-splitting equations.
- Reliability measure: Reliability is evaluated using mutual information or, equivalently, the Bhattacharyya parameter.These measures determine the reliability ordering of synthetic channels.
- Channel model: The transmission probability pY|X(y|x) specifies the probability model underlying the physical channel.It appears in the channel definition used for the recursive construction.
B. Universal partial order (UPO)
UPO provides universal reliability relations among synthetic-channel indices through Addition and Left-swap rules, but some pairs remain unresolved.
- Definition and scope: UPO applies to symmetric binary-input channels and determines partial reliability relations that do not fully order all N synthetic-channel positions.Prior work reports that only a fraction 1/log^(3/2) N remains to be ranked after applying these relations.
- UPO rules: The Left-swap rule ranks a binary pattern containing 0..1 below the corresponding 1..0 pattern.The two bits need not be adjacent, and the pattern may occur multiple times.
- Unresolved relations: Some synthetic-channel pairs cannot be ordered using Addition, Left-swap, or combinations of the two rules.These unresolved relations are described as unknown to UPO.
III. PROPERTIES OF UNIVERSAL PARTIAL ORDER
UPO has nested and symmetric properties that generate its relations recursively across block-lengths. This structure supports constructing larger UPOs from smaller ones.
- Nested property: Nestedness means that relations determined at block-length N remain unchanged when the code length grows to 2N.Binary-prefix embedding preserves the Addition and Left-swap rules.
- Symmetric property: Symmetry pairs each relation x ≺ y with the mirrored relation (N − 1 − x) ≻ (N − 1 − y).The paired indices are obtained through the symmetric transformation of the binary representations.
- Recursive representation: The minimum UPO set keeps only adjacent links from each relation chain, such as x ≺ y and y ≺ z instead of x ≺ y ≺ z.This representation uses the most adjacent nodes in each chain.
- Recursive representation: At each recursive level, inherited relations provide the nested part, mirrored relations provide the symmetric part, and additional relations are newly introduced.This decomposition describes how UPO_n is built from UPO_(n−1).
- Recursive construction: Every UPO of length 2^n can be recursively generated from UPO1 = {{0, 1}} by repeatedly applying the same rule.The construction pattern is illustrated by the listed UPO examples and Figure 1.
IV. β-EXPANSION: THEORY OF PW ALGORITHM
The paper develops β-expansion as a closed-form framework for polarization-weight ranking, connecting the PW algorithm’s nested construction to UPO through recursively determined β intervals.
- PW algorithm and nested structure: The PW algorithm fully ranks synthetic-channel reliability while preserving nested frozen sets as code length grows.A construction at length N can be reused at lengths 2N, 4N, and beyond.
- Relation to UPO: For β > 1, β-expansion respects both the Addition and left-swap rules of UPO.Positive powers preserve Addition, while increasing powers preserve the left-swap inequality.
- Relation to UPO: β-expansion can introduce orders beyond UPO, so β must be selected to produce a suitable sequence.The paper frames β selection as the central question after establishing UPO compatibility.
- β selection: β-expansions may be nonunique at algebraic values such as the golden ratio, where 0-1 polynomial relations make rankings ill-conditioned.The example φ satisfies φ + 1 = φ^2 because it is a root of x^2 − x − 1 = 0.
- β selection: For polar codes of length 2^n, algebraic boundary values partition β into intervals where expansion is unique and produces a distinct ordered sequence.The boundary sets are nested across lengths: A_n ⊂ A_n+1.
- Recursive construction: At n = 4, four polynomial equations generate roots approximately 1.325, 1.466, 1.618, and 1.839 that separate the relevant orderings.The equations include x^3 − x^2 − x − 1 = 0, x^3 − x^2 − 1 = 0, x^2 − x − 1 = 0, and x^3 − x − 1 = 0.
V. AN EXAMPLE OF FAST CONSTRUCTION FOR AWGN
The AWGN construction combines UPO’s recursive structure with β-expansion to resolve channel-ordering ambiguities while preserving a sequence close to DE/GA. As block-length grows, the admissible β interval narrows toward 1.1892.
- Fast construction: UPO cannot fully rank synthetic channels, so the proposed construction supplements its known orders with β-expansion.DE/GA can rank the full sequence but has high complexity; β-expansion is used to bridge this gap.
- Fast construction: Careful β selection makes β-expansion produce the same or approximately the same good sequence as DE/GA.The AWGN example studies how this interval changes as block-length grows from 8 to 1024.
- Recursive construction: For N = 8, the unknown order 4 ≺3 selects β ∈ (1, 1.618).This ordering is obtained from DE/GA for every SNR.
- Recursive construction: For N = 16, three new pairs reduce the β range from (1, 1.618) to (1, 1.325).The pairs are (6, 9), (3, 8), and (7, 12), with their ordering supplied by DE/GA.
- Asymptotic trend: The β interval converges near 1.1892 ≈ 2^1/4, while new pairs remain below 20% of all synthetic channels.The reported convergence concerns AWGN sequence generation from length N to 2N.
VI. ASYMPTOTIC ANALYSIS AND NUMERICAL RESULTS
The asymptotic analysis relates β-expansion distributions to Bernoulli convolution, while numerical results compare β = 1.1892 against Gaussian approximation for AWGN channels. The analysis supports absolute continuity for this β, and simulations report equal performance with lower complexity.
- Asymptotic analysis: β-expansion asymptotics are studied by transforming the distribution problem into Bernoulli convolution.The binary sequence is modeled using independent binary random variables.
- Asymptotic analysis: Absolute continuity of the Bernoulli-convolution measure is required to fully rank infinitely many synthetic channels.The measure is established to be either absolutely continuous or singular.
- Asymptotic analysis: For β = 2^1/k, the measure is absolutely continuous; k = 4 gives β = 1.1892, matching the observed convergence.This connects the theoretical condition to the AWGN interval’s numerical limit.
- Numerical results: Under BLER = 0.001, QPSK, AWGN, and SCL list size 8 with a 19-bit CRC, β-expansion performs equally well as GA with much lower complexity.The comparison uses β = 1.1892 across different code lengths.
VII. CONCLUSION
The paper presents β-expansion as a theoretical framework for fast, recursive polar-code construction. Its AWGN example shows convergence toward β ≈ 1.1892 and performance matching Gaussian approximation.
- Conclusion: The framework explains polarization weight through β-expansion and recursively constructs polar codes from UPO by solving polynomial equations.The construction links β intervals to sequence ordering and preserves the low-complexity objective.
- Conclusion: For AWGN channels, the β interval converges toward 1.1892 as block-length increases, while asymptotic and numerical results confirm performance matching GA.The conclusion reports this as the paper’s final validation.