Reversible Synthesis of Symmetric Functions with a Simple Regular Structure and Easy Testability

In this paper, we introduce a novel method of synthesizing symmetric boolean functions with reversible logic. In contrast to earlier approaches, the proposed technique deploys a simple, regular, and cascaded structure consisting of an array of Peres and CNOT gates, which results in significant reduction with respect to the quantum cost. However, the number of garbage outputs may increase slightly when such cascades are used. In order to reduce it, we next propose a post-synthesis optimization phase that allows judicious re-use of garbage outputs. In addition to offering a cost-effective synthesis methodology, the proposed reversible-logic structure exhibits elegant testability properties. With respect to all single or partial missing gate faults (SMGF and PMGF), or repeated gate faults (RGF) in such an n-input circuit module, we show that it admits a universal test set of constant cardinality (three) for any value of n. Thus, considering both the cost and testability issues, this approach provides a superior option for synthesizing symmetric functions compared to existing designs.