Document Type

Conference Proceeding

Publication Date



Logic circuits -- Testing, Quantum computing, Algorithms


There is recently an interest in test generation for reversible circuits, but nothing has been published about fault localization in such circuits. This paper deals with fault localization for binary reversible (permutative) circuits. We concentrate on functional test based fault localization, to detect and locate “stuck-at” faults in a reversible circuit by creating an adaptive tree. A striking property of reversible circuits is that they exhibit “symmetric” adaptive trees. This helps considerably by being able to generate only half of the tree, and the other half is created as the mirror image of the first half. Because each test covers half faults [1] and the fault table has a high density of ones, it is relatively easy to generate the tree. The problem of fault localization of reversible circuits is therefore easier than the same problem for standard irreversible circuits. We present some preliminary results from an approach using traditional adaptive tree methods. We propose also a new efficient algorithm that eliminates the fault table generation and dynamically creates the adaptive fault tree.


Originally presented at the International Workshop on Logic and Synthesis, June 2004, and subsequently included in its proceedings.

Persistent Identifier