Iterative Decoding : A Unifying Factor Graph Approach

Tadashi Wadayama

Ahmed Elkelesh, Moustafa Ebada, Sebastian Cammerer +1 more

We show that the performance of iterative belief propagation (BP) decoding of polar codes can be enhanced by decoding over different carefully chosen factor graph realizations. With a genie-aided stopping condition, it can achieve the successive cancellation list (SCL) decoding performance which has already been shown to achieve the maximum likelihood (ML) bound provided that the list size is sufficiently large. The proposed decoder is based on different realizations of the polar code factor graph with randomly permuted stages during decoding. Additionally, a different way of visualizing the polar code factor graph is presented, facilitating the analysis of the underlying factor graph and the comparison of different graph permutations. In our proposed decoder, a high rate Cyclic Redundancy Check (CRC) code is concatenated with a polar code and used as an iteration stopping criterion (i.e., genie) to even outperform the SCL decoder of the plain polar code (without the CRC-aid). Although our permuted factor graph-based decoder does not outperform the SCL-CRC decoder, it achieves, to the best of our knowledge, the best performance of all iterative polar decoders presented thus far.

Takuya Koumoto

Duan Linli

The LDPC coded bit-interleaved coded modulation iterative decoding(BICM-ID)system was modeled by a normal factor graph.From the angle of the message update rule,uniformly reweighted belief propagation algorithm(URW-BP)and belief propagation algorithm(BP)are unified and interpreted as message passing algorithm by variation method.Combining the local nature of BP with the improved performance of URW-BP in graphs with cycles,the uniformly reweighted iterative decoding algorithm(URID)was derived and the impact of edge appearance probabilities(EAP)on its performance discussed. Simulation results for AWGN and Rayleigh fading channel and different modulation illustrate the performance improvement of URID compared with other iterative decoding algorithms such as BP and DifferenceMap BP(DMBP)algorithm.

Wei Yongmei, Kambiz Homayounfar

Vismika Ranasinghe, Nandana Rajatheva, Matti Latva‐aho

Belief propagation (BP) is an iterative decoding algorithm for polar codes which can be parallelized effectively to achieve higher throughput. However, because of the presence of error floor due to cycles and stopping sets in the factor graph, the performance of the BP decoder is far from the performance of state of the art cyclic redundancy check (CRC) aided successive cancellation list (CA-SCL) decoders. It has been shown that successive BP decoding on multiple permuted factor graphs, which is called the multi-trellis BP decoder, can improve the error performance. However, when permuting the entire factor graph, since the decoder dismisses the information from the previous permutation, the number of iterations required is significantly larger than that of the standard BP decoder. In this work, we propose a new variant of the multi-trellis BP decoder which permutes only a subgraph of the original factor graph. This enables the decoder to retain information of variable nodes in the subgraphs, which are not permuted, reducing the required number of iterations needed in-between the permutations. As a result, the proposed decoder can perform permutations more frequently, hence being more effective in mitigating the effect of cycles which cause oscillation errors. Experimental results show that for a polar code with block length 1024 and rate 0.5 the error performance gain of the proposed decoder at the frame error rate of $10^{-6}$ is 0.25 dB compared to multi-trellis decoder based on full permutations. This performance gain is achieved along with reduced latency in terms of the number of iterations.