For Full-Text PDF, please login, if you are a member of IEICE,|
or go to Pay Per View on menu list, if you are a nonmember of IEICE.
On Fault Testing for Reversible Circuits
Satoshi TAYU Shigeru ITO Shuichi UENO
IEICE TRANSACTIONS on Information and Systems
Publication Date: 2008/12/01
Online ISSN: 1745-1361
Print ISSN: 0916-8532
Type of Manuscript: PAPER
Category: Complexity Theory
3-SAT, CNOT gate, complete test set, fault testing, NP-complete, reversible circuit, stuck-at fault, test vector,
Full Text: PDF>>
It has been known that testing of reversible circuits is relatively easier than conventional irreversible circuits in the sense that few test vectors are needed to cover all stuck-at faults. This paper shows, however, that it is NP-hard to generate a minimum complete test set for stuck-at faults on the wires of a reversible circuit using a polynomial time reduction from 3SAT to the problem. We also show non-trivial lower bounds for the size of a minimum complete test set.