Upper bounds for reversible circuits based on Young subgroups

作者：Abdessaied Nabila^*; Soeken Mathias; Thomsen Michael Kirkedal; Drechsler Rolf

来源：Information Processing Letters, 2014, 114(6): 282-286.

DOI：10.1016/j.ipl.2014.01.003

• Combinatorial problems
• Reversible functions
• Upper bounds
• Synthesis

We present tighter upper bounds on the number of Toffoli gates needed in reversible circuits. Both multiple controlled Toffoli gates and mixed polarity Toffoli gates have been considered for this purpose. The calculation of the bounds is based on a synthesis approach based on Young subgroups that results in circuits using a more generalized gate library. Starting from an upper bound for this library we derive new bounds which improve the existing bound by around 77%.

• 出版日期2014-6