## 2016 |

## Journal Articles |

Bocharova, Irina; i Fàbregas, Albert Guillén; Kudryashov, Boris; Martinez, Alfonso; Campo, Adria Tauste; Vazquez-Vilar, Gonzalo Multi-Class Source-Channel Coding (Journal Article) IEEE Transactions on Information Theory, 62 (9), pp. 5093 – 5104, 2016. (Abstract | Links | BibTeX | Tags: Channel Coding, Complexity theory, error probability, Indexes, Journal, Maximum likelihood decoding) @article{Bocharova2016, title = {Multi-Class Source-Channel Coding}, author = {Bocharova, Irina E. and Fàbregas, Albert Guillén i and Kudryashov, Boris D. and Martinez, Alfonso and Campo, Adria Tauste and Vazquez-Vilar, Gonzalo}, url = {http://arxiv.org/abs/1410.8714}, year = {2016}, date = {2016-09-01}, journal = {IEEE Transactions on Information Theory}, volume = {62}, number = {9}, pages = {5093 -- 5104}, abstract = {This paper studies an almost-lossless source-channel coding scheme in which source messages are assigned to different classes and encoded with a channel code that depends on the class index. The code performance is analyzed by means of random-coding error exponents and validated by simulation of a low-complexity implementation using existing source and channel codes. While each class code can be seen as a concatenation of a source code and a channel code, the overall performance improves on that of separate source-channel coding and approaches that of joint source-channel coding when the number of classes increases.}, keywords = {Channel Coding, Complexity theory, error probability, Indexes, Journal, Maximum likelihood decoding}, pubstate = {published}, tppubtype = {article} } This paper studies an almost-lossless source-channel coding scheme in which source messages are assigned to different classes and encoded with a channel code that depends on the class index. The code performance is analyzed by means of random-coding error exponents and validated by simulation of a low-complexity implementation using existing source and channel codes. While each class code can be seen as a concatenation of a source code and a channel code, the overall performance improves on that of separate source-channel coding and approaches that of joint source-channel coding when the number of classes increases. |

Stinner, Markus; Olmos, Pablo On the Waterfall Performance of Finite-Length SC-LDPC Codes Constructed From Protographs (Journal Article) IEEE Journal on Selected Areas in Communications, 34 (2), pp. 345–361, 2016, ISSN: 0733-8716. (Abstract | Links | BibTeX | Tags: Analytical models, capacity-achieving codes, Complexity theory, Couplings, Decoding, Encoding, finite-length analysis, Iterative decoding, Low-density parity-check (LDPC) codes, spatially coupled LDPC codes constructed from prot) @article{Stinner2016, title = {On the Waterfall Performance of Finite-Length SC-LDPC Codes Constructed From Protographs}, author = {Stinner, Markus and Olmos, Pablo M.}, url = {http://ieeexplore.ieee.org/lpdocs/epic03/wrapper.htm?arnumber=7339427}, doi = {10.1109/JSAC.2015.2504279}, issn = {0733-8716}, year = {2016}, date = {2016-02-01}, journal = {IEEE Journal on Selected Areas in Communications}, volume = {34}, number = {2}, pages = {345--361}, abstract = {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.}, keywords = {Analytical models, capacity-achieving codes, Complexity theory, Couplings, Decoding, Encoding, finite-length analysis, Iterative decoding, Low-density parity-check (LDPC) codes, spatially coupled LDPC codes constructed from prot}, pubstate = {published}, tppubtype = {article} } 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. |

## 2015 |

## Journal Articles |

Salamanca, Luis; Murillo-Fuentes, Juan; Olmos, Pablo; Perez-Cruz, Fernando; Verdu, Sergio Approaching the DT Bound Using Linear Codes in the Short Blocklength Regime (Journal Article) IEEE Communications Letters, 19 (2), pp. 123–126, 2015, ISSN: 1089-7798. (Abstract | Links | BibTeX | Tags: binary erasure channel, Channel Coding, Complexity theory, finite blocklength regime, LDPC codes, Maximum likelihood decoding, ML decoding, parity check codes, random coding) @article{Salamanca2014b, title = {Approaching the DT Bound Using Linear Codes in the Short Blocklength Regime}, author = {Salamanca, Luis and Murillo-Fuentes, Juan and Olmos, Pablo M. and Perez-Cruz, Fernando and Verdu, Sergio}, url = {http://ieeexplore.ieee.org/lpdocs/epic03/wrapper.htm?arnumber=6957577}, doi = {10.1109/LCOMM.2014.2371032}, issn = {1089-7798}, year = {2015}, date = {2015-02-01}, journal = {IEEE Communications Letters}, volume = {19}, number = {2}, pages = {123--126}, abstract = {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 paritycheck (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 below 103. The results also indicate that the maximum-likelihood solution is computationally feasible for decoding block codes over the BEC with several hundred bits.}, keywords = {binary erasure channel, Channel Coding, Complexity theory, finite blocklength regime, LDPC codes, Maximum likelihood decoding, ML decoding, parity check codes, random coding}, pubstate = {published}, tppubtype = {article} } 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 paritycheck (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 below 103. The results also indicate that the maximum-likelihood solution is computationally feasible for decoding block codes over the BEC with several hundred bits. |

## Inproceedings |

Santos, Irene; Murillo-Fuentes, Juan Jose; Olmos, Pablo Block Expectation Propagation Equalization for ISI Channels (Inproceeding) 2015 23rd European Signal Processing Conference (EUSIPCO), pp. 379–383, IEEE, Nice, 2015, ISBN: 978-0-9928-6263-3. (Abstract | Links | BibTeX | Tags: Approximation algorithms, Approximation methods, BCJR algorithm, channel equalization, Complexity theory, Decoding, Equalizers, expectation propagation, ISI, low complexity, Signal processing algorithms) @inproceedings{Santos2015, title = {Block Expectation Propagation Equalization for ISI Channels}, author = {Santos, Irene and Murillo-Fuentes, Juan Jose and Olmos, Pablo M.}, url = {http://ieeexplore.ieee.org/lpdocs/epic03/wrapper.htm?arnumber=7362409}, doi = {10.1109/EUSIPCO.2015.7362409}, isbn = {978-0-9928-6263-3}, year = {2015}, date = {2015-08-01}, booktitle = {2015 23rd European Signal Processing Conference (EUSIPCO)}, pages = {379--383}, publisher = {IEEE}, address = {Nice}, abstract = {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.}, keywords = {Approximation algorithms, Approximation methods, BCJR algorithm, channel equalization, Complexity theory, Decoding, Equalizers, expectation propagation, ISI, low complexity, Signal processing algorithms}, pubstate = {published}, tppubtype = {inproceedings} } 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. |

## 2014 |

## Journal Articles |

Salamanca, Luis; Murillo-Fuentes, Juan; Olmos, Pablo; Perez-Cruz, Fernando; Verdu, Sergio Near DT Bound Achieving Linear Codes in the Short Blocklength Regime (Journal Article) IEEE Communications Letters, PP (99), pp. 1–1, 2014, ISSN: 1089-7798. (Abstract | Links | BibTeX | Tags: binary erasure channel, Channel Coding, Complexity theory, finite blocklength regime, LDPC codes, Maximum likelihood decoding, ML decoding, parity check codes, random coding) @article{Salamanca2014, title = {Near DT Bound Achieving Linear Codes in the Short Blocklength Regime}, author = {Salamanca, Luis and Murillo-Fuentes, Juan and Olmos, Pablo M. and Perez-Cruz, Fernando and Verdu, Sergio}, url = {http://ieeexplore.ieee.org/lpdocs/epic03/wrapper.htm?arnumber=6957577}, issn = {1089-7798}, year = {2014}, date = {2014-01-01}, journal = {IEEE Communications Letters}, volume = {PP}, number = {99}, pages = {1--1}, abstract = {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 paritycheck (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 below 103. The results also indicate that the maximum-likelihood solution is computationally feasible for decoding block codes over the BEC with several hundred bits.}, keywords = {binary erasure channel, Channel Coding, Complexity theory, finite blocklength regime, LDPC codes, Maximum likelihood decoding, ML decoding, parity check codes, random coding}, pubstate = {published}, tppubtype = {article} } 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 paritycheck (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 below 103. The results also indicate that the maximum-likelihood solution is computationally feasible for decoding block codes over the BEC with several hundred bits. |

## Inproceedings |

Cespedes, Javier; Olmos, Pablo; Sanchez-Fernandez, Matilde; Perez-Cruz, Fernando Improved Performance of LDPC-Coded MIMO Systems with EP-based Soft-Decisions (Inproceeding) 2014 IEEE International Symposium on Information Theory, pp. 1997–2001, IEEE, Honolulu, 2014, ISBN: 978-1-4799-5186-4. (Abstract | Links | BibTeX | Tags: Approximation algorithms, Approximation methods, approximation theory, Channel Coding, channel decoder, communication complexity, complexity, Complexity theory, Detectors, encoding scheme, EP soft bit probability, EP-based soft decision, error statistics, expectation propagation, expectation-maximisation algorithm, expectation-propagation algorithm, Gaussian approximation, Gaussian channels, LDPC, LDPC coded MIMO system, Low Complexity receiver, MIMO, MIMO communication, MIMO communication systems, MIMO receiver, modern communication system, multiple input multiple output, parity check codes, per-antenna soft bit probability, posterior marginalization problem, posterior probability computation, QAM constellation, Quadrature amplitude modulation, radio receivers, signaling, spectral analysis, spectral efficiency maximization, symbol detection, telecommunication signalling, Vectors) @inproceedings{Cespedes2014b, title = {Improved Performance of LDPC-Coded MIMO Systems with EP-based Soft-Decisions}, author = {Cespedes, Javier and Olmos, Pablo M. and Sanchez-Fernandez, Matilde and Perez-Cruz, Fernando}, url = {http://ieeexplore.ieee.org/articleDetails.jsp?arnumber=6875183}, isbn = {978-1-4799-5186-4}, year = {2014}, date = {2014-01-01}, booktitle = {2014 IEEE International Symposium on Information Theory}, pages = {1997--2001}, publisher = {IEEE}, address = {Honolulu}, abstract = {Modern communications systems use efficient encoding schemes, multiple-input multiple-output (MIMO) and high-order QAM constellations for maximizing spectral efficiency. However, as the dimensions of the system grow, the design of efficient and low-complexity MIMO receivers possesses technical challenges. Symbol detection can no longer rely on conventional approaches for posterior probability computation due to complexity. Marginalization of this posterior to obtain per-antenna soft-bit probabilities to be fed to a channel decoder is computationally challenging when realistic signaling is used. In this work, we propose to use Expectation Propagation (EP) algorithm to provide an accurate low-complexity Gaussian approximation to the posterior, easily solving the posterior marginalization problem. EP soft-bit probabilities are used in an LDPC-coded MIMO system, achieving outstanding performance improvement compared to similar approaches in the literature for low-complexity LDPC MIMO decoding.}, keywords = {Approximation algorithms, Approximation methods, approximation theory, Channel Coding, channel decoder, communication complexity, complexity, Complexity theory, Detectors, encoding scheme, EP soft bit probability, EP-based soft decision, error statistics, expectation propagation, expectation-maximisation algorithm, expectation-propagation algorithm, Gaussian approximation, Gaussian channels, LDPC, LDPC coded MIMO system, Low Complexity receiver, MIMO, MIMO communication, MIMO communication systems, MIMO receiver, modern communication system, multiple input multiple output, parity check codes, per-antenna soft bit probability, posterior marginalization problem, posterior probability computation, QAM constellation, Quadrature amplitude modulation, radio receivers, signaling, spectral analysis, spectral efficiency maximization, symbol detection, telecommunication signalling, Vectors}, pubstate = {published}, tppubtype = {inproceedings} } Modern communications systems use efficient encoding schemes, multiple-input multiple-output (MIMO) and high-order QAM constellations for maximizing spectral efficiency. However, as the dimensions of the system grow, the design of efficient and low-complexity MIMO receivers possesses technical challenges. Symbol detection can no longer rely on conventional approaches for posterior probability computation due to complexity. Marginalization of this posterior to obtain per-antenna soft-bit probabilities to be fed to a channel decoder is computationally challenging when realistic signaling is used. In this work, we propose to use Expectation Propagation (EP) algorithm to provide an accurate low-complexity Gaussian approximation to the posterior, easily solving the posterior marginalization problem. EP soft-bit probabilities are used in an LDPC-coded MIMO system, achieving outstanding performance improvement compared to similar approaches in the literature for low-complexity LDPC MIMO decoding. |

## 2013 |

## Journal Articles |

Olmos, Pablo; Murillo-Fuentes, Juan Jose; Perez-Cruz, Fernando Tree-Structure Expectation Propagation for LDPC Decoding Over the BEC (Journal Article) IEEE Transactions on Information Theory, 59 (6), pp. 3354–3377, 2013, ISSN: 0018-9448. (Abstract | Links | BibTeX | Tags: 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 = {Olmos, Pablo M. and Murillo-Fuentes, Juan Jose and Perez-Cruz, Fernando}, 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; Perez-Cruz, Fernando; Murillo-Fuentes, Juan Jose Tree-Structured Expectation Propagation for LDPC Decoding over BMS Channels (Journal Article) IEEE Transactions on Communications, 61 (10), pp. 4086–4095, 2013, ISSN: 0090-6778. (Abstract | Links | BibTeX | Tags: 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 = {Salamanca, Luis and Olmos, Pablo M. and Perez-Cruz, Fernando and Murillo-Fuentes, Juan Jose}, 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; Murillo-Fuentes, Juan Jose; Perez-Cruz, Fernando Tree Expectation Propagation for ML Decoding of LDPC Codes over the BEC (Journal Article) 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 = {Salamanca, Luis and Olmos, Pablo M. and Murillo-Fuentes, Juan Jose and Perez-Cruz, Fernando}, 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. |

## Inproceedings |

Salamanca, Luis; Murillo-Fuentes, Juan Jose; Olmos, Pablo; Perez-Cruz, Fernando Improving the BP Estimate over the AWGN Channel Using Tree-Structured Expectation Propagation (Inproceeding) 2013 IEEE International Symposium on Information Theory, pp. 2990–2994, IEEE, Istanbul, 2013, ISSN: 2157-8095. (Abstract | Links | BibTeX | Tags: Approximation algorithms, Approximation methods, AWGN channels, BEC, belief propagation decoding, BI-AWGN channel, binary additive white Gaussian noise channel, binary erasure channel, BP estimation, Channel Coding, Complexity theory, error rate reduction, error statistics, Expectation, finite-length codes, Iterative decoding, LDPC codes, LDPC decoding, low-density parity-check decoding, Maximum likelihood decoding, parity check codes, posterior distribution, Propagation, TEP algorithm, tree-structured expectation propagation algorithm, trees (mathematics)) @inproceedings{Salamanca2013, title = {Improving the BP Estimate over the AWGN Channel Using Tree-Structured Expectation Propagation}, author = {Salamanca, Luis and Murillo-Fuentes, Juan Jose and Olmos, Pablo M. and Perez-Cruz, Fernando}, url = {http://ieeexplore.ieee.org/lpdocs/epic03/wrapper.htm?arnumber=6620774}, issn = {2157-8095}, year = {2013}, date = {2013-01-01}, booktitle = {2013 IEEE International Symposium on Information Theory}, pages = {2990--2994}, publisher = {IEEE}, address = {Istanbul}, abstract = {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.}, keywords = {Approximation algorithms, Approximation methods, AWGN channels, BEC, belief propagation decoding, BI-AWGN channel, binary additive white Gaussian noise channel, binary erasure channel, BP estimation, Channel Coding, Complexity theory, error rate reduction, error statistics, Expectation, finite-length codes, Iterative decoding, LDPC codes, LDPC decoding, low-density parity-check decoding, Maximum likelihood decoding, parity check codes, posterior distribution, Propagation, TEP algorithm, tree-structured expectation propagation algorithm, trees (mathematics)}, pubstate = {published}, tppubtype = {inproceedings} } 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. |

## 2012 |

## Journal Articles |

Olmos, Pablo; Salamanca, Luis; Murillo-Fuentes, Juan Jose; Perez-Cruz, Fernando On the Design of LDPC-Convolutional Ensembles Using the TEP Decoder (Journal Article) IEEE Communications Letters, 16 (5), pp. 726–729, 2012, ISSN: 1089-7798. (Abstract | Links | BibTeX | Tags: belief propagation decoding, binary erasure channel, channel capacity, Complexity theory, convolutional codes, convolutional LDPC codes, Decoding, design, Error analysis, finite-length analysis, Iterative decoding, LDPC-convolutional ensemble design, LDPCC code decoding, low-density parity-check convolutional code, parity check codes, tree-expectation propagation decoder, tree-structured expectation propagation, window-sliding scheme) @article{Olmos2012b, title = {On the Design of LDPC-Convolutional Ensembles Using the TEP Decoder}, author = {Olmos, Pablo M. and Salamanca, Luis and Murillo-Fuentes, Juan Jose and Perez-Cruz, Fernando}, url = {http://ieeexplore.ieee.org/lpdocs/epic03/wrapper.htm?arnumber=6168872}, issn = {1089-7798}, year = {2012}, date = {2012-01-01}, journal = {IEEE Communications Letters}, volume = {16}, number = {5}, pages = {726--729}, abstract = {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.}, keywords = {belief propagation decoding, binary erasure channel, channel capacity, Complexity theory, convolutional codes, convolutional LDPC codes, Decoding, design, Error analysis, finite-length analysis, Iterative decoding, LDPC-convolutional ensemble design, LDPCC code decoding, low-density parity-check convolutional code, parity check codes, tree-expectation propagation decoder, tree-structured expectation propagation, window-sliding scheme}, pubstate = {published}, tppubtype = {article} } 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. |

## Inproceedings |

Olmos, Pablo; Perez-Cruz, Fernando; Salamanca, Luis; Murillo-Fuentes, Juan Jose Finite-Length Performance of Spatially-Coupled LDPC Codes under TEP Decoding (Inproceeding) 2012 IEEE Information Theory Workshop, pp. 1–6, IEEE, Lausanne, 2012, ISBN: 978-1-4673-0223-4. (Links | BibTeX | Tags: asymptotic limit, belief propagation decoding, Complexity theory, convolutional codes, convolutional LDPC codes, Decoding, decoding latency, decoding threshold, erasure channel, Error analysis, error rates, finite-length analysis, finite-length performance, maximum a posteriori threshold, maximum likelihood estimation, parity check codes, regular sparse codes, spatially-coupled LDPC codes, TEP decoding, tree-structured expectation propagation, underlying regular code, very large code length, window-sliding scheme) @inproceedings{Olmos2012, title = {Finite-Length Performance of Spatially-Coupled LDPC Codes under TEP Decoding}, author = {Olmos, Pablo M. and Perez-Cruz, Fernando and Salamanca, Luis and Murillo-Fuentes, Juan Jose}, url = {http://ieeexplore.ieee.org/articleDetails.jsp?arnumber=6404722}, isbn = {978-1-4673-0223-4}, year = {2012}, date = {2012-01-01}, booktitle = {2012 IEEE Information Theory Workshop}, pages = {1--6}, publisher = {IEEE}, address = {Lausanne}, keywords = {asymptotic limit, belief propagation decoding, Complexity theory, convolutional codes, convolutional LDPC codes, Decoding, decoding latency, decoding threshold, erasure channel, Error analysis, error rates, finite-length analysis, finite-length performance, maximum a posteriori threshold, maximum likelihood estimation, parity check codes, regular sparse codes, spatially-coupled LDPC codes, TEP decoding, tree-structured expectation propagation, underlying regular code, very large code length, window-sliding scheme}, pubstate = {published}, tppubtype = {inproceedings} } |

## 2011 |

## Journal Articles |

Vazquez, Manuel; Miguez, Joaquin A Per-Survivor Processing Receiver for MIMO Transmission Systems With One Unknown Channel Order Per Output (Journal Article) IEEE Transactions on Vehicular Technology, 60 (9), pp. 4415–4426, 2011, ISSN: 0018-9545. (Abstract | Links | BibTeX | Tags: Channel estimation, communication channel, Complexity theory, dynamic programming, frequency-selective MIMO channel, frequency-selective multiple-input multiple-output, maximum likelihood detection, maximum likelihood sequence detection, maximum likelihood sequence estimation, MIMO, MIMO channel impulse response coefficient, MIMO communication, MIMO transmission system, multipath channels, mutiple-input–multiple-output (MIMO), per-survivor processing receiver, Receiving antennas, Signal processing algorithms, time-selective MIMO channel, Transmitting antennas, Viterbi algorithm) @article{Vazquez2011, title = {A Per-Survivor Processing Receiver for MIMO Transmission Systems With One Unknown Channel Order Per Output}, author = {Vazquez, Manuel A. and Miguez, Joaquin}, url = {http://www.tsc.uc3m.es/~jmiguez/papers/P31_2011_A Per-Survivor Processing Receiver for MIMO Transmission Systems With One Unknown Channel Order Per Output.pdf http://ieeexplore.ieee.org/lpdocs/epic03/wrapper.htm?arnumber=6032763}, issn = {0018-9545}, year = {2011}, date = {2011-01-01}, journal = {IEEE Transactions on Vehicular Technology}, volume = {60}, number = {9}, pages = {4415--4426}, abstract = {The order of a communications channel is the length of its impulse response. Recently, several works have tackled the problem of estimating the order of a frequency-selective multiple-input-multiple-output (MIMO) channel. However, all of them consider a single order, despite the fact that a MIMO channel comprises several subchannels (specifically, as many as the number of inputs times the number of outputs), each one possibly with its own order. In this paper, we introduce an algorithm for maximum-likelihood sequence detection (MLSD) in frequency- and time-selective MIMO channels that incorporates full estimation of the MIMO channel impulse response (CIR) coefficients, including one channel order per output. Simulation results following the analytical derivation of the algorithm suggest that the proposed receiver can achieve significant improvements in performance when transmitting through a MIMO channel that effectively comprises subchannels of different lengths.}, keywords = {Channel estimation, communication channel, Complexity theory, dynamic programming, frequency-selective MIMO channel, frequency-selective multiple-input multiple-output, maximum likelihood detection, maximum likelihood sequence detection, maximum likelihood sequence estimation, MIMO, MIMO channel impulse response coefficient, MIMO communication, MIMO transmission system, multipath channels, mutiple-input–multiple-output (MIMO), per-survivor processing receiver, Receiving antennas, Signal processing algorithms, time-selective MIMO channel, Transmitting antennas, Viterbi algorithm}, pubstate = {published}, tppubtype = {article} } The order of a communications channel is the length of its impulse response. Recently, several works have tackled the problem of estimating the order of a frequency-selective multiple-input-multiple-output (MIMO) channel. However, all of them consider a single order, despite the fact that a MIMO channel comprises several subchannels (specifically, as many as the number of inputs times the number of outputs), each one possibly with its own order. In this paper, we introduce an algorithm for maximum-likelihood sequence detection (MLSD) in frequency- and time-selective MIMO channels that incorporates full estimation of the MIMO channel impulse response (CIR) coefficients, including one channel order per output. Simulation results following the analytical derivation of the algorithm suggest that the proposed receiver can achieve significant improvements in performance when transmitting through a MIMO channel that effectively comprises subchannels of different lengths. |

## Inproceedings |

Olmos, Pablo; Murillo-Fuentes, Juan Jose; Perez-Cruz, Fernando Capacity Achieving LDPC Ensembles for the TEP Decoder in Erasure Channels (Inproceeding) 2011 IEEE International Symposium on Information Theory Proceedings, pp. 2398–2402, IEEE, St. Petersburg, 2011, ISSN: 2157-8095. (Abstract | Links | BibTeX | Tags: BP threshold, Complexity theory, Decoding, Differential equations, erasure channels, fixed-rate code, Iterative decoding, LDPC, low-density parity-check codes, MAP capacity, MAP threshold, optimisation, Optimization, optimization problem, parity check codes, TEP decoder, tree-expectation propagation decoder) @inproceedings{Olmos2011b, title = {Capacity Achieving LDPC Ensembles for the TEP Decoder in Erasure Channels}, author = {Olmos, Pablo M. and Murillo-Fuentes, Juan Jose and Perez-Cruz, Fernando}, url = {http://ieeexplore.ieee.org/lpdocs/epic03/wrapper.htm?arnumber=6033993}, issn = {2157-8095}, year = {2011}, date = {2011-01-01}, booktitle = {2011 IEEE International Symposium on Information Theory Proceedings}, pages = {2398--2402}, publisher = {IEEE}, address = {St. Petersburg}, abstract = {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.}, keywords = {BP threshold, Complexity theory, Decoding, Differential equations, erasure channels, fixed-rate code, Iterative decoding, LDPC, low-density parity-check codes, MAP capacity, MAP threshold, optimisation, Optimization, optimization problem, parity check codes, TEP decoder, tree-expectation propagation decoder}, pubstate = {published}, tppubtype = {inproceedings} } 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. |