电子学报 ›› 2020, Vol. 48 ›› Issue (3): 494-502.DOI: 10.3969/j.issn.0372-2112.2020.03.011

• 学术论文 • 上一篇    下一篇

基于布尔表达式图的可逆电路综合方法

卜登立, 郭鸣   

  1. 井冈山大学电子与信息工程学院, 江西吉安 343009
  • 收稿日期:2018-10-31 修回日期:2019-11-23 出版日期:2020-03-25
    • 作者简介:
    • 卜登立 男,1975年出生,河北定州人.博士,副教授,中国电子学会高级会员,主要研究领域为电路设计与优化、可逆逻辑综合、量子电路综合、启发式优化算法.E-mail:bodengli@163.com;郭鸣 女,1978年出生,江西吉安人.博士,副教授,主要研究领域为电路设计与优化.E-mail:guoming@jgsu.edu.cn
    • 基金资助:
    • 国家自然科学基金 (No.61961023,No.61640412,No.61762052); 江西省教育厅科技计划项目 (No.GJJ160746); 井冈山大学博士科研启动项目 (No.JZB1803); 流域生态与地理环境监测国家测绘地理信息局重点实验室资助课题 (No.WE2016012); 江西省自然科学基金项目 (No.20171BAB202010)

Reversible Circuit Synthesis Method Based on Boolean Expression Diagram

BU Deng-li, GUO Ming   

  1. School of Electronics and Information Engineering, Jinggangshan University, Ji'an, Jiangxi 343009, China
  • Received:2018-10-31 Revised:2019-11-23 Online:2020-03-25 Published:2020-03-25
    • Supported by:
    • National Natural Science Foundation of China (No.61961023, No.61640412, No.61762052); Science and Technology Project of Education Department of Jiangxi Provicne (No.GJJ160746); Ph.D Research Program of Jinggangshan University (No.JZB1803); Supported by the Key Laboratory of Watershed Ecology and Geoenvironmental Monitoring,  National Administration of Surveying,  Mapping and GeoInformation (No.WE2016012); Natural Science Foundation of Jiangxi Province,  China (No.20171BAB202010)

摘要: 本文基于布尔表达式图(Boolean Expression Diagram,BED)提出一种可逆电路综合方法.该方法使用BED表示函数,采用逐BED结点方式综合可逆电路.在综合一个结点时,通过考虑其子结点函数的值是否还会被后续电路使用,基于由NOT、CNOT以及混合极性Peres门构成的门库构建该结点的局部最优可逆子电路.为进一步改善所得电路的成本,根据函数表达式的乘积项中变量对的共享度对变量进行分组实现BED中变量的排序.使用一组基准函数对所提出方法进行了验证.结果表明所提出方法具有较高时间效率.与现有使用决策图作为函数表示模型的综合方法相比,所提出方法能改善综合所得可逆电路的量子成本,且在许多情况下还能减少量子位数和垃圾线数.

关键词: 可逆电路, 逻辑综合, 布尔表达式图, 变量排序

Abstract: A reversible circuit synthesis method based on BED (Boolean Expression Diagram) is proposed. The proposed method utilizes a BED to represent a Boolean function, and synthesizes a reversible circuit through mapping BED nodes to reversible cascades. Using a gate library consisting of NOT, CNOT and mixed-polarity Peres gates, the proposed method constructs a locally optimal reversible cascade for each BED node by considering whether the values of the child nodes of this node will be used by subsequent reversible cascades. In order to improve the cost of the circuit synthesized from the BED of a function, according to the sharing of pairs of variables among products of the function expression, variable ordering for the BED is achieved by variable grouping. The proposed method is validated using a set of benchmark functions. The results show that the proposed method is time efficient. Compared to the existing reversible circuit synthesis methods using decision diagram as a representation model, the proposed method can improve the quantum cost of the synthesized reversible circuits for almost all of the used benchmark functions, and can also reduce the number of qubits and the number of garbage lines in many cases.

Key words: reversible circuit, logic synthesis, Boolean expression diagram, variable ordering

中图分类号: