Abstract

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=Θ(m^2), here we show that for d ≥ 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.

The 2018 IEEE International Symposium on Information Theory was held at Hotel Talisa in Vail, Colorado, USA, from June 17 to June 22, 2018. The travel was supported by the NEC C&C Foundation and the Chiba University SEEDS Fund.