Département d'informatique et de recherche opérationnelle
IFT 6170 --- A97
Théorie et application des codes correcteurs
Professeur: Claude Crépeau, 3347 André--Aisenstadt
Début des cours: le jeudi 4 septembre
Horaire du cours:
mercredi 10:30-12:30, jeudi 11:30-13:30
Local du cours: Z-230
Objectifs:
La théorie des codes correcteurs étudie les façons de
transmettre sur un canal imparfait des messages avec grande fiabilité.
Ce cours considérera tout d'abord des modèles de transmissions et des modèles
d'erreurs jugés réalistes. On apprendra (ou revisera)
ensuite des notions mathématiques de base afin d'étudier les
codes correcteurs:
les calculs sur les corps finis et dans les espaces vectoriels.
On définira la notion de code et considérera les problèmes
généraux de codage et décodage d'information pour leur transmission
sur un canal imparfait.
On verra de nombreux types de code: Hamming, BCH, Reed-Müller, Reed-Solomon,
Alternant, cyclic, Gollay, Goppa, Hadamar, Intersectant, etc,
ainsi que les diverses méthodes de codage et décodage qui leur sont associées.
On considérera le problème de la construction de codes ayant de bonnes
performances et montrera des bornes inférieures et supérieures sur
les performances possibles des codes.
À cette fin, on apprendra des méthodes de combinaisons de codes:
concaténation, produit.
On analysera les performances des codes aléatoires, qui
sont généralement bien supérieures à celle obtenues par des
construction explicites.
On étudira des exemples d'applications de codes correcteurs aux
télécommunications (avec des sondes spaciales par exemple), au
stockage des données (sur des Disques Numériques par exemple),
à l'authentification (le code ISBN par exemple) et
à la cryptographie (systèmes de chiffrements basés
sur des codes, problèmes cryptographiques équivalent à des problèmes
de codage).
On verra enfin des sujets plus avancés: géométrie algébrique et
codes algébriques de Goppa (seule méthode de construction produisant des
codes meilleurs que les codes aléatoires),
graphes expandeurs, codes expandeurs et
codes superconcentrateurs de Spielman
(seuls codes pouvant être codés et décodés en temps linéaire).
PRÉREQUIS:
Ne pas craindre les mathématiques discrètes.
évaluation:
Vous devrez faire six devoirs théoriques sur une base individuelle.
Vous n'aurez pas d'examen et le cours ne demande pas de programmation explicite.
L'usage de l'ordinateur sera de temps en temps utile à la résolution des
problèmes de devoir.
Livres utiles:
[Auteur] Roman, Steven.
[Titre] Coding and information theory / Steven Roman.
1. Math-Info QA 268 R646 1992
[Auteur] MacWilliams, Florence Jessie, 1917-
[Titre] The theory of error- correcting codes / F. J. MacWilliams, N. J. A. Sloane.
1. Math-Info QA 268 M33 pt. 1
2. Math-Info QA 268 M33 pt. 2