Théorie des codes

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher
Ce modèle est-il pertinent ? Cliquez pour en voir d'autres.
Cet article ou une de ses sections doit être recyclé (indiquez la date de pose grâce au paramètre date).

Une réorganisation et une clarification du contenu paraissent nécessaires. Discutez des points à améliorer en page de discussion ou précisez les sections à recycler en utilisant {{section à recycler}}.

En théorie de l'information, la théorie des codes traite des codes et de leurs propriétés et de leurs aptitudes à servir sur différents canaux de communication. On distingue deux modèles de communication : avec et sans bruit. Sans bruit, le codage de source suffit à la communication. Avec bruit, la communication est possible avec les codes correcteurs.

Histoire[modifier | modifier le code]

En définissant l'information de façon mathématique, l'étape fondatrice de la théorie des codes a été franchie par Claude Shannon. D'autres définitions existent, mais l'entropie de Shannon a été la plus fructueuse. Ainsi, on est apte à répondre aux deux questions fondamentales de la théorie de l'information : quelles sont les ressources nécessaires à la transmission de l'information, et quelle est la quantité d'informations que l'on peut transmettre de façon fiable.

C'est de cette dernière question du codage de canal que traite la théorie des codes. En répondant aux deux questions de base de la théorie de l'information, Shannon n'a justement pas fourni un ensemble très puissant de codes correcteurs. En particulier, il n'a pas déterminé d'exemple de code qui atteint la limite prévue par son théorème du codage de canal.

C'est ce vide que comble la théorie des codes. Il existe de nos jours une multitude de méthodes visant à produire de bons codes correcteurs.

Propriétés des codes[modifier | modifier le code]

On distingue d'abord les codes par la quantité d'information transmise par un symbole. Le canal binaire symétrique étant le plus commun, on considérera souvent un code binaire. Il existe cependant aussi des codes trinaires et, en général, des codes q-aires.

Les noms de variables suivants sont la plupart du temps, utilisés par convention. C est un code contenant M mots de code, c'est-à-dire, de dimension M. La longueur d'un mot de code est dénotée par n. Un tel code est dit code (n,M).

Détection et correction d'erreurs[modifier | modifier le code]

La plupart des codes s'utilisent soit pour la détection ou la correction d'erreur.

Distance minimale et décodage[modifier | modifier le code]

Article détaillé : Méthodes de décodage.

La distance minimale d'un code influe la probabilité d'erreur de décodage. La distance minimale est un paramètre important, dénoté d. Un tel code est dit code (n,M,d).

Familles de codes[modifier | modifier le code]

Codes équivalents[modifier | modifier le code]

Deux codes sont équivalents si toutes leurs propriétés de correction d'erreur sont les mêmes.

Types de codes[modifier | modifier le code]

On distingue généralement trois types de codes.

  • Un code non linéaire est un code correcteur qui peut être construit d'une variété de façons, sans obtenir la structure d'un espace vectoriel.

Il y a un petit nombre de cas spéciaux. Un code trivial est un code qui recopie littéralement le message initial, d'où sa trivialité. Un code systématique est un code pour lequel le message à encoder est inclus dans la message encodé.

Par ailleurs, certains codes correcteurs peuvent être utilisés comme codes quantiques.

D'autres types de codes importants sont :

Familles[modifier | modifier le code]

Les codes correcteurs peuvent aussi être classés par familles.

  • Un code de Reed-Müller est un code linéaire dont les propriétés de décodage sont considérées particulièrement pratiques.
  • Un code de Goppa qui, comme les codes cycliques, est basé sur un polynôme, dit polynôme de Goppa.
  • Un code expandeur (en) est un code linéaire avec lequel il est toujours possible de corriger une fraction constante d'erreurs.
  • Un code LDPC est un code qui possède une matrice de parité creuse.

Combinaisons de codes[modifier | modifier le code]

On peut obtenir de nouveaux codes à partir d'opérations qui combinent un ou deux codes de base.

Autres propriétés[modifier | modifier le code]

On distingue aussi certaines classes de codes par leurs propriétés.

Code et « design »[modifier | modifier le code]

Il y a une connexion entre les codes et les Design combinatoire (en).

Le problème principal de la théorie des codes[modifier | modifier le code]

Soit A_q(n,d) le plus grand M pour lequel il existe un code (n,M,d) et q-naire. Le problème principal de la théorie des codes est de déterminer ces valeurs.

Codage de source[modifier | modifier le code]

Article détaillé : Codage de source.

Le but du codage de source peut être de compresser l'information répétitive du langage, sa redondance. Pour toute langue, on peut considérer l'entropie d'un message, c'est-à-dire la quantité d'information transmise. Ceci donne lieu au théorème du codage de source.

Codage de canal[modifier | modifier le code]

Le but est d'ajouter de l'information redondante à un message pour compenser le bruit sur le canal de communication. Ceci donne lieu au théorème du codage de canal et c'est à celui-ci qu'on doit l'origine de la théorie des codes.

Certains problèmes cryptographiques sont basés sur l'hypothèse de la difficulté du décodage.

Théorie algébrique des codes[modifier | modifier le code]

Article détaillé : Théorie algébrique des codes.

La théorie algébrique des codes est un sous-domaine de la théorie des codes où les propriétés des codes sont exprimées algébriquement. Autrement dit, l'approche est algébrique par opposition à l'approche traditionnelle qui est probabiliste[1]. On y étudie principalement :

  • la construction de « bons » codes, c'est-à-dire avec certains paramètres souhaitables, tels :
    • la longueur des mots de code
    • le nombre total de mots de code valides
    • la distance de Hamming minimale entre deux mots de code valides
  • le décodage efficace de ces codes

Usages en analyse de textes[modifier | modifier le code]

L'analyse de codes est utile pour essayer de décoder un texte chiffré, si le code utilisé est faible (par exemple code de César ou de Vigenère). La détection des caractéristiques statistiques d'un texte permet également de vérifier, même sans en comprendre la langue, si un texte a eu plus d'un auteur (on peut ainsi affirmer que le Papyrus Voynich a eu deux auteurs distincts; voir article correspondant). Elle permet aussi d'analyser des textes de Victor Hugo et, par ces caractéristiques statistiques, de détecter la décennie de leur rédaction. Le Centre Scientifique d'IBM a également étudié les discours de Charles De Gaulle et montré que ces discours s'allongeaient au fil du temps, sauf pour quelques discours "critiques" (comme celui du 30 mai 1968). L'université de Stanford a également comparé les vocabulaires respectifs[réf. souhaitée] de Marcel Proust et de Paul Valéry. L'ingénieur Jean-Jacques Walter a également effectué cette analyse sur le texte du coran et a soutenu une thèse d'Etat lui attribuant selon lui aussi une trentaine d'auteurs, au départ dans plusieurs langues, sur une période de deux cents ans[2],[3].

Dans la littérature de fiction, cette théorie sert de pivot journaliste du Monde Robert Escarpit dans son ouvrage Le Littératron où un spécialiste utilise un ordinateur pour construire le discours populiste ultime, qui suscite d'abord les quolibets, mais peu à peu montre une efficacité redoutable.

Référence[modifier | modifier le code]

Voir aussi[modifier | modifier le code]

Bibliographie[modifier | modifier le code]

Liens externes[modifier | modifier le code]