Search

MDS codes and self-dual codes are important families of classical codes in coding theory. Therefore, it is of interest to investigate MDS self-dual codes. The existence of MDS self-dual codes over finite field ${\mathbb F}_{q}$ is competely solved for $q$ is even. In the literature, there are many known constructions of MDS self-dual codes for $q$ is odd. In this paper, we present a unified approach on the existence of MDS self-dual codes with concise statements and simplified proof. It is illustrated that some of known results can also be stated in this framework. Furthermore, we can obtain some new MDS self-dual codes, especially for the case when $q$ is not a square. [ABSTRACT FROM AUTHOR]

In this paper, we construct several classes of maximum distance separable (MDS) codes via generalized Reed-Solomon (GRS) codes and extended GRS codes, where we can determine the dimensions of their Euclidean hulls or Hermitian hulls. It turns out that the dimensions of Euclidean hulls or Hermitian hulls of the codes in our constructions can take all or almost all possible values. As a consequence, we can apply our results to entanglement-assisted quantum error-correcting codes (EAQECCs) and obtain several new families of MDS EAQECCs with flexible parameters. The required number of maximally entangled states of these MDS EAQECCs can take all or almost all possible values. Moreover, several new classes of q-ary MDS EAQECCs of length $ {n} > {q}+1$ are also obtained. [ABSTRACT FROM AUTHOR]

In this paper, we study self-dual codes over finite fields using tools from algebraic function fields in one variable. An algebraic geometry code of length $n$ is defined using two divisors $G$ and $D=P_{1}+\cdots +P_{n}$. We characterize self-orthogonality of the genus zero code in terms of the divisors $G$ , $D$ and the value of a well-chosen derivative polynomial at points $(P_{i})_{1\le i\le n}$. We explore the existence problem of MDS self-dual codes in the odd characteristic case, and we explicitly construct families of new MDS self-dual codes. [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]

Hermitian functional and differential codes are AG-codes defined on a Hermitian curve. To ensure good performance, the divisors defining such AG-codes have to be carefully chosen, exploiting the rich combinatorial and algebraic properties of the Hermitian curves. In this paper, the case of differential codes $C_{\Omega }(\mathtt {D},m\mathtt {T})$ on the Hermitian curve $\mathscr {H}_{q^{3}}$ defined over $\mathbb {F}_{q^{6}}$ is worked out where $\mathop {\mathrm {supp}}\nolimits (\mathtt {T}):= \mathscr {H}_{q^{3}}(\mathbb {F}_{q^{2}})$ , the set of all $\mathbb {F}_{q^{2}}$ -rational points of $\mathscr {H}_{q^{3}}$ , while $\mathtt {D}$ is taken, as usual, to be the sum of the points in the complementary set $D = \mathscr {H}_{q^{3}}(\mathbb {F}_{q^{6}})\setminus \mathscr {H} _{q^{3}}(\mathbb {F}_{q^{2}})$. For certain values of $m$ , such codes $C_{\Omega }(\mathtt {D},m\mathtt {T})$ have better minimum distance compared with true values of 1-point Hermitian codes. The automorphism group of $C_{L}(\mathtt {D},m\mathtt {T})$ , $m\leq q^{3}-2$ , is isomorphic to $PGU(3,q)$. [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]

Let $\Bbb F_{q}$ be a finite field with $q$ elements and $p$ be a prime with $\gcd (p,q)=1$. Let $G$ be a finite abelian $p$ -group and $\Bbb F_{q}(G)$ be a group algebra. In this paper, we find all primitive idempotents and minimal abelian group codes in the group algebra $\Bbb F_{q}(G)$. Furthermore, we give all LCD abelian codes (linear code with complementary dual) and self-orthogonal abelian codes of $\Bbb F_{q}(G)$. [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]

Projective Reed-Solomon (PRS) codes are Reed-Solomon codes of the maximum possible length $q+1$. The classification of deep holes –received words with maximum possible error distance– for PRS codes is an important and difficult problem. In this paper, we use algebraic methods to explicitly construct three classes of deep holes for PRS codes. We show that these three classes completely classify all deep holes of PRS codes with redundancy four. Previously, the deep hole classification was only known for PRS codes with redundancy at most three. [ABSTRACT FROM AUTHOR]

We consider the problem of massive matrix multiplication, which underlies many data analytic applications, in a large-scale distributed system comprising a group of worker nodes. We target the stragglers’ delay performance bottleneck, which is due to the unpredictable latency in waiting for slowest nodes (or stragglers) to finish their tasks. We propose a novel coding strategy, named entangled polynomial code, for designing the intermediate computations at the worker nodes in order to minimize the recovery threshold (i.e., the number of workers that we need to wait for in order to compute the final output). We demonstrate the optimality of entangled polynomial code in several cases, and show that it provides orderwise improvement over the conventional schemes for straggler mitigation. Furthermore, we characterize the optimal recovery threshold among all linear coding strategies within a factor of 2 using bilinear complexity, by developing an improved version of the entangled polynomial code. In particular, while evaluating bilinear complexity is a well-known challenging problem, we show that optimal recovery threshold for linear coding strategies can be approximated within a factor of 2 of this fundamental quantity. On the other hand, the improved version of the entangled polynomial code enables further and orderwise reduction in the recovery threshold, compared to its basic version. Finally, we show that the techniques developed in this paper can also be extended to several other problems such as coded convolution and fault-tolerant computing, leading to tight characterizations. [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]

We consider the decoding of linear and array codes from errors when we are only allowed to download a part of the codeword. More specifically, suppose that we have encoded $k$ data symbols using an $(n,k)$ code with code length $n$ and dimension $k$. During storage, some of the codeword coordinates might be corrupted by errors. We aim to recover the original data by reading the corrupted codeword with a limit on the transmission bandwidth, namely, we can only download an $\alpha $ proportion of the corrupted codeword. For a given $\alpha $ , our objective is to design a code and a decoding scheme such that we can recover the original data from the largest possible number of errors. A naive scheme is to read $\alpha n$ coordinates of the codeword. This method used in conjunction with MDS codes guarantees recovery from any $\lfloor (\alpha n-k)/2\rfloor $ errors. In this paper we show that we can instead download an $\alpha $ proportion from each of the codeword’s coordinates. For a well-designed MDS code, this method can guarantee recovery from $\lfloor (n-k/\alpha)/2 \rfloor $ errors, which is $1/\alpha $ times more than the naive method, and is also the maximum number of errors that an $(n,k)$ code can correct by downloading only an $\alpha $ proportion of the codeword. We present two families of such optimal constructions and decoding schemes of which one is based on Interleaved Reed-Solomon codes and the other on Folded Reed-Solomon codes. We further show that both code constructions attain asymptotically optimal list decoding radius when downloading only a part of the corrupted codeword. We also construct an ensemble of random codes that with high probability approaches the upper bound on the number of correctable errors when the decoder downloads an $\alpha $ proportion of the corrupted codeword. [ABSTRACT FROM AUTHOR]

The Z2s-additive codes are subgroups of Zn2s, and can be seen as a generalization of linear codes over Z2 and Z4. A Z2s-linear Hadamard code is a binary Hadamard code which is the Gray map image of a Z2s-additive code. It is known that either the rank or the dimension of the kernel can be used to give a complete classification for the Z4-linear Hadamard codes. However, when s > 2, the dimension of the kernel of Z2s-linear Hadamard codes of length 2t only provides a complete classification for some values of t and s. In this paper, the rank of these codes is computed for s = 3. Moreover, it is proved that this invariant, along with the dimension of the kernel, provides a complete classification, once t ≥ 3 is fixed. In this case, the number of nonequivalent such codes is also established. [ABSTRACT FROM AUTHOR]

Locally recoverable codes are very important due to their applications in distributed storage systems. In this paper, by using cyclic codes, we construct two classes of optimal q-ary cyclic $(\text {r}, \delta _{1})$ locally recoverable codes with parameters $[2(\text {q}+1), 2(\text {q}+1)-2\delta _{1}, \delta _{1}+2]_{\text {q}}$ , where $q$ is an odd prime power and $\text {r}+\delta _{1}-1=\text {q}+1$ , and $(\text {r}, \delta _{2})$ locally recoverable codes with parameters $[2(\text {q}+1), 2(\text {q}+1)-4\delta _{2}+2, \delta _{2}+2]_{q}$ , where $\text {q}\geq 7$ is an odd prime power, $\text {q}\equiv 3~ (mod~ 4)$ and $r+\delta _{2}-1=\frac {\text {q}+1}{2}$. Compared with the known cyclic and constacyclic $(\text {r}, \delta)$ locally recoverable codes, our construction yields new optimal cyclic $(\text {r}, \delta)$ locally recoverable codes. [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]

Codes with locality are a class of codes introduced by Gopalan et al. to efficiently repair a failed node, by minimizing the number of nodes contacted during repair. An $[n,k]$ systematic code is said to have information locality $r$ , if each message symbol can be recovered by accessing $\leq r$ other symbols. An $[n,k]$ code is said to have all-symbol locality $r$ , if each code symbol can be recovered by accessing $\leq r$ other symbols. In this paper, we consider a generalization of codes with all-symbol locality to the case of handling two erasures. We study codes with locality that can recover from two erasures via a sequence of two local, parity-check computations. We refer to these codes as sequential-recovery locally repairable codes (denoted by 2-seq LR codes). Earlier approaches to handling multiple erasures considered recovery in parallel; the sequential approach allows us to potentially construct codes with improved minimum distance. We derive an upper bound on the rate of 2-seq LR codes. We provide constructions based on regular graphs which are rate-optimal with respect to the derived bound. We also characterize the structure of any rate-optimal code. By studying the Generalized Hamming Weights of the dual code, we derive a recursive upper bound on the minimum distance of 2-seq LR codes. We also provide constructions of a family of codes based on Turán graphs, that are optimal with respect to this bound. We also present explicit distance-optimal Turán graph based constructions of 2-seq LR codes for certain parameters. Our approach also leads to a new bound on the minimum distance of codes with all-symbol locality for the single-erasure case. [ABSTRACT FROM AUTHOR]

Let $q$ be a prime power and $m\geq 3$ be odd. Suppose that $n=\frac {q^{2m}-1}{a}$ with $a|(q^{m}+1)$ and $3\leq a \leq 2(q^{2}-q+1)$. This paper mainly determines the actual maximum designed distance of Hermitian dual-containing Bose-Chaudhuri-Hocquenghem (BCH) codes over $\mathbb {F}_{q^{2}}$ of length $n$. Firstly, we give the maximum designed distance $\delta _{m,a}^{R}$ of narrow-sense Hermitian dual-containing BCH codes. Secondly, we show that there are also non-narrow-sense ones of designed distance up to $\delta _{m,a}^{R}$. It is worth mentioning that our maximum designed distance $\delta _{m,a}^{R}>\lceil \frac {a}{2}\rceil \delta _{m}^{A}$ , where $\delta _{m}^{A}$ is given by Aly et al. (IEEE Trans. Inf. Theory, vol. 53, no. 3, pp. 1183-1188, 2007). Thus, many families of Hermitian dual-containing BCH codes with relatively large designed distance are obtained. Using the Hermitian construction to them, we can subsequently construct different classes of nonprimitive quantum codes, which are new in the sense that their parameters are not covered in the literature. [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 this paper, we first study deviations of the complete weight distribution of a linear code from that of a random code. Then, we consider a large family of subfield subcodes of algebraic-geometric codes over prime fields which include BCH codes and Goppa codes and prove that the complete weight distribution is close to that of a random code if the code length is large compared with the genus of the curve and the degree of the divisor defining the code. [ABSTRACT FROM AUTHOR]

Minimal linear codes are a special subclass of linear codes and have significant applications in secret sharing and secure two-party computation. In this paper, we focus on constructing minimal linear codes with $\frac {w_{\min }}{w_{\max }}\leq \frac {p-1}{p}$ for any odd prime $p$ based on a generic construction of linear codes, where $w_{\min }$ and $w_{\max }$ denote the minimum and maximum nonzero weights in a code, respectively. First, we present two new infinite families of minimal linear codes with two or three weights by selecting suitable subcode of linear codes which are not minimal. Second, we also present an infinite family of minimal linear codes by employing partial spreads, which can be viewed as a generalization of the construction of Ding et al. In addition, we determine the weight distributions of all these minimal linear codes. [ABSTRACT FROM AUTHOR]

In this paper, we study the decoding error probability of linear codes over the erasure channel under the list decoding. The notion of the $q^\ell $ -incorrigible sets of linear codes is introduced to characterize its decoding error probability under the list decoding or the maximum likelihood decoding. By calculating the $q^\ell $ -incorrigible set distributions, the decoding error probability of a linear code over the erasure channel under the list decoding or the maximum likelihood decoding is expressed by its support weight distributions. For the ensemble of all $[n,k]$ linear codes, the average decoding error probability under the maximum likelihood decoding and the average unsuccessful decoding probability under unambiguous decoding are determined. Furthermore, the error exponent of the average unsuccessful decoding probability under the unambiguous decoding is determined for the ensemble of all $[n,nR]$ linear codes. [ABSTRACT FROM AUTHOR]

In this paper, we consider a new normalization of matrices obtained by choosing distinct codewords at random from linear codes over finite fields and find that under some natural algebraic conditions of the codes their empirical spectral distribution converges to Wigner’s semicircle law as the length of the codes goes to infinity. One such condition is that the dual distance of the codes is at least five. This is analogous to previous work on the empirical spectral distribution of similar matrices obtained in this fashion that converges to the Marchenko–Pastur law. [ABSTRACT FROM AUTHOR]

Locally repairable codes (LRCs) have gained significant interest for the design of large distributed storage systems as they allow a small number of erased nodes to be recovered by accessing only a few others. Several works have thus been carried out to understand the optimal rate–distance tradeoff, but only recently the size of the alphabet has been taken into account. In this paper, a novel definition of locality is proposed to keep track of the precise number of nodes required for a local repair when the repair sets do not yield MDS codes. Then, a new alphabet-dependent bound is derived, which applies both to the new definition and the initial definition of locality. The new bound is based on consecutive residual codes and intrinsically uses the Griesmer bound. A special case of the bound yields both the extension of the Cadambe–Mazumdar bound and the Singleton-type bound for codes with locality $(r,\delta)$ , implying that the new bound is at least as good as these bounds. Furthermore, an upper bound on the asymptotic rate–distance tradeoff of LRCs is derived, and yields the tightest known upper bound for large relative minimum distances. Achievability results are also provided by deriving the locality of the family of Simplex codes together with a few examples of optimal codes. [ABSTRACT FROM AUTHOR]

In this paper, we analyze the tradeoff between coding rate and asymptotic performance of a class of generalized low-density parity-check (GLDPC) codes constructed by including a certain fraction of generalized constraint (GC) nodes in the graph. The rate of the GLDPC ensemble is bounded using classical results on linear block codes, namely, Hamming bound and Varshamov bound. We also study the impact of the decoding method used at GC nodes. To incorporate both bounded-distance (BD) and maximum likelihood (ML) decoding at GC nodes into our analysis without resorting on multi-edge type of degree distributions (DDs), we propose the probabilistic peeling decoding (P-PD) algorithm, which models the decoding step at every GC node as an instance of a Bernoulli random variable with a successful decoding probability that depends on both the GC block code and its decoding algorithm. The P-PD asymptotic performance over the BEC can be efficiently predicted using standard techniques for LDPC codes such as density evolution (DE) or the differential equation method. Furthermore, for a class of GLDPC ensembles, we demonstrate that the simulated P-PD performance accurately predicts the actual performance of the GLPDC code under ML decoding at GC nodes. We illustrate our analysis for GLDPC code ensembles with regular and irregular DDs. In all cases, we show that a large fraction of GC nodes is required to reduce the original gap to capacity, but the optimal fraction is strictly smaller than one. We then consider techniques to further reduce the gap to capacity by means of random puncturing, and the inclusion of a certain fraction of generalized variable nodes in the graph. [ABSTRACT FROM AUTHOR]

Recently, Etzion et al. introduced metrics on ${\mathbb{F}}_{2}^{n}$ based on directed graphs on $n$ vertices and developed some basic coding theory on directed graph metric spaces. In this paper, we consider the problem of classifying directed graphs, which admit the extended Hamming codes to be a perfect code. We first consider weighted poset metrics as a natural generalization of poset metrics and investigate interrelation between the weighted poset metrics and the directed graph-based metrics. In the next, we classify weighted posets on a set with eight elements and directed graphs on eight vertices, which admit the extended Hamming code $\tilde {\mathcal {H }}_{3}$ to be a two-perfect code. We also construct some families of such structures for any $k \geq 3$ , which can be viewed as generalizations of some results presented by Etzion et al. and Hyun and Kim. Those families enable us to construct packing or covering codes of radius 2 under certain maps. [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]

As an optimal combinatorial object, zero-difference balanced (ZDB) functions introduced by Ding in 2008, are a generalization of the well-known perfect nonlinear functions. ZDB functions have received much attention in recent years due to its important applications in coding theory and sequence design. One objective of this paper is to present a construction of ZDB functions based on a kind of generalized cyclotomy. It generates ZDB functions over cyclic group with new parameters which can not be produced by earlier constructions. Another objective of this paper is to employ these ZDB functions to obtain at the same time: 1) optimal constant-composition codes; 2) perfect difference systems of sets; and 3) optimal frequency-hopping sequences, all with new parameters. [ABSTRACT FROM PUBLISHER]

This paper provides a link between matroid theory and locally repairable codes (LRCs) that are either linear or more generally almost affine. Using this link, new results on both LRCs and matroid theory are derived. The parameters $(n,k,d,r,\delta )$ of LRCs are generalized to matroids, and the matroid analog of the generalized singleton bound by Gopalan et al. for linear LRCs is given for matroids. It is shown that the given bound is not tight for certain classes of parameters, implying a nonexistence result for the corresponding locally repairable almost affine codes that are coined perfect in this paper. Constructions of classes of matroids with a large span of the parameters $(n,k,d,r,\delta )$ and the corresponding local repair sets are given. Using these matroid constructions, new LRCs are constructed with prescribed parameters. The existence results on linear LRCs and the nonexistence results on almost affine LRCs given in this paper strengthen the nonexistence and existence results on perfect linear LRCs given by Song et al. [ABSTRACT FROM AUTHOR]

In this paper, we consider linear secret sharing schemes over a finite field $\mathbb {F}_{q}$ , where the secret is a vector in $\mathbb {F}_{q}^\ell $ and each of the $n$ shares is a single element of $\mathbb {F}_{q}$. We obtain lower bounds on the so-called threshold gap $g$ of such schemes, defined as the quantity $r-t$ where $r$ is the smallest number such that any subset of $r$ shares uniquely determines the secret and $t$ is the largest number such that any subset of $t$ shares provides no information about the secret. Our main result establishes a family of bounds which are tighter than previously known bounds for $\ell \geq 2$. Furthermore, we also provide bounds, in terms of $n$ and $q$ , on the partial reconstruction and privacy thresholds, a more fine-grained notion that considers the amount of information about the secret that can be contained in a set of shares of a given size. Finally, we compare our lower bounds with known upper bounds in the asymptotic setting. [ABSTRACT FROM AUTHOR]

Grassmannian codes are known to be useful in error correction for random network coding. Recently, they were used to prove that vector network codes outperform scalar linear network codes, on multicast networks, with respect to the alphabet size. The multicast networks which were used for this purpose are generalized combination networks. In both the scalar and the vector network coding solutions, the subspace distance is used as the distance measure for the codes which solve the network coding problem in the generalized combination networks. In this paper, we show that the subspace distance can be replaced with two other possible distance measures which generalize the subspace distance. These two distance measures are shown to be equivalent under an orthogonal transformation. It is proved that the Grassmannian codes with the new distance measures generalize the Grassmannian codes with the subspace distance and the subspace designs with the strength of the design. Furthermore, optimal Grassmannian codes with the new distance measures have minimal requirements for the network coding solutions of some generalized combination networks. The coding problems related to these two distance measures, especially with respect to network coding, are discussed. Finally, by using these new concepts, it is proved that the codes in the Hamming scheme form a subfamily of the Grassmannian codes. [ABSTRACT FROM AUTHOR]

In a distributed storage system, recovering from multiple failures is a critical and frequent task that is crucial for maintaining the system’s reliability and fault-tolerance. In this paper, we focus on the problem of repairing multiple failures in a centralized way, which can be desirable in many data storage configurations; furthermore, we show that a significant repair traffic reduction is possible. First, the fundamental trade-off between the repair bandwidth and the storage size for functional repair is established. Using a graph-theoretic formulation, the optimal tradeoff is identified as the solution to an integer optimization problem, for which a closed-form expression is derived. Expressions of the extreme points, namely the minimum storage multi-node repair (MSMR) and minimum bandwidth multi-node repair (MBMR) points, are obtained. Second, we describe a general framework for converting single erasure minimum storage regenerating codes to MSMR codes. The repair strategy for $e$ failures is similar to that for a single failure; however, certain extra requirements need to be satisfied by the repairing functions for a single failure. For illustration, the framework is applied to product-matrix codes and interference alignment codes. Furthermore, we prove that the functional MBMR point is not achievable for linear exact-repair codes. We also show that the exact-repair minimum bandwidth cooperative repair codes achieve an interior point, that lies near the MBMR point, when $k \equiv 1 \mod e$ , $k$ being the minimum number of nodes needed to reconstruct the entire data. Finally, for $k> 2e, e\mid k$ , and $e \mid d$ , where $d$ is the number of helper nodes during repair, we show that the functional repair trade-off is not achievable under exact repair, except for maybe a small portion near the MSMR point, which parallels the results for single-erasure repair by Shah et al. [ABSTRACT FROM AUTHOR]

For locally repairable codes (LRCs), Cadambe and Mazumdar derived the first field-dependent parameter bound, known as the C-M bound. However, the C-M bound depends on an undetermined parameter $ {k}^{({q})}_{{\textbf {opt}}}({n}, {d})$. In this paper, a sphere-packing approach is developed for upper bounding the parameter $ {k}$ for $[ {n}, {k}, {d}]$ linear LRCs with locality $ {r}$. When restricted to the binary field, three upper bounds (i.e., Bound A, Bound B, and Bound C) are derived in an explicit form. More specifically, Bound A holds under the hypothesis that the local repair groups are disjoint and of equal size. Comparing with previous bounds obtained under the same hypothesis, Bound A either covers them as special cases or has an advantage due to its explicit form. Then, the hypothesis is removed in Bound B and Bound C. As the price for explicit form, Bound B specially holds for $ {d}\geq \text {5}$ and Bound C for $ {r}=\textbf {2}$. Through specific comparisons, we show that Bound B and Bound C both tend to outperform the C-M bound, as $ {n}$ goes large. Moreover, a family of binary linear LRCs with $ {d}\geq \textbf {6}$ attaining Bound B are constructed and later extended to a wider range of parameters by a shortening technique. Lastly, most of the bounds and constructions are extended to $ {q}$ -ary LRCs. [ABSTRACT FROM AUTHOR]

In this paper, we generalize constructions in two recent works of Ding, Heng, and Zhou to any field $\mathbb {F}_{{q}}$ , ${q}$ odd, providing infinite families of minimal codes for which the Ashikhmin–Barg bound does not hold. [ABSTRACT FROM AUTHOR]

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]

The hull of linear codes has promising utilization in coding theory and quantum coding theory. In this paper, we study the hull of generalized Reed–Solomon codes and extended generalized Reed–Solomon codes over finite fields with respect to the Euclidean inner product. Several infinite families of MDS codes with hulls of arbitrary dimensions are presented. As an application, using these MDS codes with hulls of arbitrary dimensions, we construct several new infinite families of entanglement-assisted quantum error-correcting codes with flexible parameters. [ABSTRACT FROM AUTHOR]

In recent years, self-dual MDS codes have attracted a lot of attention due to theoretical interest and practical importance. Similar to self-dual MDS codes, self-dual near MDS (NMDS for short) codes have nice structures as well. From both theoretical and practical points of view, it is natural to study self-dual NMDS codes. Although there has been lots of work on NMDS codes in literature, little is known for self-dual NMDS codes. It seems more challenging to construct self-dual NMDS codes than self-dual MDS codes. The only work on construction of self-dual NMDS codes shows existence of $q$ -ary self-dual NMDS codes of length $q-1$ for odd prime power $q$ or length up to 16 for some small primes $q$ with $q\le 197$. In this paper, we make use of properties of elliptic curves to construct self-dual NMDS codes. It turns out that, as long as $2|q$ and $n$ is even with $4\le n\le q+\lfloor 2\sqrt {q}\rfloor -2$ , one can construct a self-dual NMDS code of length $n$ over $ {\mathbb {F}}_{q}$. Furthermore, for odd prime power $q$ , there exists a self-dual NMDS code of length $n$ over $ {\mathbb {F}}_{q}$ if $q\ge 4^{n+3}\times (n+3)^{2}$. [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]

The square $C^{*2}$ of a linear error correcting code $C$ is the linear code spanned by the component-wise products of every pair of (non-necessarily distinct) words in $C$. Squares of codes have gained attention for several applications mainly in the area of cryptography, and typically in those applications, one is concerned about some of the parameters (dimension and minimum distance) of both $C^{*2}$ and $C$. In this paper, motivated mostly by the study of this problem in the case of linear codes defined over the binary field, squares of cyclic codes are considered. General results on the minimum distance of the squares of cyclic codes are obtained, and constructions of cyclic codes $C$ with a relatively large dimension of $C$ and minimum distance of the square $C^{*2}$ are discussed. In some cases, the constructions lead to codes $C$ such that both $C$ and $C^{*2}$ simultaneously have the largest possible minimum distances for their length and dimensions. [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]

An error-erasure channel is a simple noise model that introduces both errors and erasures. While the two types of errors can be corrected simultaneously with error-correcting codes, it is also known that any linear code allows for first correcting errors and then erasures in two-step decoding. In particular, a carefully designed parity-check matrix not only allows for separating erasures from errors but also makes it possible to efficiently correct erasures. The separating redundancy of a linear code is the number of parity-check equations in a smallest parity-check matrix that has the required property for this error-erasure separation. In a sense, it is a parameter of a linear code that represents the minimum overhead for efficiently separating erasures from errors. While several bounds on separating redundancy are known, there still remains a wide gap between upper and lower bounds except for a few limited cases. In this paper, using probabilistic combinatorics and design theory, we improve both upper and lower bounds on separating redundancy. We also show a relation between parity-check matrices for error-erasure separation and special matrices, called X-codes, for data compaction circuits in VLSI testing. This leads to an exponentially improved bound on the size of an optimal X-code. [ABSTRACT FROM AUTHOR]

In 1964, Massey introduced a class of codes with complementary duals which are called linear complimentary dual (LCD) codes. He showed that LCD codes have applications in communication system, side-channel attack and so on. LCD codes have been extensively studied in literature. On the other hand, MDS codes form an optimal family of classical codes which have wide applications in both theory and practice. The main purpose of this paper is to give an explicit construction of several classes of LCD MDS codes, using tools from algebraic function fields. We exemplify this construction and obtain several classes of explicit LCD MDS codes for the odd characteristic case. [ABSTRACT FROM AUTHOR]

In addition to their applications in data communication and storage, linear codes also have nice applications in combinatorics and cryptography. Minimal linear codes, a special type of linear codes, are preferred in secret sharing. In this paper, a necessary and sufficient condition for a binary linear code to be minimal is derived. This condition enables us to obtain three infinite families of minimal binary linear codes with $w_{\min }/w_{\max } \leq 1/2$ from a generic construction, where $w_{\min }$ and $w_{\max }$ , respectively, denote the minimum and maximum nonzero weights in a code. The weight distributions of all these minimal binary linear codes are also determined. [ABSTRACT FROM AUTHOR]

It was shown by Massey that linear complementary dual (LCD) codes are asymptotically good. In 2004, Sendrier proved that LCD codes meet the asymptotic Gilbert–Varshamov (GV) bound. Until now, the GV bound still remains to be the best asymptotical lower bound for LCD codes. In this paper, we show that an algebraic geometry code over a finite field of even characteristic is equivalent to an LCD code and consequently there exists a family of LCD codes that are equivalent to algebraic geometry codes and exceed the asymptotical GV bound. [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]

This paper considers the problem of linear Boolean classification, where the goal is to determine in which set, among two given sets of Boolean vectors, an unknown vector belongs to by making linear queries. Finding the least number of queries is equivalent to determining the minimal rank of a matrix over $GF(2)$ , whose kernel does not intersect a given set $S$ . In the case where $S$ is a Hamming ball, this reduces to finding linear codes of largest dimension. For a general set $S$ , this is an instance of the critical problem posed by Crapo and Rota in 1970, open in general. This paper focuses on the case where $S$ is an annulus. As opposed to balls, it is shown that an optimal kernel is composed not only of dense but also of sparse vectors, and the optimal mixture is identified in various cases. These findings corroborate a proposed conjecture that for an annulus of inner and outer radius $nq$ and $np$ respectively, the optimal relative rank is given by the normalized entropy $(1-q)H(p/(1-q))$ , an extension of the Gilbert–Varshamov bound. [ABSTRACT FROM AUTHOR]