Fundamentals of Switching Theory and Logic Design: A Hands on Approach

ISBN-13: 9781441939456 / Angielski / Miękka / 2010 / 342 str.

Jaakko Astola; Radomir S. Stankovic

Opis

Switching theory and logic design provide mathematical foundations and tools for digital system design that is an essential part in the research and development in almost all areas of modern technology. The vast complexity of modern digital systems implies that they can only be handled by computer aided design tools that are built on sophisticated mathematical models. Fundamentals of Switching Theory and Logic Design is aimed at providing an accessible introduction to these mathematical techniques that underlie the design tools and that are necessary for understanding their capabilities and limitations. As is typical to many disciplines a high level of abstraction enables a unified treatment of many methodologies and techniques as well as provides a deep understanding of the subject in general. The drawback is that without a hands-on touch on the details it is difficult to develop an intuitive understanding of the techniques. We try to combine these views by providing hands-on examples on the techniques while binding these to the more general theory that is developed in parallel. For instance, the use of vector spaces and group theory unifies the spectral (Fourier-like) interpretation of polynomial, and graphic (decision diagrams) representations of logic functions, as well as provides new methods for optimization of logic functions. Consequently, Fundamentals of Switching Theory and Logic Design discusses the fundamentals of switching theory and logic design from a slightly alternative point of view and also presents links between switching theory and related areas of signal processing and system theory. It also covers the core topics recommended in IEEE/ACM curricula for teaching and study in this area. Further, it contains several elective sections discussing topics for further research work in this area

Spis treści

Preface. Acronyms. 1. SETS, RELATIONS, AND FUNCTIONS. 1. Sets. 2. Relations. 3. Functions. 4. Representations of Logic Functions. 5. Factored Expressions. 6. Exercises and Problems. 2. ALGEBRAIC STRUCTURES FOR LOGIC DESIGN. 1. Algebraic Structure. 2. Finite Groups. 3. Finite Rings. 4. Finite Fields. 5. Homomorphisms. 6. Matrices. 7. Vector spaces. 8. Algebra. 9. Boolean Algebra. 10. Graphs. 11. Exercises and Problems. 3. FUNCTIONAL EXPRESSIONS FOR SWITCHING FUNCTIONS. 1. Shannon Expansion Rule. 2. Reed-Muller Expansion Rules. 3. Fast Algorithms for Calculation of RM-expressions. 4. Negative Davio Expression. 5. Fixed Polarity Reed-Muller Expressions. 6. Algebraic Structures for Reed-Muller Expressions. 7. Interpretation of Reed-Muller Expressions. 8 Kronecker Expressions. 9. Word-Level Expressions. 10. Walsh Expressions. 11. Walsh Functions and Switching Variables. 12. Walsh Series. 13. Relationships Among Expressions. 14. Generalizations to Multiple-Valued Functions. 15. Exercises and Problems. 4. DECISION DIAGRAMS FOR REPRESENTATION OF SWITCHING FUNCTIONS. 1. Decision Diagrams. 2. Decision Diagrams over Groups. 3. Construction of Decision Diagrams. 4. Shared Decision Diagrams. 5. Multi-terminal binary decision diagrams. 6. Functional Decision Diagrams. 7. Kronecker decision diagrams. 8. Pseudo-Kronecker decision diagrams. 9. Spectral Interpretation of Decision Diagrams. 10. Reduction of Decision Diagrams. 11. Exercises and Problems. 5. CLASSIFICATION OF SWITCHING FUNCTIONS. 1. NPN-classification. 2. SD-Classification. 3. LP-classification. 4. Universal Logic Modules. 5. Exercises and Problems. 6. SYNTHESIS WITH MULTIPLEXERS. 1. Synthesis with Multiplexers. 2. Applications of Multiplexers. 3. Demultiplexers. 4. Synthesis with Demultiplexers. 5. Applications of Demultiplexers. 6. Exercises and Problems. 7. REALIZATIONS WITH ROM. 1. Realizations with ROM. 2. Two-level Addressing in ROM Realizations. 3. Characteristics of Realizations with ROM. 4. Exercises and Problems. 8. REALIZATIONS WITH PROGRAMMABLE LOGIC ARRAYS. 1. Realizations with PLA. 2. The optimization of PLA. 3. Two-level Addressing of PLA. 4. Folding of PLA. 5. Minimization of PLA by Characteristic Functions. 6. Exercises and Problems. 9. UNIVERSAL CELLULAR ARRAYS. 1. Features of Universal Cellular Arrays. 2. Realizations with Universal Cellular Arrays. 3. Synthesis with Macro Cells. 4. Exercises and Problems. 10. FIELD PROGRAMMABLE LOGIC ARRAYS. 1. Synthesis with FPGAs. 2. Synthesis with Antifuse-Based FPGAs. 3. Synthesis with LUT-FPGAs. 4. Exercises and Problems. 11. BOOLEAN DIFFERENCE AND APPLICATIONS IN TESTING LOGIC NETWORKS. 1. Boolean Difference. 2. Properties of the Boolean Difference. 3. Calculation of the Boolean Difference. 4. Boolean Difference in Testing Logic Networks. 5. Easily Testable Logic Networks. 6. Easily Testable Realizations from PPRM-expressions. 7. Easily Testable Realizations from GRM-expressions. 8. Exercises and Problems. 12. SEQUENTIAL NETWORKS. 1. Basic Sequential Machines. 2. State Tables. 3. Conversion of Sequential Machines. 4. Minimization of States. 5. Incompletely Specified Machines. 6. State Assignment. 7. Decomposition of Sequential Machines. 8. Exercises and Problems. 13. REALIZATION OF SEQUENTIAL NETWORKS. 1. Memory Elements. 2. Synthesis of Sequential Networks. 3. Realization of Binary Sequential Machines. 4. Realization of Synchronous Sequential Machines. 5. Pulse Mode Sequential Networks. 6. Asynchronous Sequential Networks. 7. Races and Hazards. 8. Exercises and Problems. References. Index

O autorze

Radomir Stankovic received the B.Sc. degree in electronic engineering from the Faculty of Electronics, University of Ni v, Serbia, Yugoslavia in 1976, and M.Sc. and Ph.D. degrees in applied mathematics from the Faculty of Electrical Engineering, University of Belgrade, Serbia, Yugoslavia, in 1984 and 1986, respectively. Currently, he is a Professor at Department of Computer Science, University of Ni v, Serbia, Yugoslavia. His research interests include spectral techniques, switching theory and multiple-valued logic, and signal processing. He is a member of IEICE.

Jaakko Astola (Fellow IEEE) received B.Sc., M.S.c, Licentiate and Ph.D. degrees in mathematics (specializing in error-correcting codes) from Turku University, Finland, in 1972, 1973, 1975, and 1978 respectively. From 1993 he has been Professor of Signal Processing and Director of Tampere International Center for Signal Processing leading a group of about 60 scientists and was nominated Academy Professor by Academy of Finland (2001-2006). His research interests include signal processing, coding theory, spectral techniques and statistics.