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     

Constructions of error-correcting DC-free block codes

Two DC-free codes are presented with distance 2d, b ⩾1 length 2n+2r(d-1) for d⩽3 and length 2n+2r(d-1)(2d -1) for d>3, where r is the least integer ⩾log₂ (2n+1). For the first code l=4, c=2, and the asymptotic rate of this code is 0.7925. For the second code l=6, c=3, and the asymptotic rate of this code is 0.8858. Asymptotically, these rates achieve the channel capacity. For small values of n these codes do not achieve the best rate. As an example of codes of short length with good rate, the author presents a (30, 10, 6, 4) DC-free block code with 2²¹ codewords. A construction is presented for which from a given code C ₁ of length n, even weight, and distance 4, the author obtains a (4n, l, c, 4) DC-free block code C₂, where l is 4, 5 or 6, and c is not greater than n+1 (but usually significantly smaller). The codes obtained by this method have good rates for small lengths. The encoding and decoding procedures for all the codes are discussed     

On repeated-root cyclic codes

A parity-check matrix for a q-ary repeated-root cyclic code is derived using the Hasse derivative. Then the minimum distance of a q-ary repeated-root cyclic code is expressed in terms of the minimum distance of a certain simple-root cyclic code. With the help of this result, several binary repeated-root cyclic codes of lengths up to n=62 are shown to contain the largest known number of codewords for their given length and minimum distance. The relative minimum distance d_min/n of q-ary repeated-root cyclic codes of rate r⩾R is proven to tend to zero as the largest multiplicity of a root of the generator g(x) increases to infinity. It is further shown that repeated-root cycle codes cannot be asymptotically better than simple-root cyclic codes     

Weight enumerators of self-dual codes

Some construction techniques for self-dual codes are investigated, and the authors construct a singly-even self-dual [48,24,10]-code with a weight enumerator that was not known to be attainable. It is shown that there exists a singly-even self-dual code C' of length n =48 and minimum weight d=10 whose weight enumerator is prescribed in the work of J.H. Conway et al. (see ibid., vol.36, no.5, p.1319-33, 1990). Two self-dual codes of length n are called neighbors, provided their intersection is a code of dimension (n/2)-1. The code C' is a neighbor of the extended quadratic residue code of length 48     

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     

Fast decoding of codes from algebraic plane curves

Improvement to an earlier decoding algorithm for codes from algebraic geometry is presented. For codes from an arbitrary regular plane curve the authors correct up to d*/2-m² /8+m/4-9/8 errors, where d* is the designed distance of the code and m is the degree of the curve. The complexity of finding the error locator is O(n^7/3 ), where n is the length of the code. For codes from Hermitian curves the complexity of finding the error values, given the error locator, is O(n²), and the same complexity can be obtained in the general case if only d*/2-m²/2 errors are corrected     

Achieving the designed error capacity in decodingalgebraic-geometric codes

A decoding algorithm for codes arising from algebraic curves explicitly constructable by Goppa's construction is presented. Any configuration up to the greatest integer less than or equal to (d *-1)/2 errors is corrected by the algorithm whenever d*⩾6g, where d* is the designed minimum distance of the code and g is the genus of the curve. The algorithm's complexity is at most O((d*)² n), where n denotes the length of the code. Application to Hermitian codes and connections with well-known algorithms are explained     

Bounds on the undetected error probabilities of linear codes forboth error correction and detection

The author investigates the (n, k, d⩾2t+1) binary linear codes, which are used for correcting error patterns of weight at most t and detecting other error patterns over a binary symmetric channel. In particular, for t=1, it is shown that there exists one code whose probability of undetected errors is upper-bounded by (n+1) [2^n-k-n]^-1 when used on a binary symmetric channel with transition probability less than 2/n     

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     

Bounds for abnormal binary codes with covering radius one

The normality of binary codes is studied. The minimum cardinality of a binary code of length n with covering radius R is denoted by K(n,R). It is assumed that C is an (n,M)R code, that is, a binary code of length n with M codewords and covering radius R. It is shown that if C is an (n,M)1 code, then it is easy to find a normal (n ,M)1 code by changing C in a suitable way, and that all the optimal (n,M)1 codes (i.e. those for which M=K(n,1)) are normal and their every coordinate is acceptable. It is shown that if C is an abnormal (n,M) code, then n⩾9, and an abnormal (9118)1 code which is the smallest abnormal code known at present, is constructed. Lower bounds on the minimum cardinality of a binary abnormal code of length n with covering radius 1 are derived, and it is shown that if an (n,M)1 code is abnormal, then M⩾96     

Balancing sets of vectors

For n>0, d⩾0, n≡d (mod 2), let K(n, d) denote the minimal cardinality of a family V of ±1 vectors of dimension n, such that for any ±1 vector w of dimension n there is a v∈V such that |v- w|⩽d, where v-w is the usual scalar product of v and w. A generalization of a simple construction due to D.E. Knuth (1986) shows that K(n , d)⩽[n/(d+1)]. A linear algebra proof is given here that this construction is optimal, so that K(n, d)-[n/(d+1)] for all n≡d (mod 2). This construction and its extensions have applications to communication theory, especially to the construction of signal sets for optical data links     

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     

On the decoding of algebraic-geometric codes

A decoding algorithm for algebraic-geometric codes arising from arbitrary algebraic curves is presented. This algorithm corrects any number of errors up to [(d-g-1)/2], where d is the designed distance of the code and g is the genus of the curve. The complexity of decoding equals σ(n³) where n is the length of the code. Also presented is a modification of this algorithm, which in the case of elliptic and hyperelliptic curves is able to correct [(d-1)/2] errors. It is shown that for some codes based on plane curves the modified decoding algorithm corrects approximately d/2-g/4 errors. Asymptotically good q-ary codes with a polynomial construction and a polynomial decoding algorithm (for q⩾361 on some segment their parameters are better than the Gilbert-Varshamov bound) are obtained. A family of asymptotically good binary codes with polynomial construction and polynomial decoding is also obtained, whose parameters are better than the Blokh-Zyablov bound on the whole interval 0<σ<1/2     

On the decoding of algebraic-geometric codes over Fq forq⩾16

It is proved that for algebraic-geometric codes on a curve over F _q for q⩾37 or on a curve of sufficiently large genus over F_q for q⩾16 there exists a polynomial decoding algorithm up to (d*-1)/2 errors, d* being the designed minimum distance     

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     

A (16, 9, 6, 5, 4) error-correcting DC free block code

A (2n, k, l, c, d) DC free binary block code is a code of length 2n, constant weight n, 2^k codewords, maximum runlength of a symbol l , maximum accumulated charge c, and minimum distance d . The purpose of this code is to achieve DC freeness and error correction at the same time. The goal is to keep the rate k/2 n and d large and l and c small. Of course, these are conflicting goals. H.C. Ferreira (IEEE Trans. Magn., vol.MAG-20, no.5, p.881-3, 1984) presented a (16, 8, 8, 5, 4) DC free code. Here, a (16, 9, 6, 5, 4) DC free code is presented. Easy encoding and decoding algorithms are also given     

The free distance of fixed convolutional rate 2/4 codes meets theCostello bound

The long standing question whether the free distance of fixed rate convolutional codes is as good as the Costello bound was almost solved by K.S. Zigangirov and J.L. Massey (1987). They proved that this is indeed the case for codes with long branch length and rates 2/c, c⩾5. It is shown that there exist fixed convolutional codes of rate 2/4 whose free distance d_free meets the Costello bound originally derived for time varying convolutional codes     

Decoding geometric Goppa codes using an extra place

Decoding geometric Goppa codes can be reduced to solving the key congruence of a received word in an affine ring. If the codelength is smaller than the number of rational points on the curve, then this method can correct up to 1.2 (d*-L)/2-s errors, where d* is the designed minimum distance of the code and s is the Clifford defect. The affine ring with respect to a place P is the set of all rational functions which have no poles except at P, and it is somehow similar to a polynomial ring. For a special kind of geometric Goppa code, namely C_Ω(D,mP), the decoding algorithm is reduced to solving the key equation in the affine ring, which can be carried out by the subresultant sequence in the affine ring with complexity O(n³), where n is the length of codewords     

On the weight distribution of linear codes having dual distanced'⩾k

Using only the principle of inclusion and exclusion, the author derives a formula for the weight distribution of an [n,k ] code whose dual code has a minimum distance d'⩾k . The result yields a new condition on the weight distributions of a linear code and its dual which is necessary and sufficient for the code to be a maximum distance separable (MDS) code. Moreover, it shows how the weight distribution for linear MDS codes is obtained in an elementary manner