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

IEEE Transactions on Information Theory

On binary majority-logic decodable codes (Corresp.)

S. Shiva, Stafford E. Tavares

Published Jan 1, 1974• 1 citation
Publisher

Abstract

LetV\primebe a binary(n,k)majority-logic decodable code withg\prime (X)as its generator polynomial and odd minimum distanced. LetVbe the(n, k - 1)subset code generated byg\prime (X)(1 + X). This correspondence shows thatVis majority-logic deeodable withd + 1orthogonal estimates. This fact is useful in the simultaneous correction of random errors and erasures.

DOI
10.1109/tit.1974.1055151

Related papers

A note on one-step majority-logic decodable codes (Corresp.)

Chin-Long Chen, W. J. Warren

Construction of shortened geometric codes as Shown here results in 1-step majority-logic deeodable codes. The shortened codes retain the error-correction ability of the parent codes and the decoders for the shortened codes are much simpler than for the parent code. A table of shortened codes is given.

IEEE Transactions on Information Theory•Jan 1, 1973•2 citations

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

Generalized minimum distance decoding on majority logic decodable codes (Corresp.)

Tai-Yang Hwang, Sheng-Uei Guan

Generalized minimum distance decoding schemes are found for majority logic decodable codes. These decoding schemes are parallel to the classical majority logic decoding schemes and thus can be easily implemented.

IEEE Transactions on Information Theory•Sep 1, 1982•0 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•0 citations

Further results on majority-logic decoding of product codes (Corresp.)

Nguyen Quang Đuc, L.V. Skattebol

In this correspondence additional results on majority-logic decoding of product codes are presented. If one of the component codes is decodable using Rudolph's nonorthogonal algorithm, and the other using Reed-Massey'sL-step orthogonalization, then the resulting product code is majority-logic decodable inLsteps, where nonorthogonal checks are used in the first step and orthogonal checks in the remaining steps. If the component codes are both decodable using Rudolph's algorithm, the product code is majority-logic decodable using the same procedure.

IEEE Transactions on Information Theory•Mar 1, 1972•1 citation

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
LetV\primebe a binary(n,k)majority-logic decodable code withg\prime (X)as its generator polynomial and odd minimum distanced. LetVbe the(n, k - 1)subset code generated byg\prime (X)(1 + X). This correspondence shows thatVis majority-logic deeodable withd + 1orthogonal estimates. This fact is useful in the simultaneous correction of random errors and erasures.
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.
In this correspondence additional results on majority-logic decoding of product codes are presented. If one of the component codes is decodable using Rudolph's nonorthogonal algorithm, and the other using Reed-Massey'sL-step orthogonalization, then the resulting product code is majority-logic decodable inLsteps, where nonorthogonal checks are used in the first step and orthogonal checks in the remaining steps. If the component codes are both decodable using Rudolph's algorithm, the product code is majority-logic decodable using the same procedure.