  This paper presents the first proof of polarization for the deletion channel
with a constant deletion rate and a regular hidden-Markov input distribution. A
key part of this work involves representing the deletion channel using a
trellis and describing the plus and minus polar-decoding operations on that
trellis. In particular, the plus and minus operations can be seen as combining
adjacent trellis stages to yield a new trellis with half as many stages. Using
this viewpoint, we prove a weak polarization theorem for standard polar codes
on the deletion channel. To achieve strong polarization, we modify this scheme
by adding guard bands of repeated zeros between various parts of the codeword.
This gives a scheme whose rate approaches the mutual information and whose
probability of error decays exponentially in the cube-root of the block length.
We conclude by showing that this scheme can achieve capacity on the deletion
channel by proving that the capacity of the deletion channel can be achieved by
a sequence of regular hidden-Markov input distributions.
