Joining the Check Nodes in the Factor Graph of the Linear Codes

Veeresh Taranalli, Paul H. Siegel

Polar codes are high density parity check codes and hence the sparse factor graph, instead of the parity check matrix, has been used to practically represent an LP polytope for LP decoding. Although LP decoding on this polytope has the ML-certificate property, it performs poorly over a BAWGN channel. In this paper, we propose modifications to adaptive cut generation based LP decoding techniques and apply the modified-adaptive LP decoder to short block-length polar codes over a BAWGN channel. The proposed decoder provides significant FER performance gain compared to the previously proposed LP decoder and its performance approaches that of ML decoding at high SNRs. We also present an algorithm to obtain a smaller factor graph from the original sparse factor graph of a polar code. This reduced factor graph preserves the small check node degrees needed to represent the LP polytope in practice. We show that the fundamental polytope of the reduced factor graph can be obtained from the projection of the polytope represented by the original sparse factor graph and the frozen bit information. Thus, the LP decoding time complexity is decreased without changing the FER performance by using the reduced factor graph representation.

Martin Bossert, F. Hergert

Nikolai Iakuba, Peter Trifonov

A generalized belief propagation algorithm is proposed for decoding of polar codes. The proposed approach relies on offline successive transformations of the factor graph, which merge parity check nodes into check nodes corresponding to some non-trivial codes. It was shown, that the constructed factor graph for (2048, 1024) polar code provides 0.25 performance gain under generalized belief propagation decoding with 5 iterations and lower worst case complexity compared to state-of-the-art belief propagation decoders of polar codes.

Diego Ruano

Saeid Haghighatshoar, Amin Karbasi, Amir Hesam Salavati

LDPC codes are typically decoded by running a synchronous message passing algorithm over the corresponding bipartite factor graph (made of variable and check nodes). More specifically, each synchronous round consists of 1) updating all variable nodes based on the information received from the check nodes in the previous round, and then 2) updating all the check nodes based on the information sent from variable nodes in the current round. However, in many applications, ranging from message passing in neural networks to hardware implementation of LDPC codes, assuming that all messages are sent and received at the same time is far from realistic. In this paper, we investigate the effect of asynchronous message passing on the decoding of LDPC codes over a Binary Erasure Channel (BEC). We effectively assume that there is a random delay assigned to each edge of the factor graph that models the random propagation delay of a message along the edge. As a result, the output messages of a check/variable node are also asynchronously updated upon arrival of a new message in its input. We show, for the first time for BEC, that the asymptotic performance of the asynchronous message passing is fully characterized by a fixed point integral equation that takes into account both the temporal and the spatial features of the factor graph. Our theoretical result is reminiscent of the fixed point equation in traditional BP decoding. Also, our simulation results show that asynchronous scheduling reduces decoding time compared to the traditional BP in certain cases in the finite block-length regime.

Antoine O. Berthet