On the maximum number of codewords of X-codes of constant weight three
On the maximum number of codewords of X-codes of constant weight three
复制标题
恒权三X码最大码字数的探讨
DOI：
10.1109/isit.2019.8849238
复制
发表时间：
2019
期刊：
影响因子：
--
通讯作者：
Y. Tsunoda
中科院分区：
文献类型：
--
作者：
Y. Fujiwara;Y. Tsunoda
X 代码形成了一类特殊的线性映射，最初是为了 VLSI 测试中的数据压缩而引入的，并且还可以为适合错误擦除通道的线性代码提供特殊的奇偶校验矩阵。在电路测试中，(m, n, d, x) X 代码将被测电路的 n 位输出数据 R 压缩为 m 位，同时允许检测 R 中是否存在最多 d 位异常，即使测试人员无法得知原始未压缩 R 的最多 x 位。使用概率组合学，我们为最大数量 n 的码字上的任何 d ≥ 2 给出一个非平凡的下界，使得存在恒定权重 3 的 (m, n, d, 2) X 代码。这是第一个结果，表明存在无限的 X 代码序列，在严格的重量限制下，对于任何固定的 d，其压缩比趋于无穷大。我们还给出了一种确定性多项式时间算法，可以生成达到我们界限的 X 代码。
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.