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
  • 4 Downloads / 240 Views

DOWNLOAD

REPORT


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