Logic Design of NanoICS

Contents......Page 5
1: Introduction......Page 25
1.1 Progress from micro- to nanoelectronics......Page 26
1.2 Logic design in spatial dimensions......Page 27
1.3.2 CAD of nanoICs......Page 30
1.3.3 Topology: 2-D vs. 3-D......Page 31
1.3.4 Prototyping technologies......Page 32
1.4.1 Data structures......Page 33
1.4.2 Assembling in 3-D......Page 36
1.4.3 Massive and parallel computation in nanodimensions......Page 37
1.4.4 Fault tolerance computing......Page 39
1.5 Example: hypercube structure of hierarchical FPGA......Page 40
1.5.2 Hierarchical FPGA as hypercube-like structure......Page 41
1.6 Summary......Page 42
1.7 Problems......Page 44
1.8 Further reading......Page 46
1.9 References......Page 47
2: Nanotechnologies......Page 51
2.1 Nanotechnologies......Page 52
2.2.1 Single-electronics......Page 53
Single-electron transistor......Page 54
Quantum-effect mesoscopic devices: quantum dot arrays......Page 56
2.2.2 Rapid single flux quantum devices......Page 57
2.3 Digital nanoscale circuits: gates vs. arrays......Page 58
Logic gates......Page 59
Multiterminal devices......Page 60
Parametron-based logic devices......Page 61
2.3.4 Switches in single-electron logic......Page 62
Switches and BDD-based models......Page 63
2.3.6 Neuron cell and cellular neural network design using SETs......Page 64
2.3.7 Single-electron systolic arrays......Page 65
Single-electron pump switch......Page 66
CMOL......Page 67
2.4.2 Other structures: nanowires......Page 68
2.5.1 Scaling limits of electronic devices......Page 69
2.5.2 Operational limits of nanoelectronic devices......Page 71
2.6 Summary......Page 72
2.7 Problems......Page 74
2.8 Further reading......Page 75
2.9 References......Page 81
3: Basics of Logic Design in Nanospace......Page 89
3.1.1 Definitions......Page 90
3.1.4 Cartesian product graphs......Page 91
3.1.5 Interconnection networks......Page 92
3.1.6 Decision tree......Page 93
3.1.7 Embedding of a guest graph in a host graph......Page 94
3.1.8 Binary decision diagrams......Page 95
3.2 Data structures for switching functions......Page 97
3.3 Sum-of-products expressions......Page 103
3.3.2 Computing the coefficients......Page 104
3.3.3 Restoration......Page 105
3.3.5 Hypercubes......Page 106
3.4.1 Formal synthesis......Page 107
3.4.2 Structural properties......Page 109
3.4.3 Decision tree reduction......Page 110
3.5.1 General form......Page 111
3.5.2 Computing the coefficients......Page 112
3.5.3 Flowgraphs......Page 113
3.5.4 Restoration......Page 114
3.5.6 Hypercube representation......Page 115
3.5.7 Polarity......Page 117
3.6.1 Formal design......Page 119
3.6.3 Decision tree reduction......Page 121
3.7 Arithmetic expressions......Page 122
3.7.1 General form......Page 123
3.7.3 Flowgraphs......Page 125
3.7.5 Useful rules......Page 127
3.7.7 Polarity......Page 128
3.8.1 Formal design......Page 130
3.8.2 Structural properties......Page 132
3.8.3 Decision tree reduction......Page 133
3.9 Summary......Page 134
3.10 Problems......Page 135
3.11 Further reading......Page 136
3.12 References......Page 138
4.1 Word-level data structures......Page 141
4.1.2 Computing by word-level expressions......Page 142
4.2 Word-level arithmetic expressions......Page 144
4.2.1 General form......Page 145
4.2.3 Computing the coefficients......Page 146
4.2.4 Restoration......Page 148
4.2.5 Useful properties......Page 149
4.2.6 Polarity......Page 150
Algebraic form......Page 151
4.3.1 General form......Page 153
4.3.3 Computing the coefficients......Page 154
4.3.4 Restoration......Page 156
4.3.5 Computing for a word-level set of assignments......Page 157
4.3.6 Word-level Shannon decision trees and diagrams......Page 158
4.4 Word-level Reed-Muller expressions......Page 160
4.4.1 General form......Page 162
4.4.3 Computing the coefficients......Page 163
4.4.4 Restoration......Page 164
4.4.5 Computing for a word-level set of assignments......Page 165
4.4.6 Word-level Davio decision trees and diagrams......Page 167
4.5 Summary......Page 168
4.6 Problems......Page 170
4.7 Further reading......Page 171
4.8 References......Page 172
5: Nanospace and Hypercube-Like Data Structures......Page 175
5.1.1 Requirement for representation in spatial dimensions......Page 176
5.1.2 Topologies......Page 177
5.2 Hypercube data structure......Page 178
5.2.1 Hypercube definition and characteristics......Page 179
5.2.2 Gray code......Page 180
5.2.4 Embedding in a hypercube......Page 182
5.3.1 Topological representation of products......Page 184
5.3.2 Assembling hypercubes for switching functions......Page 186
5.3.3 Assembling hypercubes for state assignments of finite state machines......Page 187
5.4.1 Extension of a hypercube......Page 190
5.5 Degree of freedom and rotation......Page 191
5.6 Coordinate description......Page 193
5.7 N-hypercube design for n > 3 dimensions......Page 195
5.8 Embedding a binary decision tree in N-hypercube......Page 197
5.9 Assembling......Page 200
5.10 Spatial topological measurements......Page 203
5.11 Summary......Page 205
5.12 Problems......Page 206
5.14 References......Page 208
6: Nanodimensional Multilevel Circuits......Page 211
6.1.3 N-hypercube model of multilevel circuits......Page 212
6.2.2 Metrics of N-hypercube......Page 213
6.2.3 Signal flowgraphs on an N-hypercube......Page 215
6.2.5 Library-based design paradigm......Page 217
6.2.6 Useful denotation......Page 218
6.3.2 Levelization and cascading......Page 220
6.4 Manipulation of N-hypercubes......Page 221
6.5.1 Experiment on evaluating the N-hypercube......Page 224
6.5.2 Experiment on evaluating the hybrid N-hypercube......Page 226
6.6 Summary......Page 227
Problems......Page 228
6.8 References......Page 233
7.1 Linear expressions......Page 235
7.1.1 General algebraic structure......Page 236
7.1.2 Linearization......Page 237
7.2.1 Grouping......Page 239
7.2.3 Weight assignment......Page 241
7.2.4 Masking......Page 243
7.3.1 Functions of two and three variables......Page 244
7.3.2 AND, OR, and EXOR functions of n variables......Page 245
7.3.3 “Garbage” functions......Page 247
7.4 Linear decision diagrams......Page 248
7.5 Representation of a circuit level by linear expression......Page 250
7.6.2 Examples......Page 253
7.7.1 The structure of coefficients......Page 255
7.7.2 Encoding......Page 257
7.7.3 W-trees......Page 259
7.8.1 Definition......Page 260
7.8.2 Grouping, weight assignment, and masking......Page 261
7.8.3 Linear expressions of elementary functions......Page 262
7.8.4 Linear decision diagrams......Page 263
7.8.5 Technique of computation......Page 264
7.9.1 Definition......Page 268
7.9.2 Grouping, weight assignment, and masking......Page 269
7.9.4 Linear decision diagrams......Page 270
7.10 Summary......Page 271
7.11 Problems......Page 273
7.12 Further reading......Page 276
7.13 References......Page 278
8: Event-Driven Analysis of Hypercube-Like Topology......Page 279
8.1.1 Detection of change......Page 280
8.1.2 Symmetric properties of Boolean difference......Page 286
8.2.2 Boolean difference, Davio tree, and N-hypercube......Page 287
8.3.1 Event-driven analysis of switching function properties: dependence, sensitivity, and fault detection......Page 289
8.3.2 Useful rules......Page 294
8.3.3 Probabilistic model......Page 297
8.4 Matrix models of change......Page 298
8.4.1 Boolean difference with respect to a variable in matrix form......Page 299
8.4.2 Boolean difference with respect to a vector of variables in matrix form......Page 300
8.5.1 Model for direct change......Page 302
8.5.2 Model for inverse change......Page 303
8.7 Generating Reed-Muller expressions by logic Taylor series......Page 307
8.8.1 Arithmetic analog of Boolean difference......Page 311
8.8.2 Arithmetic analog of logic Taylor expansion......Page 312
8.9 Summary......Page 313
8.10 Problems......Page 315
8.11 Further reading......Page 319
8.12 References......Page 321
9: Nanodimensional Multivalued Circuits......Page 325
9.1.1 Operations of multivalued logic......Page 326
9.1.2 Multivalued algebras......Page 331
9.1.3 Data structures......Page 332
9.2.1 Terminology......Page 334
9.2.2 Generalized Reed-Muller transform......Page 335
9.2.3 Generalized arithmetic transform......Page 337
9.2.4 Relation of spectral representations to data structures, behavior models, and massive parallel computing......Page 340
9.3.1 Operations in GF(m)......Page 343
9.3.2 Shannon trees for ternary functions......Page 344
9.3.4 Embedding decision tree in hypercube-like structure......Page 345
9.4.1 Formal definition of change for multivalued functions......Page 346
9.4.2 Computing logic difference......Page 351
9.5.1 Logic Taylor expansion of a multivalued function......Page 354
9.5.3 Computing Reed-Muller expressions in matrix form......Page 355
9.5.4 N-hypercube representation......Page 356
9.6 Linear word-level expressions of multivalued functions......Page 358
Phase 1: Partition......Page 359
Phase 2: Encoding......Page 360
Phase 3: Representation of a function by linear word-level arithmetic expression......Page 361
9.6.3 Manipulation of the linear model......Page 362
9.6.4 Library of linear models of multivalued gates......Page 363
9.6.5 Representation of a multilevel, multivalued circuit......Page 364
9.6.6 Linear decision diagrams......Page 366
9.7.1 Linear word-level for MAX expressions......Page 367
9.7.2 Network representation by linear models......Page 368
9.8 Summary......Page 370
9.9 Problems......Page 371
9.10 Further reading......Page 374
9.11 References......Page 378
10: Parallel Computation in Nanospace......Page 383
10.1 Data structures and massive parallel computing......Page 384
10.2.1 Cellular arrays......Page 385
10.2.2 Systolic arrays......Page 386
10.3.1 Design technique......Page 387
10.3.2 Formal model of computation in a linear array......Page 388
10.3.3 Parallel-pipelined computing......Page 389
10.4.1 Factorization of transform matrix......Page 390
10.4.2 Design based on logic Taylor expansion......Page 391
10.5 Computing Boolean differences......Page 394
10.6 Computing arithmetic expressions......Page 395
10.7 Computing Walsh expressions......Page 396
10.8 Tree-based network for manipulating a switching function......Page 397
10.9 Hypercube arrays......Page 398
10.10 Summary......Page 400
10.11 Problems......Page 401
10.12 Further reading......Page 403
10.13 References......Page 406
11: Fault-Tolerant Computation......Page 409
11.2.1 Noise......Page 410
11.2.2 Nanogates......Page 411
11.2.3 Noise models......Page 412
11.2.4 Fault-tolerant computing......Page 415
11.3 Neural networks......Page 416
11.3.3 Multivalued feedforward networks......Page 417
11.4.1 The model of a gate for input random pulse streams......Page 418
11.4.2 Data structure......Page 420
11.4.3 Primary statistics......Page 421
11.4.4 Stochastic encoding......Page 422
11.5 Von Neumann’s model on reliable computation with unreliable components......Page 423
11.5.2 Formalization......Page 424
11.6.1 Definitions......Page 425
11.6.2 Fault-tolerance technique......Page 427
11.8 Further reading......Page 428
11.9 References......Page 432
12.1 Information-theoretical measures at various levels of design in nanodimensions......Page 435
12.1.2 Dynamic characteristics......Page 436
12.1.4 measures on data structures......Page 437
12.2 Information-theoretical measures in logic design......Page 438
12.2.1 Information-theoretical standpoint......Page 439
12.2.3 Conditional entropy and relative information......Page 440
12.2.4 Entropy of a variable and a function......Page 442
12.2.5 Mutual information......Page 444
12.3 Information measures of elementary switching functions......Page 445
12.4 Information-theoretical measures in decision trees......Page 450
12.4.1 Decision trees......Page 451
12.4.2 Information-theoretical notation of switching function expansion......Page 452
Information notation of pD and nD expansion......Page 453
12.4.3 Optimization of variable ordering in a decision tree......Page 455
12.5 Information measures in the N-hypercube......Page 456
12.6.1 Information notation of S expansion......Page 458
12.6.2 Information notations of pD and nD expansion......Page 459
12.6.3 Information criterion for decision tree design......Page 460
12.7 Summary......Page 464
12.8 Problems......Page 465
Remarks on information measures in decision diagrams......Page 467
12.9 Further reading......Page 469
12.10 References......Page 473