### 2013

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

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

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}

}

### 2011

Olmos, Pablo M; Murillo-Fuentes, Juan Jose; Perez-Cruz, Fernando

Tree-Structured Expectation Propagation for Decoding Finite-Length LDPC Codes Journal Article

In: 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}

}