[1]朱皖宁,陈汉武,阮越.基于新型可逆门的可扩展可逆比较器[J].东南大学学报(自然科学版),2014,44(1):39-44.[doi:10.3969/j.issn.1001-0505.2014.01.008]
 Zhu Wanning,Chen Hanwu,Ruan Yue.Extensible reversible comparator based on novel reversible gate[J].Journal of Southeast University (Natural Science Edition),2014,44(1):39-44.[doi:10.3969/j.issn.1001-0505.2014.01.008]
点击复制

基于新型可逆门的可扩展可逆比较器()
分享到:

《东南大学学报(自然科学版)》[ISSN:1001-0505/CN:32-1178/N]

卷:
44
期数:
2014年第1期
页码:
39-44
栏目:
计算机科学与工程
出版日期:
2014-01-18

文章信息/Info

Title:
Extensible reversible comparator based on novel reversible gate
作者:
朱皖宁1陈汉武12阮越1
1东南大学计算机科学与工程学院, 南京 210096; 2东南大学计算机网络和信息集成教育部重点实验室, 南京 210096
Author(s):
Zhu Wanning1 Chen Hanwu12 Ruan Yue1
1School of Computer Science and Engineering, Southeast University, Nanjing 210096, China
2Key Laboratory of Computer Network and Information Integration of Ministry of Education, Southeast University, Nanjing 210096, China
关键词:
可逆比较器 新型可逆门 递归
Keywords:
reversible comparator novel reversible gate recursion
分类号:
TP387
DOI:
10.3969/j.issn.1001-0505.2014.01.008
摘要:
针对当前可逆比较器设计方案缺乏可扩展性的问题,提出了基于新型可逆门的具有可扩展性的可逆比较器可逆逻辑电路设计方案.该方案根据二进制数比较的特点采用递归思想将电路分解为2种新型可逆门,对分解出的每一个可逆门进行可逆逻辑综合,再将这2种可逆门级联成可逆比较器.给出了设计方案中每一步的逻辑演算,利用编码的思想进行带无关项的可逆逻辑综合,最终给出了具体的可逆比较器的综合方案.同时,以可逆比较器作为元器件给出了败者树排序电路,将排序的时间复杂度降低到Θ(n).
Abstract:
The design proposal for an extensible reversible comparator based on a novel reversible gate is presented to solve the problem that the previous scheme is not extensible. Using the method of recursion, the circuit is decomposed to two kinds of novel reversible gates according to the features of the binary number comparison. And each reversible gate is synthesized with reversible logic. The reversible comparator is realized by cascading these reversible gates. The logical expression of every step is given; the theory of encoding is used to solve logic synthesis with “do not care” set; the detailed scheme for synthesizing reversible comparator is provided. Tournament sort circuit based on reversible comparator is presented, and the asymptotic time complexity of the circuit is decreased to Θ(n).

参考文献/References:

[1] Landauer R. Irreversibility and heatgeneration in the computing process[J]. IBM Journal of Research and Development, 1961, 5(3): 183-191.
[2] Barenco A, Bennett C H, Cleve R, et al. Elementary gates for quantum computation [J]. Physical Review A, 1995, 52(5): 3457-3467.
[3] Song X Y, Yang G W, Perkowski M, et al. Algebraic characterization of reversible gates [J]. Theory of Computing System, 2006, 39(2): 311-319.
[4] Peres A. Reversible logic and quantum computers[J]. Physical Review A, 1985, 32(6): 3266-3276.
[5] Khan M M H A. Design of full-adder with reversible gates[C]//Proceedings of the 5th International Conference on Computer and Information Technology. Dhaka, Bangladesh, 2002: 515-519.
[6] Thapliyal H, Srinivas M B. Novel reversible TSG gate and its application for designing reversible carry look ahead adder and other adder architectures[C]//Proceedings of the 10th Asia-Pacific Computer System Architecture Conference. Singapore, 2005: 775-786.
[7] Haghparast M, Navi K. A novel reversible BCD adder for nanotechnology based systems[J]. American Journal of Applied Sciences, 2008, 5(3): 282-288.
[8] Haghparast M, Jassbi S J, Navi K, et al. Design of a novel reversible multilplier circuit using HNG gate in nanotechnology[J]. World Applied Sciences Journal, 2008, 3(6): 974-978.
[9] Islam M S, Rahman M M, Begum Z, et al. Low cost quantum realization of reversible multiplier circuit[J]. Information Technology Journal, 2009, 8(2): 208-213.
[10] Banerjee A, Pathak A. An analysis of reversible multiplier circuits[EB/OL].(2009-07-20)[2012-05-14]. http://arxiv.org/abs/0907.3357.
[11] Cheng S T, Wang C Y. Quantum switching and quantum merge sorting [J]. IEEE Transactions on Circuits and Systems, 2006, 53(2): 316-325.
[12] 李明翠. 基于Toffoli门的可逆数值比较器的设计与优化[J].华东交通大学学报,2011, 28(6):91-95.
  Li Mingcui. Design and optimization of reversible numerical comparator based on Toffoli gate[J]. Journal of East China Jiaotong University, 2011, 28(6): 91-95.(in Chinese)
[13] 朱皖宁,陈汉武,刘志昊,等.基于Ring-Sum-Expansion范式的Reed-Muller展开式算法[J].东南大学学报:自然科学版, 2010, 40(5):932-936.
  Zhu Wanning, Chen Hanwu, Liu Zhihao, et al. Reed-Muller expansion algorithm based on Ring-Sum-Expansion[J]. Journal of Southeast University: Natural Science Edition, 2010, 40(5): 932-936.(in Chinese)
[14] 王冬,陈汉武,安博,等. 量子可逆电路综合的启发式快速匹配算法[J].东南大学学报:自然科学版, 2009,39(5):900-903.
  Wang Dong, Chen Hanwu, An Bo, et al. Heuristic fast-matching algorithm for synthesis of quantum reversible logic circuits[J]. Journal of Southeast University: Natural Science Edition, 2009, 39(5): 900-903.(in Chinese)
[15] Maslov D, Young C, Miller D M, et al. Quantum circuit simplification using templates[C]//Proceedings of Design, Automation and Test in Europe. Munich, Germany,2005:1208-1213.
[16] Banerjee A, Pathak A. An algorithm for minimization of quantum cost[EB/OL].(2010-04-09)[2012-05-14]. http://arxiv.org/abs/0910.2129.
[17] 殷人昆,陶永雷,谢若阳.数据结构[M]. 北京:清华大学出版社, 1997: 313-316.

备注/Memo

备注/Memo:
收稿日期: 2013-08-26.
作者简介: 朱皖宁(1983—),男,博士生;陈汉武(联系人),男,博士,教授,博士生导师,hanwu_chen@163.com.
基金项目: 国家自然科学基金资助项目(61170321)、高等学校博士学科点专项科研基金资助项目(20110092110024).
引用本文: 朱皖宁,陈汉武,阮越.基于新型可逆门的可扩展可逆比较器[J].东南大学学报:自然科学版,2014,44(1):39-44. [doi:10.3969/j.issn.1001-0505.2014.01.008]
更新日期/Last Update: 2014-01-20