Binary Decision Diagrams and Applications for VLSI CAD by Shin-ichi Minato

By Shin-ichi Minato

Symbolic Boolean manipulation utilizing binary determination diagrams (BDDs) has been effectively utilized to a large choice of initiatives, really in very huge scale integration (VLSI) computer-aided layout (CAD). the idea that of choice graphs as an summary illustration of Boolean features dates again to the early paintings through Lee and Akers. within the final ten years, BDDs have came across frequent use as a concrete information constitution for symbolic Boolean manipulation. With BDDs, features may be developed, manipulated, and in comparison via easy and effective graph algorithms. considering the fact that Boolean services can characterize not only electronic circuit features, but in addition such mathematical domain names as units and kinfolk, a wide selection of CAD difficulties may be solved utilizing BDDs.
`Binary choice Diagrams and functions for VLSI CAD offers invaluable details for either those people who are new to BDDs in addition to to very long time aficionados.' -from the Foreword through Randal E. Bryant.
`Over the prior ten years ... BDDs have attracted the eye of many researchers as a result of their suitability for representing Boolean capabilities. they're now accepted in lots of functional VLSI CAD structures. ... this ebook can function an creation to BDD innovations and ... it provides numerous new principles on BDDs and their purposes. ... many machine scientists and engineers may be drawn to this ebook when you consider that Boolean functionality manipulation is a primary process not just in electronic process layout but in addition in exploring quite a few difficulties in laptop science.' - from the Preface through Shin-ichi Minato.

Show description

Read Online or Download Binary Decision Diagrams and Applications for VLSI CAD PDF

Similar design books

Sensing the 21st Century City: The Net City Close-up and Remote (Architectural Design November December 2005, Vol. 75, No. 6)

Will towns exist within the subsequent century? Or will all over the place be city? modern verbal exchange and transportation networks let for higher city dispersal, but towns proceed to centralise nice densities of actions and ideas. What shape will the twenty first century urban take? And what function will architects and concrete designers take up shaping the long run kind of town?

Model Generation in Electronic Design

Version iteration in digital layout covers quite a lot of version purposes and study. The ebook starts by way of describing a version generator to create part types. It is going directly to speak about ASIC layout and ASIC library new release. This part contains chapters at the specifications for constructing and ASIC library, a case examine within which very important is used to create this type of library, and the research and outline of the accuracy required in modeling interconnections in ASIC layout.

Design of Demining Machines

In consistent attempt to put off mine possibility, foreign mine motion neighborhood has been constructing safeguard, potency and cost-effectiveness of clearance tools. Demining machines became invaluable while engaging in humanitarian demining the place the mechanization of demining offers better defense and productiveness.

Extra resources for Binary Decision Diagrams and Applications for VLSI CAD

Sample text

It generates cube sets from BDDs directly without temporarily generating redun- dant cube sets in the process. • It can handle don't cares. • The algorithm can be extended to manage multiple output functions. 1 5 I-path enumeration method. In the remainder of this chapter, we first survey a conventional method for generating cube sets from BDDs, and next we present our algorithm to generate prime-irredundant cube sets. We then show experimental results of our method, followed by conclusion. 1 PREVIOUS WORKS Akers[Ake78] presented a simple method for generating cube sets from BDDs by enumerating the I-paths.

LfoJ 'Ifrl- Ifoll· We noted earlier that isop is obtained as the union set of the three parts, as shown in Fig. 2. To avoid cube set manipulation, we implemented the method in such a way that the results of cubes are directly dumped out to a file. On each recursive call, we push the processing literal to a stack, which we call a cube stack. When a tautology function is detected, the current content of the cube stack is appended to the output file as a cube. This approach is efficient because we manipulate only BDDs, no matter how large the result of the cube set becomes.

Time (sec)" shows the total time of loading the circuit data, ordering the input variables, and generating the BODs. The columns (B),(C) and (D) shows the results of the experiments without the heuristic method of variable ordering. For column (B) we use the original order of the circuit data, for column (C) the order is original but the reverse of that for (B), and for column (D) the order is random. The ordering method is very effective except in a few cases which are insensitive to the order.

Download PDF sample

Rated 4.42 of 5 – based on 46 votes