We settle the problem of determining the asymptotic behavior of the parameters of optimal difference systems of sets, or DSSes for short, which were originally introduced for computationally efficient frame synchronization under the presence of additive noise. We prove that the lowest achievable redundancy of a DSS asymptotically attains Levenshtein's lower bound for any alphabet size and relative index, answering the question of Levenshtein posed in 1971. Our proof is probabilistic and gives a linear-time randomized algorithm for constructing asymptotically optimal DSSes with high probability for any alphabet size and information rate. This provides efficient self-synchronizing codes with strong noise resilience. We also point out an application of DSSes to phase detection.

Weak superimposed codes are combinatorial structures related closely to generalized cover-free families, superimposed codes, and disjunct matrices in that they are only required to satisfy similar but less stringent conditions. This class of codes may also be seen as a stricter variant of what are known as locally thin families in combinatorics. Originally, weak superimposed codes were introduced in the context of multimedia content protection against illegal distribution of copies under the assumption that a coalition of malicious users may employ the averaging attack with adversarial noise. As in many other kinds of codes in information theory, it is of interest and importance in the study of weak superimposed codes to find the highest achievable rate in the asymptotic regime and give an efficient construction that produces an infinite sequence of codes that achieve it. Here, we prove a tighter lower bound than the sharpest known one on the rate of optimal weak superimposed codes and give a polynomial-time randomized construction algorithm for codes that asymptotically attain our improved bound with high probability. Our probabilistic approach is versatile and applicable to many other related codes and arrays.

X-codes form a special class of linear maps which were originally introduced for data compression in VLSI testing and are also known to give special parity-check matrices for linear codes suitable for error-erasure channels. In the context of circuit testing, an (m, n, d, x) X-code compresses n-bit output data R from the circuit under test into m bits, while allowing for detecting the existence of an up to d-bit-wise anomaly in R even if up to x bits of the original uncompressed R are unknowable to the tester. Using probabilistic combinatorics, we give a nontrivial lower bound for any d ≥ 2 on the maximum number n of codewords such that an (m, n, d, 2) X-code of constant weight 3 exists. This is the first result that shows the existence of an infinite sequence of X-codes whose compaction ratio tends to infinity for any fixed d under severe weight restrictions. We also give a deterministic polynomial-time algorithm that produces X-codes that achieve our bound.

It is known that redundant parity-check equations can improve the performance of an LDPC code by reducing the number of harmful substructures in the parity-check matrix. However, it is a difficult problem to design a parity-check matrix in such a way that it avoids substructures that are known to be harmful to iterative decoding while keeping the number of redundant parity-check equations moderate and ensuring other desirable properties. We explicitly give redundant parity-check matrices for cyclic regular LDPC codes of length n and minimum distance d ~ √n in which there are only n parity-check equations but no stopping sets of size d+1 or smaller except for those that correspond to the nonzero codewords of the smallest weight. We do this by showing that the well-known projective LDPC codes from the incidence matrices of projective planes PG(2, q) with q even have this property. This result may give insight into how the small number of redundant parity-check equations in the geometric LDPC codes may be contributing to the good performance reported in the literature. We also give a slightly improved upper bound on the size of a smallest generic erasure correcting set.

X-codes are special linear maps for a compression technique, called X-compact. In the context of integrated circuit testing, an (m, n, d, x) X-code is an m×n binary matrix which compresses n-bit output from the circuit under test into m bits while allowing for detecting the existence of up to d erroneous output bits even if up to x bits of the correct behavior are unknowable. In particular, X-codes of constant column weight x+1 are of special interest for practical reasons. While it is known that there exist infinite series of (m, n, 1, 2) X-codes of constant weight 3 with n=Θ(m2), here we show that for d ≥ 4 the largest possible n is o(m2). This is an application of extremal graph theory and the first asymptotic improvement on this problem. We also investigate a special class of X-codes of constant weight 3 with a design theoretic property that boosts test quality when there are fewer unknowable bits than anticipated. We improve the tightest known lower bound on the largest number n of columns of an X-code of this kind through probabilistic combinatorics. A deterministic algorithm is also given that produces X-codes of this type attaining the improved bound and runs in time polynomial in m.

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.

X-codes are linear maps with a special combinatorial property that generalizes superimposed codes, disjunct matrices, and cover-free families. In the context of circuit testing, a (t, n, d, x) X-code compresses n-bit output from the circuit under test into t bits while allowing for detecting the existence of up to d erroneous output bits even if up to x bits of the correct behavior are unknowable. A simple counting argument shows that a (t, n, d, x) X-code with t = O (log n) exists, where the coefficient of the logarithmic term when the base is 2 is at most 2x+1(d + x)ln 2 with In being the natural logarithm to base e. While there are also known constructions that provide X-codes with smaller t for given n and some specific d and x, no stronger general upper bounds on the smallest possible t that work for any d and x are available in the literature. Here, we derive general upper bounds in closed form that reduce the coefficient of the basic general bound to (x + 1)(d + x - 1)e ln 2. In terms of the highest achievable rate, our results exponentially improve the known asymptotic lower bound 1/(2x+1(d + x) ln2) to 1/((x + 1)(d + x - 1)e ln 2).

The trapping redundancy of a linear code is the number of rows of a smallest parity-check matrix such that no submatrix forms an (a, b)-trapping set. This concept was first introduced in the context of low-density parity-check (LDPC) codes in an attempt to estimate the number of redundant rows in a parity-check matrix suitable for iterative decoding. Essentially the same concepts appear in other contexts as well such as robust syndrome extraction for quantum error correction. Among the known upper bounds on the trapping redundancy, the strongest one was proposed by employing a powerful tool in probabilistic combinatorics, called the Lovász Local Lemma. Unfortunately, the proposed proof invoked this tool in a situation where an assumption made in the lemma does not necessarily hold. Hence, although we do not doubt that nonetheless the proposed bound actually holds, for it to be a mathematical theorem, a more rigorous proof is desired. Another disadvantage of the proposed bound is that it is only applicable to (a, b)-trapping sets with rather small a. Here, we give a more general and sharper upper bound on trapping redundancy by making mathematically more rigorous use of probabilistic combinatorics without relying on the lemma. Our bound is applicable to all potentially avoidable (a, b)-trapping sets with a smaller than the minimum distance of a given linear code, while being generally much sharper than the bound through the Lovász Local Lemma. In fact, our upper bound is sharp enough to exactly determine the trapping redundancy for many cases, thereby providing precise knowledge in the form of a more general bound with mathematical rigor.