Derivation of test set for detecting multiple missing-gate faults in reversible circuits

Logic synthesis of reversible circuits has become an important problem because of its relevance to the emerging area of quantum computation. Special types of quantum gates such as k-CNOT may be deployed to implement a reversible circuit. Although the classical stuck-at fault model is widely used for modeling defects in conventional CMOS circuits, new approaches, namely single missing-gate fault (SMGF), repeated-gate fault (RGF), partial missing-gate fault (PMGF), and multiple missing-gate fault (MMGF), have been found to be more befitting for modeling defects in quantum k-CNOT gates. This article presents an algorithm to derive a test set (TS) for detection of multiple missing-gate faults in a reversible circuit implemented with k-CNOT gates. It is shown that TS is sufficient to detect all single missing-gate faults (SMGFs) and all detectable repeated gate faults (RGFs). Experimental results on test set for some benchmark circuits are reported, which compare favorably with earlier findings.

ham3tc reversible circuit of size 3 with depth5Figure optionsDownload as PowerPoint slideHighlights
► Find a test set (TS) that detects all multiple missing gate faults (MMGFs) of a reversible circuit (RC).
► Injecting all MMGFs in the given circuit RC and compute the set of test patterns for detecting each MMGF.
► Initially each MMGF fault is unmarked and TS is empty.
► Add a test pattern t to TS containing maximum unmarked MMGFs and marked those MMGFs detected by t.
► Continue the previous step until no more unmarked MMGF is left; output TS.