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     

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     

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

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     

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     

On the influence of coding on the mean time to failure fordegrading memories with defects

The application of a combined test-error-correcting procedure is studied to improve the mean time to failure (MTTF) for degrading memory systems with defects. The degradation is characterized by the probability p that within a unit of time a memory cell changes from the operational state to the permanent defect state. Bounds are given on the MTTF and it is shown that, for memories with N words of k information bits, coding gives an improvement in MTTF proportional to (k/n) N(d_min^-2)/(d_min ^-1), where d_min and (k/n) are the minimum distance and the efficiency of the code used, respectively. Thus the time gain for a simple minimum-distance-3 is proportional to N^-1. A memory word test is combined with a simple defect-matching code. This yields reliable operation with one defect in a word of length k+2 at a code efficiency k/(k+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     

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     

Limiting efficiencies of burst-correcting array codes

The author evaluates the limiting efficiencies e(-S ) of burst-correcting array codes A(n₁,n₂, -s) for all negative readouts -s as n₂ tends to infinity and n₁ is properly chosen to maximize the efficiency. Specializing the result to the products of the first i primes donated by s_i (1⩽i<∞), which are optimal choices for readouts, gives the expression e(-s_i)=(2p_i+1 -2)/(2p_i+1-1) where p_i+1 is the next prime. Previously, it was known only that e(-2)⩾4/5 and e(-1)⩾2/3. This result reveals the existence of burst-correcting array codes with efficiencies arbitrarily close to 1 and with rates also arbitrarily close to 1     

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     

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     

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     

Decoding algebraic-geometric codes up to the designed minimumdistance

A simple decoding procedure for algebraic-geometric codes C _Ω(D,G) is presented. This decoding procedure is a generalization of Peterson's decoding procedure for the BCH codes. It can be used to correct any [(d*-1)/2] or fewer errors with complexity O(n³), where d * is the designed minimum distance of the algebraic-geometric code and n is the codelength     

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     

Capacity of the Gaussian arbitrarily varying channel

The Gaussian arbitrarily varying channel with input constraint Γ and state constraint Λ admits input sequences x=(x₁,---,X_n) of real numbers with Σx_i²⩽nΓ and state sequences s=(S₁,---,s_n ) of real numbers with Σs_i²⩽nΛ; the output sequence x+s+V, where V=(V₁,---,V_n) is a sequence of independent and identically distributed Gaussian random variables with mean 0 and variance σ². It is proved that the capacity of this arbitrarily varying channel for deterministic codes and the average probability of error criterion equals 1/2 log (1+Γ/(Λ+σ²)) if Λ<Γ and is 0 otherwise     

A strengthening of the Assmus-Mattson theorem

Let w₁=d,w₂,…,w _s be the weights of the nonzero codewords in a binary linear [n,k,d] code C, and let w' ₁, w'₂, …, w'₃, be the nonzero weights in the dual code C1. Let t be an integer in the range 0<t<d such that there are at most d-t weights w'_i with 0<w'_i ⩽n-t E. F. Assmus and H. F. Mattson, Jr. (1969) proved that the words of any weight w_i in C form a t-design. The authors show that if w₂⩾d+4 then either the words of any nonzero weight w_i form a (t+1)-design or else the codewords of minimal weight d form a {1,2,…,t,t+2}-design. If in addition C is self-dual with all weights divisible by 4 then the codewords of any given weight w_i form either a (t +1)-design or a {1,2,…,t,t+2}-design. The proof avoids the use of modular forms