Research Journal of Applied Sciences, Engineering and Technology 4(22): 4561-4565, 2012 ISSN: 2040-7467 © Maxwell Scientific Organization, 2012 Submitted: December 30, 2011 Accepted: March 10, 2012 Published: November 15, 2012
Design of the Efficient Nanometric Reversible Subtractor Circuit 1
Mozhgan Shiri and 2Majid Haghparast Department of Computer Engineering, Arak Branch, Islamic Azad University, Arak, Iran 2 Department of Computer Engineering, Shahre-Rey Branch, Islamic Azad University, Tehran, Iran
Abstract: Reversible logic has comprehensive applications in communications, quantum computing, low power VLSI design, computer graphics, cryptography, nanotechnology, and optical computing. It has received significant attention in low power dissipating circuit design in the past few years. While several researchers have inspected the design of reversible logic units, there is not much reported works on reversible subtractors. In this paper we proposed the quantum equivalent circuit for SRK gate and we have computed the quantum cost of SRK gate. We also showed that how SRK gate can work singly as a half-subtractor circuit. It is being tried to design the circuit optimal in terms of number of reversible gates, number of garbage outputs, number of constant inputs, and quantum cost with compared to the existing circuits. At last we proposed an implementation of the new full-subtractor circuit based on SRK gate. All the designs have nanometric scales. Keywords: Nanometric circuits, nanotechnology, quantum computing, reversible logic, subtractor INTRODUCTION In VLSI circuit design, power dissipation is one of the most prominent factors. Researchers like Rolf Landauer have shown that for irreversible logic computation each bit of information lost, generates KTLn2 joules of heat energy, where k = 1.3806505×10-23 m2/kg2.ka (Joule/Kelvin) is Boltzmann’s constant and T the absolute temperature at which computation is performed. This is Landauer’s principal. In 1973 Bennett showed that KTLn2 joules energy can save only if the gating network consists of reversible gates. Thus, in the future reversibility will moving towards low power dissipating circuit design (Haghparast and Sheikh, 2011; Saiful, 2010; Thapliyal and Gupta, 2006). Conventional logic is not reversible. All gates in a reversible logic circuit must be reversible (Haghparast and Navi, 2007). A gate is reversible if and only if there is a distinct output for each input assignment. That is, there is a one-to-one mapping between input and output vectors. Thus, in reversible logic circuit the number of input lines must be equal to the number of output lines (Hasan et al., 2004; Thapliyal et al., 2009; Thapliyal and Srinivas, 2006). While constructing reversible circuits with the reversible gates, some limitations must be strictly maintained (Haghparast and Navi, 2008): C C
Fan-out is not allowed. Loops (feed backs) are not allowed.
Many of the Boolean functions are not reversible. In front of realizing these functions, we need to convert those irreversible functions in to reversible ones (Saiful, 2010; Babu and Chowdhury, 2005). Synthesis of quantum circuits is significantly more complicated than irreversible logic circuits (Haghparast et al., 2009). METHODOLOGY Basic definitions: Consider a function f, we say f is reversible if and only if there exists a function g such that x = g (f (x)) for all x in the domain of f. The function g (as described above) is usually displayed as f (Babu et al., 2006). Minimization of the number of reversible gates, quantum cost, garbage outputs, and constant inputs is the center of research in reversible logic synthesis. Garbage outputs: The outputs that are not used for additional computations are called garbage outputs (Haghparast and Navi, 2007). Clearly we can say an unexploited output from a gate is garbage (Hasan et al., 2004; Kerntopf, 2002). Though, every synthesis method is trying to produce less number of garbage outputs but sometimes garbage outputs are not avoidable (Babu and Chowdhury, 2005). Quantum cost: Quantum cost relates to the cost of the circuit in terms of the cost of the original gates. It is calculated knowing the number of primitive reversible logic gates (1×1 or 2×2) required to perform the circuit (Rangaraju et al., 2010; Kerishnaveni and Geetha, 2011).
Corresponding Author: Mozhgan Shiri, Department of Computer Engineering, Arak Branch, Islamic Azad University, Arak, Iran
Res. J. Appl. Sci. Eng. Technol., 4(22):4561-4565, 2012 Constant inputs: The input that is added to a n×k function to make it reversible is called constant inputs (Rangaraju et al., 2010; Kerishnaveni and Geetha, 2011). These factors have to be reduced while designing a reversible circuit (Rangaraju et al., 2010; Kerishnaveni and Geetha, 2011). Reversible logic gates: A set of reversible logic gates is needed to synthesis reversible circuits. Several reversible gates have been proposed, the most important reversible logic gates are followed:
Fig. 1: NOT gate
Fig. 2: Feynman
NOT gate: There is only one 1×1 gate in reversible logic, which is inverter. This gate is very important because it produces no garbage outputs and has zero quantum cost (Hasan et al., 2003). The Not Gate is shown in Fig. 1. Fig. 3: Toffoli gate
Feynman gate (FG): One of the most consequential reversible logic gates is the Feynman Gate, also is called as Controlled NOT gate (CNOT). This gate is a 2×2 reversible logic gate and can be represented as Iv = (A, B), Ov = (P = A, Q = ArB): where, Iv and Ov are input and output vectors. A 2×2 Feynman gate is shown in Fig. 2. Also, ‘A’ input is named as control bit and ‘B’ input is named as data bit. Its quantum cost is 1 (Haghparast and Navi, 2007; Parhami, 2006). Toffoli gate (TG): There exist 8! , 3×3 Reversible logic gates. Toffoli gate is one of the well-known universal 3×3 reversible logic gates, also called 3×3 Feynman gate. It is a two-through gate, i.e. two of its inputs are also outputs. This gate is shown in Fig. 3. The quantum cost of Toffoli gate is 5 (Hasan et al., 2003; Chung and Wang, 2007). Peres gate (PG): Peres gate is a 3 inputs 3 outputs reversible gate. It can be shown as:
Fig. 4: Peres gate
Fig. 5: Fredkin gate
Fig. 6: New gate
Iv = (A, B, C), Ov = (P = A, Q = Ar B, R = ABrC) where, Iv and Ov are input and output vectors, respectively. Figure 4 shows the Peres gate. Its quantum cost is 4. In the existing literature, in 3×3 reversible gates, Peres gate has the minimum quantum cost (Thapliyal and Ranganathan, 2009). Fredkin gate (FRG): Fredkin gate also known as controlled permutation gate, is a 3×3 reversible logic gate. It can be described as: Iv = (A, B, C), Ov = (P = A, Q = ÁBrAC, R = ÁCrAB) where, Iv and Ov are input and output vectors respectively. It is shown in Fig. 5. The quantum cost of this gate is 5 (Haghparast et al., 2009; Sastry et al., 2006).
Fig. 7: SRK
New gate (NG): New gate which is shown in Fig. 6 is a 3×3 reversible gate that it can generate all the basic gates. It can be described as: Iv = (A, B, C), Ov = (P = A, Q = ABrC, R = Á‚rB') where, Iv and Ov are input and output vectors respectively. The quantum cost of this gate is 7 (Haghparast and Navi, 2008). SRK gate: SRK gate as a 3×3 reversible gate is shown in Fig. 7. Its functionality is represented as:
Res. J. Appl. Sci. Eng. Technol., 4(22):4561-4565, 2012
Fig. 8: BVF
Fig. 9: Quantum implementation of SRK gate
Iv = (A, B, C), Ov = (P = A, Q = ArBrC, R = ÁCrAB) where, Iv and Ov are input and output vectors respectively. This gate can work as a reversible 2:1 Multiplexer. When input A is ‘0’ information on input line C is chosen and put on output line R. When input A is ‘1’ information on input line B is chosen and put on output line R. Thus, input line A plays as a select line and input lines C and B play as data input lines (Kerishnaveni and Geetha, 2011). BVF gate: BVF as a 4×4reversible gate is shown in Fig. 8. It can be represented as: Iv = (A, B, C, D), Ov = (P = A, Q = ArB, R = C, S = C rD)
where, Iv and Ov are input and output vectors respectively. Its quantum cost is 2 (Kerishnaveni and Geetha, 2011). RESULTS Implementation of srk gate: In this section, we propose the implementation of SRK gate for the first time. We show that the quantum cost of SRK is only 5. Our suggested implementation of SRK is shown in Fig. 9. In this figure we see that the quantum cost of SRK is equal to 5. Truth table of SRK Gate is shown is Table 1. New reversible subtractor circuits: Before that study about the proposed reversible subtractor circuits, consider the logical equations for each output of a subtractor circuit: For a Half-Subtractor circuit: Diff = ArB, Borr = ÁB And for a Full-Subtractor circuit: Diff = ArBrC, Borr = ÁBrÁCrBC
Table 1: Truth table of SRK gate A B C 0 0 0 0 0 1 0 1 0 0 1 1 1 0 0 1 0 1 1 1 0 1 1 1
P 0 0 0 0 1 1 1 1
Table 2: Truth table of half-subtractor A B 0 0 0 1 1 0 1 1
Diff 0 1 1 0
Table 3: Truth table of full-subtractor A B C 0 0 0 0 0 1 0 1 0 0 1 1 1 0 0 1 0 1 1 1 0 1 1 1
Q 0 1 1 0 1 0 0 1
R 0 1 0 1 0 0 1 1
Borr 0 1 0 0
Diff 0 1 1 0 1 0 0 1
Borr 0 1 1 1 0 0 0 1
Table 4: A comparison of different reversible half-subtractor circuits Number of Number of Quantum reversible gates garbage outputs cost Existing circuit 2 3 6 Existing circuit 1 1 6 Existing circuit 2 1 5 Proposed circuit 1 1 5 Table 5: A comparison of different reversible full- subtractor circuits Number of Number of Quantum used gates garbage outputs cost Existing circuit 5 9 17 Existing circuit 2 2 12 Proposed design 3 2 8
Fig. 10: Proposed reversible half-subtractor circuit based on SRK gate
The corresponding truth table of the half-subtractor and full-subtractor are shown in Table 2 and 3, respectively. New reversible half-subtractor circuit: In Fig. 10 a novel design of half-subtractor using only one SRK gate is shown. As you see, if input vector is (A, 0, B) then the output vector will be (A, Diff, Borr). Constructing the above circuit requires one gate and it generates only one garbage output. According to the previous section, the
Res. J. Appl. Sci. Eng. Technol., 4(22):4561-4565, 2012
Fig. 11: Proposed reversible full-subtractor circuit
quantum cost of SRK is only 5, so the quantum cost of the proposed half-subtractor circuit is only 5. There are already three existing reversible halfsubtractor circuits. But our proposed circuit performs better than those half-subtractor circuits in the sense of number of reversible gates, number of garbage outputs, and the quantum cost. Table 4 is comparing the proposed half-subtractor circuit with the other existing circuits. New reversible full-subtractor circuit: A versatile arithmetic building element, the reversible full-subtractor can be built using three reversible gates of SRK, BVF, and FG. Implementation of this circuit is presented in Fig. 11. Whereas the quantum cost of SRK is 5 and the quantum costs of BVF and FG are 2 and 1, respectively. The quantum cost of the proposed reversible fullsubtractor circuit will be 5+2+1 = 8.Therefore, the proposed diagram requires 3 gates to design a fullsubtractor with only two garbage outputs and quantum cost of 8. A comparison between the proposed design and existing approaches in literature are shown in Table 5. Thus, the proposed approach achieves the improvement in terms of number of reversible gates, garbage outputs, and quantum cost compared to existing circuits. CONCLUSION In this research, we implemented the quantum representation of the SRK gate for the first time and we utilized it in constructing a new reversible half-subtractor circuit. We showed that the proposed reversible circuit is better than the existing circuits in literature. Furthermore, we synthesized a novel reversible full-subtractor circuit. This proposed work can be used for designing large reversible systems, which is the necessary requirement of nanotechnology based systems and quantum computers. All the scales are in the nanometric area. REFERENCES Babu, H.M.H. and A.R. Chowdhury, 2005. Design of a reversible binary coded decimal adder by using reversible 4-bit parallel adder. 18th International Conference on VLSI Design, Dhaka Univ., Bangladesh, pp: 255-260.
Chung, M.L. and C.Y. Wang, 2007. Synthesis of reversible sequential elements. Proceedings of the 2007 Asia and South Pacific Design Automation Conference, ASP-DAC '07, IEEE Computer Society Washington, DC, USA, pp: 420-425. Haghparast, M. and K. Navi, 2007. A novel reversible full adder circuit for nanotechnology based systems. J. Appl. Sci., 7(24): 3995-4000. Haghparast, M. and K. Navi, 2008a. Design of a novel fault tolerant reversible full adder for nanotechnology based systems. J. Appl. Sci., 3(1): 114-118. Haghparast, M. and K. Navi, 2008b. A novel fault tolerant reversible gate for nanotechnology based systems. Am. J. Appl. Sci., 5(5): 519-523. Haghparast, M., M. Mohammad, K. Navi and M. Eshghi, 2009. Optimized reversible multiplier circuit. J. Circuits Syst. Comp., 18(2): 311-323. Haghparast, M. and G.H. Sheikh Jabbari, 2011. A new nanometric reversible full subtractor gate. Int. R. Comp. Software, 6(2). Hasan, B., R. Islam, A.R. Chowdhury and M.A. Chowdhury, 2003. Reversible logic synthesis for minimization of full-adder circuit. Proceedings of Euromicro Symposium on Digital System Design, Dhaka Univ., Bangladesh, pp: 50-54. Hasan, B., R. Islam, A. Chowdhury and A.R. Chowdhury, 2004. Synthesis of full-adder circuit using reversible logic. Proceedings of the 17th International Conference on VLSI Design, VLSID '04, IEEE Computer Society Washington, DC, USA, pp: 757. Hung, W., X. Song, G. Yang, J. Yang and M. Perkowski, 2006. Optimal synthesis of multiple output boolean functions using a set of quantum gates by symbolic reachability analysis. IEEE T. Comput. Aid. D., 25(9): 1652-1663. Kerntopf, P., 2002. Synthesis of multipurpose reversible logic gates. Proceedings of Euromicro Symposium on Digital System Design, Warsaw Univ. of Technol., pp: 259-266. Kerishnaveni, D. and M. Geetha Priya, 2011. A novel design of reversible serial and parallel adder/subtractor. Int. J. Eng. Sci. Tech. (IJEST), 3(3): 2280-2288. Parhami, B., 2006. Fault-tolerant reversible circuits. Fortieth Asilomar Conference on Signals, Systems and Computers, ACSSC '06, Santa Barbara, CA, pp: 1726-1729.
Res. J. Appl. Sci. Eng. Technol., 4(22):4561-4565, 2012 Rangaraju, H.G., U. Venugopal, K.N. Muralidhara and K.B. Raja, 2010. Low power reversible parallel binary adder/subtractor. Int. J. VLSI Syst. (VLSICS), 1(3): 23-34. Saiful, I., 2010. A Novel Quantum Cost Efficient Reversible Full Adder Gate in Nanotechnology. Institute of Information Technology, University of Dhaka, Dehaka-1000, Bangladesh. Sastry, H.S.K., S.H. Shroff, S.K. Noor Mohammad and V. Kamakoti, 2006. Efficient building blocks for reversible sequential circuit design. 49th IEEE International Midwest Symposium on Circuits and Systems, MWSCAS '06, India, 1: 437-441. Thapliyal, H. and M.B. Srinivas, 2006. The New BCD Subtractor and its Reversible logic Implementation. In: Jesshope C. and C. Egan (Eds.), ACSAC 2006, LNCS 4186, ©Springer-Verlag Berlin Heidelberg, pp: 466-472.
Thapliyal, H. and S.K. Gupta, 2006. Design of novel reversible carry look-ahead BCD subtractor. 9th International Conference on Information Technology, ICIT '06, pp: 253-258. Thapliyal, H. and N. Ranganathan, 2009. Design of efficient reversible binary subtractors based on a new reversible gate. IEEE Computer Society Annual Symposium on VLSI, pp: 229-234, DOI: 10.1109/ISVLSI.2009.49. Thapliyal, H., H.R. Arabnia and M.B. Srinivas, 2009. Efficient Reversible Logic Design of BCD Subtractors. In: Gavrilova, M.L. and C.J.K. Tan, (Eds.), Trans. on Comput. Sci. III, LNCS 5300, ©Springer-Verlag Berlin Heidelberg, pp: 99-121.