MDS codes have garnered significant attention due to their wide applications in practice. To date, most known MDS codes are equivalent to Reed-Solomon codes. The construction of non-Reed-Solomon (non-RS) type MDS codes has emerged as an intriguing and important problem in both coding theory and finite geometry. Although some constructions of non-RS type MDS codes have been presented in the literature, the parameters of these MDS codes remain subject to strict constraints. In this paper, we introduce a general framework of constructing [n,k] MDS codes using the idea of selecting a suitable set of evaluation polynomials and a set of evaluation points such that all nonzero polynomials have at mostk–1 zeros in the evaluation set. Moreover, these MDS codes can be proved to be non-Reed-Solomon by computing their Schur squares. Furthermore, several explicit constructions of non-RS MDS codes are given by converting to combinatorial problems. As a result, new families of non-RS MDS codes with much more flexible lengths can be obtained and most of them are not covered by the known results.

In the realm of modern digital communication, cryptography, and signal processing, binary sequences with good correlation properties play a pivotal role. In the literature, considerable efforts have been dedicated to constructing good binary sequences of various lengths. As a consequence, numerous constructions of good binary sequences have been put forward. However, the majority of known constructions leverage the multiplicative cyclic group structure of finite fields Fpn, wherepis a prime andnis a positive integer. Recently, the authors made use of the cyclic group structure of all rational places of the rational function field over the finite field Fpn, and firstly constructed good binary sequences of lengthpn+ 1 via cyclotomic function fields over Fpnfor any primep[8], [10]. This approach has paved a new way for constructing good binary sequences. Motivated by the above constructions, we exploit the cyclic group structure of rational points of elliptic curves to design a family of binary sequences of length 2n+1+twith low correlation for many given integers |t| ⩽ 2(n+2)/2. Specifically, for any positive integerdwith gcd(d; 2n+1+t) = 1, we introduce a novel family of binary sequences of length 2n+1+t, sizeqd−1− 1, correlation bounded by (2d+ 1) · 2(n+2)/2+ |t|, and large linear complexity via elliptic curves.

Encoding and decoding of Reed-Muller codes have been a major research topic in coding and theoretical computer science communities. Despite of the fact that there have been numerous encoding and decoding algorithms in the literature, most of them are not quasi-linear time algorithms for arbitrary order Reed-Muller codes. Under the decoding framework proposed by Pellikaan and Wu (IEEE TIT, 2004) which regards Reed-Muller codes as subfield subcodes of Reed-Solomon codes, we propose a new decoding algorithm for Reed-Muller codes that improves previous polynomial decoding complexity to quasilinear complexity. Our new decoding algorithm includes multivariate multipoint evaluation (MPE) and interpolation under a new basis of the multivariate polynomial space as two main steps. We show that the MPE and interpolation at certain multipoint sets can be performed in quasi-linear time as well. Our approach is based on a well-known transform between univariate polynomials and multivariate polynomials. We make use of the key fact that the transformation matrix between univariate polynomials and multivariate polynomials is sparse. Due to sparsity, MPE and interpolation of multivariate polynomials and decoding of Reed-Muller codes can be reduced to MPE and interpolation of univariate polynomials and decoding of Reed-Solomon codes without extra cost respectively, i.e, the complexity of MPE and interpolation of multivariate polynomials (and, respectively, decoding of Reed-Muller codes) is dominated by that of MPE and interpolation of univariate polynomials (and, respectively, decoding of Reed-Solomon codes). As a result of this reduction, we obtain our quasi-linear time algorithms.

Fast encoding and decoding of codes have always been an important topic in coding theory as well as complexity theory. Although encoding is easier than decoding in general, designing an encoding algorithm of codes of lengthNwith quasi-linear complexityO(NlogN) is not an easy task. Despite of the fact that algebraic geometry codes (AG codes) were discovered in the early 1980s, encoding algorithms of algebraic geometry codes with quasi-linear complexityO(NlogN) have not been found except for the simplest algebraic geometry codes–Reed-Solomon codes. The best-known encoding algorithm of algebraic geometry codes based on a class of plane curves has quasi-linear complexity at leastO(Nlog2N) (Beelen et al. IEEE Trans. Inf. Theory 2021). In this paper, we design an encoding algorithm for algebraic geometry codes with quasi-linear complexityO(NlogN). Moreover, for these fast encodable AG codes, the inverse of encoding, that is, interpolating the message function from the corresponding codeword, can be computed with the same complexityO(NlogN). Our algorithms are applicable to a large class of algebraic geometry codes based on both plane and non-plane curves, including Kummer extensions, Artin-Schreier extensions, and Hermitian field towers.

Locally repairable codes have been extensively investigated due to practical applications in distributed and cloud storage systems in recent years. However, not much work on asymptotic behavior of locally repairable codes has been done. In particular, there is few result on constructive lower bound of asymptotic behavior of locally repairable codes with multiple recovering sets. In this paper, we construct some families of asymptotically good locally repairable codes with multiple recovering sets via automorphism groups of function fields of the Garcia-Stichtenoth towers. The main advantage of our construction is to allow more flexibility of localities.

Sequences with a low correlation have very important applications in communications, cryptography, and compressed sensing. In the literature, many efforts have been made to construct good sequences with various lengths, where binary sequences attract great attention. As a result, various constructions of good binary sequences have been proposed. However, most of the known constructions made use of the multiplicative cyclic group structure of finite field$\mathbb {F}_{p^{n}}$for a prime$p$and a positive integer$n$. In fact, all$p^{n}+1$rational places including the place at infinity of the rational function field over$\mathbb {F}_{p^{n}}$can form a cyclic structure under an automorphism of order$p^{n}+1$. In this paper, we make use of this cyclic structure to provide an explicit construction of binary sequences with a low correlation of length$p^{n}+1$via cyclotomic function fields over$\mathbb {F}_{p^{n}}$for any odd prime$p$. Each family of binary sequences has size$p^{n}-2$and its correlation is upper bounded by$4+\lfloor 2\cdot p^{n/2}\rfloor $. To the best of our knowledge, this is the first construction of binary sequences with a low correlation of length$p^{n}+1$for odd prime$p$. Moreover, our sequences can be constructed explicitly and have competitive parameters.

In classical coding theory, it is common to construct new codes via propagation rules. There are various propagation rules to construct classical block codes. However, propagation rules have not been extensively explored for locally repairable codes. In this paper, we systematically study some of propagation rules to construct optimal and asymptotically good locally repairable codes. To our surprise, these simple propagation rules produce interesting results. Firstly, by a lengthening propagation rule that adds some rows and columns to a parity-check matrix of a given linear code, we are able to convert a classical maximum distance separable (MDS) code into a Singleton-optimal locally repairable code and provide a simplified proof of the asymptotic Tafasman-Vlăduţ-Zink bound which exceeds the asymptotic Gilbert-Varshamov bound of locally repairable codes. Secondly, by concatenating a locally repairable code as an inner code with a classical block code as an outer code, we obtain a family of dimension-optimal locally repairable codes. Thirdly, we can make use of the shortening technique to produce more dimension-optimal locally repairable codes. Finally, one of phenomena that we observe in this paper is that some trivial propagation rules in classical block codes do not hold anymore for locally repairable codes.

In coding theory, constructing codes with good parameters is one of the most important and fundamental problems. A great many good codes have been constructed over alphabets of sizes equal to prime powers, however, good block codes over other alphabet sizes are rare. In this paper, we provide a new explicit construction of$(q+1)$-ary nonlinear codes via algebraic function fields, where$q$is a prime power. Our codes are constructed by evaluating rational functions at all rational places of an algebraic function field. Compared with algebraic geometry codes, the main difference is that we allow rational functions to be evaluated at pole places. After evaluating rational functions from a union of Riemann-Roch spaces, we obtain a family of nonlinear codes over the alphabet$\mathbb {F}_{q}\cup \{\infty \}$. It turns out that our codes have better parameters than those obtained from MDS codes or good algebraic geometry codes via code alphabet extension and restriction.

Due to wide applications of binary sequences with a low correlation to communications, various constructions of such sequences have been proposed in the literature. Many efforts have been made to construct good binary sequences with various lengths. However, most of the known constructions make use of the multiplicative cyclic group structure of finite field$\mathbb {F}_{2^{n}}$for a positive integer$n$. It is often overlooked in this community that all$2^{n}+1$rational places (including “the place at infinity”) of the rational function field over$\mathbb {F}_{2^{n}}$form a cyclic structure under an automorphism of order$2^{n}+1$. In this paper, we make use of this cyclic structure to provide an explicit construction of binary sequences with a low correlation of length$2^{n}+1$via cyclotomic function fields over$\mathbb {F}_{2^{n}}$. Each family of our sequences has size$2^{n}-1$and its correlation is upper bounded by$\lfloor 2^{(n+2)/2}\rfloor $. To the best of our knowledge, this is the first construction of binary sequences with a low correlation of length$2^{n}+1$. Moreover, our sequences can be constructed explicitly and have competitive parameters. In particular, compared with the Gold sequences of length$2^{n}-1$for even$n$, our sequences have a smaller correlation and a larger length although the family size of our sequences is slightly smaller.

It is well known that constructing codes with good parameters is one of the most important and fundamental problems in coding theory. Though a great many of good codes have been produced, most of them are defined over alphabets of sizes equal to prime powers. In this article, we provide a new explicit construction of$(q+1)$-ary nonlinear codes via rational function fields, where$q$is a prime power. Our codes are constructed by evaluations of rational functions at all rational places (including the place of “infinity”) of the rational function field. Compared to the rational algebraic geometry codes, the main difference is that we allow rational functions to be evaluated at pole places. After evaluating rational functions from a union of Riemann-Roch spaces, we obtain a family of nonlinear codes with length$q+1$over the alphabet$\mathbb {F}_{q}\cup \{\infty \}$. As a result, our codes have reasonable parameters as they are rather close to the Singleton bound. Furthermore, our codes have better parameters than those obtained from MDS codes via code alphabet restriction or extension. Amazingly, an efficient decoding algorithm can be provided for our codes.

Locally repairable codes, or locally recoverable codes (LRC for short), are designed for applications in distributed and cloud storage systems. Similar to classical block codes, there is an important bound called the Singleton-type bound for locally repairable codes. In this paper, an optimal locally repairable code refers to a block code achieving this Singleton-type bound. Like classical MDS codes, optimal locally repairable codes carry some very nice combinatorial structures. Since the introduction of the Singleton-type bound for locally repairable codes, people have put tremendous effort into construction of optimal locally repairable codes. There are a few constructions of optimal locally repairable codes in the literature. Most of these constructions are realized via either combinatorial or algebraic structures. In this paper, we apply automorphism group of the rational function field to construct optimal locally repairable codes by considering the group action on projective lines over finite fields. Due to various subgroups of the projective general linear group, we are able to construct optimal locally repairable codes with flexible locality as well as smaller alphabet size comparable to the code length. In particular, we produce new families of q-ary locally repairable codes, including codes of length q+1 via cyclic groups.

Locally repairable codes have been investigated extensively in recent years due to practical applications in distributed and cloud storage systems. However, there are few asymptotic constructions of locally repairable codes in the literature. In this paper, we provide a new explicit asymptotic construction of locally repairable codes over arbitrary finite fields from local expansions of functions at a rational place. This construction gives a Tsfasman-Vladut-Zink type bound for locally repairable codes. Its main advantage is that there are no constraints on both locality and alphabet size. Furthermore, we show that the Gilbert-Varshamov type bound of locally repairable codes over non-prime finite fields can be improved for sufficiently large alphabet sizes.

Constructing locally repairable codes achieving Singleton-type bound (we call them optimal codes in this paper) is a challenging task and has attracted great attention in the last few years. Tamo and Barg first gave a breakthrough result in this topic by cleverly considering subcodes of Reed-Solomon codes. Thus, q-ary optimal locally repairable codes from subcodes of Reed-Solomon codes given by Tamo and Barg have length upper bounded by q. Recently, it was shown through extension of construction by Tamo and Barg that length of q-ary optimal locally repairable codes can be q+1 by Jin et al.. Surprisingly it was shown by Barg et al. that, unlike classical MDS codes, q-ary optimal locally repairable codes could have length bigger than q+1. Thus, it becomes an interesting and challenging problem to construct q-ary optimal locally repairable codes of length bigger than q+1. In this paper, we make use of rich algebraic structures of elliptic curves to construct a family of q-ary optimal locally repairable codes of length up to q+2√(q). It turns out that locality of our codes can be as big as 23 and distance can be linear in length.

Locally repairable codes have been investigated extensively in recent years due to practical applications in distributed storage as well as theoretical interest. However, not much work on asymptotical behavior of locally repairable codes has been done until now. In particular, there is little result on constructive lower bound of asymptotical behavior of locally repairable codes. In this paper, we extend the construction given by Barg et al. via automorphism groups of function field towers. The main advantage of our construction is to allow more flexibility of locality. Furthermore, we show that the Gilbert-Varshamov type bound on locally repairable codes can be improved for all sufficiently large alphabet size q.