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

Graph theoreticq-ary codes (Corresp.)

L.S. Bobrow, S. L. Hakimi

Published Mar 1, 1971• 7 citations
Publisher

Abstract

This correspondence formulatesGF(q)matrix descriptions for a class of weighted, directed graphs. As a result of this formulation, the concept of graph theoretic error-correcting codes is generalized to theq-ary case. It is shown that graph theoreticq-ary codes are completely orthogonalizable and, hence, one-step majority decodable. It is also seen that known techniques for the augmentation of circuit codes can he extended to theq-ary case. The resulting codes remain easily decodable.

DOI
10.1109/tit.1971.1054616

Related papers

Graph theoretic error-correcting codes

S. L. Hakimi, Jon G. Bredeson

A study of the efficiency, error-correcting capabilities, and limitations of graph theoretic block codes is presented. Augmentation of graph theoretic codes and their generation is discussed. It is shown that such augmentation techniques can substantially increase the level of efficiency of these codes and potentially could increase it to the level of the best available codes. Furthermore, the augmented graph theoretic codes are shown to be easily decodable.

IEEE Transactions on Information Theory•Jul 1, 1968•62 citations

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

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

Graph-based codes and iterative decoding

Aamod Khandekar

The field of error correcting codes was revolutionized by the introduction of turbo codes [7] in 1993. These codes demonstrated dramatic performance improvements over any previously known codes, with significantly lower complexity. Since then, much progress has been made towards understanding the performance of these codes, as well as in using this understanding to design even better codes. This thesis takes a few more steps in both these directions. We develop a new technique, called the typical set bound, for analyzing the asymptotic performance of code ensembles based on their weight enumerators. This technique yields very tight bounds on the maximum-likelihood decoding threshold of code ensembles, and is powerful enough to reproduce Shannon's noisy coding theorem for the class of binary-input symmetric channels. We also introduce a new class of codes called irregular repeat-accumulate~(IRA) codes, which are adapted from the previously known class of repeat-accumulate~(RA) codes. These codes are competitive in terms of decoding performance with the class of irregular low-density parity-check~(LDPC) codes, which are arguably the best class of codes known today, at least for long block lengths. In addition, IRA codes have a significant advantage over irregular LDPC codes in terms of encoding complexity. We also derive an analytical bound regarding iterative decoding thresholds of code ensembles on general binary-input symmetric channels, an area in which theoretical results are currently lacking

•Jan 1, 2003•53 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

LDPC Codes Based on Combinatorial Designs, Graphs, and Superposition

W.E. Ryan, Shu Hwa Lin

Combinatorial designs [1–8] form an important branch in combinatorial mathematics. In the late 1950s and during the 1960s, special classes of combinatorial designs, such as balanced incomplete block designs , were used to construct error correcting codes, especial majority-logic-decodable codes. More recently, combinatorial designs were successfully used to construct structured LDPC codes [9–12]. LDPC codes of practical lengths constructed from several classes of combinatorial designs were shown to perform very well over the binary-input AWGN channel with iterative decoding. Graphs form another important branch in combinatorial mathematics. They were also used to construct error-correcting codes in the early 1960s, but not very successfully. Only a few small classes of majority-logic-decodable codes were constructed. However, since the rediscovery of LDPC codes in the middle of the 1990s, graphs have become an important tool for constructing LDPC codes. One example is to use protographs for constructing iteratively decodable codes as described in Chapters 6 and 8. This chapter presents several methods for constructing LDPC codes based on special types of combinatorial designs and graphs. Balanced Incomplete Block Designs and LDPC Codes Balanced incomplete block designs (BIBDs) form an important class of combinatorial designs. A special subclass of BIBDs can be used to construct RC-constrained matrices or arrays of CPMs from which LDPC codes can be constructed. This section gives a brief description of BIBDs. For an in-depth understanding of this subject, readers are referred to [1–8].

Cambridge University Press eBooks•Sep 17, 2009•1 citation
This correspondence formulatesGF(q)matrix descriptions for a class of weighted, directed graphs. As a result of this formulation, the concept of graph theoretic error-correcting codes is generalized to theq-ary case. It is shown that graph theoreticq-ary codes are completely orthogonalizable and, hence, one-step majority decodable. It is also seen that known techniques for the augmentation of circuit codes can he extended to theq-ary case. The resulting codes remain easily decodable.
The field of error correcting codes was revolutionized by the introduction of turbo codes [7] in 1993. These codes demonstrated dramatic performance improvements over any previously known codes, with significantly lower complexity. Since then, much progress has been made towards understanding the performance of these codes, as well as in using this understanding to design even better codes. This thesis takes a few more steps in both these directions. We develop a new technique, called the typical set bound, for analyzing the asymptotic performance of code ensembles based on their weight enumerators. This technique yields very tight bounds on the maximum-likelihood decoding threshold of code ensembles, and is powerful enough to reproduce Shannon's noisy coding theorem for the class of binary-input symmetric channels. We also introduce a new class of codes called irregular repeat-accumulate~(IRA) codes, which are adapted from the previously known class of repeat-accumulate~(RA) codes. These codes are competitive in terms of decoding performance with the class of irregular low-density parity-check~(LDPC) codes, which are arguably the best class of codes known today, at least for long block lengths. In addition, IRA codes have a significant advantage over irregular LDPC codes in terms of encoding complexity. We also derive an analytical bound regarding iterative decoding thresholds of code ensembles on general binary-input symmetric channels, an area in which theoretical results are currently lacking
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.
Combinatorial designs [1–8] form an important branch in combinatorial mathematics. In the late 1950s and during the 1960s, special classes of combinatorial designs, such as balanced incomplete block designs , were used to construct error correcting codes, especial majority-logic-decodable codes. More recently, combinatorial designs were successfully used to construct structured LDPC codes [9–12]. LDPC codes of practical lengths constructed from several classes of combinatorial designs were shown to perform very well over the binary-input AWGN channel with iterative decoding. Graphs form another important branch in combinatorial mathematics. They were also used to construct error-correcting codes in the early 1960s, but not very successfully. Only a few small classes of majority-logic-decodable codes were constructed. However, since the rediscovery of LDPC codes in the middle of the 1990s, graphs have become an important tool for constructing LDPC codes. One example is to use protographs for constructing iteratively decodable codes as described in Chapters 6 and 8. This chapter presents several methods for constructing LDPC codes based on special types of combinatorial designs and graphs. Balanced Incomplete Block Designs and LDPC Codes Balanced incomplete block designs (BIBDs) form an important class of combinatorial designs. A special subclass of BIBDs can be used to construct RC-constrained matrices or arrays of CPMs from which LDPC codes can be constructed. This section gives a brief description of BIBDs. For an in-depth understanding of this subject, readers are referred to [1–8].