Accueil » Publications » Le Bulletin Vert » Matériaux pour une documentation » Codes correcteurs
  APMEP   Codes correcteurs

Article du bulletin 443

Adhérer ou faire un don

par Josèphe BADRIKIAN.

Collection TECHNOSUP, édition Ellipses.

181 pages en 10,2 × 7,7.

L’auteur a enseigné les mathématiques à l’université d’Auvergne, où elle a été responsable du Centre de formation à l’informatique pédagogique et chargée de mission à l’IUFM de la région Auvergne.

Le chapitre I présente le sujet du livre : définir, pour protéger les messages des erreurs de transmission, des stratégies de « sur-codage », et des algorithmes pour détecter, à la réception, les messages erronés et les corriger « au mieux ». Il est important de bien s’imprégner du vocabulaire introduit. Les mots d’information, blocs à coder, sont traduits par des suites de même longueur r de 0 et de 1, c’est-à-dire par un vecteur de $B^r$ , B désignant l’ensemble $\{0,1\}$. Le codage associe à tout mot de $B^r$ un mot de $B^n$, n > r. Le codage est systématique si l’information est constituée par la suite des r premiers bits pour chaque mot codé.

Le codage par parité est une application simple de ces notions, mais sans permettre de correction. Le code de parités croisées est plus efficace dans le cas (le plus probable sous certaines hypothèses) d’une seule erreur. Dans ces codages comme dans tous les autres qui suivront, la probabilité de détection de message erroné et celle de l’exactitude du message corrigé donnent lieu à des calculs simples mais bien parlants pour apprécier l’efficacité des algorithmes.

$B^r$ étant considéré comme espace vectoriel sur B muni de sa structure de corps, les autres codages étudiés, à partir du chapitre II, sont les codages linéaires, c’est-à-dire des applications linéaires injectives de $B^r$ dans $B^n$ ; l’image est un code $Cl_{n,r}$. Les bases de l’algèbre linéaire jouent un rôle essentiel, en particulier les matrices à n lignes et n − r colonnes, dites matrice de contrôle, dont le noyau est le code considéré. Chacune permet de classer les messages reçus, en particulier d’identifier les messages incorrects, et d’en proposer une correction automatique par addition d’un vecteur de correction de même syndrome (image du mot par la matrice de contrôle choisie) que le message reçu, et de poids le plus faible.

La distance de Hamming, son minimum pour les vecteurs du code, renseigne sur la capacité de détection des messages erronés, sur la capacité de correction, et conduit à la notion de code de Hamming.

La suite (Chap. IV à VII) est consacrée aux codages linéaires dits polynomiaux car défi- nis en interprétant les mots comme suite des coefficients de polynômes de B[x] de degré r − 1. Le codage est obtenu par multiplication par un polynôme fixé g(x) de degré n − r, et en prenant le reste de la division euclidienne du résultat par un autre polynôme fixé p(x) de degré n. Les codes cycliques correspondent à $p(x) = 1 + x^n$ .

L’étude de leurs générateurs conduit à celle des racines n-ièmes de l’unité (chap. IV) dans un corps fini de caractéristique 2. Il est agréable et « réconfortant » de voir des éléments de la théorie de Galois servir au développement des télécommunications. Le dernier chapitre est consacré aux codes cycliques BCH et de Reed-Solomon.

Le texte est accessible à des étudiants de niveau fin de première année de premier cycle ou de math.sup. Les notions d’algèbre sont introduites au fur et à mesure, en situation.

La typographie est claire, bien aérée. Chaque chapitre débute par une introduction générale et comporte à la fin un résumé de synthèse. Résultats et définitions sont illustrés par des exemples. À la suite immédiate de chaque chapitre figurent des exercices adaptés, corrigés très en détail.
L’ensemble réalise une progression efficace et très agréable. Bien conçu pour les filières technologiques cet ouvrage est aussi utilisable comme source d’exercices intéressants et motivants dans l’enseignement de l’algèbre, et du calcul des probabilités. L’amateur éclairé trouvera également intérêt et plaisir à consulter cet ouvrage.

(Article mis en ligne par Armelle BOURGAIN)
 Accueil   Plan du site   Haut de la page   Page précédente