Information et codage - 3MMICOD

Objectif(s)

Le cours comporte deux parties, théorie de l'information et codes correcteurs d'erreurs, dont les objectifs sont :

Théorie de l'information : fournir les notions théoriques de base pour la mesure quantitative de l’information (qu'est-ce qu'un bit d'information ?), sa représentation, son stockage, sa transmission, sa protection et sa dissimulation.
Application à la compression sans perte, à la sécurité des transmissions et des contenus (stéganographie).

Codage : comprendre les outils permettant la correction d'erreurs et leurs limitations en lien avec la théorie de l'information. Entrevoir la multitude des façons de répondre à la question "qu'est-ce qu'un bon code ?". Découvrir certains codes parmis les plus courants, leur construction ainsi que l'algorithmique sous-jacente et leur mise ne oeuvre logicielle. Étudier leur application à la fiabilité des communications et du stockage de données.

Contenu(s)

• Théorie de l'Information

• • Définition des quantités informationnelles : mesurer l’information. Incertitude et information. Entropies. L’entropie de Shannon et ses propriétés. Entropie de lois composées. Entropie conditionnelle. Divergence de Kullback et information mutuelle.

• • Représentation de l'information
    - Équipartition asymptotique, notion de suite typique.
    - Codes préfixés. Inégalité de Kraft.
    - Premier théorème de Shannon (limite à la compression). Codes optimaux théoriques.
    - Codes de Fano-Shannon et de Huffman.

• • Protection de l'information
    - Canal discret sans mémoire.
    - Second théorème de Shannon (limite à la transmission).
    - Tous les codes sont bons sauf ceux que l'on sait faire : codes aléatoires vs codes de complexité réalisable.

• • Exemples qui illustrent les concepts et ouvrent le champ des applications :
    - Codage conjoint source canal.
    - Codage de source distribué. Théorème de Slépian-Wolf.
    - Stéganographie et tatouage.
    - Fuite d'information et sécurité. Modèle de Wyner (Wyner's wiretap channel).
    - Liens avec la théorie algorithmique de l'information. Kolmogorov et lempel-Ziv.

• Théorie des Codes

Les codes correcteurs d'erreur sont des outils permettant de protéger l'intégrité de l'information via l'ajout de redondance. Pour rendre le décodage réalisable en pratique, il faut donner à ces codes de la structure, le plus souvent algébrique, tout en maintenant un bon rendement.
Cette deuxième partie explore cette problématique sous les angles de la théorie (bornes, capacité), de leur algorithmique, ainsi que la description de quelques un des principaux codes utilisé et leur mise en oeuvre pour la fiabilité des communications ou du stockage des données.

• • Principes et limitations
    - La redondance pour la détection et la correction d'erreurs : codage à répétition et second théorème de Shannon.
    - différents objectifs: détection, correction d'erreurs, d'effacement
    - métriques et bornes: métrique de Hamming, borne d'empilement des sphères, de Singleton, de Gilbert Varshamov, codes parfaits

• • Les codes linéaires
    - dualité
    - décodage par syndrome
    - poinçonnage et raccourcissement
    - Codes de Hamming Binaire: un exemple de code simple mais efficace

• • Bases mathématiques pour des codes non binaires : corps finis.

• • Les codes de Reed-Solomon (point de vue interpolation)
    - équation clé
    - décodage par Berlekamp-Welch, Euclide, Berlkamp-Massey

• • Modificateurs et constructeurs de codes:
    - codes poinçonné,
    - codes raccourcis,
    - codes produits,
    - entrelacement

• • Mise en œuvre:
    - stockage distribué par-2,
    - codes QR
    - CD/DVD : entrelacement croisé avec retard

• • TPs
    - implementation de codage/décodage de différents codes et mise en oeuvre sur une info type image ou son
    - stegano + decodage. Codage canal et source.

• Langage
  - C si envisageable pour Semestre 6
  - sinon python + sagemath avec module CodingTheory

• Liens avec les autres matières
  Probabilités et statistiques
  Lien thématique (sans être un prérequis) avec l'UE d'intro à la crypto en 2A

• Liens avec les spécialisations
  Notions utiles en cryptographie, en machine learning, etc.

• Modalités pédagogiques
  - 24 h information - 24h codage
  - CM + TD + TP

Pré-requis en terme de connaissance
- bases en probabilités discrètes
- bases en algèbre linéaire.