A new upper bound on the minimal distance of self-dual codes

It is shown that the minimal distance d of a binary self-dual code of length n⩾74 is at most 2[(n+6)/10]. This bound is a consequence of some new conditions on the weight enumerator of a self-dual code obtained by considering a particular translate of the code, called its shadow. These conditions also enable one to find the highest possible minimal distance of a self-dual code for all n⩾60; to show that self-dual codes with d⩽6 exist precisely for n⩾22, with d ⩾8 exist precisely for n=24, 32 and n⩾26, and with d⩾10 exist precisely for n⩾46; and to show that there are exactly eight self-dual codes of length 32 with d=8. Several of the self-dual codes of length 34 have trivial group (this appears to be the smallest length where this can happen)     

Studying the locator polynomials of minimum weight codewords of BCHcodes

Primitive binary cyclic codes of length n=2^m are considered. A BCH code with designed distance δ is denoted B(n,δ). A BCH code is always a narrow-sense BCH code. A codeword is identified with its locator polynomial, whose coefficients are the symmetric functions of the locators. The definition of the code by its zeros-set involves some properties for the power sums of the locators. Moreover, the symmetric functions and the power sums of the locators are related to Newton's identities. An algebraic point of view is presented in order to prove or disprove the existence of words of a given weight in a code. The principal result is the true minimum distance of some BCH codes of length 255 and 511. which were not known. The minimum weight codewords of the codes B(n2^h -1) are studied. It is proved that the set of the minimum weight codewords of the BCH code B(n,2^m-2-1) equals the set of the minimum weight codewords of the punctured Reed-Muller code of length n and order 2, for any m     

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     

A convolutional single-parity-check concatenated coding scheme forhigh-data-rate applications

The coding scheme uses a set of n convolutional codes multiplexed into an inner code and a (n,n-1) single-parity-check code serving as the outer code. Each of the inner convolutional codes is decoded independently, with maximum-likelihood decoding being achieved using n parallel implementations of the Viterbi algorithm. The Viterbi decoding is followed by additional outer soft-decision single-parity-check decoding. Considering n=12 and the set of short constraint length K=3, rate 1/2 convolutional codes, it is shown that the performance of the concatenated scheme is comparable to the performance of the constraint length K=7, rate 1/2 convolutional code with standard soft-decision Viterbi decoding. Simulation results are presented for the K=3, rate 1/2 as well as for the punctured K=3, rate 2/3 and rate 3/4 inner convolutional codes. The performance of the proposed concatenated scheme using a set of K=7, rate 1/2 inner convolutional codes is given     

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     

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     

New ternary line codes based on trellis structure

The trellis coding technique is applied to line-coded baseband digital transmission systems. For R=n/n+1(n=1,2,3) coding rates, a new codeword assignment model is proposed to accomplish basic requirements for line coding in which each length n binary data sequence is encoded into a length n+1 ternary (+,0,-) line codeword chosen among the code alphabet with 2ⁿ⁺² elements. Assuming Viterbi decoding, the system error performance is improved by increasing the free Euclidean distance between coded sequences. A new algorithm is given for the calculation of the free distance between line-coded sequences so obtained. For R=1/2 and R=3/4 rates, the analytical error performance upper bounds are derived. The power spectral densities of the new line codes are also calculated and compared with those of known line codes     

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     

Pseudocyclic maximum-distance-separable codes

The (n, k) pseudocyclic maximum-distance-separable (MDS) codes modulo (xⁿ- a) over GF(q) are considered. Suppose that n is a divisor of q+1. If n is odd, pseudocyclic MDS codes exist for all k. However, if n is even, nontrivial pseudocyclic MDS codes exist for odd k (but not for even k) if a is a quadratic residue in GF(q), and they exist for even k (but not for odd k) if a is not a quadratic residue in GF(q). Also considered is the case when n is a divisor of q-1, and it is shown that pseudocyclic MDS codes exist if and only if the multiplicative order of a divides (q-1)/n, and that when this condition is satisfied, such codes exist for all k. If the condition is not satisfied, every pseudocyclic code of length n is the result of interleaving a shorter pseudocyclic code     

Computing the probability of undetected error for shortened cycliccodes

The authors present a general technique for computing P _e for all possible shortened versions of cyclic codes generated by any given polynomial. The technique is recursive, i.e. computes P_e for a given code block length n from that of the code block length n-1. The proposed computation technique for determining P_e does not require knowledge of the code weight distributions. For a generator polynomial of degree r, and |g| nonzero coefficients, the technique yields P_e for all code block lengths up to length n in time complexity O(n|g |2^r+|g|). Channels with variable bit error probabilities can be analyzed with the same complexity. This enables the performance of the code generator polynomials to be analyzed for burst errors     

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     

Index system and separability of constant weight Gray codes

A number system is developed for the conversion of natural numbers to the codewords of the Gray code G(n,k) of length n and weight k, and vice versa. The focus is on the subcode G(n,k) of G(n) consisting of those words of G(n) with precisely k 1-bits, 0<k<n. This code is called the constant weight Gray code of length n and weight k. As an application sharp lower and upper bounds are derived for the value of |i-j|, where i and j are indices of codewords g_i and g_j of G(n,k) such that they differ in precisely 2 m bits     

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 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 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     

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     

Maximum-rank array codes and their application to crisscross errorcorrection

A μ-[n×n,k] array code C over a field F is a k-dimensional linear space of n×n matrices over F such that every nonzero matrix in C has rank ⩾μ. It is first shown that the dimension of such array codes must satisfy the Singleton-like bound k⩽n(n-μ+1). A family of so-called maximum-rank μ-[n×n,k=n ( n-μ+1)] array codes is then constructed over every finite field F and for every n and μ, 1⩽μ⩽n . A decoding algorithm is presented for retrieving every Γ∈C, given a received array Γ+E, where rank (E)+1⩽(μ-1)/2. Maximum-rank array codes can be used for decoding crisscross errors in n×n bit arrays, where the erroneous bits are confined to a number t of rows or columns (or both). This construction proves to be optimal also for this model of errors. It is shown that the behavior of linear spaces of matrices is quite unique compared with the more general case of linear spaces of n×n. . .×n hyper-arrays     

Construction of t-EC/AUED codes

A t-EC/AUED code is constructed by appending a single check symbol from an alphabet S to each word of an n-bit binary t-EC code of even weight. Conditions are derived for the construction of S and a procedure is given which, for some values of t, n, leads to codes with fewer check bits than known codes with equivalent properties