AG codes and AG quantum codes from the GGS curve

In this paper, algebraic-geometric (AG) codes associated with the GGS maximal curve are investigated. The Weierstrass semigroup at all \(\mathbb F_{q^2}\)-rational points of the curve is determined; the Feng-Rao designed minimum distance is computed for infinite families of such codes, as well as the automorphism group. As a result, some linear codes with better relative parameters with respect to one-point Hermitian codes are discovered. Classes of quantum and convolutional codes are provided relying on the constructed AG codes.     

Artin–Schreier curves and weights of two-dimensional cyclic codes

Let be the finite field with q elements of characteristic p, be the extension of degree m>1 and f(x) be a polynomial over . The maximum number of affine -rational points that a curve of the form y^q−y=f(x) can have is q^m+1. We determine a necessary and sufficient condition for such a curve to achieve this maximum number. Then we study the weights of two-dimensional (2-D) cyclic codes. For this, we give a trace representation of the codes starting with the zeros of the dual 2-D cyclic code. This leads to a relation between the weights of codewords and a family of Artin–Schreier curves. We give a lower bound on the minimum distance for a large class of 2-D cyclic codes. Then we look at some special classes that are not covered by our main result and obtain similar minimum distance bounds.     

Improving bounds on the minimum Euclidean distance for block codes by inner distance measure optimization

The minimum Euclidean distance is a fundamental quantity for block coded phase shift keying (PSK). In this paper we improve the bounds for this quantity that are explicit functions of the alphabet size q, block length n and code size |C|. For q=8, we improve previous results by introducing a general inner distance measure allowing different shapes of a neighborhood for a codeword. By optimizing the parameters of this inner distance measure, we find sharper bounds for the outer distance measure, which is Euclidean.The proof is built upon the Elias critical sphere argument, which localizes the optimization problem to one neighborhood. We remark that any code with q=8 that fulfills the bound with equality is best possible in terms of the minimum Euclidean distance, for given parameters n and |C|. This is true for many multilevel codes.     

Flat tori, lattices and bounds for commutative group codes

We show that commutative group spherical codes in R ⁿ , as introduced by D. Slepian, are directly related to flat tori and quotients of lattices. As consequence of this view, we derive new results on the geometry of these codes and an upper bound for their cardinality in terms of minimum distance and the maximum center density of lattices and general spherical packings in the half dimension of the code. This bound is tight in the sense it can be arbitrarily approached in any dimension. Examples of this approach and a comparison of this bound with Union and Rankin bounds for general spherical codes is also presented.     

On the Generalized Weights of a Class of Trace Codes

We build a class of codes using hermitian forms and the functional trace code. Then we give a general expression of the rth minimum distance of our code and compute general bounds for the weight hierarchy by using exponential sums. We also get the minimum distance and calculate the rth generalized Hamming weight d_r in some special cases.     

A non-cyclic triple-error-correcting BCH-like code and some minimum distance results

In this paper, we give the first example of a non-cyclic triple-error-correcting code which is not equivalent to the primitive BCH code. It has parameters [63, 45, 7]. We also give better bounds on minimum distances of some [2 ⁿ ? 1, 2 ⁿ - 3n - 1] cyclic codes with three small zeroes. Finally, we reprove weight distribution results of Kasami for triple-error-correcting BCH-like codes using direct methods.     

On algebras admitting a complete set of near weights,evaluation codes,and Goppa codes

In 1998 Høholdt, van Lint and Pellikaan introduced the concept of a “weight function” defined on a \({\mathbb{F}_q}\)-algebra and used it to construct linear codes, obtaining among them the algebraic geometry (AG) codes supported on one point. Later, in 1999, it was proved by Matsumoto that all codes produced using a weight function are actually AG codes supported on one point. Recently, “near weight functions” (a generalization of weight functions), also defined on a \({\mathbb{F}_q}\)-algebra, were introduced to study codes supported on two points. In this paper we show that an algebra admits a set of m near weight functions having a compatibility property, namely, the set is a “complete set”, if and only if it is the ring of regular functions of an affine geometrically irreducible algebraic curve defined over \({\mathbb{F}_q}\) whose points at infinity have a total of m rational branches. Then the codes produced using the near weight functions are exactly the AG codes supported on m points. A bound for the minimum distance of these codes is presented with examples which show that in some situations it compares better than the usual Goppa bound.     

Directed graph representation of half-rate additive codes over GF(4)

We show that (n, 2 ⁿ ) additive codes over GF(4) can be represented as directed graphs. This generalizes earlier results on self-dual additive codes over GF(4), which correspond to undirected graphs. Graph representation reduces the complexity of code classification, and enables us to classify additive (n, 2 ⁿ ) codes over GF(4) of length up to 7. From this we also derive classifications of isodual and formally self-dual codes. We introduce new constructions of circulant and bordered circulant directed graph codes, and show that these codes will always be isodual. A computer search of all such codes of length up to 26 reveals that these constructions produce many codes of high minimum distance. In particular, we find new near-extremal formally self-dual codes of length 11 and 13, and isodual codes of length 24, 25, and 26 with better minimum distance than the best known self-dual codes.     

Coset bounds for algebraic geometric codes

We develop new coset bounds for algebraic geometric codes. The bounds have a natural interpretation as an adversary threshold for algebraic geometric secret sharing schemes and lead to improved bounds for the minimum distance of an AG code. Our bounds improve both floor bounds and order bounds and provide for the first time a connection between the two types of bounds.     

Cayley-Bacharach and evaluation codes on complete intersections

Hansen (Appl. Algebra Eng. Comm. Comput. 14 (2003) 175) uses cohomological methods to find a lower bound for the minimum distance of an evaluation code determined by a reduced complete intersection in P². In this paper, we generalize Hansen's results from P² to P^m; we also show that the hypotheses of Hansen (2003) may be weakened. The proof is succinct and follows by combining the Cayley-Bacharach Theorem and the bounds on evaluation codes obtained in Hansen (Zero-Dimensional Schemes (Ravello, 1992), de Gruyter, Berlin, 1994, pp. 205-211).     

Evaluation of the Hamming weights of a class of linear codes based on Gauss sums

Linear codes with a few weights have been widely investigated in recent years. In this paper, we mainly use Gauss sums to represent the Hamming weights of a class of q-ary linear codes under some certain conditions, where q is a power of a prime. The lower bound of its minimum Hamming distance is obtained. In some special cases, we evaluate the weight distributions of the linear codes by semi-primitive Gauss sums and obtain some one-weight, two-weight linear codes. It is quite interesting that we find new optimal codes achieving some bounds on linear codes. The linear codes in this paper can be used in secret sharing schemes, authentication codes and data storage systems.     

Probabilistic analysis of some euclidean clustering problems

We are given n points distributed randomly in a compact region D of R^m. We consider various optimisation problems associated with partitioning this set of points into k subsets. For each problem we demonstrate lower bounds which are satisfied with high probability. For the case where D is a hypercube we use a partitioning technique to give deterministic upper bounds and to construct algorithms which with high probability can be made arbitrarily accurate in polynomial time for a given required accuracy.     

Combinatorial bounds on Hilbert functions of fat points in projective space

We study Hilbert functions of certain non-reduced schemes A supported at finite sets of points in , in particular, fat point schemes. We give combinatorially defined upper and lower bounds for the Hilbert function of A using nothing more than the multiplicities of the points and information about which subsets of the points are linearly dependent. When N=2, we give these bounds explicitly and we give a sufficient criterion for the upper and lower bounds to be equal. When this criterion is satisfied, we give both a simple formula for the Hilbert function and combinatorially defined upper and lower bounds on the graded Betti numbers for the ideal I_A defining A, generalizing results of Geramita et al. (2006) [16]. We obtain the exact Hilbert functions and graded Betti numbers for many families of examples, interesting combinatorially, geometrically, and algebraically. Our method works in any characteristic.     

A symmetric Roos bound for linear codes

The van Lint-Wilson AB-method yields a short proof of the Roos bound for the minimum distance of a cyclic code. We use the AB-method to obtain a different bound for the weights of a linear code. In contrast to the Roos bound, the role of the codes A and B in our bound is symmetric. We use the bound to prove the actual minimum distance for a class of dual BCH codes of length q²−1 over Fq. We give cyclic codes [63,38,16] and [65,40,16] over F₈ that are better than the known [63,38,15] and [65,40,15] codes.     

On codes over $$\mathbb {F}_{q}+v\mathbb {F}_{q}+v^{2}\mathbb {F}_{q}$$

In this paper we investigate linear codes with complementary dual (LCD) codes and formally self-dual codes over the ring \(R=\mathbb {F}_{q}+v\mathbb {F}_{q}+v^{2}\mathbb {F}_{q}\), where \(v^{3}=v\), for q odd. We give conditions on the existence of LCD codes and present construction of formally self-dual codes over R. Further, we give bounds on the minimum distance of LCD codes over \(\mathbb {F}_q\) and extend these to codes over R.     

Distance bounds for algebraic geometric codes

Various methods have been used to obtain improvements of the Goppa lower bound for the minimum distance of an algebraic geometric code. The main methods divide into two categories, and all but a few of the known bounds are special cases of either the Lundell-McCullough floor bound or the Beelen order bound. The exceptions are recent improvements of the floor bound by Güneri, Stichtenoth, and Taskin, and by Duursma and Park, and of the order bound by Duursma and Park, and by Duursma and Kirov. In this paper, we provide short proofs for all floor bounds and most order bounds in the setting of the van Lint and Wilson AB method. Moreover, we formulate unifying theorems for order bounds and formulate the DP and DK order bounds as natural but different generalizations of the Feng-Rao bound for one-point codes.     

The Degree and Regularity of Vanishing Ideals of Algebraic Toric Sets Over Finite Fields

Let X* be a subset of an affine space 𝔸 ^s , over a finite field K, which is parameterized by the edges of a clutter. Let X and Y be the images of X* under the maps x → [x] and x → [(x, 1)], respectively, where [x] and [(x, 1)] are points in the projective spaces ? ^s?1 and ? ^s , respectively. For certain clutters and for connected graphs, we were able to relate the algebraic invariants and properties of the vanishing ideals I(X) and I(Y). In a number of interesting cases, we compute its degree and regularity. For Hamiltonian bipartite graphs, we show the Eisenbud–Goto regularity conjecture. We give optimal bounds for the regularity when the graph is bipartite. It is shown that X* is an affine torus if and only if I(Y) is a complete intersection. We present some applications to coding theory and show some bounds for the minimum distance of parameterized linear codes for connected bipartite graphs.     

Algebraic decoding of negacyclic codes over {\mathbb Z_4}

In this article we investigate Berlekamp’s negacyclic codes and discover that these codes, when considered over the integers modulo 4, do not suffer any of the restrictions on the minimum distance observed in Berlekamp’s original papers: our codes have minimum Lee distance at least 2t + 1, where the generator polynomial of the code has roots α, α ³, . . . , α ^2t-1 for a primitive 2nth root α of unity in a Galois extension of ${\mathbb {Z}_4}$ ; no restriction on t is imposed. We present an algebraic decoding algorithm for this class of codes that corrects any error pattern of Lee weight ≤ t. Our treatment uses Gröbner bases, the decoding complexity is quadratic in t.     

Space graphs and sphericity

For a finite point set in Euclidean n-space, if we connect each pair of points by a line segment whenever the distance between them is less than a certain positive constant, we obtain a space graph in n-space. The sphericity of a graph G is defined to be the minimum number n such that G is isomorphic to a space graph in n-space. In this paper we study the sphericities of graphs and present upper bounds on the sphericity for several types of graphs.