Search

Linear codes achieving or nearly achieving the Singleton bound are interesting in both theory and practice. The objective of this paper is to construct several infinite families of MDS, near MDS and almost MDS codes from some special cyclic subgroups of ${\mathbb {F}}_{q^{2}}^{*}$. To this end, the augmentation and extension techniques are used. The codes in this paper have flexible parameters and their lengths could be large. The minimum linear locality of the codes constructed in this paper is also studied. Some infinite families of optimal linearly locally recoverable codes are obtained. Besides, some codes in this paper are proved to be proper for error detection. [ABSTRACT FROM AUTHOR]

Recently, subfield codes of geometric codes over large finite fields ${\mathrm {GF}}(q)$ with dimension 3 and 4 were studied and distance-optimal subfield codes over ${\mathrm {GF}}(p)$ were obtained, where $q=p^{m}$. The key idea for obtaining very good subfield codes over small fields is to choose very good linear codes over an extension field with small dimension. This paper first presents a general construction of $[q+1, 2, q]$ MDS codes over ${\mathrm {GF}}(q)$ , and then studies the subfield codes over ${\mathrm {GF}}(p)$ of some of the $[q+1, 2,q]$ MDS codes over ${\mathrm {GF}}(q)$. Two families of dimension-optimal codes over ${\mathrm {GF}}(p)$ are obtained, and several families of nearly optimal codes over ${\mathrm {GF}}(p)$ are produced. Several open problems are also proposed in this paper. [ABSTRACT FROM AUTHOR]

Linear codes generated by component functions of perfect nonlinear (PN for short) and almost perfect nonlinear (APN for short) functions and the first-order Reed-Muller codes have been an object of intensive study in coding theory. The objective of this paper is to investigate some binary shortened codes of two families of linear codes from APN functions and some $p$ -ary shortened codes associated with PN functions. The weight distributions of these shortened codes and the parameters of their duals are determined. The parameters of these binary codes and $p$ -ary codes are flexible. Many of the codes presented in this paper are optimal or almost optimal. The results of this paper show that the shortening technique is very promising for constructing good codes. [ABSTRACT FROM AUTHOR]

The Bose-Chaudhuri-Hocquenghem (BCH) codes are a well-studied subclass of cyclic codes that have found numerous applications in error correction and notably in quantum information processing. They are widely used in data storage and communication systems. A subclass of attractive BCH codes is the narrow-sense BCH codes over the Galois field ${\mathrm {GF}}(q)$ with length $q+1$ , which are closely related to the action of the projective general linear group of degree two on the projective line. Despite its interest, not much is known about this class of BCH codes. This paper aims to study some of the codes within this class and specifically narrow-sense antiprimitive BCH codes (these codes are also linear complementary duals (LCD) codes that have interesting practical recent applications in cryptography, among other benefits). We shall use tools and combine arguments from algebraic coding theory, combinatorial designs, and group theory (group actions, representation theory of finite groups, etc.) to investigate narrow-sense antiprimitive BCH Codes and extend results from the recent literature. Notably, the dimension, the minimum distance of some $q$ -ary BCH codes with length $q+1$ , and their duals are determined in this paper. The dual codes of the narrow-sense antiprimitive BCH codes derived in this paper include almost MDS codes. Furthermore, the classification of ${\mathrm {PGL}}(2, p^{m})$ -invariant codes over ${\mathrm {GF}}(p^{h})$ is completed. As an application of this result, the $p$ -ranks of all incidence structures invariant under the projective general linear group ${\mathrm {PGL}}(2, p^{m})$ are determined. Furthermore, infinite families of narrow-sense BCH codes admitting a 3-transitive automorphism group are obtained. Via these BCH codes, a coding-theory approach to constructing the Witt spherical geometry designs is presented. The BCH codes proposed in this paper are good candidates for permutation decoding, as they have a relatively large group of automorphisms. [ABSTRACT FROM AUTHOR]

It is well-known that cyclic codes have efficient encoding and decoding algorithms. In recent years, antiprimitive BCH codes have attracted a lot of attention. The objective of this paper is to study BCH codes of this type over finite fields and analyse their parameters. Some lower bounds on the minimum distance of antiprimitive BCH codes are given. The BCH codes presented in this paper have good parameters in general, containing many optimal linear codes. In particular, two open problems about the minimum distance of BCH codes of this type are partially solved in this paper. [ABSTRACT FROM AUTHOR]

In this paper, we introduce the notion of generalized pair weights of an $[n, k]$ -linear code over the finite field $\mathbb {F}_{q}$ and the notion of pair $r$ -equiweight codes, where $1\le r\le k-1$. Some basic properties of generalized pair weights of linear codes over finite fields are derived. We obtain a necessary and sufficient condition for an $[n,k]$ -linear code to be a pair equiweight code, and we characterize pair $r$ -equiweight codes for any $1\le r\le k-1$. A necessary and sufficient condition for a linear isomorphism to preserve pair weights between two linear codes is obtained. At the end of this paper, an application of generalized pair weights of linear codes to symbol-pair read wire-tap channels of type II is introduced. [ABSTRACT FROM AUTHOR]

Twisted generalized Reed-Solomon (TGRS) codes are a family of codes that contains a large number of maximum distance separable (MDS) codes that are non-equivalent to generalized Reed-Solomon (GRS) codes. In this paper, we characterize a sufficient and necessary condition that a twisted Reed-Solomon (TRS) code with two twists is MDS; give a sufficient and necessary condition that a TGRS code with two twists is self-dual, and present some constructions of self-dual TGRS codes. These self-dual codes are MDS, NMDS or 2-MDS. Furthermore, we study the non-GRS properties of TGRS codes with two twists and prove that these codes are non-GRS in most cases. [ABSTRACT FROM AUTHOR]

The binary quadratic-residue codes and the punctured Reed-Muller codes ${\mathcal {R}}_{2}((m-1)/2, m))$ are two families of binary cyclic codes with parameters $[n, (n+1)/2, d \geq \sqrt {n}]$. These two families of binary cyclic codes are interesting partly due to the fact that their minimum distances have a square-root bound. The objective of this paper is to construct two families of binary cyclic codes of length $2^{m}-1$ and dimension near $2^{m-1}$ with good minimum distances. When $m \geq 3$ is odd, the codes become a family of duadic codes with parameters $[2^{m}-1, 2^{m-1}, d]$ , where $d \geq 2^{(m-1)/2}+1$ if $m \equiv 3 \pmod {4}$ and $d \geq 2^{(m-1)/2}+3$ if $m \equiv 1 \pmod {4}$. The two families of binary cyclic codes contain some optimal binary cyclic codes. [ABSTRACT FROM AUTHOR]

Boolean functions with high algebraic immunity are important cryptographic primitives in some stream ciphers. In this paper, two methodologies for constructing minimal binary codes from sets, Boolean functions and vectorial Boolean functions with high algebraic immunity, are proposed. More precisely, a general construction of new minimal codes using minimal codes contained in Reed-Muller codes and sets without nonzero low degree annihilators is presented. The other construction allows us to yield minimal codes from certain subcodes of Reed-Muller codes and vectorial Boolean functions with high algebraic immunity. Via these general constructions, infinite families of minimal binary linear codes of dimension $m$ and length less than or equal to $m(m+1)/2$ are obtained. Besides, a lower bound on the minimum distance of the proposed minimal linear codes is established. Conjectures and open problems are also presented. The results of this paper show that Boolean functions with high algebraic immunity have nice applications in several fields additionally to symmetric cryptography, such as coding theory and secret sharing schemes. [ABSTRACT FROM AUTHOR]

Self-orthogonal codes are an important type of linear codes due to their wide applications in communication and cryptography. The Euclidean (or Hermitian) hull of a linear code is defined to be the intersection of the code and its Euclidean (or Hermitian) dual. It is clear that the hull is self-orthogonal. The main goal of this paper is to obtain self-orthogonal codes by investigating the hulls. Let $\mathcal {C}_{(r,r^{m}-1,\delta,b)}$ be the primitive BCH code over $\mathbb {F}_{r}$ of length $r^{m}-1$ with designed distance $\delta $ , where $\mathbb {F}_{r}$ is the finite field of order $r$. In this paper, we will present Euclidean (or Hermitian) self-orthogonal codes and determine their parameters by investigating the Euclidean (or Hermitian) hulls of some primitive BCH codes. Several sufficient and necessary conditions for primitive BCH codes with large Hermitian hulls are developed by presenting lower and upper bounds on their designed distances. Furthermore, some Hermitian self-orthogonal codes are proposed via the hulls of BCH codes and their parameters are also investigated. In addition, we determine the dimensions of the code $\mathcal {C}_{(r,r^{2}-1,\delta,1)}$ and its hull in both Hermitian and Euclidean cases for $2 \le \delta \le r^{2}-1$. We also present two sufficient and necessary conditions on designed distances such that the hull has the largest dimension. [ABSTRACT FROM AUTHOR]

Both linear complementary dual (LCD) codes and maximum distance separable (MDS) codes have good algebraic structures, and they have interesting practical applications such as communication systems, data storage, quantum codes, and so on. So far, most of LCD MDS codes have been constructed by employing generalized Reed-Solomon codes. In this paper we construct some classes of new Euclidean LCD MDS codes and Hermitian LCD MDS codes which are not monomially equivalent to Reed-Solomon codes, called LCD MDS codes of non-Reed-Solomon type. Our method is based on the constructions of Beelen et al. (2017) and Roth and Lempel (1989). To the best of our knowledge, this is the first paper on the construction of LCD MDS codes of non-Reed-Solomon type; any LCD MDS code of non-Reed-Solomon type constructed by our method is not monomially equivalent to any LCD code constructed by the method of Carlet et al. (2018). [ABSTRACT FROM AUTHOR]

In this paper, we apply two-to-one functions over F2n in two generic constructions of binary linear codes. We consider two-to-one functions in two forms: (1) generalized quadratic functions; and (2) (x2t + x)e with gcd (t, n) = gcd(e, 2n−1) = 1. Based on the study of the Walsh transforms of those functions or their variants, we present many classes of linear codes with few nonzero weights, including one weight, three weights, four weights, and five weights. The weight distributions of the proposed codes with one weight and with three weights are determined. In addition, we discuss the minimum distance of the dual of the constructed codes and show that some of them achieve the sphere packing bound. Moreover, examples show that some codes in this paper have best-known parameters. [ABSTRACT FROM AUTHOR]

Maximum distance separable (MDS) codes are very important in both theory and practice. There is a classical construction of a family of $[{2^{m}+1, 2u-1, 2^{m}-2u+3}]$ MDS codes for $1 \leq u \leq 2^{m-1}$ , which are cyclic, reversible and BCH codes over ${\mathrm {GF}}(2^{m})$. The objective of this paper is to study the quaternary subfield subcodes and quaternary subfield codes of a subfamily of the MDS codes for even $m$. A family of quaternary cyclic codes is obtained. These quaternary codes are distance-optimal in some cases and very good in general. Furthermore, two infinite families of 3-designs from these quaternary codes and their duals are presented. [ABSTRACT FROM AUTHOR]

In this paper, we construct four families of linear codes over finite fields from the complements of either the union of subfields or the union of cosets of a subfield, which can produce infinite families of optimal linear codes, including infinite families of (near) Griesmer codes. We also characterize the optimality of these four families of linear codes with an explicit computable criterion using the Griesmer bound and obtain many distance-optimal linear codes. In addition, by a more in-depth discussion on some special cases of these four families of linear codes, we obtain several classes of (distance-)optimal linear codes with few weights and completely determine their weight distributions. It is shown that most of our linear codes are self-orthogonal or minimal which are useful in applications. [ABSTRACT FROM AUTHOR]

Combinatorial designs are closely related to linear codes. Recently, some near MDS codes were employed to construct $t$ -designs by Ding and Tang, which settles the question as to whether there exists an infinite family of near MDS codes holding an infinite family of $t$ -designs for $t \geq 2$. This paper is devoted to the construction of infinite families of 3-designs and 2-designs from special equations over finite fields. First, we present an infinite family of almost MDS codes over ${\mathrm{ GF}}(p^{m})$ holding an infinite family of 3-designs. We then provide an infinite family of almost MDS codes over ${\mathrm{ GF}}(p^{m})$ holding an infinite family of 2-designs for any field ${\mathrm{ GF}}(q)$. In particular, some of these almost MDS codes are near MDS. Second, we present an infinite family of near MDS codes over ${\mathrm{ GF}}(2^{m})$ holding an infinite family of 3-designs by considering the number of roots of a special linearized polynomial. Compared to previous constructions of 3-designs or 2-designs from linear codes, the parameters of some of our designs are new and flexible. [ABSTRACT FROM AUTHOR]

Tang and Ding [IEEE IT 67 (2021) 244-254] studied the class of BCH codes $\mathcal {C}_{(q,q+1,4,1)}$ and their dual codes with $q=2^{m}$ and established that the codewords of the minimum (or the second minimum) weight in these codes support 4-designs or 3-designs. Motivated by this, we further investigate the codewords of the next adjacent weight in such codes and discover more infinite classes of $t$ -designs with $t=3,4$. In particular, we prove that codewords of weight 7 in $\mathcal {C}_{(q,q+1,4,1)}$ support 4-designs for odd $m \geqslant 5$ and they support 3-designs for even $m \geqslant 4$ , which provide infinite classes of simple $t$ -designs with new parameters. Another significant class of $t$ -designs we produce in this paper has complementary designs with parameters 4- $(2^{2s+1}+ 1,5,5)$ ; these designs have the smallest index among all the known simple 4- $(q+1,5,\lambda)$ designs derived from codes for prime powers $q$ ; and they are further proved to be isomorphic to the 4-designs admitting the projective general linear group PGL $(2,2^{2s+1})$ as the automorphism group constructed by Alltop in 1969. [ABSTRACT FROM AUTHOR]

Erasure codes are essential for providing efficient resilience against node failures in distributed storage. Typically, an $[n, k]$ erasure code encodes $k$ symbols into $n$ symbols which are then stored in different nodes. Recent work by Kadekodi et al. shows that the failure rates of storage nodes vary significantly over time, and that changing the rate of the code (via a change in $n$ and $k$) in response to such variations provides substantial storage space savings. However, the resource overhead of re-encoding the already encoded data is prohibitively high. We present a new theoretical framework formalizing code conversion—the process of converting data encoded with an $[n^{ I}, k^{ I}]$ code into data encoded with an $[{n^{ F}}, {k^{ F}}]$ code while maintaining desired decodability properties. We then introduce convertible codes, a new class of codes that allow for code conversions in a resource-efficient manner. This paper begins the study on convertible codes by focusing on linear MDS codes and the access cost of conversion. We derive a lower bound on the access cost of conversion and present an explicit optimal construction matching this bound for an important subclass of conversions. Additionally, we propose constructions with low field-size requirement for a broad subset of parameters. Our results show that it is possible to achieve code conversions with significantly less resources than the default approach of re-encoding for a wide range of parameters. [ABSTRACT FROM AUTHOR]

Insertion–deletion codes (insdel codes for short) play an important role in synchronization error correction. The higher the minimum insdel distance, the more insdel errors the code can correct. Haeupler and Shahrasbi established the Singleton bound for insdel codes: the minimum insdel distance of any $[n,k]$ linear code over $\mathbb {F}_{q}$ satisfies $d\leq 2n-2k+2$. There have been some constructions of insdel codes through Reed-Solomon codes with high capabilities, but none has come close to this bound. Recently, Do Duc et al. showed that the minimum insdel distance of any $[n,k]$ Reed-Solomon code is no more than $2n-2k$ if $q$ is large enough compared to the code length $n$ ; optimal codes that meet the new bound were also constructed explicitly. The contribution of this paper is twofold. We first show that the minimum insdel distance of any $[n,k]$ linear code over $\mathbb {F}_{q}$ satisfies $d\leq 2n-2k$ if $n > k > 1$. This result improves and generalizes the previously known results in the literature. We then give a sufficient condition under which the minimum insdel distance of a 2-D Reed-Solomon code of length $n$ over $\mathbb {F}_{q}$ is exactly equal to $2n-4$. As a consequence, we show that the sufficient condition is not hard to achieve; we explicitly construct an infinite family of optimal 2-D Reed-Somolom codes meeting the bound. [ABSTRACT FROM AUTHOR]

In this paper, we mainly study quaternary linear codes and their binary subfield codes. First we obtain a general explicit relationship between quaternary linear codes and their binary subfield codes in terms of generator matrices and defining sets. Second, we construct quaternary linear codes via simplicial complexes and determine the weight distributions of these codes. Third, the weight distributions of the binary subfield codes of these quaternary codes are also computed by employing the general characterization. Furthermore, we present two infinite families of optimal linear codes with respect to the Griesmer Bound, and a class of binary almost optimal codes with respect to the Sphere Packing Bound. We also need to emphasize that we obtain at least 9 new quaternary linear codes. [ABSTRACT FROM AUTHOR]

Minimal linear codes have significant applications in secret sharing schemes and secure two-party computation. When they are defined over finite fields, those codes have been intensively studied, especially in recent years, but they have been firstly partially characterized by Ashikhmin and Barg since 1998. Next, they were completely characterized in 2018 by Ding, Heng, and Zhou in terms of the minimum and maximum nonzero weights in the corresponding codes. Since then, many construction methods for minimal linear codes over finite fields throughout algebraic and geometric approaches have been proposed in the literature. In particular, the algebraic approach gives rise to minimal codes from (cryptographic) functions. Linear codes over finite fields have been expanded into the collection of acceptable alphabets for codes and study codes over finite commutative rings. A natural way to extend the known results available in the literature is to consider minimal linear codes over commutative rings with unity. In extending coding theory to codes over rings, several essential principles must be considered. Particularly extending the minimality property from finite fields to rings and creating such codes is not simple. Such an extension offers more flexibility in the construction of minimal codes. The present article investigates one-dimensional minimal linear codes over the rings $\mathbb {Z}_{p^{n}}$ (where $p$ is a prime) and $\mathbb {Z}_{p^{m}q^{n}}$ (where $p < q$ are distinct primes and $m\leq n$). Our ultimate objective is to characterize such codes’ minimality and design minimal linear codes over the considered rings. Given our objective, we first introduced the notion of minimal codes over (commutative) rings and succeeded in deriving simple characterization of one-dimensional minimal linear codes over the underlying rings mentioned above. Our new algebraic approach allows designing new minimal linear codes. Almost minimal codes over rings are also presented. To the best of our knowledge, the present paper offers a wide variety of minimal codes over (commutative) rings for the first time. Novel perspectives and developments in this direction are expected in the future. [ABSTRACT FROM AUTHOR]

As a special subclass of cyclic codes, BCH codes have wide applications in communication and storage systems. A BCH code of length $n$ over $\mathbb {F}_{q}$ is always relative to an $n$ -th primitive root of unity $\beta $ in an extension field of $\mathbb {F}_{q}$ , and is called a dually-BCH code if its dual is also a BCH code relative to the same $\beta $. The question as to whether a BCH code is a dually-BCH code is in general very hard to answer. In this paper, an answer to this question for primitive narrow-sense BCH codes and projective narrow-sense ternary BCH codes is given. Sufficient and necessary conditions in terms of the designed distances $\delta $ will be presented to ensure that these BCH codes are dually-BCH codes. In addition, the parameters of the primitive narrow-sense BCH codes and their dual codes are investigated. Some lower bounds on minimum distances of the dual codes of primitive and projective narrow-sense BCH codes are developed. Especially for binary primitive narrow-sense BCH codes, the new bounds on the minimum distances of the dual codes improve the classical Sidel’nikov bound, and are also better than the Carlitz and Uchiyama bound for large designed distances $\delta $. The question as to what subclasses of cyclic codes are BCH codes is also answered to some extent. As a byproduct, the parameters of some subclasses of cyclic codes are also investigated. [ABSTRACT FROM AUTHOR]

Let $q=p^{e}$ be a prime power and $\ell $ be an integer with $0\leq \ell \leq e-1$. The $\ell $ -Galois hull of classical linear codes is a generalization of the Euclidean hull and Hermitian hull. We provide a necessary and sufficient condition under which a codeword of a GRS code or an extended GRS code belongs to its $\ell $ -Galois dual code, generalizing both the Euclidean case and Hermitian case in the literature. By using four different tools: 1) the norm mapping from $\mathbb {F}_{q}^{\ast }$ to $\mathbb {F}_{p^{\ell }}^{\ast }$ ; 2) the direct product of two cyclic subgroups; 3) the coset decomposition of a cyclic group; 4) an additive subgroup of $\mathbb {F}_{q}$ and its cosets, we construct eleven families of $q$ -ary MDS codes with $\ell $ -Galois hulls of arbitrary dimensions, and give the related eleven families of $[[n,k,d;c]]_{q}$ entanglement-assisted quantum error-correcting codes (EAQECCs) with relatively large minimum distance in the sense that $2d=n-k+2+c$. We show that developing the theory on $\ell $ -Galois hulls of $q$ -ary MDS codes in this paper enables us to obtain new $q$ -ary EAQECCs with different kinds of length sets via different $\ell $ , where $2\ell \mid e$. [ABSTRACT FROM AUTHOR]

This paper focuses on constructions of MDS self-dual codes from (extended) generalized Reed-Solomon (GRS) codes. Let $q = r^{2}$ be an odd prime power. We show that, there exists a $q$ -ary self-dual (extended) GRS code for each even length in the range $[{2r,3r-3}]$ , and for each singly even length in the range $[3r-1,4r]$. This extends the only known consecutive range $[2,2r]$ to $[{2,3r-3}]$ for this case. Furthermore, our general constructions provide many MDS self-dual codes with new parameters which, to the best of our knowledge, were not reported before. [ABSTRACT FROM AUTHOR]

A linear error correcting code is a subspace of a finite-dimensional space over a finite field with a fixed coordinate system. Such a code is said to be locally recoverable with locality r if, for every coordinate, its value at a codeword can be deduced from the value of (certain) r other coordinates of the codeword. These codes have found many recent applications, e.g., to distributed cloud storage. We will discuss the problem of constructing good locally recoverable codes and present some constructions using algebraic surfaces that improve previous constructions and sometimes provide codes that are optimal in a precise sense. The main conceptual contribution of this paper is to consider surfaces fibered over a curve in such a way that each recovery set is constructed from points in a single fiber. This allows us to use the geometry of the fiber to guarantee the local recoverability and use the global geometry of the surface to get a hold on the standard parameters of our codes. We look in detail at situations where the fibers are rational or elliptic curves and provide many examples applying our methods. [ABSTRACT FROM AUTHOR]

In this paper, we provide two complementary results for cyclic codes of composite length. First, we give a general construction of cyclic codes of length nr from cyclic codes of length n and a lower bound on the minimum distance. Numerical data show that many cyclic codes of composite length with the best parameters can be obtained in this way. Second, in the other direction, we show that for cyclic codes of length n with a primitive n-th root of unity as a non-zero, the minimum distance is roughly bounded by the square-free part of n. This means that we shall not expect good cyclic codes of length n in general if, for example, the length n is divisible by a high power of a prime. [ABSTRACT FROM AUTHOR]

In this paper, we first study in detail the relationship between minimal linear codes and cutting blocking sets, recently introduced by Bonini and Borello, and then completely characterize minimal linear codes as cutting blocking sets. As a direct result, minimal projective codes of dimension 3 and t-fold blocking sets with t ≥ 2 in projective planes are identical objects. Some bounds on the parameters of minimal codes are derived from this characterization. Using this new link between minimal codes and blocking sets, we also present new general primary and secondary constructions of minimal linear codes. As a result, infinite families of minimal linear codes not satisfying the Aschikhmin-Barg’s condition are obtained. In addition to this, open problems on the parameters and the weight distributions of some generated linear codes are presented. [ABSTRACT FROM AUTHOR]

In this paper, we study a class of linear codes defined by characteristic functions of certain subsets of a finite field. We derive a sufficient and necessary condition for such a code to be a minimal linear code by a character-theoretical approach. We obtain new three-weight or four-weight minimal linear codes that do not satisfy the Ashikhmin-Barg condition by using partial difference sets. We show that our construction yields minimal linear codes that do not arise from cutting vectorial blocking sets, and also discuss their applications in secret sharing schemes. [ABSTRACT FROM AUTHOR]