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.     

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.     

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     

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.     

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.     

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.     

Generalized burst-trapping codes

The burst-trapping error control technique developed by Tong [1] corrects both random and burst errors adaptively. A generalization of this scheme, called generalized burst trapping (GBT), is presented here. Generalized burst-trapping codes (GBTC) also correct both random and burst errors adaptively but, in addition, are capable of correcting random errors in the guard space following a correctable burst. This added capability is obtained at the expense of a longer guard space or a lower rate and a modest increase in complexity of implementation. Nevertheless, these codes are simple to encode and decode and, in particular, the storage-saving technique used with the original burst-trapping codes is directly applicable to the generalized codes. Also it is shown that at most one block of error propagation can occur if a simple and reasonable condition is met. Thus the generalized codes have better propagation properties than the original burst-trapping codes. This new error control technique is well suited to error correction on channels where it cannot be assumed that bursts are isolated events separated by error-free intervals. Thus, for example, this technique appears well suited to error correction on telephone facilities that incorporate multiple-level signaling.     

Generalized multiplication-free arithmetic codes

Arithmetic coding is a highly efficient lossless source coding technique. Multiplication-free arithmetic coding algorithms provide an excellent tradeoff between operation complexity and coding performance. A whole family of multiplication-free arithmetic codes, which achieve the best coding efficiency and can be used for arbitrary size of alphabets, is derived. The complete tradeoff between the complexity of operations and compression performance of all the algorithms is presented     

Generalized punctured convolutional codes

This letter introduces the class of generalized punctured convolutional codes (GPCCs), which is broader than and encompasses the class of the standard punctured convolutional codes (PCCs). A code in this class can be represented by a trellis module, the GPCC trellis module, whose topology resembles that of the minimal trellis module. he GPCC trellis module for a PCC is isomorphic to the minimal trellis module. A list containing GPCCs with better distance spectrum than the best known PCCs with same code rate and trellis complexity is presented.     

Generalized tensor product codes

A class of binary error-correcting codes, called generalized tensor product codes, is presented with their decoding algorithm. These codes are constructed by combining a number of codes on various extension fields with shorter binary codes. A general algorithm is provided to do bounded distance decoding for these codes. Simply decodable codes such as Wolf's tensor product codes are shown to be special cases of this class of codes. Simply decodable and more efficient codes than Wolf's codes are also included as special cases.     

Gray codes and 1D quadratic maps

The authors show how the symbolic sequences of same period superstable orbits in 1D quadratic maps are ordered according to Gray codes. Next, the Gray ordering number is introduced, in the interval (0, 1), allowing the simultaneous ordering of symbolic sequences of different period superstable orbits. Likewise, it is shown that Gray ordering number manipulation can determine whether or not a given symbolic sequence exists     

Convolutions over residue classes of quadratic integers

A Fourier-like transform is defined over a ring of quadratic integers modulo a prime numberqin the quadratic fieldR(sqrt{m}), wheremis a square-free integer. Ifqis a Fermat prime, one can utilize the fast Fourier transform (FFT) algorithm over the resulting finite fields to yield fast convolutions of quadratic integer sequences inR(sqrt{m}). The theory is also extended to a direct sum of such finite fields. From these results, it is shown that Fourier-like transforms can also be defined over the quadratic integers inR( sqrt{m})modulo a nonprime Fermat number.     

Generalized quadratic minimization and blind multichanneldeconvolution

This paper deals with the problem of quadratic minimization subject to linear equality constraints. Unlike the standard formulation, we assume the most general case of a possibly singular quadratic form. We explain that the existing formal solution to this problem has several drawbacks. Our new approach is free from most of these drawbacks. In particular, it has a simple interpretation and is relatively easy to implement. The practical importance of this result lies in its numerous applications: filter design, spectral analysis, direction finding, and blind deconvolution of multiple FIR channels. Here, we focus on the blind deconvolution application for which we present a novel solution with enhanced performance     

A note on extended quadratic residue codes overGF(9)and their ternary images (Corresp.)

We discuss[2(p + 1), p + 1]double circulant codes which are the ternary images of the[p + 1,(p + 1)/2]extended quadratic residue codes over GF(9). Herepis a prime of the formp = 12k pm 5. As a special result we obtain a[64, 32,18]ternary self-dual code which is the largest known code meeting the bound of Mallows and Sloane.     

Lattice constellations and codes from quadratic number fields

We propose new classes of linear codes over integer rings of quadratic extensions of Q, the field of rational numbers. The codes are considered with respect to a Mannheim metric, which is a Manhattan metric module a two-dimensional (2-D) grid, in particular, codes over Gaussian integers and Eisenstein-Jacobi integers are extensively studied. Decoding algorithms are proposed for these codes when up to two coordinates of a transmitted code vector are affected by errors of arbitrary Mannheim weight. Moreover, we show that the proposed codes are maximum-distance separable (MDS), with respect to the Hamming distance. The practical interest in such Mannheim-metric codes is their use in coded modulation schemes based on quadrature amplitude modulation (QAM)-type constellations, for which neither the Hamming nor the Lee metric is appropriate     

Generalized threshold decoding of linear codes

It is proved that every linear code of dimensionkcan be decoded by a threshold decoding circuit that is guaranteed to correcteerrors ife leq (d - 1)/2wheredis the minimum distance of the code. Moreover it is demonstrated that the number of levels of threshold logic is less than or equal tokby giving an algorithm for generating the decoding logic employingklevels.     

Generalized Hamming weights of linear codes

The generalized Hamming weight, d_r(C), of a binary linear code C is the size of the smallest support of any r-dimensional subcode of C. The parameter d_r(C) determines the code's performance on the wire-tap channel of Type II. Bounds on d_r(C), and in some cases exact expressions, are derived. In particular, a generalized Griesmer bound for d_r(C) is presented and examples are given of codes meeting this bound with equality     

Generalized threshold decoding of convolutional codes

A one-step threshold decoding method previously presented for cyclic block codes is shown to apply generally to linear convolutional codes. It is further shown that this method generalizes in a natural way to allow decoding of the received sequence in its unquantized analog form.