Voir la source de Théorie des codes

{{à recycler|date=janvier 2006|thème=télécommunications}}
[[Fichier:Hamming.jpg|vignette|Visualisation bidimensionnelle de la [[distance de Hamming]], une mesure essentielle dans la théorie des codes]]
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 [[canal de communication|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 [[code correcteur|codes correcteurs]].

== Histoire ==

En définissant l'[[information]] de façon [[mathématiques|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 [[code correcteur|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 ==

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 [[système trinaire|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. <math>C</math> est un code contenant <math>M</math> mots de code, c'est-à-dire, de ''dimension'' M. La ''longueur'' d'un mot de code est dénotée par <math>n</math>. Un tel code est dit code <math>(n,M)</math>.

=== Détection et correction d'erreurs ===

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

=== Distance minimale et décodage ===

{{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é <math>d</math>. Un tel code est dit code <math>(n,M,d)</math>.

=== Familles de codes ===
==== Codes équivalents ====

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

==== Types de codes ====

On distingue généralement trois types de codes.
* Un [[code linéaire]] est un [[code correcteur]] à qui l'on impose une structure d'[[espace vectoriel]].
* Un [[code cyclique]] est un code correcteur qui a davantage de structure que celle d'un espace vectoriel. En général, on peut concevoir les mots de code comme des [[polynôme formel|polynômes]]. Exemple : le [[code de Reed-Solomon]].
* 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 le message encodé.

Par ailleurs, certains codes correcteurs peuvent être utilisés comme [[code quantique|codes quantiques]].

D'autres types de codes importants sont :
* [[code algébrique]]
* [[code aléatoire]]

==== Familles ====

Les codes correcteurs peuvent aussi être classés par familles.
* Un code de parité ajoute un ou plusieurs [[Bit de parité|bits de parité]] au message.
* Un [[code de répétition]] envoie plusieurs copies de chaque bit à être transmis.
* Les [[code de Hamming|codes de Hamming]] forment la famille la plus connue. Les codes de Hamming [[code binaire|binaires]] sont équivalents aux [[code cyclique|codes cycliques]] et certains non binaires le sont aussi.
* Un [[code de Golay]] est un [[code linéaire]] considéré important en théorie et en pratique.
* 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.
* Les [[code BCH|codes BCH]] sont une généralisation des [[code de Hamming|codes de Hamming]]. Il s'agit aussi de codes cycliques. Un cas particulier est le [[code de Reed-Solomon]].
* Un [[code de résidu quadratique]] est un code cyclique basé sur la [[Résidu quadratique|résiduosité quadratique]].
* Un [[code de Goppa]] qui, comme les codes cycliques, est basé sur un polynôme, dit polynôme de Goppa.
* Un [[code stabilisateur]] est basé sur la mesure d'un [[décodage par syndrome|syndrome]], c'est-à-dire d'un [[vecteur]] dans <math>F_2^{n-k}</math>.
* Un {{Lien|trad=Expander code|code expandeur}} est un code linéaire avec lequel il est toujours possible de corriger une fraction constante d'erreurs.
* Les [[code superconcentrateur de Spielman|codes superconcentrateur de Spielman]] sont les seuls codes pouvant être codés et décodés en temps linéaire.
* Un [[code alternant]] est un code linéaire d'importance pratique.
* Un [[code de Hadamard]] est un code généré à partir d'une [[matrice de Hadamard]].
* Un code [[LDPC]] est un code qui possède une matrice de parité creuse.

==== Combinaisons de codes ====

On peut obtenir de nouveaux codes à partir d'opérations qui combinent un ou deux codes de base.
* opérations triviales : poinçonnage ou raccourcissement
* [[concaténation]] : [[code de Forney]], {{Lien|trad=Justesen code|code de Justesen}}
* produit

==== Autres propriétés ====

On distingue aussi certaines classes de codes par leurs propriétés.
* [[code intersectant]]
* [[code séparant]]
* (2014)<sub> dissimile et biner =111110110</sub>

=== Code et « design » ===

Il y a une connexion entre les codes et les [[Design combinatoire|designs combinatoires]].

=== Le problème principal de la théorie des codes ===

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

== Codage de source ==

{{Article détaillé|Codage de source}}

Le but du codage de source peut être de compresser l'[[Théorie de l'information|information répétitive du langage, sa redondance]]. Pour toute langue, on peut considérer l'[[entropie de Shannon|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 ==

Le but est d'ajouter de l'information redondante à un message pour compenser le bruit sur le [[Canal de communication (théorie de l'information)|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'''.

[[Cryptographie asymétrique|Certains problèmes cryptographiques]] sont basés sur l'hypothèse de la [[Théorie de la complexité (informatique théorique)|difficulté]] du décodage.

== Théorie algébrique des codes ==

{{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èbre|algébrique]] par opposition à l'approche traditionnelle qui est [[probabilité|probabiliste]]<ref>Préface de {{en}} [[Elwyn Berlekamp|Elwyn R. Berlekamp]], ''{{Lang|en|Algebraic Coding Theory}}'', [[McGraw-Hill Education|McGraw-Hill]], 1968, 466 p.</ref>. 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 ==
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 [[Manuscrit de Voynich|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 {{date-|30 mai 1968}}). L'université de [[Université Stanford|Stanford]] a également {{référence souhaitée|comparé les vocabulaires respectifs}} 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 plusieurs dizaines d'auteurs (au minimum 30 auteurs différents, probablement 50, au plus 100), au départ dans plusieurs langues, sur une période de deux cents ans<ref>[https://www.youtube.com/watch?v=k5pF5seXGIM Interview Jean-Jacques Walter 8/10/2013 dans l'émission "Le Grand témoin"]</ref>{{,}}<ref>[https://www.youtube.com/watch?v=6uOKexZoeKM&ebc=ANyPxKojVfBYEL0NbFNq-nS-bt_5mEqbgZfNZ9KGQyf1ZAgl2lXVS6BjEP2VuT1hTsq--f27N9vRDDJIAYTPu6PedpYBBvkD7Q Analyse statistique du coran].</ref>.

Dans la littérature de fiction, cette théorie sert de pivot au journaliste du ''Monde'' [[Robert Escarpit]] dans son ouvrage ''[[Le Littératron]]'' où un spécialiste utilise un ordinateur pour construire à partir de propos relevés dans des conversations de cafés le discours [[Populisme (politique)|populiste]] ultime, qui suscite d'abord les quolibets, mais peu à peu montre une efficacité redoutable.

== Références ==
{{Références}}

== Voir aussi ==
=== Articles connexes ===
* [[Code comma-free]]
* [[Code correcteur]]
* [[Méthode de décodage]]

=== Bibliographie ===
;Ouvrages
* Jean-Guillaume Dumas, Jean-Louis Roch, Éric Tannier et Sébastien Varrette, ''Théorie des codes (Compression, cryptage, correction)'', [[Dunod]], 2013, {{2e}} éd. ({{1re}} éd. 2007), 384 p. {{ISBN|978-2-10-059911-0}} {{présentation en ligne|lien=http://www.dunod.com/informatique-multimedia/fondements-de-linformatique/mathematiques-et-informatique-theorique/theorie-des-codes}}
* {{Ouvrage
|langue=fr
|auteur1=Bruno Martin
|titre=Codage, cryptologie et applications
|lieu=Lausanne
|éditeur=[[Presses polytechniques et universitaires romandes]]
|année=2004
|pages totales=354
|isbn=978-2-88074-569-1
|lire en ligne=https://books.google.com/books?id=SNYrhjDGlPsC&printsec=frontcover
}}.
;Articles
* {{article
 |nom1=Woryna|prénom1=Adam
 |titre=On the proportion of prefix codes in the set of three-element codes
 |journal=Discrete Mathematics
 |volume=343|numéro=8|année=2020
 |numéro article = 111939|doi=10.1016/j.disc.2020.111939}}.

=== Liens externes ===
* {{Lien web|url=https://www.math.u-bordeaux.fr/~kbelabas/teach/Agreg/code.pdf|titre=Cours de code|auteur=Christine Bachoc|site=[[université Bordeaux I]]|année=2004-2005}}
* Joël Le Roux, ''[http://www.essi.fr/~leroux/transmission/ Notions de communication numérique]'', [[Polytech Nice-Sophia]], 2001
* {{Lien archive|url=http://www-id.imag.fr/~svarrett/cours.html#theorie_code|titre=Théorie des codes (polycopié de cours)|site=[[ENSIMAG]]|horodatage archive=20080915192441|auteur=Yves Denneulin, Jean-Guillaume Dumas, Gregory Mounié, Jean-Louis Roch, Karim Samaké, Eric Tannier, Sébastien Varrette}}<!--probablement ancienne version du livre ''Théorie des codes (Compression, cryptage, correction)'' ci-dessus-->

{{Portail|télécommunications}}

[[Catégorie:Théorie des codes| ]]
[[Catégorie:Détection et correction d'erreur]]