Abstract

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.

The 2019 IEEE International Symposium on Information Theory was held at the Maison de la Mutualité in Paris from July 7 to 12, 2019 [Conference website]. The travel was supported by the Telecommunications Advancement Foundation.