Formations en Informatique de Lille
Portail pédagogique
accueil FIL L1 Maths-Info Licence Info Master Info Master Miage Master MISO Master DS Alternance
S3 S4 S5 Info S5 Miage S6 Info S6 Miage
ASD Anglais BDD2 BPC CDC JS MPC PROBA Projet SAPE
Vous êtes ici : FIL > Portail > Licence Info > S4 > CDC
Compression de l'information, détection et correction d'erreurs
BCC 2 : faire un choix de modèles et algorithmes adapatés à la résolution de problème

Organisation

Cette unité se déroule au S4 de la L2 INFO. Il s'agit d'une UE obligatoire.

Volume horaire : 1h30 de cours, 1h30 de TD et 1h30 de TP par semaine, pendant 6 semaines.

Objectifs

  • connaître la notion de codage optimal d'une source
    • savoir calculer l’entropie d’une source
    • savoir trouver un codage optimal pour une source
  • être familiarisé avec la fiabilité des codages pour la transmission des données
    • savoir calculer la distance minimale d’un code et ses capacités de détection et correction
    • savoir utiliser ou créer de nouveaux codes détecteurs ou correcteurs d’erreurs

Crédits

3 ECTS

Responsable

Mikaël Salson

Mikaël Salson
dernière modification : 05/12/2023 à 19:15:54

Contenu

  • notion de source d'information
  • quantité d'information contenue dans un symbole
  • entropie d'une source
  • codage optimal d'une source
  • construction d'un codage optimal par l'algorithme de Huffman
  • application à la compression
  • notion de canal bruité
  • codage détecteurs d'erreurs : bit de parité, répétition
  • codage correcteurs d'erreurs : exemples par la répétition trois fois, codage de Hamming (7,4,3)

Bibliographie

Mikaël Salson
dernière modification : 05/12/2023 à 19:15:54

Évaluation

Cette UE est évaluée :

  • par votre travail personnel (CC), notamment pendant les TP (pour rappel, reprendre du code qui n'est pas à vous, sans l'indiquer très clairement, est du plagiat, ce qui est une fraude, donc interdit)
  • par un DS final (DSf)

La note de l'UE est calculée par : 1/2 × (CC + DSf)

Exemples d'évaluation

Des versions corrigées des évaluations sont également accessibles. Néanmoins nous vous rappelons qu'il est inutile de regarder la correction sans avoir sérieusement travaillé chacune des questions.

L'UE étant récente il y a peu d'archive d'anciens DS. Néanmoins voici une sélection d'exercices utilisés dans une ancienne UE similaire. Attention le nombre d'exercices correspond environ à deux DS : exemples d'exercices (éléments de correction).

CoursTDTPInformations
1 13/03–19/03

Détection et correction d'erreurs

PDF (version imprimable)

  • Exemple du numéro de carte bleue
  • Notion de canal binaire symétrique sans mémoire
  • Distance de Hamming, poids de Hamming
  • Codage par parité
  • Distance minimale d'un code

Pas de TD cette semaine

pas de TP cette semaine

2 20/03–26/03

Suite du précédent

  • Capacité de détection et correction d'erreurs en fonction de la distance minimale
  • Codages systématiques
  • Codages linéaires
  • Matrice génératrice

TD 1 – Détection et correction d'erreurs

TP sur la détection et correction d'erreurs

  • Canal de communication (partie 1)
  • Répétition 3 fois (partie 2)

Vidéo résumant plusieurs aspects du cours : distance de Hamming, codage par parité, codage par répétition, codages linéaires, codage de Hamming. Autre vidéo, en anglais avec des sous-titres, qui rentre plus dans le détail du principe des codes correcteurs.

3 27/03–02/04

Suite et fin du cours

  • Matrices de contrôle
  • Détection et correction d'erreurs avec les matrices de contrôle
  • Codages de Hamming, rendement optimal

Suite du TD

Suite du TP

  • Codages linéaires systématiques
4 03/04–09/04

Codages optimaux

PDF (version imprimable)

  • Alphabets et symboles
  • Source d'information
  • Quantité d'information
  • Entropie
  • Codage optimal
  • Représentation d'un codage dans un arbre

Suite et fin du TD

Suite et fin du TP

  • Codages linéaires systématiques (fin)
  • Expériences
5 10/04–16/04

Suite de la semaine précédente

  • Critères de non optimalité
  • Algorithmes de Fano et de Huffman
  • Exemples de codage obtenus avec ces algorithmes
  • Multiplicité des codages optimaux

TD2 – compression de données

TP2 – calcul de l'entropie

Courte vidéo sur la compression par l'algorithme de Huffman.

Application interactive pour la création d'arbre de Huffman.

Cours le jeudi 13 avril, au lieu du 10 avril

17/04–23/04
24/04–30/04
6 01/05–07/05

Suite de la semaine précédente

Suite du précédent

TP 3 – Algorithme de Huffman

Cours le jeudi 4 mai, au lieu du 1er mai

7 08/05–14/05

Suite et fin du TD sur la compression

Suite et fin du TP sur Huffman

8 15/05–21/05

Pour le DS : une feuille A4 recto-verso autorisée

Mikaël Salson
dernière modification : 05/12/2023 à 19:15:54

Équipe pédagogique

Groupe Enseignant Mail
1 Asbathou Biyalou-Sama asbathou.biyalousama@univ-lille.fr
2 Jean-Luc Intumwayase jeanluc.intumwayase@univ-lille.fr
3 Igor Martayan igor.martayan@univ-lille.fr
4 Ellie Beauprez ellie.beauprez@univ-lille.fr
5 Laurent Noé Laurent.Noe@univ-lille.fr
6 Alexandre Sedoglavic Alexandre.Sedoglavic@univ-lille.fr
7 Jean-Stéphane Varré Jean-Stephane.Varre@univ-lille.fr
8 Mikaël Salson Mikael.Salson@univ-lille.fr
INFO-MATH Léopold Weinberg Leopold.Weinberg@univ-lille.fr