Search

An $(r, \delta)$ -locally repairable code ($(r, \delta)$ -LRC for short) was introduced by Prakash et al. for tolerating multiple failed nodes in distributed storage systems, which was a generalization of the concept of $r$ -LRCs produced by Gopalan et al.. An $(r, \delta)$ -LRC is said to be optimal if it achieves the Singleton-like bound. Recently, Chen et al. generalized the construction of cyclic $r$ -LRCs proposed by Tamo et al. , and constructed several classes of optimal $(r, \delta)$ -LRCs of length $n$ for $n\, |\, (q-1)$ or $n\,|\, (q+1)$ , respectively in terms of a union of the set of zeros controlling the minimum distance and the set of zeros ensuring the locality. Following the work of , , this paper first characterizes $(r, \delta)$ -locality of a cyclic code via its zeros. Then we construct several classes of optimal cyclic $(r, \delta)$ -LRCs of length $n$ for $n\, |\, (q-1)$ or $n\,|\, (q+1)$ , respectively from the product of two sets of zeros. Our constructions include all optimal cyclic $(r,\delta)$ -LRCs proposed in , , and our method seems more convenient to obtain optimal cyclic $(r, \delta)$ -LRCs with flexible parameters. Moreover, many optimal cyclic $(r,\delta)$ -LRCs of length $n$ for $n\, |\, (q-1)$ or $n\,|\, (q+1)$ , respectively with $(r+\delta -1)\nmid n$ can be obtained from our method. [ABSTRACT FROM AUTHOR]

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]

A functional $k$ -batch code of dimension $s$ consists of $n$ servers storing linear combinations of $s$ linearly independent information bits. Any multiset request of size $k$ of linear combinations (or requests) of the information bits can be recovered by $k$ disjoint subsets of the servers. The goal under this paradigm is to find the minimum number of servers for given values of $s$ and $k$. A recent conjecture states that for any $k=2^{s-1}$ requests the optimal solution requires $2^{s}-1$ servers. This conjecture is verified for $s \leqslant 5$ but previous work could only show that codes with $n=2^{s}-1$ servers can support a solution for $k=2^{s-2} + 2^{s-4} + \left \lfloor{ \frac { 2^{s/2}}{\sqrt {24}} }\right \rfloor $ requests. This paper reduces this gap and shows the existence of codes for $k=\lfloor \frac {5}{6}2^{s-1} \rfloor - s$ requests with the same number of servers. Another construction in the paper provides a code with $n=2^{s+1}-2$ servers and $k=2^{s}$ requests, which is an optimal result. These constructions are mainly based on extended Simplex codes and equivalently provide constructions for parallel Random I/O (RIO) codes. [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]

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]

$\mathbb {Z}_{2^{s}}$ -additive codes are subgroups of $\mathbb {Z}^{n}_{2^{s}}$ , and can be seen as a generalization of linear codes over $\mathbb {Z}_{2}$ and $\mathbb {Z}_{4}$. A $\mathbb {Z}_{2^{s}}$ -linear code is a binary code (not necessarily linear) which is the Gray map image of a $\mathbb {Z}_{2^{s}}$ -additive code. We consider $\mathbb {Z}_{2^{s}}$ -additive simplex codes of type $\alpha $ and $\beta $ , which are a generalization over $\mathbb {Z}_{2^{s}}$ of the binary simplex codes. These codes are related to the $\mathbb {Z}_{2^{s}}$ -additive Hadamard codes. In this paper, we use this relationship to find a linear subcode of the corresponding $\mathbb {Z}_{2^{s}}$ -linear codes, called kernel, and a representation of these codes as cosets of this kernel. In particular, this also gives the linearity of these codes. Similarly, $\mathbb {Z}_{2^{s}}$ -additive MacDonald codes are defined for $s>2$ , and equivalent results are obtained. [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]

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]

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]

Previous algorithms for decoding AG codes up to the designed distance all assumed existence of an extra rational place on the base algebraic curve. The place is used to solve the decoding problem by linear algebra over the base field of the curve. The rationality of the place is essential, and therefore AG codes supported by all rational places on the curve are excluded from the domain of applicability of the decoding algorithms. This paper presents a decoding algorithm for those AG codes using an extra place of higher degree. Hence finally all AG codes, as Goppa defined 40 years ago, are equipped with a fast decoding algorithm. [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]

In this paper, a family of $[{q}^{2}-1, 4, {q}^{2}-{q}-2]$ cyclic codes over ${\mathbb F}_{{q}}$ meeting the Griesmer bound is presented. Their duals are $[{q}^{2}-1,{q}^{2}-5,4]$ almost MDS codes and are optimal with respect to the sphere-packing bound. The ${q}_{0}$ -ary subfield codes of this family of cyclic codes are also investigated, where ${q}_{0}$ is any prime power such that q is power of ${q}_{0}$. Some of the subfield codes are optimal and some have the best known parameters. It is shown that the subfield codes are equivalent to a family of primitive BCH codes and thus the parameters of the BCH codes are solved. The duals of the subfield codes are also optimal with respect to the sphere-packing bound. A family of $[{q}^{2}, 4, {q}^{2}-{q}-1]$ linear codes over ${\mathbb F}_{{q}}$ meeting the Griesmer bound is presented. Their duals are $[{q}^{2},{q}^{2}-4,4]$ almost MDS codes and are optimal with respect to the sphere-packing bound. The ${q}_{0}$ -ary subfield codes of this family of linear codes are also investigated, where ${q}_{0}$ is any prime power such that q is power of ${q}_{0}$. Five infinite families of 2-designs are also constructed with three families of linear codes of this paper. [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]

BCH codes are an important class of cyclic codes which have applications in satellite communications, DVDs, disk drives, and two-dimensional bar codes. Although BCH codes have been widely studied, their parameters are known for only a few special classes. Recently, Ding et al. made some new progress in BCH codes. However, we still have very limited knowledge on the dimension of BCH codes, not to mention the weight distribution of BCH codes. In this paper, we generalize the results on BCH codes from several previous papers. 1) The dimension of narrow-sense BCH codes of length $((q^{m}-1)/{\lambda })$ with designed distance $2\leq \delta \leq (({q^{\lceil (m+1)/2 \rceil }-1})/(\lambda)+1)$ is settled, where $\lambda $ is any factor of $(q-1)$. 2) The weight distributions of two classes of narrow-sense BCH codes of length $(({q^{m}-1})/2)$ with designed distance $\delta =(({(q-1)q^{m-1}-q^{\lfloor (m-1)/2\rfloor }-1})/2)$ and $\delta =(({(q-1)q^{m-1}-q^{\lfloor (m+1)/2\rfloor }-1})/2)$ are determined. 3) The weight distribution of a class of BCH codes of length $((q^{m}-1)/({q-1}))$ is determined. In particular, a subclass of this class of BCH codes is optimal with respect to the Griesmer bound. Some optimal linear codes obtained from this class of BCH codes are characterized. [ABSTRACT FROM AUTHOR]

Ovoids in ${\mathrm {PG}}(3, {\mathrm {GF}}(q))$ have been an interesting topic in coding theory, combinatorics, and finite geometry for a long time. So far only two families of ovoids are known. The first is the elliptic quadrics and the second is the Tits ovoids. It is known that an ovoid in ${\mathrm {PG}}(3, {\mathrm {GF}}(q))$ corresponds to a $[q^{2}+1, 4, q^{2}-q]$ code over ${\mathrm {GF}}(q)$ , which is called an ovoid code. The objectives of this paper are to develop the general theories of subfield codes and to study the subfield codes of the two families of ovoid codes. The dimensions, minimum weights, and the weight distributions of the subfield codes of the elliptic quadric codes and Tits ovoid codes are settled. The parameters of the duals of these subfield codes are also studied. Some of the codes presented in this paper are optimal, and some are distance-optimal. The parameters of the subfield codes are new. [ABSTRACT FROM AUTHOR]

A Goppa code over $\Bbb F_{q^{m}}$ is a well-known subclass of algebraic error-correcting code. If $m=1$ , then it is a generalized Reed-Solomon(GRS) code and its dual code is called a GRS code via a Goppa code. In this paper, we give a necessary and sufficient condition that the dual codes of GRS codes via (expurgated) Goppa codes are also GRS codes via Goppa codes. Under the above condition, we show that the hulls of GRS codes via Goppa codes are still GRS codes via Goppa codes. As an application, we characterize LCD GRS codes and self-dual GRS codes under the above condition. Some numerical examples are also presented to illustrate our main results. Moreover, we also apply our result to entanglement-assisted quantum error correcting codes (EAQECCs) and obtain two new families of MDS EAQECCs with arbitrary parameters. [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 propose a systematic low density generator matrix (LDGM) code ensemble, which is defined by the Bernoulli process. We prove that, under maximum likelihood (ML) decoding, the proposed ensemble can achieve the capacity of binary-input output symmetric (BIOS) memoryless channels in terms of bit error rate (BER). The proof technique reveals a new mechanism, different from lowering down frame error rate (FER), that the BER can be lowered down by assigning light codeword vectors to light information vectors. The finite length performance is analyzed by deriving an upper bound and a lower bound, both of which are shown to be tight in the high signal-to-noise ratio (SNR) region. To improve the waterfall performance, we construct the systematic convolutional LDGM (SysConv-LDGM) codes by a random splitting process. The SysConv-LDGM codes are easily configurable in the sense that any rational code rate can be realized without complex optimization. As a universal construction, the main advantage of the SysConv-LDGM codes is their near-capacity performance in the waterfall region and predictable performance in the error-floor region that can be lowered down to any target as required by increasing the density of the uncoupled LDGM codes. Numerical results are also provided to verify our analysis. [ABSTRACT FROM AUTHOR]

Constacyclic codes are well-known generalizations of cyclic and negacyclic codes. Due to their rich algebraic structure, constacyclic codes are used to construct quantum codes and symbol-pair codes. Let ${\mathbb {F}}_{q}$ be a finite field with order $q$ , where $q$ is a positive power of a prime $p$. Suppose that $n$ is a positive integer and the product of distinct prime factors of $n$ divides $q-1$ , i.e., $rad(n)\mid (q-1)$. In this paper, we explicitly factorize the polynomial $x^{n}-\lambda $ for each $\lambda \in {\mathbb {F}}_{q}^{*}$. As applications, first, we obtain all repeated-root $\lambda $ -constacyclic codes and their dual codes of length $np^{s}$ over ${\mathbb {F}}_{q}$ ; second, we determine all simple-root LCD cyclic codes and LCD negacyclic codes of length $n$ over ${\mathbb {F}}_{q}$ ; third, we list all self-dual repeated-root negacyclic codes of length $np^{s}$ over ${\mathbb {F}}_{q}$. In contrast to known results, the lengths of constacyclic codes in this paper have more flexible parameters. [ABSTRACT FROM AUTHOR]

The notion of Generalized Hamming weights of block codes has been investigated since the nineties due to its significant role in coding theory and cryptography. In this paper we extend this concept to the context of convolutional codes. In particular, we focus on column distances and introduce the novel notion of generalized column distances (GCD). We first show that the hierarchy of GCD is strictly increasing. We then provide characterizations of such distances in terms of the truncated parity-check matrix of the code, that will allow us to determine their values. Finally, the case in which the parity-check matrix is in systematic form is treated. [ABSTRACT FROM AUTHOR]

A Locally Recoverable Code is a code such that the value of any single coordinate of a codeword can be recovered from the values of a small subset of other coordinates. When we have $\delta $ non-overlapping subsets of cardinality $r_{i}$ that can be used to recover the missing coordinate we say that a linear code $\mathcal {C}$ with length $n$ , dimension $k$ , minimum distance $d$ has $(r_{1},\ldots, r_\delta)$ -locality and denote by $[n, k, d; r_{1}, r_{2}, {\dots }, r_\delta]$. In this paper we provide a new upper bound for the minimum distance of these codes. Working with a finite number of subgroups of cardinality $r_{i}+1$ of the automorphism group of a function field $\mathcal {F}| \mathbb {F}_{q}$ of genus $g \geq 1$ we propose a construction of $[n, k, d; r_{1}, r_{2}, {\dots }, r_\delta]$ -codes and apply the results to some well known families of function fields. [ABSTRACT FROM AUTHOR]

Self-orthogonal codes are an interesting type of linear codes due to their wide applications in communication and cryptography. It is known that self-orthogonal codes are often used to construct quantum error-correcting codes, which can protect quantum information in quantum computations and quantum communications. Let $\mathcal C$ be an $[n, k]$ cyclic code over $\mathbb {F}_{q}$ , where $\mathbb {F}_{q}$ is the finite field of order $q$. The hull of $\mathcal C$ is defined to be the intersection of the code and its dual. In this paper, we will employ the defining sets of cyclic codes to present two general characterizations of the hulls that have dimension $k-1$ or $k^\perp -1$ , where $k^\perp $ is the dimension of the dual code $\mathcal C^\perp $. Several sufficient and necessary conditions for primitive and projective BCH codes to have $(k-1)$ -dimensional (or $(k^\perp -1)$ -dimensional) hulls are also developed by presenting lower and upper bounds on their designed distances. Furthermore, several classes of self-orthogonal codes are proposed via the hulls of BCH codes and their parameters are also investigated. The dimensions and minimum distances of some self-orthogonal codes are determined explicitly. In addition, several optimal codes are obtained. [ABSTRACT FROM AUTHOR]

Cyclic codes are widely employed in communication systems, storage devices, and consumer electronics, as they have efficient encoding and decoding algorithms. BCH codes, as a special subclass of cyclic codes, are in most cases among the best cyclic codes. A subclass of good BCH codes are the narrow-sense BCH codes over \mathrm GF(q) with length n=(q^m-1)/(q-1) . Little is known about this class of BCH codes when $q>2$ . The objective of this paper is to study some of the codes within this class. In particular, the dimension, the minimum distance, and the weight distribution of some ternary BCH codes with length n=(3^{m}-1)/2 are determined in this paper. A class of ternary BCH codes meeting the Griesmer bound is identified. An application of some of the BCH codes in secret sharing is also investigated. [ABSTRACT FROM PUBLISHER]

An $[{n}, {k}, {n}-{k}+1]$ linear code is called an MDS code. An $[{n}, {k}, {n}-{k}]$ linear code is said to be almost maximum distance separable (almost MDS or AMDS for short). A code is said to be near maximum distance separable (near MDS or NMDS for short) if the code and its dual code both are almost maximum distance separable. The first near MDS code was the [11, 6, 5] ternary Golay code discovered in 1949 by Golay. This ternary code holds 4-designs, and its extended code holds a Steiner system ${S}(5, 6, 12)$ with the largest strength known. In the past 70 years, sporadic near MDS codes holding t-designs were discovered and a lot of infinite families of near MDS codes over finite fields were constructed. However, the question as to whether there is an infinite family of near MDS codes holding an infinite family of t-designs for $ {t}\geq 2$ remains open for 70 years. This paper settles this long-standing problem by presenting an infinite family of near MDS codes over $ {GF}(3^{ {s}})$ holding an infinite family of 3-designs and an infinite family of near MDS codes over $ {GF}(2^{2 {s}})$ holding an infinite family of 2-designs. The subfield subcodes of these two families of codes are also studied, and are shown to be dimension-optimal or distance-optimal. [ABSTRACT FROM AUTHOR]

The binary Hamming codes with parameters $[{2^{m}-1, 2^{m}-1-m, 3}]$ are perfect. Their extended codes have parameters $[{2^{m}, 2^{m}-1-m, 4}]$ and are distance-optimal. The first objective of this paper is to construct a class of binary linear codes with parameters $[{2^{m+s}+2^{s}-2^{m},2^{m+s}+2^{s}-2^{m}-2m-2,4}]$ , which have better information rates than the class of extended binary Hamming codes, and are also distance-optimal. The second objective is to construct a class of distance-optimal binary codes with parameters $[{2^{m}+2, 2^{m}-2m, 6}]$. Both classes of binary linear codes have new parameters. [ABSTRACT FROM AUTHOR]

In this paper, locally repairable codes which have optimal minimum Hamming distance with respect to the bound presented by Prakash et al. are considered. New upper bounds on the length of such optimal codes are derived. The new bounds apply to more general cases, and have weaker requirements compared with the known ones. In this sense, they both improve and generalize previously known bounds. Further, optimal codes are constructed, whose length is order-optimal with respect to the new upper bounds. Notably, the length of the codes is super-linear in the alphabet size. [ABSTRACT FROM AUTHOR]

In this paper we prove new lower bounds for the maximal size of permutation codes by connecting the theory of permutation codes with the theory of linear block codes. More specifically, using the columns of a parity check matrix of an $[{\it{ n,k,d}}]_{ {q}}$ linear block code, we are able to prove the existence of a permutation code in the symmetric group of degree n, having minimum distance at least d and large cardinality. With our technique, we obtain new lower bounds for permutation codes that enhance the ones in the literature and provide asymptotic improvements in certain regimes of length and distance of the permutation code. [ABSTRACT FROM AUTHOR]

Gabidulin codes are the first general construction of linear codes that are maximum rank distant (MRD). They have found applications in linear network coding, for example, when the transmitter and receiver are oblivious to the inner workings and topology of the network (the so-called incoherent regime). The reason is that Gabidulin codes can be used to map information to linear subspaces, which in the absence of errors cannot be altered by linear operations, and in the presence of errors can be corrected if the subspace is perturbed by a small rank. Furthermore, in distributed coding and distributed systems, one is led to the design of error correcting codes whose generator matrix must satisfy a given support constraint. In this paper, we give necessary and sufficient conditions on the support of the generator matrix that guarantees the existence of Gabidulin codes and general MRD codes. When the rate of the code is not very high, this is achieved with the same field size necessary for Gabidulin codes with no support constraint. When these conditions are not satisfied, we characterize the largest possible rank distance under the support constraints and show that they can be achieved by subcodes of Gabidulin codes. The necessary and sufficient conditions are identical to those that appear for MDS codes which were recently proven by Yildiz et al. and Lovett in the context of settling the GM-MDS conjecture. [ABSTRACT FROM AUTHOR]

The largest minimum weights among quaternary Hermitian linear complementary dual codes are known for dimension 2. In this paper, we give some conditions on the nonexistence of quaternary Hermitian linear complementary dual codes with large minimum weights. As a consequence, we completely determine the largest minimum weights for dimension 3, by using a classification of some quaternary codes. In addition, for a positive integer s, an entanglement-assisted quantum error-correcting $[[21{s}+5,3,16{s}+3;21{s}+2]]$ code with maximal entanglement is constructed for the first time from a quaternary Hermitian linear complementary dual [26, 3, 19] code. [ABSTRACT FROM AUTHOR]

Minimal linear codes have significant applications in secret sharing schemes and secure two-party computation. There are several methods to construct linear codes, one of which is based on functions over finite fields. Recently, many construction methods for linear codes from functions have been proposed in the literature. In this paper, we generalize the recent construction methods given by Tang et al. in [IEEE Transactions on Information Theory, 62(3), 1166-1176, 2016] to weakly regular plateaued functions over finite fields of odd characteristic. We first construct three-weight linear codes from weakly regular plateaued functions based on the second generic construction and then determine their weight distributions. We also give a punctured version and subcode of each constructed code. We note that they may be (almost) optimal codes and can be directly employed to obtain (democratic) secret sharing schemes, which have diverse applications in the industry. We next observe that the constructed codes are minimal for almost all cases and finally describe the access structures of the secret sharing schemes based on their dual codes. [ABSTRACT FROM AUTHOR]

Building on recent development by Padakandla and Pradhan, and by Lim, Feng, Pastore, Nazer, and Gastpar, this paper studies the potential of structured coset coding as a complete replacement for random coding in network information theory. The roles of two techniques used in coset coding to generate nonuniform codewords, namely, shaping and channel transformation, are clarified and illustrated via the simple example of the two-sender multiple access channel. While individually deficient, the optimal combination of shaping via nested coset codes of the same generator matrix (which we refer to as homologous codes) and channel transformation is shown to achieve the same performance as traditional random codes for the general two-sender multiple access channel. The achievability proof of the capacity region is extended to multiple access channels with more than two senders, and with one or more receivers. A quantization argument adapted to the proposed combination of two techniques is presented to establish the achievability proof for their Gaussian counterparts. It is illustrated by an example that combining shaping and channel transformation is useful even when the goal of transmission for a subset of the receivers is to recover a linear combination of messages. These results open up new possibilities of utilizing homologous codes for a broader class of applications. [ABSTRACT FROM AUTHOR]

Locally repairable codes (LRC) have been studied from two approaches to locally repair multiple failed nodes: 1) parallel approach, in which a coordinate $i$ of an $[n,k,d]$ linear code is said to have locality $r$ and availability $t$ if there exist $t$ disjoint repair sets each of which contains at most $r$ other coordinates that can recover the value of the $i$ -th coordinate; 2) sequential approach, in which the erased symbols (failed nodes) are repaired, one by one, and any previously repaired node can be used to repair the remaining failed nodes. In this paper, we first consider LRC aiming at joint sequential-parallel repairing multiple failed nodes, and study the $(n,k,r,t,u)$ -ELRCs (Exact locally repairable codes) which are $[n,k]$ linear codes with the property that any set of failed nodes of size at most $t$ can be simultaneously repaired in parallel mode, and each element of a set $E$ of failed nodes of size at most $u$ can be sequentially repaired by $r$ ($r< k$) other coordinates. We present a method by which with a given parity-check matrix of an $(n,k,r,t,u)$ -ELRC with minimum Hamming distance $d$ , a new ELRC with minimum Hamming distance $2d$ and availability $t+1$ is constructed that can repair each set of failed nodes $E$ of size at most $2u+1$ in sequential mode and this repair is done in at most $u-t+2$ steps. We construct a big family of LRCs by making use of orthogonal Latin rectangles and permutation cubes and some other combinatorial designs; the constructed codes contain the family of direct product codes; we also use $m$ -dimensional permutation cubes to construct LRCs with short block length for each $r$. [ABSTRACT FROM AUTHOR]

It is an important task to construct quantum maximum-distance-separable (MDS) codes with good parameters. In the present paper, we provide six new classes of $q$ -ary quantum MDS codes by using generalized Reed–Solomon (GRS) codes and Hermitian construction. The minimum distances of our quantum MDS codes can be larger than $\frac {q}{2}+1$. Three of these six classes of quantum MDS codes have longer lengths than the ones constructed in and , hence some of their results can be easily derived from ours via the propagation rule. Moreover, some known quantum MDS codes of specific lengths can be seen as special cases of ours and the minimum distances of some known quantum MDS codes are also improved as well. [ABSTRACT FROM AUTHOR]

Bent functions, or equivalently, Hadamard difference sets in the elementary Abelian group (${\mathrm {GF}}(2^{2m}), $ +), have been employed to construct symmetric and quasi-symmetric designs having the symmetric difference property. The main objective of this paper is to use bent vectorial functions for a construction of a two-parameter family of binary linear codes that do not satisfy the conditions of the Assmus–Mattson theorem, but nevertheless hold 2-designs. A new coding-theoretic characterization of bent vectorial functions is presented. [ABSTRACT FROM AUTHOR]

In addition to their applications in data storage, communications systems, and consumer electronics, linear complementary dual (LCD) codes—a class of linear codes—have been employed in cryptography recently. LCD cyclic codes were referred to as reversible cyclic codes in the literature. The objective of this paper is to construct several families of reversible cyclic codes over finite fields and analyze their parameters. The LCD cyclic codes presented in this paper have very good parameters in general, and contain many optimal codes. A well rounded treatment of reversible cyclic codes is also given in this paper. [ABSTRACT FROM PUBLISHER]

In this paper, two different Gray-like maps from $Z_{p}^\alpha \times Z_{p^{k}}^\beta $ , where $p$ is prime, to $Z_{p}^{n}$ , $n={\alpha +\beta p^{k-1}}$ , denoted by $\varphi $ and $\Phi $ , respectively, are presented. We have determined the connection between the weight enumerators among the image codes under these two mappings. We show that if $C$ is a $Z_{p} Z_{p^{k}}$ -additive code, and $C^\bot $ is its dual, then the weight enumerators of the image $p$ -ary codes $\varphi (C)$ and $\Phi (C^\bot)$ are formally dual. This is a partial generalization of [D. S. Krotov, On $Z_{2^{k}}$ -dual binary codes, IEEE Transactions Information Theory 53 (2007), 1532–1537], and the result is generalized to odd characteristic $p$ and mixed alphabet. In addition, a construction of 1-perfect additive codes in the mixed $Z_{p} Z_{p^{2}}\ldots Z_{p^{k}}$ alphabet is given. [ABSTRACT FROM AUTHOR]

BCH codes are an interesting type of cyclic codes and have wide applications in communication and storage systems. Generally, it is very hard to determine the minimum distances of BCH codes. In this paper, we determine the weight distributions of two classes of primitive BCH codes $\mathcal C_{(q, m, \delta _{2})}$ and $\mathcal C_{(q, m, \delta _{3})}$ and their extended codes, which solve two problems proposed by Ding et al. It is shown that the extended codes $\overline {\mathcal C}_{(q, m, \delta _{2})}$ have four nonzero weights. We also employ the Hartmann-Tzeng bound to present the minimum distance of the dual code $\mathcal C_{(q, m, \delta _{2})}^\perp $ for $q \ge 5$. Inspired by the idea, we then determine the dimensions of a class of cyclic codes and give lower bounds on their minimum distances, which is greatly improved comparing with the BCH bound. Some optimal codes are obtained. [ABSTRACT FROM AUTHOR]

Algorithms for secure encryption in a post-quantum world are currently receiving a lot of attention in the research community. One of the most promising such algorithms is the code-based scheme called QC-MDPC, which has excellent performance and a small public key size. In this paper, we present a very efficient key recovery attack on the QC-MDPC scheme using the fact that decryption uses an iterative decoding step, and this can fail with some small probability. We identify a dependence between the secret key and the failure in decoding. This can be used to build what we refer to as a distance spectrum for the secret key, which is the set of all distances between any two ones in the secret key. In a reconstruction step, we then determine the secret key from the distance spectrum. The attack has been implemented and tested on a proposed instance of QC-MDPC for 80-bit security. It successfully recovers the secret key in minutes. A slightly modified version of the attack can be applied on proposed versions of the QC-MDPC scheme that provides IND-CCA security. The attack is a bit more complex in this case, but still very much below the security level. The reason why we can break schemes with proved CCA security is that the model for these proofs typically does not include the decoding error possibility. At last, we present several algorithms for key reconstruction from an empirical distance spectrum. We first improve the naïve algorithm for key reconstruction by a factor of about 3 0000, when the parameters for 80-bit security are implemented. We further develop the algorithm to deal with errors in the distance spectrum. This ultimately reduces the requirement on the number of ciphertexts that need to be collected for a successful key recovery. [ABSTRACT FROM AUTHOR]

The hull of a linear code is defined to be the intersection of the code and its dual, and was originally introduced to classify finite projective planes. The hull plays an important role in determining the complexity of algorithms for checking permutation equivalence of two linear codes and computing the automorphism group of a linear code. It has been shown that these algorithms are very effective in general if the size of the hull is small. The objective of this paper is to present some sufficient and necessary conditions that linear codes and cyclic codes have one-dimensional hull. It is shown that there are no such binary or ternary cyclic codes. Based on these characterizations, some constructions of linear codes with one-dimensional hull were given by employing quadratic number fields, partial difference sets, and difference sets. We also construct cyclic codes with one-dimensional hull. Some optimal codes with one-dimensional hull are obtained. [ABSTRACT FROM AUTHOR]

Like classical block codes, a locally repairable code also obeys the Singleton-type bound (we call a locally repairable code optimal if it achieves the Singleton-type bound). In the breakthrough work of Tamo and Barg, several classes of optimal locally repairable codes were constructed via subcodes of Reed–Solomon codes. Thus, the lengths of the codes given by Tamo and Barg are upper bounded by the code alphabet size $q$. Recently, it was proved through the extension of construction by Tamo and Barg that the length of $q$ -ary optimal locally repairable codes can be $q+1$ by Jin et al. Surprisingly, Barg et al. presented a few examples of $q$ -ary optimal locally repairable codes of small distance and locality with code length achieving roughly $q^{2}$. Very recently, it was further shown in the work of Li et al. that there exist $q$ -ary optimal locally repairable codes with the length bigger than $q+1$ and the distance proportional to $n$. Thus, it becomes an interesting and challenging problem to construct new families of $q$ -ary optimal locally repairable codes of length bigger than $q+1$. In this paper, we construct a class of optimal locally repairable codes of distances 3 and 4 with unbounded length (i.e., length of the codes is independent of the code alphabet size). Our technique is through cyclic codes with particular generator and parity-check polynomials that are carefully chosen. [ABSTRACT FROM AUTHOR]

Linear complementary dual (LCD) cyclic codes were referred historically to as reversible cyclic codes, which had applications in data storage. Due to a newly discovered application in cryptography, there has been renewed interest in LCD codes. In particular, it has been shown that binary LCD codes play an important role in implementations against side-channel attacks and fault injection attacks. In this paper, we first present a new characterization of binary LCD codes in terms of their orthogonal or symplectic basis. Using such a characterization, we solve a conjecture proposed by Galvez et al. on the minimum distance of binary LCD codes. Next, we consider the action of the orthogonal group on the set of all LCD codes, determine all possible orbits of this action, derive simple closed formulas of the size of the orbits, and present some asymptotic results on the size of the corresponding orbits. Our results show that almost all binary LCD codes are odd-like codes with odd-like duals, and about half of $q$ -ary LCD codes have orthonormal basis, where $q$ is a power of an odd prime. [ABSTRACT FROM AUTHOR]

Linear complementary-dual (LCD for short) codes are linear codes that intersect with their duals trivially. LCD codes have been used in certain communication systems. It is recently found that LCD codes can be applied in cryptography. This application of LCD codes renewed the interest in the construction of LCD codes having a large minimum distance. Maximum distance separable (MDS) codes are optimal in the sense that the minimum distance cannot be improved for given length and code size. Constructing LCD MDS codes is thus of significance in theory and practice. Recently, Jin constructed several classes of LCD MDS codes through generalized Reed-Solomon codes. In this paper, a different approach is proposed to obtain new LCD MDS codes from generalized Reed-Solomon codes. Consequently, new code constructions are provided and certain previously known results by Jin are extended. [ABSTRACT FROM AUTHOR]

The projective special linear group ${\mathrm {PSL}}_{2}(n)$ is 2-transitive for all primes $n$ and 3-homogeneous for $n \equiv 3 \pmod {4}$ on the set $\{0,1, \ldots, n-1, \infty \}$. It is known that the extended odd-like quadratic residue codes are invariant under ${\mathrm {PSL}}_{2}(n)$. Hence, the extended quadratic residue codes hold an infinite family of 2-designs for primes $n \equiv 1 \pmod {4}$ , an infinite family of 3-designs for primes $n \equiv 3 \pmod {4}$. To construct more $t$ -designs with $t \in \{2, 3\}$ , one would search for other extended cyclic codes over finite fields that are invariant under the action of ${\mathrm {PSL}}_{2}(n)$. The objective of this paper is to prove that the extended quadratic residue binary codes are the only nontrivial extended binary cyclic codes that are invariant under ${\mathrm {PSL}}_{2}(n)$. [ABSTRACT FROM AUTHOR]

The locally repairable code (LRC) studied in this paper is an [n,k] linear code of which the value at each coordinate can be recovered by a linear combination of at most r other coordinates. The central problem in this paper is to determine the largest possible minimum distance for LRCs. First, an integer programming-based upper bound is derived for any LRC. Then, by solving the programming problem under certain conditions, an explicit upper bound is obtained for LRCs with parameters n1>n2 , where n1 = \lceil ({n}/{r+1}) \rceil and n2 = n1 (r+1) - n . Finally, an explicit construction for LRCs attaining this upper bound is presented over the finite field \mathbb F2^{m} , where m\geq n1r . Based on these results, the largest possible minimum distance for all LRCs with r \le \sqrt n-1 has been definitely determined, which is of great significance in practical use. [ABSTRACT FROM PUBLISHER]

Because of their efficient encoding and decoding algorithms, cyclic codes—an interesting class of linear codes—are widely used in communication systems, storage devices, and consumer electronics. BCH codes form a special class of cyclic codes, and are usually among the best cyclic codes. A subclass of good BCH codes is the narrow-sense primitive BCH codes. However, the dimension and minimum distance of these codes are not known in general. The main objective of this paper is to study the dimension and minimum distances of a subclass of the narrow-sense primitive BCH codes with design distance \delta =(q-\ell 0)q^{m-\ell 1-1}-1 for certain pairs (\ell 0, \ell 1) , where 0 \leq \ell 0 \leq q-2 and 0 \leq \ell 1 \leq m-1 . The parameters of other related classes of BCH codes are also investigated, and some open problems are proposed in this paper. [ABSTRACT FROM PUBLISHER]

A code is said to be an $r$ -local locally repairable code (LRC) if each of its coordinates can be repaired by accessing at most r$ other coordinates. When some of the r$ coordinates are also erased, the r$ -local LRC cannot accomplish the local repair, which leads to the concept of (r,\delta)$ -locality. A q is said to have (r, \delta)$ -locality ( \delta \ge 2$ ) if for each coordinate i with support containing $i$ , whose length is at most $r + \delta - 1$ , and whose minimum distance is at least $\delta$ . The $(r, \delta)$ -LRC can tolerate $\delta -1$ erasures in every local code (i.e., punctured subcode), which degenerates to an $r$ -local LRC when $\delta =2$ . A $q$ -ary $(r,\delta)$ LRC is called optimal if it meets the singleton-like bound for $(r,\delta)$ -LRCs. A class of optimal $q$ -ary cyclic $r$ -local LRCs with lengths $n\mid q-1$ were constructed by Tamo, Barg, Goparaju, and Calderbank based on the $q$ -ary Reed-Solomon codes. In this paper, we construct a class of optimal $q$ -ary cyclic $(r,\delta)$ -LRCs ( $\delta \ge 2$ ) with length $n\mid q-1$ , which generalizes the results of Tamo et al. Moreover, we construct a new class of optimal $q$ -ary cyclic $r$ -local LRCs with lengths $n\mid q+1$ and a new class of optimal $q$ -ary cyclic $(r,\delta)$ -LRCs ( $\delta \ge 2$ ) with lengths $n\mid q+1$ . The constructed optimal LRCs with length $n=q+1$ have the best-known length for a given finite field with size $q$ when the minimum distance is larger than 4. [ABSTRACT FROM AUTHOR]