Keywords

1 Introduction

With the advancements of the fabrication technologies, the necessity of the developing high end circuit and the computing devices is observed. Quantum computing [1, 2] has evolved as one of such solutions that have the capacity to meet the asked challenges. Nowadays, it (quantum technology [3, 4]) is considered as one of the most promising research domains due not only its computing capacity but also for its wide range of applications in different fields like nanotechnology, cryptography, machine learning and bioinformatics. This highly emerging filed is not restricted to theoretical concepts only, enormous progress [5,6,7] has been made towards developing quantum circuit implementing technologies like NMR, IoN Trap and Super Conducting qubit. Successful implementation of the 2-qubit quantum gate in silicon [8], the conceptualization of lower qubit quantum computers [9] had again advanced this highly emerging computing field to a new dimension. Reversible circuit is one of the most promising means which can design quantum circuit as all the quantum operations are inherently reversible. In recent time, this filed has progressed significantly, where different well-established algorithms are proposed for the efficient synthesis and design of reversible logic, such as ESOP [10], BDD [11] and Reed-Muller [12]. In addition to circuit synthesis, identification of faults [13] in reversible circuits has also become a significant issue to fabricate the fault-free circuit. For example, some well-known fault models are Single Missing Gate Fault (SMGF), Partial Missing Gate Fault (PMGF), Multiple Missing Gate Fault (MMGF), and Repeated Gate Fault (RGF).

Several researches are ongoing in the domain of reversible circuit testing for the design of efficient fault detection and diagnosis algorithms. Here, we are presenting some well-known algorithms to perform the test operation in reversible circuits.

The test vector generation mechanism for the reversible circuit to detect the fault and also to localize the fault for different fault models is presented in [14]. Here, the deterministic approach and probabilistic approach of fault detection are described and compared. Special measurement of the internal states of gates is used to establish the probabilistic mechanism of fault detection. An efficient and complete test vector generation mechanism for the reversible circuit is reported in [15]. Apart from that, finding out minimal test set by integer linear programming for smaller circuits has been described in the work. The derivation of the optimal test set (OTS) and its effective use in the detection of missing gate faults in k-CNOT gate based reversible circuits is introduced in [16], where the authors have find out that the OTS is sufficient to detect all SMGFs and all detectable repeated gate faults (RGFs) in the circuit. Another approach of SMGF and RGF detection has been proposed in [17]. In this work, test vectors are generated with minimum test time to find out any kind of SMGF and RGF in the circuit. Here, 100% fault coverage has also been achieved. Apart from test vector generation and fault detection in reversible circuits, another aspect of testing is fault localization. The mechanism of fault localization for the reversible circuit is proposed in [18]. Here in this approach, the reversible circuit is divided into two parts. The first part of the circuit is represented as a symmetric adaptive tree and another part of the circuit is represented as a mirror image of the first part. Hence, it is quite easy to locate the exact fault in the circuit so that the fault can be corrected as early as possible. A new test vector generation technique is introduced in [19] where the concept of Boolean generator is used. An approach of fault diagnosis is also presented in [20]. Till so far we have talked on different developments over offline testing techniques, now here we are discussing on progressed made over online testing. An online testing technique for all (n × n) and d depth reversible circuits using 2d garbage outputs along with (2d + 1) auxiliary lines has been proposed in [21]. The formation of testable design for effectively finding faults is discussed in [22], where some redundant gates are added in the input side of the testable design to make the design simpler. Another approach of online testing using testable design approach has been presented in [23], where the existing gates are modified to design two new gates which efficiently detects faults in online circuits. As the testable design is formed with additional lines and gates, it creates design overhead in the testing process. Hence to minimize the design overhead in the testable design, an online testing scheme has been proposed in [24], where no auxiliary lines are used to detect the possible SMGFs in reversible circuits in online mode. So far, we mainly have talked about different offline and online testing algorithms for SMGF, PMGF, MMGF, and RGF. Apart from that, a reversible circuit may incur the control node displacement fault (CNDF) in a gate of the circuit. To deal with such a type of fault, here in this proposed approach, we have proposed an online fault detection mechanism of CNDF in reversible circuits.

The rest of the paper is presented as follows. Introduction to reversible circuit and the different fault variations are stated in Sect. 2. The proposed fault detection model with example is explained in Sect. 3. The different benchmarking and experimental evaluations are reported in Sect. 4 and finally, the paper is concluded in Sect. 5.

2 Preliminaries

Some basic concepts regarding reversible circuits and different fault models related to the reversible circuits are introduced in this section.

Definition 1: A circuit that exhibits objective mapping between inputs to outputs and has equal number of input-output lines is known as reversible circuit.

The circuit must also need to satisfy the fan-out free condition and all the gates in the circuit must be reversible only.

Some Familiar gates in the reversible domain are Feymen [25], Toffoli [26], Fredkin [27].

Definition 2 [2]: ESOP (Exclusive Sum-Of-Products) based circuit can be expressed in Boolean function represented by the operator ‘⨁’. Here, we will discuss some of the fault models for the reversible circuits.

Definition 3: When a gate completely disappears or goes missing from a circuit then the infused fault is termed as Single Missing-Gate Fault (SMGF).

Definition 4: Unwanted occurrence of a gate by multiple times is known as repeated gate fault (RGF).

Definition 5: When a circuit has multiple and consecutive SMGFs in a circuit then the intensity of the fault in the circuit goes high which is known as multiple missing-gate faults (MMGF).

Definition 6: A fault is categorized as Partial missing gate fault (PMGF), when control nodes from gates go missing by causing change in functional behavior of the circuit then the infused fault is termed as Partial missing gate fault (PMGF).

Definition 7 [28]: Unlike PMGF, when control nodes of a gate get misplaced over different circuit lines but size of the gate remain same then the incurred fault in the circuit is termed as control node displacement fault (CNDF).

For an example, If the control node at the line x in any gate \({G}_{i}\) of the circuit is displaced to the through line y then the CNDF is denoted as \({D}_{{G}_{i}}^{x\to y}\), where 0 ≤ i ≤ (N-1) and N represent total gates in the circuit. Whereas the test vectors needed to detect any \({D}_{{G}_{i}}^{x\to y}\) are represented as T (\({D}_{{G}_{i}}^{x\to y}\)) [28]. Here it is assumed that the target node is always fixed to its original position.

3 Proposed Technique

Here, we introduce two different variations in CNDF testing technique – 1) generalised CNDF testing scheme in any arbitrary reversible circuit, and 2) ESOP design specific CNDF detection procedure. Both the testing processes are divided into the following four phases: formation of circuit under test, establishment of fault detection mechanism, test vector generation, detection of the fault. We explain all the phases of this CNDF detection using a model circuit.

3.1 CNDF Testing Scheme for Any Reversible Circuit

3.1.1 Formation of Circuit Under Test

To transform a Toffoli circuit to the form of circuit under test, at first an extra circuit line is added in the input design and then a series of copy gates are added (for all the existing gates in the circuit). Hence after, a list of CNOT gate is placed in the beginning and at the end of the circuit where the number of newly added CNOT gate is twice the number of circuit lines in the Toffoli network. The steps involving this transformation are outlined in Algorithm 1.

Let us take the circuit (Cinput) of Fig. 1(a) and transform it to circuit under test (Cunder-test) using Algorithm 1. From the circuit configuration, we see that the design has 5 CNOT/Toffoli gates placed over 3 circuit lines. Now in the initial step, an auxiliary line (having input as Iaux and output as Oaux) is appended after the input line z and place five copy gates for all the five gates in the circuit. As the initial circuit had three circuit lines, accordingly we add CNOT gates at beginning and end of the design. Finally, we obtain the testable design (Cunder-test) as depicted in Fig. 1(b) and this transformed design also preserve the same logic functionality as the initial circuit had.

Fig. 1.
figure 1

(a) Input Circuit (Cinput)“ham3\design#1” and (b) Circuit Under Test (Cunder-test) for (a).

Full size image

3.1.2 CNDF Detection Mechanism

Any CNDF in any gate of the circuit is detected if and only if the following condition is true Oaux = \(\overline{{I }_{aux}}\).

Lemma 1:

For any CNDF in any gate \({G}_{i}\)(\({D}_{{G}_{i}}^{x\to y}\)), the test vector T(\({D}_{{G}_{i}}^{x\to y}\)) can detect the CNDF if and only if Oaux = \(\overline{{I }_{aux}}\).

Proof:

From any input circuit (Cinput), the circuit under test (Cunder_test) is designed in such a way that it always satisfies the statement Oaux = Iaux for any fault free circuit Cunder_test.

To illustrate trueness of the statement, let us consider the fault free circuit Cunder_test of Fig. 1(b). Now, it can be observed that Oaux = Iaux⨁ z⨁ y⨁ x⨁ yz⨁ z⨁ y⨁ z⨁ x⨁ yz⨁ y⨁ x⨁ yz⨁ z⨁ y⨁ z⨁ x⨁ yz⨁ y⨁ z⨁ x⨁ yz⨁ y⨁ x⨁ yz = Iaux.

So, for any fault free circuit Cunder_test, it is always true that Oaux = Iaux. Now for any occurrence of CNDF in the circuit Cunder_test, it is always true that Oaux = \(\overline{{I }_{aux}}\). To check the accuracy of the statement, it is assumed that a CNDF (\({D}_{{G}_{2}}^{y\to x}\)) has occurred in the circuit Cunder_test of Fig. 1(b). Now, Oaux = Iaux⨁ z⨁ y⨁ x⨁ yz⨁ z⨁ y⨁ z⨁ x⨁ yz⨁ z⨁ z⨁ y⨁ x⨁ yz = Iaux⨁ x⨁ y⨁ z⨁ yz.

At the time of the fault detection, as the control node moves from y to x, the node x always need to set to 1 and other terms would be nullified by default. Now, Oaux becomes Oaux = Iaux⨁1 = \(\overline{{I }_{aux}}\). Hence, faults are detected when Oaux = \(\overline{{I }_{aux}}\).

■

3.1.3 Test Vector Formation Method for the CNDF

Any CNDF is detected by fixing 0 at the original position of the control node and 1 at the current position of the control node of the circuit under test. Also 1 is set to others control node and 0/1 to the target line and through line of the circuit under test respectively.

Let us consider the circuit of Fig. 2(a) to evaluate the test vector formation method for the CNDF. According to the CNDF detection rule as discussed, the CNDF of \({C}_{{G}_{0}}^{y\to z}\) Fig. 2(a) is detected by < xyzT >  =  < 1 0 1 0 > and < xyzT >  =  < 1 0 1 1 >. So, T(\({D}_{{G}_{0}}^{y\to z}\)) = {<1 0 1 0 >, < 1 0 1 1 >}.

Fig. 2.
figure 2

Formation of Test Vector shown in (b), (c) for the \({C}_{{G}_{0}}^{y\to z}\) in (a).

Full size image

3.1.4 Detection of the CNDF

Let us take the circuit of Fig. 1(b) which is the circuit under test of Fig. 1(a) to observe the detection mechanism of CNDF in Fig. 1(b). Different possible CNDF in Fig. 1(b) are\({C}_{{G}_{1}}^{z\to x}\),\({C}_{{G}_{2}}^{y\to x}\), \({C}_{{G}_{3}}^{x\to y}\) and\({C}_{G4}^{z\to x}\). Based on the test vector formation method discussed earlier, generated test vectors for all the CNDF are T(\({D}_{{G}_{1}}^{z\to x}\)) =  < 1 3 4 7 >, T(\({D}_{{G}_{2}}^{y\to x}\)) =  < 1 2 4 6 >, T(\({D}_{{G}_{3}}^{x\to y}\)) =  < 1 2 4 6 >, T(\({D}_{{G}_{4}}^{z\to x}\)) =  < 2 3 6 7 >.

Let us assume that the fault \({C}_{{G}_{2}}^{y\to x}\) occurs in G2of the Cunder_test in Fig. 1(b) where the control node moves to input line x from the input line y.

So, Oaux = Iaux⨁ z⨁ y⨁ x⨁ yz⨁ z⨁ y⨁ z⨁ x⨁ yz⨁ z⨁ z⨁ y⨁ x⨁ yz = Iaux⨁ x⨁ y⨁ z⨁ yz.

To detect the CNDF (\({C}_{{G}_{2}}^{y\to x}\)), any test vector from the list < 1, 2, 4, 6 > can be used. The vector 2 (<xyz >  =  < 100 >) is chosen from the list and applied over the Cunder_test. Now, Oaux = Iaux⨁ x⨁ y⨁ z⨁ yz = Iaux⨁ 1⨁ 0⨁ 0⨁ 0.0 =\(\overline{{I }_{aux}}\).

Here, it is observed that Oaux = = \(\overline{{I }_{aux}}\) which reveals that there is CNDF in the circuit of Fig. 1(b). Similarly, any CNDF in the circuit under test can be detected in online mode.

Till now, we have seen the behaviour of Algorithm 1 on any reversible circuit constructed with k-CNOT gates. The Example 1 is used to analyse the behaviour of the Algorithm 1 on the ESOP based reversible circuit..

Example 1: Let’s consider an ESOP circuit as shown in Fig. 3(a) to see the outcome of Algorithm 1 on the ESOP circuit. The testable circuit implemented by Algorithm 1 is shown in Fig. 3(b).

Fig. 3.
figure 3

(a) Input ESOP circuit (Cinput) and (b) Circuit Under Test (Cunder-test).

Full size image

Let us assume that the CNDF (\({D}_{{G}_{2}}^{y\to z}\)) has occurred in G2of Fig. 4(b). The said CNDF can be detected by T(\({D}_{{G}_{2}}^{y\to z}\)) = {<xyzw >  =  < 10 1 0 > or < xyzw >  =  < 1 0 1 1 >}. Due to the fault in the circuit, Oaux becomes Oaux = Iaux⨁ x⨁ y⨁ z⨁ w⨁ Ti⨁ xw⨁ w⨁ xy⨁ yz⨁ Ti⨁ xw⨁ w⨁ xy⨁ yz⨁ w⨁ z⨁ y⨁ x = Iaux⨁ xy⨁ xz.

Now, for the test vector < xyzw >  =  < 1 0 1 0 >, Oaux = Iaux⨁ 1.0⨁1.1 =\(\overline{{I }_{aux}}\). Hence, the fault \({C}_{{G}_{2}}^{y\to z}\) in the testable circuit of Fig. 4(b) is detected.

Here, in this example, it can be observed that total (2n + G) number of more gates (circuit overhead) are required to design the circuit under test to detect CNDF for the ESOP circuit using the Algorithm 1, where n represents total input lines of the input circuit and G means all gates of the input circuit.

3.2 CNDF Testing Scheme Only for ESOP Circuit

It has been experimented that the circuit overhead can be reduced to perform the CNDF test on the ESOP circuit and that is the primary motivation to develop the Algorithm 2 that describes the CNDF detection only in ESOP circuit with minimized circuit overhead. Algorithm 2 is explained in detail in the next section.

3.2.1 Formation of Circuit Under Test

The very same fault detection condition (Oaux = \(\overline{{I }_{aux}}\)) discussed in Algorithm 1 is also used in Algorithm 2 for the detection of a fault in the testable circuit.

Fig. 4.
figure 4

(a). Final testable circuit Ctestable

Full size image

3.2.2 Test Vector Formation Method for the CNDF

All possible CNDF for the circuit in Fig. 4(a) are\({D}_{{G}_{0}}^{x\to y}\),\({D}_{{G}_{0}}^{x\to z}\),\({D}_{{G}_{0}}^{w\to y}\),\({D}_{{G}_{0}}^{w\to z}\),\({D}_{{G}_{1}}^{w\to x}\),\({D}_{{G}_{1}}^{w\to y}\),\({D}_{{G}_{1}}^{w\to z}\),\({D}_{{G}_{2}}^{x\to z}\),\({D}_{{G}_{2}}^{x\to w}\),\({D}_{{G}_{2}}^{y\to z}\),\({D}_{{G}_{2}}^{y\to w}\),\({D}_{{G}_{3}}^{y\to x}\),\({D}_{{G}_{3}}^{y\to w}\), \({D}_{{G}_{3}}^{z\to x}\) and\({D}_{{G}_{3}}^{z\to w}\). Required test vectors needed for all the respective CNDFs are T(\({D}_{{G}_{0}}^{x\to y}\)) =  < 5, 7 >, T(\({D}_{{G}_{0}}^{x\to z}\)) =  < 3, 7 >, T(\({D}_{{G}_{0}}^{w\to y}\)) =  < 12, 14 >, T(\({D}_{{G}_{0}}^{w\to z}\)) =  < 10, 14 >, T(\({D}_{{G}_{1}}^{w\to x}\)) =  < 8, 10, 12, 14 >, T(\({D}_{{G}_{1}}^{w\to y}\)) =  < 4, 6, 12, 14 >, T(\({D}_{{G}_{1}}^{w\to z}\)) =  < 2, 6, 10, 14 >, T(\({D}_{{G}_{2}}^{x\to z}\)) =  < 6, 7 >, T(\({D}_{{G}_{2}}^{x\to w}\)) =  < 5, 7 >, T(\({D}_{{G}_{2}}^{y\to z}\)) =  < 10, 11 >, T(\({D}_{{G}_{2}}^{y\to w}\)) =  < 9, 11 >, T(\({D}_{{G}_{3}}^{y\to x}\)) =  < 10, 11 >, T(\({D}_{{G}_{3}}^{y\to w}\)) =  < 3, 11 >, T(\({D}_{{G}_{3}}^{z\to x}\)) =  < 12, 13 >, T(\({D}_{{G}_{3}}^{z\to w}\)) =  < 5, 13 >.

3.2.3 Detection of the CNDF

Let’s consider the CNDF (\({D}_{{G}_{0}}^{x\to y}\)) that occurs in G0of Fig. 4(a). Hence, the Ctestable circuit becomes faulty and the expression from Oaux becomes Oaux = (Iaux⨁ Ti) ⨁ (xw⨁ w ⨁ xy⨁ yz) ⨁ (yw ⨁ w⨁ xy⨁ yz) ⨁ Ti = Iaux⨁ xw⨁ yw.

The fault \({D}_{{G}_{0}}^{x\to y}\) is identified by T(\({D}_{{G}_{0}}^{x\to y}\)) =  < 5, 7 >. Now apply the test vector5 i.e. < xyzw >  =  < 0101 > over the circuit Cunder-test then Oaux = Iaux⨁ 0.1⨁ 1.1=\(\overline{{I }_{aux}}\) is observed. As Oaux =\(\overline{{I }_{aux}}\), hence it is confirmed that a CNDF occurred in the circuit of Fig. 4(b). Similarly, the other CNDFs in the circuit can be detected by the described mechanism.

4 Experimental Results

We have tested our technique over a wide range of benchmarks [29] and the obtained results are summarized in Tables 1 and 2 respectively. In Table 1, the overhead calculation (Garbage Output (GO) and Quantum Cost (QC)) of the testable design over non-testable design of our approach (Algorithms 1 and 2) is compared and tabulated for any reversible circuit.

Similarly, in Table 2, Algorithms 1 and 2 of our proposed work is compared to justify the efficiency algorithm when it works only for the ESOP circuit. It has been observed from Table 2 that the ESOP circuit can be tested with the reduced design overhead using Algorithm 2.

Table 1. Overhead calculation of the circuit-under test over the input circuit
Full size table
Table 2. Comparison of Algorithms 1 and 2 only on ESOP circuit
Full size table

5 Conclusion

Several well-established algorithms are available for fault models like SMGF, PMGF, and MMGF. But, till now no such algorithms are for the detection of the control node displacement fault in online mode. Here in this work, we have implemented a fault detection mechanism to detect the control node displacement fault in the running time of the circuit. The developed fault detection method has been successfully tested over different benchmark circuits and the obtained results have been disclosed in different tables.