Polar Coding for Channels With Deletions (2021)

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 <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">only two</i> 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 <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">${d}$ </tex-math></inline-formula> deletions in a codeword of length <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">${n}$ </tex-math></inline-formula> , successive-cancellation decoding is run separately for each of the <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$\binom {n}{d}$ </tex-math></inline-formula> possible deletion patterns, while treating the deleted symbols as erasures. The resulting complexity of decoding is <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">${O}\bigl ({n}^{d+1}\log {n}\bigr)$ </tex-math></inline-formula> . 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 <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">${m} = \log _{2} {n}$ </tex-math></inline-formula> 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 <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$\binom {d+2}{2}$ </tex-math></inline-formula> scenarios at each node, and the overall decoding complexity is only <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">${O}\bigl ({d}^{3} {n} \log {n}\bigr)$ </tex-math></inline-formula> , 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 <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">${d}$ </tex-math></inline-formula> is small, <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">i.e.</i> <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">${d}={o}({n})$ </tex-math></inline-formula> . We also conjecture the strong polarization for when <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">${d}={O}(1)$ </tex-math></inline-formula> 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.