A Coding Theoretic Approach towards Symmetrization in Reversible Circuit Synthesis
Anubhab Baksi, Sumanta Sarkar and Anupam Chattopadhyay
Multiple emerging technologies in nanometer scale, including Quantum computing, requires circuit design with fan-out restriction and impose logical reversibility as a prerequisite to achieve asymptotically zero power consumption. This has prompted researchers to explore efficient design of important classes of Boolean functions with limited fan-out and using reversible logic gates as building blocks. Symmetric Boolean functions, a key subclass of Boolean functions, is studied well from the perspective of circuit complexity theory, with some promising recent results. Efficient reversible logic synthesis of symmetric Boolean functions also has been developed. On the other hand, in 1963, Arnold and Harrison proposed an algorithm that symmetrizes any Boolean function by adding an exponential number of additional input variables. The recent efficient implementation and synthesis studies, when put in combination with the Arnold-Harrison algorithm, represents an interesting possibility that one may first symmetrize an arbitrary Boolean function and then proceed towards synthesis. In this paper, we look into this possibility and present a general impossibility result. The core contribution of our work is to explain the Arnold-Harrison algorithm with the help of coding theory. Based on this framework, we show that there exists a large subclass of Boolean functions, for which a linear number of additional input variables suffice when symmetrization is attempted. As a result, indeed, for such classes of non-symmetric Boolean functions, the synthesis approach via symmetrization yields improved results.
Keywords: Boolean function, reversible computing, coding theory