On the scaling exponent of binary polarization kernels

It is well known that polar coding achieves capacity, but it is so far unknown exactly how fast polar codes approach channel capacity as a function of their blocklength. More precisely, let us fix a binary-input memoryless symmetric channel W of capacity I(W) and a desired probability of error P_e. Given W and P_e, suppose we wish to communicate at rate I(W) - Δ using a polar code of length n. It has been recently shown that this value of n scales as O (Δ^-μ), where the constant μ is known as the scaling exponent. In particular, if W is the binary erasure channel (BEC), then μ = 3.627. This is somewhat disappointing, since random codes achieve the (optimal) scaling exponent μ* = 2. As shown by Arıkan, channel polarization can be induced via a simple linear transformation: iterated Kronecker product of a 2 × 2 binary matrix G, called the polarization kernel, with itself. Is it possible to improve the scaling exponent of polar codes (on the BEC) if G is replaced by an ℓ × ℓ binary kernel matrix K for some integer ℓ ≥ 3? This is the question we address in the present paper. It was conjectured by Hassani that as ℓ → ∞, a random choice of the polarization kernel K approaches the optimal scaling exponent μ* = 2. However, herein, we are primarily interested in small values of ℓ. We begin with the fact that a given ℓ × ℓ polarization kernel K transforms ℓ copies of the underlying channel W into ℓ bit-channels W₁, W2,..., W_ℓ Notably, if W is a BEC with erasure probability z, then each of W₁, W₂,..., W∞ is also a BEC. The erasure probabilities of W₁, W2,..., W∞ are polynomials in z with integer coefficients and degree at most ℓ. We refer to the corresponding set of polynomials {p- sub>1(z), p₂(z),..., p_ℓ(z)} as the polarization behavior of K; the scaling exponent of K is completely determined by its polarization behavior. We show that the polarization behavior can be characterized in terms of a nested chain of linear codes: {0} = C₀ ⊂ C₁ ⊂ ... ⊂ C_ℓ-1 ⊂ C_ℓ{0,1}^ℓ and use this nested chain of codes to prove that computing the polarization behavior is NP-hard. We further prove that an arbitrary ℓ × ℓ polarization kernel K can be transformed into a lower-triangular form without altering its polarization behavior. We then use this result to answer the following question: what is the smallest value of ℓ for which Arıkan´s scaling exponent μ(G) = 3.627 can be improved? We show that μ(K) ≥ 3.627 for all ℓ × ℓ kernels with ℓ ≤ 7. On the other hand, we explicitly construct an 8 × 8 matrix Kg with μ(K_g) = 3.577 (and prove that it is optimal for ℓ ≤ 8). We extend our construction of Kg into a general heuristic design method. Guided by this design method, we employ the coset structure of Reed-Muller codes and bent functions in order to explicitly construct a 16 × 16 kernel K₁₆(, with μ(K₁₆) = 3.356. We conjecture that this is optimal for ℓ ≤ 16.