电子学报 ›› 2018, Vol. 46 ›› Issue (8): 1866-1875.DOI: 10.3969/j.issn.0372-2112.2018.08.010

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

基于ESOP最大加权输出相容类的可逆电路综合方法

卜登立   

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

Reversible Circuit Synthesis Method Based on Maximum Weighted Output-Compatibility Class of ESOP

BU Deng-li   

  1. 1. School of Electronics and Information Engineering, Jinggangshan University, Ji'an, Jiangxi 343009, China;
    2. Key Laboratory of Watershed Ecology and Geographical Environment Monitoring, NASG, Ji'an, Jiangxi 343009, China
  • Received:2017-08-07 Revised:2018-03-02 Online:2018-08-25 Published:2018-08-25
    • Supported by:
    • National Natural Science Foundation of China (No.61640412, No.61762052); Science and Technology Project of Education Department of Jiangxi Provicne (No.GJJ160746); Key laboratory of Watershed Ecology and Geographical Environment Monitoring,  NASG (No.WE2016012); Natural Science Foundation of Jiangxi Province,  China (No.20171BAB202010); Ph.D Research Program of Jinggangshan University (No.JZB1803)

摘要: 充分挖掘乘积项在多个函数输出之间的共享因素来降低可逆电路的量子成本是基于积之异或和(Exclusive-Sums-Of-Products,ESOP)的可逆电路综合方法要解决的一个重要问题.提出一种基于最大加权输出相容类的可逆电路综合方法.该方法先借助零抑制多输出决策图对立方体集合进行输出等价类划分,并采用贪心策略计算最大加权输出相容类,然后对最大加权输出相容类进行综合,以使混合极性多控制Toffoli门以及可逆子电路在尽可能多的输出变量线之间共享.通过立方体聚类挖掘等价类中立方体间的结构相似性,并对文字数较多的立方体实施分解,进一步降低可逆电路的量子成本.使用RevLib多输出函数对所提出方法进行了验证,结果表明所提出方法可以很好地挖掘乘积项在多个函数输出之间的共享因素,能够降低由ESOP综合所得可逆电路的量子成本,并且具有较高的时间效率.

关键词: 可逆电路, 逻辑综合, 积之异或和, 输出相容, 零抑制多输出决策图

Abstract: Reducing quantum cost of reversible circuit by exploiting sharing of product terms among multiple function outputs is one crucial problem to be solved for ESOP (Exclusive-Sums-Of-Products) based reversible circuit synthesis.A maximum weighted output-compatibility class based reversible circuit synthesis method is proposed.The proposed method first partitions cubes set into several output-equivalence classes by utilizing zero-suppressed multiple-output decision diagram,and obtains maximum weighted output-compatibility class by using greedy strategy,then synthesizes the maximum weighted output-compatibility class to share mixed-polarity multiple-control Toffoli gates and reversible sub-circuits among as many output variable lines as possible.In order to further reduce quantum cost,the proposed method clusters cubes in equivalence class by exploiting structural similarity among cubes,and decomposes those cubes that have more literals.The proposed method is validated by using several RevLib multi-output functions.Results show that the proposed method can fine exploit sharing of product terms among multiple function outputs,can reduce quantum cost of reversible circuit synthesized from ESOP,and has high time efficiency.

Key words: reversible circuit, logic synthesis, exclusive sums of products, output-compatibility, zero-suppressed multiple-output decision diagram

中图分类号: