Threshold Function Identification by Redundancy Removal and Comprehensive Weight Assignments
Threshold Function Identification by Redundancy Removal and Comprehensive Weight Assignments
复制标题
通过冗余去除和综合权重分配来识别阈值函数
DOI：
10.1109/tcad.2018.2878181
复制
发表时间：
2019
影响因子：
2.9
通讯作者：
Sigeru Yamashita
中科院分区：
文献类型：
--
作者：
Chin-Heng Liu;Chia-Chun Lin;Yung-Chih Chen;Chia-Cheng Wu;Chun-Yao Wang;Sigeru Yamashita
阈值函数（TF）的识别决定了布尔函数是否可以用线性阈值逻辑门（LTG）表示，是阈值逻辑理论中的一项基本但重要的任务。本文通过构建不冗余不等式系统并综合调整权重分配，提出了一种更加高效有效的TF识别算法。这是第一个能够识别所有八输入 TF 的非基于 ILP 的方法。实验结果表明，所提出的方法比所有现有的非基于 ILP 的方法更有效，并且所提出的方法获得的 LTG 对于接近 100% 的情况都是最佳的。对于具有 9-15 个输入的 TF，所提出的方法可以在合理的 CPU 时间内识别 100 000 个随机生成的 TF。
The identification of threshold function (TF), which determines whether a Boolean function can be represented by an linear threshold logic gate (LTG) or not, is a fundamental but important task in the theories of threshold logic. In this paper, we propose a more efficient and effective algorithm of TF identification by constructing the system of irredundant inequalities and adjusting the weight assignment comprehensively. This is the first non-ILP-based approach that is able to identify all the eight-input TFs. The experimental results demonstrated that the proposed approach is more effective than all the existing non-ILP-based approaches and the LTGs obtained by the proposed approach are optimal for near 100% cases. For TFs with 9–15 inputs, the proposed approach can identify 100 000 randomly generated TFs as well in a reasonable CPU time.