On the Construction of Polar Codes

Ramtin Pedarsani, Seyed Hamed Hassani, Ido Tal, Emre Telatar

Abstract

We consider the problem of efficiently constructing polar codes over binary memoryless symmetric (BMS) channels. The complexity of designing polar codes via an exact evaluation of the polarized channels to find which ones are "good" appears to be exponential in the block length. In \cite{TV11}, Tal and Vardy show that if instead the evaluation if performed approximately, the construction has only linear complexity. In this paper, we follow this approach and present a framework where the algorithms of \cite{TV11} and new related algorithms can be analyzed for complexity and accuracy. We provide numerical and analytical results on the efficiency of such algorithms, in particular we show that one can find all the "good" channels (except a vanishing fraction) with almost linear complexity in block-length (except a polylogarithmic factor).

Introduction

Polar codes, introduced by Erdal Arıkan in 2009, represent a landmark in coding theory as the first class of codes provably capable of achieving Shannon capacity for binary memoryless symmetric (BMS) channels with efficient encoding and decoding. However, a significant practical challenge remained: the construction problem. To implement a polar code, one must identify the "good" bit-channels—those that are reliable—among the $N$ polarized channels. As the block length $N$ increases, the number of possible output symbols for these bit-channels grows doubly exponentially ($2^N$), making exact calculation of channel reliability computationally infeasible for practical code lengths.

Methodology

The core of the proposed solution lies in quantization. Rather than tracking the exact probability distribution of a channel, the authors approximate it by replacing the massive output alphabet with a smaller one of size at most $k$.

Stochastic Degradation and Upgrading

To maintain mathematical rigor, the framework utilizes two types of approximations:

  1. Degradation: A "pessimistic" approximation where the quantized channel is a degraded version of the original. This ensures that any channel identified as "good" in the approximation is guaranteed to be good in the actual channel.
  2. Upgrading: An "optimistic" approximation that serves as a counterpart to degradation. By "sandwiching" the true channel between these two bounds, the actual performance can be tightly estimated.

Greedy Mass Merging

The primary algorithmic contribution is a greedy approach to symbol merging. Algorithm 2, the Merging Masses Algorithm, iteratively identifies and merges pairs of output symbols that minimize the loss of mutual information.

Algorithm 2: The Merging Masses Algorithm for greedy channel quantization.

The complexity of this construction is shown to be $O(k^2 N)$, which is essentially linear in the block length for a fixed quantization level $k$.

Results and Analysis

The effectiveness of these quantization algorithms was evaluated through simulations on Binary Symmetric Channels (BSC) with capacity 0.5, testing block lengths up to $N = 2^{25}$ and varying quantization levels $k$.

The Sandwich Guarantee

A key insight is the rapid convergence of the degraded and upgraded bounds. As $k$ increases, the gap between the pessimistic and optimistic estimates vanishes. For instance, at a block length of $N = 2^{15}$ and $k=64$, the difference in achievable rate was found to be only $0.0001$.

Convergence of degraded and upgraded bounds as the quantization level k increases.

Efficiency and Scalability

The proposed framework allows for the construction of polar codes with millions of bits in minutes on standard hardware. Theoretically, the authors proved that if $k$ grows polylogarithmically with $N$ (specifically $k \approx (\log N)^2$), the fraction of identified good channels approaches the true capacity $I(W)$ as $N \to \infty$.

Conclusion

This work addresses a critical bottleneck in polar coding by providing a linear-complexity construction method. By utilizing quantization with degradation and upgrading guarantees, the authors transformed polar codes from a theoretical breakthrough into a practical technology suitable for real-world communication systems. While the current framework is optimized for BMS channels, it sets the stage for future extensions to non-symmetric and non-binary channel models.

Summary updated

Abstract

We consider the problem of efficiently constructing polar codes over binary memoryless symmetric (BMS) channels. The complexity of designing polar codes via an exact evaluation of the polarized channels to find which ones are "good" appears to be exponential in the block length. In \cite{TV11}, Tal and Vardy show that if instead the evaluation if performed approximately, the construction has only linear complexity. In this paper, we follow this approach and present a framework where the algorithms of \cite{TV11} and new related algorithms can be analyzed for complexity and accuracy. We provide numerical and analytical results on the efficiency of such algorithms, in particular we show that one can find all the "good" channels (except a vanishing fraction) with almost linear complexity in block-length (except a polylogarithmic factor).
BibTeX
@inproceedings{pedarsani2011construction,
  author = {Ramtin Pedarsani and Seyed Hamed Hassani and Ido Tal and Emre Telatar},
  title = {{On the Construction of Polar Codes}},
  booktitle = {ISIT},
  year = {2011},
  url = {https://openreview.net/forum?id=8KSjLO3_-M},
}
Figure