投审稿平台
投稿指南
下载专区
地  址:北京市海淀区中关村科学院
南路6号中国科学院计算所342号 [地图]
《计算机辅助设计与图形学学报》编辑部
邮政编码:100190
电  话:010-62562491
     010-62600342
订阅信息
ISSN   1003-9775
CN    11-2925/TP
邮发代号:82-456
单  价:80.00元
全年订价:960.00元
订阅电话:010-64017032
在线期刊

结合因式分解与布尔表达式图的可逆电路综合方法

卜登立1,2)
1) (广西科技大学电气电子与计算机科学学院 柳州 545006)2) (井冈山大学电子与信息工程学院 吉安 343009)
分类号: TP331.2; TP391.72 DOI: 10.3724/SP.J.1089.2021.18738
出版年,卷(期):页码: 2021 , 33 ( 10 ): 1617-1626 卜登立
摘要: 为降低由布尔表达式图(BED)综合所得可逆电路的成本, 提出一种将因式分解与BED表示模型相结合的可逆电路综合方法. 给定布尔函数的积之异或和(ESOP)覆盖, 首先由ESOP立方体的共享零抑制多输出决策图表示借助代数除法对立方体实施因式分解, 并在此基础上构建BED; 然后将BED结点映射为可逆门级联. 对基准函数的可逆电路综合结果表明, 该方法具有较高的时间效率. 与现有将有向无环图作为函数表示模型的综合方法相比, 该方法在许多情况下能降低综合所得可逆电路的量子成本和量子位数. 从平均角度看, 与结合变量分组和BED表示模型的综合方法相比, 该方法可将量子成本和量子位数分别降低5.01%和5.47%.
关键词: 可逆电路; 积之异或和展开; 因式分解; 共享零抑制多输出决策图; 布尔表达式图
Reversible Circuit Synthesis Method by Combining Factoring and Boolean Expression Diagram
Bu Dengli1,2)
1) (School of Electrical, Electronic and Computer Science, Guangxi University of Science and Technology, Liuzhou 545006)2) (School of Electronics and Information Engineering, Jinggangshan University, Ji’an 343009)
abstract: In order to reduce the cost of the resulting circuits, a reversible circuit synthesis method by combining factoring and Boolean expression diagram (BED) is proposed. For a given cover representing the exclu-sive-sum-of-products (ESOP) expansion of a Boolean function, cubes in the ESOP expansion represented by shared zero-suppressed multiple-output decision diagrams are first factored by leveraging algebraic division, then a BED is built from the factored ESOP cover and a reversible circuit is synthesized from the BED by mapping a BED node to a cascade of reversible gates. The proposed synthesis method is evaluated using benchmark func-tions. Experimental results show that the proposed synthesis method is time efficient. Compared to the existing reversible circuit synthesis methods using a directed acyclic graph as the representation model for Boolean func-tions, the proposed synthesis method can reduce the quantum cost and the number of qubits of the resulting re-versible circuits in many cases. On average, compared to the synthesis method by combining variables grouping and BED, the proposed synthesis method can reduce the quantum cost and the number of qubits by 5.01% and 5.47%, respectively.
keyword: reversible circuits; exclusive-sum-of-products expansion; factoring; shared zero-suppressed multiple-output de-cision diagrams; Boolean expression diagram
 
Copyright © 2004《计算机辅助设计与图形学学报》版权所有
电话:010-62600342 传真:010-62562491
E_mail:jcad@ict.ac.cn