- 3MMICOD

Goal(s)

The course is divided into two parts : i/ information theory, ii/ error-correcting codes,
with the following objectives:

Information theory:
providing the basic theoretical concepts for the quantitative measurement of information (what is an information bit?), its representation, storage, transmission and protection.
Application to lossless compression, transmission and content security (steganography).

Coding:
understanding error correction tools and their limitations in relation to information theory. Glimpse the multitude of ways of answering the question ‘what is a good code? Discover some of the most common codes, how they are constructed, the underlying algorithms and how they are implemented in software. Study their application to the reliability of communications and data storage.

Contents

Information theory

Definition of informational quantities: measuring information. Uncertainty and information. Entropies. Shannon's entropy and its properties. Entropy of composite laws. Conditional entropy. Kullback divergence and mutual information.

Information representation
- Asymptotic equipartition, notion of typical sequence.
- Prefixed codes. Kraft inequality.
- Shannon's first theorem (compression limit). Theoretical optimal codes.
- Fano-Shannon and Huffman codes.

Information protection
- Discrete channel without memory.
- Shannon's second theorem (transmission limit).
- All codes are good except those we know how to make: random codes vs. codes of achievable complexity.

Examples that illustrate the concepts and open up the field of applications:
- Joint source-channel coding.
- Distributed source coding. Slépian-Wolf theorem.
- Steganography and watermarking.
- Information leakage and security. Wyner's wiretap channel.
- Links with algorithmic information theory. Kolmogorov and lempel-Ziv.

Code Theory

Error-correcting codes are tools for protecting the integrity of information by adding redundancy. To make decoding feasible in practice, these codes need to be given structure, usually algebraic, while maintaining good performance.
This second part explores this problem from the angles of theory (bounds, capacity) and algorithmics, as well as describing some of the main codes used and their implementation for reliable communications or data storage.

Principles and limitations
- Redundancy for error detection and correction: repetition coding and Shannon's second theorem.
- different objectives: detection, error correction, erasure
- metrics and bounds: Hamming metric, sphere stacking bound, Singleton bound, Gilbert Varshamov bound, perfect codes

Linear codes
- duality
- syndrome decoding
- puncturing and shortening
- Binary Hamming codes: an example of a simple but effective code

Mathematical basis for non-binary codes: finite fields.

Reed-Solomon codes (interpolation point of view)
- key equation
- decoding by Berlekamp-Welch, Euclid, Berlkamp-Massey

Code modifiers and constructors
- punctured codes,
- shortened codes,
- product codes,
- interleaving

How it's used:
- storage distributed by-2,
- QR codes
- CD/DVD: cross-interleaving with delay

Practical work
- implementation of coding/decoding of different codes and implementation on image or sound type information
- stegano + decoding. Channel and source coding.

Language
- C if possible for Semester 6
- otherwise python + sagemath with CodingTheory module

Links with other subjects
Probability and statistics
Thematic link (not a prerequisite) with the introductory crypto course in 2A

Links with specialisations
Useful notions in cryptography, machine learning, etc.

Teaching methods
- 24 h information - 24h coding
- CM + TD + TP

Prerequisites

Prerequisites in terms of knowledge

• basics in discrete probabilities
• basic knowledge of linear algebra.

Content(s)

• Information Theory

• • Definition of information quantities: measuring information. Uncertainty and information. Entropies. Shannon's entropy and its properties. Entropy of composite laws. Conditional entropy. Kullback divergence and mutual information.

• • Representation of information
    - Asymptotic equipartition, notion of typical sequence.
    - Prefixed codes. Kraft inequality.
    - Shannon's first theorem (compression limit). Theoretical optimal codes.
    - Fano-Shannon and Huffman codes.

• • Information protection
    - Discrete channel without memory.
    - Shannon's second theorem (transmission limit).
    - All codes are good except those we know how to make: random codes vs codes of achievable complexity.

• • Examples that illustrate the concepts and open up the field of applications:
    - Joint source-channel coding.
    - Distributed source coding. Slépian-Wolf theorem.
    - Steganography and watermarking.
    - Information leakage and security. Wyner's wiretap channel.
    - Links with algorithmic information theory. Kolmogorov and lempel-Ziv.

• Code theory

Error-correcting codes are tools for protecting the integrity of information by adding redundancy. To make decoding feasible in practice, these codes must be given structure, usually algebraic, while maintaining good performance.
This second part explores this problem from the angles of theory (bounds, capacity) and algorithmics, as well as describing some of the main codes used and their implementation for reliable communications or data storage.

• • Principles and limitations
    - Redundancy for error detection and correction: repetition coding and Shannon's second theorem.
    - different objectives: detection, error correction, erasure
    - metrics and bounds: Hamming metric, sphere stacking bound, Singleton bound, Gilbert Varshamov bound, perfect codes, etc.

• • Linear codes
    - duality
    - syndrome decoding
    - punching and shortening
    - Binary Hamming codes: an example of a simple but effective code

• • Mathematical basis for non-binary codes: finite fields.

• • Reed-Solomon codes (interpolation point of view)
    - key equation
    - decoding by Berlekamp-Welch, Euclid, Berlkamp-Massey

• • Code modifiers and constructors
    - punched codes,
    - shortened codes,
    - product codes,
    - interleaving

• • Implementation:
    - storage distributed by-2,
    - QR codes
    - CD/DVD: cross-interleaving with delay

• • Practical exercises
    - implementation of coding/decoding of different codes and implementation on image or sound type information.
    - stegano + decoding. Channel and source coding.

• Language
  - C if possible for Semester 6
  - otherwise python + sagemath with CodingTheory module

• Links with other subjects
  Probability and statistics
  Thematic link (not a prerequisite) with the introductory crypto course in 2A

• Links with specialisations
  Useful notions in cryptography, machine learning, etc.

• Teaching methods
  - 24 h information - 24h coding
  - CM + TD + TP

Knowledge requirements
- basic discrete probability
- basic knowledge of linear algebra.