## 2011 |

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

## 2010 |

Olmos, Pablo M; Murillo-Fuentes, Juan Jose; Perez-Cruz, Fernando Tree-Structure Expectation Propagation for Decoding LDPC Codes over Binary Erasure Channels Inproceedings 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 = {Pablo M Olmos and Juan Jose Murillo-Fuentes and Fernando Perez-Cruz}, 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. |