Bounds and Polynomial-Time Construction Algorithm for X-Codes of Constant Weight Three

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\times 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=\Theta(m^{2})$ , here we show that for $d\geq 4$ the largest possible $n$ is $o(m^{2})$ . 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$ .