Fast Synthesis of Reversible Circuits Using a Sorting Algorithm and Optimization

Susam O., Altun M.

JOURNAL OF MULTIPLE-VALUED LOGIC AND SOFT COMPUTING, cilt.29, ss.1-23, 2017 (SCI-Expanded) identifier

  • Yayın Türü: Makale / Tam Makale
  • Cilt numarası: 29
  • Basım Tarihi: 2017
  • Dergi Adı: JOURNAL OF MULTIPLE-VALUED LOGIC AND SOFT COMPUTING
  • Derginin Tarandığı İndeksler: Science Citation Index Expanded (SCI-EXPANDED), Scopus
  • Sayfa Sayıları: ss.1-23
  • İstanbul Teknik Üniversitesi Adresli: Evet

Özet

This paper studies synthesis and optimization of reversible circuits composed of Toffoli gates with negative and positive control lines. The proposed synthesis algorithm performs sorting among optimal implementations of certain functions - called as essential functions - to implement any reversible Boolean function. Essential functions comprise very small amount of all functions. For example, to implement 3 bit circuits, 28 essential functions out of all 40320 functions are needed. The proposed optimization algorithm considers both reversible and quantum circuit costs. First, reversible cost is reduced by considering adjacent gate pairs. Then, inner quantum structures of the gates are investigated and quantum optimization is performed. The proposed algorithms are evaluated on benchmark circuits in comparison with the results in the literature.