- Shopping Bag ( 0 items )
Other sellers (Hardcover)
-
All (8) from $108.05
-
New (6) from $108.05
-
Used (2) from $120.51
More About This Textbook
Overview
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 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 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 significantly differs from the design of traditional circuits. Nearly all steps in the design flow (like synthesis, verification, 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 flow exists so far.
In Towards a Design Flow for Reversible Logic, contributions to a design flow for reversible logic are presented. This includes advanced methods for synthesis, optimization, verification, and debugging. Formal methods like Boolean satisfiability and decision diagrams are thereby exploited. By combining the techniques proposed in the book, it is possible to synthesize reversible circuits representing large functions. Optimization approaches ensure that the resulting circuits are of small cost. Finally, a method for equivalence checking and automatic debugging allows to verify the obtained results and helps to accelerate the search for bugs in case of errors in the design. Combining the respective approaches, a first design flow for reversible circuits of significant size results.
Editorial Reviews
From the Publisher
From the reviews:“This is a book about the present and the future of computing machines. … At the end of the book a list of 144 refs are included giving the reader the possibility to know more than there are in the book. … the book represents an excellent text at a post-graduate level aiming to give to the researchers the basic ideas and techniques in this new emerging domain.” (Dumitru Stanomir, Zentralblatt MATH, Vol. 1210, 2011)
Product Details
Table of Contents
1 Introduction 1
2 Preliminaries 7
2.1 Background 7
2.1.1 Reversible Functions 7
2.1.2 Reversible Circuits 9
2.1.3 Quantum Circuits 13
2.2 Decision Diagrams 16
2.2.1 Binary Decision Diagrams 17
2.2.2 Quantum Multiple-valued Decision Diagrams 19
2.3 Satisfiability Solvers 21
2.3.1 Boolean Satisfiability 21
2.3.2 Extended SAT Solvers 22
3 Synthesis of Reversible Logic 27
3.1 Current Synthesis Steps 28
3.1.1 Embedding Irreversible Functions 28
3.1.2 Transformation-based Synthesis 30
3.2 BDD-based Synthesis 31
3.2.1 General Idea 32
3.2.2 Exploiting BDD Optimization 34
3.2.3 Theoretical Consideration 37
3.2.4 Experimental Results 39
3.3 SyReC: A Reversible Hardware Language 46
3.3.1 The SyReC Language 47
3.3.2 Synthesis of the Circuits 50
3.3.3 Experimental Results 53
3.4 Summary and Future Work 56
4 Exact Synthesis of Reversible Logic 57
4.1 Main Flow 58
4.2 SAT-based Exact Synthesis 61
4.2.1 Encoding for Toffoli Circuits 61
4.2.2 Encoding for Quantum Circuits 65
4.2.3 Handling Irreversible Functions 68
4.2.4 Experimental Results 70
4.3 Improved Exact Synthesis 76
4.3.1 Exploiting Higher Levels of Abstractions 77
4.3.2 Quantified Exact Synthesis 81
4.3.3 Experimental Results 84
4.4 Summary and Future Work 91
5 Embedding of Irreversible Functions 93
5.1 The Embedding Problem 94
5.2 Don't Care Assignment 96
5.2.1 Methods 96
5.2.2 Experimental Results 99
5.3 Synthesis with Output Permutation 100
5.3.1 General Idea 102
5.3.2 Exact Approach 104
5.3.3 Heuristic Approach 105
5.3.4 Experimental Results 106
5.4 Summary and Future Work 111
6 Optimization 113
6.1 Adding Lines to Reduce Circuit Cost 114
6.1.1 General Idea 114
6.1.2 Algorithm 116
6.1.3 Experimental Results 117
6.2 Reducing the Number of Circuit Lines 124
6.2.1 General Idea 125
6.2.2 Algorithm 127
6.2.3 Experimental Results 130
6.3 Optimizing Circuits for Linear Nearest Neighbor Architectures 131
6.3.1 NNC-optimal Decomposition 133
6.3.2 Optimizing NNC-optimal Decomposition 134
6.3.3 Experimental Results 138
6.4 Summary and Future Work 138
7 Formal Verification and Debugging 143
7.1 Equivalence Checking 144
7.1.1 The Equivalence Checking Problem 145
7.1.2 QMDD-based Equivalence Checking 145
7.1.3 SAT-based Equivalence Checking 148
7.1.4 Experimental Results 150
7.2 Automated Debugging and Fixing 154
7.2.1 The Debugging Problem 155
7.2.2 Determining Error Candidates 157
7.2.3 Determining Error Locations 161
7.2.4 Fixing Erroneous Circuits 165
7.2.5 Experimental Results 167
7.3 Summary and Future Work 173
8 Summary and Conclusions 175
References 177
Index 183