Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

An Absorbing Set Analysis of Quantized LDPC Decoders

Homayoon Hatami

Published Nov 16, 2022• 0 citations
Publisher

Abstract

The performance of low-density parity-check (LDPC) codes at high signal-to- noise ratios (SNRs) is known to be limited by the presence of certain sub-graphs that exist in the Tanner graph representation of the code, for example trapping sets and absorbing sets. This dissertation derives a lower bound on the frame error rate (FER) of any LDPC code containing a given problematic sub-graph, assuming a particular iterative message passing (MP) decoder and decoder quantization. A crucial aspect of the lower bound is that it is code-independent, in the sense that it can be derived based only on a problematic sub-graph and then applied to any code containing it. Due to the complexity of evaluating the exact bound, assumptions are proposed to approximate it, from which we can estimate decoder performance. For LDPC codes, the attenuated min-sum algorithm (AMSA) and the offset min- sum algorithm (OMSA) are known to outperform the conventional min-sum algorithm (MSA) at low SNRs, i.e., in the waterfall region of the FER curve. This dis- sertation demonstrates that, for quantized LDPC decoders, the AMSA and OMSA underperform the MSA at high SNRs, i.e., in the error floor region of the FER curve, and that the MSA, AMSA, and OMSA all suffer from a relatively high error floor. Therefore, we introduce a novel modification of the MSA for quantized decoding of LDPC codes, called the threshold attenuated min-sum algorithm (TAMSA) (or the threshold offset min-sum algorithm (TOMSA)) with the aim of outperforming the MSA, AMSA, and OMSA at both low and high SNRs. The new decoding algorithm is designed based on the common assumption that trapping sets are the major cause of the error floor for quantized LDPC decoders, and it is shown to reduce the error probability associated with these problematic graphic objects. The lower bound analysis tool noted above is then used to verify the effectiveness of the new TAMSA (TOMSA) and also to assist in finding its optimum design parameters. We also show that the implementation complexity of the TAMSA (TOMSA) is only slightly higher than that of the AMSA or OMSA. Finally, we extend the lower bound to sliding window (SW) decoding of spatially coupled LDPC (SC-LDPC) codes. Additionally, we show that the performance of the TAMSA (TOMSA) is better than that of the MSA, AMSA, and OMSA for SW.

DOI
10.7274/zc77sn03t6n

Related papers

A Modified Min-Sum Algorithm for Quantized LDPC Decoders

Homayoon Hatami, David G. M. Mitchell, Daniel J. Costello +1 more

It is well known that for decoding low-density parity-check (LDPC) codes, the attenuated min-sum algorithm (AMSA) and the offset min-sum algorithm (OMSA) can outperform the conventional min-sum algorithm (MSA) at low signal-to-noise-ratios (SNRs). In this paper, we demonstrate that, for quantized LDPC decoders, although the MSA achieves better high SNR performance than the AMSA and OMSA, each of the MSA, AMSA, and OMSA all suffer from a relatively high error floor. Therefore, we propose a novel modification of the MSA for decoding quantized LDPC codes with the aim of lowering the error floor. Compared to the quantized MSA, the proposed modification is also helpful at low SNRs, where it matches the waterfall performance of the quantized AMSA and OMSA. The new algorithm is designed based on the assumption that trapping/absorbing sets (or other problematic graphical objects) are the major cause of the error floor for quantized LDPC decoders, and it aims to reduce the probability that these problematic objects lead to decoding errors.

IEEE International Symposium on Information Theory (ISIT)•Jul 1, 2019•2 citations

Performance Bounds and Estimates for Quantized LDPC Decoders

Homayoon Hatami, David G. M. Mitchell, Daniel J. Costello +1 more

The performance of low-density parity-check (LDPC) codes at high signal-to-noise ratios (SNRs) is known to be limited by the presence of certain sub-graphs that exist in the Tanner graph representation of the code, for example trapping sets and absorbing sets. This paper derives a lower bound on the frame error rate (FER) of any LDPC code containing a given problematic sub-graph, assuming a particular message passing decoder and decoder quantization. A crucial aspect of the lower bound is that it is code-independent, in the sense that it can be derived based only on a problematic sub-graph and then applied to any code containing it. Due to the complexity of evaluating the exact bound, assumptions are proposed to approximate it, from which we can estimate decoder performance. Simulated results obtained for both the quantized sum-product algorithm (SPA) and the quantized min-sum algorithm (MSA) are shown to be consistent with the approximate bound and the corresponding performance estimates. Different classes of LDPC codes, including both structured and randomly constructed codes, are used to demonstrate the robustness of the approach.

arXiv:1911.02762•IEEE Transactions on Communications•Nov 13, 2019•16 citations

A Threshold-Based Min-Sum Algorithm to Lower the Error Floors of Quantized LDPC Decoders

Homayoon Hatami, David G. M. Mitchell, Daniel J. Costello +1 more

For decoding low-density parity-check (LDPC) codes, the attenuated min-sum algorithm (AMSA) and the offset min-sum algorithm (OMSA) can outperform the conventional min-sum algorithm (MSA) at low signal-to-noise-ratios (SNRs), i.e., in the “waterfall region” of the bit error rate curve. This paper demonstrates that, for quantized decoders, MSA actually outperforms AMSA and OMSA in the “error floor” region, and that all three algorithms suffer from a relatively high error floor. This motivates the introduction of a modified MSA that is designed to outperform MSA, AMSA, and OMSA across all SNRs. The new algorithm is based on the assumption that trapping sets are the major cause of the error floor for quantized LDPC decoders. A performance estimation tool based on trapping sets is used to verify the effectiveness of the new algorithm and also to guide parameter selection. We also show that the implementation complexity of the new algorithm is only slightly higher than that of AMSA or OMSA. Finally, the simulated performance of the new algorithm, using several classes of LDPC codes (including spatially coupled LDPC codes), is shown to outperform MSA, AMSA, and OMSA across all SNRs.

IEEE Transactions on Communications•Jan 27, 2020•27 citations

Lower bounds for quantized LDPC min-sum decoders based on absorbing sets

Homayoon Hatami, David G. M. Mitchell, Daniel J. Costello +1 more

Previously published lower bounds on the error-floor performance of low-density parity-check (LDPC) codes with quantized sum-product algorithm (SPA) decoders need modification to apply to min-sum algorithm (MSA) decoders. In this paper we show that, due to the sub-optimality of MSA decoders, certain assumptions that apply to SPA decoders are not valid for MSA decoders. Based on appropriately modified assumptions, an improved technique is then proposed to evaluate lower bounds on the error floor performance of LDPC codes for an additive white Gaussian noise channel and a quantized MSA decoder. This new technique not only results in error floor bounds for MSA decoders, but also for SPA decoders. The obtained bound is based on an absorbing set, and a good error floor approximation can be obtained when the multiplicity of the absorbing set is known.

Allerton Conference on Communication, Control, and Computing•Oct 1, 2017•4 citations

Performance bounds for quantized LDPC decoders based on absorbing sets

Homayoon Hatami, David G. M. Mitchell, Daniel J. Costello +1 more

A code-independent performance bound for a given absorbing set is derived for quantized low-density parity-check (LDPC) decoders. The analysis demonstrates that each absorbing set in the Tanner graph imposes a specific lower bound on the frame error rate (FER) of any code containing that absorbing set under a given quantization scheme. This approach is applicable to any message-passing (MP) decoding algorithm and any uniform or non-uniform quantization scheme for LDPC codes. Simulation results using the sum-product algorithm (SPA) provide FERs that are consistent with the obtained bounds. In addition, the bounds demonstrate that the conventional quantized SPA is not capable of achieving very low FERs if the LDPC codes contain certain absorbing sets.

IEEE International Symposium on Information Theory (ISIT)•Jul 1, 2016•5 citations

High Speed Low Error Floor Hardware Implementation and Fast and Accurate Error Floor Estimation of LDPC Decoders

Sina Tolouei

This thesis explores hardware implementation of low error floor and high speed low-density parity-check (LDPC) decoders.At first, a novel partially-parallel implementation of a protograph-based quasi-cyclic (QC) LDPC decoder, using a new column-layered message-passing schedule is presented.A new design for serial-input check nodes and switch networks, results in lower hardware complexity while having a higher throughput and comparable latency in comparison with all existing partiallyparallel architectures.Thereafter, we introduce a multi-step scheme for the input quantization of message-passing decoders for LDPC codes.The scheme is based on successive requantization and re-decoding of the input blocks that cause the decoder to be trapped in a trapping set, until the decoding is successful or a maximum number of requantization/re-decodings is reached.The proposed scheme, which is applicable to both regular and irregular codes, lowers the error floor significantly at the cost of small increase in complexity, memory and latency.Furthermore, to facilitate the process of code design and performance evaluation in the error floor region, we design a fast and accurate technique to estimate the error floor of variable-regular LDPC codes under quantized iterative decoding algorithms.This technique, which is based on enumerating the dominant elementary trapping sets of the code, provides significant improvement over existing methods in terms of speed and accuracy.Finally, we examine the harmfulness of trapping sets of variable-regular LDPC codes for soft-decision iterative decoding algorithms.We show that, other than the size of a trapping set, the number of unsatisfied check nodes and the trapping set's topological properties, the position of its subgraph in the Tanner graph of the code can also have an effect on its harmfulness.We also examine dominant trapping sets iii of the quantized min-sum (MS) decoding algorithm and two of its variants (offset-MS and MS with successive relaxation (SR)), for both regular and irregular LDPC codes.We show that the distribution of dominant trapping sets of these algorithms is similar for regular codes and different for irregular codes.Based on these results, we evaluate the error floor performance of a decoder, consisting of MS, offset-MS and SR-MS decoding algorithms working in parallel.First, I would like to thank my supervisor, Professor Amir H. Banihashemi for leading and encouraging me during my research.When I started as his M.A.Sc.student nine years ago, my dream was to acquire a set of skills.Amir helped me to achieve them with invaluable advice and excellent guidance.I would also like to thank M. Samy Hosny, the CEO of SiloconPro Inc. for supporting my research and providing me with his professional experience.I can not express my appreciation to my wonderful wife

•Jan 1, 2014•2 citations
The performance of low-density parity-check (LDPC) codes at high signal-to- noise ratios (SNRs) is known to be limited by the presence of certain sub-graphs that exist in the Tanner graph representation of the code, for example trapping sets and absorbing sets. This dissertation derives a lower bound on the frame error rate (FER) of any LDPC code containing a given problematic sub-graph, assuming a particular iterative message passing (MP) decoder and decoder quantization. A crucial aspect of the lower bound is that it is code-independent, in the sense that it can be derived based only on a problematic sub-graph and then applied to any code containing it. Due to the complexity of evaluating the exact bound, assumptions are proposed to approximate it, from which we can estimate decoder performance. For LDPC codes, the attenuated min-sum algorithm (AMSA) and the offset min- sum algorithm (OMSA) are known to outperform the conventional min-sum algorithm (MSA) at low SNRs, i.e., in the waterfall region of the FER curve. This dis- sertation demonstrates that, for quantized LDPC decoders, the AMSA and OMSA underperform the MSA at high SNRs, i.e., in the error floor region of the FER curve, and that the MSA, AMSA, and OMSA all suffer from a relatively high error floor. Therefore, we introduce a novel modification of the MSA for quantized decoding of LDPC codes, called the threshold attenuated min-sum algorithm (TAMSA) (or the threshold offset min-sum algorithm (TOMSA)) with the aim of outperforming the MSA, AMSA, and OMSA at both low and high SNRs. The new decoding algorithm is designed based on the common assumption that trapping sets are the major cause of the error floor for quantized LDPC decoders, and it is shown to reduce the error probability associated with these problematic graphic objects. The lower bound analysis tool noted above is then used to verify the effectiveness of the new TAMSA (TOMSA) and also to assist in finding its optimum design parameters. We also show that the implementation complexity of the TAMSA (TOMSA) is only slightly higher than that of the AMSA or OMSA. Finally, we extend the lower bound to sliding window (SW) decoding of spatially coupled LDPC (SC-LDPC) codes. Additionally, we show that the performance of the TAMSA (TOMSA) is better than that of the MSA, AMSA, and OMSA for SW.
It is well known that for decoding low-density parity-check (LDPC) codes, the attenuated min-sum algorithm (AMSA) and the offset min-sum algorithm (OMSA) can outperform the conventional min-sum algorithm (MSA) at low signal-to-noise-ratios (SNRs). In this paper, we demonstrate that, for quantized LDPC decoders, although the MSA achieves better high SNR performance than the AMSA and OMSA, each of the MSA, AMSA, and OMSA all suffer from a relatively high error floor. Therefore, we propose a novel modification of the MSA for decoding quantized LDPC codes with the aim of lowering the error floor. Compared to the quantized MSA, the proposed modification is also helpful at low SNRs, where it matches the waterfall performance of the quantized AMSA and OMSA. The new algorithm is designed based on the assumption that trapping/absorbing sets (or other problematic graphical objects) are the major cause of the error floor for quantized LDPC decoders, and it aims to reduce the probability that these problematic objects lead to decoding errors.
The performance of low-density parity-check (LDPC) codes at high signal-to-noise ratios (SNRs) is known to be limited by the presence of certain sub-graphs that exist in the Tanner graph representation of the code, for example trapping sets and absorbing sets. This paper derives a lower bound on the frame error rate (FER) of any LDPC code containing a given problematic sub-graph, assuming a particular message passing decoder and decoder quantization. A crucial aspect of the lower bound is that it is code-independent, in the sense that it can be derived based only on a problematic sub-graph and then applied to any code containing it. Due to the complexity of evaluating the exact bound, assumptions are proposed to approximate it, from which we can estimate decoder performance. Simulated results obtained for both the quantized sum-product algorithm (SPA) and the quantized min-sum algorithm (MSA) are shown to be consistent with the approximate bound and the corresponding performance estimates. Different classes of LDPC codes, including both structured and randomly constructed codes, are used to demonstrate the robustness of the approach.
For decoding low-density parity-check (LDPC) codes, the attenuated min-sum algorithm (AMSA) and the offset min-sum algorithm (OMSA) can outperform the conventional min-sum algorithm (MSA) at low signal-to-noise-ratios (SNRs), i.e., in the “waterfall region” of the bit error rate curve. This paper demonstrates that, for quantized decoders, MSA actually outperforms AMSA and OMSA in the “error floor” region, and that all three algorithms suffer from a relatively high error floor. This motivates the introduction of a modified MSA that is designed to outperform MSA, AMSA, and OMSA across all SNRs. The new algorithm is based on the assumption that trapping sets are the major cause of the error floor for quantized LDPC decoders. A performance estimation tool based on trapping sets is used to verify the effectiveness of the new algorithm and also to guide parameter selection. We also show that the implementation complexity of the new algorithm is only slightly higher than that of AMSA or OMSA. Finally, the simulated performance of the new algorithm, using several classes of LDPC codes (including spatially coupled LDPC codes), is shown to outperform MSA, AMSA, and OMSA across all SNRs.
Previously published lower bounds on the error-floor performance of low-density parity-check (LDPC) codes with quantized sum-product algorithm (SPA) decoders need modification to apply to min-sum algorithm (MSA) decoders. In this paper we show that, due to the sub-optimality of MSA decoders, certain assumptions that apply to SPA decoders are not valid for MSA decoders. Based on appropriately modified assumptions, an improved technique is then proposed to evaluate lower bounds on the error floor performance of LDPC codes for an additive white Gaussian noise channel and a quantized MSA decoder. This new technique not only results in error floor bounds for MSA decoders, but also for SPA decoders. The obtained bound is based on an absorbing set, and a good error floor approximation can be obtained when the multiplicity of the absorbing set is known.
A code-independent performance bound for a given absorbing set is derived for quantized low-density parity-check (LDPC) decoders. The analysis demonstrates that each absorbing set in the Tanner graph imposes a specific lower bound on the frame error rate (FER) of any code containing that absorbing set under a given quantization scheme. This approach is applicable to any message-passing (MP) decoding algorithm and any uniform or non-uniform quantization scheme for LDPC codes. Simulation results using the sum-product algorithm (SPA) provide FERs that are consistent with the obtained bounds. In addition, the bounds demonstrate that the conventional quantized SPA is not capable of achieving very low FERs if the LDPC codes contain certain absorbing sets.
This thesis explores hardware implementation of low error floor and high speed low-density parity-check (LDPC) decoders.At first, a novel partially-parallel implementation of a protograph-based quasi-cyclic (QC) LDPC decoder, using a new column-layered message-passing schedule is presented.A new design for serial-input check nodes and switch networks, results in lower hardware complexity while having a higher throughput and comparable latency in comparison with all existing partiallyparallel architectures.Thereafter, we introduce a multi-step scheme for the input quantization of message-passing decoders for LDPC codes.The scheme is based on successive requantization and re-decoding of the input blocks that cause the decoder to be trapped in a trapping set, until the decoding is successful or a maximum number of requantization/re-decodings is reached.The proposed scheme, which is applicable to both regular and irregular codes, lowers the error floor significantly at the cost of small increase in complexity, memory and latency.Furthermore, to facilitate the process of code design and performance evaluation in the error floor region, we design a fast and accurate technique to estimate the error floor of variable-regular LDPC codes under quantized iterative decoding algorithms.This technique, which is based on enumerating the dominant elementary trapping sets of the code, provides significant improvement over existing methods in terms of speed and accuracy.Finally, we examine the harmfulness of trapping sets of variable-regular LDPC codes for soft-decision iterative decoding algorithms.We show that, other than the size of a trapping set, the number of unsatisfied check nodes and the trapping set's topological properties, the position of its subgraph in the Tanner graph of the code can also have an effect on its harmfulness.We also examine dominant trapping sets iii of the quantized min-sum (MS) decoding algorithm and two of its variants (offset-MS and MS with successive relaxation (SR)), for both regular and irregular LDPC codes.We show that the distribution of dominant trapping sets of these algorithms is similar for regular codes and different for irregular codes.Based on these results, we evaluate the error floor performance of a decoder, consisting of MS, offset-MS and SR-MS decoding algorithms working in parallel.First, I would like to thank my supervisor, Professor Amir H. Banihashemi for leading and encouraging me during my research.When I started as his M.A.Sc.student nine years ago, my dream was to acquire a set of skills.Amir helped me to achieve them with invaluable advice and excellent guidance.I would also like to thank M. Samy Hosny, the CEO of SiloconPro Inc. for supporting my research and providing me with his professional experience.I can not express my appreciation to my wonderful wife