Detection of Bridging Fault in Reversible Circuits
Hafizur Rahaman, Dipak Kumar Kole, Debesh Kumar Das, Bhargab B. Bhattacharya · SSRN Electronic Journal · 2010
Logic synthesis with reversible circuits has received considerable interest in the light of advances recently made in quantum computation. Implementation of a reversible circuit is envisaged by deploying several special types of quantum gates, such as Toffoli gate. Newer technologies like ion trapping or nuclear magnetic resonance are required to emulate quantum gates. This paper presents the testability issue of reversible circuits under the bridging fault model. Intra-level bridging fault model is considered here, i.e., a single pair of lines, both lying at the same level of the circuit, may be assumed to have been logically shorted in order to model a defect in reversible circuit. For an (N x N) reversible circuit with d levels realized with simple Toffoli gates, the time complexity of the test generation procedure is O(Nd2 log2N). A test set of cardinality O(d log2N) is found to be sufficient for testing all such detectable faults. A minimal test set can also be easily derived by using the concept of test equivalence. Finally, this paper proposes a design for testability technique to achieve universal test set. The reversible circuit has been augmented by adding one control AND line to achieve a universal set for detection of this fault. For an N x N reversible circuit realized with simple Toffoli gate, this technique admits a compact test set of cardinality log2 N1.