Universal Test Sets for Reversible Circuits

摘要

A set of test vectors is complete for a reversible circuit if it covers all stuck-at faults on the wires of the circuit. It has been known that any reversible circuit has a surprisingly small complete test set, while it is NP-hard to generate a minimum complete test set for a reversible circuit. A test set is universal for a family of reversible circuits if it is complete for any circuit in the family. We show minimum universal test sets for some families of CNOT circuits.