Reduced-Complexity Successive-Cancellation Decoding for Polar Codes on Channels with Insertions and Deletions

In this paper, a simplified successive cancellation (SC) decoding algorithm for polar codes on insertiondeletion error channels is proposed. First, the SC decoding is designed to decode polar codes on insertiondeletion channels and the joint weight distribution is derived to measure the occurrence probability of different scenarios. Some scenarios with small occurrence probability can be pruned to obtain lower decoding complexity with negligible performance loss. Inspired by this, a fixed pruning strategy (FPS) is proposed to reduce the decoding complexity, which can prune as many scenarios as possible with the given performance requirement. By exploiting the periodicity of the joint weight distribution, the upper bound of the block error rate of the pruned SC decoding is derived. Furthermore, according to the convergence of the upper bound, a dynamic self-adjusting pruning strategy is designed to further reduce the decoding complexity and improve the flexibility of the pruning algorithm. Simulation results show that the decoding complexity of the proposed pruning-based decoding algorithms is significantly reduced compared to the state-of-the-art scenario simplified SC decoding algorithm.