Skip to main content
Fachgebiete
Automobil + Motoren Bauwesen + Immobilien Business IT + Informatik Elektrotechnik + Elektronik Energie + Nachhaltigkeit Finance + Banking Management + Führung Marketing + Vertrieb Maschinenbau + Werkstoffe Versicherung + Risiko
DE
EN
Bücher
Zeitschriften
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
SLX-Digitalkonferenz: Zukunftswerkstatt 2024

Mehr Umsatz mit Top-Kontakten

Am 7. Mai erfahren Sie, wie Vertriebsteams Leadgenerierung, Leadnurturing und Leadstrategien effizient steuern können.
Erweiterte Suche
Anmelden
nach oben
Erschienen in:
Self-explaining Digital Systems: Technical View, Implementation Aspects, and Completeness Kapitel lesen Erstes Kapitel lesen

2020 | OriginalPaper | Buchkapitel

8. Exact Synthesis of ESOP Forms

verfasst von : Heinz Riener, Rüdiger Ehlers, Bruno de O. Schmitt, Giovanni De Micheli

Erschienen in: Advanced Boolean Techniques

Verlag: Springer International Publishing

Einloggen

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

search-config
loading …

Abstract

We present an exact synthesis approach for computing Exclusive-or Sum-of-Products (ESOP) forms with a minimum number of product terms using Boolean satisfiability. Our approach finds one or more ESOP forms for a given Boolean function. The approach can deal with incompletely specified Boolean functions defined over many Boolean variables and is particularly fast if the Boolean function can be expressed with only a few product terms. We describe the formalization of the ESOP synthesis problem with a fixed number of terms as a decision problem and present search procedures for determining ESOP forms of minimum size. We further discuss how the search procedures can be relaxed to find ESOP forms of small sizes in reasonable time. We experimentally evaluate the performance of the SAT-based synthesis procedures on completely and incompletely specified Boolean functions.

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 Literal Selection in Switching Lattice Design
Nächstes Kapitel An Algorithm for Linear, Affine and Spectral Classification of Boolean Functions
Fußnoten
1
We use hexadecimal notation to shorten the string representation of the (binary) truth tables of Boolean functions.
 
3
The benchmarks and a detailed evaluation of the synthesis results can be found at https://​hriener.​github.​io/​misc/​2018_​easy.​html.
 
Literatur
1.
Amy, M., Maslov, D., Mosca, M., Roetteler, M.: A meet-in-the-middle algorithm for fast synthesis of depth-optimal quantum circuits. IEEE Trans. CAD Integr. Circuits Syst. 32(6), 818–830 (2013)CrossRef
2.
Audemard, G., Simon, L.: On the glucose SAT solver. Int. J. Artif. Intell. Tools 27(1), 1–25 (2018)CrossRef
3.
Barenco, A., Bennett, C.H., Cleve, R., Divincenzo, D.P., Margolus, N., Shor, P., Sleator, T., Smolin, J.A., Weinfurter, H.: Elementary gates for quantum computation. Phys. Rev. A: At. Mol. Opt. Phys. 52(5), 3457–3467 (1995)CrossRef
4.
Brayton, R.K., Mishchenko, A.: ABC: an academic industrial-strength verification tool. In: Proceedings of Computer Aided Verification, 22nd International Conference, CAV 2010, Edinburgh, July 15–19, 2010, pp. 24–40
5.
6.
7.
Eén, N., Sörensson, N.: An extensible SAT-solver. In: Theory and Applications of Satisfiability Testing, 6th International Conference, SAT 2003. Santa Margherita Ligure, Italy, May 5–8, 2003 Selected Revised Papers, pp. 502–518
8.
Fazel, K., Thornton, M.A., Rice, J.E.: ESOP-based Toffoli gate cascade generation. In: Pacific Rim Conference on Communications, Computers and Signal Processing (2007)
9.
Feynman, R.P.: Quantum mechanical computers. Opt. News 11, 11–20 (1985)CrossRef
10.
11.
Gaidukov, A.: Algorithm to derive minimum ESOP for 6-variable function. In: International Workshop on Boolean Problems, pp. 141–148 (2002)
12.
Goto, E., Takahasi, H.: Some theorems useful in threshold logic for enumerating Boolean functions. In: IFIP Congress, pp. 747–752 (1962)
13.
Kalay, U., Hall, D.V., Perkowski, M.A.: A minimal universal test set for self-test of EXOR-sum-of-products circuits. IEEE Trans. Comput. 49(3), 267–276 (2000)CrossRef
14.
Kamath, A.P., Karmarkar, N., Ramakrishnan, K.G., and Resende, M.G.C.: A continuous approach to inductive inference. Math. Program. 57, 215–238 (1992)MathSciNetMATHCrossRef
15.
Knuth, D.E.: The Art of Computer Programming, vol. 4. Fascicle 6: Satisfiability, 1st edn. Addison-Wesley Professional, Boston (2015)
16.
Kolesnikov, V., Schneider, T.: Improved garbled circuit: free XOR gates and applications. In: Proceedings Automata, Languages and Programming, 35th International Colloquium, ICALP 2008, Reykjavik, July 7–11, 2008, pp. 486–498
17.
Linke, N.M., Maslov, D., Rötteler, M., Debnath, S., Figgatt, C., Landsman, K.A., Wright, K., Monroe, C.R.: Experimental comparison of two quantum computing architectures. Quant. Phys. Comput. Sci. Emer. Technol. (2017). abs/1702.01852
18.
Maslov, D.: Advantages of using relative-phase Toffoli gates with an application to multiple control Toffoli optimization. Phys. Rev. A 93(2), 022311 (2016)CrossRef
19.
Mishchenko, A., Perkowski, M.A.: Fast heuristic minimization of exclusive-sums-of-products. In: Reed-Muller Workshop (2001)
20.
Mishchenko, A., Perkowski, M.A.: Logic synthesis of reversible wave cascades. In: International Workshop on Logic Synthesis, pp. 197–202 (2002)
21.
Mizuki, T., Otagiri, T., Sone, H.: An application of ESOP expressions to secure computations. J. Circuits Syst. Comput. 16(2), 191–198 (2007)MATHCrossRef
22.
Papakonstantinou, G.K.: A parallel algorithm for minimizing ESOP expressions. J. Circuits Syst. Comput. 23(1), 1450015 (2014)CrossRef
23.
Papakonstantinou, K.G., Papakonstantinou, G.: A nonlinear integer programming approach for the minimization of Boolean expressions. J. Circuits Syst. Comput. 29(10), 1850163 (2018)CrossRef
24.
Riener, H., Ehlers, R., Fey, G.: CEGAR-based EF synthesis of Boolean functions with an application to circuit rectification. In: 22nd Asia and South Pacific Design Automation Conference, ASP-DAC 2017, Chiba, January 16–19, 2017, pp. 251–256
25.
Sampson, M., Kalathas, M., Voudouris, D., Papakonstantinou, G.K.: Exact ESOP expressions for incompletely specified functions. Integration 45(2), 197–204 (2012)MATHCrossRef
26.
Sasao, T., Fujita, M. (eds.): Representations of Logic Functions Using EXOR Operators, pp. 29–54. Springer, New York (1996)
27.
Soeken, M., Roetteler, M., Wiebe, N., De Micheli, G.: Design automation and design space exploration for quantum computers. In: Design, Automation and Test in Europe, pp. 470–475 (2017)
28.
Soeken, M., Riener, H., Haaswijk, W., De Micheli, G.: The EPFL logic synthesis libraries (2018). arXiv e-prints 1805.05121
29.
Soeken, M., Mozafari, F., Schmitt, B., De Micheli, G.: Compiling permutations for superconducting QPUs. In: Design Automation Conference (2019)
30.
Stergiou, S., Papakonstantinou, G.K.: Exact minimization of ESOP expressions with less than eight product terms. J. Circuits Syst. Comput. 13(1), 1–15 (2004)CrossRef
Metadaten
Titel
Exact Synthesis of ESOP Forms
verfasst von
Heinz Riener
Rüdiger Ehlers
Bruno de O. Schmitt
Giovanni De Micheli
Copyright-Jahr
2020
Buch
Advanced Boolean Techniques

Print ISBN: 978-3-030-20322-1

Electronic ISBN: 978-3-030-20323-8

Copyright-Jahr: 2020

DOI
https://doi.org/10.1007/978-3-030-20323-8_8

Neuer Inhalt

    Bildnachweise