| INHALTSVERZEICHNIS | öffnen |
Contents
I Introduction 1
1 Introduction 5
1.1 VLSI: Opportunity and Challenge 5
1.1.1 Manufacturing Technology 5
1.1.2 Design technology 6
1.1.3 Why VLSI 7
1.2 VLSI Processes 7
1.3 Design Styles 8
1.3.1 Design Decomposition 8
1.3.2 Logic (Circuit) Design Styles 10
1.4 Overview of Optimal Logic Synthesis 14
1.4.1 Area-Time Tradeoff Curves 15
1.4.2 The Technology Independent View - A Bit-Serial Full Adder Circuit 16
1.4.3 The Technology Dependent View - Technology Mapping 18
1.4.4 Testing - Is What I Fabricated What I Wanted?19
1.4.5 Graph Models and Finite State Machines 21
1.4.6 Successors and Predecessors 24
1.5 Graph Algorithms and Complexity 24
1.5.1 Complexity 24
1.5.2 Computing the Product of Sets of Sets 26
1.5.3 Longest Paths 27
1.5.4 Backtracing 29
1.5.5 Complexity of Computing the Longest Path 32
1.6 Asymptotic Complexity (or just complexity)33
1.6.1 Worst Case Asymptotic Upper Bound Complexity 34
1.6.2 Complexity of Algorithms 36
1.6.3 Practical Complexities 36
1.7 Brief Summary of MOS Device Behavior 37
1.8 Notes 39
1.9 Summary 39
1.10 Problems 39
2 A Quick Tour of Logic Synthesis with the Help of a Simple Example 47
2.1 A Simple Case Conversion Circuit 47
2.2 First Refinement 49
2.3 The Transform Block 50
2.3.1 The CC Block 52
2.3.2 An Optimized Transform Block 53
2.4 The Command Interpreter 54
2.4.1 Checking for Equality 54
2.4.2 Optimizing the Command Interpreter 54
2.5 Technology Mapping 57
2.6 Problems 58
II Two Level Logic Synthesis 73
3 Boolean Algebras 77
3.1 Sets, Relations, and Functions 77
3.1.1 Sets 77
3.1.2 Relations 79
3.1.3 Reflexive Binary Relations 80
3.1.4 Functions 84
3.2 Partial Orders 85
3.2.1 Partially Ordered Sets 86
3.2.2 Hasse Diagrams 87
3.2.3 The Meet and Join Operations 87
3.2.4 Totally Ordered Sets, Well-Ordered Sets, and Induction 89
3.2.5 Lattices 90
3.2.6 Definition of Boolean Algebras 92
3.2.7 Examples and Properties of Boolean Algebras 92
3.3 Boolean Functions 95
3.3.1 Boolean Formulae 96
3.3.2 Boolean Functions 97
3.3.3 Boole's Expansion Theorem 98
3.3.4 The Minterm Canonical Form 99
[weiter lesen] |
|
|
|
|
| REGISTER | öffnen |
Index
Symbol
ε -moves, 295
ω operation on a set of tapes, 391
FA
- star operation on sets of strings, 374
Aabsorption, 95, 143, 147, 412
absorptive, 90, 92
abstraction
- existential, 309, 309, 395
- universal, 309
Ada, 50
Aho, 509
algebra, 86
- Boolean, 77, 86, 92, 421
- carrier, 86, 93, 205
- class, 93
- partition, 352
- switching, 92, 100, 132
algebraic, 420, 421, 429, 441, 478
- expression, 419
- product, 419
algebraic expression
- kernel, 425
algebraic system, 85, 90, 92
algorithms
- BEST_DIVISOR, 434
- BEST_KERNEL, 434
- BOOL_DIV, 434
- BOOL_FACTOR, 435
- COMMON_CUBE, 432
- DIVIDE, 429, 432
- DIVISOR, 429, 432, 435
- FACTOR, 429, 431
- GEN_FACTOR, 431, 432
- GOOD_FACTOR, 434, 435
- LF, 432
- MAKE_CUBE_FREE, 432, 433
- MAKE_SPARSE, 190
- ONE_LEVEL-0_KERNEL, 433
- PARTITION, 269
- QUICK_DECOMPOSITION, 439
- QUICK_DIVISOR, 433, 434
- QUICK_EXTRACTION, 439
- QUICK_FACTOR, 433, 435, 439, 447
- quick_factor, 435
- STATE_EQUIVALENCE, 269
- WEAK_DIV, 425, 429, 433, 434
all-zero, 346
alphabet
- input, 261
- output, 261
alterm , 133
arrival time, 514
ASCII, 47, 52, 53, 216, 523
ASIC, 10
associative, 90, 92
asymptotic complexity, 25
asynchronous, 343
ATPG, 65, 462, 469, 478, 484, 488
attraction, 343
automaton, 264
- accepting, 264
- deterministic, 264
- final, 264
- nondeterministic, 264
- property, 393
- task, 393
Bbacktrace, 487
- multiple, 487
backtracking, 480, 483
BCP, 335-337, 340
BDD
- =Binary Decision Diagram, 308
- characteristic functions, 306
- complement edge, 223
- dynamically re-ordering, 233
- garbage collection, 233
- regular edge, 223
- typical sizes, 306
binate, 143, 422
bipartition, 198
Blake, 134
BLIF, 58, 60-64, 444, 501, 502, 520
BLIF, 410
Boole, 92, 98, 139, 140, 192, 196
Boolean, 419, 421, 429
Boolean algebra
- atoms, 101, 103
Boolean difference, 213, 468
Boolean functions, 101
Boolean network, 410, 455, 456, 459
- cyclic, 456
- prime and irredundant, 469
bound, 152
- greatest lower, 88
- least upper, 88
- lower, 88, 149, 153, 336, 340
- upper, 88, 153, 340
bounding, 340
branch-and-bound, 149, 152-154, 33 337, 509
Brown, 134, 418
CCAD, 6, 7
canonical form
- BDD, 219
- maxterm, 99, 177
- minterm, 99, 135
canonical forms, 220
cardinality, 186
carry-bypass, 58, 491
carry-skip, 491
Cartesian plane, 87, 90, 114
Cartesian product, 78, 423
circuit
- multi-level, 410
- two-level, 129, 131, 132
clause, 133, 329, 337
CNF, 133, 197
co-domain, 96
co-kernel, 426-429
- level-0, 427
cofactor, 148, 192, 193, 201
cofactors, 98
column
- essential, 146
commutative, 90, 92
compatibility, 326
compatible
- class set of, 330
- maximal, 329
- prime, 329
complement, 91, 93
complementation, 91, 93, 201, 203, 343, 412
- recursive, 201
complete product, 177
complete sum, 137
completely specified, 261, 348, 429
complexity
- linear, 277
consensus, 94, 134, 135, 191, 204, 489
- iterated, 134, 137
constant propagation, 422
containment
- single-cube, 192
controllability, 462
Corasick, 509
core
- cyclic, 142
cover
- monotonic, 195
- unate, 195
covering
- binate, 143, 328, 334-336
- DAG, 507-509
- graph, 506
- rectangle, 436
- tree, 509
- UCP, 143
- unate, 143, 153, 160
cube-free, 425
CUT, 475
cycle sets, 388
cyclic, 148, 152, 340
DD-algorithm, 481, 487, 492
DAG, 456, 506, 510
DAGON, 506, 508, 509
DC-set, 107, 190, 191, 203
DDs (Decision Diagrams), 243
De Morgan, 201, 203, 414, 417
decision diagrams, 243
delay, 129
DeMorgan, 94
deterministic image of FST's, 383
DFA
- definition, 370
DFS
- lowlink, 323
digraph, 456
discriminants, 99
disjunction, 133
distributive, 92, 138, 421
- equalities, 92
- inequalities, 91
distributivity, 94, 331, 412
division, 422-424, 436
- algebraic, 424
- Boolean, 424, 434
- weak, 424, 425
divisor, 429, 435, 436
- algebraic, 424, 426
- Boolean, 423
- primary, 425, 426
DNF, 133
domain, 84, 96, 107
dominance, 336
- column or variable, 147, 339
- row or constraint, 146, 338
don't care, 48, 52, 54, 64, 106, 136, 137, 141, 192, 326, 436, 455, 457, 462, 491
- external, 460, 463
- implicit, 457, 464
[weiter lesen] |
|
|
|