Polar Codes:Characterization of Exponent, Bounds, and Constructions
Proceedings of the IEEE International Symposium on Information Theory, Seoul, South Korea, June 2009
Abstract

Polar   codes  were recently introduced by Arikan. They achieve the symmetric capacity of arbitrary binary-input discrete memoryless channels under a low complexity successive cancellation decoding strategy. The original  polar  code  construction  is closely related to the recursive  construction  of Reed-Muller  codes  and is based on the 2 × 2 matrix of the given equation. It was shown by Arikan and Telatar that this  construction  achieves an error  exponent  of 1/2, i.e., that for sufficiently large block-lengths the error probability decays exponentially in the square root of the length. It was already mentioned by Arikan that in principle larger matrices can be used to construct  polar   codes . A fundamental question then is to see whether there exist matrices with  exponent  exceeding 1/2. We characterize the  exponent  of a given square matrix and derive upper and lower  bounds  on achievable  exponents . Using these  bounds  we show that there are no matrices of size less than 15 with  exponents  exceeding 1/2. Further, we give a general  construction  based on BCH  codes  which for large matrix sizes achieves  exponents  arbitrarily close to 1 and which exceeds 1/2 for size 16.