Course
Description

Description:

This course describes systematic and integrated approaches towards the design and implementation of fault-tolerant combinational circuits and dynamic systems.  Building on results from recent research, the course blends together techniques from coding and complexity theory, digital design, and control, automata and system theory.  The course initially studies fault-tolerant combinational architectures under a unifying approach that exposes the similarities between coding for reliable communication and coding for reliable computation.  This approach is subsequently extended to handle fault tolerance in systems whose internal state influences their future behavior, such as finite-state controllers or algorithmic computations evolving over several time steps.  The introduction of time and state dynamics presents new challenges for engineering design, but also offers new degrees of freedom and opens up exciting possibilities for future digital system implementation.  The course discusses some of these open research questions for a number of systems of special interest, such as finite-state machines, digital signal processing filters, cellular automata and discrete event systems.  An introduction to the basic objectives and techniques in coding and in design for fault diagnosis and fault tolerance is provided.

Topics:
              - Fault models, errors, reliability, availability, fault tolerance
              - Failures in digital communication channels, coding approaches for communication systems
              - Failures in gates or computational components:
                               (i) coding approaches for noisy circuits
                               (ii) ABFT techniques for computational systems
                               (iii) efficiency considerations and other parameters (capacity, probability of error, error coverage)
              - Failures in the error correcting mechanisms, coding approaches for dynamic systems
                                (i) non-concurrent (dynamic) error correction
                                (ii) decoding complexity and low density parity check codes
                                (iii) computational capacity, fault coverage, probability of error
            - Other uses of redundancy (monitoring and testing using redundant inputs, states and outputs)

Prerequisites:

Required:  ECE313 and ECE362 (or permission of instructor).
Desired:  ECE412, ECE415.
Familiarity with elementary algebra at the level of Math317 and linear system theory at the level of ECE415 would be helpful, but not required;  a self-contained introduction to these topics will be provided.

Textbook:  Mainly class notes and research papers.

References:

• C.N. Hadjicostis, Coding Approaches to Fault Tolerance in Combinational and Dynamic Systems, Kluwer Academic Publishers, 2001.
• D.P. Siewiorek and R.S. Swarz, Reliable Computer Systems: Design and Evaluation, A.K. Peters, 1998.
• R.E. Blahut, Algebraic Codes for Data Transmission, Cambridge University Press, 2002.
• D.K. Pradhan, ed., Fault Tolerant Computer System Design,  Prentice-Hall, 1996.
• B.W. Johnson, Design and Analysis of Fault-Tolerant Digital Systems, Addison Wesley, 1989.
• S.B. Wicker, Error Control Systems, Prentice Hall, 1995.
• C.G. Cassandras and S. Lafortune,  Introduction to Discrete Event Systems, Kluwer Academic Publishers, 2001.
• F.T. Leighton, Introduction to Parallel Algorithms and Architectures:  Arrays, Trees, Hypercubes, Morgan Kaufmann Publishers, 1992.

Instructor information:  C. N. Hadjicostis / 265-8259 / 148 CSL / chadjic@control.csl.uiuc.edu

Course Time and Place: Tuesdays & Thursdays, 1:30-2:50pm, 106B6 Eng. Hall

Office Hours: Thursdays, 4:00-6:00pm, 148 CSL

Course Outline:

I. Introductory Material (Hours: 6)

•       Motivation, definitions, basic principles and fundamental concepts
•       Fault model and error manifestation, permanent vs. transient faults
•       Noise modeling in digital systems, quantization and finite precision effects
•       Reliability, availability, fault tolerance, security, cost issues
•       Examples of successful fault-tolerant schemes in general purpose computers (hardware replication, voting schemes, RAID systems)

•       Reliable communication systems, Shannon theorem and theory
•       Circuits of ``noisy gates''
•       Coding techniques for special-purpose systems ($\alpha N$ codes, arithmetic codes, algorithm-based fault tolerance)
•       Case studies:  matrix multiplication, FFT, sorting
•       Extensions to computational systems with algebraic structure

•       Finite state machines, linear systems, linear finite state machines
•       Non-concurrent error detection and identification schemes
•       Failures in the error correcting mechanisms
•       Low density parity check codes
•       Computational ``capacity'' issues

•       Reliable cellular automata
•       Fault diagnosis in discrete event systems
•       Fault-tolerant monitoring of large-scale discrete event systems

Homework:

• Course Info
  
• PS1
• PS2
• PS3
• PS4
  

Projects:

•  Some indicative projects