基于对称及特征的NPN布尔匹配算法  

NPN Boolean Matching Algorithm Based on Symmetry and Signature

作　　者：张菊玲 杨国武[1] 吴尽昭[3] 郭文强[2] ZHANG Ju-ling;YANG Guo-wu;WU Jin-zhao;GUO Wen-qiang(Big Data Research Center,School of Computer Science and Engineering,University of Electronic Science and Technology of China Chengdu 611731;Guangxi Key Laboratory of Hybrid Computation and IC Design Analysis,Guangxi University for Nationalities Nanning 530006;School of Computer Science and Engineering,Xinjiang University of Finance and Economics Urumqi 830012)

机构地区：[1]电子科技大学计算机科学与工程学院大数据研究中心,成都611731 [2]新疆财经大学计算机科学与工程学院,乌鲁木齐830012 [3]广西民族大学广西混杂计算与集成电路设计分析重点实验室,南宁530006

出　　处：《电子科技大学学报》2018年第6期876-881,共6页Journal of University of Electronic Science and Technology of China

基　　金：国家自然科学基金(61572109,11371003,61163066)。

摘　　要：该文提出了一种基于对称及特征的成对比较的NPN布尔匹配算法,利用变量对称、1阶特征向量及香农分解设计完成了NPN布尔匹配。算法利用具有相同1阶特征向量是两个布尔函数NP等价的必要条件,和具有相同1阶特征是两个变量具有映射关系的必要条件搜索两个布尔函数之间的候选变换并进行验证。对称及特征的使用降低了候选变换搜索的空间,提高了NPN等价匹配的速度。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.

关 键 词：NPN等价 香农分解 工艺映射 变量映射 变量对称 

分 类 号：TP302.2[自动化与计算机技术—计算机系统结构]