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