The performance of Reed–Solomon codes (RS codes, for short) in the presence of insertion and deletion errors has attracted growing attention in recent literature. In this work, we further study this intriguing mathematical problem, focusing on two regimes. First, we study the question of how wellfull-lengthRS codes perform against insertions and deletions. For 2-dimensional RS codes, we provide a complete characterization of codes that cannot correct even a single insertion or deletion. Furthermore, we prove that for sufficiently large field sizeq, nearly all full-length 2-dimensional RS codes can correct up to (1 - δ)qinsertion and deletion errors for any 0k≥ 2, there exists a full-lengthk-dimensional RS code capable of correctingq/(10k) insertion and deletion errors, providedqis large enough. Second, we focus on rate-1/2 RS codes that can correct a single insertion or deletion error. We present a polynomial-time algorithm that constructs such codes over fields of sizeq= Θ(k4). This result matches the existential bound given in [1].

In this paper we consider algebraic geometry (AG) codes: a class of codes constructed from algebraic codes (equivalently, using function fields) by Goppa. These codes can be list-decoded using the famous Guruswami-Sudan (GS) list-decoder, but the genus g of the used function field gives rise to negative term in the decoding radius, which we call the genus penalty. In this article, we present a GS-like list-decoding algorithm for arbitrary AG codes, which we call the inseparable GS list-decoder. Apart from the multiplicity parameter s and designed list size$\ell $, common for the GS list-decoder, we introduce an inseparability exponent e. Choosing this exponent to be positive gives rise to a list-decoder for which the genus penalty is reduced with a factor$1/p^{e}$compared to the usual GS list-decoder. Here p is the characteristic. Our list-decoder can be executed in$\tilde {\mathcal {O}} (s\ell ^{\omega }\mu ^{\omega -1}p^{e}(n+g))$field operations, where n is the code length and$\tilde {\mathcal {O}} $means that logarithmic factors are ignored.

In this article, we present a fast algorithm performing an instance of the Guruswami-Sudan list decoder for algebraic geometry codes. We show that any such code can be decoded in$\tilde {\mathcal {O}} (s^{2}\ell ^{\omega -1}\mu ^{\omega -1}(n+g) + \ell ^{\omega } \mu ^{\omega })$operations in the underlying finite field, wherenis the code length,gis the genus of the function field used to construct the code,sis the multiplicity parameter,$\ell $is the designed list size and$\mu $is the smallest positive element in the Weierstrass semigroup of some chosen place.

In this article, we present a new construction of evaluation codes in the Hamming metric, which we calltwisted Reed–Solomoncodes. 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.

We present an efficient list decoding algorithm in the style of Guruswami-Sudan for algebraic geometry codes. Our decoder can decode any such code using$\tilde{\mathcal {O}} (s\ell ^{\omega }\mu ^{\omega -1}(n+g))$operations in the underlying finite field, where$n$is the code length,$g$is the genus of the function field used to construct the code,$s$is the multiplicity parameter,$\ell $is the designed list size and$\mu $is the smallest positive element in the Weierstrass semigroup at some chosen place; the “soft-O” notation$\tilde{\mathcal {O}} (\cdot)$is similar to the “big-O” notation$\mathcal {O}(\cdot)$, but ignores logarithmic factors. For the interpolation step, which constitutes the computational bottleneck of our approach, we use known algorithms for univariate polynomial matrices, while the root-finding step is solved using existing algorithms for root-finding over univariate power series.

We investigate algorithms for encoding of one-point algebraic geometry (AG) codes over certain plane curves called Cab curves, as well as algorithms for inverting the encoding map, which we call “unencoding”. Some Cab curves have many points or are even maximal, e.g. the Hermitian curve. Our encoding resp. unencoding algorithms have complexity Õ(n3/2) resp. Õ(qn) for AG codes over any Cabcurve satisfying very mild assumptions, where n is the code length and q the base field size, and Õ ignores constants and logarithmic factors in the estimate. For codes over curves whose evaluation points lie on a grid-like structure, for example the Hermitian curve and norm-trace curves, we show that our algorithms have quasi-linear time complexity Õ(n) for both operations. For infinite families of curves whose number of points is a constant factor away from the Hasse-Weil bound, our encoding and unencoding algorithms have complexities Õ(n5/4) and Õ(n3/2) respectively.

We present a generalisation of Twisted Reed-Solomon codes containing a new large class of MDS codes. We prove that the code class contains a large subfamily that is closed under duality. Furthermore, we study the Schur squares of the new codes and show that their dimension is often large. Using these structural properties, we single out a subfamily of the new codes which could be considered for code-based cryptography: These codes resist some existing structural attacks for Reed-Solomon-like codes, i.e. methods for retrieving the code parameters from an obfuscated generator matrix.

We improve previously known lower bounds for the minimum distance of certain two-point AG codes constructed using a Generalized Giulietti-Korchmaros curve (GGK). Castellanos and Tizziotti recently described such bounds for two-point codes coming from the Giulietti-Korchmaros curve. Our results completely cover and in many cases improve on their results, using different techniques, while also supporting any GGK curve. Our method builds on the order bound for AG codes: to enable this, we study certain Weierstrass semigroups. This allows an efficient algorithm for computing our improved bounds. We find several new improvements upon the MinT minimum distance tables.

In 1964, Massey introduced a class of codes with complementary duals which are called linear complimentary dual (LCD) codes. He showed that LCD codes have applications in communication system, side-channel attack and so on. LCD codes have been extensively studied in literature. On the other hand, MDS codes form an optimal family of classical codes which have wide applications in both theory and practice. The main purpose of this paper is to give an explicit construction of several classes of LCD MDS codes, using tools from algebraic function fields. We exemplify this construction and obtain several classes of explicit LCD MDS codes for the odd characteristic case.

We present a new general construction of MDS codes over a finite field Fq. We describe two explicit subclasses which contain new MDS codes of length at least q/2 for all values of q ≥ 11. Moreover, we show that most of the new codes are not equivalent to a Reed-Solomon code.

We present the first two sub-quadratic complexity decoding algorithms for one-point Hermitian codes. The first is based on a fast realization of the Guruswami-Sudan algorithm using state-of-the-art algorithms from computer algebra for polynomial-ring matrix minimization. The second is a power decoding algorithm: an extension of classical key equation decoding which gives a probabilistic decoding algorithm up to the Sudan radius. We show how the resulting key equations can be solved by the matrix minimization algorithms from computer algebra, yielding similar asymptotic complexities.

The Gilbert-Varshamov bound guarantees the existence of families of codes over the finite field Fℓwith good asymptotic parameters. We show that this bound can be improved for all nonprime fields Fℓwith ℓ ≥ 49 , except possibly ℓ = 125. We observe that the same improvement even holds within the class of transitive codes and within the class of self-orthogonal codes.

We study a class of graph based codes with Reed-Solomon component codes as affine variety codes. We give a formulation of the exact dimension of graph codes in general. We give an algebraic description of these codes which makes the exact computation of the dimension of the graph codes easier.

We derive the Wu list-decoding algorithm for generalized Reed-Solomon (GRS) codes by using Gröbner bases over modules and the Euclidean algorithm as the initial algorithm instead of the Berlekamp-Massey algorithm. We present a novel method for constructing the interpolation polynomial fast. We give a new application of the Wu list decoder by decoding irreducible binary Goppa codes up to the binary Johnson radius. Finally, we point out a connection between the governing equations of the Wu algorithm and the Guruswami-Sudan algorithm, immediately leading to equality in the decoding range and a duality in the choice of parameters needed for decoding, both in the case of GRS codes and in the case of Goppa codes.

Affine Grassmann codes are a variant of generalized Reed-Muller codes and are closely related to Grassmann codes. These codes were introduced in a recent work by Beelen Here, we consider, more generally, affine Grassmann codes of a given level. We explicitly determine the dual of an affine Grassmann code of any level and compute its minimum distance. Further, we ameliorate the results by Beelen concerning the automorphism group of affine Grassmann codes. Finally, we prove that affine Grassmann codes and their duals have the property that they are linear codes generated by their minimum-weight codewords. This provides a clean analogue of a corresponding result for generalized Reed-Muller codes.

We consider a new class of linear codes, called affine Grassmann codes. These can be viewed as a variant of generalized Reed-Muller codes and are closely related to Grassmann codes. We determine the length, dimension, and the minimum distance of any affine Grassmann code. Moreover, we show that affine Grassmann codes have a large automorphism group and determine the number of minimum weight codewords.