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

Error correcting capability of 1-step majority logic decoding.

Claude. Laferriere

Published Jan 1, 1977• 1 citation
Publisher

Abstract

One-step majority logic decoding corrects not only all error patterns of weight t or less but also some error patterns of weight greater than t. In this thesis an estimate of the number of error patterns of weight t+1, which 1-step MLD can correct, is given since they have a high probability of occurrence as compared, to those of greater weights. General considerations on 1-step MLD are also included.

DOI
10.20381/ruor-8304

Related papers

Optimum 1-Step Majority-Logic Decoding of Binary Reed–Muller Codes

Hoang Ly, Emina Soljanin

The classical majority-logic decoder proposed by Reed for Reed-Muller codes RM(r, m) of order r and length 2^m, unfolds in r+1 sequential steps, decoding message symbols from highest to lowest degree. Several follow-up decoding algorithms reduced the number of steps, but for a limited set of parameters, or at the expense of reduced performance, or relying on the existence of some combinatorial structures. We show that any one-step majority-logic decoder-that is, a decoder performing all majority votes in one step simultaneously without sequential processing-can correct at most d_min/4 errors for all values of r and m, where d_min denotes the code's minimum distance. We then introduce a new hard-decision decoder that completes the decoding in a single step and attains this error-correction limit. It applies to all r and m, and can be viewed as a parallel realization of Reed's original algorithm, decoding all message symbols simultaneously. Remarkably, we also prove that the decoder is optimum in the erasure setting: it recovers the message from any erasure pattern of up to d_min-1 symbols-the theoretical limit. To our knowledge, this is the first 1-step decoder for RM codes that achieves both optimal erasure correction and the maximum one-step error correction capability.

arXiv:2508.08736•IEEE International Symposium on Information Theory (ISIT)•Jun 1, 2026•0 citations

L-STEP MAJORITY LOGIC DECODING,

Robert Tien-Wen Chien, Spencer W. Ng

In the search for multiple-error-correcting codes which can be easily and rapidly decoded, some coding theorists have turned their attentions to threshold (majority logic) decoding. Much work has been done in this area recently, and quite a few classes of new codes suitable for threshold decoding have been developed. The main desirable feature of majority logic decoding is that it can be very simply implemented. Furthermore majority decoding can also automatically correct many more patterns of errors other than those guaranteed by the decoding schemes without any additional equipment. This paper is a survey of the L-step majority decoding.

•Jun 1, 1970•0 citations

One-step weighted-majority decoding (Corresp.)

L. Rudolph, Woodrow E. Robbins

It is shown that any decoding function for a linear binary code can be realized as a weighted majority of nonorthogonal parity checks. An example is given of a four-error-correcting code that is neither L-step orthogonalizable nor one-step majority decodable using non-orthogonal parity checks and yet is one-step weighted-majority decodable using only ten nonorthogonal parity checks.

IEEE Transactions on Information Theory•May 1, 1972•9 citations

One-step majority-logic decoding with symbol reliability information (Corresp.)

C.-E.W. Sundberg

A method of using reliability information in one-step majority-logic decoders is presented. The idea is, basically, that the received binary digits are corrected in an order such that the least reliable digit is first corrected. With this method the error correction capability of the decoder is extended for large signal-to-noise ratios (SNR's). Different decoding algorithms are used when the number of orthogonal parity-check sums are even and odd, respectively. Computer simulations are presented for some short codes with binary antipodal signals on the additive white Gaussian noise channel.

IEEE Transactions on Information Theory•Mar 1, 1975•12 citations

Maximum Likelihood Decoding of Quantum Error Correction Codes

Hanyan Cao, Ge Yan, Yuxuan Du +1 more

Quantum error correction (QEC) is indispensable for realizing fault-tolerant quantum computation, yet its effectiveness hinges critically on the classical decoding algorithm that interprets noisy syndrome measurements. Among all possible decoding strategies, maximum likelihood decoding (MLD) is provably optimal, since it identifies the logical group with largest likelihood by summing over all possible errors within logical class consistent with the observed syndrome. Despite its optimality, MLD is computationally intractable in general (#P-hard), motivating a rich landscape of exact and approximate algorithms. In this topical review, we provide a unified perspective on MLD by surveying recent advances through three complementary lenses: statistical mechanics, tensor networks, and artificial intelligence. From the statistical mechanics viewpoint, the MLD problem maps onto evaluating partition functions of disordered spin models, enabling exact solutions for certain codes and noise models as well as threshold estimation via phase-transition analysis. From the tensor network perspective, approximate contraction of tensor networks on the code's factor graph yields decoders that closely approach MLD accuracy with polynomial computational cost. From the artificial intelligence perspective, neural-network-based decoders, including autoregressive generative models and recurrent transformers, learn to approximate the MLD distribution from data, achieving high accuracy with the parallelism afforded by modern hardware accelerators. We discuss the connections among these three approaches, review their application to both simulated and experimental quantum hardware, and outline open challenges including real-time decoding, scalability to large code distances, and generalization to high-rate quantum low-density parity-check codes.

quant-pharXiv:2605.17230•May 19, 2026•0 citations

An Efficient Majority Error Detection in Logic Decoding with Euclidean Geometry Low Density Parity Check (Eg-Ldpc) Codes

M .Vengadapathiraj Mr, U. Maheswaran, A.Karunakaran Mr

In a recent article, a technique was proposed to step up the majority logic decoding of variation set low density parity check codes. This is helpful as majority logic decoding can be implemented serially with trouble-free hardware but requires a huge decoding time. The method detect whether a word has errors in the initial iterations of majority logic decoding, and at what time there are no errors the decoding split ends without completing the rest of the iterations. While the majority words in a memory will be error-free, the average decoding time is significantly reduced. The outcome obtained proves that the technique is also effective for EG-LDPC codes. General simulation results are given to precisely estimate the prospect of error detection for different code sizes and numbers of errors.

International Journal of Business Intelligents•Jun 11, 2019•0 citations
One-step majority logic decoding corrects not only all error patterns of weight t or less but also some error patterns of weight greater than t. In this thesis an estimate of the number of error patterns of weight t+1, which 1-step MLD can correct, is given since they have a high probability of occurrence as compared, to those of greater weights. General considerations on 1-step MLD are also included.
The classical majority-logic decoder proposed by Reed for Reed-Muller codes RM(r, m) of order r and length 2^m, unfolds in r+1 sequential steps, decoding message symbols from highest to lowest degree. Several follow-up decoding algorithms reduced the number of steps, but for a limited set of parameters, or at the expense of reduced performance, or relying on the existence of some combinatorial structures. We show that any one-step majority-logic decoder-that is, a decoder performing all majority votes in one step simultaneously without sequential processing-can correct at most d_min/4 errors for all values of r and m, where d_min denotes the code's minimum distance. We then introduce a new hard-decision decoder that completes the decoding in a single step and attains this error-correction limit. It applies to all r and m, and can be viewed as a parallel realization of Reed's original algorithm, decoding all message symbols simultaneously. Remarkably, we also prove that the decoder is optimum in the erasure setting: it recovers the message from any erasure pattern of up to d_min-1 symbols-the theoretical limit. To our knowledge, this is the first 1-step decoder for RM codes that achieves both optimal erasure correction and the maximum one-step error correction capability.
In the search for multiple-error-correcting codes which can be easily and rapidly decoded, some coding theorists have turned their attentions to threshold (majority logic) decoding. Much work has been done in this area recently, and quite a few classes of new codes suitable for threshold decoding have been developed. The main desirable feature of majority logic decoding is that it can be very simply implemented. Furthermore majority decoding can also automatically correct many more patterns of errors other than those guaranteed by the decoding schemes without any additional equipment. This paper is a survey of the L-step majority decoding.
A method of using reliability information in one-step majority-logic decoders is presented. The idea is, basically, that the received binary digits are corrected in an order such that the least reliable digit is first corrected. With this method the error correction capability of the decoder is extended for large signal-to-noise ratios (SNR's). Different decoding algorithms are used when the number of orthogonal parity-check sums are even and odd, respectively. Computer simulations are presented for some short codes with binary antipodal signals on the additive white Gaussian noise channel.
Quantum error correction (QEC) is indispensable for realizing fault-tolerant quantum computation, yet its effectiveness hinges critically on the classical decoding algorithm that interprets noisy syndrome measurements. Among all possible decoding strategies, maximum likelihood decoding (MLD) is provably optimal, since it identifies the logical group with largest likelihood by summing over all possible errors within logical class consistent with the observed syndrome. Despite its optimality, MLD is computationally intractable in general (#P-hard), motivating a rich landscape of exact and approximate algorithms. In this topical review, we provide a unified perspective on MLD by surveying recent advances through three complementary lenses: statistical mechanics, tensor networks, and artificial intelligence. From the statistical mechanics viewpoint, the MLD problem maps onto evaluating partition functions of disordered spin models, enabling exact solutions for certain codes and noise models as well as threshold estimation via phase-transition analysis. From the tensor network perspective, approximate contraction of tensor networks on the code's factor graph yields decoders that closely approach MLD accuracy with polynomial computational cost. From the artificial intelligence perspective, neural-network-based decoders, including autoregressive generative models and recurrent transformers, learn to approximate the MLD distribution from data, achieving high accuracy with the parallelism afforded by modern hardware accelerators. We discuss the connections among these three approaches, review their application to both simulated and experimental quantum hardware, and outline open challenges including real-time decoding, scalability to large code distances, and generalization to high-rate quantum low-density parity-check codes.
In a recent article, a technique was proposed to step up the majority logic decoding of variation set low density parity check codes. This is helpful as majority logic decoding can be implemented serially with trouble-free hardware but requires a huge decoding time. The method detect whether a word has errors in the initial iterations of majority logic decoding, and at what time there are no errors the decoding split ends without completing the rest of the iterations. While the majority words in a memory will be error-free, the average decoding time is significantly reduced. The outcome obtained proves that the technique is also effective for EG-LDPC codes. General simulation results are given to precisely estimate the prospect of error detection for different code sizes and numbers of errors.