正规式布尔函数NPN等价匹配算法

摘要

通过对香农分解代数余子式的运算研究，发现了对称变量和独立变量在NP等价变换中的6个属性，充分利用变量的对称性和独立性NP变换后的不变性、独立变量相位不确定性、在NP匹配中独立变量识别其他变量和其他变量识别独立变量的不可用性，提出了一种基于正规式的布尔函数NPN等价匹配算法。通过对大量MCNC标准电路库中电路和随机生成电路的7-22变量布尔函数的匹配实验，在两个实验电路集上本文算法与基于高阶通用特征匹配算法相比，匹配过程中的搜索空间平均减少了58.8%、布尔匹配的速度提高了45.6%，能够为电路优化和电路映射提供更加快速和有效的布尔匹配。

关键词

布尔差分 / 正规式 / NPN等价 / 独立变量 / 香农分解

基金资助

新疆维吾尔自治区自然科学基金(2019D01A27)