The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. ex. Some numerals are expressed as "XNUMX".
Copyrights notice
The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. Copyrights notice
Il est connu que le test des circuits réversibles est relativement plus facile que celui des circuits irréversibles classiques dans le sens où peu de vecteurs de test sont nécessaires pour couvrir tous les défauts bloqués. Cet article montre cependant qu'il est NP-difficile de générer un ensemble de tests minimum complet pour les défauts coincés sur les fils d'un circuit réversible en utilisant une réduction du temps polynomial de 3SAT au problème. Nous montrons également des limites inférieures non triviales pour la taille d’un ensemble de tests minimum complet.
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.
Copier
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
Copier
@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},}
Copier
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 -