Abstract:
One of the key problems in reversible logic synthesis is optimizing the reversible circuits, and the focus of research is on how to decompose advanced reversible gates into basic reversible gates more efficiently. To improve the decomposition and optimization efficiency of Multiple Control Target (MCT) gates, an optimal decomposition method of MCT gates is proposed in the paper, along with an MCT decomposition template which correctness is verified. Based on this template, the corresponding decomposition and optimization algorithm is given. Using the optimal decomposition template, the algorithm classifies the Toffoli circuits decomposed by MCT gates and decomposes them into NCV circuits. The time complexity of the algorithm is
O(
m), which is better than
O(
m2) for the conventional algorithm. Experiments on MCT gates with benchmark reversible circuits for control bits
m∈3,10 show the effectiveness of the algorithm’s optimization and decomposition.