Search

Signed difference sets have interesting applications in communications and coding theory. A (v , k , λ) -difference set in a finite group G of order v is a subset D of G with k distinct elements such that the expressions x y - 1 for all distinct two elements x , y ∈ D , represent each non-identity element in G exactly λ times. A (v , k , λ) -signed difference set is a generalization of a (v , k , λ) -difference set D, which satisfies all properties of D, but has a sign for each element in D. We will show some new existence results for signed difference sets by using partial difference sets, product methods, and cyclotomic classes. [ABSTRACT FROM AUTHOR]

Distributed storage codes have important applications in the design of modern storage systems. In a distributed storage system, every storage node has a probability to fail and once an individual storage node fails, it must be reconstructed using the data stored in the surviving nodes. Computation load and network bandwidth are two important issues we need to concern when repairing a failed node. Generally speaking, the naive maximum distance separable (MDS) storage codes have low repair complexity but high repair bandwidth. On the contrary, minimum storage regenerating codes have low repair bandwidth but high repair complexity. Fortunately, the newly introduced piggybacked codes combine the advantages of both ones. The main result of this paper is a novel piggybacking design framework for (k + r , k) systematic MDS storage codes, where k, r denote the number of systematic nodes and the number of parity nodes, respectively. In the new code, the average repair bandwidth rate for the systematic nodes, i.e., the ratio of the average repair bandwidth of a single failed systematic node and the amount of the original data, can be as low as 2 r + 1 2 r + 3 k + 2 r k 2 , which is roughly 2 r + 1 2 r when the code has high rate k ≫ r . For relatively large r (e.g., r ≥ 6 ), this result significantly improves the previously known one which has average repair bandwidth rate roughly r - 1 2 r - 1 . In the meanwhile, every failed systematic node of the new code can be reconstructed quickly using the decoding algorithm of a classical MDS code, only with some additional additions over the underlying finite field. [ABSTRACT FROM AUTHOR]

Permutation codes under different metrics have been extensively studied due to their potentials in various applications. Generalized Cayley metric is introduced to correct generalized transposition errors, including previously studied metrics such as Kendall's τ -metric, Ulam metric and Cayley metric as special cases. Since the generalized Cayley distance between two permutations is not easily computable, Yang et al. introduced a related metric of the same order, named the block permutation metric. Given positive integers n and d, let C B (n , d) denote the maximum size of a permutation code in S n with minimum block permutation distance d. In this paper, we focus on the theoretical bounds of C B (n , d) and the constructions of permutation codes under block permutation metric. Using a graph theoretic approach, we improve the Gilbert–Varshamov type bound by a factor of Ω (log n) , when d is fixed and n goes into infinity. We also propose a new encoding scheme based on binary constant weight codes. Moreover, an upper bound beating the sphere-packing type bound is given when d is relatively close to n. [ABSTRACT FROM AUTHOR]

The problem of private information retrieval (PIR) gets renewed attentions in recent years due to its information-theoretic reformulation and applications in distributed storage systems. Let M files be stored in a distributed storage system consisting of N servers, where each file is stored via an (N, K)-MDS code. A PIR scheme will allow a user to retrieve a specific file from the distributed storage system without revealing the identity of the file to any T colluding servers. PIR rate is defined as the number of symbols privately retrieved per one downloaded symbol and the supremum of all achievable rates is called the PIR capacity. The capacity has been solved for some degenerate cases, i.e. K = 1 or T = 1 . For the general case K ≥ 2 and T ≥ 2 , the exact PIR capacity remains unknown. In this paper we propose a general private information retrieval scheme for MDS coded databases with colluding servers achieving PIR rate (1 + R + R 2 + ⋯ + R M - 1) , where R = 1 - N - T K N K . Our scheme captures the essence of the optimal schemes for degenerate cases. We also compare our scheme with some other known PIR schemes for non-degenerate cases. The advantages of our scheme include its independence of the property of the storage code and a better performance when the number of files M is small. [ABSTRACT FROM AUTHOR]

Subspace codes and constant dimension codes have become a widely investigated research topic due to their significance to error control in random linear network coding. Rank metric codes in Ferrers diagrams can be used to construct good subspace codes and constant dimension codes. In this paper, three constructions of Ferrers diagram rank metric codes are presented. The first two constructions are based on subcodes of maximum rank distance codes, and the last one generates new codes from known Ferrers diagram rank metric codes. Each of these constructions produces optimal codes with different diagrams and parameters for which no optimal construction was known before. [ABSTRACT FROM AUTHOR]

In the last two decades, parent-identifying codes and traceability codes are introduced to prevent copyrighted digital data from unauthorized use. They have important applications in the scenarios like digital fingerprinting and broadcast encryption schemes. A major open problem in this research area is to determine the upper bounds for the cardinalities of these codes. In this paper we will focus on this theme. Consider a code of length N which is defined over an alphabet of size q. Let MIPPC(N,q,t) and MTA(N,q,t) denote the maximal cardinalities of t-parent-identifying codes and t-traceability codes, respectively, where t is known as the strength of the codes. We show MIPPC(N,q,t)≤rq⌈N/(v-1)⌉+(v-1-r)q⌊N/(v-1)⌋, where v=⌊(t/2+1)2⌋, 0≤r≤v-2 and N≡rmod(v-1). This new bound improves two previously known bounds of Blackburn, and Alon and Stav. On the other hand, MTA(N,q,t) is still not known for almost all t. In 2010, Blackburn, Etzion and Ng asked whether MTA(N,q,t)≤cq⌈N/t2⌉ or not, where c is a constant depending only on N, and they have shown the only known validity of this bound for t=2. By using some complicated combinatorial counting arguments, we prove this bound for t=3. This is the first non-trivial upper bound in the literature for traceability codes with strength three. [ABSTRACT FROM AUTHOR]

Motivated by the application of high-density data storage technologies, symbol-pair codes are proposed to protect against pair-errors in symbol-pair channels, whose outputs are overlapping pairs of symbols. The research of symbol-pair codes with the largest minimum pair-distance is interesting since such codes have the best possible error-correcting capability. A symbol-pair code attaining the maximal minimum pair-distance is called a maximum distance separable (MDS) symbol-pair code. In this paper, we focus on constructing linear MDS symbol-pair codes over the finite field Fq. We show that a linear MDS symbol-pair code over Fq with pair-distance 5 exists if and only if the length n ranges from 5 to q2+q+1. As for codes with pair-distance 6, length ranging from q+2 to q2, we construct linear MDS symbol-pair codes by using a configuration called ovoid in projective geometry. With the help of elliptic curves, we present a construction of linear MDS symbol-pair codes for any pair-distance d+2 with length n satisfying 7≤d+2≤n≤q+⌊2q⌋+δ(q)-3, where δ(q)=0 or 1. [ABSTRACT FROM AUTHOR]

The problem of packing n-dimensional subspaces of m-dimensional Euclidean space such that these subspaces are as far apart as possible was introduced by Conway, Hardin and Sloane. It can be seen as a higher dimensional version of spherical codes or equiangular lines. In this paper, we first give a general construction of equiangular lines, and then present a family of equiangular lines with large size from direct product difference sets. Meanwhile, for packing higher dimensional subspaces, we give three constructions of optimal packings in Grassmannian spaces based on difference sets and Latin squares. As a consequence, we obtain many new classes of optimal Grassmannian packings. [ABSTRACT FROM AUTHOR]

Permutation codes are widely studied objects due to their numerous applications in various areas, such as power line communications, block ciphers, and the rank modulation scheme for flash memories. Several kinds of metrics are considered for permutation codes according to their specific applications. This paper concerns some improvements on the bounds of permutation codes under Hamming metric and Kendall's $$\tau $$ -metric respectively, using mainly a graph coloring approach. Specifically, under Hamming metric, we improve the Gilbert-Varshamov bound asymptotically by a factor n, when the minimum Hamming distance d is fixed and the code length n goes to infinity. Under Kendall's $$\tau $$ -metric, we narrow the gap between the known lower bounds and upper bounds. Besides, we also obtain some sporadic results under Kendall's $$\tau $$ -metric for small parameters. [ABSTRACT FROM AUTHOR]

Symbol-pair code is a new coding framework which is proposed to correct errors in the symbol-pair read channel. In particular, maximum distance separable (MDS) symbol-pair codes are a kind of symbol-pair codes with the best possible error-correction capability. Employing cyclic and constacyclic codes, we construct three new classes of MDS symbol-pair codes with minimum pair-distance five or six. Moreover, we find a necessary and sufficient condition which ensures a class of cyclic codes to be MDS symbol-pair codes. This condition is related to certain property of a special kind of linear fractional transformations. A detailed analysis on these linear fractional transformations leads to an algorithm, which produces many MDS symbol-pair codes with minimum pair-distance seven. [ABSTRACT FROM AUTHOR]

Quantum MDS codes are an important family of quantum codes. In this paper, using generalized Reed-Solomon codes and Hermitian construction, we construct seven classes of quantum MDS codes. All of them provide large minimum distance and most of them are new in the sense that the parameters of quantum codes are different from all the previously known ones. [ABSTRACT FROM AUTHOR]

Permutation polynomials over finite fields constitute an active research area and have applications in many areas of science and engineering. In this paper, four classes of monomial complete permutation polynomials and one class of trinomial complete permutation polynomials are presented, one of which confirms a conjecture proposed by Wu et al. (Sci China Math 58:2081-2094, 2015). Furthermore, we give two classes of permutation trinomial, and make some progress on a conjecture about the differential uniformity of power permutation polynomials proposed by Blondeau et al. (Int J Inf Coding Theory 1:149-170, 2010). [ABSTRACT FROM AUTHOR]

Complete reducible super-simple (CRSS) designs are closely related to $$q$$ -ary constant weight codes. A $$(v,k,\lambda )$$ -CRSS design is just an optimal $$(v,2(k-1),k)_{\lambda +1}$$ code. In this paper, we mainly investigate the existence of a $$(v,5,2)$$ -CRSS design and show that such a design exists if and only if $$v\equiv 1,5\pmod {20}$$ and $$v\ge 21$$ , except possibly when $$v = 25$$ . Using this result, we determine the maximum size of an $$(n,8,5)_3$$ code for all $$n\equiv 0,1,4,5 \pmod {20}$$ with the only length $$n=25$$ unsettled. In addition, we also construct super-simple $$(v,5,3)$$ -BIBDs for $$v=45,65$$ . [ABSTRACT FROM AUTHOR]

Planar functions in odd characteristic were introduced by Dembowski and Ostrom in order to construct finite projective planes in 1968. They were also used in the constructions of DES-like iterated ciphers, error-correcting codes, and signal sets. Recently, a new notion of pseudo-planar functions in even characteristic was proposed by Zhou. These new pseudo-planar functions, as an analogue of planar functions in odd characteristic, also bring about finite projective planes. There are three known infinite families of pseudo-planar monomial functions constructed by Schmidt and Zhou, and Scherr and Zieve. In this paper, three new classes of pseudo-planar binomials are provided. Moreover, we find that each pseudo-planar function gives an association scheme which is defined on a Galois ring. [ABSTRACT FROM AUTHOR]

The exact sizes of optimal $$q$$ -ary codes of length $$n$$ , constant weight $$w$$ and distance $$d=2w-1$$ have only been determined for $$q\in \{2,3\}$$ , and for $$w|(q-1)n$$ and $$n$$ sufficiently large. We completely determine the exact size of optimal $$q$$ -ary codes of constant weight three and minimum distance five for all $$q$$ by establishing a connection with Hanani triple packings, and settling their existence. [ABSTRACT FROM AUTHOR]

Perfect $$t$$ -deletion-correcting codes of length $$n$$ over the alphabet of size $$q$$ , denoted by perfect $$(n,t)_q\text {-DCCs}$$ , can have different number of codewords, because the balls of radius $$t$$ with respect to Levenshteĭn distance may be of different sizes. Thus determining all possible sizes of a perfect $$t$$ -deletion-correcting code makes sense. When $$t=n-2$$ , $$t$$ -deletion-correcting codes are closely related to directed packings, constructions of which are based on the tools of design theory. Recently, Chee, Ge and Ling determined completely the spectrum of possible sizes for perfect $$q$$ -ary 1-deletion-correcting codes of length three for all $$q$$ , and perfect $$q$$ -ary 2-deletion-correcting codes of length four for all but $$19$$ values of $$q$$ . In this paper, we continue to investigate the spectrum problem for perfect $$(4,2)_q\text {-DCCs}$$ . By constructing a considerable number of incomplete directed packings, we give an almost complete solution to the spectrum problem of sizes for perfect $$(4,2)_q\text {-DCCs}$$ , leaving the existence of $$(4,2)_{19}\text {-DCC}$$ of size $$62$$ and $$(4,2)_{34}\text {-DCC}$$ of size $$196$$ in doubt. [ABSTRACT FROM AUTHOR]

Non-uniform group divisible designs have been studied by numerous researchers in the past two decades due to their vital applications in the constructions for other types of designs. Much progress has been made for the existence of $$\{4\}$$ -GDDs of type $$g^um^1$$ , especially when $$gu$$ is even. The corresponding problem for block size three had been solved by Colbourn et al. (J Comb Theory Ser A 59:73-89, ). In this paper, we consider the entire existence problem for such $$\{4\}$$ -GDDs. We show that, for each given g, up to a small number of undetermined cases of $$u$$ , the necessary conditions on $$(u,m)$$ for the existence of a $$\{4\}$$ -GDD of type $$g^um^1$$ are also sufficient. [ABSTRACT FROM AUTHOR]

The known families of difference sets can be subdivided into three classes: difference sets with Singer parameters, cyclotomic difference sets, and difference sets with gcd $$(v,n)>1$$ . It is remarkable that all the known difference sets with gcd $$(v,n)>1$$ have the so-called character divisibility property. Jungnickel and Schmidt (Difference sets: an update. London Math. Soc. Lecture Note Ser., vol. 245, pp. 89-112, Cambridge University Press, Cambridge ) posed the problem of constructing difference sets with gcd $$(v,n)>1$$ that do not satisfy this property. In an attempt to attack this problem, we use difference sets with three nontrivial character values as candidates, and get some necessary conditions. [ABSTRACT FROM AUTHOR]

Constructing non-uniform designs has become a topic of considerable interest over the last two decades due to the vital role of such designs in the constructions for other types of designs. Ge, Rees and Shalaby started the investigation into the spectrum of non-uniform Kirkman frames of type $$h^{u}m^{1}$$. They determined the spectrum for the cases where $$h\in \{2,4,6,8,10,12\}$$, leaving 24 cases of $$(h,u,m)$$. In this paper, we continue to investigate this spectrum problem by removing all of these 24 possible exceptions. Using this result, we show that for each value of $$h \equiv 0 {\,\,\mathrm{mod}\, 12}\,$$ the obvious necessary conditions on $$u, m$$ are also sufficient. [ABSTRACT FROM AUTHOR]

Constant-composition codes are a special type of constant-weight codes and have attracted recent interest due to their numerous applications. In a recent work, the authors found that an optimal ( n, 5, [2, 1, 1])-code of constant-composition can be obtained from a Room square of side n with super-simple property. In this paper, we study the existence problem of super-simple Room squares. The problem is solved leaving only two minimal possible n undetermined. [ABSTRACT FROM AUTHOR]

A Steiner quadruple system of order v is an ordered pair $${(X, \mathcal{B})}$$, where X is a set of cardinality v, and $${\mathcal{B}}$$ is a set of 4-subsets of X, called blocks, with the property that every 3-subset of X is contained in a unique block. Such designs exist if and only if $${v \equiv 2,4\, (\bmod\, 6)}$$. The first and second proofs of this result were given by Hanani in and in , respectively. All the existing proofs are rather cumbersome, even though simplified proofs have been given by Lenz in and by Hartman in . To study Steiner quadruple systems, Hanani introduced the concept of H-designs in . The purpose of this paper is to provide an alternative existence proof for Steiner quadruple systems via H-designs of type 2. In , Mills showed that for n > 3, n ≠ 5, an H-design of type g exists if and only if ng is even and g( n − 1)( n − 2) is divisible by 3, where the main context is the complicated existence proof for H-designs of type 2. However, Mill's proof was based on the existence result of Steiner quadruple systems. In this paper, by using the theory of candelabra systems and H-frames, we give a new existence proof for H-designs of type 2 independent of the existence result of Steiner quadruple systems. As a consequence, we also provide a new existence proof for Steiner quadruple systems. [ABSTRACT FROM AUTHOR]

Let K( n, w, t, d) be the minimum size of a code over Z of length n, constant weight w, such that every word with weight t is within Hamming distance d of at least one codeword. In this article, we determine K( n, 4, 3, 1) for all n ≥ 4, q = 3, 4 or q = 2 + 1 with m ≥ 2, leaving the only case ( q, n) = (3, 5) in doubt. Our construction method is mainly based on the auxiliary designs, H-frames, which play a crucial role in the recursive constructions of group divisible 3-designs similar to that of candelabra systems in the constructions of 3-wise balanced designs. As an application of this approach, several new infinite classes of nonuniform group divisible 3-designs with block size four are also constructed. [ABSTRACT FROM AUTHOR]

n H-design is said to be (1, α)-resolvable, if its block set can be partitioned into α-parallel classes, each of which contains every point of the design exactly α times. When α = 1, a (1, α)-resolvable H-design of type g is simply called a resolvable H-design and denoted by RH( g), for which the general existence problem has been determined leaving mainly the case of g ≡ 0 (mod 12) open. When α = 2, a (1, 2)-RH(1) is usually called a (1, 2)-resolvable Steiner quadruple system of order n, for which the existence problem is far from complete. In this paper, we consider these two outstanding problems. First, we prove that an RH(12) exists for all n ≥ 4 with a small number of possible exceptions. Next, we give a near complete solution to the existence problem of (1, 2)-resolvable H-designs with group size 2. As a consequence, we obtain a near complete solution to the above two open problems. [ABSTRACT FROM AUTHOR]

A Uniformly Resolvable Design (URD) is a resolvable design in which each parallel class contains blocks of only one block size k, such a class is denoted k -pc and for a given k the number of k -pcs is denoted r k. In this paper we consider the case of block sizes 3 and 4. The cases r3 = 1 and r4 = 1 correspond to Resolvable Group Divisible Designs (RGDD). We prove that if a 4-RGDD of type h u exists then all admissible {3, 4}-URDs with 12 hu points exist. In particular, this gives existence for URD with v ≡ 0 (mod 48) points. We also investigate the case of URDs with a fixed number of k -pc. In particular, we show that URDs with r3 = 4 exist, and that those with r3 = 7, 10 exist, with 11 and 12 possible exceptions respectively, this covers all cases with 1 < r3 ≤ 10. Furthermore, we prove that URDs with r4 = 7 exist and that those with r4 = 9 exist, except when v = 12, 24 and possibly when v = 276. In addition, we prove that there exist 4-RGDDs of types 2 142, 2 346 and 6 54. Finally, we provide four {3,5}-URDs with 105 points. [ABSTRACT FROM AUTHOR]

Combinatorial characterizations of one-coincidence frequency-hopping (FH) sequences are provided in terms of perfect Mendelsohn packings. As a consequence, results on perfect Mendelsohn packings can be immediately applied to one-coincidence FH sequences. [ABSTRACT FROM AUTHOR]