Vous êtes ici : FIL > Portail > Licence Info > L2S3H > 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
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.

Emploi du temps 2018-2019

Gpe Nature Horaire Salle Enseignant e-mail
TOUS C Lundi 8h30-10h00 M1 Galois Mikaël Salson mikael.salson(AT)univ-lille.fr
S3H TD Mardi 10h20-11h50 SUP 303 Éric Wegrzynowski eric.wegrzynowski(AT)univ-lille.fr
S3H - 1 TP Mercredi 8h30-10h SUP 116 Éric Wegrzynowski
S3H - 2 TP Mardi 8h30-10h SUP 116 Éric Wegrzynowski
S3 - 1 TD Mercredi 10h20-11h50 M5 A1 Francesco De Comité Francesco.De-Comite(at)univ-lille.fr
S3 - 1 TP Lundi 10h20-11h50 M5 A13 Francesco De Comité
S3 - 2 TD Mercredi 10h20-11h50 M5 A5 Laurent Noé laurent.noe(AT)univ-lille.fr
S3 - 2 TP Vendredi 10h20-11h50 SUP 118 Laurent Noé
S3 - 3 TD Mercredi 8h30-10h00 M5 A1 Léopold Weinberg leopold.weinberg(AT)univ-lille.fr
S3 - 3 TP Mercredi 10h20-11h50 M5 A4 Léopold Weinberg
S3 - 4 TD Vendredi 8h30-10h M5 A6 Mikaël Salson mikael.salson(AT)univ-lille.fr
S3 - 4 TP Mercredi 8h30-10h M5 A11 Mikaël Salson
S3 - 5 TD Lundi 15h40-17h10 M5 A9 Momar Sakho momar.sakho(AT)univ-lille.fr
S3 - 5 TP Jeudi 10h20-11h50 M5 A4 Momar Sakho
S3 - 6 TD Lundi 10h20-11h50 M1 31 Weierstrass Momar Sakho momar.sakho(AT)univ-lille.fr
S3 - 6 TP Mercredi 8h30-10h M5 A12 Momar Sakho

Année 2019–2020

Semaine Préparation Cours TP Remarque
109/09–15/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
216/09–22/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

323/09–29/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 (2)

Sujet de TP sur 2 semaines

430/09–06/10
  • Opérations logiques sur les entiers (suite)

Chap 2 : Codes et codages

Suite de la semaine précédente
507/10–13/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 (suite)

  • Alphabets, mots, langages, concaténation
  • Factorisation d\'un mot dans un langage
  • Codes
  • Familles de codes
    • Codes de longueur fixe
    • Codes « à virgule» 
    • Codes préfixes (début)

TP3 : Conversion de caractères

614/10–20/10Lire les parties 2.6.2 à 2.6.4 (pages 41 et 42)

Chap 2 : Codes et codages (suite)

  • Familles de codes (suite)
    • Codes préfixes
  • Représentation des codes dans un arbre
  • Codages
  • 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)
  • Existence de codes pour une distribution de longueurs
    Théorème de Mac Millan
    Existence de codes
    Résiduel et quotient

TP4 : Base 64

721/10–27/10Lire la partie 3.1.1 (page 51).
  • Démarche systématique pour trouver une double factorisation
  • Algorithme de Sardinas Patterson
  • Comment déterminer si un langage est un code ? (résumé et exemples)

Chap 3 : Codages optimaux

  • Quantité d'information

TP5 : Codages et décodages

Sujet de TP sur 2 semaines

28/10–03/11Interruption pédagogique d'automne. Pas de cours cette semaine
804/11–10/11

Chap 3 : Codages optimaux (suite)

  • Source, entropie d'une source
  • Longueur moyenne d'un codage, codage optimal
  • Théorème du codage sans bruit
Suite du précédent
911/11–17/11

Chap 3 : Codages optimaux (fin)

  • Critères de non-optimalité d'un codage
  • Construction de codages optimaux (Algorithme et codage de Huffman)
  • L'algorithme de Huffman dans les logiciels de compression

TP6 : Compression de données

TP sur 2 semaines

1018/11–24/11

Chap 4 : Détection/correction des erreurs

  • Motivation
  • Exemple du numéro de carte bancaire
  • Canal binaire symétrique sans mémoire
  • Distance de Hamming et poids de Hamming
  • Exemple du codage par bit de parité
  • Rendement d'un codage
Suite de la semaine précédente
1125/11–01/12

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

  • Exemple du codage par répétition
  • Capacité de détection et correction en fonction de la distance minimale d'un code
  • Codages linéaires
    • Distance minimale d'un codage linéaire
    • Matrice génératrice

TP7 : détection et correction d'erreurs

1202/12–08/12

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

  • 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
1309/12–15/12

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 (pour moitié les TP du semestre et pour moitié le 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.

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.
Codages optimaux et 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.
Pourquoi l'entropie (en théorie de l'information) s'appelle-t-elle l'entropie ? Voici ce qu'en dit Shannon, à l'origine de la notion d'entropie :
My greatest concern was what to call it. I thought of calling it ‘information’, but the word was overly used, so I decided to call it ‘uncertainty’. When I discussed it with John von Neumann, he had a better idea. Von Neumann told me, ‘you should call it entropy, for two reasons. In the first place your uncertainty function has been used in statistical mechanics under that name, so it already has a name. In the second place, and more important, nobody knows what entropy really is, so in a debate you always have the advantage’.
Claude Shannon, « Energy and Information » dans Scientific American, 1971
Détection et correction d'erreurs
Une vidéo sur le codage de Hamming