Polar Coding for Channels With Deletions

Deletion errors are notoriously difficult to correct. The capacity of the binary deletion channel is not yet fully known, and there is no completely satisfactory solution even to the specific problem of correcting
only two
deletion errors. In this paper, we show that polarization theory, along with the powerful methods of polar coding and successive-cancellation decoding, can be extended to channels with deletion errors. Our results further generalize to channels corrupted by insertion errors and/or combinations of insertions and deletions. It was recently proposed to correct deletion errors using polar codes designed for the BEC, precoded with a sufficiently powerful CRC code. In this approach, in order to correct
${d}$
deletions in a codeword of length
${n}$
, successive-cancellation decoding is run separately for each of the
$\binom {n}{d}$
possible deletion patterns, while treating the deleted symbols as erasures. The resulting complexity of decoding is
${O}\bigl ({n}^{d+1}\log {n}\bigr)$
. In contrast, we develop herein a natural generalization of successive-cancellation decoding to channels with deletion errors. Our algorithm is based on the recursive structure of polar codes, processing the channel output in
${m} = \log _{2} {n}$
decoding layers, just like the conventional successive-cancellation decoder. Every node in each decoding layer propagates its uncertainty about the deletion pattern to the nodes in the next layer and, eventually, the correct deletion pattern becomes visible at the decoder output, with high probability. This makes it possible to consider at most
$\binom {d+2}{2}$
scenarios at each node, and the overall decoding complexity is only
${O}\bigl ({d}^{3} {n} \log {n}\bigr)$
, which scales polynomially rather than exponentially with the number of deletions. Based on the proposed algorithm, we also investigate the channel polarization phenomenon. We are able to prove weak polarization where the number of deletions
${d}$
is small,
i.e.

${d}={o}({n})$
. We also conjecture the strong polarization for when
${d}={O}(1)$
and provide some evidence to support this conjecture. The strong polarization, if proven, implies that our coding scheme achieves the capacity of any binary-input symmetric channel which furthermore introduces a constant number of deletions.