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. |
Year | DOI | Venue |
---|---|---|
2013 | 10.1109/TCOMM.2012.120512.110419 | Communications, IEEE Transactions |
Keywords | Field | DocType |
Gaussian processes,binary codes,maximum likelihood decoding,parity check codes,trees (mathematics),BEC,Gaussian elimination method,LDPC codes,ML decoding,approximate inference,binary erasure channel,code graph,equivalent complexity,generalized tree-structured expectation propagation,graphical message-passing procedure,maximum likelihood solution,peeling decoder,tree expectation propagation,tree graph,tree-structured expectation propagation decoder,LDPC codes,ML decoding,binary erasure channel,graphical models,tree-structured expectation propagation | Factor graph,Discrete mathematics,Concatenated error correction code,Sequential decoding,Tree (graph theory),Computer science,Low-density parity-check code,Binary erasure channel,List decoding,Belief propagation | Journal |
Volume | Issue | ISSN |
61 | 2 | 0090-6778 |
Citations | PageRank | References |
3 | 0.41 | 24 |
Authors | ||
6 |
Name | Order | Citations | PageRank |
---|---|---|---|
Luis Salamanca | 1 | 28 | 5.63 |
Pablo M. Olmos | 2 | 114 | 18.97 |
Juan José Murillo-Fuentes | 3 | 182 | 23.93 |
Fernando Pérez-Cruz | 4 | 749 | 61.24 |
Murillo-Fuentes, J.J. | 5 | 37 | 6.55 |
Perez-Cruz, F. | 6 | 3 | 0.41 |