Enumeration of reversible functions and its application to circuit complexity
We review combinational results to enumerate and classify reversible functions and investigate the application to circuit complexity. In particularly, we consider the effect of negating and permuting input and output variables and the effect of applying linear and affine transformations to inputs and outputs. We apply the results to reversible circuits and prove that minimum circuit realizations of functions in the same equivalence class differ at most in a linear number of gates in pres- ence of negation and permutation and at most in a quadratic number of gates in presence of linear and affine transformations.
2016_rc_2.pdf
openaccess
422.74 KB
Adobe PDF
699df9a577a59d5d5f5492c90861e43b