A packing lemma for polar codes

A packing lemma is proved using a setting where the channel is a binary-input discrete memoryless channel (X,w(y|x),Y ), the code is selected at random subject to parity-check constraints, and the decoder is a joint typicality decoder. The ensemble is characterized by (i) a pair of fixed parameters (H,q) where H is a parity-check matrix and q is a channel input distribution and (ii) a random parameter S representing the desired parity values. For a code of length n, the constraint is sampled from p_S(s)=Σxⁿ∈Xⁿ φ(s,xⁿ)qⁿ(xⁿ) where φ(s,xⁿ) is the indicator function of event {s = xⁿH^T} and qⁿ(xⁿ) = Π_i=1ⁿ q(x_i). Given S = s, the codewords are chosen conditionally independently from p_Xn|S(xⁿ|s) ∝ φ(s,xⁿ)qⁿ(xⁿ). It is shown that the probability of error for this ensemble decreases exponentially in n provided the rate R is kept bounded away from I(X;Y )-1 over nI(S;Yⁿ) with (X,Y ) ~ q(x)w(y|x) and (S,Yⁿ) ~ p_S(s)Σxⁿ p_Xn|S(xⁿ|s)Π_i=1ⁿ=w(y_i|x_i). In the special case where H is the parity-check matrix of a standard polar code, it is shown that the rate penalty 1 over nI(S;Yⁿ) vanishes as n increases. The paper also discusses the relation between ordinary polar codes and random codes based on polar parity-check matrices.