Reversible Logic Synthesis Benchmarks Page


you are in... Main\4-bit with maximal gate count

This set contains all functions that require the maximal number of gates, 15, in their optimal gate count implementation as a NOT, CNOT, Toffoli, and Toffoli-4 circuit. Interestingly, up to the two symmetries that do not change the form of the optimal implementation---simultaneous input/output relabeling, and inversion of the order of gates in the circuit---there are only five such functions. With all symmetries included, there are 144 functions (the numbers of symmetries are 24, 24, 48, 24, and 24). These five (one hundred forty four) functions were first described in <paper in preparation>.