Research Journal of Applied Sciences, Engineering and Technology 4(18): 3470-3475, 2012
ISSN: 2040-7467
© Maxwell Scientific Organization, 2012
Submitted: April 23, 2012 Accepted: May 18, 2012 Published: September 15, 2012
Corresponding Author:
Yu Pang, Chongqing University of Posts and Telecommunications, Chongqing, China
3470
Fault Model for Testable Reversible Toffoli Gates
Yu Pang, Shaoquan Wang, Zhilong He and Qiangbing Zhang
Chongqing University of Posts and Telecommunications, Chongqing, China
Abstract: Techniques of reversible circuits can be used in low-power microchips and quantum
communications. Current most works focuses on synthesis of reversible circuits but seldom for fault testing
which is sure to be an important step in any robust implementation. In this study, we propose a Universal
Toffoli Gate (UTG) with four inputs which can realize all basic Boolean functions. The all single stuck-at faults
are analyzed and a test-set with minimum test vectors is given. Using the proposed UTG, it is easy to implement
a complex reversible circuit and test all stuck-at faults of the circuit. The experiments show that reversible
circuits constructed by the UTGs have less quantum cost and test vectors compared to other works.
Keywords: Quantum cost, reversible logic, stuck-at fault model, test vector, toffoli gate
INTRODUCTION
Recently, reversible circuits started to emerge as an
important topic, bringing alternative solutions to classical
networks. The motivation behind reversible computation
comes from its two important properties: information
lossless computation with less energy dissipation and
close relation to several emerging technologies such as
quantum circuits and optical computing (Landauer, 1961).
The testing properties and test generation for
reversible circuits are initially proposed by (Patel et al.,
2003). The authors shown that only few vectors are
necessary to fully test a reversible circuit under the
multiple stuck-at fault model with the number growing at
most logarithmically both in the number of inputs and the
number of gates. The authors (Hayes et al., 2004) present
a method to make any circuit fully testable for single
missing gate fault with single test vector. In particular, to
test a circuit with a missing gate fault, it is necessary to
apply a vector of the form 111……1 and ensures that any
signal change or error at any node will propagate to the
circuit’s primary outputs. A design-for-testability method
has been proposed to make any reversible logic circuit
composed of n-bit Toffoli gates fully testable for single
stuck-at faults and single intra-level bridging faults
(Bubna et al., 2007). In this case bridging fault between
a pair of lines is assumed to occur one at a time and
function as a classical AND or OR bridging type.
However, the overhead caused by added circuitry for
testability is significant, since adding extra control point
in Toffoli gate increases the overall quantum cost.
Although these off-line testing methods are simple to
adopt, the on-line testing of reversible circuits is still a
challenging issue.
New online fault testing methods for reversible
circuits have been presented. A universal dual rail
reversible gate is proposed, which can implement any
reversible circuit and provide detection of any single fault
on inputs, outputs and inside the gate (Farazmand and
Mehdi, 2010). Two reversible gates R1 and R2 are used
to construct online-testable reversible circuits. The parity
outputs of R1 and R2 are monitored to detect a single bit
error (Vasudevan et al., 2004a). An extended version, i.e.,
a new two pair two rail checker is presented (Vasudevan
et al., 2004b). However the computational complexity due
to excessive number of gates limits its application.
Recently a concurrent error detection methodology is
proposed (Patel et al., 2003). The main feature of this
method is its capability to detect multi-bit error at the
outputs. However, added circuitry for inversing the
original gate and constructing a comparator, as well as
extra Feynman gates for duplicating primary outputs and
inputs increases the area and quantum cost of the overall
reversible circuit (Ketan et al., 2004).
In this study, we propose a new reversible gate, i.e.,
a Universal Toffoli Gate (UTG), which can be used to
construct any testable reversible circuit. Since a stuck-at
fault is a particular fault model used by fault simulators
and automatic test pattern generation tools to mimic a
manufacturing defect within an integrated circuit, in this
study we investigate stuck-at faults of UTG. A small set
of test vectors is capable of finding any single fault on
inputs, outputs and inside the gate can be found. Further,
an algorithm is proposed to find test vectors for a complex
circuit constructed by UTGs. Compared to existing
methods, the testable reversible circuits generated by
UTGs have smaller quantum costs and high testing
efficiency.
METHODOLOGY
Proposed UTG:
Definition 1: The network quantum cost is the sum of the
quantum cost of all gates. The quantum cost of a gate is