International Symposium on Turbo Codes and Iterative Information Processing

Modified augmented belief propagation for general memoryless channels

Benjamin Gadat, Charly Poulliat

Published Sep 1, 2016• 1 citation

Abstract

In this paper, we propose an efficient implementation of the augmented belief propagation (ABP) algorithm for low-density parity-check codes over general memoryless channels. ABP is a multistage BP based decoder that uses a backtracking processing when decoding fails. The algorithm proceeds in two main steps, namely a symbol selection step and an augmented decoding step. The former is based on a criterion related both to the stopping subgraph connectivity and to the input reliability, while the latter can be either implemented using a list based or a greedy approach. Compared to the original implementation, we consider a different approach for both steps. First, the proposed node selection is only based on the dynamic of sign changes of the extrinsic messages at the variable nodes output. This enables us to consider indifferently general memoryless channels, while still taking into account the graph irregularity. Then, we propose a simple yet efficient implementation of the augmented decoding procedure based on pruning of the branching tree The proposed algorithm shows near maximum likelihood decoding performance while decreasing the overall complexity (computation and memory) of the original algorithm. Moreover, complexity-performance trade-off is an built-in feature for this kind of algorithm.

DOI: 10.1109/istc.2016.7593103

Related papers

Augmented Belief-Propagation Decoding of Low-Density Parity-Check Codes

Nedeljko Varnica, M.P.C. Fossorier, A. Kavcic

We propose an augmented belief-propagation (BP) decoder for low-density parity-check (LDPC) codes which can be used on memoryless or intersymbol-interference (ISI) channels. The proposed method is a heuristic algorithm that eliminates a large number of pseudocodewords that can cause nonconvergence in the BP decoder. The augmented decoder is a multistage iterative decoder, where at each stage, the original channel messages on select symbol nodes are replaced by saturated messages. The key element of the proposed method is the symbol-selection process, which is based on the appropriately defined subgraphs of the code graph and/or the reliability of the information received from the channel. We demonstrate by examples that this decoder can be implemented to achieve substantial gains (compared with the standard locally operating BP decoder) for short LDPC codes decoded on both memoryless and ISI Gaussian channels. Using the Margulis code example, we also show that the augmented decoder reduces the error floors. Finally, we discuss types of BP decoding errors and relate them to the augmented BP decoder.

IEEE Transactions on CommunicationsOct 1, 20064 citations

Augmented Belief Propagation Decoding of Low-Density Parity Check Codes

Nedeljko Varnica, M.P.C. Fossorier, A. Kavcic

We propose an augmented belief propagation (BP) decoder for low-density parity check (LDPC) codes which can be utilized on memoryless or intersymbol interference channels. The proposed method is a heuristic algorithm that eliminates a large number of pseudocodewords that can cause nonconvergence in the BP decoder. The augmented decoder is a multistage iterative decoder, where, at each stage, the original channel messages on select symbol nodes are replaced by saturated messages. The key element of the proposed method is the symbol selection process, which is based on the appropriately defined subgraphs of the code graph and/or the reliability of the information received from the channel. We demonstrate by examples that this decoder can be implemented to achieve substantial gains (compared to the standard locally-operating BP decoder) for short LDPC codes decoded on both memoryless and intersymbol interference Gaussian channels. Using the Margulis code example, we also show that the augmented decoder reduces the error floors. Finally, we discuss types of BP decoding errors and relate them to the augmented BP decoder.

IEEE Transactions on CommunicationsJul 1, 200764 citations

Improved augmented belief propagation decoding based on oscillation

Mu Zhou, Xiqi Gao

The augmented belief propagation (ABP) decoding using previous node selection methods for low-density parity check (LDPC) codes with a large number of short cycles is investigated on the additive white Gaussian noise (AWGN) channel in this paper. Based on the observations obtained from the investigation, a new node selection method is proposed. It is shown that oscillation plays an important role in the ABP decoding and needs to be controlled. It is also shown that the most possible variable nodes needed to stop oscillation in cycles should be selected and kept stable in correct values in the ABP decoding. A parallel decoding scheme is also proposed, which proves that a better method exists. Simulation results confirm that the new method outperforms the previous ones for short LDPC codes on the AWGN channel.

Asia-Pacific Conference on Communications (APCC)Oct 1, 20083 citations

Tree-Structure Expectation Propagation for LDPC Decoding Over the BEC

Pablo M. Olmos, Juan Jose Murillo-Fuentes, Fernando Pérez‐Cruz

We present the tree-structure expectation propagation (Tree-EP) algorithm to decode low-density parity-check (LDPC) codes over discrete memoryless channels (DMCs). Expectation propagation generalizes belief propagation (BP) in two ways. First, it can be used with any exponential family distribution over the cliques in the graph. Second, it can impose additional constraints on the marginal distributions. We use this second property to impose pairwise marginal constraints over pairs of variables connected to a check node of the LDPC code's Tanner graph. Thanks to these additional constraints, the Tree-EP marginal estimates for each variable in the graph are more accurate than those provided by BP. We also reformulate the Tree-EP algorithm for the binary erasure channel (BEC) as a peeling-type algorithm (TEP) and we show that the algorithm has the same computational complexity as BP and it decodes a higher fraction of errors. We describe the TEP decoding process by a set of differential equations that represents the expected residual graph evolution as a function of the code parameters. The solution of these equations is used to predict the TEP decoder performance in both the asymptotic regime and the finite-length regimes over the BEC. While the asymptotic threshold of the TEP decoder is the same as the BP decoder for regular and optimized codes, we propose a scaling law for finite-length LDPC codes, which accurately approximates the TEP improved performance and facilitates its optimization.

arXiv:1201.0715IEEE Transactions on Information TheoryFeb 6, 201315 citations

Tree-structure expectation propagation for LDPC decoding over the BEC

Pablo M. Olmos, Juan José Murillo-Fuentes

Abstract—We present the tree-structure expectation propa-gation (Tree-EP) algorithm to decode low-density parity-check (LDPC) codes over discrete memoryless channels (DMCs). EP generalizes belief propagation (BP) in two ways. First, it can be used with any exponential family distribution over the cliques in the graph. Second, it can impose additional constraints on the marginal distributions. We use this second property to impose pair-wise marginal constraints over pairs of variables connected to a check node of the LDPC code’s Tanner graph. Thanks to these additional constraints, the Tree-EP marginal estimates for each variable in the graph are more accurate than those provided by BP. We also reformulate the Tree-EP algorithm for the binary erasure channel (BEC) as a peeling-type algorithm (TEP) and we show that the algorithm has the same computational complexity as BP and it decodes a higher fraction of errors. We describe the TEP decoding process by a set of differential equations that represents the expected residual graph evolution as a function of the code parameters. The solution of these equations is used to predict the TEP decoder performance in both the asymptotic regime and the finite-length regime over the BEC. While the asymptotic threshold of the TEP decoder is the same as the BP decoder for regular and optimized codes, we propose a scaling law (SL) for finite-length LDPC codes, which accurately approximates the TEP improved performance and facilitates its optimization. I.

Jan 1, 201318 citations

Tree Expectation Propagation for LDPC Decoding over the BEC

Pablo M. Olmos, Juan José Murillo-Fuentes, Fernando Pérez‐Cruz

We present the tree-structure expectation propagation (Tree-EP) to decode low-density parity-check (LDPC) codes over discrete memoryless channels (DMCs). EP generalizes belief propagation (BP) in two ways. First, it can be used with any exponential family distribution over the cliques in the graph. Second, it can impose additional constraints on the marginal distributions. We use this second property to impose pair-wise marginal constraints over pairs of variables connected to a check node of the LDPC code's Tanner graph. Thanks to these additional constraints, the Tree-EP marginal estimates for each variable in the graph are more accurate than those provided by BP. We also reformulate the Tree-EP algorithm for the binary erasure channel (BEC) as a peeling-type algorithm (TEP) and we show that the algorithm has the same computational complexity as BP and it decodes a higher fraction of errors. We describe the TEP decoding process by a set of differential equations that represents the expected residual graph evolution as a function of the code parameters. The solution of these equations is used to predict the TEP decoder performance in both the asymptotic regime and the finite-length regime over the BEC. While the TEP decoder asymptotically performs as the BP for regular and optimized codes. For finite-length LDPC codes, we derive a scaling law to predict the decoder performance that can be used for LDPC optimization.

Jan 3, 20120 citations