New multilevel codes over GF(q)

Set partitioning is applied to multidimensional signal spaces over GF(q), i.e., GFⁿ¹(q) (n1⩽q ), and it is shown how to construct both multilevel block codes and multilevel trellis codes over GF(q). Multilevel (n, k, d) block codes over GF(q) with block length n, number of information symbols k, and minimum distance d_min⩾d are presented. These codes use Reed-Solomon codes as component codes. Longer multilevel block codes are also constructed using q-ary block codes with block length longer than q+1 as component codes. Some quaternary multilevel block codes are presented with the same length and number of information symbols as, but larger distance than, the best previously known quaternary one-level block codes. It is proved that if all the component block codes are linear. the multilevel block code is also linear. Low-rate q-ary convolutional codes, word-error-correcting convolutional codes, and binary-to-q-ary convolutional codes can also be used to construct multilevel trellis codes over GF(q) or binary-to-q-ary trellis codes     

On the existence of optimum cyclic burst correcting codes over GF(q)

A cyclic b-burst correcting code over GF(q) of redundancy r and length n=(q^r-b+1-1)/(q-1) is said to be optimum. It is proved that a necessary condition for the existence of such a code is the existence of a square-free polynomial in GF(q)[x] of degree b-1 which is not divisible by x such that its period and the degrees of its irreducible factors are relatively prime to q-1. Moreover, if such a polynomial exists, then there are an infinite number of optimum cyclic b-burst correcting codes over GF(q)     

Composition of Reed-Solomon codes and geometric designs

It is shown that good linear (n,k,d) codes over a finite field GF(q) can be constructed by concatenating the generator matrices of Reed-Solomon codes. For the case of k=3, it is shown that many of the codes obtained using projective-geometry techniques can readily be obtained by the proposed algebraic approach     

A construction of non-Reed-Solomon type MDS codes

A construction is presented of long maximum-distance-separable (MDS) codes that are not generalized Reed-Solomon (GRS) type. The construction uses subsets S,|S|=m of a finite field F=GF(q) with the property that no t distinct elements of S add up to some fixed element of F . Large subsets of this kind are used to construct [n=m+2, k=t+1] non-GRS MDS codes over F     

Identities and approximations for the weight distribution of q-ary codes

An explicit formula is derived that enumerates the complete weight distribution of an (n, k, d) linear code using a partially known weight distribution. An approximation formula for the weight distribution of q-ary linear (n, k , d) codes is also derived. It is shown that, for a given q-ary linear (n, k, d) code, the ratio of the number of codewords of weight u to the number of words of weight u approaches the constant Q=q ^-(n-k) as u becomes large. The error term is a decreasing function of the minimum weight of the dual. The results are also valid for nonlinear (n, M, d) codes with the minimum weight of the dual replaced by the dual distance     

Binary linear quasi-perfect codes are normal

Whether quasi-perfect codes are normal is addressed. Let C be a code of length n, dimension k, covering radius R, and minimal distance d. It is proved that C is normal if d⩾2R-1. Hence all quasi-perfect codes are normal. Consequently, any [n,k ]R binary linear code with minimal distance d⩾2R-1 is normal     

Invariant permutations for consecutive k-out-of-ncycles

Consecutive-k-out-of-n cycles are proposed as topologies for k-loop computer networks and describe a circular system of n components where the system fails if and only if any k consecutive components all fail. Suppose that the components are interchangeable. The the question arises as to which permutation maximizes the system reliability, assuming that the components have unequal reliabilities. If there exists on optimal permutation which depends on the ordering, but not the values, of the component reliabilities, then the system (and the permutation) is called invariant. The circular system is found to be not invariant except for k=1, 2, n-2, n-1, and n     

A burst-error-correcting algorithm for Reed-Solomon codes

It is known that for a burst-error environment, the error-correcting capability of Reed-Solomon codes can be extended beyond the Singleton bound with a high degree of confidence. This is significant in that an (n, k) code with an arbitrarily small probability of a miscorrection can correct more than (n- k)/2 errors. A decoding algorithm for correcting a burst of length greater than (n-k)/2 is presented     

Reliability of a consecutivek-out-of-r-from-n:F system

The reliability of the consecutive k-out-of-r-from-n:F system is studied. For k=2 an explicit solution is given for n components in line or in cycle in the i.i.d. case. For k⩾3 sharp lower and upper bounds are given for the reliability of the system and demonstrated for different values of n, k, r, p. These bounds are exact for r=n, n-1, n-2, n-3, and for these values the exact analytic solution is also given     

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     

On (k, t)-subnormal covering codes

The concept of a (k, t)-subnormal covering code is defined. It is discussed how an amalgamated-direct-sumlike construction can be used to combine such codes. The existence of optimal (q, n, M) 1 codes C is discussed such that by puncturing the first coordinate of C one obtains a code with (q, 1)-subnorm 2     

Optimum codes of dimension 3 and 4 over GF(4)

n_q(k,d), the length of a q-ary optimum code for given k and d, for q=4 and k=3, 4 is discussed. The problem is completely solved for k=3, and the exact value of n₄(4,d) is determined for all but 52 values of d     

Optimal codes for minimax criterion on error detection

Nonlinear quadratic codes that are optimal for the minimax error detection are presented. Characteristic functions for these codes are asymptotically bent. For a given block size n and the number of codewords |C|, these codes minimize max Q(e), e≠0, where Q(e) is the conditional error-masking probability, given the error pattern e. The codewords are blocks of n symbols from GF(q). Encoding and decoding procedures for the codes are described     

Some new upper bounds on the covering radius of binary linear codes

A Griesmer-like upper bound on the covering radius, R, is given. To the author's knowledge this is the only upper bound which explicitly depends on all three parameters n, k, and d. An upper bound on R for cyclic codes is then given which depends on the generator polynomial of the cyclic code and which, in many cases, leads to an improvement of the previous bound. An upper bound on the irreducible generator polynomial cyclic codes is also given. New interpretations and applications of the so-called Norse bounds and necessary and sufficient conditions to attain one of these bounds are provided. Generalizations of most of the results for codes over GF(q) are outlined     

Binary [18,11]2 codes do not exist-Nor do [64,53]2 codes

A binary, linear block code C with block length n and dimension n is commonly denoted by [n, k] or, if its minimum distance is d, by [n, k,d]. The code's covering radius r(C) can be defined as the smallest number r such that any binary column vector of length (n-k) can be written as a sum of r or fewer columns of a parity-check matrix of C. An [n,k] code with covering radius r is denoted by [n,k]r. R.A. Brualdi et al., (1989) showed that l(m,r) is defined to be the smallest n such that an [n,n-m]r code exists. l(m,2) is known for m⩽6, while it is shown by Brualdi et al. that 17⩽l(7,2)⩽19. This lower bound is improved by A.R. Calderbank et al. (1988), where it is shown that [17,10]2 codes do not exist. The nonexistence of [18,11]2 codes is proved, so that l(7,2)=19. l[7.2)=19 is established by showing that [18,11]2 codes do not exist. It is also shown that [64,53]2 codes do not exist, implying that l(11,2)⩾65     

New lower bounds for covering codes

Some new lower bounds on |C| for a binary linear [n, k]R code C with n+1=t(R +1)-r(0⩽r<R+1, t>2 odd) or with n+1=t(R+1)-1(t>2 even) are obtained. These bounds improve the sphere covering bound considerably and give several new values and lower bounds for the function t[n, k], the smallest covering radius of any [n, k] code     

Relationships between m-sequences over GF(q) andGF(qm)

It is shown that m-sequences over GF(q^m ) of length q^nm-1 corresponding to primitive polynomials in GF[q^m,x] of degree n can be generated from known m-sequences over GF(q) of length q^nm-1 obtained from primitive polynomials in GF[q,x] of degree mn. A procedure for generating the m-sequences over GF(q²) from m-sequences over GF(q) was given which enables the generation of m-sequences over GF( p²ⁿ). In addition it was shown that all of the primitive polynomials in GF[q,^m,x] can be obtained from a complete set of the primitive polynomials in GF[q ,x]     

A general decoding technique applicable to replicated filedisagreement location and concatenated code decoding

Code symbols are treated as vectors in an r-dimensional vector space F^r over a field F. Given any ( n, k) linear block code over F with minimum distance d, it is possible to derive an (n, k) code with symbols over F^r, also with minimum distance d, which can correct any pattern of d-2 or fewer symbol errors for which the symbol errors as vectors are linearly independent. This is about twice the bound on the number of errors guaranteed to be correctable. Furthermore, if the error vectors are linearly dependent and d-2 or fewer in number, the existence of dependence can always be detected. A decoding techinque is described for which complexity increases no greater than as n ³, for any choice of code. For the two applications considered, situations are described where the probability of the error patterns being linearly dependent decreases exponentially with r     

New minimum distance bounds for certain binary linear codes

Let an [n, k, d]-code denote a binary linear code of length n, dimension k, and minimum distance at least d. Define d(n, k) as the maximum value of d for which there exists a binary linear [n, k, d]-code. T. Verhoeff (1989) has provided an updated table of bounds on d(n, k) for 1⩽k⩽n⩽127. The authors improve on some of the upper bounds given in that table by proving the nonexistence of codes with certain parameters