## 2016 |

## Journal Articles |

Stinner, Markus; Olmos, Pablo On the Waterfall Performance of Finite-Length SC-LDPC Codes Constructed From Protographs (Journal Article) IEEE Journal on Selected Areas in Communications, 34 (2), pp. 345–361, 2016, ISSN: 0733-8716. (Abstract | Links | BibTeX | Tags: Analytical models, capacity-achieving codes, Complexity theory, Couplings, Decoding, Encoding, finite-length analysis, Iterative decoding, Low-density parity-check (LDPC) codes, spatially coupled LDPC codes constructed from prot) @article{Stinner2016, title = {On the Waterfall Performance of Finite-Length SC-LDPC Codes Constructed From Protographs}, author = {Stinner, Markus and Olmos, Pablo M.}, url = {http://ieeexplore.ieee.org/lpdocs/epic03/wrapper.htm?arnumber=7339427}, doi = {10.1109/JSAC.2015.2504279}, issn = {0733-8716}, year = {2016}, date = {2016-02-01}, journal = {IEEE Journal on Selected Areas in Communications}, volume = {34}, number = {2}, pages = {345--361}, abstract = {An analysis of spatially coupled low-density parity-check (SC-LDPC) codes constructed from protographs is proposed. Given the protograph used to generate the SC-LDPC code ensemble, a set of scaling parameters to characterize the average finite-length performance in the waterfall region is computed. The error performance of structured SC-LDPC code ensembles is shown to follow a scaling law similar to that of unstructured randomly constructed SC-LDPC codes. Under a finite-length perspective, some of the most relevant SC-LDPC protograph structures proposed to date are compared. The analysis reveals significant differences in their finite-length scaling behavior, which is corroborated by simulation. Spatially coupled repeat-accumulate codes present excellent finite-length performance, as they outperform in the waterfall region SC-LDPC codes of the same rate and better asymptotic thresholds.}, keywords = {Analytical models, capacity-achieving codes, Complexity theory, Couplings, Decoding, Encoding, finite-length analysis, Iterative decoding, Low-density parity-check (LDPC) codes, spatially coupled LDPC codes constructed from prot}, pubstate = {published}, tppubtype = {article} } An analysis of spatially coupled low-density parity-check (SC-LDPC) codes constructed from protographs is proposed. Given the protograph used to generate the SC-LDPC code ensemble, a set of scaling parameters to characterize the average finite-length performance in the waterfall region is computed. The error performance of structured SC-LDPC code ensembles is shown to follow a scaling law similar to that of unstructured randomly constructed SC-LDPC codes. Under a finite-length perspective, some of the most relevant SC-LDPC protograph structures proposed to date are compared. The analysis reveals significant differences in their finite-length scaling behavior, which is corroborated by simulation. Spatially coupled repeat-accumulate codes present excellent finite-length performance, as they outperform in the waterfall region SC-LDPC codes of the same rate and better asymptotic thresholds. |

## 2015 |

## Journal Articles |

Olmos, Pablo; Urbanke, Rudiger A Scaling Law to Predict the Finite-Length Performance of Spatially-Coupled LDPC Codes (Journal Article) IEEE Transactions on Information Theory, 61 (6), pp. 3164–3184, 2015, ISSN: 0018-9448. (Abstract | Links | BibTeX | Tags: asymptotic analysis, asymptotic properties, binary erasure channel, Channel Coding, Codes on graphs, Couplings, Decoding, Differential equations, error probability, finite length performance, finite length spatially coupled code, finite-length code performance, finite-length performance, Iterative decoding, iterative decoding thresholds, parity check codes, Probability, SC-LDPC codes, scaling law, Sockets, spatially coupled LDPC codes, spatially-coupled LDPC codes) @article{Olmos2015, title = {A Scaling Law to Predict the Finite-Length Performance of Spatially-Coupled LDPC Codes}, author = {Olmos, Pablo M. and Urbanke, Rudiger L.}, url = {http://ieeexplore.ieee.org/lpdocs/epic03/wrapper.htm?arnumber=7086074}, doi = {10.1109/TIT.2015.2422816}, issn = {0018-9448}, year = {2015}, date = {2015-06-01}, journal = {IEEE Transactions on Information Theory}, volume = {61}, number = {6}, pages = {3164--3184}, abstract = {Spatially-coupled low-density parity-check (SC-LDPC) codes are known to have excellent asymptotic properties. Much less is known regarding their finite-length performance. We propose a scaling law to predict the error probability of finite-length spatially coupled code ensembles when transmission takes place over the binary erasure channel. We discuss how the parameters of the scaling law are connected to fundamental quantities appearing in the asymptotic analysis of these ensembles and we verify that the predictions of the scaling law fit well to the data derived from simulations over a wide range of parameters. The ultimate goal of this line of research is to develop analytic tools for the design of SC-LDPC codes under practical constraints.}, keywords = {asymptotic analysis, asymptotic properties, binary erasure channel, Channel Coding, Codes on graphs, Couplings, Decoding, Differential equations, error probability, finite length performance, finite length spatially coupled code, finite-length code performance, finite-length performance, Iterative decoding, iterative decoding thresholds, parity check codes, Probability, SC-LDPC codes, scaling law, Sockets, spatially coupled LDPC codes, spatially-coupled LDPC codes}, pubstate = {published}, tppubtype = {article} } Spatially-coupled low-density parity-check (SC-LDPC) codes are known to have excellent asymptotic properties. Much less is known regarding their finite-length performance. We propose a scaling law to predict the error probability of finite-length spatially coupled code ensembles when transmission takes place over the binary erasure channel. We discuss how the parameters of the scaling law are connected to fundamental quantities appearing in the asymptotic analysis of these ensembles and we verify that the predictions of the scaling law fit well to the data derived from simulations over a wide range of parameters. The ultimate goal of this line of research is to develop analytic tools for the design of SC-LDPC codes under practical constraints. |

Olmos, Pablo; Urbanke, Rudiger A Scaling Law to Predict the Finite-Length Performance of Spatially-Coupled LDPC Codes (Journal Article) IEEE Transactions on Information Theory, 61 (6), pp. 3164–3184, 2015, ISSN: 0018-9448. (Abstract | Links | BibTeX | Tags: asymptotic analysis, asymptotic properties, binary erasure channel, Channel Coding, Codes on graphs, Couplings, Decoding, Differential equations, error probability, finite length performance, finite length spatially coupled code, finite-length code performance, finite-length performance, Iterative decoding, iterative decoding thresholds, Journal, parity check codes, Probability, SC-LDPC codes, scaling law, Sockets, spatially coupled LDPC codes, spatially-coupled LDPC codes) @article{Olmos2015b, title = {A Scaling Law to Predict the Finite-Length Performance of Spatially-Coupled LDPC Codes}, author = {Olmos, Pablo M. and Urbanke, Rudiger L.}, url = {http://ieeexplore.ieee.org/lpdocs/epic03/wrapper.htm?arnumber=7086074}, doi = {10.1109/TIT.2015.2422816}, issn = {0018-9448}, year = {2015}, date = {2015-06-01}, journal = {IEEE Transactions on Information Theory}, volume = {61}, number = {6}, pages = {3164--3184}, abstract = {Spatially-coupled low-density parity-check (SC-LDPC) codes are known to have excellent asymptotic properties. Much less is known regarding their finite-length performance. We propose a scaling law to predict the error probability of finite-length spatially coupled code ensembles when transmission takes place over the binary erasure channel. We discuss how the parameters of the scaling law are connected to fundamental quantities appearing in the asymptotic analysis of these ensembles and we verify that the predictions of the scaling law fit well to the data derived from simulations over a wide range of parameters. The ultimate goal of this line of research is to develop analytic tools for the design of SC-LDPC codes under practical constraints.}, keywords = {asymptotic analysis, asymptotic properties, binary erasure channel, Channel Coding, Codes on graphs, Couplings, Decoding, Differential equations, error probability, finite length performance, finite length spatially coupled code, finite-length code performance, finite-length performance, Iterative decoding, iterative decoding thresholds, Journal, parity check codes, Probability, SC-LDPC codes, scaling law, Sockets, spatially coupled LDPC codes, spatially-coupled LDPC codes}, pubstate = {published}, tppubtype = {article} } Spatially-coupled low-density parity-check (SC-LDPC) codes are known to have excellent asymptotic properties. Much less is known regarding their finite-length performance. We propose a scaling law to predict the error probability of finite-length spatially coupled code ensembles when transmission takes place over the binary erasure channel. We discuss how the parameters of the scaling law are connected to fundamental quantities appearing in the asymptotic analysis of these ensembles and we verify that the predictions of the scaling law fit well to the data derived from simulations over a wide range of parameters. The ultimate goal of this line of research is to develop analytic tools for the design of SC-LDPC codes under practical constraints. |

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

## 2013 |

## Inproceedings |

Salamanca, Luis; Murillo-Fuentes, Juan Jose; Olmos, Pablo; Perez-Cruz, Fernando Improving the BP Estimate over the AWGN Channel Using Tree-Structured Expectation Propagation (Inproceeding) 2013 IEEE International Symposium on Information Theory, pp. 2990–2994, IEEE, Istanbul, 2013, ISSN: 2157-8095. (Abstract | Links | BibTeX | Tags: Approximation algorithms, Approximation methods, AWGN channels, BEC, belief propagation decoding, BI-AWGN channel, binary additive white Gaussian noise channel, binary erasure channel, BP estimation, Channel Coding, Complexity theory, error rate reduction, error statistics, Expectation, finite-length codes, Iterative decoding, LDPC codes, LDPC decoding, low-density parity-check decoding, Maximum likelihood decoding, parity check codes, posterior distribution, Propagation, TEP algorithm, tree-structured expectation propagation algorithm, trees (mathematics)) @inproceedings{Salamanca2013, title = {Improving the BP Estimate over the AWGN Channel Using Tree-Structured Expectation Propagation}, 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=6620774}, issn = {2157-8095}, year = {2013}, date = {2013-01-01}, booktitle = {2013 IEEE International Symposium on Information Theory}, pages = {2990--2994}, publisher = {IEEE}, address = {Istanbul}, abstract = {In this paper, we propose the tree-structured expectation propagation (TEP) algorithm for low-density parity-check (LDPC) decoding over the binary additive white Gaussian noise (BI-AWGN) channel. By approximating the posterior distribution by a tree-structure factorization, the TEP has been proven to improve belief propagation (BP) decoding over the binary erasure channel (BEC). We show for the AWGN channel how the TEP decoder is also able to capture additional information disregarded by the BP solution, which leads to a noticeable reduction of the error rate for finite-length codes. We show that for the range of codes of interest, the TEP gain is obtained with a slight increase in complexity over that of the BP algorithm. An efficient way of constructing the tree-like structure is also described.}, keywords = {Approximation algorithms, Approximation methods, AWGN channels, BEC, belief propagation decoding, BI-AWGN channel, binary additive white Gaussian noise channel, binary erasure channel, BP estimation, Channel Coding, Complexity theory, error rate reduction, error statistics, Expectation, finite-length codes, Iterative decoding, LDPC codes, LDPC decoding, low-density parity-check decoding, Maximum likelihood decoding, parity check codes, posterior distribution, Propagation, TEP algorithm, tree-structured expectation propagation algorithm, 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 binary additive white Gaussian noise (BI-AWGN) channel. By approximating the posterior distribution by a tree-structure factorization, the TEP has been proven to improve belief propagation (BP) decoding over the binary erasure channel (BEC). We show for the AWGN channel how the TEP decoder is also able to capture additional information disregarded by the BP solution, which leads to a noticeable reduction of the error rate for finite-length codes. We show that for the range of codes of interest, the TEP gain is obtained with a slight increase in complexity over that of the BP algorithm. An efficient way of constructing the tree-like structure is also described. |

## 2012 |

## Journal Articles |

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

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

Olmos, Pablo; Murillo-Fuentes, Juan Jose; Perez-Cruz, Fernando Capacity Achieving LDPC Ensembles for the TEP Decoder in Erasure Channels (Inproceeding) 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 = {Olmos, Pablo M. and Murillo-Fuentes, Juan Jose and Perez-Cruz, Fernando}, 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; Murillo-Fuentes, Juan Jose; Perez-Cruz, Fernando MAP Decoding for LDPC Codes over the Binary Erasure Channel (Inproceeding) 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. |

## 2010 |

## Journal Articles |

Fresia, Maria; Perez-Cruz, Fernando; Poor, Vincent; Verdu, Sergio Joint Source and Channel Coding (Journal Article) IEEE Signal Processing Magazine, 27 (6), pp. 104–113, 2010, ISSN: 1053-5888. (Abstract | Links | BibTeX | Tags: belief propagation, Channel Coding, combined source-channel coding, Decoding, Encoding, graphical model, Hidden Markov models, Iterative decoding, joint source channel coding, JSC coding, LDPC code, low density parity check code, Markov processes, parity check codes, Slepian-Wolf problem, variable length codes) @article{Fresia2010, title = {Joint Source and Channel Coding}, author = {Fresia, Maria and Perez-Cruz, Fernando and Poor, H. Vincent and Verdu, Sergio}, url = {http://ieeexplore.ieee.org/lpdocs/epic03/wrapper.htm?arnumber=5563107}, issn = {1053-5888}, year = {2010}, date = {2010-01-01}, journal = {IEEE Signal Processing Magazine}, volume = {27}, number = {6}, pages = {104--113}, abstract = {The objectives of this article are two-fold: First, to present the problem of joint source and channel (JSC) coding from a graphical model perspective and second, to propose a structure that uses a new graphical model for jointly encoding and decoding a redundant source. In the first part of the article, relevant contributions to JSC coding, ranging from the Slepian-Wolf problem to joint decoding of variable length codes with state-of-the-art source codes, are reviewed and summarized. In the second part, a double low-density parity-check (LDPC) code for JSC coding is proposed. The double LDPC code can be decoded as a single bipartite graph using standard belief propagation (BP) and its limiting performance is analyzed by using extrinsic information transfer (EXIT) chart approximations.}, keywords = {belief propagation, Channel Coding, combined source-channel coding, Decoding, Encoding, graphical model, Hidden Markov models, Iterative decoding, joint source channel coding, JSC coding, LDPC code, low density parity check code, Markov processes, parity check codes, Slepian-Wolf problem, variable length codes}, pubstate = {published}, tppubtype = {article} } The objectives of this article are two-fold: First, to present the problem of joint source and channel (JSC) coding from a graphical model perspective and second, to propose a structure that uses a new graphical model for jointly encoding and decoding a redundant source. In the first part of the article, relevant contributions to JSC coding, ranging from the Slepian-Wolf problem to joint decoding of variable length codes with state-of-the-art source codes, are reviewed and summarized. In the second part, a double low-density parity-check (LDPC) code for JSC coding is proposed. The double LDPC code can be decoded as a single bipartite graph using standard belief propagation (BP) and its limiting performance is analyzed by using extrinsic information transfer (EXIT) chart approximations. |