一种可逆有限状态机的电路设计

doi:10.3969/j.issn.0372-2112.2020.11.019

电子学报 ›› 2020, Vol. 48 ›› Issue (11): 2226-2232.DOI: 10.3969/j.issn.0372-2112.2020.11.019

一种可逆有限状态机的电路设计

吴钰, 张莹, 王伦耀, 储著飞, 夏银水

宁波大学信息科学与工程学院, 浙江宁波 315211

收稿日期:2019-10-10 修回日期:2020-03-28 出版日期:2020-11-25 发布日期:2020-11-25
作者简介:吴钰女,1995年出生于安徽安庆,信息科学与工程学院研究生,研究方向为可逆逻辑综合.E-mail:13566361397@163.com;张莹女,1992年出生于安徽安庆,信息科学与工程学院研究生,研究方向为可逆逻辑综合;王伦耀 男,1972年生于浙江宁波.宁波大学信息科学与工程学院教授.研究方向为低功耗集成设计、集成电路设计自动化等.E-mail:wanglunyao@nbu.edu.cn
基金资助:
国家自然科学基金（No.61471211，No.U1709218，No.61871242）；浙江省自然科学基金（No.LY19F040004）；宁波市自然科学基金（No.2019A610077）

Design of a Reversible Finite State Machine

WU Yu, ZHANG Ying, WANG Lun-yao, CHU Zhu-fei, XIA Yin-shui

Faculty of Electrical Engineering and Computer Science, Ningbo University, Zhejiang, Ningbo 315211, China

Received:2019-10-10 Revised:2020-03-28 Online:2020-11-25 Published:2020-11-25

摘要/Abstract

摘要： 不同以往通过重构电路行为实现可逆有限状态机方法，本文提出了一种可逆有限状态机的电路结构.该电路主要包括次态与输出计算电路以及状态预置与采样锁存电路两部分，且提出的可逆有限状态机电路中不存在独立的可逆触发器，但可以实现可逆JK，D，T等触发器功能.同时，文中也提出了基于该可逆有限状态机电路的可逆时序电路综合方法，并用实例进行了验证.相比于基于行为重构的可逆有限状态机的综合方法，本文提出的综合方法可以避免原始状态机的逆状态机的求解和增加额外的信号位，从而使得综合过程变得更加简单.

关键词: 可逆逻辑, 有限状态机, 时序电路, 逻辑综合

Abstract: Unlike the previous methods of realizing reversible finite state machine(FSM) by reconstructing FSM behavior,a circuit structure for reversible FSM realization is proposed in this paper.The circuit structure mainly includes two parts,one for next state and output calculation,the other for state preset,data sampling and storage.In the proposed reversible FSM,there is no complete reversible flip-flops such as JK,D and T,but their functions can be realized by the proposed reversible FSM.Furthermore,a synthesis method of reversible sequential circuits based on the proposed reversible FSM is presented and verified by an example.Compared with the synthesis methods of reversible finite state machine based on behavior reconstruction,the proposed synthesis method in this paper can avoid the solution of the inverse state machine of the original state machine and adding extra bits,which makes the synthesis process simpler.

Key words: reversible logic, finite state machine, sequential circuits, logic synthesis

中图分类号:

TP331.1

吴钰, 张莹, 王伦耀, 储著飞, 夏银水. 一种可逆有限状态机的电路设计[J]. 电子学报, 2020, 48(11): 2226-2232.

WU Yu, ZHANG Ying, WANG Lun-yao, CHU Zhu-fei, XIA Yin-shui. Design of a Reversible Finite State Machine[J]. Acta Electronica Sinica, 2020, 48(11): 2226-2232.

参考文献

[1] Landauer R.Irreversibility and heat generation in the computing process[J].IBM Journal of Research and Development,1961,5(3):183-191.
[2] Bennett,Charles H.Notes on landauer's principle,reversible computation,and maxwell's demon[J].Studies in History & Philosophy of Modern Physics,2002,34(3):501-510.
[3] 管致锦,秦小麟,陶涛,施佺.可逆逻辑门网络的表示与级联[J].电子学报,2010,38(10):2370-2376. Guan Zhi-jin,Qin Xiao-lin,Tao Tao,Shi Quan.Representation and cascade for reversible gate network[J].Acta Electronica Sinica,2010,38(10):2370-2376.(in Chinese)
[4] Naveen K B,Puneeth G,Sandngaraju M N S.Low power Viterbi decoder design based on reversible logic gates[A].International Conference on Electronics and Communication Systems[C].Coimbatore:IEEE,2017.201-205.
[5] Mondal B,Dey K,Chakraborty S.An efficient reversible cryptographic circuit design[A].International Symposium on Vlsi Design and Test[C].Guwahati:IEEE,2016.1-6.
[6] Govindapriya K,Periyasamy M.Nano design of communication partswith QCA using reversible logic[A].International Conference on Advanced Communication Control and Computing Technologies[C].Ramanathapuram:IEEE,2017.819-823.
[7] Bandyopadhyay C,Parekh S,Rahaman H.Improved circuit synthesis approach for exclusive-sum-of-product-based reversible circuits[J].Iet Computers & Digital Techniques,2018,12(4):167-175.
[8] Molahosseini A S,Asadpoor A,Zarandi A A E,et al.Towards efficient modular adders based on reversible circuits[A].International Symposium on Circuits and Systems[C].Florence:IEEE,2018.1-5.
[9] Kole D K,Rahaman H,Das D K,et al.A novel reversible synthesis of array multiplier[A].International Symposium on Devices,Circuits and Systems[C].Howrah:IEEE,2018.1-4.
[10] Wille R,Soeken M,Miller D M,et al.Trading off circuit lines and gate costs in the synthesis of reversible logic[J].Integration the Vlsi Journal,2014,47(2):284-294.
[11] Khan M H A.Design of reversible synchronous sequential circuits using pseudo Reed-Muller expressions[J].IEEE Transactions on Very Large Scale Integration System,2014,22(11):2278-2286.
[12] Kulkarni A,Kaushik B K,Zilic Z.Implementation and analysis of spin-torque-based reversible D-latch[A].Canadian Conference on Electrical & Computer Engineering[C].Quebec City:IEEE,2018.1-4.
[13] Goswami M,Narzary A,Raj G,et al.Design of reversible bidirectional logarithmic barrel shifter[A].International Symposium on Embedded Computing and System Design[C].Durgapur:IEEE,2017.1-4.
[14] Ghosh S,Sen B,Das R.Bijective mapping of arbitrary finite state machine[A].International Conference on High Performance Computing and Applications[C].Bhubaneswar:IEEE,2014.1-5.
[15] Gupta S,Pareek V,Jain S C,et al.Realization of sequential reversible circuit from finite state machine[A].International Computer Science and Engineering Conference[C].Khon Kaen:IEEE,2014.458-463.
[16] Vasudevan D P,Goudarzi M,Popovici E M,et al.A reversible MIPS multi-cycle control FSM design[A].Asia Symposium on Quality Electronic Design[C].Kuala Lumpur:IEEE,2009.336-342.
[17] Goudarzi M,Chen J,Vasudevan D P,et al.Reversing deterministic finite state machines[A].Irish Signals and Systems Conference[C].Dublin:IET,2009.1-6.
[18] Sentovich E.M,et al.SIS:A system for sequential circuit synthesis[R].UCB/ERL M92/41 Electronics Research Lab.University of California:Berkeley,CA 94720,1992.
[19] Upadhyay K K,Srivastava S,Arun V et al.Design and performance analysis of MZI based 2×2 reversible XOR logic gate[A].Recent Advances on Engineering,Technology and Computational Sciences[C].Allahabad:IEEE,2018.1-5.
[20] Meuli G,Soeken M,Roetteler M,et al.A best-fit mapping algorithm to facilitate ESOP-decomposition in Clifford+T quantum network synthesis[A].Design Automation Conference[C].Jeju:IEEE,2018.664-669.
[21] 瞿婷,王伦耀,罗文强,夏银水.大函数ISFPRM面积优化方法[J].电子学报,2018,46(05):1101-1106. QU Ting,WANG Lun-yao,LUO Wen-qiang,XIA Yin-shui.A novel method for large ISPFRM function optimization[J].Acta Electronica Sinica,2018,46(05):1101-1106.(in Chinese)
[22] Yang S.Logic synthesis and optimization benchmarks user guide:version 3.0[R].Carolina:Microelectronics Center of North Carolina (MCNC),1991.
[23] Maslov D,Young C,Miller D M,et al.Quantum circuit simplification using templates[A].Design.Automation and Test in Europe Conference and Exposition[C].Munich,Germany:IEEE Computer Society,2005.

一种可逆有限状态机的电路设计

Design of a Reversible Finite State Machine

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

[1]	卜登立, 郭鸣. 基于布尔表达式图的可逆电路综合方法[J]. 电子学报, 2020, 48(3): 494-502.
[2]	常丽, 朱宇祥, 蒋辉. 量子全加器设计[J]. 电子学报, 2019, 47(9): 1863-1867.
[3]	卜登立. 基于ESOP最大加权输出相容类的可逆电路综合方法[J]. 电子学报, 2018, 46(8): 1866-1875.
[4]	姜淑娟, 鞠小林, 王兴亚, 李海洋, 张艳梅, 刘颖祺. 基于UIO序列的类重要性度量[J]. 电子学报, 2015, 43(10): 2062-2068.
[5]	卜登立, 江建慧. 基于对偶逻辑的混合极性RM电路极性转换和优化方法[J]. 电子学报, 2015, 43(1): 79-85.
[6]	王友仁, 沈先坤, 周影辉. 基于KFDD的可逆逻辑电路综合设计方法[J]. 电子学报, 2014, 42(5): 1025-1029.
[7]	徐明强, 管致锦, 张海豹. 基于最小混乱度的三值可逆逻辑综合算法[J]. 电子学报, 2013, 41(7): 1352-1357.
[8]	李志强, 陈汉武, 刘文杰, 薛希玲, 肖芳英. 基于新型量子逻辑门库的最优NCV三量子电路快速综合算法[J]. 电子学报, 2013, 41(4): 690-697.
[9]	朱皖宁, 陈汉武, 李志钢, 阮越, 王冬, 周刚. 基于NCP门库的一维量子行走可逆逻辑电路[J]. 电子学报, 2013, 41(1): 91-97.
[10]	欧阳城添, 江建慧. 基于概率转移矩阵的时序电路可靠度估计方法[J]. 电子学报, 2013, 41(1): 171-177.
[11]	杨忠明;陈汉武;王冬;. 基于二分法量子可逆逻辑电路综合[J]. 电子学报, 2012, 40(5): 1045-1049.
[12]	王友仁;黄媛媛;冯冉;张砦. 基于矩阵编码的量子可逆逻辑电路进化设计方法[J]. 电子学报, 2011, 39(11): 2576-2582.
[13]	王冬;陈汉武;安博;杨忠明. 基于矩阵初等变换的四量子比特可逆电路综合算法[J]. 电子学报, 2010, 38(11): 2561-2565.
[14]	管致锦;秦小麟;陶涛;施 . 可逆逻辑门网络的表示与级联[J]. 电子学报, 2010, 38(10): 2370-2376.
[15]	胡靖;马光胜;李东海;冯刚. 考虑串扰因素的可逆电路的符号综合方法[J]. 电子学报, 2008, 36(5): 1029-1034.