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.

Energy loss is an important consideration in digital design. Part of the problem of energy dissipation is related to non-ideality of switches and material. However, higher levels of integration and the use of new fabrication processes over the last decades have dramatically reduced the heat loss. The other part of the problem arises from Landauer’s principle (Landauer, 1961), for which there is no known solution other than reversible computation (when input values of a computation can be uncovered by the information on its outputs). If Integrated Circuit (IC) technology continues to follow the pattern predicted by the Moore’s Law (Moore, 1965), energy loss in non-reversible design is likely to become more dominant, and reversible logic may offer a viable solution in the future with newer technologies. Reversible logic can be employed to design information lossless circuits (Landauer, 1961; and Bennett, 1973 and 1988). An n-input, m-output boolean function F is said to be reversible if and only if m = n, and F is one-to-one. A combinational logic circuit is said to be reversible if it is fanout free, acyclic, and consists of only reversible gates, which themselves implement reversible functions; such gates need to be specially designed, e.g., Toffoli gates. Reversible Circuits (RCs) have manifold applications in optical computing, digital signal processing, communication, cryptography, nanotechnology, quantum computing, DNA technology, and low-power CMOS design (Preskill, 1988; Picton, 1991 and 2000; Merkle, 1993a and 1993b; Athas and Svensson, 1994; Merkle and Drexler, 1996; Gershenfeld and Chuang, 1998; and Nielsen and Chuang, 2000). Basically, the circuit design that does not result in information loss is called reversible. It naturally takes care of heating generated due to the information loss. All quantum computations are necessarily reversible. Therefore, research of reversible logic is beneficial to the development of future quantum technologies: reversible design methods might give rise to methods of quantum circuit construction, resulting in much more powerful computers and computations. The synthesis and testing of reversible circuits need further investigation.

Conventional logic gates such as AND, OR, or EXOR used in digital design are not reversible. Only the NOT gate is reversible. To design a reversible circuit, only reversible gates can be used, for example, the Controlled-NOT (CNOT) gate proposed by Toffoli (1980), and Fredkin and Toffoli (1982), Feynman (1985) gates. Several techniques for synthesis of reversible logic circuits are available (Perkowski et al., 2001; Iwama et al., 2002; Miller, 2002; Mishchenko and Perkowski, 2002; Miller and Dueck, 2003; and Shende et al., 2003).

Computer Sciences Journal, Bridging Faults, Reversible Circuits, Nuclear Magnetic Resonance, Optical Computing, Digital Signal Processing, Conventional Logic Gates, Missing Gate Fault, Universal Test Set, Benchmark Circuits.