Decision diagram techniques for micro- and nanoelectronic design handbook

Select an Action

Place Hold(s)
Add to My Lists
Email
Print

Title:

Publication Information:

Boca Raton, FL : CRC Press, 2006

ISBN:

9780849334245

Subject Term:

Decision-making -- Mathematical models

Decision logic tables

Microelectronics

Nanotechnology

Added Author:

Yanushkevich, Svetlana N.

Available:*

Library	Item Barcode	Call Number	Material Type	Item Category 1	Status
Searching... PSZ JB	30000010103626	T57.95 D42 2004	Open Access Book	Book	Searching... Unknown

Decision diagram (DD) techniques are very popular in the electronic design automation (EDA) of integrated circuits, and for good reason. They can accurately simulate logic design, can show where to make reductions in complexity, and can be easily modified to model different scenarios.

Presenting DD techniques from an applied perspective, Decision Diagram Techniques for Micro- and Nanoelectronic Design Handbook provides a comprehensive, up-to-date collection of DD techniques. Experts with more than forty years of combined experience in both industrial and academic settings demonstrate how to apply the techniques to full advantage with more than 400 examples and illustrations. Beginning with the fundamental theory, data structures, and logic underlying DD techniques, they explore a breadth of topics from arithmetic and word-level representations to spectral techniques and event-driven analysis. The book also includes abundant references to more detailed information and additional applications.

Decision Diagram Techniques for Micro- and Nanoelectronic Design Handbook collects the theory, methods, and practical knowledge necessary to design more advanced circuits and places it at your fingertips in a single, concise reference.

Author Notes

Yanushkevich, Svetlana N.; Miller, D. Michael; Shmerko, Vlad P.; Stankovic, Radomir S.

Preface	p. xxv
I Fundamentals of Decision Diagram Techniques	p. 1
1 Introduction	p. 3
1.1 Data structures for the representation of discrete functions	p. 3
1.2 Decision tables	p. 9
1.3 Graphical data structures	p. 10
1.4 Spectral techniques	p. 11
1.5 Stochastic models and information theoretic measures	p. 16
1.6 CAD of micro- and nanoelectronic circuits	p. 18
1.7 Further reading	p. 19
2 Data Structures	p. 21
2.1 Introduction	p. 21
2.2 Truth tables	p. 22
2.3 Algebraic representations	p. 23
2.4 AND-OR expressions	p. 25
2.5 Relevance to other data structures	p. 27
2.6 Relationship of data structures	p. 32
2.7 Further reading	p. 34
3 Graphical Data Structures	p. 37
3.1 Introduction	p. 37
3.2 Graphs	p. 38
3.3 Decision trees	p. 43
3.4 Shape of decision diagrams	p. 52
3.5 Embedding decision trees and diagrams into various topological structures	p. 60
3.6 Examples with hierarchical FPGA configuration	p. 62
3.7 Voronoi diagrams and Delaunay triangulations	p. 63
3.8 Further reading	p. 72
4 AND-EXOR Expressions, Trees, and Diagrams	p. 79
4.1 Introduction	p. 79
4.2 Terminology and classification of AND-EXOR expressions	p. 80
4.3 Algebraic representation	p. 83
4.4 Graphical representation	p. 93
4.5 Transeunt triangle representation	p. 102
4.6 Triangle topology	p. 102
4.7 Further reading	p. 112
5 Arithmetic Representations	p. 119
5.1 Introduction	p. 119
5.2 Algebraic description	p. 120
5.3 Graphical representations	p. 126
5.4 Further reading	p. 132
6 Word - Level Representations	p. 135
6.1 Introduction	p. 135
6.2 Arithmetic word-level computation in matrix form	p. 139
6.3 Computing word-level expressions in the form of corteges	p. 145
6.4 Further reading	p. 154
7 Spectral Techniques	p. 157
7.1 Introduction	p. 157
7.2 Spectral transforms	p. 158
7.3 Haar and related transforms	p. 164
7.4 Computing spectral coefficients	p. 167
7.5 Discrete wavelet transforms	p. 172
7.6 Further reading	p. 172
8 Information - Theoretical Measures	p. 179
8.1 Introduction	p. 179
8.2 Information-theoretical measures	p. 180
8.3 Information measures of elementary switching function of two variables	p. 188
8.4 Information-theoretical measures and symmetry	p. 191
8.5 Information and flexibility	p. 196
8.6 Further reading	p. 200
9 Event - Driven Analysis	p. 209
9.1 Introduction	p. 209
9.2 Formal definition of change in a binary system	p. 210
9.3 Generating Reed-Muller expressions with logic Taylor series	p. 222
9.4 Computing Boolean differences on decision diagrams	p. 222
9.5 Models of logic networks in terms of change	p. 227
9.6 Other logic differential operators	p. 231
9.7 Further reading	p. 235
II Decision Diagram Techniques for Switching Functions	p. 239
10 Introduction	p. 241
10.1 Genesis and evolution of decision diagrams	p. 241
10.2 Various aspects of the construction of decision diagrams	p. 244
10.3 Applications of decision diagrams	p. 249
10.4 Implementation and technologies	p. 252
10.5 Further reading	p. 257
11 Classification of Decision Diagrams	p. 261
11.1 Introduction	p. 261
11.2 Classification of decision diagrams with respect to constant nodes	p. 263
11.3 Classification of decision diagrams with respect to non-terminal nodes	p. 265
11.4 Classification of decision diagrams with respect to decomposition rules	p. 266
11.5 Classification of decision diagrams with respect to labels at the edges	p. 267
11.6 Further reading	p. 271
12 Variable Ordering in Decision Diagrams	p. 273
12.1 Introduction	p. 273
12.2 Adjacent variable interchange	p. 275
12.3 Exact BDD minimization techniques	p. 276
12.4 Problem specific ordering techniques	p. 277
12.5 Dynamic variable ordering	p. 279
12.6 Advanced techniques	p. 281
12.7 Path length	p. 285
12.8 Reordering in BDD packages	p. 286
12.9 Further reading	p. 287
13 Spectral Decision Diagrams	p. 293
13.1 The theoretical background of spectral interpretation of decision diagram techniques	p. 293
13.2 Decision tree and spectrum of switching function	p. 294
13.3 Bases of spectral transforms and decision diagrams	p. 296
13.4 Fixed polarity spectral representations	p. 296
13.5 Spectral decision diagram techniques	p. 300
13.6 Further reading	p. 303
14 Linearly Transformed Decision Diagrams	p. 305
14.1 Introduction	p. 305
14.2 Manipulation of variables using affine transforms	p. 307
14.3 Linearly transformed decision trees and diagrams	p. 312
14.4 Examples of linear transform techniques	p. 317
14.5 Further reading	p. 319
15 Decision Diagrams for Arithmetic Circuits	p. 329
15.1 Introduction	p. 329
15.2 Binary adders	p. 329
15.3 Multipliers	p. 333
15.4 Word-level decision diagrams for arithmetic circuits	p. 336
15.5 Further reading	p. 340
16 Edge - Valued Decision Diagrams	p. 345
16.1 Introduction	p. 345
16.2 Terminology and abbreviations of edge-valued decision trees and diagrams	p. 346
16.3 Spectral interpretation of edge-valued decision diagrams	p. 349
16.4 Binary moment diagrams	p. 353
16.5 Further reading	p. 354
17 Word - Level Decision Diagrams	p. 357
17.1 Introduction	p. 357
17.2 Multiterminal decision trees and diagrams	p. 358
17.3 Spectral interpretation of word-level decision diagrams	p. 360
17.4 Binary moment trees and diagrams	p. 361
17.5 Haar spectral diagrams	p. 366
17.6 Haar spectral transform decision trees	p. 368
17.7 Other decision diagrams	p. 369
17.8 Further reading	p. 369
18 Minimization via Decision Diagrams	p. 373
18.1 Introduction	p. 373
18.2 Terminology	p. 374
18.3 Minimization using hypercubes	p. 378
18.4 Minimization of AND-EXOR expressions	p. 383
18.5 Further reading	p. 387
19 Decision Diagrams for Incompletely Specified Functions	p. 391
19.1 Introduction	p. 391
19.2 Representation of incompletely specified functions	p. 392
19.3 Decision diagrams for incompletely specified logic functions	p. 394
19.4 Incompletely specified decision diagrams	p. 399
19.5 Further reading	p. 407
20 Probabilistic Decision Diagram Techniques	p. 413
20.1 Introduction	p. 413
20.2 BDD methods for computing output probability	p. 414
20.3 Cross-correlation of functions	p. 420
20.4 Further reading	p. 426
21 Power Consumption Analysis using Decision Diagrams	p. 429
21.1 Introduction	p. 429
21.2 Switching activity	p. 431
21.3 Decision diagrams for power consumption estimation	p. 433
21.4 Further reading	p. 441
22 Formal Verification of Circuits	p. 447
22.1 Introduction	p. 447
22.2 Verification of combinational circuits	p. 448
22.3 Verification using other types of diagrams	p. 453
22.4 Verification of sequential circuits	p. 458
22.5 Further reading	p. 460
23 Ternary Decision Diagrams	p. 465
23.1 Terminology and abbreviations	p. 465
23.2 Definition of ternary decision trees	p. 467
23.3 EXOR ternary decision trees	p. 469
23.4 Bit-level ternary decision trees	p. 469
23.5 Word-level ternary decision trees	p. 471
23.6 Arithmetic transform ternary decision diagrams	p. 473
23.7 The relationships between arithmetic transform ternary decision diagrams and other decision trees	p. 473
23.8 Ternary decision diagrams and differential operators for switching functions	p. 474
23.9 Further reading	p. 476
24 Information - Theoretical Measures in Decision Diagrams	p. 481
24.1 Introduction	p. 481
24.2 Information-theoretical measures	p. 481
24.3 Information-theoretical measures in decision trees	p. 484
24.4 Information-theoretical measures in multivalued functions	p. 492
24.5 Ternary and pseudo-ternary decision trees	p. 500
24.6 Entropy-based minimization using pseudo-ternary trees	p. 503
24.7 Further reading	p. 506
25 Decomposition Using Decision Diagrams	p. 509
25.1 Introduction	p. 509
25.2 Decomposition types	p. 513
25.3 Decomposition based on BDD structure	p. 518
25.4 Decomposition based on BDD operations	p. 526
25.5 Further reading	p. 536
26 Complexity of Decision Diagrams	p. 545
26.1 Introduction	p. 545
26.2 Specific functions	p. 546
26.3 Bounds	p. 549
26.4 Complemented edges	p. 552
26.5 Path length	p. 554
26.6 Further reading	p. 561
27 Programming of Decision Diagrams	p. 567
27.1 Introduction	p. 567
27.2 Representation of nodes	p. 568
27.3 Representation of decision diagrams	p. 568
27.4 Construction of decision diagrams	p. 569
27.5 Construction of decision diagrams based on truth tables and variable ordering	p. 573
27.6 Calculations with decision diagrams	p. 575
27.7 Further reading	p. 576
III Decision Diagram Techniques for Multivalued Functions	p. 579
28 Introduction	p. 581
28.1 Multivalued logic	p. 581
28.2 Representation of multivalued functions	p. 583
28.3 Spectral theory of multivalued functions	p. 584
28.4 Multivalued decision trees and diagrams	p. 586
28.5 Further reading	p. 588
29 Multivalued Functions	p. 595
29.1 Introduction	p. 595
29.2 Multivalued functions	p. 596
29.3 Multivalued logic	p. 596
29.4 Galois fields	p. 602
29.5 Fault models based on the concept of change	p. 606
29.6 Further reading	p. 610
30 Spectral Transforms of Multivalued Functions	p. 613
30.1 Introduction	p. 613
30.2 Reed-Muller spectral transform	p. 614
30.3 Arithmetic transform	p. 622
30.4 Partial Reed-Muller-Fourier transforms	p. 627
30.5 Relation of spectral representations	p. 627
30.6 Further reading	p. 629
31 Classification of Multivalued Decision Diagrams	p. 635
31.1 Introduction	p. 635
31.2 Background theory	p. 636
31.3 Construction of EVDDs	p. 638
31.4 Illustrative examples	p. 643
31.5 Further reading	p. 650
32 Event - Driven Analysis in Multivalued Systems	p. 655
32.1 Introduction	p. 655
32.2 Multivalued difference	p. 656
32.3 Generation of Reed-Muller expressions	p. 662
32.4 Further reading	p. 666
IV Selected Topics of Decision Diagram Techniques	p. 669
33 Introduction	p. 671
33.1 Relationship between decision diagrams and spatial structures	p. 671
33.2 Decision diagrams for reversible computation	p. 678
33.3 Special types of decision diagrams and hybrid techniques	p. 678
33.4 Developing of new decision diagrams	p. 680
33.5 Further reading	p. 680
34 Three - Dimensional Techniques	p. 685
34.1 Introduction	p. 685
34.2 Spatial structures	p. 687
34.3 Hypercube data structure	p. 689
34.4 Assembling of hypercubes	p. 694
34.5 N-hypercube definition	p. 696
34.6 Embedding a binary decision tree into an N-hypercube	p. 702
34.7 Spatial topological measurements	p. 707
34.8 Embedding decision diagrams into incomplete N-hypercubes	p. 710
34.9 Further reading	p. 711
35 Decision Diagrams in Reversible Logic	p. 719
35.1 Introduction	p. 719
35.2 Reversible and quantum circuits	p. 720
35.3 Decision diagram techniques	p. 729
35.4 Further reading	p. 737
36 Decision Diagrams on Quaternion Groups	p. 741
36.1 Terminology	p. 742
36.2 Introduction	p. 743
36.3 Group-theoretic approach to decision diagrams	p. 744
36.4 Decision diagrams on quaternion group	p. 748
36.5 Further reading	p. 752
37 Linear Word - Level Decision Diagrams	p. 757
37.1 Introduction	p. 757
37.2 Linearization	p. 757
37.3 Linear arithmetic expressions	p. 758
37.4 Linear arithmetic expressions of elementary functions	p. 763
37.5 Linear decision diagrams	p. 767
37.6 Representation of a circuit level by linear word-level expression	p. 769
37.7 Linear decision diagrams for circuit representation	p. 772
37.8 Linear word-level expressions of multivalued functions	p. 773
37.9 Linear nonarithmetic word-level representation of multivalued functions	p. 782
37.10 Further reading	p. 784
38 Fibonacci Decision Diagrams	p. 789
38.1 Introduction	p. 789
38.2 Terminology and abbreviations for Fibonacci decision trees and diagrams	p. 790
38.3 Generalized Fibonacci numbers and codes	p. 794
38.4 Fibonacci decision trees	p. 795
38.5 Fibonacci decision trees and contracted Fibonacci p-codes	p. 802
38.6 Spectral Fibonacci decision diagrams	p. 803
38.7 Further reading	p. 805
39 Techniques of Computing via Taylor - Like Expansions	p. 809
39.1 Terminology	p. 810
39.2 Computing Reed-Muller expressions	p. 812
39.3 Computing arithmetic expressions via arithmetic Taylor expansion	p. 822
39.4 Computing Walsh expressions via Taylor expansion	p. 829
39.5 Further reading	p. 839
40 Developing New Decision Diagrams	p. 845
40.1 Introduction	p. 845
40.2 Spectral tools for generation of decision diagrams	p. 845
40.3 Group theoretic approach to designing decision diagrams	p. 857
40.4 Further reading	p. 860
41 Historical Perspectives and Open Problems	p. 867
41.1 Trends in decision diagram techniques	p. 867
41.2 New design and optimization strategies	p. 867
41.3 Extension of the area of application	p. 874
41.4 Nanocircuit design - a new frontier for decision diagrams	p. 875
41.5 Further reading	p. 876
V Appendix	p. 889
Appendix-A Algebraic Structures for the Fourier Transform on Finite Groups	p. 891
Appendix-B Fourier Analysis on Groups	p. 897
Appendix-C Discrete Walsh Functions	p. 907
Appendix-D The Basic Operations for Ternary and Quaternary Logic	p. 913
Index	p. 915

Available:*

On Order

Summary

Summary

Author Notes

Table of Contents