On Generating Test Sets for Detecting Stuck-at Faults in Reversible Circuits

概要

論文の詳細を見る
Reversible circuits are quite attractive because of the possibility of nearly energy-free computation. During 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 test set for detecting faults in a given reversible circuit. In this paper, first of all, it is proved to be NP-hard to generate a minimum test set for detecting stuck-at faults in a given reversible circuit even when the circuit is restricted to use only three kinds of simple reversible gates, that is NOT, 1-CNOT, and Toffoli gates. Next, the paper presents a randomized algorithm to generate a test set for detecting 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.
一般社団法人情報処理学会の論文
2009-11-20