On the scaling exponent of binary polarization kernels
Arman Fazeli, Alexander Vardy · 2014
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 Pe. Given W and Pe, 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 W1, W2,..., WℓNotably, if W is a BEC with erasure probability z, then each of W1, W2,..., W∞ is also a BEC. The erasure probabilities of W1, W2,..., W∞ are polynomials in z with integer coefficients and degree at most ℓ. We refer to the corresponding set of polynomials {p1(z), p2(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} = C0⊂ C1⊂ ... ⊂ 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 μ(Kg) = 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 K16(, with μ(K16) = 3.356. We conjecture that this is optimal for ℓ ≤ 16.