Search

We construct families of locally recoverable codes with availability t ≥ 2 using fiber products of curves, determine the exact minimum distance of many families, and prove a general theorem for minimum distance of such codes. The paper concludes with an exploration of parameters of codes from these families and the fiber product construction more generally. We show that fiber product codes can achieve arbitrarily large rate and arbitrarily small relative defect, and compare to known bounds and important constructions from the literature. [ABSTRACT FROM AUTHOR]

Let $q$ be a prime power and $\mathbb {F}_{q}$ be the finite field of size $q$. In this paper we provide a Galois theoretical framework that allows to produce good polynomials for the Tamo and Barg construction of optimal locally recoverable codes (LRC). Using our approach we construct new good polynomials and therefore optimal LRCs with new parameters. The existing theory of good polynomials fits entirely in our new framework. The key advantage of our method is that we do not need to rely on arithmetic properties of the pair $(q,r)$ , where $r$ is the locality of the code. [ABSTRACT FROM AUTHOR]

In this article, we present a new construction of evaluation codes in the Hamming metric, which we call twisted Reed–Solomon codes. Whereas Reed–Solomon (RS) codes are MDS codes, this need not be the case for twisted RS codes. Nonetheless, we show that our construction yields several families of MDS codes. Further, for a large subclass of (MDS) twisted RS codes, we show that the new codes are not generalized RS codes. To achieve this, we use properties of Schur squares of codes as well as an explicit description of the dual of a large subclass of our codes. We conclude the paper with a description of a decoder, that performs very well in practice as shown by extensive simulation results. [ABSTRACT FROM AUTHOR]

Projective Reed-Muller codes are obtained by evaluating homogeneous polynomials of degree d in F q [ X 0 , ... , X n ] on the points of a projective space of dimension n defined over a finite field F q . They were introduced by Lachaud, in 1986, and their minimum distance was determined by Serre and Sørensen. As for the higher Hamming weights, contributions were made by Rodier, Sboui, Ballet and Rolland, mostly for the case where d < q . In 2016 we succeeded in determining all next-to-minimal weights when q = 2 , and in 2018 we determined all next-to-minimal weights for q = 3 , and almost all of these weights for the case where q ≥ 4 . In the present paper we determine some of the missing next-to-minimal weights of projective Reed-Muller codes when q ≥ 4 . Our proofs combine results of geometric nature with techniques from Gröbner basis theory. [ABSTRACT FROM AUTHOR]

In 1988 Lachaud introduced the class of projective Reed–Muller codes, defined by evaluating the space of homogeneous polynomials of a fixed degree d on the points of P n (F q) . In this paper we evaluate the same space of polynomials on the points of a higher dimensional scroll, defined from a set of rational normal curves contained in complementary linear subspaces of a projective space. We determine a formula for the dimension of the codes, and the exact value of the dimension and the minimum distance in some special cases. [ABSTRACT FROM AUTHOR]

We introduce a new class of evaluation linear codes by evaluating polynomials at the roots of a suitable trace function. We give conditions for self-orthogonality of these codes and their subfield-subcodes with respect to the Hermitian inner product. They allow us to construct stabilizer quantum codes over several finite fields which substantially improve the codes in the literature. For the binary case, we obtain records at http://codetables.de/. Moreover, we obtain several classical linear codes over the field $\mathbb {F}_{4}$ which are records at http://codetables.de/. [ABSTRACT FROM AUTHOR]

The decreasing norm-trace codes are evaluation codes defined by a set of monomials closed under divisibility and the rational points of the extended norm-trace curve. In particular, the decreasing norm-trace codes contain the one-point algebraic geometry (AG) codes over the extended norm-trace curve. We use Gröbner basis theory and find the indicator functions on the rational points of the curve to determine the basic parameters of the decreasing norm-trace codes: length, dimension, and minimum distance. We also obtain their dual codes. We give conditions for a decreasing norm-trace code to be a self-orthogonal or a self-dual code. We provide a linear exact repair scheme to correct single erasures for decreasing norm-trace codes, which applies to higher rate codes than the scheme developed by Jin et al. (IEEE Trans Inf Theory 64(2):900–908, 2018) when applied to the one-point AG codes over the extended norm-trace curve. [ABSTRACT FROM AUTHOR]

Abstract A linear code C with the property that C ∩ C ⊥ = { 0 } is said to be a linear complementary dual, or LCD, code. In this paper, we consider generalized affine Cartesian codes which are LCD. Generalized affine Cartesian codes arise naturally as the duals of affine Cartesian codes in the same way that generalized Reed–Solomon codes arise as duals of Reed–Solomon codes. Generalized affine Cartesian codes are evaluation codes constructed by evaluating multivariate polynomials of bounded degree at points in an m -dimensional Cartesian set over a finite field K and scaling the coordinates. The LCD property depends on the scalars used. Because Reed–Solomon codes are a special case, we obtain a characterization of those generalized Reed–Solomon codes which are LCD along with the more general result for generalized affine Cartesian codes. These results are independent of the characteristic of the underlying field. [ABSTRACT FROM AUTHOR]

In this paper we prove new lower bounds for the minimum distance of a toric surface code CP defined by a convex lattice polygon P ⊂ ℝ2. The bounds involve a geometric invariant L(P), called the full Minkowski length of P. We also show how to compute L(P) in polynomial time in the number of lattice points in P. [ABSTRACT FROM AUTHOR]

In this paper we study an instance of projective Reed–Muller type codes, i.e., codes obtained by the evaluation of homogeneous polynomials of a fixed degree in the points of a projective variety. In our case the variety is an important example of a determinantal variety, namely the projective surface known as rational normal scroll, defined over a finite field, which is the basic underlining algebraic structure of this work. We determine the dimension and a lower bound for the minimum distance of the codes, and in many cases we also find the exact value of the minimum distance. To obtain the results we use some methods from Gröbner bases theory. [ABSTRACT FROM AUTHOR]

Abstract: In this paper we construct evaluation codes on zero-dimensional complete intersections in toric varieties and give lower bounds for their minimum distance. This generalizes the results of Gold–Little–Schenck and Ballico–Fontanari who considered evaluation codes on complete intersections in the projective space. [Copyright &y& Elsevier]

Abstract: Let be a finite field with q elements and let X be a subset of a projective space , over the field K, parameterized by Laurent monomials. Let be the vanishing ideal of X. Some of the main contributions of this paper are in determining the structure of to compute some of its invariants. It is shown that is a lattice ideal. We introduce the notion of a parameterized code arising from X and present algebraic methods to compute and study its dimension, length and minimum distance. For a parameterized code, arising from a connected graph, we are able to compute its length and to make our results more precise. If the graph is non-bipartite, we show an upper bound for the minimum distance. [ABSTRACT FROM AUTHOR]

Abstract: Constructing new codes from existing ones by puncturing is in this paper viewed in the context of order domains R where puncturing can be seen as redefinition of the evaluation map . The order domains considered here are of the form where redefining can be done by adding one or more polynomials to the basis of the defining ideal I to form a new ideal J in such a way that the number of points in the variety is reduced by t to form and puncturing in t coordinates is achieved. An explicit construction of such polynomials is given in the case of codes defined by Norm–Trace curves and examples are given of both evaluation codes and dual codes. Finally, it is demonstrated that the improvement in minimum distance can be significant when compared to the lower bound obtained by ordinary puncturing. [Copyright &y& Elsevier]

The main results of this paper are derived by using only simple Gro¨bner basis techniques. We present a new construction of evaluation codes from Miura–Kamiya curves Cab. We estimate the minimum distance of the codes and estimate the minimum distance of a class of related one-point geometric Goppa codes. With respect to these estimates the new codes perform at least as well as the related geometric Goppa codes. In particular we consider codes from norm–trace curves. We show that our estimates give actually the true minimum distance of these codes. The new codes from norm–trace curves perform rather well. In many cases much better than the corresponding geometric Goppa codes. It turns out that an alternative description of the new codes from norm–trace curves can be made by using Høholdt et al.'s in: V.S. Pless, W.C. Huffman (Eds.), Handbook of Coding Theory, Vol. 1, Elsevier, Amsterdam, 1998, pp. 871–961 (Chapter 10) construction of improved dual codes. [Copyright &y& Elsevier]

The aim of this work is to study the dual and the algebraic dual of an evaluation code using standard monomials and indicator functions. We show that the dual of an evaluation code is the evaluation code of the algebraic dual. We develop an algorithm for computing a basis for the algebraic dual. Let C 1 and C 2 be linear codes spanned by standard monomials. We give a combinatorial condition for the monomial equivalence of C 1 and the dual C 2 ⊥ . Moreover, we give an explicit description of a generator matrix of C 2 ⊥ in terms of that of C 1 and coefficients of indicator functions. For Reed–Muller-type codes we give a duality criterion in terms of the v-number and the Hilbert function of a vanishing ideal. As an application, we provide an explicit duality for Reed–Muller-type codes corresponding to Gorenstein ideals. In addition, when the evaluation code is monomial and the set of evaluation points is a degenerate affine space, we classify when the dual is a monomial code. [ABSTRACT FROM AUTHOR]

Lifted Reed–Solomon codes, introduced by Guo et al. (in: Kleinberg (ed) Proceedings of the 4th conference on innovations in theoretical computer science, ITCS'13, ACM, New York, 2013), are known as one of the few families of high-rate locally correctable codes. They are built through the evaluation over the affine space of multivariate polynomials whose restriction along any affine line can be interpolated as a low degree univariate polynomial. In this work, we give a formal definition of their analogues over projective spaces, and we study some of their parameters and features. Local correcting algorithms are first derived from the very nature of these codes, generalizing the well-known local correcting algorithms for Reed–Muller codes. We also prove that the lifting of both Reed–Solomon and projective Reed–Solomon codes are deeply linked through shortening and puncturing operations. It leads to recursive formulae on their dimension and their monomial bases. We finally emphasize the practicality of lifted projective Reed–Solomon codes by computing their information sets and by providing an implementation of the codes and their local correcting algorithms. [ABSTRACT FROM AUTHOR]

We generalize the concept of near weight stated in Carvalho et al. (IEEE Trans Inf Theory 53(5):1919-1924, 2007) in the sense that we consider maps to arbitrary well-ordered semigroups instead of the nonnegative integers. This concept can be used as a tool to study AG codes based on more than one point via elementary methods only, as well as to construct codes from higher dimensional varieties. [ABSTRACT FROM AUTHOR]

We compute the basic parameters (dimension, length, minimum distance) of affine evaluation codes defined on a cartesian product of finite sets. Given a sequence of positive integers, we construct an evaluation code, over a degenerate torus, with prescribed parameters of a certain type. As an application of our results, we recover the formulas for the minimum distance of various families of evaluation codes. [ABSTRACT FROM AUTHOR]

For the family of graded lattice ideals of dimension 1, we establish a complete intersection criterion in algebraic and geometric terms. In positive characteristic, it is shown that all ideals of this family are binomial set-theoretic complete intersections. In characteristic zero, we show that an arbitrary lattice ideal which is a binomial set-theoretic complete intersection is a complete intersection. [ABSTRACT FROM AUTHOR]

Let X be a subset of a projective space, over a finite field K, which is parameterized by the monomials arising from the edges of a clutter. Let I( X) be the vanishing ideal of X. It is shown that I( X) is a complete intersection if and only if X is a projective torus. In this case we determine the minimum distance of any parameterized linear code arising from X. [ABSTRACT FROM AUTHOR]