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 the construction of a class of majority-logic decodable codes

Tadao Kasami, Shu Lin

Published Sep 1, 1971• 6 citations
Publisher

Abstract

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.

DOI
10.1109/tit.1971.1054691

Related papers

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

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

On the Lin-Weldon majority-logic decoding algorithm for product codes (Corresp.)

Nguyen Quang Đuc

It is shown that a majority-logic decoding algorithm proposed by Lin and Weldon for the product of anL-step and a one-step orthogonalizable code is incomplete whenLis greater than unity. An improvement is presented to overcome this disadvantage in the binary case.

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

Modified Majority Logic Decoding of Reed-Muller Codes for Channel Coding

Ting‐Ya Yang, Houshou Chen, Chen-Han Chuang

This paper proposes the modify majority-logic decoding using sum-product or min-sum decoding algorithms at the highest-order information bits in RM codes. Numerical results show that, compared with the traditional majority-logic decoding algorithm, the modified majority logic decoding method proposed in this study can reduce the bit error rate (BER) considerably. This task is accomplished without incurring a significant increase in decoding complexity because soft-decision decoding is used only at the highest information bits of RM codes, whereas majority-logic decoding is still applied at the other orders of information bits.

IIAE International Conference on Industrial Application Engineering (ICIAE)•Jan 1, 2020•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

Iterative Algorithms for Decoding a Class of Two-Step Majority-Logic Decodable Cyclic Codes

Li Guo Zhang, Qin Huang, Shu Lin

Codes constructed based on finite geometries form a large class of cyclic codes with large minimum distances which can be decoded with simple majority-logic decoding in one or multiple steps. In 2001, Kou, Lin and Fossorier showed that the one-step majority-logic decodable finite geometry codes form a class of cyclic LDPC codes whose Tanner graphs are free of cycles of length 4. These cyclic finite geometry LDPC codes perform very well over the AWGN channel using iterative decoding based on belief propagation (IDBP) and have very low error-floors. However, the standard IDBP is not effective for decoding other cyclic finite geometry codes because their Tanner graphs contain too many short cycles of length 4 which severely degrade the decoding performance. This paper investigates iterative decoding of two-step majority-logic decodable finite geometry codes. Three effective algorithms for decoding these codes are proposed. These algorithms are devised based on the orthogonal structure of the parity-check matrices of the codes to avoid or reduce the degrading effect of the short cycles of length 4. These decoding algorithms provide significant coding gains over the standard IDBP using either the sum-product or the min-sum algorithms.

IEEE Transactions on Communications•Dec 22, 2010•6 citations
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.
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.
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.
This paper proposes the modify majority-logic decoding using sum-product or min-sum decoding algorithms at the highest-order information bits in RM codes. Numerical results show that, compared with the traditional majority-logic decoding algorithm, the modified majority logic decoding method proposed in this study can reduce the bit error rate (BER) considerably. This task is accomplished without incurring a significant increase in decoding complexity because soft-decision decoding is used only at the highest information bits of RM codes, whereas majority-logic decoding is still applied at the other orders of information bits.
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.
Codes constructed based on finite geometries form a large class of cyclic codes with large minimum distances which can be decoded with simple majority-logic decoding in one or multiple steps. In 2001, Kou, Lin and Fossorier showed that the one-step majority-logic decodable finite geometry codes form a class of cyclic LDPC codes whose Tanner graphs are free of cycles of length 4. These cyclic finite geometry LDPC codes perform very well over the AWGN channel using iterative decoding based on belief propagation (IDBP) and have very low error-floors. However, the standard IDBP is not effective for decoding other cyclic finite geometry codes because their Tanner graphs contain too many short cycles of length 4 which severely degrade the decoding performance. This paper investigates iterative decoding of two-step majority-logic decodable finite geometry codes. Three effective algorithms for decoding these codes are proposed. These algorithms are devised based on the orthogonal structure of the parity-check matrices of the codes to avoid or reduce the degrading effect of the short cycles of length 4. These decoding algorithms provide significant coding gains over the standard IDBP using either the sum-product or the min-sum algorithms.