| 基于对称及特征的NPN布尔匹配算法 |
| |
| 引用本文： | 张菊玲,杨国武,吴尽昭,郭文强.基于对称及特征的NPN布尔匹配算法[J].电子科技大学学报（自然科学版）,2018,47(6):876-881. |
| |
| 作者姓名： | 张菊玲 杨国武 吴尽昭 郭文强 |
| |
| 作者单位： | 1.电子科技大学计算机科学与工程学院大数据研究中心 成都 611731 |
| |
| 基金项目： | 国家自然科学基金61572109国家自然科学基金11371003国家自然科学基金61163066 |
| |
| 摘 要： | 该文提出了一种基于对称及特征的成对比较的NPN布尔匹配算法, 利用变量对称、1阶特征向量及香农分解设计完成了NPN布尔匹配。算法利用具有相同1阶特征向量是两个布尔函数NP等价的必要条件, 和具有相同1阶特征是两个变量具有映射关系的必要条件搜索两个布尔函数之间的候选变换并进行验证。对称及特征的使用降低了候选变换搜索的空间, 提高了NPN等价匹配的速度。
|
| 关 键 词： | NPN等价 香农分解 工艺映射 变量映射 变量对称 |
| 收稿时间： | 2017-12-26 |
NPN Boolean Matching Algorithm Based on Symmetry and Signature |
| |
| Affiliation: | 1.Big Data Research Center, School of Computer Science and Engineering, University of Electronic Science and Technology of China Chengdu 6117312.Guangxi Key Laboratory of Hybrid Computation and IC Design Analysis, Guangxi University for Nationalities Nanning 5300063.School of Computer Science and Engineering, Xinjiang University of Finance and Economics Urumqi 830012 |
| |
| Abstract: | The paper proposes a pairwise NPN (Input Negation and/or Input Permutation and/or Output Negation) Boolean matching algorithm based on symmetry and signature.The algorithm utilizes variable symmetry, the first order signature vector and Shannon decomposition to design and implement NPN Boolean matching.The candidate NP transformations between two functions are searched and verified through two necessary conditions:1) two NP equivalent Boolean functions must have the same the first order signature vector and 2) two variables having a mapping relation must have the same the first order signature.The use of symmetry and signature reduces the search space of the candidate NP transformations and speeds up NPN Boolean matching process. |
| |
| Keywords: | |
|
| 点击此处可从《电子科技大学学报（自然科学版）》浏览原始摘要信息 |
|
点击此处可从《电子科技大学学报（自然科学版）》下载全文 |
