On Generating Test Sets for Detecting Stuck-at Faults in Reversible Circuits

• Item type: SIG Technical Reports(1)
• 公開日: 2009-11-20
• タイトル: On Generating Test Sets for Detecting Stuck-at Faults in Reversible Circuits
• タイトル / 言語: en
• タイトル: On Generating Test Sets for Detecting Stuck-at Faults in Reversible Circuits
• 言語: eng
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_18gh
• 資源タイプ: technical report
• 著者所属: Division of Mathematics, Electronics and Informatics, Graduate School of Science and Engineering, Saitama University
• 著者所属: Division of Mathematics, Electronics and Informatics, Graduate School of Science and Engineering, Saitama University
• 著者所属(英): en
• 著者所属(英): Division of Mathematics, Electronics and Informatics, Graduate School of Science and Engineering, Saitama University
• 著者所属(英): en
• 著者所属(英): Division of Mathematics, Electronics and Informatics, Graduate School of Science and Engineering, Saitama University
• 著者名: Kaku, Tabei; Toshinori, Yamada
• 著者名(英): Kaku, Tabei; Toshinori, Yamada
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: Reversible circuits are quite attractive because of the possibility of nearly energy-free computation. During constructing a reversible circuit, it is important to test the circuit and detect faults in the circuit. However, very few algorithms are known to generate a test set for detecting faults in a given reversible circuit. In this paper, first of all, it is proved to be NP-hard to generate a minimum test set for detecting stuck-at faults in a given reversible circuit even when the circuit is restricted to use only three kinds of simple reversible gates, that is NOT, 1-CNOT, and Toffoli gates. Next, the paper presents a randomized algorithm to generate a test set for detecting stuck-at faults in a given reversible circuit. As far as the authors know, the proposed algorithm is the first one to guarantee that the expected time complexity is polynomial and that the size of the obtained test size is bounded. Finally, the effectiveness of the proposed algorithm is shown by experiments.
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: Reversible circuits are quite attractive because of the possibility of nearly energy-free computation. During constructing a reversible circuit, it is important to test the circuit and detect faults in the circuit. However, very few algorithms are known to generate a test set for detecting faults in a given reversible circuit. In this paper, first of all, it is proved to be NP-hard to generate a minimum test set for detecting stuck-at faults in a given reversible circuit even when the circuit is restricted to use only three kinds of simple reversible gates, that is NOT, 1-CNOT, and Toffoli gates. Next, the paper presents a randomized algorithm to generate a test set for detecting stuck-at faults in a given reversible circuit. As far as the authors know, the proposed algorithm is the first one to guarantee that the expected time complexity is polynomial and that the size of the obtained test size is bounded. Finally, the effectiveness of the proposed algorithm is shown by experiments.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN1009593X
• 書誌情報: 研究報告アルゴリズム（AL）; 巻 2009-AL-127, 号 2, p. 1-8, 発行日 2009-11-20
• Notice: SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc.
• 出版者 / 言語: ja
• 出版者: 情報処理学会