Polar codes were recently introduced by Ar‡kan. They achieve the capac-
ity of arbitrary symmetric 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£1 0
1 1. It was shown
by Ar‡kan and Telatar that this construction achieves an error exponent of12, i.e., that for su–ciently large blocklengths the error probability decays
exponentially in the square root of the length.
We flrst generalize the result of Arikan and Telatar by characterizing the
exponent of any‘£‘matrix. We derive upper and lower bounds on the
achievable exponents and show that the exponent cannot be improved for‘ <15. We also provide a general construction based on BCH codes which
for large‘achieves exponents arbitrarily close to 1 and which exceeds12for
size 16.
We then consider source coding. We show that polar codes with succes-
sive cancellation encoding also achieves the optimum rate-distortion tradeofi
for a binary symmetric source. Moreover, using these codes we can construct
nested codes which achieve the optimum performance of the Wyner-Ziv and
Gelfand-Pinsker setups.
[The talk is based on joint work with Eren S»a»so‚glu and R˜udiger Urbanke.]
1