Bounds and Polynomial-Time Construction Algorithm for X-Codes of Constant Weight Three
Yu Tsunoda, Yuichiro Fujiwara · 2018
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.