  A method for efficiently constructing polar codes is presented and analyzed.
Although polar codes are explicitly defined, straightforward construction is
intractable since the resulting polar bit-channels have an output alphabet that
grows exponentially with he code length. Thus the core problem that needs to be
solved is that of faithfully approximating a bit-channel with an intractably
large alphabet by another channel having a manageable alphabet size. We devise
two approximation methods which "sandwich" the original bit-channel between a
degraded and an upgraded version thereof. Both approximations can be
efficiently computed, and turn out to be extremely close in practice. We also
provide theoretical analysis of our construction algorithms, proving that for
any fixed $\epsilon > 0$ and all sufficiently large code lengths $n$, polar
codes whose rate is within $\epsilon$ of channel capacity can be constructed in
time and space that are both linear in $n$.
