9 results
Search Results
2. Majority decoding of some classes of binary cyclic codes
- Author
-
L. Rudolph, J. R. Riek Jr., and C. Hartmann
- Subjects
Discrete mathematics ,Block code ,Polynomial ,Burst error-correcting code ,Library and Information Sciences ,Linear code ,Computer Science Applications ,Combinatorics ,Majority logic decoding ,Primitive polynomial ,Cyclic code ,BCH code ,Information Systems ,Mathematics - Abstract
This paper presents majority-decoding algorithms for four classes of binary cyclic codes. The classes are those for which the parity-check polynomial is: 1) the product of two primitive polynomials with relatively prime exponents and 2) the product of (x^r + 1)/(x + 1) and a primitive polynomial, where r \geq 3 is odd and the exponents are relatively prime, together with the corresponding nonexpurgated codes.
- Published
- 1974
3. Performance of selected block and convolutional codes on a fading HF channel
- Author
-
A. Pierce, J. Meyn, D. Cohn, and Allen H. Levesque
- Subjects
Block code ,Theoretical computer science ,Interleaving ,Computer science ,Repetition code ,Data_CODINGANDINFORMATIONTHEORY ,Library and Information Sciences ,Luby transform code ,Online codes ,Reed–Solomon error correction ,Fountain code ,Turbo code ,Fading ,Forward error correction ,Low-density parity-check code ,Raptor code ,Computer Science::Information Theory ,Error floor ,Concatenated error correction code ,Serial concatenated convolutional codes ,Linear code ,Computer Science Applications ,Convolutional code ,Erasure ,Tornado code ,Error detection and correction ,Algorithm ,Hamming code ,BCH code ,Information Systems ,Data transmission ,Communication channel - Abstract
This paper describes the application of selected block and convolutional coding techniques to digital transmission over an HF radio channel. Performance results are presented for interleaved binary Bose-Chaudhuri-Hocquenghem (BCH) codes, interleaved two-stage concatenated codes, and diffuse convolutional codes. The performance results are based upon raw error data recorded in transmission over a 640-km HF path, with various data runs representing the typical effects of frequency-selective and non-selective fading, atmospheric impulse noise, and interference from other users of the HF band. The performance of binary BCH codes with bit interleaving is presented and the selection of a code to meet a specified performance criterion is described. The sensitivity of specific codes to changing channel conditions is presented, along with the cost, in terms of interleaving, of designing for one set of channel conditions rather than others. Concatenated codes are discussed as a means of effective error control on channels with clustered errors. Performance data are presented for selected two-stage codes used with inner-stage word interleaving and the effects of varying certain of the code parameters are shown. Emphasis is placed on code designs that use the inner-stage code only for error detection and the outer-stage code mainly for erasure filling with only a small amount of symbol error correction. The impact of error clustering on the performance of concatenated codes is discussed. Two diffuse convolutional codes are evaluated with the use of recorded error data in computer simulations of their threshold-decoding algorithms. Performance of various configurations of these convolutional codes is given and a comparison is made with that of a simple block coding scheme having the same decoder storage requirements. The various coding techniques studied are compared on the basis of achievable performance as well as certain factors affecting the feasibility of implementation.
- Published
- 1968
4. Encoding and error-correction procedures for the Bose-Chaudhuri codes
- Author
-
W. W. Peterson
- Subjects
Block code ,Computer science ,List decoding ,Library and Information Sciences ,Luby transform code ,Online codes ,Expander code ,Reed–Solomon error correction ,Fountain code ,Redundancy (engineering) ,Turbo code ,Forward error correction ,Low-density parity-check code ,Arithmetic ,Raptor code ,Error floor ,Berlekamp–Welch algorithm ,Concatenated error correction code ,BCJR algorithm ,Serial concatenated convolutional codes ,Linear code ,Computer Science Applications ,Binary code ,Tornado code ,Error detection and correction ,Algorithm ,Hamming code ,Decoding methods ,BCH code ,Information Systems - Abstract
Bose and Ray-Chaudhuri have recently described a class of binary codes which for arbitrary m and t are t -error correcting and have length 2^m - 1 of which no more than mt digits are redundancy. This paper describes a simple error-correction procedure for these codes. Their cyclic structure is demonstrated and methods of exploiting it to implement the coding and correction procedure using shift registers are outlined. Closer bounds on the number of redundancy digits are derived.
- Published
- 1960
5. Shift-register synthesis and BCH decoding
- Author
-
J. Massey
- Subjects
Computer science ,Berlekamp–Welch algorithm ,Data_CODINGANDINFORMATIONTHEORY ,Berlekamp–Massey algorithm ,Sequential decoding ,Library and Information Sciences ,MAXEkSAT ,Berlekamp's algorithm ,Nonlinear feedback shift register ,Computer Science Applications ,Forney algorithm ,Algorithm ,BCH code ,Decoding methods ,Computer Science::Information Theory ,Information Systems - Abstract
It is shown in this paper that the iterative algorithm introduced by Berlekamp for decoding BCH codes actually provides a general solution to the problem of synthesizing the shortest linear feedback shift register capable of generating a prescribed finite sequence of digits. The shift-register approach leads to a simple proof of the validity of the algorithm as well as providing additional insight into its properties. The equivalence of the decoding problem for BCH codes to a shift-register synthesis problem is demonstrated, and other applications for the algorithm are suggested.
- Published
- 1969
6. Cyclic decoding procedures for Bose- Chaudhuri-Hocquenghem codes
- Author
-
Robert T. Chien
- Subjects
Block code ,BCJR algorithm ,Concatenated error correction code ,Sequential decoding ,Serial concatenated convolutional codes ,Library and Information Sciences ,Linear code ,Computer Science Applications ,Tornado code ,Arithmetic ,Algorithm ,BCH code ,Information Systems ,Mathematics - Abstract
This paper presents new general error-correction procedures for fhe class of codes known as Bose-Chaudhuri-Hocquenghem codes. It is shown that these procedures are efficient in time required for error-correction, and that they can be implemented with relatively simple electronic circuits. A comparison is also made with existing procedures.
- Published
- 1964
7. On majority-logic decoding for duals of primitive polynomial codes
- Author
-
T. Kasami and Shu Lin
- Subjects
Discrete mathematics ,Block code ,Concatenated error correction code ,Reed–Muller code ,Data_CODINGANDINFORMATIONTHEORY ,Library and Information Sciences ,Luby transform code ,Linear code ,Expander code ,Computer Science Applications ,Combinatorics ,Reed–Solomon error correction ,BCH code ,Computer Science::Information Theory ,Information Systems ,Mathematics - Abstract
The class of polynomial codes introduced by Kasami et al. has considerable inherent algebraic and geometric structure. It has been shown that this class of codes and their dual codes contain many important classes of cyclic codes as subclasses, such as BCH codes, Reed-Solomon codes, generalized Reed-Muller codes, projective geometry codes, and Euclidean geometry codes. The purpose of this paper is to investigate further properties of polynomial codes and their duals. First, majority-logic decoding for the duals of certain primitive polynomial codes is considered. Two methods of forming nonorthogonal parity-check sums are presented. Second, the maximality of Euclidean geometry codes is proved. The roots of the generator polynomial of an Euclidean geometry code are specified.
- Published
- 1971
8. Goppa codes
- Author
-
E. Berlekamp
- Subjects
Block code ,Discrete mathematics ,Error floor ,Binary number ,Data_CODINGANDINFORMATIONTHEORY ,Library and Information Sciences ,Computer Science Applications ,Combinatorics ,Redundancy (information theory) ,Goppa code ,Algebraic decoding ,BCH code ,Computer Science::Cryptography and Security ,Computer Science::Information Theory ,Information Systems ,Mathematics - Abstract
Goppa described a new class of linear noncyclic error-correcting codes in [1] and [2]. This paper is a summary of Goppa's work, which is not yet available in English. ^1 We prove the four most important properties of Goppa codes. 1) There exist q -ary Goppa codes with lengths and redundancies comparable to BCH codes. For the same redundancy, the Goppa code is typically one digit longer. 2) All Goppa codes have an algebraic decoding algorithm which will correct up to a certain number of errors, comparable to half the designed distance of BCH codes. 3) For binary Goppa codes, the algebraic decoding algorithm assumes a special form. 4) Unlike primitive BCH codes, which are known to have actual distances asymptotically equal to their designed distances, long Goppa codes have actual minimum distances much greater than twice the number of errors, which are guaranteed to be correctable by the algebraic decoding algorithm. In fact, long irreducible Goppa codes asymptotically meet the Gilbert bound.
- Published
- 1973
9. On decoding binary Bose-Chadhuri- Hocquenghem codes
- Author
-
Elwyn R. Berlekamp
- Subjects
Block code ,BCJR algorithm ,Concatenated error correction code ,List decoding ,Sequential decoding ,Serial concatenated convolutional codes ,Library and Information Sciences ,Arithmetic ,Linear code ,BCH code ,Computer Science Applications ,Information Systems ,Mathematics - Abstract
The solution of Newton's identities over a field of characteristic two is the key step in decoding Bose-Chaudhuri-Hocquenghem codes. This paper introduces a simple transformation of variables which halves the size of the resulting matrix. This transformation can increase the decoder's speed by almost a factor of eight and decrease the decoder's storage requirements by almost a factor of four.
- Published
- 1965
Discovery Service for Jio Institute Digital Library
For full access to our library's resources, please sign in.