## 2015 |

## Inproceedings |

Olmos, Pablo; Mitchell, David; Costello, Daniel Analyzing the Finite-Length Performance of Generalized LDPC Codes (Inproceeding) 2015 IEEE International Symposium on Information Theory (ISIT), pp. 2683–2687, IEEE, Hong Kong, 2015, ISBN: 978-1-4673-7704-1. (Abstract | Links | BibTeX | Tags: BEC, binary codes, binary erasure channel, Block codes, Codes on graphs, Decoding, Differential equations, error probability, finite-length generalized LDPC block codes, finite-length performance analysis, generalized LDPC codes, generalized peeling decoder, GLDPC block codes, graph degree distribution, graph theory, Iterative decoding, parity check codes, protographs) @inproceedings{Olmos2015b, title = {Analyzing the Finite-Length Performance of Generalized LDPC Codes}, author = {Olmos, Pablo M. and Mitchell, David G. M. and Costello, Daniel J.}, url = {http://ieeexplore.ieee.org/lpdocs/epic03/wrapper.htm?arnumber=7282943}, doi = {10.1109/ISIT.2015.7282943}, isbn = {978-1-4673-7704-1}, year = {2015}, date = {2015-06-01}, booktitle = {2015 IEEE International Symposium on Information Theory (ISIT)}, pages = {2683--2687}, publisher = {IEEE}, address = {Hong Kong}, abstract = {In this paper, we analyze the performance of finite-length generalized LDPC (GLDPC) block codes constructed from protographs when transmission takes place over the binary erasure channel (BEC). A generalized peeling decoder is proposed and we derive a system of differential equations that gives the expected evolution of the graph degree distribution during decoding. We then show that the finite-length performance of a GLDPC code can be estimated by means of a simple scaling law, where a single scaling parameter represents the finite-length properties of the code. We also show that, as we consider stronger component codes, both the asymptotic threshold and the finite-length scaling parameter are improved.}, keywords = {BEC, binary codes, binary erasure channel, Block codes, Codes on graphs, Decoding, Differential equations, error probability, finite-length generalized LDPC block codes, finite-length performance analysis, generalized LDPC codes, generalized peeling decoder, GLDPC block codes, graph degree distribution, graph theory, Iterative decoding, parity check codes, protographs}, pubstate = {published}, tppubtype = {inproceedings} } In this paper, we analyze the performance of finite-length generalized LDPC (GLDPC) block codes constructed from protographs when transmission takes place over the binary erasure channel (BEC). A generalized peeling decoder is proposed and we derive a system of differential equations that gives the expected evolution of the graph degree distribution during decoding. We then show that the finite-length performance of a GLDPC code can be estimated by means of a simple scaling law, where a single scaling parameter represents the finite-length properties of the code. We also show that, as we consider stronger component codes, both the asymptotic threshold and the finite-length scaling parameter are improved. |

## 2013 |

## Journal Articles |

Salamanca, Luis; Olmos, Pablo; 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 |

## Inproceedings |

Olmos, Pablo; Perez-Cruz, Fernando; Salamanca, Luis; Murillo-Fuentes, Juan Jose Finite-Length Analysis of the TEP Decoder for LDPC Ensembles over the BEC (Inproceeding) 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 = {Olmos, Pablo M. and Perez-Cruz, Fernando and Salamanca, Luis and Murillo-Fuentes, Juan Jose}, 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 |

## Inproceedings |

Olmos, Pablo; Urbanke, Rudiger Scaling Behavior of Convolutional LDPC Ensembles over the BEC (Inproceeding) 2011 IEEE International Symposium on Information Theory Proceedings, pp. 1816–1820, IEEE, Saint Petersburg, 2011, ISSN: 2157-8095. (Abstract | Links | BibTeX | Tags: BEC, binary codes, binary erasure channel, Bit error rate, convolutional codes, convolutional LDPC ensembles, coupled sparse graph codes, Couplings, Decoding, error probability, Iterative decoding, parity check codes, scaling behavior) @inproceedings{Olmos2011, title = {Scaling Behavior of Convolutional LDPC Ensembles over the BEC}, author = {Olmos, Pablo M. and Urbanke, Rudiger}, url = {http://ieeexplore.ieee.org/lpdocs/epic03/wrapper.htm?arnumber=6033863}, issn = {2157-8095}, year = {2011}, date = {2011-01-01}, booktitle = {2011 IEEE International Symposium on Information Theory Proceedings}, pages = {1816--1820}, publisher = {IEEE}, address = {Saint Petersburg}, abstract = {We study the scaling behavior of coupled sparse graph codes over the binary erasure channel. In particular, let 2L+1 be the length of the coupled chain, let M be the number of variables in each of the 2L+1 local copies, let ℓ be the number of iterations, let Pb denote the bit error probability, and let ∈ denote the channel parameter. We are interested in how these quantities scale when we let the blocklength (2L + 1)M tend to infinity. Based on empirical evidence we show that the threshold saturation phenomenon is rather stable with respect to the scaling of the various parameters and we formulate some general rules of thumb which can serve as a guide for the design of coding systems based on coupled graphs.}, keywords = {BEC, binary codes, binary erasure channel, Bit error rate, convolutional codes, convolutional LDPC ensembles, coupled sparse graph codes, Couplings, Decoding, error probability, Iterative decoding, parity check codes, scaling behavior}, pubstate = {published}, tppubtype = {inproceedings} } We study the scaling behavior of coupled sparse graph codes over the binary erasure channel. In particular, let 2L+1 be the length of the coupled chain, let M be the number of variables in each of the 2L+1 local copies, let ℓ be the number of iterations, let Pb denote the bit error probability, and let ∈ denote the channel parameter. We are interested in how these quantities scale when we let the blocklength (2L + 1)M tend to infinity. Based on empirical evidence we show that the threshold saturation phenomenon is rather stable with respect to the scaling of the various parameters and we formulate some general rules of thumb which can serve as a guide for the design of coding systems based on coupled graphs. |