Abstract

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 2^{x + 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/(2^{x + 1} (d + x) ln2) to 1/((x + 1)(d + x - 1)e ln 2).

The 2017 IEEE International Symposium on Information Theory was held at the Eurogress Aachen in Aachen, Germany, from June 25 to 30, 2017 [Conference Website]. The travel was supported by the Chiba University SEEDS Fund.