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

2010 | Buch

Introduction Kapitel lesen Erstes Kapitel lesen

Towards a Design Flow for Reversible Logic

verfasst von: Robert Wille, Rolf Drechsler

Verlag: Springer Netherlands

Enthalten in: Springer Professional "Wirtschaft+Technik" , Springer Professional "Technik"

Einloggen, um Zugang zu erhalten
insite
SUCHEN

Über dieses Buch

The development of computing machines found great success in the last decades. But the ongoing miniaturization of integrated circuits will reach its limits in the near future. Shrinking transistor sizes and power dissipation are the major barriers in the development of smaller and more powerful circuits. Reversible logic p- vides an alternative that may overcome many of these problems in the future. For low-power design, reversible logic offers signi?cant advantages since zero power dissipation will only be possible if computation is reversible. Furthermore, quantum computation pro?ts from enhancements in this area, because every quantum circuit is inherently reversible and thus requires reversible descriptions. However, since reversible logic is subject to certain restrictions (e.g. fanout and feedback are not directly allowed), the design of reversible circuits signi?cantly differs from the design of traditional circuits. Nearly all steps in the design ?ow (like synthesis, veri?cation, or debugging) must be redeveloped so that they become applicable to reversible circuits as well. But research in reversible logic is still at the beginning. No continuous design ?ow exists so far. Inthisbook,contributionstoadesign?owforreversiblelogicarepresented.This includes advanced methods for synthesis, optimization, veri?cation, and debugging.

Inhaltsverzeichnis

Frontmatter
Chapter 1. Introduction
Abstract
The ongoing miniaturization of integrated circuits will reach its limits in the near future. Shrinking transistor sizes and power dissipation are the major barriers in the development of smaller and more powerful circuits. Reversible logic provides an alternative that may overcome many of these problems in the future. For low-power design, reversible logic offers significant advantages since zero power dissipation will only be possible if computation is reversible. Furthermore, quantum computation profits from enhancements in this area, because every quantum circuit inherently is reversible and thus requires reversible descriptions. However, since reversible logic is subject to certain restrictions (e.g. fanout and feedback are not directly allowed), the design of reversible circuits significantly differs from the design of traditional circuits. No continuous design flow exists so far.
Robert Wille, Rolf Drechsler
Chapter 2. Preliminaries
Abstract
This chapter provides the basic definitions and notations to keep the remaining book self-contained. The chapter is divided into three parts. In the first section, Boolean functions, reversible functions, and the respective circuit descriptions are introduced. This builds the basis for all approaches described in this book. Since many of the proposed techniques exploit decision diagrams and satisfiability solvers, respectively, the basic concepts of these core techniques are also introduced in the last two sections. All descriptions are thereby kept brief, but references for a more in-depth treatment are provided.
Robert Wille, Rolf Drechsler
Chapter 3. Synthesis of Reversible Logic
Abstract
Synthesis is the most important step while building complex circuits. In the last years, first approaches for reversible logic have been introduced. The first section of this chapter briefly reviews them. In particular, it is shown how irreversible functions must be embedded into reversible ones in order to become applicable to existing synthesis methods. Afterwards, two new synthesis approaches are introduced. While the first one exploits Binary Decision Diagrams, the second one makes use of a new programming language. This enables synthesis of more complex reversible circuits than by previous approaches.
Robert Wille, Rolf Drechsler
Chapter 4. Exact Synthesis of Reversible Logic
Abstract
In contrast to (heuristic) approaches, exact synthesis methods determine a minimal solution, i.e. a circuit with a minimal number of gates or quantum cost, respectively. Ensuring minimality often causes an enormous computational overhead and thus exact approaches are only applicable to relatively small functions. Nevertheless, it is worth to consider exact methods, since they (1) allow finding smaller circuits than the currently best known realizations, (2) allow the evaluation of the quality of heuristic approaches, and (3) allow the computation of minimal circuits as building blocks for larger circuits. This chapter proposes new methods based on Boolean satisfiability (SAT). More precisely, exact synthesis for both, reversible circuits and quantum circuits, is presented. Besides pure SAT solvers, also SMT solvers, problem specific solvers, and finally solvers supporting quantifiers are utilized for this purpose.
Robert Wille, Rolf Drechsler
Chapter 5. Embedding of Irreversible Functions
Abstract
Quite often reversible circuits should be synthesized for irreversible functions. Thus, the problem of embedding is an important aspect. For this purpose, additional lines are introduced resulting in constant inputs, garbage outputs, and don’t care conditions, which have to be assigned to concrete values. Further options exist how (i.e. in which order) to arrange the outputs in the circuit to be synthesized. Overall, functions can be embedded in different ways whereby the concrete don’t care assignments as well as the chosen output arrangement may have a significant impact on the resulting circuit size. In this chapter, the different aspects of embedding mentioned above are investigated in detail. First, strategies for the don’t care assignment. Afterwards, the order of outputs in the function to be synthesized is considered.
Robert Wille, Rolf Drechsler
Chapter 6. Optimization
Abstract
The primary task of synthesis approaches is to generate circuits that realize the desired functions. Secondarily, it should be ensured that the resulting circuits are as compact as possible. However, the results obtained by synthesis approaches often are sub-optimal. Consequently, in common design flows optimization approaches are applied after synthesis. In this chapter, three new optimization approaches are introduced—each with an own focus on a particular cost metric. The first one considers the reduction of the well-established quantum cost (used in quantum circuits) and the transistor cost (used in CMOS implementations), respectively. The second approach considers the line count in a circuit. Finally, an optimization method is introduced which takes so called Nearest Neighbor Cost (NNC) into account.
Robert Wille, Rolf Drechsler
Chapter 7. Formal Verification and Debugging
Abstract
This chapter introduces approaches for formal verification and debugging and therewith completes the proposed approaches towards a design flow for reversible logic. Verification is an essential step that ensures whether obtained designs in fact realize the desired functionality or not. In the first part of this chapter, two equivalence checkers are proposed. The first approach employs decision diagram techniques, while the second one uses Boolean satisfiability. However, while verification methods can be used to detect the existence of errors, they do not provide any information about the source of the error. Thus, in the second part of this chapter, it is shown how the debugging process can be accelerated by using an automatic debugging method.
Robert Wille, Rolf Drechsler
Chapter 8. Summary and Conclusions
Abstract
In this book, a design flow for reversible logic has been proposed. That is, methods ranging from synthesis, embedding, optimization, verification, and debugging have been introduced and experimentally evaluated. Combining the respective approaches, a design flow results that already can handle functions and circuits of notable size. The uniform RevLib-format for reversible functions and circuits (see www.​revlib.​org) thereby builds the basis to link the respective steps together. The respective approaches are available by RevKit (see www.​revkit.​org). So, designer of reversible circuits have a first continuous and consistent flow to create their circuits.
Robert Wille, Rolf Drechsler
Backmatter
Metadaten
Titel
Towards a Design Flow for Reversible Logic
verfasst von
Robert Wille
Rolf Drechsler
Copyright-Jahr
2010
Verlag
Springer Netherlands
Electronic ISBN
978-90-481-9579-4
Print ISBN
978-90-481-9578-7
DOI
https://doi.org/10.1007/978-90-481-9579-4

Neuer Inhalt

    Bildnachweise