Polar Codes for the Deletion Channel: Weak and Strong Polarization
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 this
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.
Using this approach, we obtain a scheme whose rate approaches the mutual
information and whose probability of error decays exponentially in the
cube-root of the block length.