Abstract
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 1 , W2,..., W ℓ Notably, if W is a BEC with erasure probability z, then each of W 1 , W 2 ,..., W∞ is also a BEC. The erasure probabilities of W 1 , W2,..., W∞ are polynomials in z with integer coefficients and degree at most ℓ. We refer to the corresponding set of polynomials {p 1 (z), p 2 (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 0 ⊂ C 1 ⊂ ... ⊂ 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 16 (, with μ(K 16 ) = 3.356. We conjecture that this is optimal for ℓ ≤ 16.