Vous êtes ici : FIL > Portail > Licence Info > L2S3 > CODAGE

Codage de l'information

Responsable

  • Mikaël Salson, Bât. M3, e-mail : Mikael.Salson (AT) univ-lille1.fr

Volume horaire

Cet enseignement a lieu au semestre 3 de la licence mention Informatique.

Il est organisé en
  • une séance de cours hebdomadaire (1h30)
  • une séance de TD hebdomadaire (1h30)
  • une séance de TP hebdomadaire (1h30)
Il est réparti sur une durée de douze semaines, soit un volume total de 48h.

Crédits

5 ECTS
Éric Wegrzynowski et Mikaël Salson
dernière modification : 29/06/2016 à 18:30:30
Il y a 10 sortes de personnes :
celles qui comprennent le binaire,
et les autres ...

Objectifs

Le but de ce cours est de montrer comment l'information (nombres, textes, images, sons, ...) traitée par des machines numériques (ordinateurs) peut être représentée. Le choix d'une représentation (codage) peut être soumis à deux contraintes parfois antagonistes :
  • codage de taille optimale (compression)
  • fiabilité du codage pour la transmission des données (détection et correction des erreurs)
Le cours donnera un aperçu de résolution de ces deux contraintes.

Contenu

Le cours comprend trois parties :
  • Représentation des nombres.
  • Codage
    • Alphabets, mots.
    • Codage. Codage décodable.
    • Codage préfixe. Inégalité de Kraft.
    • Codage optimal. Codage de Fano, de Huffman
  • Codage détecteur et correcteur d'erreurs.
    • Codage linéaire.
    • Distance de Hamming.
    • Codage de Hamming.

Bibliographie

  • Architecture et technologie des ordinateurs. P. Zanella, Y. Légier. Dunod.
  • Méthodes mathématiques pour l'informatique. Jaques Vélu. Dunod.
  • Compression et cryptage des données multimédias. X. Marsault. Hermes.
  • Introduction aux codes correcteurs. Pierre Csillag. Ellipses.
  • Fontes et codages. Yannis Haralambous. O'Reilly.
  • Théorie des codes. Jean-Guillaume Dumas, Jean-Louis Roch, Éric Tannier et Sébastien Varrette. Dunod.
Éric Wegrzynowski et Mikaël Salson
dernière modification : 29/06/2016 à 18:30:30

Emploi du temps 2016-2017

Gpe Nature Horaire Salle Enseignant e-mail
TOUS C Lundi 8h30-10h00 M1 Archimède Mikaël Salson mikael.salson(AT)univ-lille1.fr
S3H TD Mardi 10h20-11h50 Éric Wegrzynowski eric.wegrzynowski(AT)univ-lille1.fr
S3H - 1 TP Mercredi 8h30-10h SUP 116 Éric Wegrzynowski
S3H - 2 TP Mardi 8h30-10h SUP 116 Éric Wegrzynowski
S3 - 1 TD Lundi 10h20-11h50 M5 A7 Francesco De Comité Francesco.De-Comite(at)univ-lille1.fr
S3 - 1 TP Mardi 10h20-11h50 SUP 118 Francesco De Comité
S3 - 2 TD Mercredi 10h20-11h50 M5 A1 Laurent Noé laurent.noe(AT)univ-lille1.fr
S3 - 2 TP Vendredi 10h20-11h50 SUP 118 Laurent Noé
S3 - 3 TD Mercredi 8h30-10h00 M5 A9 Léopold Weinberg leopold.weinberg(AT)univ-lille1.fr
S3 - 3 TP Mercredi 10h20-11h50 SUP 118 Léopold Weinberg
S3 - 4 TD Vendredi 8h30-10h M5 A3 Mikaël Salson mikael.salson(AT)univ-lille1.fr
S3 - 4 TP Mardi 15h20-16h50 SUP 118 Mikaël Salson
S3 - 5 TD Mardi 8h30-10h SUP 203 Vincent Hugot Vincent.Hugot(at)inria.fr
S3 - 5 TP Jeudi 10h20-11h50 M5 A14 Vincent Hugot
Éric Wegrzynowski et Mikaël Salson
dernière modification : 07/09/2016 à 09:10:18

Année 2016–2017

Semaine Préparation Cours TP Remarque
105/09–11/09Ce que nous verrons dans ce cours

Chap 1 : Représentation des nombres

  • Bases de numération
  • Cas des bases 2 et 16
  • Taille de l'écriture d'un entier
Pas de TP cette semaine
212/09–18/09Lire l'article Comment le "Gangnam Style" (n')a (pas) cassé le compteur de YouTube .
  • Quel est le nombre maximal que l'on peut stocker dans un entier 32 bits ?
  • Quel est le problème dans le cas présent ?

Chap 1 : Représentation des nombres (suite)

  • Taille de l'écriture d'un entier (fin)
  • Représentation des entiers en informatique
  • Entiers signés

TP1 : Représentation des nombres

319/09–25/09Lire les sections 1.6.1 et 1.6.2.
  • Les opérations logiques s'appliquent-elles uniquement sur des nombres binaires ?
  • À quelle opération arithmétique (sur un bit) est équivalente l'opération ou exclusif ?
  • À quelle opération arithmétique (sur un bit) est équivalente l'opération et ?

Chap 1 : Représentation des nombres (fin)

  • Nombres flottants, norme IEEE 754
  • Boutisme
  • Opérations logiques sur les entiers

TP2 : Représentation des nombes et caractères

Sujet de TP sur 2 semaines

426/09–02/10Lire les sections 2.2.1 à 2.2.5 (pages 24 à 27)
  • Combien peut-on former de mots à partir de l'alphabet {a, b} ?
  • Quel(s) mot(s) est(sont) dans A* mais pas dans A+ ?
  • Pourquoi un mot a-t-il plus de préfixes qu'il ne contient de lettres ?

Chap 2 : Codes et codages

  • Alphabets, mots, langages, concaténation
  • Factorisation d'un mot dans un langage
Suite de la semaine précédente
503/10–09/10Lire la partie 2.2.7 du polycopié

Chap 2 : Codes et codages (suite)

  • Codes
  • Codages
  • Familles de codes
    • Codes de longueur fixe
    • Codes « à virgule» 
    • Codes préfixes
  • Représentation des codes dans un arbre
  • Décodage d'un code préfixe à l'aide d'un arbre
  • Existence de codes préfixes pour une distribution de longueurs (théorème de Kraft)

TP3 : Base 64

610/10–16/10Lire les parties 2.6.2 à 2.6.4 (pages 41 et 42)

Chap 2 : Codes et codages (suite)

  • Représentation des codes dans un arbre
  • Décodage d'un code préfixe à l'aide d'un arbre
  • Existence de codes pour une distribution de longueurs
    Théorème de Mac Millan
    Existence de codes
    Démarche systématique pour trouver une double factorisation
    Résiduel et quotient
    Algorithme de Sardinas Patterson

TP4 : Codages et décodages

Sujet de TP sur 3 semaines

717/10–23/10Lire la partie 3.1.1 (page 51).

Chap 3 : Codages optimaux

  • Source, quantité d'information, entropie d'une source
  • Longueur moyenne d'un codage, codage optimal
  • Théorème du codage sans bruit (début)
Suite du précédent
824/10–30/10

Chap 3 : Codages optimaux (suite)

  • Théorème du codage sans bruit (suite)
  • Critères de non-optimalité d'un codage
  • Construction de codages optimaux (début)
Suite du précédentInterruption pédagogique du 27 octobre au 2 novembre.
931/10–06/11Interruption pédagogique du 27 octobre au 2 novembre. DS de codage le 4/11 de 16h30 à 18h30 Pas de cours cette semaine
1007/11–13/11Faîtes l'algorithme de Huffman sur l'exemple vu en cours mais en plaçant le symbole E,F après les symboles B et C (dans la liste triée des symboles).

Chap 3 : Codages optimaux (fin)

  • Construction de codages optimaux (Algorithme et codage de Huffman)
  • L'algorithme de Huffman dans les logiciels de compression

Chap 4 : Détection/correction des erreurs

  • Motivation
  • Exemple du numéro de carte bancaire
  • Canal binaire symétrique sans mémoire

TP5 : Compression de données

TP sur 2 semaines

1114/11–20/11

Chap 4 : Détection/correction des erreurs (suite)

  • Distance de Hamming et poids de Hamming
  • Exemples des codages par bit de parité et par répétition
  • Capacité de détection et correction en fonction de la distance minimale d'un code
Suite de la semaine précédente
1221/11–27/11

Chap 4 : Détection/correction des erreurs (suite)

  • Rendement d'un codage

TP6 : détection et correction d'erreurs

1328/11–04/12

Chap 4 : Détection/correction des erreurs (fin)

  • Codages linéaires
    • Distance minimale d'un codage linéaire
    • Matrice génératrice
    • Matrice de contrôle
    • Détection et correction d'erreurs avec un codage linéaire
  • Codages de Hamming
    • Exemple sur le [7, 4, 3]
Suite de la semaine précédente
1405/12–11/12
Éric Wegrzynowski et Mikaël Salson
dernière modification : 10/10/2016 à 10:39:35

L'évaluation s'effectue suivant une procédure de contrôle continu.

Trois notes seront attribuées à chaque étudiant durant le semestre :

  • DS1 et DS2 : deux notes sur 20 de devoirs surveillés ;
  • TP : une note sur 20 de Travaux Pratiques (TP du semestre + contrôle en fin de semestre) ;

À partir des notes de DS on calcule une note d'écrit :

Ecrit = (DS1+DS2)/2

La note finale sur 20 (N) est calculée comme une moyenne pondérée de la note d'écrit et de celle de TP :

N= (TP + 3Ecrit)/4

Pour la session de rattrapage, la note de TP est conservée, et la note d'écrit est remplacée par la note du DS de rattrapage ( DS3) :

Ecrit = DS3

L'unité acquise apporte 5 ECTS.

Éric Wegrzynowski et Mikaël Salson
dernière modification : 29/06/2016 à 18:30:30

Polycopiés

Sujets de DS depuis 2010

Contrôle de TP

Contrôle de TP du 14 décembre 2015.

Divers

Codage des caractères
ici pour en savoir plus sur le codage ASCII
ici ou  pour en savoir plus sur Unicode.
Compression
Un document sur la compression édité par le CNDP  (744 Ko)
Des vidéos sur la quantité d'information, l'entropie et l'algorithme de Huffman.
Détection et correction d'erreurs
Une vidéo sur le codage de Hamming
Éric Wegrzynowski et Mikaël Salson
dernière modification : 05/06/2017 à 12:32:19