IEICE TRANSACTIONS on Information
On Fault Testing for Reversible Circuits
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.
- Publication
- IEICE TRANSACTIONS on Information Vol.E91-D No.12 pp.2770-2775
- Publication Date
- 2008/12/01
- Publicized
- Online ISSN
- 1745-1361
- DOI
- 10.1093/ietisy/e91-d.12.2770
- Type of Manuscript
- PAPER
- Category
- Complexity Theory
Authors
Keyword
Latest Issue
Copyrights notice of machine-translated contents
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
Cite this
Copy
Satoshi TAYU, Shigeru ITO, Shuichi UENO, "On Fault Testing for Reversible Circuits" in IEICE TRANSACTIONS on Information,
vol. E91-D, no. 12, pp. 2770-2775, December 2008, doi: 10.1093/ietisy/e91-d.12.2770.
Abstract: 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.
URL: https://global.ieice.org/en_transactions/information/10.1093/ietisy/e91-d.12.2770/_p
Copy
@ARTICLE{e91-d_12_2770,
author={Satoshi TAYU, Shigeru ITO, Shuichi UENO, },
journal={IEICE TRANSACTIONS on Information},
title={On Fault Testing for Reversible Circuits},
year={2008},
volume={E91-D},
number={12},
pages={2770-2775},
abstract={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.},
keywords={},
doi={10.1093/ietisy/e91-d.12.2770},
ISSN={1745-1361},
month={December},}
Copy
TY - JOUR
TI - On Fault Testing for Reversible Circuits
T2 - IEICE TRANSACTIONS on Information
SP - 2770
EP - 2775
AU - Satoshi TAYU
AU - Shigeru ITO
AU - Shuichi UENO
PY - 2008
DO - 10.1093/ietisy/e91-d.12.2770
JO - IEICE TRANSACTIONS on Information
SN - 1745-1361
VL - E91-D
IS - 12
JA - IEICE TRANSACTIONS on Information
Y1 - December 2008
AB - 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.
ER -
English
