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:2501.13923 · IEEE International Symposium on Information Theory (ISIT)

Efficient Mitigation of Error Floors in Quantum Error Correction Using Non-Binary Low-Density Parity-Check Codes

Kenta Kasai

Published Jun 22, 2025• 3 citations
arXivHTMLPDF

Abstract

In this paper, we propose an efficient method to reduce error floors in quantum error correction using non-binary low-density parity-check (LDPC) codes. We identify and classify cycle structures in the parity-check matrix where estimated noise becomes trapped, and develop tailored decoding methods for each cycle type. For Type-I cycles, we propose a method to make the difference between estimated and true noise degenerate. Type-II cycles are shown to be un-correctable, while for Type-III cycles, we utilize the fact that cycles in non-binary LDPC codes do not necessarily correspond to codewords, allowing us to estimate the true noise. Our method significantly improves decoding performance and reduces error floors.

DOI
10.1109/isit63088.2025.11195217

Related papers

Trapping Sets of Iterative Decoders for Quantum and Classical Low-Density Parity-Check Codes

Nithin Raveendran

Protecting logical information in the form of a classical bit or a quantum bit (qubit) is an essential step in ensuring fault-tolerant classical or quantum computation. Error correction codes and their decoders perform this step by adding redundant information that aids the decoder to recover or protect the logical information even in the presence of noise. Low-density parity-check (LDPC) codes have been one of the most popular error correction candidates in modern communication and data storage systems. Similarly, their quantum analogues, quantum LDPC codes are being actively pursued as excellent prospects for error correction in future fault-tolerant quantum systems due to their asymptotically non-zero rates, sparse parity check matrices, and efficient iterative decoding algorithms. This dissertation deals with failure configurations, known as \emph{trapping sets} of classical and quantum LDPC codes when decoded with iterative message passing decoding algorithms, and the \emph{error floor phenomenon} - the degradation of logical error rate performance at low physical noise regime. The study of quantum trapping sets will enable the construction of better quantum LDPC codes and also help in modifying iterative quantum decoders to achieve higher fault-tolerant thresholds and lower error floors. Towards this goal, the dissertation also presents iterative decoders for classical and quantum LDPC codes using the \emph{deep neural network framework}, novel iterative decoding algorithms, and a decoder-aware \emph{expansion-contraction method} for error floor estimation. In this dissertation, we first establish a systematic methodology by which one can identify and classify \emph{quantum trapping sets} (QTSs) according to their topological structure and decoder used. For this purpose, we leverage the known harmful configurations in the Tanner graph, called \emph{trapping sets} (TSs), from the classical error correction world. The conventional definition of a trapping set of classical LDPC codes is generalized to address the syndrome decoding scenario for quantum LDPC codes. Furthermore, we show that the knowledge of QTSs can be used to design better quantum LDPC codes and decoders. In the context of the development of novel decoders, we extend the stochastic resonance based decoders to quantum LDPC codes, propose iteration-varying message passing decoders with their message update rules learned by neural networks tuned for low logical error rate, and present a syndrome based generalized belief propagation algorithm for tackling convergence failure of iterative decoders due to the presence of short cycles. Our analysis of TSs of a layered decoding architecture clearly reveals the dependence of the harmfulness of TSs (classical or quantum) on the iterative decoder, and thus on the error floor estimates. We present a computationally efficient method for estimating error floors of LDPC codes over the binary symmetric channel without any prior knowledge of its trapping sets. The sub-graph expansion-contraction method is a general procedure for TS characterization, which lists all harmful error patterns up to a given weight for the LDPC code and decoder. Based on this decoder-aware trapping set characterization for LDPC codes, we propose a model-driven deep neural network (DNN) framework that unfolds the decoding iterations, to design the \emph{decoder diversity of finite alphabet iterative decoders (FAIDs)}. Our decoder diversity DNN-FAID delivers excellent waterfall performance along with a low error floor.

•Jan 1, 2021•1 citation

Improved Hard-Reliability Based Majority-Logic Decoding for Non-Binary LDPC Codes

Saedong Yeo, In‐Cheol Park

This letter proposes two methods to improve the iterative hard-reliability based majority-logic decoding algorithm for non-binary low-density parity-check (NB-LDPC) codes. The first method improves the error-correcting performance by modifying the initialization process, which is based on the fact that Gray coded modulation is used in general. In addition, a storage reduction method is proposed to make the proposed decoding hardware-friendly, which reduces the memory size considerably while sustaining the error-correcting performance achieved by the modified initialization. For an NB-LDPC code over Galois field of 32 elements, the memory size is reduced by about 75% compared with that of the conventional decoding algorithm.

IEEE Communications Letters•Nov 1, 2016•16 citations

Error rate estimation of low-density parity-check codes on binary symmetric channels using cycle enumeration

Hua Xiao, Amir H. Banihashemi

The performance of low-density parity-check (LDPC) codes decoded by hard-decision iterative decoding algorithms can be accurately estimated if the weight J and the number |EJ| of the smallest error patterns that cannot be corrected by the decoder are known. To obtain J and |EJ|, one would need to perform the direct enumeration of error patterns with weight i les J. The complexity of enumeration increases exponentially with J, essentially as nJ, where n is the code block length. This limits the application of direct enumeration to codes with small n and J. In this letter, we approximate J and |EJ| by enumerating and testing the error patterns that are subsets of short cycles in the code's Tanner graph. This reduces the computational complexity by several orders of magnitude compared to direct enumeration, making it possible to estimate the error rates for almost any practical LDPC code. To obtain the error rate estimates, we propose an algorithm that progressively improves the estimates as larger cycles are enumerated. Through a number of examples, we demonstrate that the proposed method can accurately estimate both the bit error rate (BER) and the frame error rate (FER) of regular and irregular LDPC codes decoded by a variety of hard-decision iterative decoding algorithms.

IEEE Transactions on Communications•Jun 1, 2009•35 citations

Quantum Error Correction with Girth-16 Non-Binary LDPC Codes via Affine Permutation Construction

Kenta Kasai

We propose a method for constructing quantum error-correcting codes using non-binary low-density parity-check codes whose Tanner graphs have girth 16. While conventional constructions based on circulant permutation matrices are limited to a maximum girth of 12, our approach leverages affine permutation matrices combined with a randomized sequential selection strategy to eliminate short cycles and achieve girth 16. Numerical experiments show that the proposed codes significantly reduce the number of low-weight codewords. Joint belief propagation decoding over depolarizing channels reveals that although a slight degradation appears in the waterfall region, a substantial improvement is achieved in the error floor performance. We also evaluated the minimum distance of the proposed codes and found that they achieve a larger upper bound than conventional constructions.

arXiv:2504.17790•International Symposium on Turbo Codes and Iterative Information Processing•Aug 18, 2025•2 citations

Error Rate Estimation of Finite-Length Low-Density Parity-Check Codes on Binary Symmetric Channels Using Cycle Enumeration

Hua Xiao, Amir H. Banihashemi

The performance of low-density parity-check (LDPC) codes decoded by hard-decision iterative decoding algorithms can be accurately estimated if the weight J and the number |Ej| of the smallest error patterns that cannot be corrected by the decoder are known. To obtain J and |Ej|, one would need to perform the direct enumeration of error patterns with weight i les J. The complexity of enumeration increases exponentially with J, essentially as nJ, where n is the code block length. In this paper, we approximate J and |Ej| by enumerating and testing the error patterns that are subsets of short cycles in the code's Tanner graph. This reduces the computational complexity by several orders of magnitude compared to direct enumeration, making it possible to estimate the error rates for almost any practical LDPC code. To obtain the error rate estimates, we propose an algorithm that progressively improves the estimates as larger cycles are enumerated. Through a number of examples, we demonstrate that the proposed method can accurately estimate both the bit error rate (BER) and the frame error rate (FER) of regular and irregular LDPC codes decoded by a variety of hard-decision iterative decoding algorithms.

IEEE International Symposium on Information Theory (ISIT)•Jun 1, 2007•4 citations

Analysis of Error Floors of Non-binary LDPC Codes over BEC

T. Nozaki, Kenta Kasai, Kohichi Sakaniwa

In this paper, we investigate the error floors of the non-binary low-density parity-check codes transmitted over the binary erasure channels under belief propagation decoding. We propose a method to improve the decoding erasure rates in the error floors by optimizing labels in zigzag cycles in the Tanner graphs of codes. Furthermore, we give lower bounds on the bit and the symbol erasure rates in the error floors. The simulation results show that the presented lower bounds are tight for the codes designed by the proposed method.

IEICE Transactions on Fundamentals of Electronics Communications and Computer Sciences•Jan 1, 2012•3 citations
In this paper, we propose an efficient method to reduce error floors in quantum error correction using non-binary low-density parity-check (LDPC) codes. We identify and classify cycle structures in the parity-check matrix where estimated noise becomes trapped, and develop tailored decoding methods for each cycle type. For Type-I cycles, we propose a method to make the difference between estimated and true noise degenerate. Type-II cycles are shown to be un-correctable, while for Type-III cycles, we utilize the fact that cycles in non-binary LDPC codes do not necessarily correspond to codewords, allowing us to estimate the true noise. Our method significantly improves decoding performance and reduces error floors.
Protecting logical information in the form of a classical bit or a quantum bit (qubit) is an essential step in ensuring fault-tolerant classical or quantum computation. Error correction codes and their decoders perform this step by adding redundant information that aids the decoder to recover or protect the logical information even in the presence of noise. Low-density parity-check (LDPC) codes have been one of the most popular error correction candidates in modern communication and data storage systems. Similarly, their quantum analogues, quantum LDPC codes are being actively pursued as excellent prospects for error correction in future fault-tolerant quantum systems due to their asymptotically non-zero rates, sparse parity check matrices, and efficient iterative decoding algorithms. This dissertation deals with failure configurations, known as \emph{trapping sets} of classical and quantum LDPC codes when decoded with iterative message passing decoding algorithms, and the \emph{error floor phenomenon} - the degradation of logical error rate performance at low physical noise regime. The study of quantum trapping sets will enable the construction of better quantum LDPC codes and also help in modifying iterative quantum decoders to achieve higher fault-tolerant thresholds and lower error floors. Towards this goal, the dissertation also presents iterative decoders for classical and quantum LDPC codes using the \emph{deep neural network framework}, novel iterative decoding algorithms, and a decoder-aware \emph{expansion-contraction method} for error floor estimation. In this dissertation, we first establish a systematic methodology by which one can identify and classify \emph{quantum trapping sets} (QTSs) according to their topological structure and decoder used. For this purpose, we leverage the known harmful configurations in the Tanner graph, called \emph{trapping sets} (TSs), from the classical error correction world. The conventional definition of a trapping set of classical LDPC codes is generalized to address the syndrome decoding scenario for quantum LDPC codes. Furthermore, we show that the knowledge of QTSs can be used to design better quantum LDPC codes and decoders. In the context of the development of novel decoders, we extend the stochastic resonance based decoders to quantum LDPC codes, propose iteration-varying message passing decoders with their message update rules learned by neural networks tuned for low logical error rate, and present a syndrome based generalized belief propagation algorithm for tackling convergence failure of iterative decoders due to the presence of short cycles. Our analysis of TSs of a layered decoding architecture clearly reveals the dependence of the harmfulness of TSs (classical or quantum) on the iterative decoder, and thus on the error floor estimates. We present a computationally efficient method for estimating error floors of LDPC codes over the binary symmetric channel without any prior knowledge of its trapping sets. The sub-graph expansion-contraction method is a general procedure for TS characterization, which lists all harmful error patterns up to a given weight for the LDPC code and decoder. Based on this decoder-aware trapping set characterization for LDPC codes, we propose a model-driven deep neural network (DNN) framework that unfolds the decoding iterations, to design the \emph{decoder diversity of finite alphabet iterative decoders (FAIDs)}. Our decoder diversity DNN-FAID delivers excellent waterfall performance along with a low error floor.
This letter proposes two methods to improve the iterative hard-reliability based majority-logic decoding algorithm for non-binary low-density parity-check (NB-LDPC) codes. The first method improves the error-correcting performance by modifying the initialization process, which is based on the fact that Gray coded modulation is used in general. In addition, a storage reduction method is proposed to make the proposed decoding hardware-friendly, which reduces the memory size considerably while sustaining the error-correcting performance achieved by the modified initialization. For an NB-LDPC code over Galois field of 32 elements, the memory size is reduced by about 75% compared with that of the conventional decoding algorithm.
The performance of low-density parity-check (LDPC) codes decoded by hard-decision iterative decoding algorithms can be accurately estimated if the weight J and the number |EJ| of the smallest error patterns that cannot be corrected by the decoder are known. To obtain J and |EJ|, one would need to perform the direct enumeration of error patterns with weight i les J. The complexity of enumeration increases exponentially with J, essentially as nJ, where n is the code block length. This limits the application of direct enumeration to codes with small n and J. In this letter, we approximate J and |EJ| by enumerating and testing the error patterns that are subsets of short cycles in the code's Tanner graph. This reduces the computational complexity by several orders of magnitude compared to direct enumeration, making it possible to estimate the error rates for almost any practical LDPC code. To obtain the error rate estimates, we propose an algorithm that progressively improves the estimates as larger cycles are enumerated. Through a number of examples, we demonstrate that the proposed method can accurately estimate both the bit error rate (BER) and the frame error rate (FER) of regular and irregular LDPC codes decoded by a variety of hard-decision iterative decoding algorithms.
We propose a method for constructing quantum error-correcting codes using non-binary low-density parity-check codes whose Tanner graphs have girth 16. While conventional constructions based on circulant permutation matrices are limited to a maximum girth of 12, our approach leverages affine permutation matrices combined with a randomized sequential selection strategy to eliminate short cycles and achieve girth 16. Numerical experiments show that the proposed codes significantly reduce the number of low-weight codewords. Joint belief propagation decoding over depolarizing channels reveals that although a slight degradation appears in the waterfall region, a substantial improvement is achieved in the error floor performance. We also evaluated the minimum distance of the proposed codes and found that they achieve a larger upper bound than conventional constructions.
The performance of low-density parity-check (LDPC) codes decoded by hard-decision iterative decoding algorithms can be accurately estimated if the weight J and the number |Ej| of the smallest error patterns that cannot be corrected by the decoder are known. To obtain J and |Ej|, one would need to perform the direct enumeration of error patterns with weight i les J. The complexity of enumeration increases exponentially with J, essentially as nJ, where n is the code block length. In this paper, we approximate J and |Ej| by enumerating and testing the error patterns that are subsets of short cycles in the code's Tanner graph. This reduces the computational complexity by several orders of magnitude compared to direct enumeration, making it possible to estimate the error rates for almost any practical LDPC code. To obtain the error rate estimates, we propose an algorithm that progressively improves the estimates as larger cycles are enumerated. Through a number of examples, we demonstrate that the proposed method can accurately estimate both the bit error rate (BER) and the frame error rate (FER) of regular and irregular LDPC codes decoded by a variety of hard-decision iterative decoding algorithms.
In this paper, we investigate the error floors of the non-binary low-density parity-check codes transmitted over the binary erasure channels under belief propagation decoding. We propose a method to improve the decoding erasure rates in the error floors by optimizing labels in zigzag cycles in the Tanner graphs of codes. Furthermore, we give lower bounds on the bit and the symbol erasure rates in the error floors. The simulation results show that the presented lower bounds are tight for the codes designed by the proposed method.