On Fault Testing for Reversible Circuits

被引：3

作者：

Tayu, Satoshi ^{[1
]}

Ito, Shigeru ^{[1
]}

Ueno, Shuichi ^{[1
]}

机构：

[1] Tokyo Inst Technol, Dept Commun & Integrated Syst, Tokyo 1528550, Japan

来源：

IEICE TRANSACTIONS ON INFORMATION AND SYSTEMS | 2008年 / E91D卷 / 12期

关键词：

3-SAT; CNOT gate; complete test set; fault testing; NP-complete; reversible circuit; stuck-at fault; test vector;

D O I：

10.1093/ietisy/e91-d.12.2770

中图分类号：

TP [自动化技术、计算机技术];

学科分类号：

0812 ;

摘要：

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 oil the wires of a reversible circuit using a polynomial time reduction from 3SAT to the problem. We also show non-trivial lower hounds for the size of a minimum complete test set.

引用

页码：2770 / 2775

页数：6

共 7 条

[1] LOGICAL REVERSIBILITY OF COMPUTATION [J].

BENNETT, CH .

IBM JOURNAL OF RESEARCH AND DEVELOPMENT, 1973, 17 (06) :525-532

[2]

CHAKRABORTY A, 2005, P 18 INT C VLSI DES

[3] IRREVERSIBILITY AND HEAT GENERATION IN THE COMPUTING PROCESS [J].

LANDAUER, R .

IBM JOURNAL OF RESEARCH AND DEVELOPMENT, 1961, 5 (03) :183-191

[4]

Merkle R. C., 1993, Nanotechnology, V4, P114, DOI 10.1088/0957-4484/4/2/007

[5]

Nielsen M.A., 2002, Quantum computation and quantum information, DOI DOI 10.1119/1.1463744

[6] Fault testing for reversible circuits [J].

Patel, KN ;

Hayes, JP ;

Markov, IL .

IEEE TRANSACTIONS ON COMPUTER-AIDED DESIGN OF INTEGRATED CIRCUITS AND SYSTEMS, 2004, 23 (08) :1220-1230

[7] Synthesis of reversible logic circuits [J].

Shende, VV ;

Prasad, AK ;

Markov, IL ;

Hayes, JP .

IEEE TRANSACTIONS ON COMPUTER-AIDED DESIGN OF INTEGRATED CIRCUITS AND SYSTEMS, 2003, 22 (06) :710-722

← 1 →