On Fault Testing for Reversible Circuits

Satoshi TAYU  Shigeru ITO  Shuichi UENO  

IEICE TRANSACTIONS on Information and Systems   Vol.E91-D   No.12   pp.2770-2775
Publication Date: 2008/12/01
Online ISSN: 1745-1361
DOI: 10.1093/ietisy/e91-d.12.2770
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>>
Buy this Article

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.