Evènement pour le groupe GT Graphes et Applications


Date 2010-02-19  14:00-15:00
Titre Codes et graphes extenseurs 
RésuméLes graphes extenseurs (expander graphs) sont des familles de graphes pour lesquels tout sous-ensemble de sommets X suffisamment distinct de l'ensemble complet a un nombre de voisins au moins égal à cjXj pour une certaine constante c. Cette propriété se caractérise par un large écart entre les première et seconde valeurs propres du graphe. Les premières constructions de tels graphes remontent aux années 1980 et ont trouvé de nombreuses applications depuis, principalement dues à ce qu'ils ont des propriétés typiques de graphes aléatoires mais non triviales à obtenir constructivement. Or justement, les meilleurs codes correcteurs étant des codes aléatoires typiques, il est tentant d'essayer d'obtenir des bonnes constructions de codes par l'intermédiaire de graphes extenseurs. L'idée de construire des codes à l'aide d'un graphe et de petits codes linéaires constituants remonte à Tanner (1981) et pris son plein essor en 1996 grâce à un travail de Sipser et Spielman qui montrèrent, en s'appuyant sur la propriété d'expansion, que l'idée de Tanner permet à la fois la construction de codes binaires asymptotiquement bons et de garantir la correction d'un nombre d'erreurs proportionnel en la longueur du code n, le tout en temps quasi-linéaire en n. Nous présenterons cette construction ainsi qu'un certain nombre de variantes et de développements récents. Cette approche peut être vue comme intermédiaire entre le codage algébrique traditionnel et les méthodes plus modernes de décodage itératif impliquant les codes à matrice de parité creuse (LDPC).  
LieuSalle 178 
OrateurGilles Zémor 



Aucun document lié à cet événement.

Retour
Retour à l'index