Two recursive algorithms for computing the weight distribution ofcertain irreducible cyclic codes

Two recursive algorithms for computing the weight distributions of certain binary irreducible cyclic codes of length n in the so-called index 2 case are presented. The running times of these algorithms are smaller than O(log²r) where r=2^m and n is a factor of r-1     

Some results on arithmetic codes of composite length

A new upper bound on the minimum distance of binary cyclic arithmetic codes of composite length is derived. New classes of binary cyclic arithmetic codes of composite length are introduced. The error correction capability of these codes is discussed, and in some cases the actual minimum distance is found. Decoding algorithms based on majority-logic decision are proposed for these codes.     

等重码的一些新结果

本文给出两种构造二元非线性等重码的方法，这些方法是［１］文构造二元非线性循环等重码方法的改进。通过我们的构造方法可以得到几类二元最优等重码。我们进一步说明通过ＧＦ（ｑ）上的等重码和达到Ｐｌｏｔｋｉｎ界的最优码可以构造达到Ｊｏｈｎｓｏｎ上界的二元最优等重码     

基于初等数论的圈长8规则准循环LDPC码

This paper is concerned with (3, n ) and (4, n ) regular quasi-cyclic Low Density Parity Check (LDPC) code constructions from elementary number theory. Given the column weight, we determine the shift values of the circulant permutation matrices via arithmetic analysis. The proposed constructions of quasi-cyclic LDPC codes achieve the following main advantages simultaneously: 1) our methods are constructive in the sense that we avoid any searching process; 2) our methods ensure no four or six cycles in the bipartite graphs corresponding to the LDPC codes; 3) our methods are direct constructions of quasi-cyclic LDPC codes which do not use any other quasi-cyclic LDPC codes of small length like component codes or any other algorithms/cyclic codes like building block; 4)the computations of the parameters involved are based on elementary number theory, thus very simple and fast. Simulation results show that the constructed regular codes of high rates perform almost 1.25 dB above Shannon limit and have no error floor down to the bit-error rate of 10-6 .     

Multiplicative complexity of bilinear algorithms for cyclic convolution over finite fields

The multiplicative complexity of bilinear algorithms for cyclic convolution over finite fields is investigated. It is shown that mutually prime factor algorithms are inferior to directly designed algorithms for all lengths except those whose factors have relatively prime exponents. A previously described approach is proposed for directly designing algorithms which are highly structured and computationally efficient. Several complexity results are provided for factor lengths of specific form, and the manner in which cyclic convolution algorithms lead to linear algebraic error-correcting codes is discussed.Research supported by Natural Sciences and Engineering Research Council Canada Grant A0912.     

The minimum distance of the duals of binary irreducible cyclic codes

Irreducible cyclic codes have been an interesting subject of study for many years. The weight distribution of some of them have been determined. We determine the minimum distance and certain weights of the duals of binary irreducible cyclic codes. We show that the weight distribution of these codes is determined by the cyclotomic numbers of certain order. As a byproduct, we describe a class of double-error correcting codes.     

Some results on the minimum distance structure of cyclic codes

This paper presents a number of interesting results relating to the determination of actual minimum distance of cyclic codes. Codes with multiple sets of consecutive roots are constructed. A bound on the minimum weight of odd-weight codewords is determined. Relations on the distribution of roots of the generator polynomial are investigated. Location polynomials of reversible codes are examined. These results are used to obtain better estimates of the minimum distance of many new cyclic codes.     

Cyclotomic Linear Codes of Order $3$

In this correspondence, two classes of cyclotomic linear codes over GF(q) of order 3 are constructed and their weight distributions are determined. The two classes are two-weight codes and contain optimal codes. They are not equivalent to irreducible cyclic codes in general when q > 2.     

The Weight Distribution of Some Irreducible Cyclic Codes

Irreducible cyclic codes have been an interesting subject of study for a long time. Their weight distribution is known in only a few cases. In this paper, the weight distribution of the irreducible cyclic codes in a number of other cases is determined. The number of nonzero weights in the codes dealt with in this paper varies between one and four.      

On the generalized Hamming weights of several classes of cycliccods

The generalized Hamming weights of a linear code are fundamental code parameters related to the minimal overlap structures of the subcodes. They were introduced by V.K. Wei (1991) and shown to characterize the performance of the linear code in certain cryptographical applications. Results are presented on the generalized Hamming weights of several classes of binary cyclic codes, including primitive double-error-correcting and triple-error-correcting BCH codes, certain reversible cyclic codes, and some extended binary Goppa codes. In particular, the second generalized Hamming weight of primitive double-error-correcting BCH codes is determined and upper and lower bounds are obtained for the generalized Hamming weights for the codes studied. These bounds are compared to results from other methods     

Weight distributions of cyclic self-dual codes

We give a 1-level squaring construction for binary repeated-root cyclic codes of length n=2/sup a/b, a/spl ges/1, b odd. This allows us to obtain the weight distributions of all cyclic binary self-dual codes of lengths up to 110, which are not accessible by direct computation. We also use the shadow construction, as a particular method for Type I self-dual codes.     

一类循环码的神经网络软判决译码算法

本文分析了一类循环码的结构特性，提出了这类循环码的神经网络软判决译码算法。新算法的复杂度比现有一般的神经网络译码算法要低得多，而其译码性能接近大似然译码。     

The weight distributions of some binary quadratic residue codes

The weight distributions of binary quadratic residue codes C can be computed from the weight distribution of a subset of C containing one-fourth (resp., one-eighth) of the codewords in C when the length of the code is congruent to 1 (resp., -1) modulo 8. An algorithm to determine the weight distributions of binary cyclic codes is given. As a consequence, the weight distributions of (73,37,13), (89,45,17), and (97,49,15) quadratic residue codes are determined precisely.     

New generalizations of the Reed-Muller codes--I: Primitive codes

First it is shown that all binary Reed-Muller codes with one digit dropped can be made cyclic by rearranging the digits. Then a natural generalization to the nonbinary case is presented, which also includes the Reed-Muller codes and Reed-Solomon codes as special cases. The generator polynomial is characterized and the minimum weight is established. Finally, some results on weight distribution are given.     

On binary images of shortened cyclic (8, 5) codes over GF(2/sup 8/)

We have generated binary images of a large number of shortened cyclic (8, 5) codes over GF(2/sup 8/) and have computed weight distributions of the binary images of the codes. Based on the weight distributions, we have chosen four codes with the largest minimum weight 8 and the second largest minimum weight 7 among the generated codes. Over an additive white Gaussian noise channel with binary phase-shift keying modulation, simulation results have shown that block error rates of the chosen codes by a soft-decision decoding based on order-2 reprocessing are smaller than those of (64, 40) subcodes of Reed-Muller (64, 42) code by maximum likelihood decoding.     

Repeated-root cyclic codes

In the theory of cyclic codes, it is common practice to require that (n,q)=1, where n is the word length and F_q is the alphabet. It is shown that the even weight subcodes of the shortened binary Hamming codes form a sequence of repeated-root cyclic codes that are optimal. In nearly all other cases, one does not find good cyclic codes by dropping the usual restriction that n and q must be relatively prime. This statement is based on an analysis for lengths up to 100. A theorem shows why this was to be expected, but it also leads to low-complexity decoding methods. This is an advantage, especially for the codes that are not much worse than corresponding codes of odd length. It is demonstrated that a binary cyclic code of length 2n (n odd) can be obtained from two cyclic codes of length n by the well-known | u|u+v| construction. This leads to an infinite sequence of optimal cyclic codes with distance 4. Furthermore, it is shown that low-complexity decoding methods can be used for these codes. The structure theorem generalizes to other characteristics and to other lengths. Some comparisons of the methods using earlier examples are given     

A family of low-complexity binary linear codes for Bluetooth and BLAST signaling applications

We construct a family of linear binary block codes that are useful for Bluetooth, OFDM and BLAST applications. These codes are derived from ordinary block repetition codes using cyclic shifts of the input information vector which greatly simplifies encoding. We find several sets of cyclic shifts that constrain the search for good codes. We consider code lengthening and the input-output weight enumerators. We show that the codes are good candidates for low-power, low-cost and high data-rate applications using fixed code rate and variable codeword length, or adaptive coding with variable minimum Hamming distance. We propose a parallel structure of the encoder well-suited to OFDM and BLAST systems. Finally, we give an example of code design for use in retransmission schemes, and another example of a concatenated rate 2/3 code well-suited to the Bluetooth system.     

Fast parallel algorithms for decoding Reed-Solomon codes based onremainder polynomials

The problem of decoding cyclic error correcting codes is one of solving a constrained polynomial congruence, often achieved using the Berlekamp-Massey or the extended Euclidean algorithm on a key equation involving the syndrome polynomial. A module-theoretic approach to the solution of polynomial congruences is developed here using the notion of exact sequences. This technique is applied to the Welch-Berlekamp (1986) key equation for decoding Reed-Solomon codes for which the computation of syndromes is not required. It leads directly to new and efficient parallel decoding algorithms that can be realized with a systolic array. The architectural issues for one of these parallel decoding algorithms are examined in some detail     

On Z4-duality

Recently the notion on binary codes called Z₄-linearity was introduced. This notion explains why Kerdock codes and Delsarte-Goethals codes admit formal duals in spite of their nonlinearity. The “Z₄-duals” of these codes (called “Preparata” and “Goethals” codes) are new nonlinear codes which admit simpler decoding algorithms than the previously known formal duals (the generalized Preparata and Goethals codes). We prove, by using the notion of exact weight enumerator, that the relationship between any Z₄-linear code and its Z₄ -dual is stronger than the standard formal duality and we deduce the weight enumerators of related generalized codes