Search

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. [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]

We investigate algorithms for encoding of one-point algebraic geometry (AG) codes over certain plane curves called $C_{ab}$ curves, as well as algorithms for inverting the encoding map, which we call “unencoding”. Some $C_{ab}$ curves have many points or are even maximal, e.g. the Hermitian curve. Our encoding resp. unencoding algorithms have complexity $ \tilde { \mathcal {O}}(\text {n}^{3/2})$ resp. $ \tilde { \mathcal {O}}({\it\text { qn}})$ for AG codes over any $C_{ab}$ curve satisfying very mild assumptions, where n is the code length and q the base field size, and $ \tilde { \mathcal {O}}$ 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 $ \tilde { \mathcal {O}}(\text {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 $ \tilde { \mathcal {O}}(\text {n}^{5/4})$ and $ \tilde { \mathcal {O}}(\text {n}^{3/2})$ respectively. [ABSTRACT FROM AUTHOR]

In this article we consider linear codes coming from skew-symmetric determinantal varieties, which are defined by the vanishing of minors of a certain fixed size in the space of skew-symmetric matrices. In odd characteristic, the minimum distances of these codes are determined and a recursive formula for the weight of a general codeword in these codes is given. [ABSTRACT FROM AUTHOR]

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. [ABSTRACT FROM AUTHOR]

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. [ABSTRACT FROM AUTHOR]

In this article we explicitly determine the structure of the Weierstrass semigroups H ( P ) for any point P of the Giulietti–Korchmáros curve X . We show that as the point varies, exactly three possibilities arise: one for the F q 2 -rational points (already known in the literature), one for the F q 6 ∖ F q 2 -rational points, and one for all remaining points. As a result, we prove a conjecture concerning the structure of H ( P ) in case P is an F q 6 ∖ F q 2 -rational point. [ABSTRACT FROM AUTHOR]

Let F be any field and A 1 , … , A m be finite subsets of F . We determine the maximum number of common zeroes a linearly independent family of r polynomials of degree at most d of F [ x 1 , … , x m ] can have in A 1 × … × A m . In the case when F is a finite field, our results resolve the problem of determining the generalized Hamming weights of affine Cartesian codes. This is a generalization of the work of Heijnen and Pellikaan where these were determined for the generalized Reed–Muller codes. Finally, we determine the duals of affine Cartesian codes and compute their generalized Hamming weights as well. [ABSTRACT FROM AUTHOR]

We consider a class of linear codes associated to projective algebraic varieties defined by the vanishing of minors of a fixed size of a generic matrix. It is seen that the resulting code has only a small number of distinct weights. The case of varieties defined by the vanishing of 2×2 minors is considered in some detail. Here we obtain the complete weight distribution. Moreover, several generalized Hamming weights are determined explicitly and it is shown that the first few of them coincide with the distinct nonzero weights. One of the tools used is to determine the maximum possible number of matrices of rank 1 in a linear space of matrices of a given dimension over a finite field. In particular, we determine the structure and the maximum possible dimension of linear spaces of matrices in which every nonzero matrix has rank 1. [ABSTRACT FROM AUTHOR]

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. [ABSTRACT FROM AUTHOR]

We determine the number of F q -rational points of hyperplane sections of classical determinantal varieties defined by the vanishing of minors of a fixed size of a generic matrix, and identify the hyperplane sections giving the maximum number of F q -rational points. Further we consider similar questions for sections by linear subvarieties of a fixed codimension in the ambient projective space. This is closely related to the study of linear codes associated to determinantal varieties, and the determination of their weight distribution, minimum distance, and generalized Hamming weights. The previously known results about these are generalized and expanded significantly. Connections to eigenvalues of certain association schemes, distance regular graphs, and rank metric codes are also indicated. [ABSTRACT FROM AUTHOR]

The second generalized GK function fields K n are a recently found family of maximal function fields over the finite field with q 2 n elements, where q is a prime power and n ≥ 1 an odd integer. In this paper we construct many new maximal function fields by determining various Galois subfields of K n. In case gcd ⁡ (q + 1 , n) = 1 and either q is even or q ≡ 1 (mod 4) , we find a complete list of Galois subfields of K n. Our construction adds several previously unknown genera to the genus spectrum of maximal curves. [ABSTRACT FROM AUTHOR]

We give a complete characterization of all Galois subfields of the generalized Giulietti–Korchmáros function fields C n / F q 2 n for n ≥ 5 . Calculating the genera of the corresponding fixed fields, we find new additions to the list of known genera of maximal function fields. [ABSTRACT FROM AUTHOR]