Ensimag Rubrique Formation 2022

Coding and Fault Tolerances - WMM53C3

  • Number of hours

    • Lectures 18.0
    • Tutorials 12.0

    ECTS

    ECTS 3.0

Goal(s)

The present course introduces basic tools used in order to assure the transmission of information on the supports producing
errors by noise. The basic mathematical concepts are given which make it possible to construct codes with a given guaranteed speed
(information rate).
In particular, we treat cyclic codes and geometric Goppa codes.
Effective implementation of codes and industrial applications (CIRC code for audio compact disks, turbo-codes, …) are detailed.

Contact Alexei PANTCHICHKINE

Content(s)

The course is divided in 2 parts:
A- Foundations of error-correcting codes [5 lectures, Alexei PANTCHICHKINE]
1. Transmission of Information, coding and optimal decoding on a noisy channel.
2. Distance of Hamming, speed and information rate, relative distance. Hamming bound and codes.
3. Linear codes and cyclic codes. Generating matrix and computation of the syndrome of errors.
4. Error-locating polynomials. Application to decoding.
5. Reed-Solomon codes and BCH codes. Coding and decoding.
6. Bounds of Plotkin and of Gilbert-Varshamov.
7. Geometric Goppa codes and algebraic curves over finite fields.
B – Implementation and industrial applications of error-correcting codes
Implementation and applications of Reed-Solomon Codes [2 lectures, Jean-Louis ROCH]
1. Errors and erasures. Burst errors and Interleaving. CIRC (Cross-Interleaved Reed-Solomon codes).
2. Applications: Audio CD; RAID disk systems. Satellite communications.
Implementation and applications of convolutional and turbo codes [3 lectures, Jean-Marc BROSSIER]
1. Definition of convolutional codes. Distance and decoding (Viterbi algorithm)
2. Turbo-codes.
3. Applications.



Prerequisites

Finite fields, linear algebra, polynomials, Euclidean algorithm, ideals and rings Practice in programming (C/C++) with I/O streams.

Test

The exam is given in english only 

Session 1:

  • E1A, E1B: Final examination: 2 written exams: E1A=1h30 for part A -; E1B=1h30 for part B
  • TP: Practical work: 1 (part B)
  • CC: Continuous controls: 1 controls (1h for part I). The mark obtained to the continuous control is taken into account only if larger
    than the mark of the final examination. Session2 :(under decision of the jury) :
  • E2A2, E2B2: one or two final examination in session 2. E2A2 for part A and/or parts B. Oral (30’) if <= 5 students; written (1h) if
    >=6 students


S1=40%E1 (partA)+25%E1(partB)+10%MAX(E1A, CC)+25%TP; S2=40%E2(partA)+25%E2(partB)+10%MAX (E2A,CC)+25%TP

Additional Information

This course is given in english only EN

Curriculum->M2 Sec, Crypt. and Coding of Info.->SCCI - Semester 3