Title: Polar Coding for the Binary Erasure Channel with Deletions,
Abstract: We study the application of polar codes in deletion channels by analyzing the
cascade of a binary erasure channel (BEC) and a deletion channel. We show how
polar codes can be used effectively on a BEC with a single deletion, and
propose a list decoding algorithm with a cyclic redundancy check for this case.
The decoding complexity is $O(N^2\log N)$, where $N$ is the blocklength of the
code. An important contribution is an optimization of the amount of redundancy
added to minimize the overall error probability. Our theoretical results are
corroborated by numerical simulations which show that the list size can be
reduced to one and the original message can be recovered with high probability
as the length of the code grows.