基于分层超立方体的精确ESOP最小化

针对大变量逻辑函数的ESOP最小化求解问题,提出一种面向任意完全规定逻辑函数的精确ESOP最小化方法.该方法引入逻辑函数的n维分层超立方体表示模型,采用立方体几何图形映射Exorlink操作,实现一种立方体EXOR转换图的精确最小化转换;使用立方体集合划分与变量置换完成逻辑函数的分层超立方体结构映射以减少函数覆盖;在此基础上,给出基于分层超立方体的ESOP精确最小化算法.在MCNC基准电路上的实验结果表明,与其他ESOP最小化方法相比,文中方法可在多项式计算时间内实现大变量逻辑函数的ESOP最小化.     

快速启发式ESOP电路面积优化算法

针对积之异或和(ESOP)电路面积优化的时间效率问题,提出一种快速的启发式算法.该算法使用多输出立方体表示乘积项,首先由基于伪Kronecker判决图的方法得到初始ESOP覆盖,然后使用启发式局部极性转换与局部变换交替迭代的方式进行面积优化.为提高算法效率,启发式局部极性转换仅尝试改变立方体中单个变量的极性,并且仅接受对减少电路面积有帮助的极性转换,该转换有助于使优化过程跳出局部极小;局部变换则通过对ESOP覆盖中距离为1或2的立方体进行变形来减少电路面积,该变换有助于算法的收敛.实验结果表明,文中算法能够适用于具有较多输入变量的多输出电路;与MPRM电路相比,ESOP电路能够降低电路面积开销;与其他ESOP电路优化算法相比,该算法能够显著改善面积优化的时间效率.     

二叉决策图在逻辑综合中的应用

二叉决策图(BDDs)是布尔函数的一个表示方法,最近它被广泛应用于逻辑综合、布尔电路的模拟和测试等领域.在这些应用中,有些基本问题需要解决,其中包括电路图到决策图的转换.本文提出一个转换的方法.文中分两步叙述,首先是对无扇出电路的转换,然后是对有扇出电路的转换,最后把两者结合为一个通用算法.     

基于位运算的量子可逆逻辑电路快速综合算法

量子可逆逻辑电路是构建量子计算机的基本单元.本文结合可逆逻辑电路综合的多种算法,根据可逆逻辑电路综合的本质是置换问题,巧妙应用位运算构造高效完备的Hash函数,提出了基于Hash表的新颖高效的量子可逆逻辑电路综合算法,可使用多种量子门,以极高的效率生成最优的量子可逆逻辑电路,从理论上实现制造量子电路的成本最低.按照国际同行认可的3变量可逆函数测试标准,该算法不仅能够生成全部最优电路,而且运行速度远远超过其它算法.实验结果表明,该算法按最小长度标准综合电路的平均速度是目前最好结果的69.8倍.     

类选择排序的可逆逻辑综合算法

可逆逻辑综合是指对给定的可逆函数自动构造对应的可逆逻辑电路.由于搜索空间随电路规模增长成指数增长,现有的可逆逻辑综合算法虽然能够得到近似最优的解,但是都存在计算时间过长的问题.文中提出了一种类似选择排序的可逆逻辑综合算法,其实质为基于变换规则的合成法.它采用一个无向无权图表示所有可以进行变换的路径,在综合的过程中,采用选择排序思想每次从小到大的选择需要交换的输出项,然后从路径选择图中找到最优的路径进行变换,最终使得函数的输出序列有序即完成综合.此外,文中还对得到的量子电路进行了优化.实验表明,相比其它综合算法,该算法不仅总能获得最优解或近似最优解,而且效率高、易于实现.     

二叉决策图在逻辑综合中的应用

二叉决策图（BDDs）是布尔函数的一个表示方法，最近它被广泛于逻辑综合、布尔电路的模拟和测试等领域。在这些应用中，有些基本问题需要解决，其中包括电路图到决策图的转换。本文提出一个转换的方法。文中分两步叙述，首先是对无扇出电路的转换，然后是对有扇出电路的转换，最后把两者结合为一个通用算法。     

基于Hash表的量子可逆逻辑电路综合的快速算法

量子可逆逻辑电路是构建量子计算机的基本单元,通过量子门的级联与组合构成量子计算机,量子可逆逻辑电路的综合就是根据电路功能,以较小的量子代价自动构造量子可逆逻辑电路.结合可逆逻辑电路综合的多种算法,提出了一种新颖高效的量子电路综合算法,巧妙构造最小完备的Hash函数,可使用多种量子门,采用任意量子代价标准,以极高的效率生成最优的量子可逆逻辑电路.为实现量子电路综合的自动化,首次提出了利用量子线的置换自动构造各种量子门库的通用算法.采用国际同行认可的3变量可逆函数测试标准,该算法不仅能够生成全部最优电路.而且运行速度远远超过其他算法·实验结果表明,该算法按最小长度、最小代价标准综合电路的平均速度分别是目前最好结果的49.15倍、365.13倍.     

基于矩阵初等变换的量子可逆逻辑电路双向综合算法

基于矩阵初等变换,提出了量子可逆逻辑电路双向综合算法。该算法依据两数字间的汉明距离,通过交换矩阵行号或矩阵元素对量子可逆逻辑电路的矩阵进行初等行变换。在变换的过程中,利用邻接矩阵的电路转化规则,生成任意给定置换的量子可逆逻辑电路。与其它同类算法相比,由于不需要穷尽搜索,该算法的时空复杂度有大幅降低;又由于采用任意n量子扩展通用Toffoli门,该算法可综合任一置换(奇或偶置换)的量子可逆逻辑电路,并且电路中门的数量有所减少。     

量子可逆逻辑电路综合的快速算法研究

可逆逻辑有许多应用,尤其在量子计算领域,量子可逆逻辑电路是构建量子计算机的基本单元,量子可逆逻辑电路综合就是根据电路功能,以较小的量子代价自动构造量子可逆逻辑电路.文中结合可逆逻辑电路综合的多种算法,提出了一种新颖高效的算法,自动构造正极性Reed-Muller展开式(RM),在生成量子可逆逻辑电路的解空间树上,采用总体层次遍历,局部深度搜索,借鉴模板优化技术,构造限界函数快速剪去无解或非最优解的分枝,优先探测RM中的因子,以极高的效率生成最优电路.以国际公认的3变量可逆函数测试标准,该算法不仅能够生成全部最优电路,而且运行速度远远超过同类算法.     

基于带权有向图的可逆逻辑综合改进算法

为减少可逆逻辑综合中使用的可逆门,通过对基于带权有向图的可逆逻辑综合算法的分析,针对函数转换过程中过渡门数较多及电路优化算法简单的问题,提出了有效的等复杂度基本输出变换的概念,扩充并证明了Toffoli门序列的移动和化简规则,给出了改进的基于带权有向图的可逆逻辑综合算法。实验结果表明,该算法不仅减少了可逆电路构成时所使用的可逆门,而且对构建的可逆电路实现了有效化简,大幅度减少了门数和控制位数,降低了可逆电路代价。