2021
Olmos, Pablo M; Liu, Yanfang; Mitchell, David G M
Low-Density Parity-Check (LDPC) Codes for 5G Communications Capítulo de libro
En: Wiley 5G Ref, pp. 1-23, American Cancer Society, 2021, ISBN: 9781119471509.
Resumen | Enlaces | BibTeX | Etiquetas: 5G, Channel Coding, FPGA, hardware implementation, LDPC codes, pipeline architecture, protographs, quasi-cyclic LDPC codes
@inbook{doi,
title = {Low-Density Parity-Check (LDPC) Codes for 5G Communications},
author = {Pablo M Olmos and Yanfang Liu and David G M Mitchell},
url = {https://onlinelibrary.wiley.com/doi/abs/10.1002/9781119471509.w5GRef013},
doi = {https://doi.org/10.1002/9781119471509.w5GRef013},
isbn = {9781119471509},
year = {2021},
date = {2021-01-01},
urldate = {2021-01-01},
booktitle = {Wiley 5G Ref},
pages = {1-23},
publisher = {American Cancer Society},
abstract = {Abstract In this article, we describe the fundamental advances in low-density parity-check (LDPC) codes over the last two decades with special emphasis on the class of LDPC codes selected for the 5G new radio standard. We present structured protograph and quasi-cyclic LDPC codes, which are convenient for hardware implementation. The 5G LDPC codes are then reviewed in detail. Hardware considerations regarding the implementation of the encoders and decoders of 5G LDPC codes are also discussed. We conclude the article by presenting three of the more promising extensions of LDPC codes known to date (generalized LDPC codes, nonbinary LDPC codes, and spatially coupled LDPC codes), which could potentially replace conventional LDPC codes in future communication standards.},
keywords = {5G, Channel Coding, FPGA, hardware implementation, LDPC codes, pipeline architecture, protographs, quasi-cyclic LDPC codes},
pubstate = {published},
tppubtype = {inbook}
}
Abstract In this article, we describe the fundamental advances in low-density parity-check (LDPC) codes over the last two decades with special emphasis on the class of LDPC codes selected for the 5G new radio standard. We present structured protograph and quasi-cyclic LDPC codes, which are convenient for hardware implementation. The 5G LDPC codes are then reviewed in detail. Hardware considerations regarding the implementation of the encoders and decoders of 5G LDPC codes are also discussed. We conclude the article by presenting three of the more promising extensions of LDPC codes known to date (generalized LDPC codes, nonbinary LDPC codes, and spatially coupled LDPC codes), which could potentially replace conventional LDPC codes in future communication standards.
2015
Salamanca, Luis; Murillo-Fuentes, Juan José; Olmos, Pablo M; Perez-Cruz, Fernando; Verdu, Sergio
Approaching the DT Bound Using Linear Codes in the Short Blocklength Regime Artículo de revista
En: IEEE Communications Letters, vol. 19, no 2, pp. 123–126, 2015, ISSN: 1089-7798.
Resumen | Enlaces | BibTeX | Etiquetas: binary erasure channel, Channel Coding, Complexity theory, finite blocklength regime, LDPC codes, Maximum likelihood decoding, ML decoding, parity check codes, random coding
@article{Salamanca2014bb,
title = {Approaching the DT Bound Using Linear Codes in the Short Blocklength Regime},
author = {Luis Salamanca and Juan Jos\'{e} Murillo-Fuentes and Pablo M Olmos and Fernando Perez-Cruz and Sergio Verdu},
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.
2014
Salamanca, Luis; Murillo-Fuentes, Juan José; Olmos, Pablo M; Perez-Cruz, Fernando; Verdu, Sergio
Near DT Bound Achieving Linear Codes in the Short Blocklength Regime Artículo de revista
En: IEEE Communications Letters, vol. PP, no 99, pp. 1–1, 2014, ISSN: 1089-7798.
Resumen | Enlaces | BibTeX | Etiquetas: binary erasure channel, Channel Coding, Complexity theory, finite blocklength regime, LDPC codes, Maximum likelihood decoding, ML decoding, parity check codes, random coding
@article{Salamanca2014bb,
title = {Near DT Bound Achieving Linear Codes in the Short Blocklength Regime},
author = {Luis Salamanca and Juan Jos\'{e} Murillo-Fuentes and Pablo M Olmos and Fernando Perez-Cruz and Sergio Verdu},
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.
2013
Salamanca, Luis; Murillo-Fuentes, Juan Jose; Olmos, Pablo M; Perez-Cruz, Fernando
Improving the BP Estimate over the AWGN Channel Using Tree-Structured Expectation Propagation Proceedings Article
En: 2013 IEEE International Symposium on Information Theory, pp. 2990–2994, IEEE, Istanbul, 2013, ISSN: 2157-8095.
Resumen | Enlaces | BibTeX | Etiquetas: 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 = {Luis Salamanca and Juan Jose Murillo-Fuentes and Pablo M Olmos and Fernando Perez-Cruz},
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.
Olmos, Pablo M; Murillo-Fuentes, Juan Jose; Perez-Cruz, Fernando
Tree-Structure Expectation Propagation for LDPC Decoding Over the BEC Artículo de revista
En: IEEE Transactions on Information Theory, vol. 59, no 6, pp. 3354–3377, 2013, ISSN: 0018-9448.
Resumen | Enlaces | BibTeX | Etiquetas: Algorithm design and analysis, Approximation algorithms, Approximation methods, BEC, belief propagation, Belief-propagation (BP), binary erasure channel, Complexity theory, decode low-density parity-check codes, Decoding, discrete memoryless channels, expectation propagation, finite-length analysis, LDPC codes, LDPC decoding, parity check codes, peeling-type algorithm, Probability density function, random graph evolution, Tanner graph, tree-structure expectation propagation
@article{Olmos2013b,
title = {Tree-Structure Expectation Propagation for LDPC Decoding Over the BEC},
author = {Pablo M Olmos and Juan Jose Murillo-Fuentes and Fernando Perez-Cruz},
url = {http://ieeexplore.ieee.org/lpdocs/epic03/wrapper.htm?arnumber=6451276},
issn = {0018-9448},
year = {2013},
date = {2013-01-01},
journal = {IEEE Transactions on Information Theory},
volume = {59},
number = {6},
pages = {3354--3377},
abstract = {We present the tree-structure expectation propagation (Tree-EP) algorithm to decode low-density parity-check (LDPC) codes over discrete memoryless channels (DMCs). Expectation propagation generalizes belief propagation (BP) in two ways. First, it can be used with any exponential family distribution over the cliques in the graph. Second, it can impose additional constraints on the marginal distributions. We use this second property to impose pairwise marginal constraints over pairs of variables connected to a check node of the LDPC code's Tanner graph. Thanks to these additional constraints, the Tree-EP marginal estimates for each variable in the graph are more accurate than those provided by BP. We also reformulate the Tree-EP algorithm for the binary erasure channel (BEC) as a peeling-type algorithm (TEP) and we show that the algorithm has the same computational complexity as BP and it decodes a higher fraction of errors. We describe the TEP decoding process by a set of differential equations that represents the expected residual graph evolution as a function of the code parameters. The solution of these equations is used to predict the TEP decoder performance in both the asymptotic regime and the finite-length regimes over the BEC. While the asymptotic threshold of the TEP decoder is the same as the BP decoder for regular and optimized codes, we propose a scaling law for finite-length LDPC codes, which accurately approximates the TEP improved performance and facilitates its optimization.},
keywords = {Algorithm design and analysis, Approximation algorithms, Approximation methods, BEC, belief propagation, Belief-propagation (BP), binary erasure channel, Complexity theory, decode low-density parity-check codes, Decoding, discrete memoryless channels, expectation propagation, finite-length analysis, LDPC codes, LDPC decoding, parity check codes, peeling-type algorithm, Probability density function, random graph evolution, Tanner graph, tree-structure expectation propagation},
pubstate = {published},
tppubtype = {article}
}
We present the tree-structure expectation propagation (Tree-EP) algorithm to decode low-density parity-check (LDPC) codes over discrete memoryless channels (DMCs). Expectation propagation generalizes belief propagation (BP) in two ways. First, it can be used with any exponential family distribution over the cliques in the graph. Second, it can impose additional constraints on the marginal distributions. We use this second property to impose pairwise marginal constraints over pairs of variables connected to a check node of the LDPC code's Tanner graph. Thanks to these additional constraints, the Tree-EP marginal estimates for each variable in the graph are more accurate than those provided by BP. We also reformulate the Tree-EP algorithm for the binary erasure channel (BEC) as a peeling-type algorithm (TEP) and we show that the algorithm has the same computational complexity as BP and it decodes a higher fraction of errors. We describe the TEP decoding process by a set of differential equations that represents the expected residual graph evolution as a function of the code parameters. The solution of these equations is used to predict the TEP decoder performance in both the asymptotic regime and the finite-length regimes over the BEC. While the asymptotic threshold of the TEP decoder is the same as the BP decoder for regular and optimized codes, we propose a scaling law for finite-length LDPC codes, which accurately approximates the TEP improved performance and facilitates its optimization.
Salamanca, Luis; Olmos, Pablo M; Murillo-Fuentes, Juan Jose; Perez-Cruz, Fernando
Tree Expectation Propagation for ML Decoding of LDPC Codes over the BEC Artículo de revista
En: IEEE Transactions on Communications, vol. 61, no 2, pp. 465–473, 2013, ISSN: 0090-6778.
Resumen | Enlaces | BibTeX | Etiquetas: approximate inference, Approximation algorithms, Approximation methods, BEC, binary codes, binary erasure channel, code graph, Complexity theory, equivalent complexity, Gaussian elimination method, Gaussian processes, generalized tree-structured expectation propagatio, graphical message-passing procedure, graphical models, LDPC codes, Maximum likelihood decoding, maximum likelihood solution, ML decoding, parity check codes, peeling decoder, tree expectation propagation, tree graph, Tree graphs, tree-structured expectation propagation, tree-structured expectation propagation decoder, trees (mathematics)
@article{Salamanca2013b,
title = {Tree Expectation Propagation for ML Decoding of LDPC Codes over the BEC},
author = {Luis Salamanca and Pablo M Olmos and Juan Jose Murillo-Fuentes and Fernando Perez-Cruz},
url = {http://ieeexplore.ieee.org/lpdocs/epic03/wrapper.htm?arnumber=6384612},
issn = {0090-6778},
year = {2013},
date = {2013-01-01},
journal = {IEEE Transactions on Communications},
volume = {61},
number = {2},
pages = {465--473},
abstract = {We propose a decoding algorithm for LDPC codes that achieves the maximum likelihood (ML) solution over the binary erasure channel (BEC). In this channel, the tree-structured expectation propagation (TEP) decoder improves the peeling decoder (PD) by processing check nodes of degree one and two. However, it does not achieve the ML solution, as the tree structure of the TEP allows only for approximate inference. In this paper, we provide the procedure to construct the structure needed for exact inference. This algorithm, denoted as generalized tree-structured expectation propagation (GTEP), modifies the code graph by recursively eliminating any check node and merging this information in the remaining graph. The GTEP decoder upon completion either provides the unique ML solution or a tree graph in which the number of parent nodes indicates the multiplicity of the ML solution. We also explain the algorithm as a Gaussian elimination method, relating the GTEP to other ML solutions. Compared to previous approaches, it presents an equivalent complexity, it exhibits a simpler graphical message-passing procedure and, most interesting, the algorithm can be generalized to other channels.},
keywords = {approximate inference, Approximation algorithms, Approximation methods, BEC, binary codes, binary erasure channel, code graph, Complexity theory, equivalent complexity, Gaussian elimination method, Gaussian processes, generalized tree-structured expectation propagatio, graphical message-passing procedure, graphical models, LDPC codes, Maximum likelihood decoding, maximum likelihood solution, ML decoding, parity check codes, peeling decoder, tree expectation propagation, tree graph, Tree graphs, tree-structured expectation propagation, tree-structured expectation propagation decoder, trees (mathematics)},
pubstate = {published},
tppubtype = {article}
}
We propose a decoding algorithm for LDPC codes that achieves the maximum likelihood (ML) solution over the binary erasure channel (BEC). In this channel, the tree-structured expectation propagation (TEP) decoder improves the peeling decoder (PD) by processing check nodes of degree one and two. However, it does not achieve the ML solution, as the tree structure of the TEP allows only for approximate inference. In this paper, we provide the procedure to construct the structure needed for exact inference. This algorithm, denoted as generalized tree-structured expectation propagation (GTEP), modifies the code graph by recursively eliminating any check node and merging this information in the remaining graph. The GTEP decoder upon completion either provides the unique ML solution or a tree graph in which the number of parent nodes indicates the multiplicity of the ML solution. We also explain the algorithm as a Gaussian elimination method, relating the GTEP to other ML solutions. Compared to previous approaches, it presents an equivalent complexity, it exhibits a simpler graphical message-passing procedure and, most interesting, the algorithm can be generalized to other channels.
2011
Salamanca, Luis; Olmos, Pablo M; Murillo-Fuentes, Juan Jose; Perez-Cruz, Fernando
MAP Decoding for LDPC Codes over the Binary Erasure Channel Proceedings Article
En: 2011 IEEE Information Theory Workshop, pp. 145–149, IEEE, Paraty, 2011, ISBN: 978-1-4577-0437-6.
Resumen | Enlaces | BibTeX | Etiquetas: binary erasure channel, Channel Coding, computational complexity, Decoding, generalized peeling decoder, generalized tree-structured expectation propagatio, graphical models, Iterative decoding, LDPC codes, MAP decoding, MAP decoding algorithm, Maximum likelihood decoding, parity check codes, TEP decoder, tree graph theory, Tree graphs, tree-structured expectation propagation, trees (mathematics)
@inproceedings{Salamanca2011a,
title = {MAP Decoding for LDPC Codes over the Binary Erasure Channel},
author = {Luis Salamanca and Pablo M Olmos and Juan Jose Murillo-Fuentes and Fernando Perez-Cruz},
url = {http://ieeexplore.ieee.org/lpdocs/epic03/wrapper.htm?arnumber=6089364},
isbn = {978-1-4577-0437-6},
year = {2011},
date = {2011-01-01},
booktitle = {2011 IEEE Information Theory Workshop},
pages = {145--149},
publisher = {IEEE},
address = {Paraty},
abstract = {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.},
keywords = {binary erasure channel, Channel Coding, computational complexity, Decoding, generalized peeling decoder, generalized tree-structured expectation propagatio, graphical models, Iterative decoding, LDPC codes, MAP decoding, MAP decoding algorithm, Maximum likelihood decoding, parity check codes, TEP decoder, tree graph theory, Tree graphs, tree-structured expectation propagation, trees (mathematics)},
pubstate = {published},
tppubtype = {inproceedings}
}
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.