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]

An $(m,n,a,b)$ -tensor code consists of $m\times n$ matrices whose columns satisfy ‘ $a$ ’ parity checks and rows satisfy ‘ $b$ ’ parity checks (i.e., a tensor code is the tensor product of a column code and row code). Tensor codes are useful in distributed storage because a single erasure can be corrected quickly either by reading its row or column. Maximally Recoverable (MR) Tensor Codes, introduced by Gopalan et al., are tensor codes which can correct every erasure pattern that is information theoretically possible to correct. The main questions about MR Tensor Codes are characterizing which erasure patterns are correctable and obtaining explicit constructions over small fields. In this paper, we study the important special case when $a=1$ , i.e., the columns satisfy a single parity check equation. We introduce the notion of higher order MDS codes ($\mathrm {MDS}(\ell)$ codes) which is an interesting generalization of the well-known MDS codes, where $\ell $ captures the order of genericity of points in a low-dimensional space. We then prove that a tensor code with $a=1$ is MR if the row code is an $\mathrm {MDS}(m)$ code. We then show that $\mathrm {MDS}(m)$ codes satisfy some weak duality. Using this characterization and duality, we prove that $(m,n,a=1,b)$ -MR tensor codes require fields of size $q=\Omega _{m,b}(n^{\min \{b,m\}-1})$. Our lower bound also extends to the setting of $a>1$. We also give a deterministic polynomial time algorithm to check if a given erasure pattern is correctable by the MR tensor code (when $a=1$). [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]

In this paper, we determine all dihedral subgroups in $PGL_{2}(\mathbb {F}_{q})$ , where $q=2^{l}$ and $l$ is a positive integer; and construct binary expurgated and extended Goppa codes with dihedral automorphism groups. Moreover, it is easy to obtain binary quasi-cyclic expurgated or extended Goppa codes. [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]

Maximum Distance Separable (MDS) codes with a sparse and balanced generator matrix are appealing in distributed storage systems for balancing and minimizing the computational load. Such codes have been constructed via Reed-Solomon codes over large fields. In this paper, we focus on small fields. We prove that there exists an $[n,k]_{q}$ MDS code that has a sparse and balanced generator matrix for any $q\geq n-1$ provided that $n\leq 2k$ , by designing several algorithms with complexity running in polynomial time in $k$ and $n$. For the case $n>2k$ , we give some constructions for $q=n=p^{s}$ and $k=p^{e}m$ based on sumsets, when $e\leq s-2$ and $m\leq p-1$ , or $e=s-1$ and $m < \frac {p}{2}$. [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]

This paper investigates the decoding of a remarkable set of lattices: We treat in a unified framework the Leech lattice in dimension 24, the Nebe lattice in dimension 72, and the Barnes-Wall lattices. A new interesting lattice, named $L_{3\cdot 24}$ , is constructed as a simple application of the single parity check on the Leech lattice. The common aspect of these lattices is that they can be obtained via a single parity check or via the $k$ -ing construction. We exploit these constructions to introduce a new efficient paradigm for decoding. This leads to efficient list decoders and quasi-optimal decoders on the Gaussian channel. Both theoretical and practical performance (point error probability and complexity) of the new decoders are provided. [ABSTRACT FROM AUTHOR]

Sequences and their correlation properties have been extensively studied due to their broad applications. In this paper, we develop a connection between sequences and well-studied combinatorial objects, circular Florentine arrays. This connection allows us to derive two types of sequences with good correlation properties. The first type consists of sequences having optimal correlation with respect to the Sarwate bound. Our constructions are based on perfect polyphase sequences. The number of perfect sequences with optimal correlation depends on the existence of circular Florentine arrays, which improves the previous known results. The second type is about multiple ZCZ sequence sets with low inter-set cross-correlation. Each generated ZCZ sequence set is optimal with respect to the Tang-Fan-Matsufuji bound, and each sequence in each set is perfect. In addition, any two sequences from distinct ZCZ sequence sets possess optimal inter-set cross-correlation with respect to the Sarwate bound. Compared with the previous results, the number of ZCZ sequence sets with optimal inter-set cross-correlation property is improved, because of the existence of circular Florentine arrays. [ABSTRACT FROM AUTHOR]

In this article, we present a new construction of evaluation codes in the Hamming metric, which we call twisted Reed–Solomon codes. Whereas Reed–Solomon (RS) codes are MDS codes, this need not be the case for twisted RS codes. Nonetheless, we show that our construction yields several families of MDS codes. Further, for a large subclass of (MDS) twisted RS codes, we show that the new codes are not generalized RS codes. To achieve this, we use properties of Schur squares of codes as well as an explicit description of the dual of a large subclass of our codes. We conclude the paper with a description of a decoder, that performs very well in practice as shown by extensive simulation results. [ABSTRACT FROM AUTHOR]

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]

Local pseudorandom generators are a class of fundamental cryptographic primitives having very broad applications in theoretical cryptography. Following Couteau et al.’s work at ASIACRYPT 2018, this paper further studies the concrete security of one important class of local pseudorandom generators, i.e., Goldreich’s pseudorandom generators. Our first attack is of the guess-and-determine type. Our result significantly improves the state-of-the-art algorithm proposed by Couteau et al., in terms of both asymptotic and concrete complexity, and breaks all the challenge parameters they proposed. For instance, for a parameter set suggested for 128 bits of security, we could solve the instance faster by a factor of about 277, thereby destroying the claimed security completely. Our second attack further exploits the extremely sparse structure of the predicate $P_{5}$ and combines ideas from iterative decoding. This novel attack, named guess-and-decode, substantially improves the guess-and-determine approaches for cryptographic-relevant parameters. All the challenge parameter sets proposed in Couteau et al.’s work in ASIACRYPT 2018 aiming for 80-bit (128-bit) security levels can be solved in about 258 (278) operations. We suggest new parameters for achieving 80-bit (128-bit) security with respect to our attacks. We also extend the attacks to other promising predicates and investigate their resistance. [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]

In this paper, we consider the problem for which lengths a maximum distance separable (MDS) Euclidean self-dual code over $\mathbb {F}_{q}$ exists. This problem is completely solved for the case where $q$ is even. For $q$ is odd, some $q$ -ary MDS Euclidean self-dual codes were obtained in the literature. In this paper, we construct six new classes of $q$ -ary MDS Euclidean self-dual codes by using generalized Reed–Solomon (GRS for short) codes and extended GRS codes. [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]

This paper considers the transmission of an infinite sequence of messages (a streaming source) over a packet erasure channel, where every source message must be recovered perfectly at the destination subject to a fixed decoding delay. While the capacity of a channel that introduces only bursts of erasures has been known for more than fifteen years, only recently, the capacity of a channel with either one burst of erasures or multiple arbitrary erasures in any fixed-sized sliding window has been established. However, explicit codes shown to achieve this capacity for any admissible set of parameters require a large field size that scales exponentially with the delay. Recently, it has been shown that there exist codes that achieve the capacity with field size which scales quadratically with the delay. However, explicit constructions were shown only to specific combinations of parameters. This work describes an explicit rate-optimal construction for all admissible channel and delay parameters over a field size that scales quadratically with the delay. [ABSTRACT FROM AUTHOR]

This paper proposes the Guruswami-Sudan (GS) list decoding algorithm for one-point elliptic codes, in which the interpolation is realized by the module basis reduction (BR). Elliptic codes are a kind of algebraic-geometric (AG) codes with a genus of one. Over the same finite field, they have a greater codeword length than Reed-Solomon (RS) codes, capable of correcting more errors. The GS decoding consists of interpolation and root-finding, while the former that determines the interpolation polynomial $\mathcal {Q}(\text {x}, \text {y}, \text {z})$ dominates the decoding complexity. By defining the Lagrange interpolation function over an elliptic function field, a basis of the interpolation module can be constructed. The desired Gröbner basis that contains $\mathcal {Q}(\text {x}, \text {y}, \text {z})$ can be determined by reducing the constructed basis. This is namely the BR interpolation and it requires less finite field arithmetic operations than the conventional Kötter’s interpolation, facilitating the GS decoding. Re-encoding transform (ReT) is further introduced to facilitate the BR interpolation. This work also shows that both the BR interpolation and its ReT variant will have a lower complexity as the code rate ${k}/{n}$ increases, where n and ${k}$ are the length and dimension of the code, respectively. Our numerical results demonstrate the complexity advantage of the BR interpolation over Kötter’s interpolation, and the performance advantage of elliptic codes over RS codes. [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]

In an interesting paper, Prof. C. Ding provided three constructions of cyclic codes of length being a product of two primes. Numerical data shows that many codes from these constructions are best cyclic codes of the same length and dimension over the same finite field. However, not much is known about these codes. In this paper, we explain some of the numerical data by developing a general method on cyclic codes of composite length and on estimating the minimum distance. We also provide a general construction of cyclic codes of composite length which are related to Ding’s constructions. Numerical data shows that it produces many best cyclic codes as well. Finally, we point out how these cyclic codes can be used to construct convolutional codes with large free distance. [ABSTRACT FROM AUTHOR]

In this paper upper and lower bounds on the probability of decoding failure under maximum likelihood decoding are derived for different (nonbinary) Raptor code constructions. In particular four different constructions are considered; (i) the standard Raptor code construction, (ii) a multi-edge type construction, (iii) a construction where the Raptor code is nonbinary but the generator matrix of the LT code has only binary entries, (iv) a combination of (ii) and (iii). The latter construction resembles the one employed by RaptorQ codes, which at the time of writing this article represents the state of the art in fountain codes. The bounds are shown to be tight, and provide an important aid for the design of Raptor codes. [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 have been widely used in many applications of communication systems and data storage systems. This paper proposes a new procedure for decoding cyclic codes up to actual minimum distance. The decoding procedure consists of two steps: 1) computation of known syndromes and 2) computation of error positions and error values simultaneously. To do so, a matrix whose all entries are syndromes is called syndrome matrix. A matrix whose entries are either syndromes or the elements of a finite field is said to be partial syndrome matrix. In this paper, two novel methods are presented to determine error positions and error values simultaneously and directly. The first method uses a new partial syndrome matrix along with Gaussian elimination. The partial syndrome matrices for binary (respectively, ternary) cyclic codes of lengths from 69 to 99 (respectively, 16 to 37) are tabulated. For some cyclic codes, the partial syndrome matrices contain unknown syndromes; the second method constructs a matrix from a system of equations, which is generated by the determinants of different partial syndrome matrices and makes use of Gaussian elimination to determine its row rank. Many more cyclic codes beyond the Bose–Chaudhuri–Hocquenghem bound can be decoded with these methods. [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]

All correlation measures, classical and quantum, must be monotonic under local operations. In this paper, we characterize monotonic formulas that are linear combinations of the von Neumann entropies associated with the quantum state of a physical system that has $n$ parts. We show that these formulas form a polyhedral convex cone, which we call the monotonicity cone, and enumerate its facets. We illustrate its structure and prove that it is equivalent to the cone of monotonic formulas implied by strong subadditivity. We explicitly compute its extremal rays for ${n} \leq5$. We also consider the symmetric monotonicity cone, in which the formulas are required to be invariant under subsystem permutations. We describe this cone fully for all $n$. [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]

The discrete Fourier transform test is a randomness test included in NIST SP800-22. However, the variance of the test statistic is smaller than expected and the theoretical value of the variance is not known. Hitherto, the mechanism explaining why the former variance is smaller than expected has been qualitatively explained based on Parseval’s theorem. In this paper, we explore this quantitatively and derive the variance using Parseval’s theorem under particular assumptions. Numerical experiments are then used to show that this derived variance is robust. [ABSTRACT FROM AUTHOR]