Debugging reversible circuits

A strong driving force for research of post-CMOS technologies is the fact that silicon-based transistors cannot be arbitrarily scaled down. Furthermore, power dissipation is a major barrier in the development of smaller and more efficient computer chips. In contrast, reversible logic with its applications e.g. in low-power design or quantum computation provides a promising alternative to traditional technologies. While there have been investigations in the domain of reversible logic synthesis, testing, and verification; debugging of reversible circuits has not yet been considered. The goal of debugging is to determine gates of an erroneous circuit that explain the observed incorrect behavior. In this paper, we propose the first approach for automatic debugging of reversible Toffoli circuits. Our method uses a formulation for the debugging problem based on Boolean satisfiability. We show the differences to traditional (irreversible) debugging. In addition, we introduce an improved approach that strengthens error candidate identification. This overcomes the limitations from traditional debugging, i.e. that error candidates are only an approximation of the real source of the error. Furthermore, observations are presented that can be applied to automatically fix an erroneous circuit just by replacing a single gate by a cascade. Due to reversibility this cascade can be efficiently computed. Experimental results show the quality and efficiency of our debugging approaches. (C) 2010 Elsevier B.V. All rights reserved.