## 2013 |

## Journal Articles |

Salamanca, Luis ; Olmos, Pablo M; Perez-Cruz, Fernando ; Murillo-Fuentes, Juan Jose Tree-Structured Expectation Propagation for LDPC Decoding over BMS Channels Journal Article IEEE Transactions on Communications, 61 (10), pp. 4086–4095, 2013, ISSN: 0090-6778. Abstract | Links | BibTeX | Tags: Approximation algorithms, Approximation methods, BEC, belief propagation, binary erasure channel, binary memoryless symmetric channels, BMS channels, Channel Coding, Complexity theory, convolutional codes, convolutional low-density parity-check codes, Decoding, decoding block, expectation propagation, finite-length codes, LDPC decoding, message-passing algorithm, parity check codes, Probability density function, sparse linear codes, TEP algorithm, tree-structured expectation propagation, trees (mathematics), Vegetation @article{Salamanca2013a, title = {Tree-Structured Expectation Propagation for LDPC Decoding over BMS Channels}, author = {Salamanca, Luis and Olmos, Pablo M. and Perez-Cruz, Fernando and Murillo-Fuentes, Juan Jose}, url = {http://ieeexplore.ieee.org/lpdocs/epic03/wrapper.htm?arnumber=6587624}, issn = {0090-6778}, year = {2013}, date = {2013-01-01}, journal = {IEEE Transactions on Communications}, volume = {61}, number = {10}, pages = {4086--4095}, abstract = {In this paper, we put forward the tree-structured expectation propagation (TEP) algorithm for decoding block and convolutional low-density parity-check codes over any binary channel. We have already shown that TEP improves belief propagation (BP) over the binary erasure channel (BEC) by imposing marginal constraints over a set of pairs of variables that form a tree or a forest. The TEP decoder is a message-passing algorithm that sequentially builds a tree/forest of erased variables to capture additional information disregarded by the standard BP decoder, which leads to a noticeable reduction of the error rate for finite-length codes. In this paper, we show how the TEP can be extended to any channel, specifically to binary memoryless symmetric (BMS) channels. We particularly focus on how the TEP algorithm can be adapted for any channel model and, more importantly, how to choose the tree/forest to keep the gains observed for block and convolutional LDPC codes over the BEC.}, keywords = {Approximation algorithms, Approximation methods, BEC, belief propagation, binary erasure channel, binary memoryless symmetric channels, BMS channels, Channel Coding, Complexity theory, convolutional codes, convolutional low-density parity-check codes, Decoding, decoding block, expectation propagation, finite-length codes, LDPC decoding, message-passing algorithm, parity check codes, Probability density function, sparse linear codes, TEP algorithm, tree-structured expectation propagation, trees (mathematics), Vegetation}, pubstate = {published}, tppubtype = {article} } In this paper, we put forward the tree-structured expectation propagation (TEP) algorithm for decoding block and convolutional low-density parity-check codes over any binary channel. We have already shown that TEP improves belief propagation (BP) over the binary erasure channel (BEC) by imposing marginal constraints over a set of pairs of variables that form a tree or a forest. The TEP decoder is a message-passing algorithm that sequentially builds a tree/forest of erased variables to capture additional information disregarded by the standard BP decoder, which leads to a noticeable reduction of the error rate for finite-length codes. In this paper, we show how the TEP can be extended to any channel, specifically to binary memoryless symmetric (BMS) channels. We particularly focus on how the TEP algorithm can be adapted for any channel model and, more importantly, how to choose the tree/forest to keep the gains observed for block and convolutional LDPC codes over the BEC. |

Salamanca, Luis ; Olmos, Pablo M; Murillo-Fuentes, Juan Jose ; Perez-Cruz, Fernando Tree Expectation Propagation for ML Decoding of LDPC Codes over the BEC Journal Article IEEE Transactions on Communications, 61 (2), pp. 465–473, 2013, ISSN: 0090-6778. Abstract | Links | BibTeX | Tags: approximate inference, Approximation algorithms, Approximation methods, BEC, binary codes, binary erasure channel, code graph, Complexity theory, equivalent complexity, Gaussian elimination method, Gaussian processes, generalized tree-structured expectation propagatio, graphical message-passing procedure, graphical models, LDPC codes, Maximum likelihood decoding, maximum likelihood solution, ML decoding, parity check codes, peeling decoder, tree expectation propagation, tree graph, Tree graphs, tree-structured expectation propagation, tree-structured expectation propagation decoder, trees (mathematics) @article{Salamanca2013b, title = {Tree Expectation Propagation for ML Decoding of LDPC Codes over the BEC}, author = {Salamanca, Luis and Olmos, Pablo M. and Murillo-Fuentes, Juan Jose and Perez-Cruz, Fernando}, url = {http://ieeexplore.ieee.org/lpdocs/epic03/wrapper.htm?arnumber=6384612}, issn = {0090-6778}, year = {2013}, date = {2013-01-01}, journal = {IEEE Transactions on Communications}, volume = {61}, number = {2}, pages = {465--473}, abstract = {We propose a decoding algorithm for LDPC codes that achieves the maximum likelihood (ML) solution over the binary erasure channel (BEC). In this channel, the tree-structured expectation propagation (TEP) decoder improves the peeling decoder (PD) by processing check nodes of degree one and two. However, it does not achieve the ML solution, as the tree structure of the TEP allows only for approximate inference. In this paper, we provide the procedure to construct the structure needed for exact inference. This algorithm, denoted as generalized tree-structured expectation propagation (GTEP), modifies the code graph by recursively eliminating any check node and merging this information in the remaining graph. The GTEP decoder upon completion either provides the unique ML solution or a tree graph in which the number of parent nodes indicates the multiplicity of the ML solution. We also explain the algorithm as a Gaussian elimination method, relating the GTEP to other ML solutions. Compared to previous approaches, it presents an equivalent complexity, it exhibits a simpler graphical message-passing procedure and, most interesting, the algorithm can be generalized to other channels.}, keywords = {approximate inference, Approximation algorithms, Approximation methods, BEC, binary codes, binary erasure channel, code graph, Complexity theory, equivalent complexity, Gaussian elimination method, Gaussian processes, generalized tree-structured expectation propagatio, graphical message-passing procedure, graphical models, LDPC codes, Maximum likelihood decoding, maximum likelihood solution, ML decoding, parity check codes, peeling decoder, tree expectation propagation, tree graph, Tree graphs, tree-structured expectation propagation, tree-structured expectation propagation decoder, trees (mathematics)}, pubstate = {published}, tppubtype = {article} } We propose a decoding algorithm for LDPC codes that achieves the maximum likelihood (ML) solution over the binary erasure channel (BEC). In this channel, the tree-structured expectation propagation (TEP) decoder improves the peeling decoder (PD) by processing check nodes of degree one and two. However, it does not achieve the ML solution, as the tree structure of the TEP allows only for approximate inference. In this paper, we provide the procedure to construct the structure needed for exact inference. This algorithm, denoted as generalized tree-structured expectation propagation (GTEP), modifies the code graph by recursively eliminating any check node and merging this information in the remaining graph. The GTEP decoder upon completion either provides the unique ML solution or a tree graph in which the number of parent nodes indicates the multiplicity of the ML solution. We also explain the algorithm as a Gaussian elimination method, relating the GTEP to other ML solutions. Compared to previous approaches, it presents an equivalent complexity, it exhibits a simpler graphical message-passing procedure and, most interesting, the algorithm can be generalized to other channels. |

## 2012 |

## Journal Articles |

Olmos, Pablo M; Salamanca, Luis ; Murillo-Fuentes, Juan Jose ; Perez-Cruz, Fernando On the Design of LDPC-Convolutional Ensembles Using the TEP Decoder Journal Article IEEE Communications Letters, 16 (5), pp. 726–729, 2012, ISSN: 1089-7798. Abstract | Links | BibTeX | Tags: belief propagation decoding, binary erasure channel, channel capacity, Complexity theory, convolutional codes, convolutional LDPC codes, Decoding, design, Error analysis, finite-length analysis, Iterative decoding, LDPC-convolutional ensemble design, LDPCC code decoding, low-density parity-check convolutional code, parity check codes, tree-expectation propagation decoder, tree-structured expectation propagation, window-sliding scheme @article{Olmos2012b, title = {On the Design of LDPC-Convolutional Ensembles Using the TEP Decoder}, author = {Olmos, Pablo M. and Salamanca, Luis and Murillo-Fuentes, Juan Jose and Perez-Cruz, Fernando}, url = {http://ieeexplore.ieee.org/lpdocs/epic03/wrapper.htm?arnumber=6168872}, issn = {1089-7798}, year = {2012}, date = {2012-01-01}, journal = {IEEE Communications Letters}, volume = {16}, number = {5}, pages = {726--729}, abstract = {Low-density parity-check convolutional (LDPCC) codes asymptotically achieve channel capacity under belief propagation (BP) decoding. In this paper, we decode LDPCC codes using the Tree-Expectation Propagation (TEP) decoder, recently proposed as an alternative decoding method to the BP algorithm for the binary erasure channel (BEC). We show that, for LDPCC codes, the TEP decoder improves the BP solution with a comparable complexity or, alternatively, it allows using shorter codes to achieve similar error rates. We also propose a window-sliding scheme for the TEP decoder to reduce the decoding latency.}, keywords = {belief propagation decoding, binary erasure channel, channel capacity, Complexity theory, convolutional codes, convolutional LDPC codes, Decoding, design, Error analysis, finite-length analysis, Iterative decoding, LDPC-convolutional ensemble design, LDPCC code decoding, low-density parity-check convolutional code, parity check codes, tree-expectation propagation decoder, tree-structured expectation propagation, window-sliding scheme}, pubstate = {published}, tppubtype = {article} } Low-density parity-check convolutional (LDPCC) codes asymptotically achieve channel capacity under belief propagation (BP) decoding. In this paper, we decode LDPCC codes using the Tree-Expectation Propagation (TEP) decoder, recently proposed as an alternative decoding method to the BP algorithm for the binary erasure channel (BEC). We show that, for LDPCC codes, the TEP decoder improves the BP solution with a comparable complexity or, alternatively, it allows using shorter codes to achieve similar error rates. We also propose a window-sliding scheme for the TEP decoder to reduce the decoding latency. |

## Inproceedings |

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 = {Salamanca, Luis and Murillo-Fuentes, Juan Jose and Olmos, Pablo M. and Perez-Cruz, Fernando}, 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 Performance of Spatially-Coupled LDPC Codes under TEP Decoding Inproceedings 2012 IEEE Information Theory Workshop, pp. 1–6, IEEE, Lausanne, 2012, ISBN: 978-1-4673-0223-4. Links | BibTeX | Tags: asymptotic limit, belief propagation decoding, Complexity theory, convolutional codes, convolutional LDPC codes, Decoding, decoding latency, decoding threshold, erasure channel, Error analysis, error rates, finite-length analysis, finite-length performance, maximum a posteriori threshold, maximum likelihood estimation, parity check codes, regular sparse codes, spatially-coupled LDPC codes, TEP decoding, tree-structured expectation propagation, underlying regular code, very large code length, window-sliding scheme @inproceedings{Olmos2012, title = {Finite-Length Performance of Spatially-Coupled LDPC Codes under TEP Decoding}, author = {Olmos, Pablo M. and Perez-Cruz, Fernando and Salamanca, Luis and Murillo-Fuentes, Juan Jose}, url = {http://ieeexplore.ieee.org/articleDetails.jsp?arnumber=6404722}, isbn = {978-1-4673-0223-4}, year = {2012}, date = {2012-01-01}, booktitle = {2012 IEEE Information Theory Workshop}, pages = {1--6}, publisher = {IEEE}, address = {Lausanne}, keywords = {asymptotic limit, belief propagation decoding, Complexity theory, convolutional codes, convolutional LDPC codes, Decoding, decoding latency, decoding threshold, erasure channel, Error analysis, error rates, finite-length analysis, finite-length performance, maximum a posteriori threshold, maximum likelihood estimation, parity check codes, regular sparse codes, spatially-coupled LDPC codes, TEP decoding, tree-structured expectation propagation, underlying regular code, very large code length, window-sliding scheme}, pubstate = {published}, tppubtype = {inproceedings} } |

## 2011 |

## Journal Articles |

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 = {Olmos, Pablo M. and Murillo-Fuentes, Juan Jose and Perez-Cruz, Fernando}, 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. |

## Inproceedings |

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 = {Salamanca, Luis and Olmos, Pablo M. and Murillo-Fuentes, Juan Jose and Perez-Cruz, Fernando}, 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. |