Codage de l'information

On s'intéresse ici aux moyens de formaliser l'information afin de pouvoir la manipuler (principalement pour la transmettre). On ne s'intéressera donc pas au contenu mais seulement à la forme.

Sommaire

1 Alphabet, mot, langages

1.1 Définitions
1.2 Opérations

2 Codages et codes

2.1 Codage
2.2 Code

3 Applications, exemples

Alphabet, mot, langages

Définitions

On définit un alphabet comme un ensemble non vide de symboles, par exemple :

A = {a,b,,...,z}, l'alphabet latin ;
A = {0,1,2,..,9}, les chiffres dits arabes (en fait, indiens ; dans la numération arabe, le chiffre 5 ressemble à notre 0) ;
A = {0,1,...,9, A, B,...,F}, les chiffres hexadécimaux.
A = {0,1}, l'alphabet de la logique booléenne.
A = {A,T,G,C}, les bases de l'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 de 0 lettre est nommée le mot vide, 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'ADN, ces règles sont contenues dans le ribosome, dans les langues naturels, elles sont contenues dans leur lexique, sur un ordinateur, elles sont présentes dans les circuits de l'unité centrale

Opérations

Soit un alphabet $A$ et un entier naturel $n$ .
On note $A n$ l'ensemble de tous les mots de longeur $n$ sur $A$ . et on note $A *$ l'ensemble de tous les mots de $A$ .
On dispose de: $A^* = \bigcup_{n \geq 0}^{\infty}A^n$ (fermeture de Kleene).
On définit l'opération de concaténation $\cdot : A^* \times A^* \rightarrow A^*$ qui à $(u, v)$ associe un mot $w$ qui est constitué de la suite de lettres de $u$ puis celle de $v$ .
Exemple: « marc » $\cdot$ « et sophie » = « marc et sophie » (les guillemets servent à délimiter les symboles, elles ne sont pas des éléments de $A$ ).

Propriétés:
- $\cdot$ est associatif : $\forall u, v, w \in A^*, (u \cdot v) \cdot w = u \cdot (v \cdot w)$
- $\cdot$ admet ε comme élément neutre : $\forall u \in A^*, u \cdot \epsilon = \epsilon \cdot u = u$
- $\cdot$ n'est PAS commutative.

Codages et codes

Codage

Soit L et M deux langages.
Un codage c de L dans M est un morphisme (pour l'operation .) injectif. En d'autres termes, c'est une correspondance entre les mots de L et ceux 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. ( $\forall u,v \in L, c(u.v) = c(u).c(v)$ ).

Code

Un langage L sur un alphabet A est un code si et seulement s'il n'existe pas deux factorisations différentes des mots $A *$ avec des mots de L.