Abstract
In recent years, reversible logic has attracted high importance because of its in-cognitive property of reduction in energy dissipation which is the main requirement in low-power digital circuits. Reversible logic is one of emerging fields of research, which is used in various fields such as low-power CMOS, DNA computing, quantum computing, fault tolerance and nanotechnology. A circuit is reversible if it has the same number of inputs and outputs, and there is a one-to-one correspondence between them. A reversible circuit is parity-preserving if the EXOR of the inputs is equal to the EXOR of the outputs. Flip-flops are considered as one of the most important digital designs that are widely used as building blocks in the design of sequential circuits. In this paper, two new 4 × 4 parity-preserving reversible blocks are first proposed, called PNM1 and PNM2, respectively. Quantum syntheses of the proposed blocks are carried out using the Miller et al. method. In the following, effective designs of parity-preserving reversible D, T and J-K flip-flops along with their master–slave versions are introduced using the proposed parity-preserving reversible blocks and DFG gates. Finally, a 4-bit asynchronous up-counter is designed using the proposed parity-preserving reversible D flip-flop and FRG gate. The results of the comparisons show that although the proposed structures are close to previous designs in terms of gate count, constant input and garbage output criteria, they are superior in terms of quantum cost.
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.Avoid common mistakes on your manuscript.
1 Introduction
Landauer proved that the thermal energy generated by the loss of one bit of information during processing is equal to kTLn2 Joules of heat energy, where k is the Boltzmann’s constant and T is the absolute temperature of the environment [1]. Bennett showed that in order to avoid energy waste in computational circuits, the processes should be reversible; that is, if reversible logic gates are used, there is no power consumption, and no energy is lost [2]. A block is reversible if the number of inputs with the number of outputs is equal, and there is a one-to-one correspondence between them [3]. In other words, the input vector can be retrieved through the output vector. In reversible logic, feedback loop and fan-out (fan-out = 1) are not allowed [3]. Of course, Toffoli showed that feedback is possible in reversible circuits [4]. Accordingly, a sequential circuit is reversible if its combinational part is reversible. Fredkin used this concept to propose the first reversible sequential circuit design, which had a feedback loop from the output. Reversible logic is widely applied in a wide variety of research fields such as low-power CMOS [5], optical technology [6], quantum computing [7], DNA computing [8] and nanotechnology [9]. In order to properly synthesize the reversible circuits, it is necessary that criteria such as, gate count (GC), number of constant inputs (CI), garbage outputs (GO), and quantum cost (QC) are optimized, which are defined as follows [10,11,12,13,14,15,16,17,18,19]:
Gate count (GC) This criterion refers to the number of gates used in reversible circuit design.
Constant inputs (CI) This criterion refers to the number of inputs that are set to a constant value (0 or 1) for the synthesis of the logical function.
Garbage outputs (GO) This indicates the number of unwanted outputs which are added to make a function reversible.
Quantum cost (QC) This refers to the cost of reversible circuits based on the number of elementary quantum gates. The QC of reversible 1 × 1 gate (such as the NOT gate) and 2 × 2 gates (such as the controlled-V, controlled-\(V^{ + }\), CNOT and integrated 2-qubit gates) is considered to be equal to one.
Logical calculation (LC) A number of gates such as EXOR, AND and NOT are used to construct a logical function.
One of the most issues in the reversible circuits is the fault-detection problem. The parity check is considered as one of the straightforward and low-cost approaches to identify faults in the communication and digital systems. Hence, the parity-preserving can be used well in the reversible circuits with an effective cost. A reversible block is called parity-preserving if the EXOR of the inputs is equal to EXOR of the outputs [20].
So far, several reversible computational circuits with parity-preserving capability are introduced, such as adder [21], multiplier [22, 23], divider [24], ALU [25] and flip-flops [26].
Among these, flip-flops are of particular importance since they are frequently used as the building blocks in the sequential circuits.
The main scientific contributions of this paper are summed up as follows:
Proposing two new parity-preserving reversible blocks with the low quantum cost.
Quantum synthesis of the proposed blocks is performed using the Miller et al. method.
Introducing effective designs of D, T and J-K flip-flops and their master–slave versions using the proposed parity-preserving reversible blocks.
The comparison results indicate that the proposed circuits are better than previous related works.
The rest of the paper is as follows: In Sect. 2, the basis of the reversible logic and Miller et al. synthesis algorithm are described. In Sect. 3, the related works are reviewed. In Sect. 4, the proposed new parity-preserving reversible blocks are introduced. In Sect. 5, the simulation results and comparisons are presented. Finally, Sect. 6 concludes the paper.
2 An overview of reversible logic
In this section, we introduce some basic concepts in reversible logic, including preliminaries, some parity-preserving reversible gates and Miller et al. synthesis algorithm.
A gate/block is called reversible if there is a one-to-one correspondence between the inputs and the outputs. The function F, with the input vector Iv = (I1, I2, …, In) and the output vector Ov = (O1, O2, …, On), is reversible if and only if there is a one-to-one correspondence between the input and output vectors [27].
A gate/block is parity-preserving if the parity of the inputs is equal to the parity of the outputs. Therefore, if a fault takes place on one of the outputs, it can be detected. Furthermore, a reversible circuit is fault-tolerant if it is only made from the parity-preserving reversible gates/blocks [20].
2.1 Basic reversible gates
NOT gate
A NOT gate is a 1 × 1 quantum gate with QC equal to 1, as shown in Fig. 1 [28].
Controlled-NOT gate (CNOT)
The CNOT gate, which is also known as the Feynman gate (FG), is a 2 × 2 reversible gate that has the inputs control (A) and target (B) and the produces the outputs P = A and Q = A ⊕ B. The CNOT quantum representation is shown in Fig. 2. As can be seen, if the control input is equal to 1 (A = 1), the output Q will be the inverse of the target input (\(\bar{B}\)); otherwise, the target input (B) is transferred unchanged to the output Q [29].
Controlled-V and controlled- \(V^{ + }\) gates
Controlled-V and controlled-\(V^{ + }\) gates are known as primary 2 × 2 quantum gates and are shown in Fig. 3a and b, respectively [10, 28].
V and \(V^{ + }\) matrices are provided in Eqs. (1) and (2), respectively [10, 28, 30,31,32]:
Also, V and \(V^{ + }\) matrices have the following properties [10, 28]:
As seen in Fig. 3, if the control input A is equal to 1 (A = 1), controlled-V and controlled-\(V^{ + }\) gates result in V(B) and \(V^{ + }\)(B) outputs, respectively. Otherwise, target input B will be transferred unchanged to the output. Their QC is 1.
The quantum realization of the three integrated 2-qubit gates is shown in Fig. 4. It should be mentioned that each dotted rectangle in Fig. 4 is equivalent to a 2 × 2 gate, and its QC is 1 [11, 12, 32, 33].
A common method to simplifying of quantum circuits is template matching. Two practical templates are illustrated in Fig. 5 showing possible reductions for several cascades [34, 35].
It should be noted that the quantum cost of the circuits shown in Fig. 6 is equal to zero [35,36,37,38,39].
2.2 Basic parity-preserving reversible gates
So far, various parity-preserving reversible gates/blocks have been introduced [14, 26, 40,41,42,43,44,45,46]. In the following, we introduce the three most important gates, including double Feynman gate (DFG), Fredkin gate (FRG) and new fault tolerance gate (NFT).
Double Feynman gate (DFG) Circuit representation and quantum realization of the 3 × 3 parity-preserving reversible DFG gate are illustrated in Fig. 7 [20]. Its truth table is also provided in Table 1 so that its output equations are P = A, Q = A ⊕ B and R = A ⊕ C. Moreover, its quantum cost is 2 and the logical calculation is 2α.
Fredkin gate (FRG) Circuit representation and quantum realization of the 3 × 3 parity-preserving reversible FRG gate are shown in Fig. 8 [47]. Its truth table is also given in Table 2 so that its output equations are P = A, Q = A′B ⊕ AC and R = A′C ⊕ AB. In addition, its quantum cost is 5 and logical calculation is 2α + 4β + 1δ.
New fault tolerance gate (NFT) Circuit representation and quantum realization of the 3 × 3 parity-preserving reversible NFT gate are shown in Fig. 9 [48]. Its truth table is also given in Table 3 so that its output equations are P = A ⊕ B, Q = B′C ⊕ AC′ and R = BC ⊕ AC′. Moreover, its quantum cost is 5 and the logical calculation is 3α + 3β + 2δ.
2.3 Miller synthesis algorithm
Miller et al. synthesis algorithm is a transformation-based approach that is able to synthesis a reversible circuit in terms of n × n Toffoli gates. In this method, a circuit is built by a single pass through the specification with minimal look ahead and no back-tracking [34]. Basic Miller et al. synthesis algorithm is given as follows [34].
Consider, an m-input, m-output, totally specified Boolean function f (X), X = {x1, x2… xm} is reversible if it maps each input assignment to a unique output assignment. In the other words, a reversible function specified as a mapping over {0, 1… 2m − 1}.
To start, a basic naive and greedy scheme is utilized that specifies Toffoli gates only on the output side of the specification.
2.4 Basic algorithm
Step 1 If f (0) ≠ 0, invert the outputs corresponding to 1 bits in f (0). Each inversion needs a 1 × 1 Toffoli gate (TOF1). The transformed function f+ has f+ (0) = 0.
Step 2 Assume each i in turn for 1 ≤ i < 2m − 1 letting f+ indicate the current reversible specification. If f+ (i) = i, no transformation and therefore no Toffoli gate are needed for this i. Otherwise, gates are needed to transform the specification to a new specification with f++(i) = i. The required gates have to map f+ (i) → i.
Let p be the bit sequence with 1’s in all positions where the binary expansion of i is 1, while the expansion of f+ (i) is 0. These are the 1 bits that should be added in transforming f+ (i) → i. Conversely, let q be the bit sequence with 1’s in all positions where the expansion of i is 0, while the expansion of f+ (i) is 1. q specifies the bits to be deleted in the transformation.
For each pj = 1, utilize the Toffoli gate with control lines corresponding to all outputs in positions where the expansion of i is 1 and whose target line is the output in position j. Then, for each qk = 1, apply the Toffoli gate with control lines corresponding to all outputs in positions where the expansion of f+ (i) is 1 and whose target line is the output in position k.
3 Related works
In 2006, Thapliyal and Srinivas [49], using eight Fredkin gates (FRG), proposed a parity-preserving reversible T flip-flop, which has GC = 8, CI = 11, GO = 11 and QC = 40. Also, they provided a parity-preserving reversible J-K flip-flop using seven FRG gate which has GC = 7, CI = 9, GO = 10 and QC = 35. Moreover, they introduced D, T, J-K master–slave flip-flops. D master–slave flip-flop has GC = 5, CI = 6, GO = 6 and QC = 25. T master–slave flip-flop has GC = 23, CI = 32 and GO = 35, and QC = 115. J-K master–slave flip-flop has GC = 22, CI = 30, GO = 32 and QC = 110.
In 2010, Thapliyal and Ranganathan, using two reversible Fredkin gates (FRGs), proposed a parity-preserving reversible D flip-flop, which has GC = 2, CI = 2, GO = 2 and QC = 10 [50]. Also, they presented a parity-preserving reversible T flip-flop using three FRG gates, in which the GC = 3, CI = 3, GO = 3 and QC = 15. They also presented a parity-preserving reversible J-K flip-flop using four FRG gates, in which the GC = 4, CI = 4, GO = 5 and QC = 20.
In 2011, Haghparast and Navi, using one FRG gate as well as one double Feynman gate (DFG), proposed a reversible D latch, which has GC = 2, CI = 1 as well as GO = 2 and QC = 7 [51].
In 2012, Gharajeh and Haghparast first suggested a new parity-preserving reversible gate, called Unit4, and then presented a fault-tolerant reversible D flip-flop using one Unit4 gate in which GC = 1, CI = 3 as well as GO = 3 and QC = 10 [41].
In 2014, Pareek et al. first suggested a new parity-preserving reversible gate, called PAREEK gate and then presented a parity-preserving reversible D flip-flop, using PAREEK gate, with GC = 1, CI = 1 as well as GO = 2 and QC = 7 [40].
Also, in 2014, Pareek [52] presented a parity-preserving reversible D flip-flop, using PAREEK and DFG gates, with GC = 2, CI = 3, GO = 3 and QC = 9 and also, presented a parity-preserving reversible T flip-flop, using PAREEK and DFG gates, with GC = 2, CI = 2 as well as GO = 2 and QC = 9. Also, they provided a parity-preserving reversible J-K flip-flop using FRG, DFG and PAREEK gates, in which GC = 4, CI = 5 as well as GO = 6 and QC = 19. They also provided a parity-preserving reversible master–slave D flip-flop using two PAREEK gates, in which GC = 2, CI = 2 as well as GO = 3 and QC = 14.
In 2017, Misra et al. first proposed a new parity-preserving reversible gate, called RCQCA gate, and then presented a parity-preserving reversible D flip-flop, using RCQCA and DFG gates, with GC = 2, CI = 3, as well as GO = 3 and QC = 8 [26]. Also, they provided a parity-preserving reversible T flip-flop using RCQCA and DFG gates, in which GC = 2, CI = 2, GO = 2 and QC = 8.
In 2018, Goswami et al. [53] first proposed two new parity-preserving reversible block, called TFR and TF2G, and then presented a parity-preserving reversible D flip-flop, using one TFR and one TF2G gates, with GC = 2, CI = 3, as well as GO = 3 and QC = 19. Also, they provided a parity-preserving reversible master–slave D flip-flop using two TFR and two TF2G gates, in which GC = 4, CI = 5, GO = 4 and QC = 38.
Moreover, in Table 4, a summary of the previous parity-preserving reversible flip-flops designs is provided.
4 Proposed parity-preserving reversible designs
In this section, we first propose two effective parity-preserving reversible blocks and then, using these blocks, various new parity-preserving reversible flip-flops are introduced.
4.1 Proposed parity-preserving reversible blocks
4.1.1 Proposed block, PNM1
The truth table of the proposed 4 × 4 parity-preserving reversible block is shown in Table 5. Each input vector is mapped individually to an output vector. The proposed reversible structure is called the PNM1 block.
The output equations of the PNM1 block can be determined as follows:
\(P\left( {A,B,C,D} \right) = \left( {A \oplus B} \right)'\) | (1) |
\(Q\left( {A,B,C,D} \right) = B'\) | (2) |
\(R\left( {A,B,C,D} \right) = B^{\prime}C \oplus BD\) | (3) |
\(S\left( {A,B,C,D} \right) = B^{\prime}D \oplus BC'\) | (4) |
The circuit representation of the PNM1 block is shown in Fig. 10.
In order to calculate the quantum cost of the proposed reversible block, it is necessary first to be implemented using the NCT library (NOT-CNOT and Toffoli). For this purpose, the synthesis approach provided by Miller et al. is used [34]. The Miller et al. synthesis algorithm is a greedy method that determined the Toffoli gates only on the output side of the specification. The steps of the Miller algorithm in order to obtain the inputs via the outputs are shown in Table 6.
An \(n \times n\) Toffoli gate (TOFn (x1, x2, …, xn)) consists of (n − 1) control lines that transit through the gate unchanged and a target line on which the value is inverted if all the control lines are equal to value ‘1.’ TOF1 (A) is the special case that there are no control lines; therefore, x1 always invert. It is called NOT gate. TOF2 (A, B) is called Feynman or controlled-NOT gate (CNOT). TOF3 (A, B, C) is often termed to simply as a Toffoli gate. These gates are illustrated in Fig. 11.
As can be seen from Table 6,
Step 1 identifies TOF1 (P, Q) giving Step 2
Step 2 identifies TOF2 (Q, P) giving Step 3
Step 3 identifies TOF2 (Q, S) giving Step 4
Step 4 identifies TOF3 (Q, R, S) giving Step 5
Step 5 identifies TOF3 (Q, S, R) giving Step 6
Step 6 identifies TOF3 (Q, R, S).
It should be noted that the TOF gates are determined from the output side to the input side. The Toffoli-based circuit of the proposed PNM1 block is illustrated in Fig. 12.
Given that the quantum cost of the primitive gates \(1 \times 1\) and \(2 \times 2\) is one, then the initial quantum cost of the proposed PNM1 block is 11.
Moreover, according to Fig. 12, the NCV display of the proposed PNM1 block is shown in Fig. 13.
After simplifying the circuit shown in Fig. 13, according to the simplification rules in [33, 35,36,37], the optimized NCV display of the proposed PNM1 circuit is illustrated in Fig. 14.
Therefore, the total quantum cost of the proposed PNM1 block is 5. In addition, its logical calculation is 3α + 3β + 3δ.
4.1.2 Proposed block, PNM2
The truth table of the proposed 4 × 4 parity-preserving reversible block is shown in Table 7. Each input vector is mapped individually to an output vector. The proposed reversible structure is called the PNM2 block.
The output equations of the PNM2 block can be determined as follows:
\(P\left( {A,B,C,D} \right) = AC' \oplus BC\) | (1) |
\(Q\left( {A,B,C,D} \right) = \left( {A \oplus B} \right)'\) | (2) |
\(R\left( {A,B,C,D} \right) = C'\) | (3) |
\(S\left( {A,B,C,D} \right) = AC' \oplus BC \oplus D\) | (4) |
The circuit representation of the PNM2 block is shown in Fig. 15.
As can be seen from Table 8,
Step 1 identifies TOF1 (Q, R) giving Step 2
Step 2 identifies TOF2 (P, S) giving Step 3
Step 3 identifies TOF3 (Q, R, P) giving Step 4
Step 4 identifies TOF2 (P, Q).
It should be noted that the TOF gates are determined from the output side to the input side, respectively. The Toffoli-based circuit of the proposed PNM2 block is illustrated in Fig. 16.
Given that the quantum cost of the primitive gates \(1 \times 1\) and \(2 \times 2\) is one, then the initial quantum cost of the proposed PNM2 block is 9.
Moreover, according to Fig. 16, the NCV display of the proposed PNM1 block is shown in Fig. 17.
After simplifying the circuit shown in Fig. 17 according to the simplification rules in [33, 35,36,37], the optimized NCV display of the proposed PNM2 circuit is illustrated in Fig. 18.
Therefore, the total quantum cost of the proposed PNM2 block is 6. In addition, its logical calculation is 4α + 2β + 2δ.
4.2 Proposed parity-preserving reversible flip-flops
In this section, using the proposed parity-preserving reversible blocks PNM1, PNM2 blocks and DFG gate various parity-preserving reversible flip-flops D, T and J-K are introduced.
The output equation of a D flip-flop with inputs D and CLK is expressed as \(Q_{t + 1} = Q_{t} . \overline{\text{CLK}} + {\text{CLK}}. {\text{D}}\). In Fig. 19, the first proposed parity-preserving reversible D flip-flop (PPDFF1) is illustrated using the PNM2 block.
As seen in Fig. 19, the first proposed parity-preserving reversible D flip-flop has GC = 1, CI = 1 and GO = 2. Given that one parity-preserving reversible PNM2 block has been used in its design, so the quantum cost is calculated as follows:
The second parity-preserving reversible D flip-flop (PPDFF2) is shown in Fig. 20 using the proposed PNM1 block and DFG gate.
As seen in Fig. 20, the second proposed parity-preserving reversible D flip-flop has GC = 2, CI = 3 and GO = 3. Given that one parity-preserving reversible PNM1 block and one DFG gate have been used in its design, so the quantum cost is calculated as follows:
The output equation of the T flip-flop with inputs T and CLK can be written as \(Q_{t + 1} = {\text{T}} Q_{t} . {\text{CLK}} Q_{t} . \overline{\text{CLK}}\). Moreover, it can be easily demonstrated that the above equation is equal to \(Q_{t + 1} = ({\text{T}}. {\text{CLK}}) Q_{t} .\)
In Fig. 21, the first proposed parity-preserving reversible T flip-flop (PPTFF1) is illustrated using the PNM2 block and DFG gate.
As seen in Fig. 21, the first proposed parity-preserving reversible T flip-flop has GC = 2, CI = 2 and GO = 2. Given that one parity-preserving reversible PNM2 block and one DFG gate have been used in its design, so the quantum cost is calculated as follows:
In Fig. 22, the second proposed parity-preserving reversible T flip-flop (PPTFF2) is illustrated using the PNM1 block and DFG gate.
As seen in Fig. 22, the second proposed parity-preserving reversible T flip-flop has GC = 2, CI = 3 and GO = 3. Given that one parity-preserving reversible PNM1 block and one DFG gate have been used in its design, so the quantum cost is calculated as follows:
The characteristic equation of J-K flip-flop is \(Q_{t + 1} = \overline{\text{CLK}} Q_{t} + {\text{CLK}}\left( {J\bar{Qt} + \bar{K}Qt} \right)\). The parity-preserving reversible J-K flip-flop is shown in Fig. 23 using the proposed reversible PNM1 and PNM2 blocks.
As seen in Fig. 23, the second proposed parity-preserving reversible J-K flip-flop has GC = 2, CI = 2 and GO = 3. Given that one PNM1 block and one PNM2 block have been used in its design, so the quantum cost is calculated as follows:
In Fig. 24, the first proposed parity-preserving reversible master–slave D flip-flop is illustrated using the two parity-preserving reversible D Flip-flops (PPDFF1).
As seen in Fig. 24, the first proposed parity-preserving reversible master–slave D flip-flop has GC = 2, CI = 2 and GO = 3. Given that two parity-preserving reversible D flip-flops (PPDFF1) has been used in its design, so the quantum cost is calculated as follows:
In Fig. 25, the second proposed parity-preserving reversible master–slave D flip-flop is illustrated using the two parity-preserving reversible D flip-flops (PPDFF2).
As seen in Fig. 25, the second proposed parity-preserving reversible master–slave D flip-flop has GC = 4, CI = 6 and GO = 6. Given that two parity-preserving reversible D flip-flops (PPDFF2) have been used in its design, so the quantum cost is calculated as follows:
In Fig. 26, the proposed parity-preserving reversible master–slave T flip-flop is illustrated using the one parity-preserving reversible T flip-flop (PPTFF2) and one parity-preserving reversible D flip-flop (PPDFF2).
As seen in Fig. 26, the proposed parity-preserving reversible master–slave T flip-flop has GC = 4, CI = 6 and GO = 6. Given that one parity-preserving reversible T flip-flop (PPTFF2) and one parity-preserving reversible D flip-flop (PPDFF2) have been used in its design, so the quantum cost is calculated as follows:
In Fig. 27, the proposed parity-preserving reversible master–slave J-K flip-flop is illustrated using the one parity-preserving J-K flip-flop (PPJ-KFF) and one parity-preserving reversible D flip-flop (PPDFF2).
As seen in Fig. 27, the proposed parity-preserving reversible master–slave J-K flip-flop has GC = 4, CI = 5, and GO = 6. Given that one parity-preserving J-K flip-flop (PPJ-KFF) and one parity-preserving reversible D flip-flop (PPDFF2) have been used in its design, so the quantum cost is calculated as follows:
In Fig. 28, the proposed parity-preserving reversible 4-bit asynchronous up-counter (PPUPC) is illustrated using the four proposed parity-preserving reversible D flip-flops (PPDFF2) and three FRG gates.
As seen in Fig. 28, the proposed parity-preserving reversible 4-bit asynchronous up-counter has GC = 11, CI = 18 and GO = 15. Given that four parity-preserving reversible D flip-flops (PPDFF1) flip-flops and three FRG gates have been used in its design, so the quantum cost is calculated as follows:
5 Simulation results and comparisons
In this section, we implement the proposed reversible blocks in QCA technology by QCADesigner 2.0.3 software [54]. As observed, the proposed reversible blocks consist of 2-input AND, 2-input XOR and 2-input XNOR gates. To achieve effective quantum-dot cellular automata [55,56,57,58,59] implementation of the proposed blocks, we have used 2-input XOR presented in [60]. The QCA layouts, along with the simulation results of the proposed reversible blocks, are illustrated in Fig. 29.
As seen in Fig. 29, the proposed QCA layouts are coplanar and consist of simple cells so that crossing of the wires is carried out using the technique introduced by Abedi et al. [61]. The QCA layout of the PNM1 block has 345 cells with occupied area 0.82 μm2 and a delay equal to 2.75 clock cycles. Also, the QCA layout of the PNM2 block has 353 cells with occupied area 0.63 μm2 and a delay equal to 2.5 clock cycles.
In order to compute the energy consumption of the QCA reversible blocks, we have used the QCAPRO tool [62]. The results of the energy consumption analysis of the proposed structures at three different levels of energy (0.5 EK, 1 EK and 1.5 EK) are provided in Table 9.
Besides, energy dissipation maps of the proposed designs with tunneling energy of 0.5 EK are illustrated in Fig. 30. The cells with higher power dissipation are depicted with darker colors in the thermal hot spot maps.
In the following, the performance analyses of the proposed parity-preserving reversible designs concerning the existing designs are provided. Tables 10, 11, 12, 13, 14, 15 and 16 give the characteristics of the proposed flip-flops circuits along with the previous designs in terms of GC, CI, GO, QC, LC and ratio criteria. The ratio criterion denoted the ratio of quantum cost of each existing design in comparison with the quantum cost of the proposed design.
As shown in Table 10a, the quantum cost of the proposed PPDFF1, compared with the best previous design in [51] and [40], shows an improvement of 14.28%. Also, its GC, CI and GO criteria are equal or better to all of the previous designs. Also, as shown in Table 10b, the quantum cost of the proposed PPDFF2, compared with the best previous design in [26], shows an improvement of 12.50%. Besides, its GC, CI and GO criteria are very close to than all of previous designs.
Moreover, the improvement percentage of the proposed parity-preserving reversible PPDFF1 and PPDFF2 is shown in Fig. 31.
As shown in Table 11, the quantum cost of the proposed PPTFF2, compared with the best previous design in [26], shows an improvement of 12.50%. In addition, its GC, CI and GO criteria are smaller or equal to all of previous designs. In addition, the improvement percentage of the proposed parity-preserving reversible PPTFF1 and PPTFF2 is shown in Fig. 32.
As shown in Table 12, the quantum cost of the proposed PPJ-KFF1, compared with the best previous design in [52], shows an improvement of 42.10%. Also, its GC, CI and GO criteria are so better than all of the previous designs.
Besides, the improvement percentage of the proposed parity-preserving reversible PPJ-KFF1 is shown in Fig. 33.
As shown in Table 13a, the quantum cost of the parity-preserving master–slave Proposed#1, compared with the best previous design in [52], shows an improvement of 14.28%. In addition, its GC, CI and GO criteria are equal to all of the previous designs. Also, as shown in Table 13b, the quantum cost of the parity-preserving master–slave Proposed#2, compared with the best previous design in [49] shows an improvement of 44%. Besides, its GC, CI and GO criteria are very close to all of the previous designs.
In addition, the improvement percentage of the proposed parity-preserving reversible master–slave D flip-flop is shown in Fig. 34.
Also, as shown in Table 14, the quantum cost of the proposed parity-preserving master–slave T flip-flop, compared with the best previous design in [49], shows an improvement of 87.82%. In addition, its GC, CI and GO criteria are smaller than all of the previous designs. Besides, the improvement percentage of the proposed parity-preserving reversible master–slave T flip-flop is shown in Fig. 35.
Also, as shown in Table 15, the quantum cost of the proposed parity-preserving master–slave J-K flip-flop, compared with the best previous design in [49], shows an improvement of 83.63%. In addition, its GC, CI and GO criteria are smaller than all of the previous designs. Besides, the improvement percentage of the proposed parity-preserving reversible master–slave J-K is shown in Fig. 36.
6 Conclusion
In this paper, initially two novel parity-preserving reversible blocks were introduced. Then, effective designs of parity-preserving reversible D, T and J-K flip-flops, as well as their master–slave, were proposed using the proposed blocks and DFG gates. Finally, a parity-preserving reversible 4-bit asynchronous up-counter was designed using the proposed parity-preserving reversible D flip-flops and three FRG gates. The proposed circuits are compared with the existing counterparts in terms of constant inputs, garbage outputs and quantum cost. The comparison results show that the proposed designs are superior to the quantum cost and some of the other criteria, such as constant input and garbage outputs. Utilizing the proposed flip-flops designs in the parity-preserving reversible sequential circuits such as registers, BCD counters and RAM minimizes the quantum cost criteria. All the scales are in the nanometric area.
References
Landauer R (1961) Irreversibility and heat generation in the computing process. IBM J Res Dev 5(3):183–191
Bennett CH (1973) Logical reversibility of computation. IBM J Res Dev 17(6):525–532
Perkowski M et al (2001) A general decomposition for reversible logic. In: Proceedings of RM’2001, Starkville, pp 119–138
Toffoli T (1980) Reversible computing. In: International Colloquium on Automata, Languages, and Programming. Springer, pp 632–644
Allen JS, Biamonte JD, Perkowski M (2005) ATPG for reversible circuits using technology-related fault models. In: Proceedings of the 7th international symposium on representations and methodology of future computing technologies, RM2005, Tokyo, Japan, pp 100–107
Taraphdar C, Chattopadhyay T, Roy JN (2010) Mach-Zehnder interferometer-based all-optical reversible logic gate. Opt Laser Technol 42(2):249–259
Nielson MA, Chuang IL (2000) Quantum computation and quantum information. Cambridge University Press, Cambridge
Wood DH, Chen J (2004) Fredkin gate circuits via recombination enzymes. In: Proceedings of the 2004 Congress on Evolutionary Computation (IEEE Cat. No. 04TH8753), 2004, vol 2. IEEE, pp 1896–1900
Bandyopadhyay S, Balandin A, Roychowdhury V, Vatan F (1998) Nanoelectronic implementations of reversible and quantum logic. Superlattices Microstruct 23(3–4):445–464
Barenco A et al (1995) Elementary gates for quantum computation. Phys Rev A 52(5):3457
Morrison MA (2012) Design of a reversible alu based on novel reversible logic structures
Hung WN, Song X, Yang G, Yang J, Perkowski M (2004) Quantum logic synthesis by symbolic reachability analysis. In: Proceedings of the 41st Annual Design Automation Conference, 2004. ACM, pp 838–841
Mohammadi M, Eshghi M (2009) On figures of merit in reversible and quantum logic designs. Quantum Inf Process 8(4):297–318
Babu HMH, Mia MS (2016) Design of a compact reversible fault tolerant division circuit. Microelectron J 51:15–29
Biswas AK, Hasan MM, Chowdhury AR, Babu HMH (2008) Efficient approaches for designing reversible binary coded decimal adders. Microelectron J 39(12):1693–1703
Akbar EPA, Haghparast M, Navi K (2011) Novel design of a fast reversible Wallace sign multiplier circuit in nanotechnology. Microelectron J 42(8):973–981
Noorallahzadeh M, Mosleh M (2019) Efficient designs of reversible latches with low quantum cost. IET Circuits Dev Syst 13(6):806–815
Misra NK, Sen B, Wairya S (2017) Towards designing efficient reversible binary code converters and a dual-rail checker for emerging nanocircuits. J Comput Electron 16(2):442–458
PourAliAkbar E, Mosleh M (2019) An efficient design for reversible wallace unsigned multiplier. Theor Comput Sci 773:43–52
Parhami B (2006) Fault-tolerant reversible circuits. In: 2006 Fortieth Asilomar Conference on Signals, Systems and Computers, 2006. IEEE, pp 1726–1729
Haghparast M, Navi K (2008) Design of a novel fault tolerant reversible full adder for nanotechnology based systems. World Appl Sci J 3(1):114–118
Valinataj M (2017) Novel parity-preserving reversible logic array multipliers. J Supercomput 73(11):4843–4867
Ariafar Z, Mosleh M (2019) Effective designs of reversible vedic multiplier. Int J Theor Phys 58(8):2556–2574
Dastan F, Haghparast M (2011) A novel nanometric fault tolerant reversible divider. Int J Phys Sci 6(24):5671–5681
Safari P, Haghparast M, Azari A, Branch A (2012) A design of fault tolerant reversible arithmetic logic unit. Life Sci J 9(3):643–646
Misra NK, Wairya S, Sen B (2018) Design of conservative, reversible sequential logic for cost efficient emerging nano circuits with enhanced testability. Ain Shams Eng J 9(4):2027–2037
Sarker A, Babu HMH, Rashid SMM (2015) Design of a DNA-based reversible arithmetic and logic unit. IET Nanobiotechnol 9(4):226–238
Thapliyal H, Ranganathan N (2010) Design of reversible sequential circuits optimizing quantum cost, delay, and garbage outputs. ACM J Emerg Technol Comput Syst (JETC) 6(4):14
Feynman RP (1986) Quantum mechanical computers. Found Phys 16(6):507–531
Morrison M, Ranganathan N (2011) Design of a reversible ALU based on novel programmable reversible logic gate structures. In: 2011 IEEE Computer Society Annual Symposium on VLSI, 2011. IEEE, pp 126–131
Smolin JA, DiVincenzo DP (1996) Five two-bit quantum gates are sufficient to implement the quantum Fredkin gate. Phys Rev A 53(4):2855
Morrison M, Ranganathan N (2013) A novel optimization method for reversible logic circuit minimization. In: 2013 IEEE Computer Society Annual Symposium on VLSI (ISVLSI), 2013. IEEE, pp 182–187
Rahman MM, Banerjee A, Dueck GW, Pathak A (2011) Two-qubit quantum gates to reduce the quantum cost of reversible circuit. In: 2011 41st IEEE International Symposium on Multiple-Valued Logic, 2011. IEEE, pp 86–92
Miller DM, Maslov D, Dueck GW (2003) A transformation based algorithm for reversible logic synthesis. In: Proceedings 2003. Design Automation Conference (IEEE Cat. No. 03CH37451), 2003. IEEE, pp 318–323
Sasanian Z (2012) Technology mapping and optimization for reversible and quantum circuits, Doctoral dissertation
Maslov D, Dueck GW, Miller DM (2005) Toffoli network synthesis with templates. IEEE Trans Comput Aided Des Integr Circuits Syst 24(6):807–817
Maslov D, Dueck GW, Miller DM (2003) Simplification of Toffoli networks via templates. In: 16th Symposium on Integrated Circuits and Systems Design, 2003. SBCCI 2003. Proceedings, 2003. IEEE, pp 53–58
Ali MB, Hirayama T, Yamanaka K, Nishitani Y (2018) Function design for minimum multiple-control Toffoli circuits of reversible adder/subtractor blocks and arithmetic logic units. IEICE Trans Fundam Electron Commun Comput Sci 101(12):2231–2243
Ali MB, Hirayama T, Yamanaka K, Nishitani Y (2015) Quantum cost reduction of reversible circuits using new Toffoli decomposition techniques. In: 2015 International Conference on Computational Science and Computational Intelligence (CSCI), 2015. IEEE, pp 59–64
Pareek V, Gupta S, Jain SC, Kumar A (2014) A novel realization of sequential reversible building blocks. In: Future Computing 2014, the Sixth International Conference on Future Computational Technologies and Applications, 2014, pp 1–6
Gharajeh MS, Haghparast M (2012) On design of a fault tolerant reversible 4-bit binary counter with parallel load. Aust J Basic Appl Sci 6(7):430–446
Zhou R-G, Li Y-C, Zhang M-Q (2014) Novel designs for fault tolerant reversible binary coded decimal adders. Int J Electron 101(10):1336–1356
Haghparast M, Bolhassani A (2016) On design of parity preserving reversible adder circuits. Int J Theor Phys 55(12):5118–5135
Misra NK, Sen B, Wairya S, Bhoi B (2017) Testable novel parity-preserving reversible gate and low-cost quantum decoder design in 1D molecular-QCA. J Circuits Syst Comput 26(09):1750145
Arabani SR, Reshadinezhad MR, Haghparast M (2018) Design of a parity preserving reversible full adder/subtractor circuit. Int J Comput Intell Stud 7(1):19–32
Islam M, Begum Z (2010) Reversible logic synthesis of fault tolerant carry skip BCD adder. arXiv:1008.3288
Fredkin E, Toffoli T (1982) Conservative logic. Int J Theor Phys 21(3–4):219–253
Hagparast M, Navi K (2008) A novel fault tolerant reversible gate for nanotechnology based system. Am J Appl Sci 5(5):519–523
Thapliyal H, Srinivas M (2006) An extension to DNA based Fredkin gate circuits: design of reversible sequential circuits using Fredkin gates. arXiv:cs/0603092
Thapliyal H, Ranganathan N (2009) Reversible logic-based concurrently testable latches for molecular QCA. IEEE Trans Nanotechnol 9(1):62–69
Haghparast M, Navi K (2011) Novel reversible fault tolerant error coding and detection circuits. Int J Quantum Inf 9(02):723–738
Pareek V (2014) A new gate for optimal fault tolerant & testable reversible sequential circuit design. arXiv:1410.2373
Goswami M, Raj G, Narzary A, Sen B (2018) A methodology to design online testable reversible circuits. In: International Symposium on VLSI Design and Test, 2018. Springer, pp 322–334
Walus K, Dysart TJ, Jullien GA, Budiman RA (2004) QCADesigner: a rapid design and simulation tool for quantum-dot cellular automata. IEEE Trans Nanotechnol 3(1):26–31
Seyedi S, Darbandi M, Navimipour NJ (2019) Designing an efficient fault tolerance D-latch based on quantum-dot cellular automata nanotechnology. Optik 185:827–837
Fam SR, Navimipour NJ (2019) Design of a loop-based random access memory based on the nanoscale quantum dot cellular automata. Photon Netw Commun 37(1):120–130
Ahmadpour S-S, Mosleh M (2019) New designs of fault-tolerant adders in quantum-dot cellular automata. Nano Commun Netw 19:10–25
Ahmadpour SS, Mosleh M, Rasouli Heikalabad S (2019) Robust QCA full-adders using an efficient fault-tolerant five-input majority gate. Int J Circuit Theory Appl 47(7):1037–1056
Ahmadpour S-S, Mosleh M (2018) A novel fault-tolerant multiplexer in quantum-dot cellular automata technology. J Supercomput 74(9):4696–4716
Ahmadpour S-S, Mosleh M, Heikalabad SR (2018) A revolution in nanostructure designs by proposing a novel QCA full-adder based on optimized 3-input XOR. Phys B 550:383–392
Abedi D, Jaberipur G, Sangsefidi M (2015) Coplanar full adder in quantum-dot cellular automata via clock-zone-based crossover. IEEE Trans Nanotechnol 14(3):497–504
Srivastava S, Asthana A, Bhanja S, Sarkar S (2011) QCAPro-an error-power estimation tool for QCA circuit design. In: 2011 IEEE International Symposium of Circuits and Systems (ISCAS), 2011. IEEE, pp 2377–2380
Author information
Authors and Affiliations
Corresponding author
Additional information
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
Rights and permissions
About this article
Cite this article
Noorallahzadeh, M., Mosleh, M. Parity-preserving reversible flip-flops with low quantum cost in nanoscale. J Supercomput 76, 2206–2238 (2020). https://doi.org/10.1007/s11227-019-03074-3
Published:
Issue Date:
DOI: https://doi.org/10.1007/s11227-019-03074-3