Improving the Gilbert-Varshamov bound for q-ary codes

Given positive integers q,n, and d, denote by A/sub q/(n,d) the maximum size of a q-ary code of length n and minimum distance d. The famous Gilbert-Varshamov bound asserts that A/sub q/(n,d+1)/spl ges/q/sup n//V/sub q/(n,d) where V/sub q/(n,d)=/spl Sigma//sub i=0//sup d/ (/sub i//sup n/)(q-1)/sup i/ is the volume of a q-ary sphere of radius d. Extending a recent work of Jiang and Vardy on binary codes, we show that for any positive constant /spl alpha/ less than (q-1)/q there is a positive constant c such that for d/spl les//spl alpha/n A/sub q/(n,d+1)/spl ges/cq/sup n//V/sub q/(n,d)n. This confirms a conjecture by Jiang and Vardy.     

The parity check codes through geometric Goppa codes.

This work treats a way to obtain the parity check codes through geometric Goppa codes. Two cases have been considered depending on the taken field characteristic as alphabet and on the code length. It has been used the technique of linear code restriction. More precisely, it has been showed that the parity check codes are obtained as the restriction of a rational geometric Goppa code.     

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     

When are two geometric Goppa codes equal?

Sufficient and necessary conditions are obtained for which the geometric Goppa codes C(D,G) and C( D,H) are equal for two divisors G and H . In particular, it is proven that if G and H are two effective divisors of the same degree smaller than n-1, then C(D,G) and C(D,H ) are equal, if and only if G=H     

Gilbert-Varshamov bound for Euclidean space codes overdistance-uniform signal sets

In this correspondence, in an extension of Piret's bound for codes over phase-shift keying (PSK) signal sets, we investigate the application of the Gilbert-Varshamov (GV) bound to a variety of distance-uniform (DU) signal sets in Euclidean space. It is shown that four-dimensional signal sets matched to binary tetrahedral, binary octahedral, and binary icosahedral groups lead to better bounds compared to the bounds for signal sets matched to dicyclic groups with the same number of signal points and comparable symmetric PSK signal sets     

Long nonbinary codes exceeding the Gilbert-Varshamov bound for any fixed distance

Let A(q,n,d) denote the maximum size of a q-ary code of length n and distance d. We study the minimum asymptotic redundancy as n grows while q and d are fixed. For any d and q/spl ges/d-1, long algebraic codes are designed that improve on the Bose-Chaudhuri-Hocquenghem (BCH) codes and have the lowest asymptotic redundancy known to date. Prior to this work, codes of fixed distance that asymptotically surpass BCH codes and the Gilbert-Varshamov bound were designed only for distances 4,5, and 6.     

Asymptotic improvement of the Gilbert-Varshamov bound on the size of binary codes

Given positive integers n and d, let A/sub 2/(n,d) denote the maximum size of a binary code of length n and minimum distance d. The well-known Gilbert-Varshamov bound asserts that A/sub 2/(n,d)/spl ges/2/sup n//V(n,d-l), where V(n,d) = /spl sigma//sub i=0//sup d/(/sub i//sup n/) is the volume of a Hamming sphere of radius d. We show that, in fact, there exists a positive constant c such that A/sub 2/(n, d)/spl ges/c2/sup n//V(n,d-1)log/sub 2/V(n, d-1) whenever d/n/spl les/0.499. The result follows by recasting the Gilbert-Varshamov bound into a graph-theoretic framework and using the fact that the corresponding graph is locally sparse. Generalizations and extensions of this result are briefly discussed.     

Intersecting Goppa codes

Bounds on the rates of intersecting Goppa codes are derived and compared with previous bounds on intersecting codes. Intersecting, self-intersecting, and highly intersecting Goppa codes are discussed in detail. It is shown that asymptotically good intersecting Goppa codes exist and lower bounds are given on their rates. Six theorems for Goppa codes are also presented     

Lengthening and the Gilbert-Varshamov bound

We use lengthening and an enhanced version of the Gilbert-Varshamov lower bound for linear codes to construct a large number of record-breaking codes. Our main theorem may be seen as a closure operation on databases     

A new lower bound for the minimum distance of binary Goppa codes

Binary Goppa codes are a large and powerful family of error-correcting codes. But how to find the true minimum distance of binary Goppa codes is not solved yet. In this paper a new lower bound for the minimum distance of binary Goppa codes is shown. This new lower bound improves the results in Y. Sugiyama (1976) and Feng Guiliang's (1983) papers. The method in this paper can be generalized to other Goppa codes easily.     

A Gilbert-Varshamov bound for quasi-cycle codes of rate 1/2 (Corresp.)

It is shown that there exist arbitrarily long quasi-cyclic(2k,k)binary codes that meet a bound slightly weaker than the Gilbert-Varshamov bound. This is a refinement of the result of Chen, Peterson, and Weldon [1].     

Improved Gilbert-Varshamov bound for constrained systems

Nonconstructive existence results are obtained for block error-correcting codes whose codewords lie in a given constrained system. Each such system is defined as a set of words obtained by reading the labels of a finite directed labeled graph. For a prescribed constrained system and relative minimum distance δ, the new lower bounds on the rate of such codes improve on those derived recently by V.D. Kolesnik and V.Y. Krachkovsky (1991). The better bounds are achieved by considering a special subclass of sequences in the constrained system, namely, those having certain empirical statistics determined by δ     

Parameters of Goppa codes revisited

We discuss parameters of Goppa (1970) codes, such as minimum distance, covering radius, distance distribution, and generalized Hamming weights. By a variation on the exponential sums method and combinatorial arguments, we sharpen known bounds on these parameters     

Goppa codes and trace operator

We study Goppa codes, Γ(L,g), defined by the polynomial g(z)=a(z)TrF_pms:F_ps(b(z)). It is shown that the dimension of these codes never reaches the general, well-known, bound for Goppa codes. New bounds are proposed depending on the value of m and p. Furthermore, we prove that when p=2 these codes have only even weights     

The algebraic decoding of Goppa codes

An interesting class of linear error-correcting codes has been found by Goppa [3], [4]. This paper presents algebraic decoding algorithms for the Goppa codes. These algorithms are only a little more complex than Berlekamp's well-known algorithm for BCH codes and, in fact, make essential use of his procedure. Hence the cost of decoding a Goppa code is similar to the cost of decoding a BCH code of comparable block length.     

Exponential sums and Goppa codes. II

For pt.I, see Proc. AMS, vol.III, p.523-31 (1991). The minimum distance of a Goppa code is found when the length of code satisfies a certain inequality on the degree of the Goppa polynomial. In order to do this, conditions are improved on a theorem of E. Bombieri (1966). This improvement is used also to generalize a previous result on the minimum distance of the dual of a Goppa code. This approach is generalized and results are obtained about the parameters of a class of subfield subcodes of geometric Goppa codes; in other words, the covering radii are estimated, and further, the number of information symbols whenever the minimum distance is small in relation to the length of the code is found. Finally, a bound on the minimum distance of the dual code is discussed     

Note on decoding binary Goppa codes

The author gives a simple expression for the polynomial y(x) which solves the polynomial equation y(x)²≡t(x) mod G(x), where t(x), y(x) and G(x) are polynomials over the field GF(2^m). The solution of such an equation is a step in the so called Patterson algorithm for decoding binary Goppa codes. The result may also be useful for other applications     

Bounds on Goppa codes (Corresp.)

Goppa showed that the performance of most "Goppa codes" approaches the Gilbert bound asymptotically, but their performance for moderate lengths has not previously been demonstrated. In this correspondence, lower bounds are obtained on the minimum distance of most binary Goppa codes of any length.     

Equivalent irreducible Goppa codes (Corresp.)

Irreducible Goppa codes extended with an overall parity check are shown to be cyclic or shortened cyclic codes. The location points of a codeword of the extended irreducible codes can be designated as the points of a finite projective geometry. Bounds on the number of equivalence classes of both irreducible and extended irreducible Goppa codes are derived.