2014 · 55 citations · 9 references
EngineeringComputer ScienceElectrical EngineeringDigital CommunicationInformation TheoryTheory Of ComputationChannel CapacityChannel CodingCoding TheoryError Control CodingError-correcting CodesChannel Capacity ApproximationsError ExponentsFinite Blocklength Channel CapacityPolar CodesPolarizationSymmetric Channel Capacity
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.
9
Finite-length scaling of polar codes
Kasra Alishahi · 2016 · 139 citations
Algorithmic complexity in coding theory and the minimum distance problem
Alexander Vardy · 1997 · 117 citations