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:2308.13377

Layered Decoding of Quantum LDPC Codes

Julien Du Crest, Francisco García-Herrero, Mehdi Mhalla, Valentin Savin, Javier Valls

Published Aug 25, 2023• 2 citations
arXivHTMLPDF

Abstract

We address the problem of performing message-passing-based decoding of quantum LDPC codes under hardware latency limitations. We propose a novel way to do layered decoding that suits quantum constraints and outperforms flooded scheduling, the usual scheduling on parallel architectures. A generic construction is given to construct layers of hypergraph product codes. In the process, we introduce two new notions, t-covering layers which is a generalization of the usual layer decomposition, and a new scheduling called random order scheduling. Numerical simulations show that the random ordering is of independent interest as it helps relieve the high error floor typical of message-passing decoders on quantum codes for both layered and serial decoding without the need for post-processing.

DOI
10.48550/arxiv.2308.13377

Related papers

Layered Decoding of Quantum LDPC Codes

Julien Du Crest, Francisco García-Herrero, Mehdi Mhalla +2 more

We address the problem of doing message passing based decoding of quantum LDPC codes under hardware latency limitations. We propose a novel way to do layered decoding that suits quantum constraints and outperforms flooded scheduling, the usual scheduling on parallel architectures. A generic construction is given to construct layers of hypergraph product codes. In the process, we introduce two new notions, t-covering layers which is a generalization of the usual layer decomposition, and a modified scheduling called random order scheduling. Numerical simulations show that the random ordering is of independent interest as it helps relieve the high error floor typical of message passing decoders on quantum codes for both layered and serial decoding without the need of post-processing.

International Symposium on Turbo Codes and Iterative Information Processing•Sep 4, 2023•11 citations

Layered decoding for non-binary LDPC codes

Shuai Zhou, Jin Sha, Li Li +1 more

In this paper, we present a layered decoding algorithm for non-binary LDPC codes. Differing from the flooding message-passing schedule in conventional designs, the proposed scheme updates check node messages in serial. Furthermore, since fully serial decoding will lead to long latency, the locally-parallel globally-serial schedule is adopted. Basically the check nodes can be divided into several groups, i.e. layers. The layers are processed one by one while the check nodes in each layer are processed in parallel. Simulation results show that the proposed algorithm not only brings some improvement in error correcting performance but also gives some advantage in VLSI implementation of efficient partially parallel decoders.

IEEE International Symposium on Circuits and Systems proceedings•May 1, 2010•6 citations

Extended layered decoding of LDPC codes

Zhiqiang Cui, Zhongfeng Wang

In this paper, we propose an extended layered decoding approach for low density parity check (LDPC) codes. Compared to conventional layered decoding algorithms, the proposed approach has no constraint in the column weight of each layer. Hence, it enables more flexibility in high-throughput LDPC decoder design with layered decoding. Simulations on structured and random LDPC codes show that the proposed decoding method achieves significantly faster convergence and slightly better error correction performance than the conventional two phase massage passing sum-product algorithm. We also propose an efficient highly parallel decoder architecture for generic quasi-cyclic LDPC codes to facilitate the practical application of the proposed decoding scheme.

ACM Great Lakes Symposium on VLSI (GLSVLSI)•May 4, 2008•5 citations

Coarsely Quantized Layered Decoding Using the Information Bottleneck Method

Philipp H. Mohr, Gerhard Bauch, Fan Yu +1 more

In recent years coarsely quantized LDPC decoding using a flooding schedule has been extensively studied. However, there exist few works addressing coarse quantization for a layered schedule, which enables improved convergence speed of the message passing algorithm. The layered schedule can especially be beneficial for high throughput applications like fiber optical systems. This paper presents innovative layered decoding approaches, where the information bottleneck method is used for the design of different coarsely quantized decoder architectures. The varieties of investigated node implementations include lookup tables, computational domain techniques as well as reduced complexity approximations. All structures are designed offline using a layered discrete density evolution method. The performance of multiple node architectures is investigated in terms of evolution of mutual information in the design phase and in terms of error rates. We focus in this paper on regular quasi-cyclic codes. Our simulations running on GPUs also allow insights into the error floor behavior.

International Conference on Communications•Jun 1, 2021•12 citations

High throughput layered decoding of LDPC codes

Mohamed Ismail, Justin P. Coon, Imran Ahmed +2 more

Layered decoding of Low Density Parity Check (LDPC) codes has been shown to give faster convergence and use less storage than the conventional Two Phase Message Passing (TPMP) algorithm in decoding such codes. To achieve higher throughput, multiple rows of the parity check matrix may be decoded in parallel, as in the Parallel-Turbo Decoding Message Passing (P-TDMP) algorithm. However, contention for globally shared memory permits only a subset of rows to be decoded in parallel thus limiting overall throughput. This paper uses a near optimal scheduling algorithm, based on graph colouring, to overcome memory contention, allowing processing of multiple rows without code modification, resulting in significant throughput gains over the standard P-TDMP algorithm. For the LDPC codes studied, throughput gains compared to the P-TDMP algorithm, of between ten and fifteen are shown to be possible.

IEEE International Symposium on Personal, Indoor and Mobile Radio Communications (PIMRC)•Sep 1, 2009•0 citations

Low-Complexity Syndrome-Based Linear Programming Decoding of Quantum LDPC Codes

Sana Javed, Sergio Colet, Francisco García-Herrero +4 more

This paper proposes a novel low-complexity syndrome-based linear programming (SB-LP) decoding algorithm for decoding quantum low-density parity-check (LDPC) codes. Under the code-capacity model, the SB-LP decoder can be used as a standalone decoder; however, it is particularly powerful when used as a post-processing step following syndrome-based min-sum (SB-MS) decoding. In the latter case, the proposed decoder is shown to be capable of significantly reducing the error floor of the SB-MS decoder for both flooded and layered SB-MS scheduling. Also, an early stopping criterion is introduced to decide when to activate the SB-LP algorithm, avoiding executing a predefined maximum number of iterations for the SB-MS decoder. Simulation results show, for some example hypergraph and generalized bicycle (GB) codes, that the proposed decoder can lower the error floor by one to three orders of magnitude compared to SB-MS for the same total number of decoding iterations. Furthermore, for the class of GB codes, it is shown that as the minimum distance of the code increases, the logical error rate provided by the proposed decoder also improves, indicating that the solution is scalable. Under the circuit-level noise model, it is shown that while the SB-LP decoder does not fully replace the need for ordered statistics decoding (OSD) when flooded SB-MS is used as a preliminary step, it reduces the number of calls to the OSD post-processor, which directly impacts the overall latency. Additionally, the method offers a syndrome-matching decoder and improves the accuracy of the logical error rate for bivariate bicycle codes of distances six to eighteen, particularly at low error rates, when compared to the BP+OSD benchmark.

IEEE Transactions on Quantum Engineering•Dec 4, 2025•0 citations
We address the problem of performing message-passing-based decoding of quantum LDPC codes under hardware latency limitations. We propose a novel way to do layered decoding that suits quantum constraints and outperforms flooded scheduling, the usual scheduling on parallel architectures. A generic construction is given to construct layers of hypergraph product codes. In the process, we introduce two new notions, t-covering layers which is a generalization of the usual layer decomposition, and a new scheduling called random order scheduling. Numerical simulations show that the random ordering is of independent interest as it helps relieve the high error floor typical of message-passing decoders on quantum codes for both layered and serial decoding without the need for post-processing.
We address the problem of doing message passing based decoding of quantum LDPC codes under hardware latency limitations. We propose a novel way to do layered decoding that suits quantum constraints and outperforms flooded scheduling, the usual scheduling on parallel architectures. A generic construction is given to construct layers of hypergraph product codes. In the process, we introduce two new notions, t-covering layers which is a generalization of the usual layer decomposition, and a modified scheduling called random order scheduling. Numerical simulations show that the random ordering is of independent interest as it helps relieve the high error floor typical of message passing decoders on quantum codes for both layered and serial decoding without the need of post-processing.
In this paper, we present a layered decoding algorithm for non-binary LDPC codes. Differing from the flooding message-passing schedule in conventional designs, the proposed scheme updates check node messages in serial. Furthermore, since fully serial decoding will lead to long latency, the locally-parallel globally-serial schedule is adopted. Basically the check nodes can be divided into several groups, i.e. layers. The layers are processed one by one while the check nodes in each layer are processed in parallel. Simulation results show that the proposed algorithm not only brings some improvement in error correcting performance but also gives some advantage in VLSI implementation of efficient partially parallel decoders.
In this paper, we propose an extended layered decoding approach for low density parity check (LDPC) codes. Compared to conventional layered decoding algorithms, the proposed approach has no constraint in the column weight of each layer. Hence, it enables more flexibility in high-throughput LDPC decoder design with layered decoding. Simulations on structured and random LDPC codes show that the proposed decoding method achieves significantly faster convergence and slightly better error correction performance than the conventional two phase massage passing sum-product algorithm. We also propose an efficient highly parallel decoder architecture for generic quasi-cyclic LDPC codes to facilitate the practical application of the proposed decoding scheme.
In recent years coarsely quantized LDPC decoding using a flooding schedule has been extensively studied. However, there exist few works addressing coarse quantization for a layered schedule, which enables improved convergence speed of the message passing algorithm. The layered schedule can especially be beneficial for high throughput applications like fiber optical systems. This paper presents innovative layered decoding approaches, where the information bottleneck method is used for the design of different coarsely quantized decoder architectures. The varieties of investigated node implementations include lookup tables, computational domain techniques as well as reduced complexity approximations. All structures are designed offline using a layered discrete density evolution method. The performance of multiple node architectures is investigated in terms of evolution of mutual information in the design phase and in terms of error rates. We focus in this paper on regular quasi-cyclic codes. Our simulations running on GPUs also allow insights into the error floor behavior.
Layered decoding of Low Density Parity Check (LDPC) codes has been shown to give faster convergence and use less storage than the conventional Two Phase Message Passing (TPMP) algorithm in decoding such codes. To achieve higher throughput, multiple rows of the parity check matrix may be decoded in parallel, as in the Parallel-Turbo Decoding Message Passing (P-TDMP) algorithm. However, contention for globally shared memory permits only a subset of rows to be decoded in parallel thus limiting overall throughput. This paper uses a near optimal scheduling algorithm, based on graph colouring, to overcome memory contention, allowing processing of multiple rows without code modification, resulting in significant throughput gains over the standard P-TDMP algorithm. For the LDPC codes studied, throughput gains compared to the P-TDMP algorithm, of between ten and fifteen are shown to be possible.
This paper proposes a novel low-complexity syndrome-based linear programming (SB-LP) decoding algorithm for decoding quantum low-density parity-check (LDPC) codes. Under the code-capacity model, the SB-LP decoder can be used as a standalone decoder; however, it is particularly powerful when used as a post-processing step following syndrome-based min-sum (SB-MS) decoding. In the latter case, the proposed decoder is shown to be capable of significantly reducing the error floor of the SB-MS decoder for both flooded and layered SB-MS scheduling. Also, an early stopping criterion is introduced to decide when to activate the SB-LP algorithm, avoiding executing a predefined maximum number of iterations for the SB-MS decoder. Simulation results show, for some example hypergraph and generalized bicycle (GB) codes, that the proposed decoder can lower the error floor by one to three orders of magnitude compared to SB-MS for the same total number of decoding iterations. Furthermore, for the class of GB codes, it is shown that as the minimum distance of the code increases, the logical error rate provided by the proposed decoder also improves, indicating that the solution is scalable. Under the circuit-level noise model, it is shown that while the SB-LP decoder does not fully replace the need for ordered statistics decoding (OSD) when flooded SB-MS is used as a preliminary step, it reduces the number of calls to the OSD post-processor, which directly impacts the overall latency. Additionally, the method offers a syndrome-matching decoder and improves the accuracy of the logical error rate for bivariate bicycle codes of distances six to eighteen, particularly at low error rates, when compared to the BP+OSD benchmark.