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
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 109 É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 SUP 210 Francesco De Comité Francesco.De-Comite(at)univ-lille.fr
S3 - 1 TP Mercredi 8h30-10h M5 A11 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 A3 Léopold Weinberg leopold.weinberg(AT)univ-lille.fr
S3 - 3 TP Mercredi 10h20-11h50 SUP 118 Léopold Weinberg
S3 - 4 TD Vendredi 8h30-10h M5 A6 Mikaël Salson mikael.salson(AT)univ-lille.fr
S3 - 4 TP Mardi 15h40-17h10 SUP 118 Mikaël Salson
S3 - 5 TD Mardi 8h30-10h M5 A1 Dimitri Gallois Dimitri.Gallois(at)inria.fr
S3 - 5 TP Jeudi 10h20-11h50 SUP 116 Dimitri Gallois

Année 2018–2019

Semaine Préparation Cours TP Remarque
110/09–16/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
217/09–23/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

324/09–30/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

401/10–07/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
Suite de la semaine précédente
508/10–14/10Lire la partie 2.2.7 du polycopié

Chap 2 : Codes et codages (suite)

  • Factorisation d\'un mot dans un langage
  • Codes
  • Codages
  • Familles de codes
    • Codes de longueur fixe

TP3 : Conversion de caractères

615/10–21/10Lire les parties 2.6.2 à 2.6.4 (pages 41 et 42)

Chap 2 : Codes et codages (suite)

  • Familles de codes (suite)
    • 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)
  • 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

TP4 : Base 64

722/10–28/10Lire la partie 3.1.1 (page 51).
  • 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

DS de codage le 26/10 de 16h30 à 18h30 (polycopié autorisé)
29/10–04/11Interruption pédagogique d'automne. Pas de cours cette semaine
805/11–11/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
912/11–18/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

1019/11–25/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
1126/11–02/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

1203/12–09/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
1310/12–16/12
1417/12–23/12Contrôle de TP le 17/12 de 8h à 12h30 (M5 salles A11 à A16

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