On the scaling exponent of binary polarization kernels

Arman Fazeli, Alexander Vardy

2014 · 55 citations · 9 references

Concepts

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 <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">e</sub> . Given W and P <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">e</sub> , 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 (Δ <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">-μ</sup> ), 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 <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">1</sub> , W2,..., W <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">ℓ</sub> Notably, if W is a BEC with erasure probability z, then each of W <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">1</sub> , W <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">2</sub> ,..., W∞ is also a BEC. The erasure probabilities of W <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">1</sub> , W2,..., W∞ are polynomials in z with integer coefficients and degree at most ℓ. We refer to the corresponding set of polynomials {p <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">1</sub> (z), p <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">2</sub> (z),..., p <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">ℓ</sub> (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 <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">0</sub> ⊂ C <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">1</sub> ⊂ ... ⊂ C <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">ℓ-1</sub> ⊂ C <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">ℓ</sub> {0,1} <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">ℓ</sup> 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 <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">g</sub> ) = 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 <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">16</sub> (, with μ(K <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">16</sub> ) = 3.356. We conjecture that this is optimal for ℓ ≤ 16.

References

9