Deep Polar Codes

Abstract

The proliferation of mission-critical applications underscores the need for a com- munication system that supports ultra-reliable low-latency communication (URLLC). The concept of URLLC aims to deliver data packets within a very short time duration (e.g., 1 ms) with extremely high reliability (e.g., 10−3). To meet these stringent re- quirements, it is essential to have a channel coding technology that operates at rates close to the finite-blocklength capacity while being fast decodable. Polar codes are the first explicitly constructed error-correcting codes over binary- input memoryless channels that provably achieve asymptotic capacity using low com- plexity encoding and decoding algorithms. Applying an upper-triangular pre-transform before polar encoding can improve the distance properties of existing polar codes. These pre-transformed polar codes not only allow for low-complexity decodability but also provide a universal representation of binary linear codes, making them an attractive design candidate. In the first chapter, we introduce a novel class of pre-transformed polar codes, termed “deep polar codes.” The encoder performs a series of multi-layered polar trans- formations with varying sizes. Our approach to encoding enables a low-complexity implementation while significantly enhancing the weight distribution of the code. Moreover, our encoding method offers flexibility in rate-profiling, embracing a wide range of code rates and blocklengths. Next, we put forth a low-complexity decod- ing algorithm called successive cancellation list with “backpropagation parity check” (SCL-BPC). This decoding algorithm leverages the parity check equations in the re- verse process of the multi-layered pre-transformed encoding for SCL decoding. Ad- ditionally, we present a low-latency decoding algorithm that employs parallel SCL decoding by treating partially pre-transformed bit patterns as additional frozen bits. In simulations, we demonstrate that deep polar codes outperform existing pre-transformed polar codes in terms of block error rates across various code rates under short block lengths, while maintaining low encoding and decoding complexity. Furthermore, we show that concatenating deep polar codes with cyclic-redundancy-check (CRC) codes can achieve the meta-converse bound of the finite block length capacity within 0.4 dB in some instances. In the second chapter, we modify deep polar codes to be more suitable for SCL decoders with small list sizes. The key idea is to limit the number of consecutive semi-polarized information bits. To achieve this, we propose applying multiple po- lar pre-transform matrices in parallel. Additionally, we present an algorithm to select the indices for applying the pre-transform, based on an analysis of the formation of minimum-weight codewords after pre-transformation. This approach efficiently re- duces the number of minimum-weight codewords. Extensive simulation results under various blocklengths and code rates have demonstrated that our codes consistently outperform all existing state-of-the-art pre-transformed polar codes, including CRC- aided polar codes and polarization-adjusted convolutional codes. Notably, we confirm that our code is particularly effective for SCL decoders with small list sizes.