1 Introduction

According to Rolf Landauer [12], logical irreversibility is associated with physical irreversibility which serves the purpose of standardizing signals by minimal heat generation, per machine cycle. The standardized signals are independent of their exact logical history and the device is said to be logically irreversible if the output of a device does not uniquely define the inputs. For every bit of information lost in the process, there is an increase in entropy by the factor of k T l n2 Joules [12] where k is the Boltzmann constant (approximately 1.38×(10−23) J/K), T is the temperature of the circuit in Kelvins, and l n2 is the natural logarithm of 2 (approximately 0.69315). Charles H. Bennett argued that for zero power dissipation the computation has to be reversible, but if a computation is reversible it is not zero power [1]. Basically the energy dissipation for each information bit lost in a reversible circuit is less than the energy limit proposed by Landauer i.e., E<k T l n2. Hence reversible logic has gained importance with its low power application.

Reversible circuits used with newer technologies such as quantum computing [21], optical computing [28], Quantum Cellular Automata (QCA) [14], trapped-ion technology [23], adiabatic CMOS [18] offers reduction in power dissipation. Testing is one of the most important procedures in accomplishing a chip. The product quality confides in the defect level. A defect in an electronic system is the inadvertent difference between the implemented hardware and its intended design. An embodiment of a defect at the abstract function level is a fault. Detection of these faults before releasing the chip into the market is very essential. Otherwise it would be a huge setback for the manufacturing company. The benefits of testing are quality and economy [22].

Fault detection and fault diagnosis are the two important phases of testing. The role of the former is to detect whether the circuit/chip is functioning properly or not; while the latter determines exactly what went wrong and where the process needs to be altered. Both these phases have their own complexities and the latter depends on the former. Hence fault detection is the basis for fault diagnosis. There are several faults which may occur during fabrication or manufacturing of chips. These physical defects are mapped to fault models such as stuck-at faults, missing gate faults, bridging faults, cross point faults and many more [23, 24]. The detection of these faults in reversible logic circuits is relatively easy compared to irreversible counterpart. Several works have been done in this area with certain assumptions or constraints. The authors in [24] have proposed an ATPG algorithm which detects only stuck-at faults in a circuit comprising of only k-CNOT gates with few gate overheads due to incorporation of DFT technique to detect faults. The work in [7] proposes an ATPG algorithm for detecting Single Missing Gate Fault (SMGF) for k-CNOT circuits with an assumption that at most one gate can be faulty at a time and are detectable only at circuit’s primary outputs. As an extension to the work in [7], the same authors in [23] proposed an ATPG for Multiple Missing Gate Fault (MMGF) and Partial Missing Gate Fault (PMGF) considering only k-CNOT gate. The authors in [26] optimized the test set generation for the combination of SMGF and PMGF whereas the optimized test set generation for MMGF is presented in [11] and have also proved that test set for MMGF is sufficient to test SMGF and Repeated Gate Fault (RGF).

Generating complete test set for a combinational circuit with minimal test set is a NP-hard problem and the solution can be obtained using an exhaustive search technique [33]. Exact algorithms aim at computing optimal solution, with the algorithm passing through the same sequence of operations. These exact algorithms (deterministic algorithms) are expensive in terms of run time or memory and hence not suitable for very large input size. On the other hand, the solution can be obtained for this problem with various heuristic approaches. Heuristic approaches use optimization techniques for solving and they may not give minimal solution. In this work we have used an exact approach to determine CTS with minimal test set for reversible combinational circuits. Although the complexity of the problem may become exponential in some rare cases, an optimal solution is found. The detailed analysis of algorithms are presented in next sections.

In this work, we have proposed an ATPG algorithm for reversible circuits using exact approach to generate CTS which can detect single stuck-at faults, multiple stuck-at faults, repeated gate fault, partial and complete missing gate faults either exclusively or combining different fault models. This is the first work in the literature to generate CTS combining both stuck-at fault models and missing gate fault models considering all kinds of standard reversible gates such as k-CNOT, Peres and Fredkin gates (we will be referring these gates as the family of reversible gates). The synthesis algorithms for reversible circuits using Toffoli-Fredkin and k-CNOT-Peres-Fredkin gates are proposed in [5, 17, 27] for which test algorithms are not proposed in literature. This is one of the main motivations for this work. A testing tool is developed to generate CTS with minimal test set for reversible circuits which take inputs either in the form of .tfc, .real, .jpg, .bmp, .png or .fig. The output panel displays the minimal test set for that particular circuit and also the simulation time of the CPU, number of gates, and number of lines in a circuit. The tool also generates all possible CTS’s for a given circuit with an additional feature of redundancy detection and removal. All the proposed algorithms are validated on the benchmark circuits from the source available in [16].

The main contributions of this work are as follows:

  1. 1.

    An exact ATPG algorithm to generate CTS with minimal test set for a given reversible circuit.

  2. 2.

    Algorithm to test reversible circuits designed with the family of reversible gates.

The rest of the paper is organized as follows. A general discussion on reversible logic, basic reversible gates, fault models and prior work on fault detection in reversible logic is given in Section 2. In Section 3, we present the ATPG algorithms with detailed illustrations and complexity analysis to detect stuck-at fault, complete missing gate fault and partial missing gate fault in reversible circuits. Performance evaluation and the experimental results are reported in Section 4. Concluding remarks and future work are materialized in Section 5.

2 Preliminaries

2.1 Reversible Logic

Reversible logic is one of the forerunners of post-CMOS technology with ultra-low power applications. For a circuit to be called as reversible, it should satisfy certain conditions: there should be no fan-out and no feedback and also the function should be bijective. The No-fan-out theorem of reversible logic circuits has a correlation with No-cloning theorem of quantum circuits which states that an unknown quantum state cannot be copied [13]. On the other hand, the reversible circuit function should be bijective means that, it maps each input pattern to a unique output pattern. In general sense, for logic function f:B n⇒B m the number of inputs should be equal to number of outputs, i.e., n = m.

2.2 Basic Reversible Gates

For a logic gate to be reversible, there must be equal number of inputs and outputs satisfying the bijective property otherwise some information in the input can be lost in the output and vice versa [22]. Some of the reversible gates are NOT gate, CNOT/FEYNMAN gate, TOFFOLI gate, FREDKIN gate and PERES gate. The circuits designed using these gates are called reversible circuits and are governed by performance parameters such as Gate Count (GC), Quantum Cost (QC), Ancilla Inputs (AI), Garbage Outputs (GO) and Delay (Δ).

The k-CNOT gate is a k-input, k-output reversible gate having transformation from [I 1, I 2,...I k−1, I k ] to [I 1, I 2,...,I k−1,(I 1⋅I 2⋅....⋅I k−1)⊕I k ]. If k=2, then it is called CNOT gate and if k=3, it becomes TOFFOLI gate. TOFFOLI gate is the most popular reversible gate having a quantum cost of 5. FREDKIN gate is a 3X3 reversible gate which basically operates as a conditional router or multiplexer [31]. Depending on the bit value in one line (Control Line), the outputs at other two lines (Target Lines) are either passed through unchanged or swapped with each other. The FREDKIN gate is also known as controlled swap(CSWAP) gate [22] having a quantum cost of 5. FREDKIN gate has a special property that it preserves parity. Hence FREDKIN is regarded as Fault Tolerant gate, in other words conservative gate. FREDKIN gate has transformation from [ I 1, I 2, I 3] to [\(I_{1}, \bar {I_{1}} \cdot I_{2} \oplus I_{1} \cdot I_{3}, \bar {I_{1}} \cdot I_{3} \oplus I_{1} \cdot I_{2} \)]. When I 1=1, it becomes SWAP gate. The PERES gate is also a 3X3 reversible gate having transformation from [ I 1, I 2, I 3] to [ I 1, I 1⊕I 2, I 1⋅I 2⊕I 3]. The quantum cost of PERES is 4.

2.3 Fault Models

In reversible logic, in addition to traditional fault models, a few more fault models need to be considered for complete testing of these circuits and testing a circuit for these specific fault models will give high confidence over the designs. For a reversible circuit designed with k-CNOT based gates, several fault models were introduced in literature [23] and [24]. Single and Multiple Stuck-at Faults (SMSF) [23], Single Missing Gate Fault (SMGF) [23], Repeated Gate Fault (RGF) [24], Partial Missing Gate Fault (PMGF) [24] and Multiple Missing Gate Fault (MMGF) [24]. In this section, we discuss these faults in detail and their effects on functionality of reversible circuits. 3_17tc as shown in Fig. 1a is used as the reference in the following sections for explanation.

Fig. 1
figure 1

Illustration of Reversible Circuit 3_17t c for various fault conditions

Full size image

2.3.1 Single and Multiple Stuck-at Fault (SMSF)

Stuck-at faults are the traditional fault models. A single-bit error or the cell fault which makes a particular signal permanently stuck at a value and thus does not allow a signal transition. (Eg: When the circuit implemented using QCA, or adiabatic CMOS [18] and [4]). Figure 1b shows the effect of single stuck at fault in 3_17tc bench mark circuit. In Fig. 1b, a stuck-at 0 fault is present on line ‘a’ in level 3. In any test pattern generation methods for stuck-at faults, there are three necessary and sufficient steps [2]: Fault Activation, Fault Propagation and Back Tracing. On applying these steps, the test vector needed to test this fault is: 000 or 001 or 010 or 011. The truth table for the above circuit with and without Sa-0 fault is as depicted in Table 1.

Table 1 Truth table for 3_17tc reversible circuit with faulty and fault-free outputs
Full size table

2.3.2 Single Missing Gate Fault (SMGF)

In this fault model, any one k-CNOT gate completely disappears from the circuit. Technically CNOT gate behaves as a simple wire connection. This also has an impact on circuit functionality. The pulse implementing the gate operation may be short, missing, misaligned, or mistuned. Let us consider the 4th gate that is, TOFFOLI gate is missing from the circuit as shown in Fig. 1c. If we apply {1 0 1} to the circuit, the output would be {0 1 0}, whereas in the presence of SMGF fault highlighted by a box, the output will be {1 1 1}. Hence the vector {1 0 1} detects this fault. The functional error in the circuit for all other inputs due to this fault is depicted in Table 1. The total number of SMGFs is equal to total number of gates in the circuit.

2.3.3 Repeated Gate Fault (RGF)

If a gate is repeated due to multiple instantiation of a particular gate, then RGF models are used to define the effects of this fault on functionality of reversible circuit. The physical justification for an RGF is the occurrence of long or duplicated pulses [23]. Figure 1d shows the RGF model in 3_17tc reversible circuit. Let {0 0 0} be the input applied to the circuit and the expected fault-free output is {1 1 1}, whereas with the presence of RGF the output evaluates to {0 1 0}. Hence {0 0 0} is one of the test vector to detect RGF in the circuit shown in Fig. 1a. Table 1 shows fault-free and faulty outputs for all other input combinations. From the truth table it is evident that the test patterns for SMGF and RGF are the same. Both these fault types have same characteristics in terms of test patters. Based on this observation, the following theorem holds when generalized:

Theorem 1 (RGF Fault Effect on Reversible Circuit)

Consider a Reversible Circuit RC having RGF fault effect which replaces a reversible gate by r instances of the same gate. Then the

$$Test\ Set\ for\ RGF\ \,=\,\left\{\begin{array}{l} Test\ Set\ of\ SMGF; \hspace{1cm} if\ r\ is\ even\\ No\ Test\ Set\ Required; \hspace{0.6cm} if\ r\ is\ odd \end{array}\right. $$

Proof

According to the truth table shown in Table 1 for the circuits depicted in Fig. 1a and Fig. 1d, the output values in the presence of RGF (even number of gate instances i.e., for r being even) differs from the actual value for two inputs {0 0 0} and {1 0 1}. For the same inputs, the output values in the presence of SMGF also differs from ideal value. Hence {0 0 0} and {1 0 1} can detect both RGF and SMGF. When r is odd, the fault is redundant since the fault effect gets cancelled and hence there is no need of any test set to detect this redundant fault. □

2.3.4 Partial Missing Gate Fault (PMGF)

This fault models the defects caused in a reversible gate if any control is missing due to physical alignment or tuning of the gate pulses. In case of k-CNOT gate, PMGF reduces the gate to p-CNOT gate, with p<k; whereas in case of FREDKIN gate, the presence of PMGF converts the gate functionality from FREDKIN gate to SWAP gate. Let us consider a case where control of the TOFFOLI gate is missing as shown in Fig. 1e. For the applied input {0 1 1}, the output will be {1 1 0} instead of {0 1 1} due to the presence of PMGF. Hence the vector {0 1 1} detects this fault. The corresponding fault-free and faulty outputs for all other inputs are depicted in Table 1. It has been shown in [23] that the test vector which detects first order PMGF is sufficient to detect higher order PMGF as well. This statement is exclusively for k-CNOT gates as higher order PMGF occurs only in k-CNOT gate.

2.3.5 Multiple Missing Gate Fault (MMGF)

If a physical defect causes multiple gates or a subset of reversible gates to disappear from the circuit, then those type of faults are modeled as MMGF. Even this requires a detailed analysis to detect the fault from the functional analysis of the circuit. According to the authors in [24], a fault is said to be MMGF, if and only if two or more consecutive gates are missing. This is justified by the assumption that the gate operations implemented using laser is more likely to be disturbed for a period of time exceeding one gate operations. Hence always consecutive gates are affected rather than distinct gates here and there. Consider a case where two consecutive gates are missing as shown in Fig. 1f. Let the input applied be {0 1 0}. The fault-free output is {0 0 1} whereas, the faulty output is {0 1 0} which differs from expected output. Hence the vector {0 1 0} detects MMGF. The functional errors for other inputs are described in Table 1.

2.4 Prior Work on Fault Detection in Reversible Logic

2.4.1 Single and Multiple Stuck-at Faults

These are the classical fault models defined for reversible and quantum circuits. Testing can be performed either online or offline or with DFT. Online testing implies that the testing can be performed during the normal mode of operation of the circuit with hardware overhead. But offline testing needs a dedicated test mode without any test hardware overhead, whereas DFT refers to Testing with definite test input and with minimal additional test hardware [2]. The authors in [24] have proposed an ATPG with DFT for detecting all single stuck-at faults in a k-CNOT reversible circuit. But the methodology proposed by them does not consider any general n-bit reversible circuit. In [9], an ATPG with DFT methodology is proposed to detect all stuck-at faults. Here stuck-at faults are tested using minimal vectors with the gate replacement technique which increases the quantum cost of a testable circuit.

figure a

Various researchers have proposed online testing techniques to detect all single and multiple stuck-at faults which can detect the faults by designing new testable gates [10, 15, 20, 29, 30]. Among these techniques, the work in [20] has 100 % fault coverage with minimum gate overhead and all other techniques have partial fault coverage with high gate overhead. The offline techniques of testing will not add any overhead in terms of hardware complexity but they will have performance overhead since the circuit needs to be worked in test mode for offline testing.

2.4.2 Missing Gate Faults

Missing gate faults were proposed by the authors in [26] for the first time. They proposed a DFT methodology for detection of missing gate faults in k-CNOT gates. But this work does not deal with multiple missing gate faults. The complexity of the methodology developed depends on number of gates in the circuit and considers one gate missing at a time. Hence this method does not take multiple missing gate faults into consideration.

The authors in [6] have proposed an ATPG algorithm using linear programming model for detecting SMGF for circuits designed with k-CNOT gates. The authors in [25, 26] have proposed a technique of detecting SMGF in k-CNOT reversible circuit. An algorithm for CTS generation for all subset of missing gate faults was proposed in [11] for reversible circuits with k-CNOT gates. Also this technique has not dealt with stuck-at fault models. All the above mentioned methodologies were offline method of fault detection. The authors in [34] has proposed an online testing methodology which can detect missing gate faults when the circuit is operating in normal mode. But this can detect only odd number of repeated or missing gate faults. The offline testing techniques requires the circuit to operate in test mode for fault detection. The authors in [32] has proposed an offline testing methodology to test reversible circuits using Boolean Satisfiability (SAT) based approach which tests SMGF faults along with Single Missing Control Fault (SMCF) and Single Additional Control Fault (SACF). SMCF and SACF fault models are subsets of PMGF. The work in [35] has proposed a ping pong test to detect SMGF and multiple SMGF in a k-CNOT reversible circuit with 86 % fault coverage in average. In [19], the test set for SMGF is generated using a boolean difference method which has reported both test set and test vector set for detecting 100 % SMGF in a reversible circuit designed with k-CNOT gates.

So from the literature review, we can conclude that all the existing offline test methodologies have either concentrated on a particular fault type or adopted DFT for generating minimal test set and CTS. In this work, we target both stuck-at and super-set of missing gate fault detection in a reversible circuit designed with family of reversible gates and hence proposed algorithm does not restrict the testing of circuits designed with only k-CNOT gates.

3 Proposed Algorithms

3.1 Algorithm for Single and Multiple Stuck-at Fault Detection

In this algorithm, minimal CTS for single and multiple stuck-at faults are generated with Reversible Circuit (RC) as Input. The algorithm follows deterministic approach. We consider all the faults in each level of the circuit and generate minimal CTS and test sets which covers 100 % of faults.

3.2 Illustration/Analysis of Proposed SMSF Algorithm Using an Example

Let 3_17tc benchmark circuit is provided as input to the SMSF algorithm having number of lines n=3 and number of gates N=6. The complete flow of the algorithm to determine CTS for single and multiple Stuck-at faults is as represented in Fig. 2.

Fig. 2
figure 2

Demonstration of SMSF algorithm for 3_17tc benchmark circuit

Full size image

SaFarray obtained in Fig. 2 is an 2n×p matrix where p is the number of all possible Stuck-at Faults (including Sa-0 and Sa-1) for a given circuit. Figure 2 also shows all possible minimal test set to detect SMSF. Test vector is the n-bit binary equivalent of each element in the test set. Let us verify whether the test set [0 1 6] covers all the faults. From c we get

$$ {(l_{0}\ |\ l_{1}\ |\ l_{6} )\ = 1} $$
(d)

Table 2 shows the implementation of equation d. The last row indicates that this test set covers all possible SMSF faults in 3_17tc circuit.

Table 2 Implementation table of equation (d) of SMSF algorithm
Full size table

The same procedure is repeated for any circuit and applying appropriate equations required variables are determined. Figure 3 illustrates the SMSF test set generation for a Reversible circuit comprised of k-CNOT, FREDKIN and PERES gates.

Fig. 3
figure 3

Demonstration of SMSF algorithm for MBRC_2 circuit

Full size image

Lemma 1

Proposed Algorithm generates minimal CTS for a given Reversible circuit with 100 % fault coverage.

Proof

As explained in Section 3.2 and Table 2, for 3_17tc benchmark circuit 100 % fault coverage is achieved with number of test vectors = 3. Let us consider the mathematical induction method of proving this lemma. Hence it is sufficient to prove that 2 vectors are not enough to detect all possible SMSaF.Let the number of test vectors = 2. Total number of SMSF for 3_17tc benchmark circuit are 18. The fault coverage for all possible 2 vectors set is as shown in Table 3. Hence we have proved that 3 vectors are sufficient to detect all SMSaF which is minimal for 3_17tc benchmark circuit. In general, our proposed algorithm generated minimal CTS for all reversible circuits. □

Table 3 Fault coverage table for 3_17tc benchmark circuit with 2 test vectors
Full size table

3.3 Redundancy Detection and Removal

In the proposed algorithm, redundancy detection is performed by analyzing the entries in SaFarray, which contains the information on whether a particular vector detects all the fault or not. From the SaFarray, if any of the column contains all zeros then that particular fault is said to be redundant since the condition for fault detection is governed by equation c and hence to remove this redundant fault the algorithm ignores that column and processes further for test vector generation. Total number of redundant faults in the circuit is directly proportional to number of columns with all zero entries.

3.4 Algorithm for Partial and Complete Missing Gate Fault detection

Complete missing gate fault algorithm proposed in Algorithm 2 covers three different types of missing gate faults such as SMGF (Single Missing Gate Fault), MMGF (Multiple Missing Gate Fault) and RGF (Repeated Gate Fault) whereas Algorithm 3 generates minimal CTS for PMGF faults.

figure b
figure c

3.5 Illustration/Analysis of Proposed Complete Missing Gate Fault Algorithm with an Example

Let us consider 3_17tc benchmark circuit as an input circuit for the proposed algorithm to generate CTS to detect partial and complete missing gate faults. The algorithm flow remains the same as explained in Figs. 2 and 3 for SMSF algorithm. The same flow holds good for all proposed fault models but fault_det is evaluated using equation d for CMGF and equation h for PMGF. Hence Figs. 2 and 3 can be considered as a general flow diagram for all fault models but the final evaluation equation differs from one fault model to other.

4 Results and Discussions

The ATPG algorithms proposed in this work detects Single and Multiple stuck-at faults, SMGF, MMGF, PMGF and RGF exclusively or combining different fault models. The test sets are generated using exact approach and is found to be minimal compared to existing state-of-the-art work. The proposed SMSF has the computation complexity of \(O([2^{n}(n+N)log_{2}(n)+{\sum }^{n}_{r=1} {~~}^{2^{n}}C_{r}])\) and SMGF, RGF and PMGF has the complexity of \(O([2^{n}(N+1)log_{2}(n)+{\sum }^{n}_{r=1} {~~}^{2^{n}}C_{r}])\). The complexity of an exact algorithm is exponential - polynomial and in our work, the exponential complexity is due to the generation of fault table and searching of minimal test set with CTS from this fault table. Since the size of fault table is 2n⋅L the search also has complexity of O(2n).

4.1 Single and Multiple Stuck-at Faults

Couple of attempts are made in the literature to generate test sets for stuck-at-fault models using DFT approach. In all these approaches there is an extra overhead due to adaptation of DFT method. In this work, there is no overhead as the design is completely exact and is found to be more optimal approach satisfying the requirements. The comparison of the proposed work with the existing works in [8] and [3] is described in Table 4. It is found that though the numbers of test vectors are one or two more than those proposed in [8], there is no extra overhead in terms of gate cost. Hence there is no area overhead in proposed work. Similarly, the required number of test vector in [3] is 3 for few benchmark circuits with an additional gate cost due to incorporation of DFT approach. Hence the proposed method generates minimal test vectors to detect all single and multiple stuck-at faults with no extra overhead. The proposed algorithm is applied to all the benchmark circuits and the results are tabulates along with the CPU simulation time as shown in Table 12.

Table 4 Comparison of CTS for Single and Multiple stuck-at faults in Reversible circuits containing k-CNOT gates
Full size table

4.2 Missing and Repeated Gate Faults

There are various variants of missing gate fault model. A complete gate or any control line or two or more consecutive gates may disappear to cause fault effect on the circuit. Contrary to the missing gate, there may be gates which are repeated two or more times causing functional errors in the circuit. The test vector to detect all these variants of fault types is not found in the literature. This work is supposed to be first in the literature to generate test vectors for all these types of faults.

The authors in [7] have used Greedy and Branch & Bound algorithm to generate test vectors to detect SMGF with some additional gates due to DFT method. Our proposed algorithm also generates the test sets whose cardinality matches with those proposed in [7] with an advantage of zero overhead. The results are tabulated and compared in Table 5.

Table 5 Comparison of CTS for single missing gate fault for benchmark circuits
Full size table

The authors in [23] have proposed an algorithm which do not uses any DFT approach and detects SMGF, MMGF and PMGF. The test set cardinality for the proposed SMGF algorithm also matches with the one proposed in [23], but for few benchmark circuits the proposed algorithm gives better test sets. The comparison of CTS for SMGF are as described in Table 5. The proposed MMGF and PMGF algorithms are found to give minimal test set when compared to the results in [23]. For 5m o d5t c benchmark circuit, the number of test vectors needed to test PMGF is reduced by 80 % compared to [23].

The work in [19] targets for determining test set for SMGF. Table 6 gives the comparison of our work with [19]. On an average, test set cardinality is reduced by 60 %. Table 7 shows the comparison of the proposed work with [35]. The test set proposed in [35] has variations in fault coverage for different benchmark circuits. Compared to [35] the test vectors required to test a given reversible circuit is reduced by an average of 40 % with 100 % fault coverage.

Table 6 Comparison of CTS for Single Missing Gate Fault with [19]
Full size table
Table 7 Comparison of CTS for single missing gate fault with [35]
Full size table

The comparison of the proposed work with the existing work is tabulated in Table 8 for MMGF and for PMGF. The number of test vectors needed to detect the combined effect of SMGF, MMGF and PMGF are compared with the work done in [23] and is tabulated in Table 8. It is found that, for 5o f5d1 benchmark circuit, there is an improvement of 45.45 % wrt [23] in number of test vectors needed to detect SMGF, MMGF and PMGF. The authors in [23] does not discusses on repeated gate faults and stuck-at faults.

Table 8 Comparison of CTS for SMGF,MMGF and PMGF for benchmark circuits
Full size table

Not much work have been found in the literature which discusses all types of fault models which takes combinations of all fault types. The authors in [26] discusses on test vector generation for the combined fault model of SMGF and PMGF. The proposed algorithm for combined effect of SMGF and PMGF is compared with [26] and tabulated as depicted in Table 8. The proposed algorithm generates minimal test sets compared to the counterpart with an improvement of 66.66 % for x o r5d1 and 71.42 % for 5m o d5t c benchmark circuit. Though for one or two of the benchmark circuits the number of test vector are slightly more compared to [26], for most of the cases, the proposed algorithm is found to be optimal.

The author in [11] discusses on the test vector generation for combined effect of SMGF, MMGF and RGF whose results are compared with the proposed work as depicted in Table 9. It is found that the test set cardinality is improved by 50 % and 66.66 % for h w b4t c and 5m o d5t c benchmark circuits respectively when compared to [11]. Other fault models are not discussed and also it is applicable only for circuits containing k-CNOT gates.

Table 9 Comparison of CTS for SMGF, MMGF and RGF for benchmark Circuits
Full size table

The authors in [32] has defined variants of missing control faults as a Single Missing Control Fault (SMCF), Single Additional Control Fault (SACF) and Single Missing Gate Fault (SMGF). In the proposed work, both SMCF and SACF are subsets of PMGF and are detected using Algorithm 3. SMGF faults are detected using Algorithm 2. It is evident from Table 10 that the number of test vectors are reduced by 98.24 % for PMGF and 96.875 % for SMGF for S y m9_148 benchmark circuit. For some of the circuits in [32], there are some un-testable faults present which is not the case in the proposed work which detects all the faults present in the circuit with minimal test set cardinality.

Table 10 Comparison of CTS for SMGF, MMGF and PMGF for benchmark circuits
Full size table

The main objective of this work is to test circuits containing other reversible gates such as Fredkin, Peres and k-CNOT. Some of the reversible circuits designed using all these gates are considered and tested for all kinds of fault models. The results obtained are tabulated in Table 11. The reversible circuits for validating the proposed algorithms are as shown in Fig. 4.

Table 11 CTS with simulation time for reversible circuits designed with k-CNOT, Fredkin, and Peres gates
Full size table
Fig. 4
figure 4

Reversible Circuits designed using standard gates for validating the algorithm

Full size image

The CTS for most of the benchmark circuits along with the simulation time for Single/Multiple Stuck-at Fault, SMGF, MMGF, PMGF and their combinations are tabulated in Table 12. # Test Vectors indicates the number of minimal test vectors needed to test a particular fault and #Test Set indicates CTS i.e., all possible minimal test vector sets. #Lines and #Gates indicate number of lines and gates present in a circuit under test.

Table 12 CTS and minimal test set with Simulation Time for the benchmark Circuits
Full size table

In this work, we have proposed an ATPG algorithm using an exact approach to generate minimal test vectors with CTS for a given reversible circuit consisting of family of reversible gates. Based on these proposed algorithms, a testing tool is developed which can take inputs either in the form of circuit image (.bmp, .jpg, .png, .fig) or in .tfc or .real format. This tool is capable of generating test vectors for different fault models such as Single and Multiple stuck-at fault, Missing gate fault model and its variants. The tool generates the all possible test vectors needed to test a particular fault in a circuit indicating the number of lines and number of gates in the circuit along with CPU time required for processing. There is an option to write the results in to a text file for future reference. The tool also display the circuit under test at the left pane. The snapshots of the tool for h a m3t c benchmark circuit as input is as shown in Fig. 5.

Fig. 5
figure 5

Snapshot of Testing Tool for h a m3t c as input circuit

Full size image

5 Conclusion and Future Work

In this paper, we have developed a generalized platform to generate CTS for various fault models in a reversible circuit comprising of family of reversible gates. This is the first attempt in literature which combines all types of fault models and for circuits designed using family of reversible gates. So far in the existing state-of-the-art approaches, only k-CNOT gate is taken into consideration and any one or two fault models are combined for offline testing. In this work, we have also considered other standard reversible gates such as FREDKIN and PERES gates along with k-CNOT gates. All variants of stuck-at faults and missing Gate Faults are tested either exclusively or by grouping. A testing tool is developed based on the proposed ATPG algorithms. The tool is developed with flexibility in providing inputs and detailed analysis in output. The proposed algorithm is implemented in MATLAB 2011a on an Intel Core i7−3612Q M processor with 2.10G H z processing speed. The CPU simulation time quoted in this work is strictly based on the processor specifications mentioned. The algorithm can be used independent of the implementation technology. Because of the exponential complexity of algorithm, for some benchmark circuits that have large gate count and lines, we are not able to use our tool successfully. In our future work we will report some heuristic approach for reducing the time complexity of test generation based on a divide-and-conquer strategy using circuit partitioning. Hence our future work includes reducing the time complexity of test generation by using Heuristic approaches and to work on circuit partitioning methods for large circuits which will divide the exponential complexity of the algorithm. Our future work also include detection of other quantum circuit fault models.