Reversible Function Synthesis of Large Reversible Functions with No Ancillary Bits Using Covering Set Partitions

This paper presents a synthesis algorithm, Covering Set Partitions (CSP), for reversible binary functions with no ancillary (garbage) bits. Existing algorithms are constrained to functions of small number of variables because they store the entire truth table of 2n terms in memory or require a huge amount of time to yield results because they must calculate all possible permutations of an input vector. In contrast, the CSP algorithm harnesses the natural mathematical properties of binary numbers, partially ordered sets and covering graph theory, to construct input vectors which are guaranteed to produce valid results. A randomly selected subset of all valid input vectors are processed where the best input vector sequence wins. The CSP algorithm is capable of synthesizing functions of large number of variables (30 bits) in a reasonable amount of time.