Bounds and Polynomial-Time Construction Algorithm for X-Codes of Constant Weight Three
Bounds and Polynomial-Time Construction Algorithm for X-Codes of Constant Weight Three
复制标题
DOI：
10.1109/isit.2018.8437884
复制
发表时间：
2018-06
期刊：
影响因子：
--
通讯作者：
Y. Tsunoda;Yuichiro Fujiwara
中科院分区：
文献类型：
--
作者：
Y. Tsunoda;Yuichiro Fujiwara
X编码是压缩技术的特殊线性图，称为X-COMPACT。在集成电路测试的背景下，An（m，n，d，x）x代码是$ m \ times n $二进制矩阵，可压缩来自测试的电路的n位输出到$ m $位，同时允许即使最多不知情的是$ x $的位置，检测最多$ d $错误的输出位。特别是，出于实际原因，恒定柱重量x+1的X编码是特别的兴趣。虽然众所周知，存在无限序列（m，n，1，2）contant Weight 3的X代码3，带有$ n = \ theta（m^{2}）$，但我们在这里表明，对于$ d \ geq 4 $最大的$ n $是$ o（m^{2}）$。这是极端图理论的应用，也是该问题的第一个渐近改进。我们还研究了具有设计理论特性的恒定重量3的特殊类别X编码，该特性在不可预期的不可知位时提高了测试质量。我们通过概率组合制剂改善了此类X代码的最大数量$ n $ $ n $ $ n $。还给出了一种确定性算法，该算法会产生这种类型的X编码，从而获得了改进的绑定并在$ m $中运行多项式。
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$.