## 2012 |

Salamanca, Luis; Murillo-Fuentes, Juan Jose; Olmos, Pablo M; Perez-Cruz, Fernando Tree-Structured Expectation Propagation for LDPC Decoding over the AWGN Channel Inproceedings 2012 IEEE International Workshop on Machine Learning for Signal Processing, pp. 1–6, IEEE, Santander, 2012, ISSN: 1551-2541. Abstract | Links | BibTeX | Tags: additive white Gaussian noise channel, Approximation algorithms, Approximation methods, approximation theory, AWGN channel, AWGN channels, belief propagation solution, Bit error rate, Decoding, error floor reduction, finite-length regime, Gain, Joints, LDPC decoding, low-density parity-check decoding, pairwise marginal constraint, parity check codes, TEP decoder, tree-like approximation, tree-structured expectation propagation, trees (mathematics) @inproceedings{Salamanca2012, title = {Tree-Structured Expectation Propagation for LDPC Decoding over the AWGN Channel}, author = {Luis Salamanca and Juan Jose Murillo-Fuentes and Pablo M Olmos and Fernando Perez-Cruz}, url = {http://ieeexplore.ieee.org/lpdocs/epic03/wrapper.htm?arnumber=6349716}, issn = {1551-2541}, year = {2012}, date = {2012-01-01}, booktitle = {2012 IEEE International Workshop on Machine Learning for Signal Processing}, pages = {1--6}, publisher = {IEEE}, address = {Santander}, abstract = {In this paper, we propose the tree-structured expectation propagation (TEP) algorithm for low-density parity-check (LDPC) decoding over the additive white Gaussian noise (AWGN) channel. By imposing a tree-like approximation over the graphical model of the code, this algorithm introduces pairwise marginal constraints over pairs of variables, which provide joint information of the variables related. Thanks to this, the proposed TEP decoder improves the performance of the standard belief propagation (BP) solution. An efficient way of constructing the tree-like structure is also described. The simulation results illustrate the TEP decoder gain in the finite-length regime, compared to the standard BP solution. For code lengths shorter than n = 512, the gain in the waterfall region achieves up to 0.25 dB. We also notice a remarkable reduction of the error floor.}, keywords = {additive white Gaussian noise channel, Approximation algorithms, Approximation methods, approximation theory, AWGN channel, AWGN channels, belief propagation solution, Bit error rate, Decoding, error floor reduction, finite-length regime, Gain, Joints, LDPC decoding, low-density parity-check decoding, pairwise marginal constraint, parity check codes, TEP decoder, tree-like approximation, tree-structured expectation propagation, trees (mathematics)}, pubstate = {published}, tppubtype = {inproceedings} } In this paper, we propose the tree-structured expectation propagation (TEP) algorithm for low-density parity-check (LDPC) decoding over the additive white Gaussian noise (AWGN) channel. By imposing a tree-like approximation over the graphical model of the code, this algorithm introduces pairwise marginal constraints over pairs of variables, which provide joint information of the variables related. Thanks to this, the proposed TEP decoder improves the performance of the standard belief propagation (BP) solution. An efficient way of constructing the tree-like structure is also described. The simulation results illustrate the TEP decoder gain in the finite-length regime, compared to the standard BP solution. For code lengths shorter than n = 512, the gain in the waterfall region achieves up to 0.25 dB. We also notice a remarkable reduction of the error floor. |

Olmos, Pablo M; Perez-Cruz, Fernando; Salamanca, Luis; Murillo-Fuentes, Juan Jose Finite-Length Analysis of the TEP Decoder for LDPC Ensembles over the BEC Inproceedings 2012 IEEE International Symposium on Information Theory Proceedings, pp. 2346–2350, IEEE, Cambridge, MA, 2012, ISSN: 2157-8095. Abstract | Links | BibTeX | Tags: Approximation methods, BEC, binary codes, binary erasure channel, Decoding, Error analysis, error probability, finite-length analysis, LDPC ensembles, low-density parity check ensembles, parity check codes, TEP decoder, Trajectory, tree-expectation propagation algorithm, waterfall region @inproceedings{Olmos2012a, title = {Finite-Length Analysis of the TEP Decoder for LDPC Ensembles over the BEC}, author = {Pablo M Olmos and Fernando Perez-Cruz and Luis Salamanca and Juan Jose Murillo-Fuentes}, url = {http://ieeexplore.ieee.org/lpdocs/epic03/wrapper.htm?arnumber=6283932}, issn = {2157-8095}, year = {2012}, date = {2012-01-01}, booktitle = {2012 IEEE International Symposium on Information Theory Proceedings}, pages = {2346--2350}, publisher = {IEEE}, address = {Cambridge, MA}, abstract = {In this work, we analyze the finite-length performance of low-density parity check (LDPC) ensembles decoded over the binary erasure channel (BEC) using the tree-expectation propagation (TEP) algorithm. In a previous paper, we showed that the TEP improves the BP performance for decoding regular and irregular short LDPC codes, but the perspective was mainly empirical. In this work, given the degree-distribution of an LDPC ensemble, we explain and predict the range of code lengths for which the TEP improves the BP solution. In addition, for LDPC ensembles that present a single critical point, we propose a scaling law to accurately predict the performance in the waterfall region. These results are of critical importance to design practical LDPC codes for the TEP decoder.}, keywords = {Approximation methods, BEC, binary codes, binary erasure channel, Decoding, Error analysis, error probability, finite-length analysis, LDPC ensembles, low-density parity check ensembles, parity check codes, TEP decoder, Trajectory, tree-expectation propagation algorithm, waterfall region}, pubstate = {published}, tppubtype = {inproceedings} } In this work, we analyze the finite-length performance of low-density parity check (LDPC) ensembles decoded over the binary erasure channel (BEC) using the tree-expectation propagation (TEP) algorithm. In a previous paper, we showed that the TEP improves the BP performance for decoding regular and irregular short LDPC codes, but the perspective was mainly empirical. In this work, given the degree-distribution of an LDPC ensemble, we explain and predict the range of code lengths for which the TEP improves the BP solution. In addition, for LDPC ensembles that present a single critical point, we propose a scaling law to accurately predict the performance in the waterfall region. These results are of critical importance to design practical LDPC codes for the TEP decoder. |

## 2011 |

Olmos, Pablo M; Murillo-Fuentes, Juan Jose; Perez-Cruz, Fernando Capacity Achieving LDPC Ensembles for the TEP Decoder in Erasure Channels Inproceedings 2011 IEEE International Symposium on Information Theory Proceedings, pp. 2398–2402, IEEE, St. Petersburg, 2011, ISSN: 2157-8095. Abstract | Links | BibTeX | Tags: BP threshold, Complexity theory, Decoding, Differential equations, erasure channels, fixed-rate code, Iterative decoding, LDPC, low-density parity-check codes, MAP capacity, MAP threshold, optimisation, Optimization, optimization problem, parity check codes, TEP decoder, tree-expectation propagation decoder @inproceedings{Olmos2011b, title = {Capacity Achieving LDPC Ensembles for the TEP Decoder in Erasure Channels}, author = {Pablo M Olmos and Juan Jose Murillo-Fuentes and Fernando Perez-Cruz}, url = {http://ieeexplore.ieee.org/lpdocs/epic03/wrapper.htm?arnumber=6033993}, issn = {2157-8095}, year = {2011}, date = {2011-01-01}, booktitle = {2011 IEEE International Symposium on Information Theory Proceedings}, pages = {2398--2402}, publisher = {IEEE}, address = {St. Petersburg}, abstract = {In this work we address the design of degree distributions (DD) of low-density parity-check (LDPC) codes for the tree-expectation propagation (TEP) decoder. The optimization problem to find distributions to maximize the TEP decoding threshold for a fixed-rate code can not be analytically solved. We derive a simplified optimization problem that can be easily solved since it is based in the analytic expressions of the peeling decoder. Two kinds of solutions are obtained from this problem: we either design LDPC ensembles for which the BP threshold equals the MAP threshold or we get LDPC ensembles for which the TEP threshold outperforms the BP threshold, even achieving the MAP capacity in some cases. Hence, we proved that there exist ensembles for which the MAP solution can be obtained with linear complexity even though the BP threshold does not achieve the MAP threshold.}, keywords = {BP threshold, Complexity theory, Decoding, Differential equations, erasure channels, fixed-rate code, Iterative decoding, LDPC, low-density parity-check codes, MAP capacity, MAP threshold, optimisation, Optimization, optimization problem, parity check codes, TEP decoder, tree-expectation propagation decoder}, pubstate = {published}, tppubtype = {inproceedings} } In this work we address the design of degree distributions (DD) of low-density parity-check (LDPC) codes for the tree-expectation propagation (TEP) decoder. The optimization problem to find distributions to maximize the TEP decoding threshold for a fixed-rate code can not be analytically solved. We derive a simplified optimization problem that can be easily solved since it is based in the analytic expressions of the peeling decoder. Two kinds of solutions are obtained from this problem: we either design LDPC ensembles for which the BP threshold equals the MAP threshold or we get LDPC ensembles for which the TEP threshold outperforms the BP threshold, even achieving the MAP capacity in some cases. Hence, we proved that there exist ensembles for which the MAP solution can be obtained with linear complexity even though the BP threshold does not achieve the MAP threshold. |

Salamanca, Luis; Olmos, Pablo M; Murillo-Fuentes, Juan Jose; Perez-Cruz, Fernando MAP Decoding for LDPC Codes over the Binary Erasure Channel Inproceedings 2011 IEEE Information Theory Workshop, pp. 145–149, IEEE, Paraty, 2011, ISBN: 978-1-4577-0437-6. Abstract | Links | BibTeX | Tags: binary erasure channel, Channel Coding, computational complexity, Decoding, generalized peeling decoder, generalized tree-structured expectation propagatio, graphical models, Iterative decoding, LDPC codes, MAP decoding, MAP decoding algorithm, Maximum likelihood decoding, parity check codes, TEP decoder, tree graph theory, Tree graphs, tree-structured expectation propagation, trees (mathematics) @inproceedings{Salamanca2011a, title = {MAP Decoding for LDPC Codes over the Binary Erasure Channel}, author = {Luis Salamanca and Pablo M Olmos and Juan Jose Murillo-Fuentes and Fernando Perez-Cruz}, url = {http://ieeexplore.ieee.org/lpdocs/epic03/wrapper.htm?arnumber=6089364}, isbn = {978-1-4577-0437-6}, year = {2011}, date = {2011-01-01}, booktitle = {2011 IEEE Information Theory Workshop}, pages = {145--149}, publisher = {IEEE}, address = {Paraty}, abstract = {In this paper, we propose a decoding algorithm for LDPC codes that achieves the MAP solution over the BEC. This algorithm, denoted as generalized tree-structured expectation propagation (GTEP), extends the idea of our previous work, the TEP decoder. The GTEP modifies the graph by eliminating a check node of any degree and merging this information with the remaining graph. The GTEP decoder upon completion either provides the unique MAP solution or a tree graph in which the number of parent nodes indicates the multiplicity of the MAP solution. This algorithm can be easily described for the BEC, and it can be cast as a generalized peeling decoder. The GTEP naturally optimizes the complexity of the decoder, by looking for checks nodes of minimum degree to be eliminated first.}, keywords = {binary erasure channel, Channel Coding, computational complexity, Decoding, generalized peeling decoder, generalized tree-structured expectation propagatio, graphical models, Iterative decoding, LDPC codes, MAP decoding, MAP decoding algorithm, Maximum likelihood decoding, parity check codes, TEP decoder, tree graph theory, Tree graphs, tree-structured expectation propagation, trees (mathematics)}, pubstate = {published}, tppubtype = {inproceedings} } In this paper, we propose a decoding algorithm for LDPC codes that achieves the MAP solution over the BEC. This algorithm, denoted as generalized tree-structured expectation propagation (GTEP), extends the idea of our previous work, the TEP decoder. The GTEP modifies the graph by eliminating a check node of any degree and merging this information with the remaining graph. The GTEP decoder upon completion either provides the unique MAP solution or a tree graph in which the number of parent nodes indicates the multiplicity of the MAP solution. This algorithm can be easily described for the BEC, and it can be cast as a generalized peeling decoder. The GTEP naturally optimizes the complexity of the decoder, by looking for checks nodes of minimum degree to be eliminated first. |

Olmos, Pablo M; Murillo-Fuentes, Juan Jose; Perez-Cruz, Fernando Tree-Structured Expectation Propagation for Decoding Finite-Length LDPC Codes Journal Article IEEE Communications Letters, 15 (2), pp. 235–237, 2011, ISSN: 1089-7798. Abstract | Links | BibTeX | Tags: belief propagation decoder, BP algorithm, BP decoder, code graph, communication complexity, computational complexity, Decoding, finite-length analysis, finite-length low-density parity-check code, LDPC code, LDPC decoding, parity check codes, radiowave propagation, stopping set, TEP algorithm, TEP decoder, tree-structured expectation propagation @article{Olmos2011c, title = {Tree-Structured Expectation Propagation for Decoding Finite-Length LDPC Codes}, author = {Pablo M Olmos and Juan Jose Murillo-Fuentes and Fernando Perez-Cruz}, url = {http://ieeexplore.ieee.org/lpdocs/epic03/wrapper.htm?arnumber=5682215}, issn = {1089-7798}, year = {2011}, date = {2011-01-01}, journal = {IEEE Communications Letters}, volume = {15}, number = {2}, pages = {235--237}, abstract = {In this paper, we propose Tree-structured Expectation Propagation (TEP) algorithm to decode finite-length Low-Density Parity-Check (LDPC) codes. The TEP decoder is able to continue decoding once the standard Belief Propagation (BP) decoder fails, presenting the same computational complexity as the BP decoder. The BP algorithm is dominated by the presence of stopping sets (SSs) in the code graph. We show that the TEP decoder, without previous knowledge of the graph, naturally avoids some fairly common SSs. This results in a significant improvement in the system performance.}, keywords = {belief propagation decoder, BP algorithm, BP decoder, code graph, communication complexity, computational complexity, Decoding, finite-length analysis, finite-length low-density parity-check code, LDPC code, LDPC decoding, parity check codes, radiowave propagation, stopping set, TEP algorithm, TEP decoder, tree-structured expectation propagation}, pubstate = {published}, tppubtype = {article} } In this paper, we propose Tree-structured Expectation Propagation (TEP) algorithm to decode finite-length Low-Density Parity-Check (LDPC) codes. The TEP decoder is able to continue decoding once the standard Belief Propagation (BP) decoder fails, presenting the same computational complexity as the BP decoder. The BP algorithm is dominated by the presence of stopping sets (SSs) in the code graph. We show that the TEP decoder, without previous knowledge of the graph, naturally avoids some fairly common SSs. This results in a significant improvement in the system performance. |