Polar Coding for the Binary Erasure Channel with Deletions

Eldho K. Thomas, Vincent Y. F. Tan, Alexander Vardy, Mehul Motani

Abstract

Polar codes, while capacity-achieving for memoryless channels, face significant challenges in channels with synchronization errors like deletions. This paper explores a cascaded channel model consisting of a Binary Erasure Channel (BEC) followed by a single adversarial deletion. We propose a decoding strategy that treats deletions as erasures by generating a candidate set of vectors with inserted erasure symbols. By employing List Successive Cancellation (SC) decoding combined with an optimized Cyclic Redundancy Check (CRC), we demonstrate that reliable communication is achievable with $O(N^2 \log N)$ complexity. Numerical simulations confirm that the probability of decoding error and list ambiguity vanishes as the blocklength increases.

Introduction

In traditional coding theory, erasures are relatively straightforward to handle because the receiver knows the exact location of the missing data. In contrast, deletions cause a loss of synchronization, shifting all subsequent bits and making the channel "memory-dependent." While polar codes are highly effective for memoryless channels, they are not inherently designed for synchronization errors. This work addresses a specific "cascade" model where a message passes through a BEC and then suffers a single adversarial deletion.

System model of the cascaded erasure-deletion channel.

Methods

To bridge the gap between polar codes and deletion channels, we propose a three-step approach:

  1. Erasure Insertion: Since the deletion location is unknown, the receiver generates a "candidate set" by inserting an erasure symbol (e) at every possible position in the received string. This converts the synchronization problem into a set of standard erasure problems.
  2. List Successive Cancellation (SC) Decoding: The standard polar SC decoder is applied to every vector in the candidate set. Polar codes' robustness to erasures ensures the true message is likely within the resulting list.
  3. CRC Pruning: A Cyclic Redundancy Check (CRC) is used to identify the correct message from the list. We optimize the number of CRC bits $r$ to scale as $\Theta(\sqrt{N})$, balancing error probability against code rate overhead.

Results

The proposed method was evaluated through MATLAB simulations with blocklengths $N$ from $2^6$ to $2^{11}$ and an erasure probability $p=0.3$.

Overall error probabilities vs. log block length for various code rates R.

As shown in Figure 2, the overall error probability decreases significantly as the blocklength $N$ increases. Furthermore, the probability that the CRC fails to reduce the list size to 1 ($|\mathcal{L}| > 1$) also tends toward zero, indicating successful list convergence. The total decoding complexity remains polynomial at $O(N^2 \log N)$, making it significantly more efficient than brute-force synchronization methods.

Conclusion

This research demonstrates that polar codes can be effectively adapted for deletion channels by leveraging their inherent erasure-correction capabilities. While the current work focuses on a single adversarial deletion, the framework can be generalized to a finite number of deletions $d$ with $O(N^{d+1} \log N)$ complexity. Future work will address probabilistic deletion models and burst deletions.

Summary updated

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.
BibTeX
@article{thomas2017polar,
  author = {Eldho K. Thomas and Vincent Y. F. Tan and Alexander Vardy and Mehul Motani},
  title = {{Polar Coding for the Binary Erasure Channel with Deletions}},
  journal = {IEEE Communications Letters},
  year = {2017},
  doi = {10.1109/lcomm.2017.2650918},
}
Figure