布尔函数NPN等价分类及等价匹配的研究

摘要

布尔函数等价分类是逻辑设计和开关理论中的重要难题之一，等价分类的目标是按照分类规则找到互相等价的一组布尔函数，可以使用一组具有代表性的函数来处理大量布尔函数。布尔函数等价匹配是在给定的准则下判断两个布尔函数是否等价的算法，相互等价的两个布尔函数可以使用其中一个布尔函数的电路实现另一个布尔函数的电路。布尔函数等价匹配在逻辑综合中有重要的应用，因此成为了研究热点之一。本文主要研究了在NPN等价准则下的布尔函数等价分类及等价匹配问题。 基于对群代数理论的学习，本文研究了布尔函数NPN等价分类计数问题。论文将所有的置换映射和非映射结合在一起共同组成了(NP)群，成功的将布尔函数NP等价分类问题转换为求(NP)群作用下的等价类问题。利用Po′lya计数方法和Burnside引理推导出了一种新的计算布尔函数NP和NPN等价分类个数的方法。该方法将m变量布尔函数NP等价分类的计算复杂度从22m降低到(m+1)!，显著地提高了布尔函数NP和NPN等价分类的效率。通过本文提出的方法计算出了3-10变量布尔函数的NP和NPN等价分类数。 布尔函数NPN等价匹配算法在工艺库映射和组合逻辑验证中有着广泛的应用，人们提出了多个不同种类的布尔函数NPN等价匹配方法。本文主要研究了成对比较和基于正规式的布尔函数NPN等价匹配算法。通过对前人所提出的布尔函数NPN等价匹配算法及理论知识的学习和研究，论文提出了两个新的成对比较和一个基于正规式的布尔函数NPN等价匹配算法。通过对这三个算法的运行，论文测试了7-22变量布尔函数NPN等价匹配的搜索空间指标和运行速度指标，并且与文献[1]中提出的算法进行了比对。 基于布尔函数的二叉决策图（Binary Decision Diagrams, BDD）的表示，本文提出了一种组合特征即结构化特征（Structural Signature, SS）。根据布尔函数输入变量的1-阶特征及其对称性与NP变换的独立性，以及具有映射关系的变量在Shannon分解过程中1-阶特征同步变化的性质，本文提出了基于结构化特征的布尔函数NPN等价匹配算法。算法利用变量的SS值建立变量映射，通过变量对称、相位冲突检测和变量分组过滤错误的变量映射及删除错误的NP变换。这些方法的使用减少了算法的搜索空间并提高了布尔函数NPN等价匹配速度。 基于本文所提出的SS特征，结合Shannon余子式的布尔差分运算，本文提出了结构化差分特征（Structural Boolean Difference Signature, SDS）。布尔差分特征的引入使得SDS特征相对SS特征可以分离出布尔函数中的独立变量以及更好的区分变量，从而更快的搜索到正确的变量映射和NP变换。结构化差分特征的提出在更大程度上地减少了布尔函数NPN等价匹配的搜索空间和加快了匹配进程。论文从可搜索到的NP变换数、候选NP变换数和分解次数三个方面分析并说明了基于SDS特征的布尔函数NPN等价匹配算法的优越性。 本文还提出了一种新的基于正规式的布尔函数NPN等价匹配算法，说明了每个布尔函数都有一个唯一的DC（Boolean Difference and Cofactor）特征向量。算法取具有最大DC特征向量的布尔函数作为NPN等价类的正规式。通过变量DC特征值的比较对变量排序，快速计算布尔函数的正规式，最终实现快速的布尔函数NPN等价匹配。

目录

第一个书签之前

摘要

Abstract

第一章 绪论

1.1 问题定义及其研究意义

1.2 国内外研究现状

1.2.1 布尔函数NPN等价分类研究现状

1.2.2 布尔函数NPN等价匹配研究现状

1.3 本文的研究内容及创新点

1.4 论文结构安排

第二章 布尔函数NPN等价分类及等价匹配的基础知识

2.1.1 置换群

2.1.2 等价关系与等价类

2.1.3 Burnside引理介绍

2.1.4 Pólya定理

2.2 布尔函数的表示形式

2.3 布尔函数NPN等价介绍

2.3.1 非门输入

2.3.2 置换输入

2.3.3 NP变换

2.3.4 布尔函数NPN等价

2.4 本章小结

第三章 基于群代数的布尔函数NPN等价分类研究

3.1 置换映射

3.2 非映射

3.3 布尔函数NPN等价分类

3.4 布尔函数NPN等价分类结果

3.5 本章小结

第四章 基于结构化特征的布尔函数NPN等价匹配算法

4.1 基本概念与问题陈述

4.1.1 基本概念

4.1.2 变量映射

4.1.3 变量对称

4.2 基于SS向量的布尔函数NPN等价匹配算法

4.2.1 SS向量更新

4.2.2 搜索变量映射

4.2.3 NP变换探测

4.2.4 匹配算法

4.3 实验结果及分析

4.4 本章小结

第五章 基于结构化布尔差分特征的布尔函数NPN等价匹配算法

5.1 Shannon余子式的运算

5.2 结构化差分特征

5.2.1 独立变量

5.2.2 结构化差分特征向量

5.3 基于SDS的布尔函数NPN等价匹配算法

5.4 实验结果及分析

5.5 本章小结

第六章 一种基于正规式的布尔函数NPN等价匹配算法

6.1 特征与特征向量

6.2 基于特征向量的正规式

6.2.1 DC特征

6.2.2 DC特征的排序

6.2.3 DC特征向量

6.3.1 正规式介绍

6.3.2 本文提出的正规式

6.3.3 正规式的计算

6.3.4 候选正规变换的搜索

6.4 实验结果及分析

6.5 本章小结

第七章 总结与展望

7.1 论文的主要工作

7.2 后续工作展望

致 谢

参考文献

攻读博士学位期间取得的研究成果