Search

Variational autoencoders (VAEs), as well as other generative models, have been shown to be efficient and accurate for capturing the latent structure of vast amounts of complex high-dimensional data. However, existing VAEs can still not directly handle data that are heterogenous (mixed continuous and discrete) or incomplete (with missing data at random), which is indeed common in real-world applications. In this paper, we propose a general framework to design VAEs suitable for fitting incomplete heterogenous data. The proposed HI-VAE includes likelihood models for real-valued, positive real valued, interval, categorical, ordinal and count data, and allows accurate estimation (and potentially imputation) of missing data. Furthermore, HI-VAE presents competitive predictive performance in supervised tasks, outperforming supervised models when trained on incomplete data. The authors wish to thank Christopher K. I. Williams, for fruitful discussions and helpful comments to the manuscript. Alfredo Nazabal would like to acknowledge the funding provided by the UK Government’s Defence & Security Programme in support of the Alan Turing Institute, EPSRC Grant EP/N510129/1. The work of Pablo M. Olmos is sup-ported by Spanish government MCI under grant RTI2018-099655-B-100, by Comunidad de Madrid under grants IND2017/TIC-7618, IND2018/TIC-9649, and Y2018/TCS-4705, by BBVA Foundation under the Deep-DARWiNproject, and by the European Union (FEDER and the European Research Council (ERC) through the European Unions Horizon 2020 research and innovation program under Grant 714161). Zoubin Ghahramani acknowledges support from the Alan Turing Institute (EPSRC Grant EP/N510129/1) and EPSRC Grant EP/N014162/1, and donations from Google and Microsoft Research. We also gratefully acknowledge the support of NVIDIA Corporation with the donation of the Titan X Pascal GPU used for this research.

Proceeding of 2020 Computing in Cardiology (CinC 2020), 13-16 September 2020, Rimini, Italy Activity detection in atrial fibrillation (AF) electrograms (EGMs) is a key concept to understand the mechanisms of this frequent arrhythmia and design new strategies for its treatment. We present a new method that employs Hidden Markov Models (HMMs) to identify activity presence in bipolar EGMs. The method is fully unsupervised and hence it does not require labeled training data. The HMM activity detection method was validated and compared to the non-linear energy operator (NLEO) method for a set of manually annotated EGMs. The HMM performed better than the NLEO and exhibited more robustness in the presence of low voltage fragmented EGMs. This study was supported by grants PI18/01895 from the Instituto de Salud Carlos III, and RD16/0011/0029 Red de Terapia Celular from the Instituto de Salud Carlos III, the projects RTI2018-099655-B-I00; TEC2017-92552-EXP; PID2019-108539RB-C22, Y2018/TCS-4705, and the support of NVIDIA Corporation with the donation of the Titan V GPU used during this research. Publicado

This paper focuses on the offline handwriting text recognition problem (HTR) with small training data sets. Some techniques such as transfer learning or data augmentation have recently been applied to this problem, improving the performance of the recognition. In these scenarios, we found that errors in the labelling of the training samples, present in some databases, have a great impact in the character error rates (CER). Accordingly, we propose a novel cross validation technique to remove incorrect labelled lines. In this approach, after a first training stage, transcript lines with CER above a threshold are discarded, where the threshold is a function of the available data. Less available data favours larger CER, even for healthy lines, suggesting higher thresholds for fewer lines. This new technique and the validation of the threshold are analyzed over the ICFHR 2018 competition on automated HTR and other well known databases such as Washington and Parzival. For the Ricordi database in the ICFHR 2018, with transcription errors, we report a reduction of CER by 2%.

The Bayesian approach to feature extraction, known as factor analysis (FA), has been widely studied in machine learning to obtain a latent representation of the data. An adequate selection of the probabilities and priors of these bayesian models allows the model to better adapt to the data nature (i.e. heterogeneity, sparsity), obtaining a more representative latent space. The objective of this article is to propose a general FA framework capable of modelling any problem. To do so, we start from the Bayesian Inter-Battery Factor Analysis (BIBFA) model, enhancing it with new functionalities to be able to work with heterogeneous data, to include feature selection, and to handle missing values as well as semi-supervised problems. The performance of the proposed model, Sparse Semi-supervised Heterogeneous Interbattery Bayesian Analysis (SSHIBA), has been tested on different scenarios to evaluate each one of its novelties, showing not only a great versatility and an interpretability gain, but also outperforming most of the state-of-the-art algorithms.

In this paper, we face the soft equalization of channels with inter-symbol interference for large constellation sizes, $ \mathtt {M}$ . In this scenario, the optimal BCJR solution and most of their approximations are intractable, as the number of states they track grows fast with $ \mathtt {M}$ . We present a probabilistic equalizer to approximate the posterior distributions of the transmitted symbols using the expectation propagation (EP) algorithm. The solution is presented as a recursive sliding window approach to ensure that the computational complexity is linear with the length of the frame. The estimations can be further improved with a forward–backward approach. This novel soft equalizer, denoted as smoothing EP (SEP), is also tested as a turbo equalizer, with a low-density parity-check (LDPC) channel decoder. The extensive results reported reveal remarkably good behavior of the SEP. In low dimensional cases, the bit error rate (BER) curves after decoding are closer than 1 dB from those of the BJCR, robust to the channel response. For large $ \mathtt {M}$ , the SEP exhibits gains in the range of 3–5 dB compared to the linear minimum mean square error algorithm.

This article presents a novel method for predicting suicidal ideation from Electronic Health Records (EHR) and Ecological Momentary Assessment (EMA) data using deep sequential models. Both EHR longitudinal data and EMA question forms are defined by asynchronous, variable length, randomly-sampled data sequences. In our method, we model each of them with a Recurrent Neural Network (RNN), and both sequences are aligned by concatenating the hidden state of each of them using temporal marks. Furthermore, we incorporate attention schemes to improve performance in long sequences and time-independent pre-trained schemes to cope with very short sequences. Using a database of 1023 patients, our experimental results show that the addition of EMA records boosts the system recall to predict the suicidal ideation diagnosis from 48.13% obtained exclusively from EHR-based state-of-the-art methods to 67.78%. Additionally, our method provides interpretability through the t-SNE representation of the latent space. Further, the most relevant input features are identified and interpreted medically., Accepted for publication in IEEE Journal of Biomedical and Health Informatics (JBHI)

In this paper, we take a new approach for time of arrival geo-localization. We show that the main sources of error in metropolitan areas are due to environmental imperfections that bias our solutions, and that we can rely on a probabilistic model to learn and compensate for them. The resulting localization error is validated using measurements from a live LTE cellular network to be less than 10 meters, representing an order-of-magnitude improvement., Comment: IEEE Signal Processing Letters, 2019

An analysis of spatially coupled low-density parity-check (SC-LDPC) codes constructed from protographs is proposed. Given the protograph used to generate the SC-LDPC code ensemble, a set of scaling parameters to characterize the average finite-length performance in the waterfall region is computed. The error performance of structured SC-LDPC code ensembles is shown to follow a scaling law similar to that of unstructured randomly constructed SC-LDPC codes. Under a finite-length perspective, some of the most relevant SC-LDPC protograph structures proposed to date are compared. The analysis reveals significant differences in their finite-length scaling behavior, which is corroborated by simulation. Spatially coupled repeat-accumulate codes present excellent finite-length performance, as they outperform in the waterfall region SC-LDPC codes of the same rate and better asymptotic thresholds.

In this paper, we explore low-complexity probabilistic algorithms for soft symbol detection in high-dimensional multiple-input multiple-output (MIMO) systems. We present a novel algorithm based on the expectation consistency (EC) framework, which describes the approximate inference problem as an optimization over a nonconvex function. EC generalizes algorithms such as belief propagation and expectation propagation. For the MIMO symbol detection problem, we discuss feasible methods to find stationary points of the EC function and explore their tradeoffs between accuracy and speed of convergence. The accuracy is studied, first in terms of input-output mutual information and show that the proposed EC MIMO detector greatly improves state-of-the-art methods, with a complexity order cubic in the number of transmitting antennas. Second, these gains are corroborated by combining the probabilistic output of the EC detector with a low-density parity-check channel code. This work has been partly supported by the Ministerio de Economía of Spain jointly with the European Commission (ERDF) under projects MIMOTEX (TEC2014-61776-EXP), CIES (RTC-2015-4213-7), ELISA (TEC2014-59255-C3-3R), FLUID (TEC2016-78434-C3-3-R) and CAIMAN (TEC2017-86921-C2-2-R), by the Juan de la Cierva program (IJCI-2014-19150), and by Comunidad de Madrid (project “CASI-CAM-CM" id. S2013/ICE-2845). Publicado

Generalized low-density parity-check (GLDPC) codes are a class of LDPC codes in which the standard single parity check (SPC) constraints are replaced by more general constraints, viz., constraints defined by a linear block code. These stronger constraints typically result in improved error floor performance, due to better minimum distance and trapping set properties, at a cost of some increased decoding complexity. In this paper, we summarize some recent results on spatially coupled generalized low-density parity-check (SC-GLDPC) codes. Results are compared to GLDPC block codes and the advantages and disadvantages of SC-GLDPC codes are discussed.

In this paper we deal with the offline handwriting text recognition (HTR) problem with reduced training datasets. Recent HTR solutions based on artificial neural networks exhibit remarkable solutions in referenced databases. These deep learning neural networks are composed of both convolutional (CNN) and long short-term memory recurrent units (LSTM). In addition, connectionist temporal classification (CTC) is the key to avoid segmentation at character level, greatly facilitating the labeling task. One of the main drawbacks of the CNNLSTM-CTC (CLC) solutions is that they need a considerable part of the text to be transcribed for every type of calligraphy, typically in the order of a few thousands of lines. Furthermore, in some scenarios the text to transcribe is not that long, e.g. in the Washington database. The CLC typically overfits for this reduced number of training samples. Our proposal is based on the transfer learning (TL) from the parameters learned with a bigger database. We first investigate, for a reduced and fixed number of training samples, 350 lines, how the learning from a large database, the IAM, can be transferred to the learning of the CLC of a reduced database, Washington. We focus on which layers of the network could be not re-trained. We conclude that the best solution is to re-train the whole CLC parameters initialized to the values obtained after the training of the CLC from the larger database. We also investigate results when the training size is further reduced. The differences in the CER are more remarkable when training with just 350 lines, a CER of 3.3% is achieved with TL while we have a CER of 18.2% when training from scratch. As a byproduct, the learning times are quite reduced. Similar good results are obtained from the Parzival database when trained with this reduced number of lines and this new approach., Comment: ICFHR 2018 Conference

Spatially-coupled LDPC codes are known to have excellent asymptotic properties. Much less is known regarding their finite-length performance. We propose a scaling law to predict the error probability of finite-length spatially-coupled ensembles when transmission takes place over the binary erasure channel. We discuss how the parameters of the scaling law are connected to fundamental quantities appearing in the asymptotic analysis of these ensembles and we verify that the predictions of the scaling law fit well to the data derived from simulations over a wide range of parameters. The ultimate goal of this line of research is to develop analytic tools for the design of spatially-coupled LDPC codes under practical constraints.

The dependence-testing (DT) bound is one of the strongest achievability bounds for the binary erasure channel (BEC) in the finite block length regime. In this paper, we show that maximum likelihood decoded regular low-density parity-check (LDPC) codes with at least 5 ones per column almost achieve the DT bound. Specifically, using quasi-regular LDPC codes with block length of 256 bits, we achieve a rate that is less than 1% away from the rate predicted by the DT bound for a word error rate below10 −3 . The results also indicate that the maximum-likelihood solution is computationally feasible for decoding block codes over the BEC with several hundred bits. Index Terms—LDPC codes, finite blocklength regime, ML de- coding, binary erasure channel, random coding.

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.

Proceeding of: 2017 IEEE International Symposium on Information Theory, Aachen, Germany, 25-30 June, 2017 In this paper, we analyze the tradeoff between coding rate and asymptotic performance of a class of generalized low-density parity-check (GLDPC) codes constructed by including a certain fraction of generalized constraint (GC) nodes in the graph. The rate of the GLDPC ensemble is bounded using classical results on linear block codes, namely Hamming bound and Varshamov bound. We also study the impact of the decoding method used at GC nodes. To incorporate both bounded-distance (BD) and Maximum Likelihood (ML) decoding at GC nodes into our analysis without having to resort on multi-edge type of degree distributions (DDs), we propose the probabilistic peeling decoder (P-PD) algorithm, which models the decoding step at every GC node as an instance of a Bernoulli random variable with a success probability that depends on the GC block code and its decoding algorithm. The P-PD asymptotic performance over the BEC can be efficiently predicted using standard techniques for LDPC codes such as density evolution (DE) or the differential equation method. Furthermore, for a class of GLDPC ensembles, we demonstrate that the simulated P-PD performance accurately predicts the actual performance of the GLPDC code. We illustrate our analysis for GLDPC code ensembles using (2, 6) and (2,15) base DDs. In all cases, we show that a large fraction of GC nodes is required to reduce the original gap to capacity. This work has been funded in part by the Spanish Ministerio de Economía y Competitividad and the Agencia Española de Investigación under Grant TEC2016-78434-C3-3-R (AEI/FEDER, EU) and by the Comunidad de Madrid in Spain under Grant S2103/ICE-2845. T. Koch has further received funding from the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme (grant agreement number 714161), from the 7th European Union Framework Programme under Grant 333680, and from the Spanish Ministerio de Economía y Competitividad under Grants TEC2013-41718-R and RYC-2014-16332. Pablo M. Olmos has further received funding from the Spanish Ministerio de Economía y Competitividad under Grant IJCI-2014-19150.

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.

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.

The equivalence of peeling decoding (PD) and Belief Propagation (BP) for low-density parity-check (LDPC) codes over the binary erasure channel is analyzed. Modifying the scheduling for PD, it is shown that exactly the same variable nodes (VNs) are resolved in every iteration than with BP. The decrease of erased VNs during the decoding process is analyzed instead of resolvable equations. This quantity can also be derived with density evolution, resulting in a drastic decrease in complexity. Finally, a scaling law using this quantity is established for spatially coupled LDPC codes.

We propose a novel encoding/transmission scheme called continuous chain (CC) transmission that is able to improve the finite-length performance of a system using spatially-coupled low-density parity-check (SC-LDPC) codes. In CC transmission, instead of transmitting a sequence of independent codewords from a terminated SC-LDPC code chain, we connect multiple chains in a layered format, where encoding, transmission, and decoding are now performed in a continuous fashion. The connections between chains are created at specific points, chosen to improve the finite-length performance of the code structure under iterative decoding. We describe the design of CC schemes for different SC-LDPC code ensembles constructed from protographs: a (J,K)-regular SC-LDPC code chain, a spatially-coupled repeat-accumulate (SC-RA) code, and a spatially-coupled accumulate-repeat-jagged-accumulate (SC- ARJA) code. In all cases, significant performance improvements are reported and, in addition, it is shown that using CC transmission only requires a small increase in decoding complexity and decoding delay with respect to a system employing a single SC-LDPC code chain for transmission., Comment: arXiv admin note: text overlap with arXiv:1402.7170

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.

This work provides a novel technological solution to jamming in wireless systems, particularly to remotely detect interfered communications in a cellular network. The new system is focused on the detection of a failure in a link between a base station and a fixed wireless terminal located in a residential or business area. It has an important impact in security systems based on wireless terminals to transmit an alarm to a central station. In these systems, non-authorised people can prevent the transmission of the alarm by using a short-range jammer. The main advantage of this proposal is that it is non-intrusive; that is, no modification is needed in the base station, and no protocol modification is performed in the terminal. The detection is implemented in an external unit developed on a software-defined radio platform. The novel system proposed is valid for any cellular system and operator. In this work, we focus on its implementation in the GSM/GPRS system to illustrate its benefits and outline the method for Universal Mobile Telecommunications System. We describe the results of some experiments where the system successfully detects the presence of a short-range jammer in a real scenario. Copyright © 2012 John Wiley & Sons, Ltd.

We aim at finding the comorbidity patterns of substance abuse, mood and personality disorders using the diagnoses from the National Epidemiologic Survey on Alcohol and Related Conditions database. To this end, we propose a novel Bayesian nonparametric latent feature model for categorical observations, based on the Indian buffet process, in which the latent variables can take values between 0 and 1. The proposed model has several interesting features for modeling psychiatric disorders. First, the latent features might be off, which allows distinguishing between the subjects who suffer a condition and those who do not. Second, the active latent features take positive values, which allows modeling the extent to which the patient has that condition. We also develop a new Markov chain Monte Carlo inference algorithm for our model that makes use of a nested expectation propagation procedure.

In this paper we consider distributed allocation problems with memory constraint limits. Firstly, we propose a tractable relaxation to the problem of optimal symmetric allocations from [1]. The approximated problem is based on the Q-error function, and its solution approaches the solution of the initial problem, as the number of storage nodes in the network grows. Secondly, exploiting this relaxation, we are able to formulate and to solve the problem for storage allocations for memory-limited DSS storing and arbitrary memory profiles. Finally, we discuss the extension to the case of multiple data objects, stored in the DSS., Submitted to IEEE GLOBECOM'15

The authors propose a novel method to evaluate the interference conditions in a cellular network. The method takes advantage of the signal strength and quality measurements available at a Base Station. Measurements from both up-link and down-link are jointly processed to remotely detect the presence of a medium-range frequency jammer and other situations involving abnormal interference levels, as a malfunctioning of the power control algorithm, a bad radio optimization and planning or an outer interference, among others. The proposed method can be adapted to any cellular system. In this paper we focus on its application to GSM/GPRS system. We include some experiments where real cell data recordings were analyzed.

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 analyze the performance of finite-length generalized LDPC (GLDPC) block codes constructed from protographs when transmission takes place over the binary erasure channel (BEC). A generalized peeling decoder is proposed and we derive a system of differential equations that gives the expected evolution of the graph degree distribution during decoding. We then show that the finite-length performance of a GLDPC code can be estimated by means of a simple scaling law, where a single scaling parameter represents the finite-length properties of the code. We also show that, as we consider stronger component codes, both the asymptotic threshold and the finite-length scaling parameter are improved.

Multi-output inference tasks, such as multi-label classification, have become increasingly important in recent years. A popular method for multi-label classification is classifier chains, in which the predictions of individual classifiers are cascaded along a chain, thus taking into account inter-label dependencies and improving the overall performance. Several varieties of classifier chain methods have been introduced, and many of them perform very competitively across a wide range of benchmark datasets. However, scalability limitations become apparent on larger datasets when modeling a fully-cascaded chain. In particular, the methods' strategies for discovering and modeling a good chain structure constitutes a mayor computational bottleneck. In this paper, we present the classifier trellis (CT) method for scalable multi-label classification. We compare CT with several recently proposed classifier chain methods to show that it occupies an important niche: it is highly competitive on standard multi-label problems, yet it can also scale up to thousands or even tens of thousands of labels., (accepted in Pattern Recognition)

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.

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. This work has been partly funded by the Spanish Ministry of Science and Innovation with the projects GRE3NSYST (TEC2011- 29006-C03-03) and ALCIT (TEC2012-38800-C03-01) and by the program CONSOLIDER-INGENIO 2010 under the project COMONSENS (CSD 2008- 00010). Publicado

The finite length performance of codes on graphs constructed by connecting spatially coupled low-density parity-check (SC-LDPC) code chains is analyzed. Successive (peeling) decoding is considered for the binary erasure channel (BEC). The evolution of the undecoded portion of the bipartite graph remaining after each iteration is analyzed as a dynamical system. It is shown that, in addition to superior iterative decoding thresholds, connected chain ensembles have better performance than single chain ensembles of the same rate and length.

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

Generalized low-density parity-check (GLDPC) codes are a class of LDPC codes in which the standard single parity check (SPC) constraints are replaced by constraints defined by a linear block code. These stronger constraints typically result in improved error floor performance, due to better minimum distance and trapping set properties, at a cost of some increased decoding complexity. In this paper, we study spatially coupled generalized low-density parity-check (SC-GLDPC) codes and present a comprehensive analysis of these codes, including: (1) an iterative decoding threshold analysis of SC-GLDPC code ensembles demonstrating capacity approaching thresholds via the threshold saturation effect; (2) an asymptotic analysis of the minimum distance and free distance properties of SC-GLDPC code ensembles, demonstrating that the ensembles are asymptotically good; and (3) an analysis of the finite-length scaling behavior of both GLDPC block codes and SC-GLDPC codes based on a peeling decoder (PD) operating on a binary erasure channel (BEC). Results are compared to GLDPC block codes, and the advantages and disadvantages of SC-GLDPC codes are discussed., Comment: Revised version submitted to the IEEE Transactions on Information Theory