Gaussian Approximation for Polar Code Construction

Polar codes, invented by Erdal Arıkan in 2009, achieve channel capacity through a phenomenon called channel polarization. To construct an efficient polar code, we need to identify which bit channels are reliable (used for information) and which are unreliable (frozen to known values).

Gaussian Approximation (GA) is a computationally efficient method to estimate the reliability of each bit channel without running expensive Monte Carlo simulations.

The Channel Polarization Problem

When we encode a message using polar codes, the original channel splits into $N$ virtual bit channels with varying reliabilities. Our goal is to:

Rank all $N$ bit channels by reliability
Select the $K$ most reliable channels for information bits
Freeze the remaining $N-K$ channels to zero

The challenge: How do we efficiently compute these reliabilities?

The φ Function

To track how reliability evolves through the tree, we use the φ function and its inverse:

\[\phi(x) = \begin{cases} e^{0.0564x^2 - 0.4856x} & \text{if } x < 0.867861 \\ e^{-0.4527x^{0.86} + 0.0218} & \text{otherwise} \end{cases}\]

The φ⁻¹ Function

The inverse function is computed as:

\[\phi^{-1}(t) = \begin{cases} 4.304964539 \cdot \left(1 - \sqrt{1 + 0.9567131408 \cdot \ln(t)}\right) & \text{if } t > 0.6845772418 \\ \left(\frac{\ln(t)}{\alpha} + \frac{-\beta}{\alpha}\right)^{1/\gamma} & \text{otherwise} \end{cases}\]

where $\alpha = -0.4527$, $\beta = 0.0218$, and $\gamma = 0.8600$.

Density Evolution with GA

Starting from the channel reliability $m_0 = \frac{2}{\sigma^2}$, we recursively compute reliabilities:

Left Child (Check Node) — The reliability decreases (channel becomes worse):

\[m_{\text{left}} = \phi^{-1}\left(1 - (1-\phi(m_1))(1-\phi(m_2))\right)\]

Right Child (Variable Node) — The reliability increases (channel becomes better):

\[m_{\text{right}} = m_1 + m_2\]

Algorithm Summary

Algorithm: Gaussian Approximation for Polar Code Construction

Input:  N (code length), σ (noise standard deviation)
Output: Ranked list of bit channel reliabilities

1. Initialize: m[i] = 2/σ² for all N channels

2. Recursively traverse the polar code tree:
   - At each left branch:  m_new = φ⁻¹(1 - (1-φ(m₁))(1-φ(m₂)))
   - At each right branch: m_new = m₁ + m₂

3. Collect leaf node reliabilities

4. Sort channels by reliability (descending)

5. Return: K most reliable indices → information bits
          N-K least reliable indices → frozen bits

Visual Representation

                    [m₀, m₀, m₀, m₀]
                          |
            ┌─────────────┴─────────────┐
            │                           │
       [m₁, m₁]                    [m₂, m₂]
      (check node)               (variable node)
       m₁ < m₀                     m₂ > m₀
            │                           │
      ┌─────┴─────┐               ┌─────┴─────┐
      │           │               │           │
    [m₃]       [m₄]             [m₅]       [m₆]
   worst      bad              good        best

As we go down the tree:

Left branches degrade channel quality
Right branches improve channel quality

This creates polarization: channels become either very good or very bad.

Puncturing Support: For punctured polar codes, initialize punctured positions with $m = 0$ (completely unreliable).

Code Example

def gaussian_approximation(N, sigma):
    m = [2.0 / sigma**2] * N  # Initialize channel reliabilities
    reliabilities = []
    
    def recurse(means, stage):
        if len(means) == 1:
            reliabilities.append(means[0])
            return
        
        half = len(means) // 2
        
        # Left branch (check node) - reliability decreases
        left_means = [phi_inv(1 - (1-phi(means[i])) * (1-phi(means[i+half]))) 
                      for i in range(half)]
        
        # Right branch (variable node) - reliability increases  
        right_means = [means[i] + means[i+half] 
                       for i in range(half)]
        
        recurse(left_means, stage - 1)
        recurse(right_means, stage - 1)
    
    recurse(m, int(log2(N)))
    
    # Return indices sorted by reliability (best first)
    return sorted(range(N), key=lambda i: reliabilities[i], reverse=True)

References

Arıkan, E. (2009). “Channel Polarization: A Method for Constructing Capacity-Achieving Codes for Symmetric Binary-Input Memoryless Channels”
Trifonov, P. (2012). “Efficient Design and Decoding of Polar Codes”
Tal, I. & Vardy, A. (2013). “How to Construct Polar Codes”