Voir la source de Codage de l'information

Le '''codage de l’information''' concerne les moyens de formaliser l'information afin de pouvoir la manipuler, la stocker ou la transmettre. Il ne s'intéresse pas au contenu, mais seulement à la forme et à la taille des informations à coder.

== Alphabet, mot, langages ==
=== Définitions ===
On définit un <tt>alphabet</tt> comme un ensemble non vide de symboles, par exemple : 
* A = {a,b,c,…,z}, l'[[alphabet latin]] ;
* A = {0,1,2,…,9}, les [[chiffres arabes|chiffres dits arabes]]  ;
* A = {0,1,…,9,A,B,…,F}, les [[Système hexadécimal|chiffres hexadécimaux]] ;
* A = {0,1}, l'alphabet de la [[logique booléenne]] ;
* A = {A,T,G,C}, les bases de l'[[Acide désoxyribo-nucléique|ADN]] qui codent notre [[génome]] (cet alphabet est le sujet principal de la [[bio-informatique]]).
On nomme ''lettre'' un élément d'un alphabet.

On nomme ''mot'' une suite finie de lettres. La suite qui ne contient aucune lettre est nommée ''mot vide'', et notée ε.

On  nomme ''langage'' un ensemble de mots associé à certaines règles d'interprétation (sans cette dernière restriction, n'importe quelle table de valeurs aléatoires pourrait être nommée langage). Dans le cas de l'[[Acide désoxyribonucléique|ADN]], ces règles sont contenues dans le [[ribosome]] ; dans les langues naturelles, elles sont contenues dans leur [[lexique]] ; dans un [[ordinateur]], elles sont présentes dans les circuits de l'[[unité centrale]].

=== Opérations ===
Soit un alphabet <math>A</math> et un entier naturel <math>n</math>.<br />
On note <math>A^n</math> l'ensemble de tous les mots de longueur <math>n</math> sur <math>A</math> et <math>A^*</math> l'ensemble de tous les mots de <math>A</math>.<br />
On dispose de : <math>A^* = \bigcup_{n \geq 0}^{\infty}A^n</math> ([[fermeture de Kleene]]).<br />
On définit l'opération de [[concaténation]] 
<math>\cdot : A^* \times A^* \rightarrow A^*</math> qui à <math>(u, v)</math> associe un mot <math>w</math> qui est constitué de la suite de lettres de <math>u</math> puis celle de <math>v</math>.<br />
''Exemple'' : « marc » <math>\cdot</math> « et sophie » = « marc et sophie » (les guillemets servent à délimiter les symboles, ce ne sont pas des éléments de <math>A</math>).
* '''Propriétés''' : 
** <math>\cdot</math> est [[associativité|associatif]] : <math>\forall u, v, w \in A^*, (u \cdot v) \cdot w = u \cdot (v \cdot w)</math>
** <math>\cdot</math> admet ε comme [[élément neutre]] : <math>\forall u \in A^*, u \cdot \epsilon = \epsilon \cdot u = u</math>
** <math>\cdot</math> n'est ''pas'' [[commutativité|commutative]]

== Codages et codes ==
=== Codage ===
Soit L et M deux langages.<br />
Un <tt>codage</tt> c de L dans M est un [[morphisme]] (pour l'opération <math>\cdot</math>) injectif.
En d'autres termes, c'est une correspondance entre les mots de L et ceux de M, où à tout mot de L est associé un unique mot de M et tel que le codage de la concaténée soit égale à la concaténée des codages. (<math> \forall u,v \in  L, c(u.v) = c(u).c(v) </math>).

=== Codes ===
Un langage L sur un alphabet A est un <tt>code</tt> si et seulement s'il n'existe pas deux factorisations différentes des mots <math>A^*</math> avec des mots de L.

== Applications, exemples ==
* [[Codage Manchester]]
* [[Codage NRZ]]
* [[Codage Miller]]
* [[Code Baudot]]

== Articles connexes ==
* [[Fuite d'information]]

{{Palette|Informatique théorique}}
{{Portail|informatique théorique}}

[[Catégorie:Théorie de l'information|Codage de l'information]]