Computer Science ›› 2017, Vol. 44 ›› Issue (Z6): 546-550.doi: 10.11896/j.issn.1002-137X.2017.6A.122

Previous Articles     Next Articles

Karnaugh-based Reversible Logic Circuit Synthesis Algorithm for 3-bits

ZHU Wan-ning and LIU Zhi-hao   

  • Online:2017-12-01 Published:2018-12-01

Abstract: This paper presented a new algorithm of reversible logic synthesis based on Karnaugh map.This algorithm can solve reversible logic synthesis with garbage bit very fast.Most of the specific reversible logic gates have some garbage bits.It is very difficult to synthesize the reversible logic circuit with garbage by using the classical algorithms which are true table algorithm,permutation group algorithm and etc.The problem is that it is hardly to get the overall situation which the classical algorithms must need.The algorithm proposed in this paper does not care the overall situation and synthesizes every output variable respectively based on the feature of Karnaugh map.The algorithm of reversible logic synthesis based on Karnaugh map divides all the three-bits-reversible-logic-circuits to five equivalence classes based on contiguity of Karnaugh map.Then the algorithm calculates every equivalence class respectively and synthesizes the reversible logic circuit with garbage bits in constant time.

Key words: Karnaugh map,Reversible logic synthesis,Garbage bit,NCT gate library,EGT

[1] LANDAUER R.Irreversibility and heatgeneration in the computing process[J].IBM Journal of Research and Development,2000,44(1/2):261-269.
[2] BARCNCO A,BENNETT C,et al.Elementary gates for quantum computation[J].Physical Review A,1995,52(5):3457-3467.
[3] LI Z Q,LI W Q,CHEN H W.Algorithm of optimizing quantum reversible logic synthesis[J].Journal of Software,2009,20(9):2332-2343.
[4] LI Z Q,CHEN H W,XU B W,et al.A fast algorithm for synthesis of quantum reversible logic circuits[J].Chinese Journal of Computers,2009,23(7):1291-1303.
[5] 王冬,陈汉武,安博,等.基于矩阵初等变换的四量子比特可逆电路综合算法[J].电子学报,2010,38(11):2561-2565.
[6] 王冬,陈汉武,安博,等.量子可逆电路综合的启发式快速匹配算法[J].东南大学学报(自然科学版),2009,39(5):900-903.
[7] WANG D,CHEN H W,AN B,et al.A Novel RM-Based Algorithm for Reversible Circuits[C]∥LNCS 5821.2009:63-69.
[8] WANG D,CHEN H W,ZHU W N.Bidirectional Matrix-based Algorithm for 4-qubit Reversible Logic Circuits Synthesis[C]∥2010 IEEE Congress on Evolutionary Computation (IEEE CEC 2010).Barcelona,Spain,2010:1325-1329.
[9] 王冬,陈汉武,朱皖宁,等.多值逻辑量子置换门的酉矩阵表示[J].计算机学报,2012,5(3):639-644.
[10] 李志强,陈汉武,徐宝文,等.基于Hash表的量子可逆逻辑电路综合的快速算法[J].计算机研究与发展,2008,45(12):2162-2171.
[11] PERES A.Reversible logic and quantum computers[J].Physical Review A,DEC,1985,32(6):3266-3276.
[12] KHAN M H A.Design of full-adder with reversible gates[C]∥Processings of the 5th International Conference on Computer and Imformation Technology(ICCIT’2002).Dhaka,Bangladesh,2002:515-519.
[13] THAPLIYAL H,SRINIVAS M B.Novel Reversible TSG gate and its application for designing reversible carry look ahead adder and other adder architectures[C]∥Processings of the 10th Asia-Pacific Computer System Architecture Conference,LNCS,3740.Springer-Verlag,Singapore,2005:775-786.
[14] HAGHPARAST M,NAVI K.A Novel Reversible BCD Adder For Nanotechnology Based Systems[J].American Journal of Applied Sciences,2008,5(3):282-288.
[15] HAGHPARAST M,JASSBI S J,NAVI K,et al.Design of aNovel Reversible Multilpier Circuit Using HNG Gate in Nanotechnology[J].World Applied Sciences Journal,2008,3(6):974-978.
[16] ISLAM M S,RAHMAN M M,BEGUM Z,et al.Low Cost Quan-tum Realization of Reversible Multiplier Circuit[J].Information Technology Journal,2009,8(2):208-213.
[17] BANERJEE A,PATHAK A.An analysis of reversible multip-lier circuits[J].arXiv:0907,7,2009:1-10.
[18] CEHNG S T,WANG C Y.Quantum switching and quantummerge sorting [J].IEEE Transactions on Circuits and Systems,2006,53(2):316-325.

No related articles found!
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
No Suggested Reading articles found!