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.
Methods
To bridge the gap between polar codes and deletion channels, we propose a three-step approach:
- 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. - 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.
- 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$.
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