nach oben

Erschienen in:

2020 | OriginalPaper | Buchkapitel

Ant Colony Optimization Implementation for Reversible Synthesis in Walsh-Hadamard Domain

verfasst von : Krzysztof Podlaski

Erschienen in: Computational Science – ICCS 2020

Verlag: Springer International Publishing

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

Reversible circuits are one of the technologies that can provide future low energy circuits. The synthesis of an optimal reversible circuit for a given function is an np-hard problem. The meta-heuristic approaches are one of the most promising methods for these types of optimization problems. In this paper, a new approach for ACO reversible synthesis is presented. Usually, authors build an ACO system with the use of truth table or permutation representation of the reversible function. In this work, a Walsh spectral representation of a Boolean function is used. This allows dividing search spaces into smaller “promising” areas with well-defined transition operations between them. As a result, we can minimize the enormous search space and generate better solutions than obtained by ACO synthesis with classical reversible function representation. The proposed approach was applied to benchmark reversible functions of 4,5 and 6 variables and compared to other meta-heuristic results and best-known solutions.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Vorheriges Kapitel Radial Basis Functions Based Algorithms for Non-Gaussian Delay Propagation in Very Large Circuits

Nächstes Kapitel COEBA: A Coevolutionary Bat Algorithm for Discrete Evolutionary Multitasking

Amy, M., Maslov, D., Mosca, M., Roetteler, M.: A meet-in-the-middle algorithm for fast synthesis of depth-optimal quantum circuits. IEEE Trans. Comput.-Aided Des. Integr. Circuits Syst. 32(6), 818–830 (2013)CrossRef

Barenco, A., et al.: Elementary gates for quantum computation. Phys. Rev. A 52, 3457–3467 (1995)CrossRef

Conte, T.M., DeBenedictis, E.P., Gargini, P.A., Track, E.: Rebooting computing: the road ahead. Computer 50(1), 20–29 (2017)CrossRef

Datta, K., Sengupta, I., Rahaman, H.: Particle swarm optimization based reversible circuit synthesis using mixed control Toffoli gates. J. Low Power Electron. 9(3), 363–372 (2013)CrossRef

Dorigo, M.: Optimization, learning and natural algorithms. Ph.D. thesis, Politecnico di Milano, Italy (1992)

Dorigo, M., Blum, C.: Ant colony optimization theory: a survey. Theor. Comput. Sci. 344(2), 243–278 (2005)MathSciNetCrossRef

Dorigo, M., Maniezzo, V., Colorni, A.: Ant system: optimization by a colony of cooperating agents. IEEE Trans. Syst. Man Cybern. Part B (Cybern.) 26(1), 29–41 (1996)

Dorigo, M., Stützle, T.: Ant Colony Optimization. A Bradford Book. BRADFORD BOOK (2004)

Edwards, C.R.: The application of the Rademacher-Walsh transform to boolean function classification and threshold logic synthesis. IEEE Trans. Comput. 100(1), 48–62 (1975)MathSciNetCrossRef

10.

Frank, M.P.: Throwing computing into reverse. IEEE Spect. 54(9), 32–37 (2017)CrossRef

11.

Hadjam, F.Z., Moraga, C.: RIMEP2: evolutionary design of reversible digital circuits. ACM J. Emerg. Technol. Comput. Syst. (JETC) 11(3), 27 (2014)

12.

Hurst, S.L.: The Logical Processing of Digital Signals. Crane Russak & Company Inc./Edward Arnold, New York/London (1978)MATH

13.

Karpovsky, M.G., Stanković, R.S., Astola, J.T.: Spectral Logic and Its Applications for the Design of Digital Devices. Wiley, Hoboken (2008)

14.

Kerntopf, P., Perkowski, M., Podlaski, K.: Synthesis of reversible circuits: a view on the state-of-the-art. In: Proceedings of the 12th IEEE Conference on Nanotechnology (IEEE-NANO), pp. 1–6. IEEE (2012)

15.

Landauer, R.: Irreversibility and heat generation in the computing process. IBM J. Res. Dev. 5(3), 183–191 (1961)MathSciNetCrossRef

16.

Lechner, R.J.: A transform approach to logic design. IEEE Trans. Comput. 100(7), 627–640 (1970)CrossRef

17.

Li, M., Zheng, Y., Hsiao, M.S., Huang, C.: Reversible logic synthesis through ant colony optimization. In: Proceedings of the Design, Automation & Test in Europe Conference & Exhibition (DATE), pp. 307–310. IEEE (2010)

18.

Manna, P., Kole, D.K., Rahaman, H., Das, D.K., Bhattacharya, B.B.: Reversible logic circuit synthesis using genetic algorithm and particle swarm optimization. In: Proceedings of the International Symposium on Electronic System Design (ISED), pp. 246–250. IEEE (2012)

19.

Maslov, D., Dueck, G.W., Miller, D.M.: Techniques for the synthesis of reversible Toffoli networks. ACM Trans. Des. Autom. Electron. Syst. 12(4), 42–es (2007)

20.

Miller, D.M., Maslov, D., Dueck, G.W.: A transformation based algorithm for reversible logic synthesis. In: Proceedings of the 40th Annual Design Automation Conference, pp. 318–323. ACM (2003)

21.

Miller, D.M., Soeken, M., Drechsler, R.: Mapping NCV circuits to optimized Clifford+T circuits. In: Yamashita, S., Minato, S. (eds.) RC 2014. LNCS, vol. 8507, pp. 163–175. Springer, Cham (2014). https://doi.org/10.1007/978-3-319-08494-7_13CrossRef

22.

Nielsen, M.A., Chuang, I.L.: Quantum Computation and Quantum Information. Cambridge University Press (2010)

23.

Saeedi, M., Markov, I.: Synthesis and optimization of reversible circuits – a survey. ACM Comput. Surv. 45(2), 21:1–21:34 (2013)

24.

Saeedi, M., Zamani, M.S., Sedighi, M., Sasanian, Z.: Reversible circuit synthesis using a cycle-based approach. J. Emerg. Technol. Comput. Syst. 6(4), 1–26 (2010)CrossRef

25.

Soeken, M., Frehse, S., Wille, R., Drechsler, R.: RevKit: an open source toolkit for the design of reversible circuits. In: De Vos, A., Wille, R. (eds.) RC 2011. LNCS, vol. 7165, pp. 64–76. Springer, Heidelberg (2012). https://doi.org/10.1007/978-3-642-29517-1_6CrossRef

26.

Stanković, R.S., Astola, J.T.: Spectral Interpretation of Decision Diagrams. Springer, Heidelberg (2003). https://doi.org/10.1007/b97562CrossRefMATH

27.

Wang, X., Jiao, L., Li, Y., Qi, Y., Wu, J.: A variable-length chromosome evolutionary algorithm for reversible circuit synthesis. J. Multiple-Valued Log. Soft Comput. 25(6), 643–671 (2015)MathSciNet

28.

Wille, R., Drechsler, R.: Bdd-based synthesis of reversible logic. Int. J. Appl. Metaheuristic Comput. 1(4), 25–41 (2010)CrossRef

29.

Wille, R., Große, D., Teuber, L., Dueck, G.W., Drechsler, R.: RevLib: an online resource for reversible functions and reversible circuits. In: International Symposium on Multi-Valued Logic, pp. 220–225 (2008), RevLib. http://www.revlib.org

Titel: Ant Colony Optimization Implementation for Reversible Synthesis in Walsh-Hadamard Domain
verfasst von: Krzysztof Podlaski
Verlag: Springer International Publishing
Buch: Computational Science – ICCS 2020
Print ISBN: 978-3-030-50425-0

Electronic ISBN: 978-3-030-50426-7

Copyright-Jahr: 2020
DOI: https://doi.org/10.1007/978-3-030-50426-7_18

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"