Determining minimal testsets for reversible circuits using Boolean satisfiability

Reversible circuits are an attractive computation model as they theoretically enable computations with close to zero power consumption. Furthermore, reversible circuits found significant attention in the domain of quantum computation. With the emergence of first physical realizations for this kind of circuits, also testing issues become of interest. Accordingly, first approaches for automatic test pattern generation have been introduced. However, they suffer either from their limited scalability or do not generate a minimal testset. In this paper, a SAT-based algorithm for the determination of minimal complete testsets is proposed. An experimental evaluation of the proposed method shows that the algorithm is applicable to reversible circuits with more than 2 000 gates.