Detection and Identification of Gate Faults in Reversible Circuit

Abstract

In recent time, efficient implementation of reversible logic circuits has come out as an important research area before the design industry. With the advancement in reversible logic synthesis, developing mechanism for identification of faults finds importance. Though there exist well-known testing techniques, but developing improved testing algorithms is the need of the hour. Aiming to develop efficient testing technique, here in this work, we show an improved testing scheme based on Boolean logic function. Two different testing approaches are presented here, where in the first work, by using Boolean difference method SMGFs in reversible circuit are tracked successfully, where a test vector generator is derived to find the faults. In the second work, a Reed–Muller (RM) form based testing approach is developed that not only detects the faults but also locates the exact position of the faulty area. A limitation for the second testing scheme is that it can only be employed over a specific type of reversible circuit known as Exclusive-Or Sum-Of-Product (ESOP) design. Both the testing techniques have been executed over different benchmark suites and a comparative study with state-of-the-art testing approaches have been included in the work.

1 Introduction

Heat dissipation is considered as the essential concern in modern day’s VLSI circuit. As per Launder’s principles [1], loss of information generates KTlog₂joule amount of heat, where k is Boltzmann constant and T is absolute temperature. Hence, alternative technology is required so that heat generation can be minimized in the circuit. Bennet [2] claimed that dissipation of energy can be made zero only when the circuit is constructed with reversible gates. Therefore, reversible logic design is considered as the prerequisite needed to minimize heat dissipation during logic computation. On the other side, as the quantum circuit [3] follows the principle of reversibility, the implementation of quantum functionality using reversible circuit is possible. Reversible circuit not only has the dominance in the field of quantum circuit design, but it too has applications in adiabatic computing [4, 5], Cryptography and Optical Computing. In the last couple of years, several progresses have been made on efficient design strategies of reversible circuit.

Synthesis algorithms have been developed for making the designs of reversible circuit generic. But, not only designing the cost-efficient circuits get the high importance but simultaneously developing testing algorithms [6–11] for checking the correctness of such designs find popularity. In recent time, some promising works on efficient testing strategies have been developed where improved algorithms are formulated to make the testing process easier.

Here, in this work, we show two different approaches to find faults in reversible circuit. In the first work, a Boolean difference-based testing technique is developed, where a Boolean generator is formulated to produce test vectors and then the faults are tracked. This approach is very generic as it can be employed over any type of circuits. The second testing scheme is not very generic like the first one as it can only operate over ESOP-based designs. In this testing scheme, the functional power of Reed–Muller expression is used to find and locate the faults.

The remaining portion of the article is formulated as follows: preliminaries associated with reversible testing are stated in Sect. 2. Section 3 summarizes previous research works on reversible testing. The developed methodologies are presented in Sect. 4. The experimental data of our work are summarized in Sect. 5. Finally, the chapter is concluded in Sect. 6.

2 Preliminaries

2.1 Reversible Circuits and Gates

Definition 1

A circuit C_nf over a set of circuit lines L = {c₁, c₂, …, c_n} is said to be reversible if it satisfies the following three criteria:

• (i). input (m) lines are equal with the output (n) lines

• (ii). if the circuit is fan-out free

• (iii). circuit consists of reversible gates only.

Definition 2

A reversible gate G can be described as G(C; T), where parameters C, T represents the control and target connection inputs. In that gate G, the control input set C may contain an empty value but the set T must have a minimum of one target line in such that C∩T = Φ.

In classical circuit different logic gates are used to implement a circuit, similarly there are well-known reversible gates like Toffoli [12], Fredkin [13], Feynman [14] that are used to construct reversible circuits. Some examples of reversible gates are depicted in Fig. 1.

Fig. 1

a 2-control Toffoli gate, b CNOT gate, c NOT gate

2.2 ESOP-Based Design

A reversible circuit may have different designs and such variations in design depend on the type of algorithm deployed or heuristic employed. Among the several design models, due to the scalable feature property, ESOP (Exclusive Sum-Of-Products) [15]-based representation has been found as one of the widely used design model for reversible circuit. Now in the following, we introduce this special type of circuit.

ESOP can be represented in the form of Sum-Of-Products (SOP) form except that the SOP product terms which are separated by ‘+’ operator, it is separated by “⨁” operator. To express any n-input, m-output reversible function in ESOP representation, it requires (n + m) numbers of input lines in the circuit, where n represents the control set and the rest m lines operate as functional output lines.

Cube list a special data structure from which the ESOP designs are formed. Such cube list contains the detail gate specification and control structure for the ESOP circuit. Each cube in the cube list denotes a gate in the design. For an ease of understanding, cube list and its corresponding ESOP expression are given in Fig. 2a and b, where it can be seen that each of the cubes from the list has been mapped to an equivalent gate and finally a complete design is formed Fig. 2b.

Fig. 2

a Cubelist for $f\left( {a_{1} ,a_{2} ,a_{3} ,a_{4} } \right) = a_{2} a_{3} \oplus a_{4} \oplus a_{1} \oplus \bar{a}_{1} a_{2} a_{4} \oplus \bar{a}_{1} a_{2} a_{3} \bar{a}_{4}$, b ESOP expression of Fig. 2a

2.3 Reed–Muller Form

For efficient design and testing of reversible circuit, the concept of Boolean algebra operator is used widely. The modulo-2 arithmetic is applied and any Boolean function can be realized using this algebra. For implementation purpose, Reed–Muller expansion can be represented using sum-of-products expression of modulo-2 arithmetic. Reversible circuit based on module-2 expansion can be realized using only exclusive OR (EXOR) gates. For any Boolean function $f(x_{1} x_{2} \,\ldots\, x_{n} )$, it is expressed in the form of Reed–Muller expansion [16, 17].

PPRM: The positive polarity based Reed–Muller (PPRM) expression can be realized in the form of an EXOR canonical sum-of-products expression in which each variable represents a positive polarity (un-complimented). A PPRM expression of n variable can be expressed as

${\text{f}}({\text{x}}_{1} {\text{x}}_{2} \,\ldots\, {\text{x}}_{\text{n}} ) = {\text{a}}_{0} \oplus {\text{a}}_{1} {\text{x}}_{1} \oplus {\text{a}}_{2} {\text{x}}_{2} \oplus {\text{a}}_{3} {\text{x}}_{1} {\text{x}}_{2} \oplus \,\ldots\, \oplus {\text{a}}_{{2^{\text{n}} - 1}} {\text{x}}_{1} {\text{x}}_{2} \,\ldots\, {\text{x}}_{\text{n}}$, where ${\text{a}}_{\text{i}} \in \{ 0,1\}$. The variable ${\text{a}}_{\text{i}}$ in the above expression represents coefficient vector, where ${\text{x}}_{\text{i}}$ denotes input variables. If the coefficient becomes zero, then the corresponding product term is not present in the PPRM expression otherwise the product term is included in the given expression.

FPRM: In fixed polarity Reed–Muller (FPRM) expression, the n variable function can be represented as

${\text{f}}({\text{x}}_{1} {\text{x}}_{2} \,\ldots\, {\text{x}}_{\text{n}} ) = {\text{a}}_{0} \oplus {\text{a}}_{1} {\dot{\text{x}}}_{1} \oplus {\text{a}}_{2} {\dot{\text{x}}}_{2} \oplus {\text{a}}_{3} {\dot{\text{x}}}_{1} {\dot{\text{x}}}_{2} \oplus \,\ldots\, \oplus {\text{a}}_{{2^{\text{n}} - 1}} {\dot{\text{x}}}_{1} {\dot{\text{x}}}_{2} \,\ldots\, {\dot{\text{x}}}_{\text{n}}$ where ${\text{a}}_{\text{i}} \in \{ 0,1\}$ and ${\dot{\text{x}}} \in \{ {\text{x}},{\bar{\text{x}}}\}$, where x denoted un-complemented literals and ${\bar{\text{x}}}$ denotes complemented literals.

GRM/MPRM: The Mixed polarity Reed–Muller (MPRM) expression can be considered as the generalization of FPRM expression in which there is hardly any limitation in the polarity of each variable. The Boolean function having n variable can be represented by a number of $2^{{{\text{n}}2^{{{\text{n}} - 1}} }}$ GRM form. The MPRM expression for n variable function is represented as

${\text{f}}({\text{x}}_{1} {\text{x}}_{2} \,\ldots\, {\text{x}}_{\text{n}} ) = {\text{a}}_{0} \oplus {\text{a}}_{1} {\dot{\text{x}}}_{1} \oplus {\text{a}}_{2} {\dot{\text{x}}}_{2} \oplus {\text{a}}_{3} {\dot{\text{x}}}_{1} {\dot{\text{x}}}_{2} \oplus \,\ldots\, \oplus {\text{a}}_{{2^{\text{n}} - 1}} {\dot{\text{x}}}_{1} {\dot{\text{x}}}_{2} \,\ldots\, {\dot{\text{x}}}_{\text{n}}$ where ${\text{a}}_{\text{i}} \in \{ 0,1\}$ and ${\dot{\text{x}}} \in \{ {\text{x}},{\bar{\text{x}}}\}$.

The association among various Reed–Muller configurations can be represented as PPRM $\subset$ FPRM $\subset$ GRM/MPRM.

2.4 Different Fault Models and Their Properties

Faults in a circuit may originate due to several reasons [18–20]. Depending on the type of errors, there are four types of faults such as—single missing gate fault (SMGF), repeated gate fault (RGF), partial missing gate fault (PMGF) and multiple missing gate fault (MMGF).

Definition 3

Complete disappearance of a gate from a given circuit results in a single missing gate fault.

The Fig. 3a shows an SMGF in a benchmark circuit ham3\design#, where the faulty area has been marked with a dotted box. In the dotted region, the first 2-CNOT gates are missing. A SMGF fault can be detected by providing value 1 to all the control line set of the gate and either 0 or 1 at the target node of corresponding gate.

Fig. 3

a SMGF fault in circuitham3\design#, b RGF in ham3\design#1 circuit, c PMGF in circuitham3\design#1, d MMGF in ham3#design#1

Definition 4

A fault can be considered as repeated gate fault if the same gate consecutively reappears in the design and may change the functionality of the circuit.

In Fig. 3b, the RGF is shown in the first gate of the ham3\design#1. It can be ascertained that if a gate reappears even number of times then its effect becomes equivalent to an SMGF fault while odd occurrence makes the RGF fault as redundant indicating the circuit functionality remains unchanged.

Definition 5

Disappearance of control connection input of a gate results in a fault in a circuit known as partial missing gate fault (PMGF).

In Fig. 3c, a PMGF fault is shown in the first gate of the circuit. It is considered that a PMGF fault can only be uncovered by applying value 0 to at the missing control inputs and a value 1 is set for other control lines.

Definition 6

Missing of two or more successive gates from the circuit generates a fault known as multiple missing gate fault (MMGF).

Consider the circuit shown in Fig. 3d, where the first two gates enclosed within the dotted box are missing.

Still so far we have seen the fundamentals related to reversible circuit and its associated fault models. Now, here we are discussing some of the works in testing and highlighting their contributions.

3 Related Works and Contributions

An efficient approach of stuck-at-fault detection by the adaptive tree-based technique is proposed in [6]. Here, in this technique at first the fault in half of the circuit is detected and then by applying the reversible property, a mirror image of the remaining part of the circuit is developed to detect faults in the remaining part of the circuit.

Furthermore, a generalized approach of “stuck-at” fault detection for all k-CNOT based circuit has been reported in [7], where a universal test of size 3 has been used for the fault detection.

Taking one step more, a novel technique for fault detection is shown in [8], where an (n × n) reversible circuit constructed with k-CNOT gates is tested for possible faults. In this method, a testable design has been developed by copying gates along with an additional line. Though some overhead is incurred to transform the original circuit into the testable form, but the modified testable design becomes very sufficient and easy to detect all existing fault models in the given circuit.

To make the faults detection easier, not only fault specific test vectors have been generated but the way of making simpler testable designs also have been explored and such a work is reported in [9], where extra inputs and additional k-CNOT gates are added in the design to make the design testing friendly. This modified testing design methodology determines a universal test set of size (n + 2) and thereby identifies the said faults in the given circuit.

Instead of applying huge number of test vectors in fault detection and also to reduce the design complexity, testing of SMGFs and RGFs and MMGFs in reversible circuit with minimum number of test vectors is presented in [10].

4 Proposed Testing Methods

Here we state both the testing schemes with examples. The first testing scheme is based on Boolean difference method, whereas the second one relies on Reed–Muller expansion.

4.1 Boolean-Based Testing Method1

Here we state the technique to determine the existence of SMGF in a circuit. The proposed approach is divided into three phases. At first, Boolean difference of the circuit is computed for each of the missing gate. In the second phase, a Boolean generator for the entire circuit is constructed and in the third phase, test vectors are constructed from the Boolean generator which finally checks the presence of SMGF in the circuit. All three phases are stated next in detail.

4.1.1 Computation of the Boolean Difference for Missing Gate Faults

Let us assume a reversible circuit having n number of input lines and N number of gates.

Definition 7

The Boolean expression generated at the jth line of a fault-free circuit is known as the OriginalExpression_j, where (0 ≤ j ≤ n − 1). For any given reversible circuit with n inputs can be represented by OriginalExpression₀, OriginalExpression₁, OriginalExpression_n−1.

Definition 8

For a faulty circuit, the Boolean expression produced at the jth line as a result of the gate missing from the ith level of circuit can be represented as the FaultyExpression_i,j, where (0 ≤ i ≤ N − 1), (0 ≤ j ≤ n − 1).

For any reversible circuit with n lines can be expressed as FaultyExpression_i,0, FaultyExpression_i,1, … , FaultyExpression_i,n−1 for the detected fault occurring at ith gate. The computed Boolean expression of the jth line in the faulty circuit may not be identical to the one generated at the jth line of the corresponding fault-free circuit.

Boolean difference method [21] is basically used to determine the complete test set for detecting stuck-at faults. We have employed the same it in reversible circuit for identifying SMGF faults.

Definition 9

The Boolean difference $\left( {\frac{{{\text{dF}}_{\text{j}} }}{{{\text{dG}}_{\text{i}} }}} \right)$ estimated at the jth line for the gate missing from the ith level can be expressed as $\frac{{{\text{dF}}_{\text{j}} }}{{{\text{dG}}_{\text{i}} }} = {\text{F}}_{\text{j}}^{\text{o}} \oplus {\text{F}}_{\text{j}}^{\text{i}}$, where ${\text{F}}_{\text{j}}^{\text{o}}$ is the OriginalExpression_j, ${\text{F}}_{\text{j}}^{\text{i}}$ is the FaultyExpression_i,j, (0 ≤ i ≤ N − 1) and (0 ≤ j ≤ n − 1).

Definition 10

The Boolean difference resulted due to removal of gate located at ith level is represented as $\frac{\text{dF}}{{{\text{dG}}_{\text{i}} }}$ which can be determined as follows:

$$ \frac{\text{dF}}{{{\text{dG}}_{\text{i}} }} = \sum \frac{{{\text{dF}}_{\text{j}} }}{{{\text{dG}}_{\text{i}} }} = \left( {\frac{{{\text{dF}}_{0} }}{{{\text{dG}}_{\text{i}} }}} \right) + \left( {\frac{{{\text{dF}}_{1} }}{{{\text{dG}}_{\text{i}} }}} \right) + \cdots + \left( {\frac{{{\text{dF}}_{{{\text{n}} - 1}} }}{{{\text{dG}}_{\text{i}} }}} \right),\left( {0 \le {\text{i}} \le {\text{N}} - 1} \right),\left( {0 \le {\text{j}} \le {\text{n}} - 1} \right) $$

In this way, at first the Boolean difference for the missing of each gate in the circuit is computed and then the Boolean difference of the circuit is constructed using the Boolean difference for each gate of the given circuit.

Definition 11

The Boolean generator can be defined as the Boolean expression needed for the test set construction so as to identify all the possible SMGFs in the circuit.

Lemma 1

For a reversible circuit of n number input lines and N number of gates, then computation of individual Boolean difference $\left( {\frac{\text{dF}}{{{\text{dG}}_{\text{i}} }}} \right)$ enables to identify SMGF at the ith level.

Proof

For the reversible circuit with n lines and N gates, the Boolean difference $\left( {\frac{\text{dF}}{{{\text{dG}}_{\text{i}} }}} \right)$ for detecting the gate missing at the ith level is computed as:

$$ \frac{\text{dF}}{{{\text{dG}}_{\text{i}} }} = \sum \frac{{{\text{dF}}_{\text{j}} }}{{{\text{dG}}_{\text{i}} }},\left( {0 \le {\text{i}} \le {\text{N}}{-}1} \right),\left( {0 \le {\text{j}} \le {\text{n}} - 1} \right) $$

(1)

Σ denotes the OR operation and

$$ \frac{{{\text{dF}}_{\text{j}} }}{{{\text{dG}}_{\text{i}} }} = {\text{F}}_{\text{j}}^{\text{o}} \oplus {\text{F}}_{\text{j}}^{\text{i}} ,\left( {0 \le {\text{i}} \le {\text{N}} - 1} \right),\left( {0 \le {\text{j}} \le {\text{n}} - 1} \right) $$

(2)

From the expression given at Eq. (1), it can be noticed that the possible values for $\frac{\text{dF}}{{{\text{dG}}_{\text{i}} }}$ can be either 0 or some other Boolean representation. Furthermore, it can be determined that the estimated result of $\frac{\text{dF}}{{{\text{dG}}_{\text{i}} }}$ becomes zero provided each of the terms $\frac{{{\text{dF}}_{\text{j}} }}{{{\text{dG}}_{\text{i}} }}$ evaluates to “0” as logical OR is being performed between any two successive terms of $\frac{\text{dF}}{{{\text{dG}}_{\text{i}} }}$.

By analyzing the expression given in Eq. (2), it can be observed that the term $\frac{{{\text{dF}}_{\text{j}} }}{{{\text{dG}}_{\text{i}} }}$ returns the value “0”, if both ${\text{F}}_{\text{j}}^{\text{o}}$ and ${\text{F}}_{\text{j}}^{\text{i}}$ are becomes identical only if the circuit is fault free. This in turns suggests that, if the expression $\frac{\text{dF}}{{{\text{dG}}_{\text{i}} }}$ returns 0 then the circuit is said to be fault free.

For any SMGF in the circuit, it is obvious that the output expression obtained at any of the n input lines varies with the one derived for fault-free circuit. It means that at least a single line say j must be present for which the terms ${\text{F}}_{\text{j}}^{\text{o}}$ and ${\text{F}}_{\text{j}}^{\text{i}}$ turns out to be different due to existence of fault. It implies that $\frac{\text{dF}}{{{\text{dG}}_{\text{i}} }}$ cannot be equal to 0 in the faulty reversible circuit as logical OR is implemented between the consecutive terms $\frac{\text{dF}}{{{\text{dG}}_{\text{i}} }}$ and $\frac{{{\text{dF}}_{\text{j}} }}{{{\text{dG}}_{\text{i}} }}$.

4.1.2 Implementation of Boolean Generator for Detection of Single Missing Gate Fault

In the proposed method, the Boolean generator of the given circuit is estimated using the function ${\text{B}}_{\text{Gen }} = \frac{\text{dF}}{{{\text{dG}}_{0} }} \wedge \frac{\text{dF}}{{{\text{dG}}_{1} }} \wedge \,\ldots\, \wedge \frac{\text{dF}}{{{\text{dG}}_{{{\text{N}} - 1}} }}$, where ˄ represents the logical AND operation and N represents number of gates in the circuit. For BGen ≠ 0, the BGen is minimized to construct the Boolean generator of the circuit. For BGen = 0, the expressions ${\text{B}}_{\text{Gen}}^{1}$ and ${\text{B}}_{\text{Gen}}^{2}$ need to be computed to determine the Boolean generator of the given circuit. The computation method of the expressions ${\text{B}}_{\text{Gen}}^{1}$ and ${\text{B}}_{\text{Gen}}^{2}$ are as follows:

Let S = (so, s1, … , sN − 1) be the set of all $\frac{\text{dF}}{{{\text{dG}}_{\text{i}} }}$, where si = $\frac{\text{dF}}{{{\text{dG}}_{\text{i}} }}$ for (0 ≤ i ≤ N − 1). Let ${\text{S}}1 \subseteq {\text{S}}$ contains maximum number of si’s such that ${\text{B}}_{\text{Gen}}^{1} = {\text{Si}}1\Lambda {\text{Si}}2\Lambda \cdots\Lambda {\text{Sik}} \ne 0$, where ${\text{Sik}} \in {\text{S}}1$. ${\text{B}}_{\text{Gen}}^{2}$ are remaining si’s of S. For each of the ${\text{B}}_{\text{Gen}}^{2}$, the ${\text{B}}_{\text{Gen}}^{1} = 0$.

After the formation ${\text{B}}_{\text{Gen}}^{1}$ and ${\text{B}}_{\text{Gen}}^{2}$, the expression ${\text{B}}_{\text{Gen}}^{1}$ is upgraded to compute the final form of the Boolean generator as follows:

• (i) If any term of $B_{Gen}^{2}$ completely matches or is subset of any term of $B_{Gen}^{1}$, no need to upgrade the $B_{Gen}^{1}$, else compare different terms of the $B_{Gen}^{1}$ with each term of the $B_{Gen}^{2}$ and upgrade the $B_{Gen}^{1}$ as: $B_{Gen}^{1} = B_{Gen}^{1} +$ highest matching term [i], i = 0 to (number of highest matching term – 1). Repeat the same procedure between upgraded $B_{Gen}^{1}$ and other available $B_{Gen}^{2}$, if exist.

• (ii) The minimized form of $B_{Gen}^{1}$ is the Boolean generator of the circuit.

4.1.3 Test Vector Construction from the Boolean Generator of the Circuit

The minterms and their corresponding decimal values for the generator are calculated and the collection of those decimal values is the test set of the circuit that will be used for the detection of SMGF.

Example 1

The ham3tc benchmark circuit of Fig. 4a is considered here. The circuits consisting of three lines (n = 3) and five gates (N = 5).

Fig. 4

a Fault free ham3tc circuit, b testable circuit for SMGF (Faulty ham3tc circuit where dotted box indicates missing of that gate)

As per the first phase of the proposed technique, output expressions OriginalExpression₀, OriginalExpression₁ and OriginalExpression₂ are computed from the fault-free circuit of Fig. 4a.

The output expression generated for each circuit line is OriginalExpression₀ = (a ⊕ b · c), OriginalExpression₁ = ((b ⊕ c) ⊕ ((c ⊕ (b ⊕ c)) ⊕ (a ⊕ b · c))), OriginalExpression₂ = ((c ⊕ (b ⊕ c)) ⊕ (a ⊕ b · c)).

Now, let us assume that the gate G₀ at the level₀ is removed from the circuit. Hence, the circuit ham3tc becomes a faulty circuit (as shown in Fig. 4b) and its output expressions are FaultyExpression0,0, FaultyExpression0,1, FaultyExpression0,2.

Each expression of the faulty circuit are FaultyExpression_0,0 = (a), FaultyExpression_0,1 = ((b ⊕ c) ⊕ ((c ⊕ (b ⊕ c) ⊕ (a))), FaultyExpression0_,2 = ((c ⊕ (b ⊕ c)) ⊕ (a)).

After finding out fault free expression of each line and the faulty expression of each line of the circuit, the Eqs. 1 and 2 as discussed earlier are used to compute the Boolean difference of the circuit. The Boolean difference of the circuit for the missing of the gate G0 is as $\frac{\text{dF}}{{{\text{dG}}_{0} }} = \left( {\frac{{{\text{dF}}_{0} }}{{{\text{dG}}_{0} }}} \right) + \left( {\frac{{{\text{dF}}_{1} }}{{{\text{dG}}_{0} }}} \right) + \left( {\frac{{{\text{dF}}_{2} }}{{{\text{dG}}_{0} }}} \right)$, $\frac{dF}{{dG_{0} }}$ = (OriginaIExpression0 ⊕ FaultyExpression0,0) + (OriginalExpression1 ⊕ FaultyExpression_0,1) + (OriginalExpression2 ⊕ FaultyExpression0,2) $= (({\text{a}} \oplus {\text{b}} \cdot {\text{c}}) \oplus {\text{a}}) + ((({\text{b}} \oplus {\text{c}}) \oplus (({\text{c}} \oplus ({\text{b}} \oplus {\text{c}}))$ $\oplus ({\text{a}} \oplus {\text{b}} \cdot {\text{c}}))) \oplus (({\text{b}} \oplus {\text{c}}) \oplus (({\text{c}} \oplus ({\text{b}} \oplus {\text{c}}) \oplus \left( {\text{a}} \right)))))$ $+ ((({\text{c}} \oplus ({\text{b}} \oplus {\text{c}})) \oplus ({\text{a}} \oplus {\text{b}} \cdot {\text{c}}))$ $\oplus (({\text{c}} \oplus ({\text{b}} \oplus {\text{c}})) \oplus \left( {\text{a}} \right))) = {\text{bc}}$

Similarly, each gate is removed at a time and the Boolean difference of the given circuit for the remaining gates is computed.

So, $\frac{dF}{{dG_{1} }} = c$, $\frac{dF}{{dG_{2} }} = b\bar{c} + \bar{b}c$, $\frac{dF}{{dG_{3} }} = \bar{a}bc + {\text{a}}\bar{b} + a\bar{c}$, $\frac{dF}{{dG_{4} }} = \bar{a}b\bar{c} + a\bar{b} + ac$.

Now as per the second phase of the proposed testing method, the Boolean generator of the circuit is computed by the statement B_Gen, where $B_{Gen} = (\frac{dF}{{dG_{0} }})AND(\frac{dF}{{dG_{1} }})AND(\frac{dF}{{dG_{2} }})$ $AND(\frac{dF}{{dG_{3} }})AND(\frac{dF}{{dG_{4} }}) = (bc)AND(c)$ $AND(b\bar{c} + \bar{b}c)AND(\bar{a}bc + {\text{a}}\bar{b} + a\bar{c})$ $AND(\bar{a}b\bar{c} + ab + ac) = 0$. As B_Gen is 0, we have to find out the $B_{Gen}^{1}$ and $B_{Gen}^{2}$ to calculate the final form of the Boolean generator.

For this example, as gate count is N = 5, we need 5 iterations to generate the resultant Boolean generator of the circuit.

First Iteration: Let us assume $B_{Gen}^{1} = \frac{dF}{{dG_{0} }} = bc$.

Second Iteration: Here $B_{Gen}^{1}$ is upgraded as follows: $B_{Gen}^{1} = B_{Gen}^{1} AND(\frac{dF}{{dG_{1} }}) = (bc)AND(c) = bc$.

Third Iteration: Similarly, $B_{Gen}^{1} = B_{Gen}^{1} AND(\frac{dF}{{dG_{2} }}) = (bc)AND(b\bar{c} + \bar{b}c) = 0$. That means the term $(b\bar{c} + \bar{b}c)$ converts the term $B_{Gen}^{1}$ to 0 and therefore, the $B_{Gen}^{2} (0)$ is computed and $B_{Gen}^{1}$ will not be upgraded. Now, $B_{Gen}^{2} (0) = (b\bar{c} + \bar{b}c)$.

Fourth Iteration: $B_{Gen}^{1} = B_{Gen}^{1} AND(\frac{dF}{{dG_{3} }}) = (bc)AND(\bar{a}bc + {\text{a}}\bar{b} + a\bar{c}) = \bar{a}bc$.

Fifth Iteration: $B_{Gen}^{1} = B_{Gen}^{1} AND(\frac{dF}{{dG_{4} }}) = (\bar{a}bc)AND(\bar{a}b\bar{c} + a\bar{b} + ac) = 0$. Once again as per the third iteration, the $B_{Gen}^{2}$ (1) is computed and the function $B_{Gen}^{1}$ will not be modified. Now, $B_{Gen}^{2} (1) = (\bar{a}b\bar{c} + a\bar{b} + ac)$.

Now, we need to compare $B_{Gen}^{1}$ with $B_{Gen}^{2}$ (0) and $B_{Gen}^{2}$ (1) once again to upgrade the $B_{Gen}^{1} .$ At First, the expression $B_{Gen}^{1} (\bar{a}bc)$ is compared with both the terms of $B_{Gen}^{2}$ (0). The term $(\bar{a}bc)$ of $B_{Gen}^{1}$ contains a single literal matching with both the terms of $B_{Gen}^{2}$ (0) and hence, $B_{Gen}^{1} (0) = (\bar{a}bc + b\bar{c})$ and $B_{Gen}^{1} (1) = (\bar{a}bc + \bar{b}c)$.

Now, we need to compare both the $B_{Gen}^{1}$ with the $B_{Gen}^{2}$(1) to determine the updated value of $B_{Gen}^{1}$ (0) and $B_{Gen}^{1}$ (1). The $B_{Gen}^{1}$ (0) is compared with the $B_{Gen}^{2}$ (1) and the term $(\bar{a}bc)$ of $B_{Gen}^{1}$ (0) and the term $(\bar{a}b\bar{c})$ of $B_{Gen}^{2}$ (1) has the highest literal matching. So, the $B_{Gen}^{1}$ (0) is upgraded to $B_{Gen}^{1} (0) = (\bar{a}bc + b\bar{c} + \bar{a}b\bar{c})$. Similarly, the $B_{Gen}^{1}$ (1) is upgraded to $B_{Gen}^{1} (1) = (\bar{a}bc + \bar{b}c + \bar{a}b\bar{c})$.

After the minimization, the $B_{Gen}^{1} (0) = (\bar{a}b + b\bar{c})$ and $B_{Gen}^{1} (1) = (\bar{a}b + \bar{b}c)$.

As both $B_{Gen}^{1}$ (0) and $B_{Gen}^{1}$ (1) contains similar number of literals, there will be only two generators to identify all the possible SMGF in the given circuit. ${\text{generator}}(0) = B_{Gen}^{1} (0) = (\bar{a}b + b\bar{c})$ ${\text{and generator}}(1) = B_{Gen}^{1} (1) = (\bar{a}b + \bar{b}c)$

Now as per the third phase, the test vector formation from the Boolean generator is explained as follows:

$Minterm_{generator(0)} = \bar{a}b(c + \bar{c}) + b\bar{c}(a + \bar{a})$ $= \bar{a}bc + \bar{a}b\bar{c} + ab\bar{c} + \bar{a}b\bar{c}$ $= \bar{a}bc + \bar{a}b\bar{c} + ab\bar{c} = \{ 3,2,6\} = \{ 2,3,6\}$. The test set derived from the generator(0) is {2, 3, 6}. Similarly, $Minterm_{generator(1)} = \bar{a}b(c + \bar{c}) + \bar{b}c(a + \bar{a})$ $= \bar{a}bc + \bar{a}b\bar{c} + a\bar{b}c + \bar{a}\bar{b}c = \{ 3,2,5,1\} = \{ 3,2,5,1\}$.

The test set derived from the generator(1) is {1, 2, 3, 5}. As the generator(0) contains lesser number of test vectors, the generator(0) will be used to uncover the SMGF fault.

4.2 Boolean Based Testing Method2

In this method, the ESOP-based reversible circuit is considered for the detection of SMGF fault and also to diagnosis the detected fault. Let us assume that C_test is the testable circuit in which the test has to be performed. To test the C_test circuit, initially a fault-free ESOP-based circuit (C_true) is read from a given specification files (T_spec) and then the logical XOR is performed between C_true and C_test.

But the design of fault-free ESOP circuit from the T_spec creates problem because number of distinct ESOP circuits can be generated from the T_spec and due to this reason MPRM can be considered as the subclass of an ESOP expression. A fault-free ESOP circuit (C_true) can be identified from a number of distinct ESOP circuits by the help of some complex calculation. To solve the said problem, we have used the PPRM class from which only one circuit can be designed.

The proposed testing method is segmented into two stages. At first, fault detection is performed in the C_test and after that in second stage, identification of the detected fault in the C_test is performed and proper diagnosis is done in the C_test to transform the circuit from faulty to fault-free circuit.

4.2.1 Detection of SMGF

Here in this phase, a PPRM expression $f_{true}^{PPRM}$ from the given circuit specification fileT_spec is obtained for the circuit, C_test. After that the MPRM expression $f_{test}^{MPRM}$ is derived from testable ESOP circuit C_test. Now, for each variable contained within MPRM expression $({\text{f}}_{\text{test}}^{\text{MPRM}} )$, the polarity of such variables is converted to positive form and thereby a FPRM form $(f_{test}^{FPRM} )$ can be derived. Now, the L_XOR is computed as follows: ${\text{L}}_{\text{XOR}} = f_{true}^{PPRM} \oplus f_{test}^{FPRM}$, where $\oplus$ denotes the XOR operation. If L_XOR is zero that means fault is not detected in the C_test else SMGF is detected in the C_test.

4.2.2 Detection and Correction of SMGF

Here, both fault identification and correction of the specified fault in a given circuit. The output expression obtained from L_XOR is considered as the specification details of the corresponding missing gate and represented in the form of a Boolean expression and the variables contained within such expression L_XOR designates the control inputs for the gate Mg, where Mg denotes the missing gate in C_test circuit.

To make the circuit function correctly, if the identified missing gate (M_g) is attached to the input circuit C_test to convert it to a fault-free circuit.

Now, the proposed method of SMGF identification and medication in an ESOP based circuit has been discussed with supportive examples below.

Example 2

The benchmark ESOP circuit 4gt4 [22] is used here for testing the proposed methodology. The T_spec of 4gt4 is represented in Fig. 5a. The testable circuit, C_test for the given circuit 4gt4 is also shown in Fig. 5c. Now, the PPRM cover of the fault-free circuit is obtained from file T_spec employing [23]. In Fig. 5b, the corresponding PPRM cube can be observed and the derived PPRM expression is $f_{true}^{PPRM} = {\text{a}} \oplus {\text{bd}} \oplus {\text{bc}} \oplus {\text{bcd}} \oplus {\text{abd}} \oplus {\text{abc}} \oplus {\text{abcd}}$. Now, the obtained expression from the circuit C_test is $f_{test}^{MPRM} = {\text{a}} \oplus \bar{a}{\text{b}}\bar{c}\bar{d} \oplus \bar{a}{\text{b}}$ and changing the polarity of each literal in the expression $f_{test}^{MPRM}$ to positive value is required to derive the corresponding FPRM expression ($(f_{test}^{FPRM} = {\text{a}} \oplus {\text{bd}} \oplus {\text{bc}} \oplus {\text{bcd}} \oplus {\text{abd}} \oplus {\text{abc}} \oplus {\text{abcd}})$. Now L_XOR is computed as ${\text{L}}_{\text{XOR}} = f_{true}^{PPRM} \oplus f_{test}^{FPRM} = {\emptyset }$.

Fig. 5

Illustration of Example 2. a Input specification file of 4gt4 b Equivalent PPRM cube list of 4gt4 c Testable input ESOP circuit for function 4gt4

Hence, it can be confirmed that there an SMGF does not exist in the circuit C_test as L_XOR is null.

Example 3

The benchmark circuit 4mod5 [22] is considered here once again to explain the proposed technique. The specification file T_spec for 4mod5 and C_test circuit are represented in Fig. 6a and b, respectively. Initially, $f_{true}^{PPRM} = 1 \oplus {\text{ad}} \oplus {\text{ab}} \oplus {\text{bc}} \oplus {\text{cd}} \oplus {\text{a}} \oplus {\text{b}} \oplus {\text{c}} \oplus {\text{d}}$ is obtained from T_spec. Then, MPRM expression $(f_{test}^{MPRM} = 1 \oplus {\text{a}}\bar{d} \oplus \bar{a}{\text{b}} \oplus \bar{b}c)$ is derived from the circuit C_test. Now, an FPRM logic expression $(f_{test}^{FPRM} = 1 \oplus {\text{ad}} \oplus {\text{ab}} \oplus {\text{bc}} \oplus {\text{a}} \oplus {\text{b}} \oplus {\text{c}})$ is formed. The equivalent ESOP structure of derived $f_{test}^{FPRM}$ and $f_{true}^{PPRM}$ expressions are represented in Fig. 6c and d, respectively. Now, $L_{XOR} = f_{true}^{PPRM} \oplus f_{test}^{FPRM} = {\text{cd}} \oplus {\text{d}} = \bar{c}{\text{d}}$.

Fig. 6

Illustration of Example 3. a Specification file T_spec for circuit 4mod5 b Testable input circuit 4mod5 c $f_{test}^{FPRM}$ function equivalent ESOP circuit d $f_{test}^{FPRM}$ function equivalent ESOP circuit e Detected missing gate details f Fault free circuit of 4mod5

Hence, it is confirmed that a SMGF fault is present in C_test exists as L_XOR is equal to some Boolean value. As per the proposed method, the expression L_XOR represents the control lines of the gate M_g (as depicted in Fig. 6e) which is completely missing in the testable circuit. Thereafter, it can be described that the M_g is having a negative control and positive control at lines c and d, respectively.

The circuit can be made fault free if the corresponding missing gate (M_g) is adjoined to the input circuit C_test and the resultant original ESOP structure of 4mod5 is depicted in Fig. 6f.

5 Experimental Results

We have tested both of our approaches against different benchmark suites [22]. The results obtained from first testing approach is summarized in Table 1, where first three columns represent the circuit name, the number of lines (n) and the number of gates (N) present in a benchmark function. The Boolean generator is shown in column 4 and the set of test patterns produced from the generator are tabulated in column 5 of Table 1.

Table 1 Boolean generator for the detection of SMGF

The second testing technique is also checked over several benchmark circuits and the effectiveness of RM form also has been verified for successful detection and localization of faults.

6 Conclusions

This work has presented two Boolean based approaches for testing of SMGF faults in reversible circuit. In the first method, a Boolean generator has developed for a reversible circuit and in later time, from this generator test vectors are constructed to a test a circuit. The second testing technique has mainly targeted to test a special class of reversible circuit known as ESOP designs. But, the first testing technique is very generic and can be employed over any type of circuits. In both the testing approaches, we have addressed SMGF only, but other types of faults like RGF, MMGF also can be tracked by following the same strategy as used to find SMGF. The presented techniques have successfully tested over a wide spectrum of benchmarks also.