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

arXiv:1911.02762 · IEEE Transactions on Communications

Performance Bounds and Estimates for Quantized LDPC Decoders

Homayoon Hatami, David G. M. Mitchell, Daniel J. Costello, Thomas E. Fuja

Published Nov 13, 2019• 15 citations
arXivHTMLPDF

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

DOI
10.1109/tcomm.2019.2953232

Related papers

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

An Absorbing Set Analysis of Quantized LDPC Decoders

Homayoon Hatami

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.

•Jan 1, 2019•0 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

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

Predicting error floors of structured LDPC codes: deterministic bounds and estimates

Lara Dolecek, P. Lee, Zhengya Zhang +3 more

The error-correcting performance of low-density parity check (LDPC) codes, when decoded using practical iterative decoding algorithms, is known to be close to Shannon limits for codes with suitably large blocklengths. A substantial limitation to the use of finite-length LDPC codes is the presence of an error floor in the low frame error rate (FER) region. This paper develops a deterministic method of predicting error floors, based on high signal-to-noise ratio (SNR) asymptotics, applied to absorbing sets within structured LDPC codes. The approach is illustrated using a class of array-based LDPC codes, taken as exemplars of high-performance structured LDPC codes. The results are in very good agreement with a stochastic method based on importance sampling which, in turn, matches the hardware-based experimental results. The importance sampling scheme uses a mean-shifted version of the original Gaussian density, appropriately centered between a codeword and a dominant absorbing set, to produce an unbiased estimator of the FER with substantial computational savings over a standard Monte Carlo estimator. Our deterministic estimates are guaranteed to be a lower bound to the error probability in the high SNR regime, and extend the prediction of the error probability to as low as 10-30. By adopting a channel-independent viewpoint, the usefulness of these results is demonstrated for both the standard Gaussian channel and a channel with mixture noise.

IEEE Journal on Selected Areas in Communications•Jul 29, 2009•96 citations

Analysis of failures of decoders for LDPC codes

Shashi Kiran Chilappagari

Ever since the publication of Shannon's seminal work in 1948, the search for capacity achieving codes has led to many interesting discoveries in channel coding theory. Low-density parity-check (LDPC) codes originally proposed in 1963 were largely forgotten and rediscovered recently. The significance of LDPC codes lies in their capacity approaching performance even when decoded using low complexity sub-optimal decoding algorithms. Iterative decoders are one such class of decoders that work on a graphical representation of a code known as the Tanner graph. Their properties have been well understood in the asymptotic limit of the code length going to infinity. However, the behavior of various decoders for a given finite length code remains largely unknown.An understanding of the failures of the decoders is vital for the error floor analysis of a given code. Broadly speaking, error floor is the abrupt degradation in the frame error rate (FER) performance of a code in the high signal-to-noise ratio domain. Since the error floor phenomenon manifests in the regions not reachable by Monte-Carlo simulations, analytical methods are necessary for characterizing the decoding failures. In this work, we consider hard decision decoders for transmission over the binary symmetric channel (BSC).For column-weight-three codes, we provide tight upper and lower bounds on the guaranteed error correction capability of a code under the Gallager A algorithm by studying combinatorial objects known as trapping sets. For higher column weight codes, we establish bounds on the minimum number of variable nodes that achieve certain expansion as a function of the girth of the underlying Tanner graph, thereby obtaining lower bounds on the guaranteed error correction capability. We explore the relationship between a class of graphs known as cage graphs and trapping sets to establish upper bounds on the error correction capability.We also propose an algorithm to identify the most probable noise configurations, also known as instantons, that lead to error floor for linear programming (LP) decoding over the BSC. With the insight gained from the above analysis techniques, we propose novel code construction techniques that result in codes with superior error floor performance.

•Jan 1, 2008•0 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 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.
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.
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.
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.
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 error-correcting performance of low-density parity check (LDPC) codes, when decoded using practical iterative decoding algorithms, is known to be close to Shannon limits for codes with suitably large blocklengths. A substantial limitation to the use of finite-length LDPC codes is the presence of an error floor in the low frame error rate (FER) region. This paper develops a deterministic method of predicting error floors, based on high signal-to-noise ratio (SNR) asymptotics, applied to absorbing sets within structured LDPC codes. The approach is illustrated using a class of array-based LDPC codes, taken as exemplars of high-performance structured LDPC codes. The results are in very good agreement with a stochastic method based on importance sampling which, in turn, matches the hardware-based experimental results. The importance sampling scheme uses a mean-shifted version of the original Gaussian density, appropriately centered between a codeword and a dominant absorbing set, to produce an unbiased estimator of the FER with substantial computational savings over a standard Monte Carlo estimator. Our deterministic estimates are guaranteed to be a lower bound to the error probability in the high SNR regime, and extend the prediction of the error probability to as low as 10-30. By adopting a channel-independent viewpoint, the usefulness of these results is demonstrated for both the standard Gaussian channel and a channel with mixture noise.
Ever since the publication of Shannon's seminal work in 1948, the search for capacity achieving codes has led to many interesting discoveries in channel coding theory. Low-density parity-check (LDPC) codes originally proposed in 1963 were largely forgotten and rediscovered recently. The significance of LDPC codes lies in their capacity approaching performance even when decoded using low complexity sub-optimal decoding algorithms. Iterative decoders are one such class of decoders that work on a graphical representation of a code known as the Tanner graph. Their properties have been well understood in the asymptotic limit of the code length going to infinity. However, the behavior of various decoders for a given finite length code remains largely unknown.An understanding of the failures of the decoders is vital for the error floor analysis of a given code. Broadly speaking, error floor is the abrupt degradation in the frame error rate (FER) performance of a code in the high signal-to-noise ratio domain. Since the error floor phenomenon manifests in the regions not reachable by Monte-Carlo simulations, analytical methods are necessary for characterizing the decoding failures. In this work, we consider hard decision decoders for transmission over the binary symmetric channel (BSC).For column-weight-three codes, we provide tight upper and lower bounds on the guaranteed error correction capability of a code under the Gallager A algorithm by studying combinatorial objects known as trapping sets. For higher column weight codes, we establish bounds on the minimum number of variable nodes that achieve certain expansion as a function of the girth of the underlying Tanner graph, thereby obtaining lower bounds on the guaranteed error correction capability. We explore the relationship between a class of graphs known as cage graphs and trapping sets to establish upper bounds on the error correction capability.We also propose an algorithm to identify the most probable noise configurations, also known as instantons, that lead to error floor for linear programming (LP) decoding over the BSC. With the insight gained from the above analysis techniques, we propose novel code construction techniques that result in codes with superior error floor performance.