## 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. |

Stinner, Markus; Olmos, Pablo Finite-Length Performance of Multi-Edge Protograph-Based Spatially Coupled LDPC Codes (Inproceeding) 2015 IEEE International Symposium on Information Theory (ISIT), pp. 889–893, IEEE, Hong Kong, 2015, ISBN: 978-1-4673-7704-1. (Abstract | Links | BibTeX | Tags: binary erasure channel, Block codes, Couplings, Decoding, Error analysis, finite length performance, finite-length performance, graph theory, Iterative decoding, low density parity check codes, multiedge protograph, parity check codes, spatially coupled LDPC codes, spatially-coupled LDPC codes, Steady-state) @inproceedings{Stinner2015, title = {Finite-Length Performance of Multi-Edge Protograph-Based Spatially Coupled LDPC Codes}, author = {Stinner, Markus and Olmos, Pablo M.}, url = {http://ieeexplore.ieee.org/lpdocs/epic03/wrapper.htm?arnumber=7282583}, doi = {10.1109/ISIT.2015.7282583}, isbn = {978-1-4673-7704-1}, year = {2015}, date = {2015-06-01}, booktitle = {2015 IEEE International Symposium on Information Theory (ISIT)}, pages = {889--893}, publisher = {IEEE}, address = {Hong Kong}, abstract = {The finite-length performance of multi-edge spatially coupled low-density parity-check (SC-LDPC) codes over the binary erasure channel (BEC) is analyzed. Existing scaling laws are extended to arbitrary protograph base matrices that include puncturing patterns and multiple edges between nodes. A regular protograph-based SC-LDPC construction based on the (4; 8)-regular LDPC block code works well in the waterfall region compared to more involved rate-1/2 structures proposed to improve the threshold to minimum distance trade-off. Scaling laws are also used for code design and to estimate the block length of a given SC-LDPC code ensemble to match the performance of some other code. Estimates on the performance degradation are developed if the chain length varies.}, keywords = {binary erasure channel, Block codes, Couplings, Decoding, Error analysis, finite length performance, finite-length performance, graph theory, Iterative decoding, low density parity check codes, multiedge protograph, parity check codes, spatially coupled LDPC codes, spatially-coupled LDPC codes, Steady-state}, pubstate = {published}, tppubtype = {inproceedings} } The finite-length performance of multi-edge spatially coupled low-density parity-check (SC-LDPC) codes over the binary erasure channel (BEC) is analyzed. Existing scaling laws are extended to arbitrary protograph base matrices that include puncturing patterns and multiple edges between nodes. A regular protograph-based SC-LDPC construction based on the (4; 8)-regular LDPC block code works well in the waterfall region compared to more involved rate-1/2 structures proposed to improve the threshold to minimum distance trade-off. Scaling laws are also used for code design and to estimate the block length of a given SC-LDPC code ensemble to match the performance of some other code. Estimates on the performance degradation are developed if the chain length varies. |

## 2011 |

## Inproceedings |

Maiz, Cristina; Miguez, Joaquin On the Optimization of Transportation Routes with Multiple Destinations in Random Networks (Inproceeding) 2011 IEEE Statistical Signal Processing Workshop (SSP), pp. 349–352, IEEE, Nice, 2011, ISBN: 978-1-4577-0569-4. (Abstract | Links | BibTeX | Tags: Approximation algorithms, communication networks, Estimation, graph theory, Histograms, intelligent transportation, Monte Carlo algorithm, Monte Carlo methods, multiple destinations, optimisation, Optimization, random networks, route optimization, routing, Sequential Monte Carlo, Signal processing algorithms, stochastic graph, Stochastic processes, telecommunication network routing, time-varying graph, transportation routes) @inproceedings{Maiz2011, title = {On the Optimization of Transportation Routes with Multiple Destinations in Random Networks}, author = {Maiz, Cristina S. and Miguez, Joaquin}, url = {http://ieeexplore.ieee.org/lpdocs/epic03/wrapper.htm?arnumber=5967701}, isbn = {978-1-4577-0569-4}, year = {2011}, date = {2011-01-01}, booktitle = {2011 IEEE Statistical Signal Processing Workshop (SSP)}, pages = {349--352}, publisher = {IEEE}, address = {Nice}, abstract = {Various practical problems in transportation research and routing in communication networks can be reduced to the computation of the best path that traverses a certain graph and visits a set of D specified destination nodes. Simple versions of this problem have received attention in the literature. Optimal solutions exist for the cases in which (a) D >; 1 and the graph is deterministic or (b) D = 1 and the graph is stochastic (and possibly time-dependent). Here, we address the general problem in which both D >; 1 and the costs of the edges in the graph are stochastic and time-varying. We tackle this complex global optimization problem by first converting it into an equivalent estimation problem and then computing a numerical solution using a sequential Monte Carlo algorithm. The advantage of the proposed technique over some standard methods (devised for graphs with time-invariant statistics) is illustrated by way of computer simulations.}, keywords = {Approximation algorithms, communication networks, Estimation, graph theory, Histograms, intelligent transportation, Monte Carlo algorithm, Monte Carlo methods, multiple destinations, optimisation, Optimization, random networks, route optimization, routing, Sequential Monte Carlo, Signal processing algorithms, stochastic graph, Stochastic processes, telecommunication network routing, time-varying graph, transportation routes}, pubstate = {published}, tppubtype = {inproceedings} } Various practical problems in transportation research and routing in communication networks can be reduced to the computation of the best path that traverses a certain graph and visits a set of D specified destination nodes. Simple versions of this problem have received attention in the literature. Optimal solutions exist for the cases in which (a) D >; 1 and the graph is deterministic or (b) D = 1 and the graph is stochastic (and possibly time-dependent). Here, we address the general problem in which both D >; 1 and the costs of the edges in the graph are stochastic and time-varying. We tackle this complex global optimization problem by first converting it into an equivalent estimation problem and then computing a numerical solution using a sequential Monte Carlo algorithm. The advantage of the proposed technique over some standard methods (devised for graphs with time-invariant statistics) is illustrated by way of computer simulations. |

## 2010 |

## Inproceedings |

Olmos, Pablo; Murillo-Fuentes, Juan Jose; Perez-Cruz, Fernando Tree-Structure Expectation Propagation for Decoding LDPC Codes over Binary Erasure Channels (Inproceeding) 2010 IEEE International Symposium on Information Theory, pp. 799–803, IEEE, Austin, TX, 2010, ISBN: 978-1-4244-7892-7. (Abstract | Links | BibTeX | Tags: belief propagation, binary erasure channels, Bipartite graph, BP decoder, Capacity planning, Channel Coding, codeword, computational complexity, Decoding, Finishing, graph theory, H infinity control, LDPC code decoding, LDPC Tanner graph, Maxwell decoder, parity check codes, Performance analysis, tree structure expectation propagation, trees (mathematics), Upper bound) @inproceedings{Olmos2010, title = {Tree-Structure Expectation Propagation for Decoding LDPC Codes over Binary Erasure Channels}, author = {Olmos, Pablo M. and Murillo-Fuentes, Juan Jose and Perez-Cruz, Fernando}, url = {http://ieeexplore.ieee.org/lpdocs/epic03/wrapper.htm?arnumber=5513636}, isbn = {978-1-4244-7892-7}, year = {2010}, date = {2010-01-01}, booktitle = {2010 IEEE International Symposium on Information Theory}, pages = {799--803}, publisher = {IEEE}, address = {Austin, TX}, abstract = {Expectation Propagation is a generalization to 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 distribution constraints in some check nodes of the LDPC Tanner graph. These additional constraints allow decoding the received codeword when the BP decoder gets stuck. In this paper, we first present the new decoding algorithm, whose complexity is identical to the BP decoder, and we then prove that it is able to decode codewords with a larger fraction of erasures, as the block size tends to infinity. The proposed algorithm can be also understood as a simplification of the Maxwell decoder, but without its computational complexity. We also illustrate that the new algorithm outperforms the BP decoder for finite block-size codes.}, keywords = {belief propagation, binary erasure channels, Bipartite graph, BP decoder, Capacity planning, Channel Coding, codeword, computational complexity, Decoding, Finishing, graph theory, H infinity control, LDPC code decoding, LDPC Tanner graph, Maxwell decoder, parity check codes, Performance analysis, tree structure expectation propagation, trees (mathematics), Upper bound}, pubstate = {published}, tppubtype = {inproceedings} } Expectation Propagation is a generalization to 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 distribution constraints in some check nodes of the LDPC Tanner graph. These additional constraints allow decoding the received codeword when the BP decoder gets stuck. In this paper, we first present the new decoding algorithm, whose complexity is identical to the BP decoder, and we then prove that it is able to decode codewords with a larger fraction of erasures, as the block size tends to infinity. The proposed algorithm can be also understood as a simplification of the Maxwell decoder, but without its computational complexity. We also illustrate that the new algorithm outperforms the BP decoder for finite block-size codes. |