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

L-STEP MAJORITY LOGIC DECODING,

Robert Tien-Wen Chien, Spencer W. Ng

Published Jun 1, 1970• 0 citations
OpenAlex

Abstract

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.

Related papers

Some new results on majority-logic codes for correction of random errors

D. McQuilton

The main advantages of random error-correcting majority-logic codes and majority-logic decoding in general are well known and two-fold. Firstly, they offer a partial solution to a classical coding theory problem, that of decoder complexity. Secondly, a majority-logic decoder inherently corrects many more random error patterns than the minimum distance of the code implies is possible. The solution to the decoder complexity is only a partial one because there are circumstances under which a majority-logic decoder is too complex and expensive to implement. [Continues.]

•Jan 1, 1978•2 citations

RECENT DEVELOPMENTS IN MAJORITY-LOGIC DECODING,

C. L. Chen, Robert Tien-Wen Chien

Abstract : The paper gives a survey of recent advances in majority-logic decoding for linear block codes. General majority-logic decoding algorithms are reviewed. The decoding schemes for product codes and the finite geometry codes are discussed. An improved decoding algorithm for the finite geometry codes is described. The improved decoding algorithm greatly reduces the decoding complexity of the codes. It should make the finite geometry codes very attractive in practical use on error-control systems. (Author)

•Sep 1, 1970•1 citation

On the construction of a class of majority-logic decodable codes

Tadao Kasami, Shu Lin

The attractiveness of majority-logic decoding is its simple implementation. Several classes of majority-logic decodable block codes have been discovered for the past two decades. In this paper, a method of constructing a new class of majority-logic decodable block codes is presented. Each code in this class is formed by combining majority-logic decodable codes of shorter lengths. A procedure for orthogonalizing codes of this class is formulated. For each code, a lower bound on the number of correctable errors with majority-logic decoding is obtained. An upper bound on the number of orthogonalization steps for decoding each code is derived. Several majority-logic decodable codes that have more information digits than the Reed-Muller codes of the same length and the same minimum distance are found. Some results presented in this paper are extensions of the results of Lin and Weldon [11] and Gore [12] on the majority-logic decoding of direct product codes.

IEEE Transactions on Information Theory•Sep 1, 1971•6 citations

Error correcting capability of 1-step majority logic decoding.

Claude. Laferriere

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.

•Jan 1, 1977•1 citation

Iterative threshold decoding of Quasi-Cyclic One Step Majority logic decodable codes

Karim Rkizat, Mohammed Lahmer, Mostafa Belkasmi

This paper presents a new class of Quasi-Cyclic One Step Majority logic codes of 1/2 rate constructed from perfect difference set. Theses codes can be encoded with low complexity, and perform very well when decoded with the Iterative threshold decoding algorithm. Much of these codes is a subfamily of the LDPC codes and can be decoded using belief propagation algorithm. A comparison between our results and those for LDPC code in terms of BER performance are presented.

World Congress on Information and Communication Technologies•Dec 1, 2015•3 citations

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•5 citations
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.
The main advantages of random error-correcting majority-logic codes and majority-logic decoding in general are well known and two-fold. Firstly, they offer a partial solution to a classical coding theory problem, that of decoder complexity. Secondly, a majority-logic decoder inherently corrects many more random error patterns than the minimum distance of the code implies is possible. The solution to the decoder complexity is only a partial one because there are circumstances under which a majority-logic decoder is too complex and expensive to implement. [Continues.]
Abstract : The paper gives a survey of recent advances in majority-logic decoding for linear block codes. General majority-logic decoding algorithms are reviewed. The decoding schemes for product codes and the finite geometry codes are discussed. An improved decoding algorithm for the finite geometry codes is described. The improved decoding algorithm greatly reduces the decoding complexity of the codes. It should make the finite geometry codes very attractive in practical use on error-control systems. (Author)
The attractiveness of majority-logic decoding is its simple implementation. Several classes of majority-logic decodable block codes have been discovered for the past two decades. In this paper, a method of constructing a new class of majority-logic decodable block codes is presented. Each code in this class is formed by combining majority-logic decodable codes of shorter lengths. A procedure for orthogonalizing codes of this class is formulated. For each code, a lower bound on the number of correctable errors with majority-logic decoding is obtained. An upper bound on the number of orthogonalization steps for decoding each code is derived. Several majority-logic decodable codes that have more information digits than the Reed-Muller codes of the same length and the same minimum distance are found. Some results presented in this paper are extensions of the results of Lin and Weldon [11] and Gore [12] on the majority-logic decoding of direct product codes.
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.