On generating test sets for reversible circuits

Reversible circuits are quite attractive because of the possibility of nearly energy-free computation. During designing and constructing a reversible circuit, it is important to test the circuit and detect faults in the circuit. However, very few algorithms are known to generate a complete test set for a given reversible circuit. In this paper, first of all, it is NP-hard to generate a minimum complete test set for stuck-at faults even when a given reversible circuit is restricted to use only three kinds of simple reversible gates, that is NOT, 1-CNOT, and Toffoli gates. Therefore, it seems to be quite difficult, or even impossible, to generate minimum complete test sets for practical reversible circuits. Next, the paper presents a randomized algorithm to generate a complete test set for stuck-at faults in a given reversible circuit. As far as the authors know, the proposed algorithm is the first one to guarantee that the expected time complexity is polynomial and that the size of the obtained test size is bounded. Finally, the effectiveness of the proposed algorithm is shown by experiments.