Search

In this paper we propose a novel turbo equalizer based on the expectation propagation (EP) algorithm. Optimal equalization is computationally unfeasible when high-order modulations and/or large memory channels are used. In these scenarios, low-cost and suboptimal equalizers, such as those based on the linear minimum mean square error (LMMSE), are commonly used. The LMMSE-based equalizer can be efficiently implemented with a Kalman smoother (KS), i.e., a forward and backward Kalman filtering whose predictions are merged in a posterior smoothing step. Recently, it was shown that applying EP at the forward and backward stages of a KS equalizer could significantly improve its performance. In this paper, we investigate applying EP at the smoothing level instead. Also, we propose some further modifications to better exploit the information coming from the channel decoder in turbo equalization schemes. Overall, we remarkably reduce the computational complexity while highly improving the performance in terms of bit error rate.

We investigate a turbo soft detector based on the expectation propagation (EP) algorithm for large-scale multiple-input multiple-output (MIMO) systems. Optimal detection in MIMO systems becomes computationally unfeasible for high-order modulations and/or large number of antennas. In this situation, the linear minimum mean square error (LMMSE) exhibits a low-complexity with a good performance, however far from optimal. To improve the performance, the EP algorithm can be used. In this paper, we review previous EP-based detectors and enhance their estimation in terms of complexity and performance. Specifically, we improve the convergence of the self-iterated EP stage by replacing the uniform prior by a non-uniform one, which better characterizes the information returned by the decoder once the turbo procedure starts. We also review the EP parameters to avoid instabilities when using high-order modulations and to reduce the computational complexity. Simulation results illustrate the robustness and enhanced performance of this novel detector in comparison with previous approaches found in the literature. Results also show that the proposed detector is robust in the presence of imperfect channel state information (CSI).

We propose a new iterative detection and decoding algorithm for multiple-input multiple-output (MIMO) based on expectation propagation (EP) with application to massive MIMO scenarios. Two main results are presented. We first introduce EP to iteratively improve the Gaussian approximations of both the estimation of the posterior by the MIMO detector and the soft output of the channel decoder. With this novel approach, denoted by double-EP (DEP), the convergence is very much improved with a computational complexity just two times the one of the linear minimum mean square error (LMMSE), as illustrated by the included experiments. Besides, as in the LMMSE MIMO detector, when the number of antennas increases, the computational cost of the matrix inversion operation required by the DEP becomes unaffordable. In this work we also develop approaches of DEP where the mean and the covariance matrix of the posterior are approximated by using the Gauss-Seidel and Neumann series methods, respectively. This low-complexity DEP detector has quadratic complexity in the number of antennas, i.e., the same as the low-complexity LMMSE techniques. Experimental results show that the new low-complexity DEP achieves the performance of the DEP as the ratio between the number of transmitting and receiving antennas decreases

This manuscript has been submitted to Transactions on Communications on September 7, 2017; revised on January 10, 2018 and March 27, 2018; and accepted on April 25, 2018 We propose a novel filter-type equalizer to improve the solution of the linear minimum-mean squared-error (LMMSE) turbo equalizer, with computational complexity constrained to be quadratic in the filter length. When high-order modulations and/or large memory channels are used the optimal BCJR equalizer is unavailable, due to its computational complexity. In this scenario, the filter-type LMMSE turbo equalization exhibits a good performance compared to other approximations. In this paper, we show that this solution can be significantly improved by using expectation propagation (EP) in the estimation of the a posteriori probabilities. First, it yields a more accurate estimation of the extrinsic distribution to be sent to the channel decoder. Second, compared to other solutions based on EP the computational complexity of the proposed solution is constrained to be quadratic in the length of the finite impulse response (FIR). In addition, we review previous EP-based turbo equalization implementations. Instead of considering default uniform priors we exploit the outputs of the decoder. Some simulation results are included to show that this new EP-based filter remarkably outperforms the turbo approach of previous versions of the EP algorithm and also improves the LMMSE solution, with and without turbo equalization.

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.

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.

Actual communications systems use high-order modulations and channels with memory. However, as the memory of the channels and the order of the constellations grow, optimal equalization such as BCJR algorithm is computationally intractable, as their complexity increases exponentially with the number of taps and size of modulation. In this paper, we propose a novel low-complexity hard and soft output equalizer based on the Expectation Propagation (EP) algorithm that provides high-accuracy posterior probability estimations at the input of the channel decoder with similar computational complexity than the linear MMSE. We experimentally show that this quasi-optimal solution outperforms classical solutions reducing the bit error probability with low complexity when LDPC channel decoding is used, avoiding the curse of dimensionality with channel memory and constellation size.

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.

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.

In this paper, we propose the tree-structured expectation propagation (TEP) algorithm for low-density parity-check (LDPC) decoding over the additive white Gaussian noise (AWGN) channel. By imposing a tree-like approximation over the graphical model of the code, this algorithm introduces pairwise marginal constraints over pairs of variables, which provide joint information of the variables related. Thanks to this, the proposed TEP decoder improves the performance of the standard belief propagation (BP) solution. An efficient way of constructing the tree-like structure is also described. The simulation results illustrate the TEP decoder gain in the finite-length regime, compared to the standard BP solution. For code lengths shorter than n = 512, the gain in the waterfall region achieves up to 0.25 dB. We also notice a remarkable reduction of the error floor.

In this work, we analyze the finite-length performance of low-density parity check (LDPC) ensembles decoded over the binary erasure channel (BEC) using the tree-expectation propagation (TEP) algorithm. In a previous paper, we showed that the TEP improves the BP performance for decoding regular and irregular short LDPC codes, but the perspective was mainly empirical. In this work, given the degree-distribution of an LDPC ensemble, we explain and predict the range of code lengths for which the TEP improves the BP solution. In addition, for LDPC ensembles that present a single critical point, we propose a scaling law to accurately predict the performance in the waterfall region. These results are of critical importance to design practical LDPC codes for the TEP decoder.

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.

We present the tree-structure expectation propagation (Tree-EP) algorithm to decode low-density parity-check (LDPC) codes over discrete memoryless channels (DMCs). EP 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 pair-wise 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 regime 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 (SL) for finite-length LDPC codes, which accurately approximates the TEP improved performance and facilitates its optimization.

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.

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.

In this paper we focus on the probabilistic channel equalization in digital communications. We face the single input single output (SISO) model to show how the statistical information about the multipath channel can be exploited to further improve our estimation of the a posteriori probabilities (APP) during the equalization process. We consider not only the uncertainty due to the noise in the channel, but also in the estimate of the channel estate information (CSI). Thus, we resort to a Bayesian approach for the computation of the APP. This novel algorithm has the same complexity as the BCJR, exhibiting lower bit error rate at the output of the channel decoder than the standard BCJR that considers maximum likelihood (ML) to estimate the CSI

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

Low-density parity-check (LPDC) decoders assume the channel estate information (CSI) is known and they have the true a posteriori probability (APP) for each transmitted bit. But in most cases of interest, the CSI needs to be estimated with the help of a short training sequence and the LDPC decoder has to decode the received word using faulty APP estimates. In this paper, we study the uncertainty in the CSI estimate and how it affects the bit error rate (BER) output by the LDPC decoder. To improve these APP estimates, we propose a Bayesian equalizer that takes into consideration not only the uncertainty due to the noise in the channel, but also the uncertainty in the CSI estimate, reducing the BER after the LDPC decoder., Comment: 5 pages, 6 figures, ISIT 2010 conference

In probabilistic equalization of channels with inter-symbol interference, the BCJR algorithm and its approximations become intractable for high-order modulations, even for moderate channel dispersions. In this paper, we introduce a novel soft equalizer to approximate the symbol a posteriori probabilities (APP), where the expectation propagation (EP) algorithm is used to provide an accurate estimation. This new soft equalizer is presented as a block solution, denoted as block-EP (BEP), where the structure of the matrices involved is exploited to reduce the complexity order to $ {\mathcal {O}}( L N ^{2})$ , i.e., linear in the length of the channel, $ L$ , and quadratic in the frame length, $ N$ . The solution is presented in complex-valued formulation within a turbo equalization scheme. This algorithm can be cast as a linear minimum-mean-squared-error (LMMSE) turbo equalization with double feedback architecture, where constellations being discrete is a restriction exploited by the EP that provides a first refinement of the APP. In the experiments included, the BEP exhibits a robust performance, regardless of the channel response, with gains in the range 1.5–5 dB compared with the LMMSE equalization.

In this paper we propose to use Gaussian processes for classification (GPC) for solving the channel equalization problem. GPC provides not only accurate decisions as other nonlinear machine learning tools do, i.e. support vector machines or neural networks, but it also assigns posterior probabilities to each one of its output. This is a significant advantage of GPC with respect to other machine learning tools for channel equalization, because the channel decoder benefits from its soft outputs to provide significantly better error correcting capabilities for the entire communication system. As, for previous schemes, the channel decoder had to rely on the hard decisions given by the equalizer, because the output of these methods cannot be transformed into posterior probabilities. We show that the GCP equalizer is able to estimate posterior probabilities accurately in a variety of real digital communications channel.