Search

We study the Singleton-type bound that provides an upper limit on the minimum distance of locally repairable codes. We present an improved bound by carefully analyzing the combinatorial structure of the repair sets. Thus, we show the previous bound is unachievable for certain parameters. We then also provide explicit constructions of optimal codes which show that for certain parameters the new bound is sharp. Additionally, as a byproduct, some previously known codes are shown to attain the new bound and are thus proved to be optimal. [ABSTRACT FROM AUTHOR]

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

For high-rate linear systematic maximum distance separable (MDS) codes, most early constructions could initially optimally repair all the systematic nodes but not all the parity nodes. Fortunately, this issue was first solved by Li et al. in (IEEE Trans. Inform. Theory, 64(9), 6257-6267, 2018), where a transformation that can convert any nonbinary MDS array code into another one with desired properties was proposed. However, the transformation does not work for binary MDS array codes. In this paper, we address this issue by proposing another generic transformation that can convert any $[n, k]$ binary MDS array code into a new one, which endows any $r=n-k\ge 2$ chosen nodes with optimal repair bandwidth and optimal rebuilding access properties, and at the same time, preserves the normalized repair bandwidth/rebuilding access for the remaining $k$ nodes under some conditions. As two immediate applications, we show that 1) by applying the transformation multiple times, any binary MDS array code can be converted into one with optimal rebuilding access for all nodes, 2) any binary MDS array code with optimal repair bandwidth or optimal rebuilding access for the systematic nodes can be converted into one with the corresponding optimality property for all nodes. [ABSTRACT FROM AUTHOR]

We construct maximally recoverable codes (corresponding to partial MDS codes) which are based on linearized Reed-Solomon codes. The new codes have a smaller field size requirement compared with known constructions. For certain asymptotic regimes, the constructed codes have order-optimal alphabet size, asymptotically matching the known lower bound. [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]

Locally repairable codes are desirable for distributed storage systems to improve the repair efficiency. In this paper, a connection between locally repairable codes with multiple disjoint repair sets and packings is derived under the condition that each repair set contains exactly one check symbol. Particularly, conditions under which an optimal locally repairable code corresponds to a packing are also characterized. As an application of this connection, some optimal locally repairable codes can be obtained by packings. Specifically, two constructions of locally repairable codes are proposed which not only generalize some known explicit constructions but also give optimal locally repairable codes with flexible new parameters. [ABSTRACT FROM AUTHOR]

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]

Separable codes were introduced to provide protection against illegal redistribution of copyrighted multimedia material. Let $${\mathcal {C}}$$ be a code of length n over an alphabet of q letters. The descendant code $${\mathsf{desc}}({\mathcal {C}}_0)$$ of $${\mathcal {C}}_0 = \{\mathbf{c}_1, \mathbf{c}_2, \ldots , \mathbf{c}_t\} \subseteq {{\mathcal {C}}}$$ is defined to be the set of words $$\mathbf{x} = (x_1, x_2, \ldots ,x_n)^T$$ such that $$x_i \in \{c_{1,i}, c_{2,i}, \ldots , c_{t,i}\}$$ for all $$i=1, \ldots , n$$ , where $$\mathbf{c}_j=(c_{j,1},c_{j,2},\ldots ,c_{j,n})^T$$ . $${\mathcal {C}}$$ is a $${\overline{t}}$$ -separable code if for any two distinct $${\mathcal {C}}_1, {\mathcal {C}}_2 \subseteq {\mathcal {C}}$$ with $$|{\mathcal {C}}_1| \le t$$ , $$|{\mathcal {C}}_2| \le t$$ , we always have $${\mathsf{desc}}({\mathcal {C}}_1) \ne {\mathsf{desc}}({\mathcal {C}}_2)$$ . Let $$M({\overline{t}},n,q)$$ denote the maximal possible size of such a separable code. In this paper, an upper bound on $$M({\overline{3}},3,q)$$ is derived by considering an optimization problem, and then two constructions for $${\overline{3}}\hbox {-SC}(3,M,q)$$ s are provided by means of perfect hash families and Steiner triple systems. [ABSTRACT FROM AUTHOR]

The Singleton-type bound that offers an upper limit on the minimum Hamming distance for locally repairable codes (LRCs) has been studied by a lot of literatures. However, the work to determine tight Singleton-type bound for LRCs under all parameters is still incomplete. This paper focuses on the tightness of Singleton-type bound for general LRCs (linear and nonlinear). By exploring how the structure of repair sets affects the minimum Hamming distance, some properties for minimum Hamming distance of LRCs are derived. Through these properties, the following results are obtained: 1. The necessary conditions for LRCs whose minimum Hamming distance reaches the previous Singleton-type bound are provided. Due to these necessary conditions, the previous Singleton-type bound is proved to be unreachable under a number of parameters, and the tight Singleton-type bounds are given under some of these parameters. 2. Under a class of parameters where the previous Singleton-type bound for linear LRCs has been proved unreachable in the literatures, we improve Singleton-type bound and show that the new Singleton-type bound is tight. In addition, based on the existing LRC constructions, the previous Singleton-type bound for LRCs is shown to be tight under some other parameters. Finally, for an importance case of LRCs (i.e., every repair set is a 1-erasure correcting code), the Singleton-type bound under three classes of parameters is further improved. [ABSTRACT FROM AUTHOR]