Search

Given n items with at most d of which being positive, instead of testing these items individually, the theory of combinatorial group testing aims to identify all positive items using as few tests as possible. This paper is devoted to a fundamental and thirty-year-old problem in the nonadaptive group testing theory. A binary matrix is called d -disjunct if the Boolean sum of arbitrary d columns does not contain another column not in this collection. Let T(d) denote the minimal t , such that there exists a t\times n\,\,d -disjunct matrix with n>t and was conjectured that T(d)\ge (d+1)^{2} . In this paper, we narrow the gap by proving T(d)/d^{2}\ge (15+\sqrt {33})/24$ , a quantity in [6/7,7/8]. [ABSTRACT FROM PUBLISHER]

One central theme in quantum error-correction is to construct quantum codes that have a relatively large minimum distance. In this paper, we first present a construction of classical linear codes based on certain classes of polynomials. Through these classical linear codes, we are able to obtain some new quantum codes. It turns out that some of the quantum codes exhibited here have better parameters than the ones available in the literature. [ABSTRACT FROM PUBLISHER]

Snake-in-the-box codes under Kendall’s \tau -metric are studied in the rank modulation scheme for flash memories, where codewords are a subset of permutations in S_{n} with minimal Kendall’s \tau -distance two, and two cyclically consecutive codewords are connected via a push-to-the-top operation. Studies so far restrict the push-to-the-top operations only on odd indices, resulting in a snake consisting of permutations with the same parity, and thus, the minimal distance constraint is easily satisfied. Asymptotically optimal snake codes have been constructed this way in S2n+1 . As for S2n+2 , this framework keeps the last element fixed, and thus, a snake in S2n+2 is equivalent to a snake in S2n+1 , which is rather trivial. If one wants to do better, then it is inevitable to have some push-to-the-top operations on even indices, resulting in a combination of odd and even permutations in the snake, which increases the difficulty to guarantee the minimal Kendall’s $\tau $ -distance constraint. Thus, Horovitz and Etzion pose the open problem to prove or disprove that the size of the largest snake in ({1}/{4})|S_{2n+2}| . [ABSTRACT FROM PUBLISHER]

Some physical effects that limit the reliability and performance of multilevel flash memories induce errors that have low magnitudes and are dominantly asymmetric. This motivated the application of the asymmetric limited magnitude error model in flash memory. In this paper, we present a new construction of quasi-perfect codes for such errors, and we also study the perfect codes with symmetric errors. Moreover, we show some nonexistence results on perfect codes for correcting single error of limited magnitude. [ABSTRACT FROM PUBLISHER]

Quadratic residue codes are a well-known class of codes. In this paper, we consider the constructions of self-dual codes by higher power residues, especially fourth power residues. New infinite families of self-dual codes over GF(2), GF(3), GF(4), GF(8), and GF(9) are introduced. Some of them have better minimum weight than previously known codes. We also give general results related to the automorphism group of some of these codes. [ABSTRACT FROM PUBLISHER]

Multimedia fingerprinting is an effective technique to trace the sources of pirate copies of copyrighted multimedia contents. Separable codes were introduced to detect colluders taking part in the averaging attack, which is the most feasible approach to perform a collusion attack. In this paper, we provide some improved bounds for the size of separable codes. Using a combinatorial technique named grouping coordinates, we have greatly reduced the upper bound. On the other hand, we also provide some lower bounds for the size of separable codes by both probabilistic and deterministic construction methods. In particular, \( \overline {2}\) -separable codes with asymptotically optimal rate are obtained by the deletion method. [ABSTRACT FROM AUTHOR]

The theory of cyclotomy dates back to Gauss and has a number of applications in combinatorics, coding theory, and cryptography. Cyclotomy over a residue class ring \BBZv can be divided into classical cyclotomy or generalized cyclotomy, depending on v prime or composite. In this paper, we introduce a generalized cyclotomy of order d over \BBZp1^{e1p2^{e2},\ldots, pn^{en}}, which includes Whiteman's and Ding-Helleseth's generalized cyclotomy as special cases. Here, p1,p2,\ldots,pn are pairwise distinct odd primes satisfying d\vert (pi-1) for all 1\leq i\leq n and e1,e2,\ldots,en are positive integers. We derive some basic properties of the corresponding cyclotomic numbers and obtain a general formula to compute them via classical cyclotomic numbers. As applications, we completely solve an open problem and a conjecture on Whiteman's generalized cyclotomy of order four over \BBZp1p2. Besides, we also construct an infinite series of near-optimal codebooks over \BBZp1p2, as well as some infinite series of asymptotically optimal difference systems of sets over \BBZp1^{e1p2^{e2},\ldots,pn^{en}}. [ABSTRACT FROM AUTHOR]

Constant-weight codes play an important role in coding theory. The problem of determining the sizes for optimal quaternary constant-weight codes with length n, weight 4, and minimum Hamming distance 5 ((n,5,4)4 codes) has been investigated in several papers. Although some constructions and several infinite families for such codes with length n\equiv 0,1\pmod4 have been given, the problem is still far from complete. In this paper, we determine the size of an optimal (n,5,4)4 code for each integer n\geq 4 leaving 55 lengths unsolved. Especially, for length n\equiv 0,1\pmod 4, the existence problem of the equivalent combinatorial object, namely the generalized Steiner system, is solved leaving only seven values undetermined. [ABSTRACT FROM AUTHOR]

The sizes of optimal constant-composition codes (CCCs) of weight 3 have been determined by Chee, Ge, and Ling with four cases in doubt. Group divisible codes (GDCs) played an important role in their constructions. In this paper, we study the problem of constructing optimal quaternary CCCs with Hamming weight 4 and minimum distances 5 or 6 through GDCs and Room square approaches. The problem is solved leaving only five lengths undetermined. Previously, the results on the sizes of such quaternary CCCs were scarce. [ABSTRACT FROM AUTHOR]

Constant-composition codes (CCCs) are a generalization of constant weight codes and permutation codes. The concept of group divisible codes, an analog of group divisible designs in combinatorial design theory, was first introduced by Chee et al. This new class of codes has been shown to be useful in recursive constructions of constant-weight codes and constant-composition codes. In this paper, we consider the problem of determining the maximal sizes of ternary constant-composition codes of weight four and distance five using group divisible codes as the main tools. We determine the exact values for these parameters. The previously known results are those with code length no greater than 10. [ABSTRACT FROM AUTHOR]

Recently, Chee and Ling ("Constructions for q-ary constant-weight codes", IEEE Trans. Inf. Theory, vol. 53, no. 1, 135-146, Jan. 2007 ) introduced a new combinatorial construction for q-ary constant-weight codes which reveals a close connection between q-ary constant-weight codes and sets of pairwise disjoint combinatorial designs. In this paper, we study the problem of constructing optimal ternary constant-weight codes with Hamming weight four and minimum distance six using this approach. The construction here exploits completely reducible super simple designs and group divisible codes. The problem is solved leaving only two cases undetermined. Previously, the sizes of constant-weight codes of weight four and distance six were known only for those of length no greater than 10. [ABSTRACT FROM AUTHOR]

Describes the direct constructions for optimal optical orthogonal codes. Constructions via skew starters; Auxiliary designs of recursive constructions; Required designs for the creation of optimal codes.

The centralized coded caching scheme is a technique proposed by Maddah-Ali and Niesen as a method to reduce the network burden in peak times in a wireless network system. Yan et al. reformulate the problem as designing a corresponding placement delivery array and propose two new schemes from this perspective. These schemes significantly reduce the rate compared with the uncoded caching schemes. However, to implement these schemes, each file should be cut into $F$ pieces, where $F$ grows exponentially with the number of users $K$. Such a constraint is obviously infeasible in the practical setting, especially when $K$ is large. Thus, it is desirable to design caching schemes with constant rate $R$ (independent of $K$ ) as well as smaller $F$. In this paper, we view the centralized coded caching problem in a hypergraph perspective and show that designing a feasible placement delivery array is equivalent to constructing a linear and (6,3)-free 3-uniform 3-partite hypergraph. Several new results and constructions arise from our novel point of view. First, by using the famous (6,3)-theorem in extremal graph theory, we show that constant rate placement delivery arrays with $F$ growing linearly with $K$ do not exist. Second, we present two infinite classes of placement delivery arrays to show that constant rate caching schemes with $F$ growing sub-exponentially with $K$ do exist. [ABSTRACT FROM AUTHOR]

Constacyclic codes which generalize the classical cyclic codes have played important roles in recent constructions of many new quantum maximum distance separable (MDS) codes. However, the mathematical mechanism may not have been fully understood. In this paper, we use pseudo-cyclic codes, which is a further generalization of constacyclic codes, to construct the quantum MDS codes. We can not only provide a unified explanation of many previous constructions, but also produce some new quantum MDS codes. [ABSTRACT FROM AUTHOR]

Permutation codes have been shown to be useful in power line communications, block ciphers, and multilevel flash memory models. Construction of such codes is extremely difficult. In fact, the only general lower bound known is the Gilbert–Varshamov type bound. In this paper, we establish a connection between permutation codes and independent sets in certain graphs. Using the connection, we improve the Gilbert–Varshamov bound asymptotically by a factor \log (n), when the code length n goes to infinity. [ABSTRACT FROM PUBLISHER]

Constant-weight codes (CWCs) play an important role in coding theory. The problem of determining the sizes for optimal ternary CWCs with length n, weight 4, and minimum Hamming distance 5 ((n,5,4)3 code) has been settled for all positive integers n\leq 10 or n > 10 and n\equiv 1\pmod 3 with n\in \13,52,58\ undetermined. In this paper, we investigate the problem of constructing optimal (n,5,4)3 codes for all lengths n with the tool of group divisible codes. We determine the size of an optimal (n,5,4)3 code for each integer n\geq 4 leaving the lengths n\in \12,13,21,27,33,39,45,52\ unsolved. [ABSTRACT FROM PUBLISHER]

The determination of weight distribution of cyclic codes involves the evaluation of Gauss sums and exponential sums. Despite some cases where a neat expression is available, the computation is generally rather complicated. In this note, we determine the weight distribution of a class of reducible cyclic codes whose dual codes may have arbitrarily many zeros. This goal is achieved by building an unexpected connection between the corresponding exponential sums and the spectra of Hermitian forms graphs. [ABSTRACT FROM PUBLISHER]