Generalized quadratic residue codes

A simple definition of generalized quadratic residue codes, that is, quadratic residue codes of block lengthp^{m}, is given, and an account of many of their properties is presented.     

Gaps in the binary weight distributions of Reed-Solomon codes

When a Reed-Solomon code is expanded to form a binary code, certain combinations of the spectrum of the Reed-Solomon code and the basis used for the expansion result in large gaps in the weight distribution of the binary code. It is shown that the size of these gaps can be bounded by computing the sums of various powers of the basis elements and applying a theorem normally used for cyclic codes. This explains why codes obtained by using a polymomial basis often have smaller gaps in their weight distributions than those obtained by using a normal basis. Similar results apply to the number of intersections between codewords, which can be used to show that the codewords are orthogonal     

Universal decoding algorithm for binary quadratic residue codes using syndrome-weight determination

A novel decoding scheme, called syndrome-weight determination, was proposed by Chang et al. in 2008 for the Golay code, or the (23, 12, 7) quadratic residue code. This method is not only very simple in principle but also suitable for parallel hardware design. Presented is a modified version for any binary quadratic residue codes which has been developed. Because of its regular property, the proposed decoder is suitable for both software design and hardware development.     

Double circulant quadratic residue codes

We give a lower bound for the minimum distance of double circulant binary quadratic residue codes for primes p/spl equiv//spl plusmn/3(mod8). This bound improves on the square root bound obtained by Calderbank and Beenker, using a completely different technique. The key to our estimates is to apply a result by Helleseth, to which we give a new and shorter proof. Combining this result with the Weil bound leads to the improvement of the Calderbank and Beenker bound. For large primes p, their bound is of order /spl radic/(2p) while our new improved bound is of order 2/spl radic/p. The results can be extended to any prime power q and the modifications of the proofs are briefly indicated.     

Two quaternary quadratic residue codes

The weight distributions of the (13, 6) and the (17, 8) quaternary quadratic residue codes are computed.     

A performance comparison of the binary quadratic residue codes withthe 1/2-rate convolutional codes

The 1/2-rate binary quadratic residue (QR) codes, using binary phase-shift keyed (BPSK) modulation and hard decoding, are presented as an efficient system for reliable communication. Performance results of error correction are obtained both theoretically and by means of computer calculations for a number of binary QR codes. These results are compared with the commonly used 1/2-rate convolutional codes with constraint lengths from 3 to 7 for the hard-decision case. The binary QR codes of different lengths are shown to be equivalent in error-correction performance to some 1/2-rate convolutional codes, each of which has a constraint length K that corresponds to the error-control rate d/n and the minimum distance d of the QR codes     

On the minimum distance of some quadratic residue codes (Corresp.)

We find the minimum distances of the binary(113, 57), and ternary(37, 19), (61, 31), (71, 36), and(73, 37)quadratic residue codes and the corresponding extended codes. These distances are15, 10, 11, 17, and17, respectively, for the nonextended codes and are increased by one for the respective extended codes. We also characterize the minimum weight codewords for the(113, 57)binary code and its extended counterpart.     

The automorphism groups of the generalized quadratic residue codes

We give the full automorphism groups as groups of semiaffine transformations, of the extended generalized quadratic residue codes. We also present a proof of the Gleason-Prange theorem for the extended generalized quadratic residue codes that relies only on their definition and elementary theory of linear characters     

Odd weight symmetry in some binary codes (Corresp.)

If a linear binary code of lengthncontains the all-one codeword, than the weights of the code are symmetric. We consider those codes which do not contain the all-one codeword and yet have an equal number of symmetrically placed odd weight words.     

Weight distributions of some classes of binary cyclic codes (Corresp.)

Leth_1(x)h_2(x)be the parity-check polynomial of a binary cyclic code. This correspondence presents a formula for decomposing words in the code as sums of multiples of words in the codes whose parity-check polynomials areh_1(x)andh_2(x). This decomposition provides information about the weight distribution of the code.     

The weight hierarchies of some product codes

We determine the weight hierarchies of the product of an n-tuple space and an arbitrary code, the product of an m-dimensional even-weight code and the [24,12,8] extended Golay code, and the product of an m-dimensional even-weight code and the [8,4,4] extended Hamming code. The conjecture d_r=d*_r is proven for all three cases     

On the binary quadratic residue system with noncoprime moduli

The residue number system (RNS) appropriate for implementing fast digital signal processors since it can support parallel, carry-free, high-speed arithmetic. A development in residue arithmetic is the quadratic residue number system (QRNS), which can perform complex multiplications with only two integer multiplications instead of four. An RNS/QRNS is defined by a set of relatively prime integers, called the moduli set, where the choice of this set is one of the most important design considerations for RNS/QRNS systems. In order to maintain simple QRNS arithmetic, moduli sets with numbers of forms 2ⁿ+1 (n is even) have been considered. An efficient such set is the three-moduli set (2^2k-2+1.2^2k+1.2^2k+2+1) for odd k. However, if large dynamic ranges are desirable, QRNS systems with more than three relatively prime moduli must be considered. It is shown that if a QRNS set consists of more than four relatively prime moduli of forms 2ⁿ+1, the moduli selection process becomes inflexible and the arithmetic gets very unbalanced. The above problem can be solved if nonrelatively prime moduli are used. New multimoduli QRNS systems are presented that are based on nonrelatively prime moduli of forms 2ⁿ +1 (n even). The new systems allow flexible moduli selection process, very balanced arithmetic, and are appropriate for large dynamic ranges. For a given dynamic range, these new systems exhibit better speed performance than that of the three-moduli QRNS system     

A double circulant presentation for quadratic residue codes (Corresp.)

Forp eqiv pm 1 pmod{8}there are two binary codes,Q(p)andN(p), each an extended quadratic residue code of lengthp+1and dimension(p+1)/2. The existence of double circulant generator matrices for these codes is investigated. A possibly infinite family of primespis presented for whichQ(p)andN(p)must have double circulant generator matrices. Two counterexamples prove the construction is not always possible.     

No binary quadratic residue code of length 8m-1 is quasi-perfect

The class of binary quadratic residue (QR) codes of length n=8m-1 contains two perfect codes. These are the (7,4,3) Hamming code and the (23,12,7) Golay code. However, it is proved in the present paper that there are no quasi-perfect QR codes of length 8m-1. Finally, this result is generalized to all binary self-dual codes of length N>72     

An approximation to the weight distribution of binary linear codes

Binary primitive BCH codes form a large class of powerful error-correcting codes. The weight distributions of primitive BCH codes are unknown except for some special classes, such as the single, double, triple error-correcting codes and some very low-rate primitive BCH codes. However, asymptotic results for the weight distribution of a large subclass of primitive BCH codes have been derived by Sidel'nikov. These results provide some insight into the weight structure of primitive BCH codes. Sidel'nikov's approach is improved and applied to the weight distribution of any binary linear block code. Then Sidel'nikov's results on the weight distributions of binary primitive BCH codes are improved and it is shown that the weights of a binary primitive code have approximate binomial distribution.     

Construction of some binary linear codes of minimum distance five

A method of constructing binary linear codes that have a minimum Hamming distance of five is presented. The author proposes a general formulation of the parity check matrix for the desired code and then derives necessary conditions for the code to have a minimum distance of five. Some new codes that satisfy the necessary conditions are described. Some efficient new codes are obtained. In particular, a (47,36,5) code is obtained that has six more information bits than the best previously known code with 11 check bits     

On maximum likelihood soft decoding of some binary self-dual codes

Efficient algorithms are derived for maximum likelihood (ML) soft-decision decoding of some binary self-dual codes. A family of easily decodable self-dual codes is derived by modifying a known F₂₄, which has a weight distribution resembling that of the [24, 12, 8] Golay code G₂₄. The ML decoding of F₂₄ is accomplished by only 227 real additions, compared to 651 required for G₂₄, yet the error rates of the two decoders are similar for moderate noise conditions