2014
Cespedes, Javier; Olmos, Pablo M; Sanchez-Fernandez, Matilde; Perez-Cruz, Fernando
Expectation Propagation Detection for High-order High-dimensional MIMO Systems Artículo de revista
En: IEEE Transactions on Communications, vol. PP, no 99, pp. 1–1, 2014, ISSN: 0090-6778.
Resumen | Enlaces | BibTeX | Etiquetas: Approximation methods, computational complexity, Detectors, MIMO, Signal to noise ratio, Vectors
@article{Cespedes2014,
title = {Expectation Propagation Detection for High-order High-dimensional MIMO Systems},
author = {Javier Cespedes and Pablo M Olmos and Matilde Sanchez-Fernandez and Fernando Perez-Cruz},
url = {http://ieeexplore.ieee.org/lpdocs/epic03/wrapper.htm?arnumber=6841617},
issn = {0090-6778},
year = {2014},
date = {2014-01-01},
journal = {IEEE Transactions on Communications},
volume = {PP},
number = {99},
pages = {1--1},
abstract = {Modern communications systems use multiple-input multiple-output (MIMO) and high-order QAM constellations for maximizing spectral efficiency. However, as the number of antennas and the order of the constellation grow, the design of efficient and low-complexity MIMO receivers possesses big technical challenges. For example, symbol detection can no longer rely on maximum likelihood detection or sphere-decoding methods, as their complexity increases exponentially with the number of transmitters/receivers. In this paper, we propose a low-complexity high-accuracy MIMO symbol detector based on the Expectation Propagation (EP) algorithm. EP allows approximating iteratively at polynomial-time the posterior distribution of the transmitted symbols. We also show that our EP MIMO detector outperforms classic and state-of-the-art solutions reducing the symbol error rate at a reduced computational complexity.},
keywords = {Approximation methods, computational complexity, Detectors, MIMO, Signal to noise ratio, Vectors},
pubstate = {published},
tppubtype = {article}
}
Modern communications systems use multiple-input multiple-output (MIMO) and high-order QAM constellations for maximizing spectral efficiency. However, as the number of antennas and the order of the constellation grow, the design of efficient and low-complexity MIMO receivers possesses big technical challenges. For example, symbol detection can no longer rely on maximum likelihood detection or sphere-decoding methods, as their complexity increases exponentially with the number of transmitters/receivers. In this paper, we propose a low-complexity high-accuracy MIMO symbol detector based on the Expectation Propagation (EP) algorithm. EP allows approximating iteratively at polynomial-time the posterior distribution of the transmitted symbols. We also show that our EP MIMO detector outperforms classic and state-of-the-art solutions reducing the symbol error rate at a reduced computational complexity.
2013
Olmos, Pablo M; Murillo-Fuentes, Juan Jose; Perez-Cruz, Fernando
Tree-Structure Expectation Propagation for LDPC Decoding Over the BEC Artículo de revista
En: IEEE Transactions on Information Theory, vol. 59, no 6, pp. 3354–3377, 2013, ISSN: 0018-9448.
Resumen | Enlaces | BibTeX | Etiquetas: Algorithm design and analysis, Approximation algorithms, Approximation methods, BEC, belief propagation, Belief-propagation (BP), binary erasure channel, Complexity theory, decode low-density parity-check codes, Decoding, discrete memoryless channels, expectation propagation, finite-length analysis, LDPC codes, LDPC decoding, parity check codes, peeling-type algorithm, Probability density function, random graph evolution, Tanner graph, tree-structure expectation propagation
@article{Olmos2013b,
title = {Tree-Structure Expectation Propagation for LDPC Decoding Over the BEC},
author = {Pablo M Olmos and Juan Jose Murillo-Fuentes and Fernando Perez-Cruz},
url = {http://ieeexplore.ieee.org/lpdocs/epic03/wrapper.htm?arnumber=6451276},
issn = {0018-9448},
year = {2013},
date = {2013-01-01},
journal = {IEEE Transactions on Information Theory},
volume = {59},
number = {6},
pages = {3354--3377},
abstract = {We present the tree-structure expectation propagation (Tree-EP) algorithm to decode low-density parity-check (LDPC) codes over discrete memoryless channels (DMCs). Expectation propagation generalizes 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 pairwise marginal constraints over pairs of variables connected to a check node of the LDPC code's Tanner graph. Thanks to these additional constraints, the Tree-EP marginal estimates for each variable in the graph are more accurate than those provided by BP. We also reformulate the Tree-EP algorithm for the binary erasure channel (BEC) as a peeling-type algorithm (TEP) and we show that the algorithm has the same computational complexity as BP and it decodes a higher fraction of errors. We describe the TEP decoding process by a set of differential equations that represents the expected residual graph evolution as a function of the code parameters. The solution of these equations is used to predict the TEP decoder performance in both the asymptotic regime and the finite-length regimes over the BEC. While the asymptotic threshold of the TEP decoder is the same as the BP decoder for regular and optimized codes, we propose a scaling law for finite-length LDPC codes, which accurately approximates the TEP improved performance and facilitates its optimization.},
keywords = {Algorithm design and analysis, Approximation algorithms, Approximation methods, BEC, belief propagation, Belief-propagation (BP), binary erasure channel, Complexity theory, decode low-density parity-check codes, Decoding, discrete memoryless channels, expectation propagation, finite-length analysis, LDPC codes, LDPC decoding, parity check codes, peeling-type algorithm, Probability density function, random graph evolution, Tanner graph, tree-structure expectation propagation},
pubstate = {published},
tppubtype = {article}
}
We present the tree-structure expectation propagation (Tree-EP) algorithm to decode low-density parity-check (LDPC) codes over discrete memoryless channels (DMCs). Expectation propagation generalizes 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 pairwise marginal constraints over pairs of variables connected to a check node of the LDPC code's Tanner graph. Thanks to these additional constraints, the Tree-EP marginal estimates for each variable in the graph are more accurate than those provided by BP. We also reformulate the Tree-EP algorithm for the binary erasure channel (BEC) as a peeling-type algorithm (TEP) and we show that the algorithm has the same computational complexity as BP and it decodes a higher fraction of errors. We describe the TEP decoding process by a set of differential equations that represents the expected residual graph evolution as a function of the code parameters. The solution of these equations is used to predict the TEP decoder performance in both the asymptotic regime and the finite-length regimes over the BEC. While the asymptotic threshold of the TEP decoder is the same as the BP decoder for regular and optimized codes, we propose a scaling law for finite-length LDPC codes, which accurately approximates the TEP improved performance and facilitates its optimization.
Salamanca, Luis; Olmos, Pablo M; Perez-Cruz, Fernando; Murillo-Fuentes, Juan Jose
Tree-Structured Expectation Propagation for LDPC Decoding over BMS Channels Artículo de revista
En: IEEE Transactions on Communications, vol. 61, no 10, pp. 4086–4095, 2013, ISSN: 0090-6778.
Resumen | Enlaces | BibTeX | Etiquetas: Approximation algorithms, Approximation methods, BEC, belief propagation, binary erasure channel, binary memoryless symmetric channels, BMS channels, Channel Coding, Complexity theory, convolutional codes, convolutional low-density parity-check codes, Decoding, decoding block, expectation propagation, finite-length codes, LDPC decoding, message-passing algorithm, parity check codes, Probability density function, sparse linear codes, TEP algorithm, tree-structured expectation propagation, trees (mathematics), Vegetation
@article{Salamanca2013a,
title = {Tree-Structured Expectation Propagation for LDPC Decoding over BMS Channels},
author = {Luis Salamanca and Pablo M Olmos and Fernando Perez-Cruz and Juan Jose Murillo-Fuentes},
url = {http://ieeexplore.ieee.org/lpdocs/epic03/wrapper.htm?arnumber=6587624},
issn = {0090-6778},
year = {2013},
date = {2013-01-01},
journal = {IEEE Transactions on Communications},
volume = {61},
number = {10},
pages = {4086--4095},
abstract = {In this paper, we put forward the tree-structured expectation propagation (TEP) algorithm for decoding block and convolutional low-density parity-check codes over any binary channel. We have already shown that TEP improves belief propagation (BP) over the binary erasure channel (BEC) by imposing marginal constraints over a set of pairs of variables that form a tree or a forest. The TEP decoder is a message-passing algorithm that sequentially builds a tree/forest of erased variables to capture additional information disregarded by the standard BP decoder, which leads to a noticeable reduction of the error rate for finite-length codes. In this paper, we show how the TEP can be extended to any channel, specifically to binary memoryless symmetric (BMS) channels. We particularly focus on how the TEP algorithm can be adapted for any channel model and, more importantly, how to choose the tree/forest to keep the gains observed for block and convolutional LDPC codes over the BEC.},
keywords = {Approximation algorithms, Approximation methods, BEC, belief propagation, binary erasure channel, binary memoryless symmetric channels, BMS channels, Channel Coding, Complexity theory, convolutional codes, convolutional low-density parity-check codes, Decoding, decoding block, expectation propagation, finite-length codes, LDPC decoding, message-passing algorithm, parity check codes, Probability density function, sparse linear codes, TEP algorithm, tree-structured expectation propagation, trees (mathematics), Vegetation},
pubstate = {published},
tppubtype = {article}
}
In this paper, we put forward the tree-structured expectation propagation (TEP) algorithm for decoding block and convolutional low-density parity-check codes over any binary channel. We have already shown that TEP improves belief propagation (BP) over the binary erasure channel (BEC) by imposing marginal constraints over a set of pairs of variables that form a tree or a forest. The TEP decoder is a message-passing algorithm that sequentially builds a tree/forest of erased variables to capture additional information disregarded by the standard BP decoder, which leads to a noticeable reduction of the error rate for finite-length codes. In this paper, we show how the TEP can be extended to any channel, specifically to binary memoryless symmetric (BMS) channels. We particularly focus on how the TEP algorithm can be adapted for any channel model and, more importantly, how to choose the tree/forest to keep the gains observed for block and convolutional LDPC codes over the BEC.
Salamanca, Luis; Olmos, Pablo M; Murillo-Fuentes, Juan Jose; Perez-Cruz, Fernando
Tree Expectation Propagation for ML Decoding of LDPC Codes over the BEC Artículo de revista
En: IEEE Transactions on Communications, vol. 61, no 2, pp. 465–473, 2013, ISSN: 0090-6778.
Resumen | Enlaces | BibTeX | Etiquetas: 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}
}
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.
2012
Salamanca, Luis; Murillo-Fuentes, Juan Jose; Perez-Cruz, Fernando
Bayesian Equalization for LDPC Channel Decoding Artículo de revista
En: IEEE Transactions on Signal Processing, vol. 60, no 5, pp. 2672–2676, 2012, ISSN: 1053-587X.
Resumen | Enlaces | BibTeX | Etiquetas: Approximation methods, Bayes methods, Bayesian equalization, Bayesian estimation problem, Bayesian inference, Bayesian methods, BCJR (Bahl–Cocke–Jelinek–Raviv) algorithm, BCJR algorithm, Channel Coding, channel decoding, channel equalization, channel equalization problem, Channel estimation, channel state information, CSI, Decoding, equalisers, Equalizers, expectation propagation, expectation propagation algorithm, fading channels, graphical model representation, intersymbol interference, Kullback-Leibler divergence, LDPC, LDPC coding, low-density parity-check decoder, Modulation, parity check codes, symbol posterior estimates, Training
@article{Salamanca2012b,
title = {Bayesian Equalization for LDPC Channel Decoding},
author = {Luis Salamanca and Juan Jose Murillo-Fuentes and Fernando Perez-Cruz},
url = {http://ieeexplore.ieee.org/lpdocs/epic03/wrapper.htm?arnumber=6129544},
issn = {1053-587X},
year = {2012},
date = {2012-01-01},
journal = {IEEE Transactions on Signal Processing},
volume = {60},
number = {5},
pages = {2672--2676},
abstract = {We describe the channel equalization problem, and its prior estimate of the channel state information (CSI), as a joint Bayesian estimation problem to improve each symbol posterior estimates at the input of the channel decoder. Our approach takes into consideration not only the uncertainty due to the noise in the channel, but also the uncertainty in the CSI estimate. However, this solution cannot be computed in linear time, because it depends on all the transmitted symbols. Hence, we also put forward an approximation for each symbol's posterior, using the expectation propagation algorithm, which is optimal from the Kullback-Leibler divergence viewpoint and yields an equalization with a complexity identical to the BCJR algorithm. We also use a graphical model representation of the full posterior, in which the proposed approximation can be readily understood. The proposed posterior estimates are more accurate than those computed using the ML estimate for the CSI. In order to illustrate this point, we measure the error rate at the output of a low-density parity-check decoder, which needs the exact posterior for each symbol to detect the incoming word and it is sensitive to a mismatch in those posterior estimates. For example, for QPSK modulation and a channel with three taps, we can expect gains over 0.5 dB with same computational complexity as the ML receiver.},
keywords = {Approximation methods, Bayes methods, Bayesian equalization, Bayesian estimation problem, Bayesian inference, Bayesian methods, BCJR (Bahl\textendashCocke\textendashJelinek\textendashRaviv) algorithm, BCJR algorithm, Channel Coding, channel decoding, channel equalization, channel equalization problem, Channel estimation, channel state information, CSI, Decoding, equalisers, Equalizers, expectation propagation, expectation propagation algorithm, fading channels, graphical model representation, intersymbol interference, Kullback-Leibler divergence, LDPC, LDPC coding, low-density parity-check decoder, Modulation, parity check codes, symbol posterior estimates, Training},
pubstate = {published},
tppubtype = {article}
}
We describe the channel equalization problem, and its prior estimate of the channel state information (CSI), as a joint Bayesian estimation problem to improve each symbol posterior estimates at the input of the channel decoder. Our approach takes into consideration not only the uncertainty due to the noise in the channel, but also the uncertainty in the CSI estimate. However, this solution cannot be computed in linear time, because it depends on all the transmitted symbols. Hence, we also put forward an approximation for each symbol's posterior, using the expectation propagation algorithm, which is optimal from the Kullback-Leibler divergence viewpoint and yields an equalization with a complexity identical to the BCJR algorithm. We also use a graphical model representation of the full posterior, in which the proposed approximation can be readily understood. The proposed posterior estimates are more accurate than those computed using the ML estimate for the CSI. In order to illustrate this point, we measure the error rate at the output of a low-density parity-check decoder, which needs the exact posterior for each symbol to detect the incoming word and it is sensitive to a mismatch in those posterior estimates. For example, for QPSK modulation and a channel with three taps, we can expect gains over 0.5 dB with same computational complexity as the ML receiver.