Efficient simulation-based debugging of reversible logic

Reversible logic has become an active research area due to its various applications in emerging technologies, like quantum computing, low power design, optical computing, DNA computing, or nanotechnologies. As a result, complex reversible circuits containing thousands of gates can be efficiently synthesized, today. However, this also increases the probability of design errors. While for the detection of errors already a couple of simulation-based or formal verification techniques have been proposed for reversible logic. Research in the domain of debugging is still at the beginning. In this paper, we present an automatic debugging approach for reversible logic which is based on simulation. We show that a particular error in a gate always requires a counterexample leading to a concrete gate input pattern. By simulating all counterexamples and checking for these input patterns, irrelevant gates (i.e. gates that do not contain an error) can be excluded. Experiments show, that applying the proposed approach leads to speed-ups of up to five orders of magnitude. Furthermore, the number of error candidates can be reduced in comparison to previous work.