Logic Design of NanoICS

by Yanushkevich; Svetlana N.

• ISBN13: 9780849327667
• ISBN10: 0849327660
• Edition: 1st
• Format: Hardcover
• Copyright: 2004-10-28
• Publisher: CRC Press

Summary

Today's engineers will confront the challenge of a new computing paradigm, relying on micro- and nanoscale devices. Logic Design of NanoICs builds a foundation for logic in nanodimensions and guides you in the design and analysis of nanoICs using CAD. The authors present data structures developed toward applications rather than a purely theoretical treatment.Requiring only basic logic and circuits background, Logic Design of NanoICs draws connections between traditional approaches to design and modern design in nanodimensions. The book begins with an introduction to the directions and basic methodology of logic design at the nanoscale, then proceeds to nanotechnologies and CAD, graphical representation of switching functions and networks, word-level and linear word-level data structures, 3-D topologies based on hypercubes, multilevel circuit design, and fault-tolerant computation in hypercube-like structures. The authors propose design solutions and techniques, going beyond the underlying technology to provide more applied knowledge.This design-oriented reference is written for engineers interested in developing the next generation of integrated circuitry, illustrating the discussion with approximately 250 figures and tables, 100 equations, 250 practical examples, and 100 problems. Each chapter concludes with a summary, references, and a suggested reading section.

Table of Contents

Preface	xv
Acknowledgments	xxiii
Introduction	1	(26)
Progress from micro- to nanoelectronics	2	(1)
Logic design in spatial dimensions	3	(3)
Towards computer aided design of nanoICs	6	(3)
Contemporary CAD of ICs	6	(1)
CAD of nanoICs	6	(1)
Topology: 2-D vs. 3-D	7	(1)
Prototyping technologies	8	(1)
Methodology	9	(7)
Data structures	9	(3)
Assembling in 3-D	12	(1)
Massive and parallel computation in nanodimensions	13	(2)
Fault tolerance computing	15	(1)
Analysis, characterization, and information measures	16	(1)
Example: hypercube structure of hierarchical FPGA	16	(2)
FPGA based on multiinput multioutput switching	17	(1)
Hierarchical FPGA as hypercube-like structure	17	(1)
Summary	18	(2)
Problems	20	(2)
Further reading	22	(1)
References	23	(4)
Nanotechnologies	27	(38)
Nanotechnologies	28	(1)
Nanoelectronic devices	29	(5)
Single-electronics	29	(4)
Rapid single flux quantum devices	33	(1)
Resonant-tunneling devices	34	(1)
Digital nanoscale circuits: gates vs. arrays	34	(9)
Voltage-state logic: library of gates	35	(2)
Charge state logic	37	(1)
Single-electron memory	38	(1)
Switches in single-electron logic	38	(2)
Interconnect problem in voltage-state devices	40	(1)
Neuron cell and cellular neural network design using SETs	40	(1)
Single-electron systolic arrays	41	(2)
Parallel computation in nanoscale circuits: bit-level vs. word-level models	43	(1)
Molecular electronics	43	(2)
CMOS-molecular electronics	43	(1)
Other structures: nanowires	44	(1)
Nanotechnology-enhanced microelectronics	45	(1)
Scaling and fabrication	45	(3)
Scaling limits of electronic devices	45	(2)
Operational limits of nanoelectronic devices	47	(1)
Summary	48	(2)
Problems	50	(1)
Further reading	51	(6)
References	57	(8)
Basics of Logic Design in Nanospace	65	(52)
Graphs	66	(7)
Definitions	66	(1)
Directed graphs	67	(1)
Undirected graphs	67	(1)
Cartesian product graphs	67	(1)
Interconnection networks	68	(1)
Decision tree	69	(1)
Embedding of a guest graph in a host graph	70	(1)
Binary decision diagrams	71	(2)
Data structures for switching functions	73	(6)
Sum-of-products expressions	79	(4)
General form	80	(1)
Computing the coefficients	80	(1)
Restoration	81	(1)
Useful rules	82	(1)
Hypercubes	82	(1)
Shannon decision trees and diagrams	83	(4)
Formal synthesis	83	(2)
Structural properties	85	(1)
Decision tree reduction	86	(1)
Reed-Muller expressions	87	(8)
General form	87	(1)
Computing the coefficients	88	(1)
Flowgraphs	89	(1)
Restoration	90	(1)
Useful rules	91	(1)
Hypercube representation	91	(2)
Polarity	93	(2)
Decision trees and diagrams	95	(3)
Formal design	95	(2)
Structural properties	97	(1)
Decision tree reduction	97	(1)
Arithmetic expressions	98	(8)
General form	99	(2)
Computing the coefficients	101	(1)
Flowgraphs	101	(2)
Restoration	103	(1)
Useful rules	103	(1)
Hypercube representation	104	(1)
Polarity	104	(2)
Decision trees and diagrams	106	(4)
Formal design	106	(2)
Structural properties	108	(1)
Decision tree reduction	109	(1)
Summary	110	(1)
Problems	111	(1)
Further reading	112	(2)
References	114	(3)
Word-Level Data Structures	117	(34)
Word-level data structures	117	(3)
Computing by word-level set of assignments	118	(1)
Computing by word-level expressions	118	(2)
Word-level arithmetic expressions	120	(9)
General form	121	(1)
Masking operator	122	(1)
Computing the coefficients	122	(2)
Restoration	124	(1)
Useful properties	125	(1)
Polarity	126	(1)
Computing for a word-level set of assignments	127	(2)
Word-level sum-of-products expressions	129	(7)
General form	129	(1)
Masking operator	130	(1)
Computing the coefficients	130	(2)
Restoration	132	(1)
Computing for a word-level set of assignments	133	(1)
Word-level Shannon decision trees and diagrams	134	(2)
Word-level Reed-Muller expressions	136	(8)
General form	138	(1)
Masking operator	139	(1)
Computing the coefficients	139	(1)
Restoration	140	(1)
Computing for a word-level set of assignments	141	(2)
Word-level Davio decision trees and diagrams	143	(1)
Summary	144	(2)
Problems	146	(1)
Further reading	147	(1)
References	148	(3)
Nanospace and Hypercube-Like Data Structures	151	(36)
Spatial structures	152	(2)
Requirement for representation in spatial dimensions	152	(1)
Topologies	153	(1)
Hypercube data structure	154	(6)
Hypercube definition and characteristics	155	(1)
Gray code	156	(2)
Hamming distance	158	(1)
Embedding in a hypercube	158	(2)
Assembling of hypercubes	160	(6)
Topological representation of products	160	(2)
Assembling hypercubes for switching functions	162	(1)
Assembling hypercubes for state assignments of finite state machines	163	(3)
N-hypercube definition	166	(1)
Extension of a hypercube	166	(1)
Structural components	167	(1)
Degree of freedom and rotation	167	(2)
Coordinate description	169	(2)
N-hypercube design for n > 3 dimensions	171	(2)
Embedding a binary decision tree in N-hypercube	173	(3)
Assembling	176	(3)
Spatial topological measurements	179	(2)
Summary	181	(1)
Problems	182	(2)
Further reading	184	(1)
References	184	(3)
Nanodimensional Multilevel Circuits	187	(24)
Graph-based models in logic design of multilevel networks	188	(1)
DAG-based representation of multilevel circuits	188	(1)
Decision diagram based representation of circuits	188	(1)
N-hypercube model of multilevel circuits	188	(1)
Library of N-hypercubes for elementary logic functions	189	(7)
Structure of the library	189	(1)
Metrics of N-hypercube	189	(2)
Signal flowgraphs on an N-hypercube	191	(2)
Manipulation of N-hypercube	193	(1)
Library-based design paradigm	193	(1)
Useful denotation	194	(2)
Hybrid design paradigm: N-hypercube and DAG	196	(1)
Embedding a DAG in N-hypercube	196	(1)
Levelization and cascading	196	(1)
Manipulation of N-hypercubes	197	(3)
Numerical evaluation of 3-D structures	200	(3)
Experiment on evaluating the N-hypercube	200	(2)
Experiment on evaluating the hybrid N-hypercube	202	(1)
Summary	203	(6)
Further reading	209	(1)
References	209	(2)
Linear Word-Level Models of Multilevel Circuits	211	(44)
Linear expressions	211	(4)
General algebraic structure	212	(1)
Linearization	213	(2)
Linear arithmetic expressions	215	(5)
Grouping	215	(2)
Computing of the coefficients in the linear expression	217	(1)
Weight assignment	217	(2)
Masking	219	(1)
Linear arithmetic expressions of elementary functions	220	(4)
Functions of two and three variables	220	(1)
AND, OR, and EXOR functions of n variables	221	(2)
``Garbage'' functions	223	(1)
Linear decision diagrams	224	(2)
Representation of a circuit level by linear expression	226	(3)
Linear decision diagrams for circuit representation	229	(2)
The basic statement	229	(1)
Examples	229	(2)
Technique for manipulating the coefficients	231	(5)
The structure of coefficients	231	(2)
Encoding	233	(2)
W-trees	235	(1)
Linear word-level sum-of-products expressions	236	(8)
Definition	236	(1)
Grouping, weight assignment, and masking	237	(1)
Linear expressions of elementary functions	238	(1)
Linear decision diagrams	239	(1)
Technique of computation	240	(4)
Linear word-level Reed-Muller expressions	244	(3)
Definition	244	(1)
Grouping, weight assignment, and masking	245	(1)
Linear Reed-Muller expressions of primitives	246	(1)
Linear decision diagrams	246	(1)
Summary	247	(2)
Problems	249	(3)
Further reading	252	(2)
References	254	(1)
Event-Driven Analysis of Hypercube-Like Topology	255	(46)
Formal definition of change in a binary system	256	(7)
Detection of change	256	(6)
Symmetric properties of Boolean difference	262	(1)
Computing Boolean differences	263	(2)
Boolean difference and N-hypercube	263	(1)
Boolean difference, Davio tree, and N-hypercube	263	(2)
Models of logic networks in terms of change	265	(9)
Event-driven analysis of switching function properties: dependence, sensitivity, and fault detection	265	(5)
Useful rules	270	(3)
Probabilistic model	273	(1)
Matrix models of change	274	(4)
Boolean difference with respect to a variable in matrix form	275	(1)
Boolean difference with respect to a vector of variables in matrix form	276	(2)
Models of directed changes in algebraic form	278	(5)
Model for direct change	278	(1)
Model for inverse change	279	(4)
Local computation via partial Boolean difference	283	(1)
Generating Reed-Muller expressions by logic Taylor series	283	(4)
Arithmetic analogs of Boolean differences and logic Taylor expansion	287	(2)
Arithmetic analog of Boolean difference	287	(1)
Arithmetic analog of logic Taylor expansion	288	(1)
Summary	289	(2)
Problems	291	(4)
Further reading	295	(2)
References	297	(4)
Nanodimensional Multivalued Circuits	301	(58)
Introduction to multivalued logic	302	(8)
Operations of multivalued logic	302	(5)
Multivalued algebras	307	(1)
Data structures	308	(2)
Spectral technique	310	(9)
Terminology	310	(1)
Generalized Reed-Muller transform	311	(2)
Generalized arithmetic transform	313	(3)
Relation of spectral representations to data structures, behavior models, and massive parallel computing	316	(3)
Multivalued decision trees and decision diagrams	319	(3)
Operations in GF(m)	319	(1)
Shannon trees for ternary functions	320	(1)
Shannon and Davio trees for quaternary functions	321	(1)
Embedding decision tree in hypercube-like structure	321	(1)
Concept of change in multivalued circuits	322	(8)
Formal definition of change for multivalued functions	322	(5)
Computing logic difference	327	(3)
Generation of Reed-Muller expressions	330	(4)
Logic Taylor expansion of a multivalued function	330	(1)
Computing Reed-Muller expressions	331	(1)
Computing Reed-Muller expressions in matrix form	331	(1)
N-hypercube representation	332	(2)
Linear word-level expressions of multivalued functions	334	(9)
Approach to linearization	335	(1)
Algorithm for linearization of multivalued functions	335	(3)
Manipulation of the linear model	338	(1)
Library of linear models of multivalued gates	339	(1)
Representation of a multilevel, multivalued circuit	340	(2)
Linear decision diagrams	342	(1)
Remarks on computing details	343	(1)
Linear nonarithmetic word-level representation of multivalued functions	343	(3)
Linear word-level for MAX expressions	343	(1)
Network representation by linear models	344	(2)
Summary	346	(1)
Problems	347	(3)
Further reading	350	(4)
References	354	(5)
Parallel Computation in Nanospace	359	(26)
Data structures and massive parallel computing	360	(1)
Arrays	361	(2)
Cellular arrays	361	(1)
Systolic arrays	362	(1)
Tree-structured networks	363	(1)
Linear systolic arrays for computing logic functions	363	(3)
Design technique	363	(1)
Formal model of computation in a linear array	364	(1)
Parallel-pipelined computing	365	(1)
Computing Reed-Muller expressions	366	(4)
Factorization of transform matrix	366	(1)
Design based on logic Taylor expansion	367	(3)
Computing Boolean differences	370	(1)
Computing arithmetic expressions	371	(1)
Computing Walsh expressions	372	(1)
Tree-based network for manipulating a switching function	373	(1)
Hypercube arrays	374	(2)
Summary	376	(1)
Problems	377	(2)
Further reading	379	(3)
References	382	(3)
Fault-Tolerant Computation	385	(26)
Definitions	386	(1)
Probabilistic behavior of nanodevices	386	(6)
Noise	386	(1)
Nanogates	387	(1)
Noise models	388	(3)
Fault-tolerant computing	391	(1)
Neural networks	392	(2)
Threshold networks	393	(1)
Stochastic feedforward neural networks	393	(1)
Multivalued feedforward networks	393	(1)
Stochastic computing	394	(5)
The model of a gate for input random pulse streams	394	(2)
Data structure	396	(1)
Primary statistics	397	(1)
Stochastic encoding	398	(1)
Von Neumann's model on reliable computation with unreliable components	399	(2)
Architecture	400	(1)
Formalization	400	(1)
Faulty hypercube-like computing structures	401	(3)
Definitions	401	(2)
Fault-tolerance technique	403	(1)
Summary	404	(1)
Further reading	404	(4)
References	408	(3)
Information Measures in Nanodimensions	411	(42)
Information-theoretical measures at various levels of design in nanodimensions	411	(3)
Static characteristics	412	(1)
Dynamic characteristics	412	(1)
Combination of static and dynamic characteristics	413	(1)
measures on data structures	413	(1)
Information-theoretical measures in logic design	414	(7)
Information-theoretical standpoint	415	(1)
Quantity of information	416	(1)
Conditional entropy and relative information	416	(2)
Entropy of a variable and a function	418	(2)
Mutual information	420	(1)
Joint entropy	421	(1)
Information measures of elementary switching functions	421	(5)
Information-theoretical measures in decision trees	426	(6)
Decision trees	427	(1)
Information-theoretical notation of switching function expansion	428	(3)
Optimization of variable ordering in a decision tree	431	(1)
Information measures in the N-hypercube	432	(2)
Information-theoretical measures in multivalued functions	434	(6)
Information notation of S expansion	434	(1)
Information notations of pD and nD expansion	435	(1)
Information criterion for decision tree design	436	(4)
Summary	440	(1)
Problems	441	(4)
Further reading	445	(4)
References	449	(4)
Index	453