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
Éric Wegrzynowski et Mikaël Salson
dernière modification : 13/11/2017 à 11:42:19
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 : 13/11/2017 à 11:42:19

Emploi du temps 2016-2017

Gpe Nature Horaire Salle Enseignant e-mail
TOUS C Lundi 8h30-10h00 M1 Chatelet 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 Dimitri Gallois Dimitri.Gallois(at)inria.fr
S3 - 5 TP Jeudi 10h20-11h50 M5 A14 Dimitri Gallois
Éric Wegrzynowski et Mikaël Salson
dernière modification : 13/11/2017 à 11:42:19

Année 2017–2018

Semaine Préparation Cours TP Remarque
104/09–10/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
211/09–17/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

318/09–24/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

425/09–01/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
502/10–08/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
    • Codes « à virgule» 
    • Codes préfixes
  • Représentation des codes dans un arbre
  • Décodage d'un code préfixe à l'aide d'un arbre

TP3 : Base 64

Sujet de TP sur 2 semaines

609/10–15/10Lire les parties 2.6.2 à 2.6.4 (pages 41 et 42)

Chap 2 : Codes et codages (suite)

  • 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
    Algorithme de Sardinas Patterson
Suite du précédent
716/10–22/10Lire la partie 3.1.1 (page 51).
  • Comment déterminer si un langage est un code ? (résumé et exemples)

Chap 3 : Codages optimaux

  • Source, quantité d'information, entropie d'une source
  • Longueur moyenne d'un codage, codage optimal

TP4 : Codages et décodages

Sujet de TP sur 2 semaines

823/10–29/10

Chap 3 : Codages optimaux (suite)

  • Théorème du codage sans bruit
  • Critères de non-optimalité d'un codage
Suite du précédentDS de codage le 27/10 de 16h00 à 18h00 (polycopié autorisé)
30/10–05/11Interruption pédagogique d'automne. Pas de cours cette semaine
906/11–12/11

Chap 3 : Codages optimaux (fin)

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

TP5 : Compression de données

TP sur 2 semaines

1013/11–19/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
1120/11–26/11

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
    • Matrice de contrôle
    • Détection et correction d'erreurs avec un codage linéaire

TP6 : détection et correction d'erreurs

1227/11–03/12

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

  • Codages de Hamming
    • Exemple sur le [7, 4, 3]
Suite de la semaine précédente
1304/12–10/12
1411/12–17/12
1518/12–24/12Contrôle de TP le 18/12 de 8h à 12h30 (M5 salles A11 à A16 : la répartition sera déterminée ultérieurement.)
Éric Wegrzynowski et Mikaël Salson
dernière modification : 13/11/2017 à 11:42:19

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 : 13/11/2017 à 11:42:19

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
Éric Wegrzynowski et Mikaël Salson
dernière modification : 13/11/2017 à 11:42:19