A list decoding scheme for universal polar codes is presented. Our scheme applies to the universal polar codes first introduced by Sasoglu and Wang, and generalized to processes with memory by the authors. These codes are based on the concatenation of different polar transforms: a sequence of "slow" transforms and Arikan's original "fast" transform. List decoding of polar codes has been previously presented in the context of the fast transform. However, the slow transform is markedly different and requires new techniques and data structures. We show that list decoding is possible with space complexity O(L N) and time complexity O(L N log N), where N is the overall blocklength and L is the list size.
Although iterative decoding of polar codes has recently made huge progress based on the idea of permuted factor graphs, it still suffers from a non-negligible performance degradation when compared to state-of-the-art CRC-aided successive cancellation list (CA-SCL) decoding. In this work, we show that iterative decoding of polar codes based on the belief propagation list (BPL) algorithm can approach the error-rate performance of CA-SCL decoding and, thus, can be efficiently used for decoding the standardized 5G polar codes. Rather than only utilizing the cyclic redundancy check (CRC) as a stopping condition (i.e., for error-detection), we also aim to benefit from the error-correction capabilities of the outer CRC code. For this, we develop two distinct soft-decision CRC decoding algorithms: a Bahl-Cocke-Jelinek-Raviv (BCJR)-based approach and a sum product al- gorithm (SPA)-based approach. Further, an optimized selection of permuted factor graphs is analyzed and shown to reduce the decoding complexity significantly. Finally, we benchmark the proposed CRC-aided belief propagation list (CA-BPL) decoding to state-of-the-art 5G polar codes under CA-SCL decoding and, thereby, showcase an error-rate performance not just close to the CA-SCL but also close to the maximum likelihood (ML) bound as estimated by ordered statistic decoding (OSD).
This work analyzes the latency of the simplified successive cancellation (SSC) decoding scheme for polar codes proposed by Alamdar-Yazdi and Kschischang. It is shown that, unlike conventional successive cancellation decoding, where latency is linear in the block length, the latency of SSC decoding is sublinear. More specifically, the latency of SSC decoding is O(N^(1−1/µ)), where N is the block length and µ is the scaling exponent of the channel, which captures the speed of convergence of the rate to capacity. Numerical results demonstrate the tightness of the bound and show that most of the latency reduction arises from the parallel decoding of subcodes of rate 0 and 1.
Recursive trellis decoding of polar codes is considered. Polar codes are shown to have much lower recursive trellis decoding complexity compared to similar Reed-Muller codes. Furthermore, a low-latency decoding algorithm, which combines recursive trellis and successive cancellation decoding methods, is presented.
In this paper, we present an improved belief propagation list decoding (BPL) for polar codes. Rather than choosing L permuted factor graphs (FGs) at random, we use the upper bounds on the block error propability of polar codes with different permuted FGs as the metric to choose the best L permuted FGs. By observing the bounds of different permuted FGs, we propose a heuristic method to reduce search complexity. Simulation results show that there is only a gap of 0.2 dB between the frame error rate (FER) performance of the improved BPL decoder using RM16-GA construction and that of length-1024 5G polar code decoded by SCL with the same list size of 32 at FER = 10^−4, but with proposed factor graph selection method, BPL can reduce clock cycles by 97.74% compared with the SCL decoding.
A new polar-coded modulation (PCM) framework with the bit interleaving is proposed to enhance the polarization diversity among the bit polarized subchannels under the finite block length, consequently, the transmission reliability is further improved. The key idea is asynchronously transmitting the coded bits within one block and spatially coupling multiple coded blocks by the joint modulation, and the polarization diversity among the modulation synthesized subchannels under the parallel partition is enhanced. Combining the binary polar coding, this polarization enhancement at the modulation partition stage is then delivered to the final bit polarized subchannels. The capacity-achieving property under the infinite block length and the polarization superiority with respect to state-of-the-art PCM schemes under the finite block length are proved. Finally, the simulation results indicate the performance gain compared to the conventional PCM and 5G LDPC coded modulation schemes.