Introduction to the hardware building blocks used in digital computers. Arithmetic and logic functions; Boolean algebra; combinatorial and sequential circuit synthesis; counters, registers, and other system design techniques.
Introduction to structures and techniques used in digital system design. Design with available SSI, MSI, LSI, and programmable logic circuits and memories. Application to microprocessors, I/O structures, and interface design.
Introduction to algorithm analysis and treatment of simple data structures and sorting algorithms. Numerous applications of the data structures and algorithms.
Hardware and software design methodology for embedding micro-controllers and microprocessors. Architecture, hardware, I/O, interrupts, memory organization, and decoding. Software techniques include dispatch tables and real time monitors. Intel 8085 and Motorola 68HCO5, 68HC11, and 68HCHC16 micro-controllers, Intel 8085 and 8086 series microprocessors, and Motorola 6800 series microprocessors. Peripheral devices including counter timers, serial USARTs, parallel ports, interrupt controllers, and DMA controllers.
Selected topics in discrete mathematics. Formal systems, mathematical deduction. Logical concepts. Theorem proving. Sets, relations on sets, operations on sets. Functions; graphs; mathematical structures, morphisms; algebraic structures, semi-groups, quotient groups; finite-state machines, their homomorphism, and simulations.
Markov chains, Chapman-Kolmogorov equation. Classification of states, limiting probabilities, Poisson process and its generalization, continuous-time Markov chains, queuing theory, reliability theory.
Introduction to codes for error detection and correction, linear algebra over finite fields, bounds, perfect, and quasi-perfect codes, probability of error checking, Hamming, BCH, MDS, Reed-Solomon codes, and nonlinear codes. Application of error detecting/correcting codes for data compression, reliable communications, testing and fault-tolerant computing.
Very large-scale integrated circuit design. Review of FET basics. Functional module design, including combinational and sequential logic, programmable logic arrays, finite state machines, and random access memory. Fabrication techniques, layout strategies, scalable design rules, design-rule checking, and guidelines for testing and testability. Analysis of factors affecting speed of charge transfer, power requirements, control and minimization of parasitic effects.
Recently developed information-theoretical approach to the analysis and design of computer algorithms. Previous knowledge of information theory or the theory of algorithms is not required, though desirable. Main topics include the complexity of algorithms; P, E, NP, and NP-hard problems; basic concepts of information theory, optimal coding; information-theoretical approach to sorting, order statistics, binary search, decision trees, hashing.
Interconnection network topologies. Static and dynamic networks. Routing in multicomputer networks. Network flow control. Deadlocks in routing. Multicast and broadcast. Fault-tolerance and reliability of interconnection networks. Modules for realization (nodes and routers). Performance metrics for different topologies.
A unified presentation of approaches for testing of computer hardware. Gate-level testing, functional testing, testing microprocessors, memory testing, and random testing. Self-error-detection and self-error-correction in processors and memories. Diagnostic tests, board and system test, BIST, DFT, and testability analysis.
Fault-tolerant PLAs, gate arrays, ALUs, and computer memories. Replication techniques. Coding techniques in fault-tolerant computing. Totally self-checking checkers. Self-error detection/correction for multiprocessors. Fault-tolerant computer networks.
Introduction to information theory; entropy and information; discrete sources; Shannon-McMillan theorem; noiseless coding theorems; noisy channel and information transmission rate; channel capacity; Shannon's theorem for the noisy channel; error correcting codes; continuous messages and continuous channels; reproduction with a fidelity criterion; basic theorem for a continuous channel.
VLSI circuit testing, built-in self testing, memory testing, fault-tolerant routing in multiprocessors.