Binary Decision Diagrams Theory and Implementation
For someone with a hammer the whole world looks like a nail. Within the last 10-13 years Binar·y Decision Diagmms (BDDs) have become the state-of-the-art data structure in VLSI CAD for representation and ma nipulation of Boolean functions. Today, BDDs ar
- PDF / 14,891,800 Bytes
- 205 Pages / 439.323 x 665.939 pts Page_size
- 5 Downloads / 264 Views
BINARY DECISION DIAGRAMS Theory and Implementation
Rolf DRECHSLER Albert-Ludwigs-University Freiburg, Germany
•
Bernd BECKER Albert-Ludwigs-University Freiburg, Germany
Springer Science+Business Media, LLC
A C.I.P. Catalogue record for this book is available from the Library of Congress.
Printed on acid-free paper
ISBN 978-1-4419-5047-5 ISBN 978-1-4757-2892-7 (eBook) DOI 10.1007/978-1-4757-2892-7 All Rights Reserved
© 1998 Springer Science+Business Media New York
Originally published by Kluwer Academic Publishers in 1998 Softcover reprint of the hardcover 1st edition 1998
No part of the material protected by this copyright notice may be reproduced or utilized in any form or by any means, electronic or mechanical, including photocopying, recording or by any information storage and retrieval system, without writlen permission from the copyright owner.
Ta
Heidi and Bernd and Christina and Kurt
CONTENTS
PREFACE
IX
1
INTRODUCTION
1
2
NOTATIONS AND DEFINITIONS
5
3
DECISION DIAGRAMS
9
4
5
3.1
Introduction
9
3.2
General Definition, Structural Restrictions
9
3.3
Binary Decision Diagram
11
3.4
Extensions of Binary Decision Diagrams
15
3.5
Reduction Concepts
20
3.6
Evaluation and Satisfiability
28
THEORETICAL ASPECTS
31
4.1
Relation between BDDs and FDDs
31
4.2
Exponential Trade-Offs
37
4.3
Exponential Lower Bounds
39
4.4
Further Theoretical Studies
43
MINIMIZATION OF DECISION DIAGRAMS: CLASSICAL METHODS
45
5.1
Introduction
45
5.2
Exchange of Neighboring Variables
46
v
BINARY DECISION DIAGRAMS
Vl
5.3 5.4 5.5 5.6
6
Experimental Results Recent Developments and Future Trends
Introduction BDDs Representing (Partially) Symmetrie Functions Symmetries of Completely Specified Functions Symmetries of Incompletely Specified Functions Experimental Results
ALTERNATIVE MINIMIZATION CONCEPTS 7.1 7.2 7.3 7.4 7.5 7.6 7.7 7.8
8
Heuristic Minimization
MINIMIZATION USING SYMMETRIES 6.1 6.2 6.3 6.4 6.5
7
Exact Minimization
57 57 57 61 68 82
Simulation based Approach
93 93 93 94 100
EA for Incompletely Specified Boolean Functions
103
Heuristic Learning
109 114 124
Introduction Evolutionary Algorithms Standard EA
Experimental Results Recent Developments and Future Trends
IMPLEMENTATIONAL CONCEPTS 8.1 8.2 8.3 8.4 8.5 8.6 8.7
47 48 53 56
Introduction Symbolic Simulation with BDDs Recursive Synthesis Reordering Based Synthesis Seeure Implementation Experimental Results Recent Developments and Future Trends
127 127 127 128 131 146 151 163
vii
Contents
9
A CASE STUDY: TWO-LEVEL AND/EXOR
MINIMIZATION 9.1 9.2 9.3 9.4 9.5 9.6
Introduction AND /EXOR Classes Previous Work Use of Decision Diagrams Experimental Results Recent Developments and Future Trends
165 165 165 166 167 175 182
10 CONCLUSIONS
183
REFERENCES
185
INDEX
199
PREFACE
For someone with a hammer the whole world looks like a nail.
Within the last 10-13 years Binar·y Decision Diagmms (BDDs) have become the state-of-the-art data structure in VLSI CAD for representation and manipulatio
Data Loading...
