Course detail
ÚSI-RTSOPAcad. year: 2020/2021
Algorithms and principles of the design of systems resistant to failures, error-correcting code theory.
1. Project assignment. INTRODUCTION: basic definitions, reliability, reliability indicators, safety, application classes of fault tolerant systems. Methods of the design and operation of fault tolerant systems, reconfiguration, recovery.
2. Ways of achieving resistance against failure, redundancy types. PERIPHERAL and SOFTWARE REDUNDANCY: static - TMR, dynamic - duplication, reconfiguration, time tracking, hybrid redundancy, NMR, automatic cleaning, triple duplex. Tolerance of errors. SIFT, Byzantine Agreement. 3. INFORMATION REDUNDANCY: 3.1. Basic properties of codes, basic codes - parity codes, two-dimensional and multi-dimensional parity, rotating parity. 3.2. Berger Code. 3.3. Duplication codes. 3.4. Checksum.
4. ARITHMETIC CODES - AN, residual, RNS.
5.1. HAMMING AND SIMILAR CODES. 5.2. Codes with syllable error detection. 5.3. LDPC low-density parity codes. 5.4. Processor code security.
6. CYCLIC CODES: Arithmetic circuits for cyclic codes. Cyclic codes created by division and multiplication. Matrix description of cyclic codes. Meggitt decoder. Tables of primitive polynomials.
7. Calculations of CRC
8. FIRE CODES:
9. CONSTRUCTION OF GALOIS FIELDS (2P). Minimal polynomials. Tables of minimal polynomials.
10. BCH CODES. BCH codes for FLASH memory.
11. REED-SOLOMON CODES. RS code for CD and CD ROM, RS code for VCR.
12. CONVOLUTIONAL CODES and their application, punctured codes, turbo-codes.
13. TIME REDUNDANCY: detection of transient and permanent errors, alternating logic, repetition of RESO, RESWO, REDWC calculation.
14. Fault tolerance at the VLSI level: increasing yield and reconfigurable arrays, memory chips. Processor fields. Reconfigurable MP chip.
15. RADIATION RESISTANCE OF COMPUTERS, SEU.
16. FAULT TOLERANCE COMMUNICATION NETOWORKS: Bus. Shared memory connection. Ring. Tree. Cube, super cube.
17. FAILURE ISOLATION PRINCIPLE.
18. AIRCRAFT CONTROL SYSTEM.
19. FAULT TOLERANT SYSTEM ARCHITECTURES - history.
20. FAULT TOLERANT SYSTEMS in the 1980s-90s. Space research, aviation, transport, telephone exchanges, transaction processing, management of technical processes.
21. FAULT TOLERANCE SYSTEM PROGRAMMES: recovery, (SIFT, Byzantine Agreement - see Chap. 2), reconfiguration, resistant programming.
Supervisor
Department
Learning outcomes of the course unit
Not applicable.
Prerequisites
Basic knowledge of digital computing, linear algebra and matrix calculus.
Co-requisites
Not applicable.
Recommended optional programme components
Not applicable.
Recommended or required reading
Lin, S., Costello, D.J.: Error Control Coding: Fundamentals and Applications, Prentice-Hall, 1983, ISBN 0-13-283796-X (CS)
Hlavička, J., Racek, S., Golan, P., Blažek T.: Číslicové systémy odolné proti poruchám, Vydavatelství ČVUT, Praha, 1992, ISBN 80-01-00852-5 (CS)
Zvolené publikace z časopisů a konferencí (CS)
Planned learning activities and teaching methods
Not applicable.
Assesment methods and criteria linked to learning outcomes
Written semestral exam
Production of an individual project, and its presentation
Language of instruction
Czech
Work placements
Not applicable.
Course curriculum
Algorithms and principles of the design of systems resistant to failures, error-correcting code theory.
1. Project assignment. INTRODUCTION: basic definitions, reliability, reliability indicators, safety, application classes of fault tolerant systems. Methods for the design and operation of fault tolerant systems, reconfiguration, recovery.
2. Ways of achieving fault tolerance, redundancy types. PERIPHERAL and SOFTWARE REDUNDANCY: static - TMR, dynamic - duplication, reconfiguration, time tracking, hybrid redundancy, NMR, automatic cleaning, triple duplex. Tolerance of errors. SIFT, Byzantine Agreement.
3. INFORMATION REDUNDANCY: 3.1. Basic properties of codes, basic codes - parity codes, two-dimensional and multi-dimensional parity, rotating parity. 3.2. Berger Code. 3.3. Duplication codes. 3.4. Checksum.
4. ARITHMETIC CODES - AN, residual, RNS.
5.1. HAMMING AND SIMILAR CODES. 5.2. Codes with syllable error detection. 5.3. LDPC low-density parity codes. 5.4. Processor code security.
6. CYCLIC CODES: Arithmetic circuits for cyclic codes. Cyclic codes created by division and multiplication. Matrix description of cyclic codes. Meggitt decoder. Tables of primitive polynomials.
7. CRC calculations
8. FIRE CODES
9. CONSTRUCTION OF GALOIS FIELDS (2P). Minimal polynomials. Tables of minimal polynomials.
10. BCH CODES. BCH codes for FLASH memory.
11. REED-SOLOMON CODES. RS code for CD and CD ROM, RS code for VCR.
12. CONVOLUTIONAL CODES and their application, punctured codes, turbo-codes.
13. TIME REDUNDANCY: detection of transient and permanent errors, alternating logic, repetition of RESO, RESWO, REDWC calculation.
14. Fault tolerance at the VLSI level: increasing yield and reconfigurable arrays, memory chips. Processor fields. Reconfigurable MP chip.
15. RADIATION RESISTANCE OF COMPUTERS, SEU.
16. FAULT TOLERANCE OF COMMUNICATION NETOWORKS: Bus. Shared memory connection. Ring. Tree. Cube, super cube.
17. THE FAILURE ISOLATION PRINCIPLE.
18. AIRCRAFT CONTROL SYSTEM.
19. FAULT TOLERANT SYSTEM ARCHITECTURES - history.
20. FAULT TOLERANT SYSTEMS in the 1980s-90s. Space research, aviation, transport, telephone exchanges, transaction processing, management of technical processes.
21. FAULT TOLERANCE SYSTEM PROGRAMMES: recovery, (SIFT, Byzantine Agreement - see Chap. 2), reconfiguration, resistant programming.
Aims
Not applicable.