On Fault Testing for Reversible Circuits

Satoshi TAYU  Shigeru ITO  Shuichi UENO  

Publication
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
Keyword: 
3-SAT,  CNOT gate,  complete test set,  fault testing,  NP-complete,  reversible circuit,  stuck-at fault,  test vector,  

Full Text: PDF>>
Buy this Article




Summary: 
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.