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

张菊玲, 郭文强, 杨晓梅, 朱义鑫, 杨国武

电子科技大学学报 ›› 2023, Vol. 52 ›› Issue (01) : 102-107.

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

  • 张菊玲, 郭文强, 杨晓梅, 朱义鑫, 杨国武
作者信息 +
History +

摘要

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

关键词

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

中图分类号

TM13

引用本文

导出引用
张菊玲, 郭文强, 杨晓梅, 朱义鑫, 杨国武. 正规式布尔函数NPN等价匹配算法. 电子科技大学学报. 2023, 52(01): 102-107

基金

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

评论

Accesses

Citation

Detail

段落导航
相关文章

/