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:2104.00304 · IEEE Transactions on Quantum Engineering

Log-Domain Decoding of Quantum LDPC Codes Over Binary Finite Fields

Ching–Yi Lai, Kao-Yueh Kuo

Published Jan 1, 2021• 28 citations
arXivHTMLPDF

Abstract

A quantum stabilizer code over$\GF(q)$corresponds to a classical additive code over$\GF(q^2)$that is self-orthogonal with respect to a symplectic inner product. We study the decoding of quantum low-density parity-check (LDPC) codes over binary finite fields$\GF(q=2^l)$by the sum-product algorithm, also known as belief propagation (BP). Conventionally, a message in a nonbinary BP for quantum codes over$\GF(2^l)$represents a probability vector over$\GF(2^{2l})$, inducing high decoding complexity. In this paper, we explore the property of the symplectic inner product and show that scalar messages suffice for BP decoding of nonbinary quantum codes, rather than vector messages necessary for the conventional BP. Consequently, we propose a BP decoding algorithm for quantum codes over${\GF(2^l)}$by passing scalar messages so that it has low computation complexity. The algorithm is specified in log domain by using log-likelihood ratios (LLRs) of the channel statistics to have a low implementation cost. Moreover, techniques such as message normalization or offset can be naturally applied in this algorithm to mitigate the effects of short cycles to improve BP performance. This is important for nonbinary quantum codes since they may have more short cycles compared to binary quantum codes. Several computer simulations are provided to demonstrate these advantages. The scalar-based strategy can also be used to improve the BP decoding of classical linear codes over$\GF(2^l)$with many short cycles.

DOI
10.1109/tqe.2021.3113936

Related papers

Refined Belief-Propagation Decoding of Quantum Codes with Scalar Messages

Kao-Yueh Kuo, Ching-Yi Lai

Codes based on sparse matrices have good performance and can be efficiently decoded by belief-propagation (BP). Decoding binary stabilizer codes needs a quaternary BP for (additive) codes over GF(4), which has a higher check-node complexity compared to a binary BP for codes over GF(2). Moreover, BP decoding of stabilizer codes suffers a performance loss from the short cycles in the underlying Tanner graph. In this paper, we propose a refined BP algorithm for decoding quantum codes by passing scalar messages. For a given error syndrome, this algorithm decodes to the same output as the conventional quaternary BP but with a check-node complexity the same as binary BP. As every message is a scalar, the message normalization can be naturally applied to improve the performance. Another observation is that the message-update schedule affects the BP decoding performance against short cycles. We show that running BP with message normalization according to a serial schedule (or other schedules) may significantly improve the decoding performance and error-floor in computer simulation.

arXiv:2102.07122•IEEE Globecom Workshops (GC Wkshps)•Dec 1, 2020•8 citations

Decoding Algorithms for Nonbinary LDPC Codes Over GF$(q)$

David Declercq, M.P.C. Fossorier

In this letter, we address the problem of decoding nonbinary low-density parity-check (LDPC) codes over finite fields GF(q), with reasonable complexity and good performance. In the first part of the letter, we recall the original belief propagation (BP) decoding algorithm and its Fourier domain implementation. We show that the use of tensor notations for the messages is very convenient for the algorithm description and understanding. In the second part of the letter, we introduce a simplified decoder which is inspired by the min-sum decoder for binary LDPC codes. We called this decoder extended min-sum (EMS). We show that it is possible to greatly reduce the computational complexity of the check-node processing by computing approximate reliability measures with a limited number of values in a message. By choosing appropriate correction factors or offsets, we show that the EMS decoder performance is quite good, and in some cases better than the regular BP decoder. The optimal values of the factor and offset correction are obtained asymptotically with simulated density evolution. Our simulations on ultra-sparse codes over very-high-order fields show that nonbinary LDPC codes are promising for applications which require low frame-error rates for small or moderate codeword lengths. The EMS decoder is a good candidate for practical hardware implementations of such codes

IEEE Transactions on Communications•Apr 1, 2007•725 citations

Refined Belief Propagation Decoding of Sparse-Graph Quantum Codes

Kao-Yueh Kuo, Ching–Yi Lai

Quantum stabilizer codes constructed from sparse matrices have good performance and can be efficiently decoded by belief propagation (BP). A conventional BP decoding algorithm treats binary stabilizer codes as additive codes over GF(4). This algorithm has a relatively complex process of handling check-node messages, which incurs higher decoding complexity. Moreover, BP decoding of a stabilizer code usually suffers a performance loss due to the many short cycles in the underlying Tanner graph. In this paper, we propose a refined BP decoding algorithm for quantum codes with complexity roughly the same as binary BP. For a given error syndrome, this algorithm decodes to the same output as the conventional quaternary BP but the passed node-to-node messages are single-valued, unlike the quaternary BP, where multivalued node-to-node messages are required. Furthermore, the techniques of message strength normalization can naturally be applied to these single-valued messages to improve the performance. Another observation is that the message-update schedule affects the performance of BP decoding against short cycles. We show that running BP with message strength normalization according to a serial schedule (or other schedules) may significantly improve the decoding performance and error floor in computer simulation.

arXiv:2002.06502•IEEE Journal on Selected Areas in Information Theory•Jul 24, 2020•53 citations

Reduced complexity and improved performance decoding algorithm for nonbinary LDPC codes over GF(q)

Xin Chen, Aidong Men

Low-density parity-check (LDPC) codes over finite fields GF(q) have a better performance than those of the binary low-density parity-check codes, at short and medium block lengths, but the decoder of GF(q)-LDPC has more complexity. In this paper, we present a new reduced-complexity belief propagation (BP) decoding algorithm for GF(q)-LDPC codes by analyzing the reliability of code symbols. Instead of update all the variable nodes during iteration, we just update variable nodes which are mostly to be in an error. The algorithm also shows a property to reduce the effects of oscillating on decoding. The simulations prove that we could improve performance and reduce complexity at the same time for short and medium GF(q)-LDPC codes.

IEEE International Conference on Communication Technology (ICCT)•Nov 1, 2008•6 citations

Reduced-Complexity Decoding of LDPC Codes

J. Chen, Ajay Dholakia, Evangelos S. Eleftheriou +2 more

Various log-likelihood-ratio-based belief-propagation (LLR-BP) decoding algorithms and their reduced-complexity derivatives for low-density parity-check (LDPC) codes are presented. Numerically accurate representations of the check-node update computation used in LLR-BP decoding are described. Furthermore, approximate representations of the decoding computations are shown to achieve a reduction in complexity by simplifying the check-node update, or symbol-node update, or both. In particular, two main approaches for simplified check-node updates are presented that are based on the so-called min-sum approximation coupled with either a normalization term or an additive offset term. Density evolution is used to analyze the performance of these decoding algorithms, to determine the optimum values of the key parameters, and to evaluate finite quantization effects. Simulation results show that these reduced-complexity decoding algorithms for LDPC codes achieve a performance very close to that of the BP algorithm. The unified treatment of decoding techniques for LDPC codes presented here provides flexibility in selecting the appropriate scheme from performance, latency, computational-complexity, and memory-requirement perspectives.

IEEE Transactions on Communications•Aug 1, 2005•964 citations

Reduced-Complexity Decoding of LDPC Codes

Reduced-Complexity Decoding of LDPC Codes Various log-likelihood-ratio-based belief-propagation (LLR- BP) decoding algorithms and their reduced-complexity derivatives for low-density parity-check (LDPC) codes are presented. Numerically accurate representations of the check-node update computation used in LLR-BP decoding are described. Furthermore, approximate representation of the decoding computations are shown to achieve a reduction in complexity, by simplifying the check-node update or symbol-node update, or both. In particular, two main approaches for simplified check-node updates are presented that are based on the so-called min-sum approximation coupled with either a normalization term or an additive offset term. Density evolution is used to analyze the performance of these decoding algorithms, to determine the optimum values of the key parameters, and to evaluate finite quantization effects. Simulation results show that these reduced-complexity decoding algorithms for LDPC codes achieve a performance very close to that of the BP algorithm. The unified treatment of decoding techniques for LDPC codes presented here provides flexibility in selecting the appropriate scheme from a performance, latency, computational complexity, and memory-requirement perspective.

IEEE Transactions on Communications•Jul 1, 2005•32 citations
A quantum stabilizer code over\GF(q)\GF(q)\GF(q)corresponds to a classical additive code over\GF(q2)\GF(q^2)\GF(q2)that is self-orthogonal with respect to a symplectic inner product. We study the decoding of quantum low-density parity-check (LDPC) codes over binary finite fields\GF(q=2l)\GF(q=2^l)\GF(q=2l)by the sum-product algorithm, also known as belief propagation (BP). Conventionally, a message in a nonbinary BP for quantum codes over\GF(2l)\GF(2^l)\GF(2l)represents a probability vector over\GF(22l)\GF(2^{2l})\GF(22l), inducing high decoding complexity. In this paper, we explore the property of the symplectic inner product and show that scalar messages suffice for BP decoding of nonbinary quantum codes, rather than vector messages necessary for the conventional BP. Consequently, we propose a BP decoding algorithm for quantum codes over\GF(2l){\GF(2^l)}\GF(2l)by passing scalar messages so that it has low computation complexity. The algorithm is specified in log domain by using log-likelihood ratios (LLRs) of the channel statistics to have a low implementation cost. Moreover, techniques such as message normalization or offset can be naturally applied in this algorithm to mitigate the effects of short cycles to improve BP performance. This is important for nonbinary quantum codes since they may have more short cycles compared to binary quantum codes. Several computer simulations are provided to demonstrate these advantages. The scalar-based strategy can also be used to improve the BP decoding of classical linear codes over\GF(2l)\GF(2^l)\GF(2l)with many short cycles.
Codes based on sparse matrices have good performance and can be efficiently decoded by belief-propagation (BP). Decoding binary stabilizer codes needs a quaternary BP for (additive) codes over GF(4), which has a higher check-node complexity compared to a binary BP for codes over GF(2). Moreover, BP decoding of stabilizer codes suffers a performance loss from the short cycles in the underlying Tanner graph. In this paper, we propose a refined BP algorithm for decoding quantum codes by passing scalar messages. For a given error syndrome, this algorithm decodes to the same output as the conventional quaternary BP but with a check-node complexity the same as binary BP. As every message is a scalar, the message normalization can be naturally applied to improve the performance. Another observation is that the message-update schedule affects the BP decoding performance against short cycles. We show that running BP with message normalization according to a serial schedule (or other schedules) may significantly improve the decoding performance and error-floor in computer simulation.
Decoding Algorithms for Nonbinary LDPC Codes Over GF(q)(q)(q)
In this letter, we address the problem of decoding nonbinary low-density parity-check (LDPC) codes over finite fields GF(q), with reasonable complexity and good performance. In the first part of the letter, we recall the original belief propagation (BP) decoding algorithm and its Fourier domain implementation. We show that the use of tensor notations for the messages is very convenient for the algorithm description and understanding. In the second part of the letter, we introduce a simplified decoder which is inspired by the min-sum decoder for binary LDPC codes. We called this decoder extended min-sum (EMS). We show that it is possible to greatly reduce the computational complexity of the check-node processing by computing approximate reliability measures with a limited number of values in a message. By choosing appropriate correction factors or offsets, we show that the EMS decoder performance is quite good, and in some cases better than the regular BP decoder. The optimal values of the factor and offset correction are obtained asymptotically with simulated density evolution. Our simulations on ultra-sparse codes over very-high-order fields show that nonbinary LDPC codes are promising for applications which require low frame-error rates for small or moderate codeword lengths. The EMS decoder is a good candidate for practical hardware implementations of such codes
Quantum stabilizer codes constructed from sparse matrices have good performance and can be efficiently decoded by belief propagation (BP). A conventional BP decoding algorithm treats binary stabilizer codes as additive codes over GF(4). This algorithm has a relatively complex process of handling check-node messages, which incurs higher decoding complexity. Moreover, BP decoding of a stabilizer code usually suffers a performance loss due to the many short cycles in the underlying Tanner graph. In this paper, we propose a refined BP decoding algorithm for quantum codes with complexity roughly the same as binary BP. For a given error syndrome, this algorithm decodes to the same output as the conventional quaternary BP but the passed node-to-node messages are single-valued, unlike the quaternary BP, where multivalued node-to-node messages are required. Furthermore, the techniques of message strength normalization can naturally be applied to these single-valued messages to improve the performance. Another observation is that the message-update schedule affects the performance of BP decoding against short cycles. We show that running BP with message strength normalization according to a serial schedule (or other schedules) may significantly improve the decoding performance and error floor in computer simulation.
Low-density parity-check (LDPC) codes over finite fields GF(q) have a better performance than those of the binary low-density parity-check codes, at short and medium block lengths, but the decoder of GF(q)-LDPC has more complexity. In this paper, we present a new reduced-complexity belief propagation (BP) decoding algorithm for GF(q)-LDPC codes by analyzing the reliability of code symbols. Instead of update all the variable nodes during iteration, we just update variable nodes which are mostly to be in an error. The algorithm also shows a property to reduce the effects of oscillating on decoding. The simulations prove that we could improve performance and reduce complexity at the same time for short and medium GF(q)-LDPC codes.
Various log-likelihood-ratio-based belief-propagation (LLR-BP) decoding algorithms and their reduced-complexity derivatives for low-density parity-check (LDPC) codes are presented. Numerically accurate representations of the check-node update computation used in LLR-BP decoding are described. Furthermore, approximate representations of the decoding computations are shown to achieve a reduction in complexity by simplifying the check-node update, or symbol-node update, or both. In particular, two main approaches for simplified check-node updates are presented that are based on the so-called min-sum approximation coupled with either a normalization term or an additive offset term. Density evolution is used to analyze the performance of these decoding algorithms, to determine the optimum values of the key parameters, and to evaluate finite quantization effects. Simulation results show that these reduced-complexity decoding algorithms for LDPC codes achieve a performance very close to that of the BP algorithm. The unified treatment of decoding techniques for LDPC codes presented here provides flexibility in selecting the appropriate scheme from performance, latency, computational-complexity, and memory-requirement perspectives.
Reduced-Complexity Decoding of LDPC Codes Various log-likelihood-ratio-based belief-propagation (LLR- BP) decoding algorithms and their reduced-complexity derivatives for low-density parity-check (LDPC) codes are presented. Numerically accurate representations of the check-node update computation used in LLR-BP decoding are described. Furthermore, approximate representation of the decoding computations are shown to achieve a reduction in complexity, by simplifying the check-node update or symbol-node update, or both. In particular, two main approaches for simplified check-node updates are presented that are based on the so-called min-sum approximation coupled with either a normalization term or an additive offset term. Density evolution is used to analyze the performance of these decoding algorithms, to determine the optimum values of the key parameters, and to evaluate finite quantization effects. Simulation results show that these reduced-complexity decoding algorithms for LDPC codes achieve a performance very close to that of the BP algorithm. The unified treatment of decoding techniques for LDPC codes presented here provides flexibility in selecting the appropriate scheme from a performance, latency, computational complexity, and memory-requirement perspective.