Cours CDC
Dans la vie quotidienne, les numéros qu'on utilise utilisent des mécanismes de détection d'erreur (code de carte bleue). Le code consiste à multiplier par 2 les chiffres d'indice impairs, sommer tous les chiffres, et le résultat doit être divisible par 10. Si on change deux chiffres par erreur, on n'a aucune garanti de détecter l'erreur. Le fait de multiplier par deux un chiffre sur deux permet de détecter les erreurs de permutation de 2 chiffres consécutifs.
Canal binaire symétrique sans mémoire (CBSSM)
- Binaire : 0 et 1
- Symétrique : la probabilité d'erreur est identique sur un 0 ou un 1
Sans mémoire : la probabilité d'erreur ne dépend pas des erreurs précédentes
Nous considérerons uniquement les erreurs de substitution, pas d'ajout/suppression
Correction d'erreur
Distance de Hamming
Distance de Hamming
Pour deux mots binaires \( v \) et \( v ^{\prime} \) de même longueur. La distancs de Hamming de ces deux mots correspond au nombre d'indices auxquels \( v_{i} \neq v ^{\prime}_{i} \)
Poids de Hamming
Pour un mot binaire \( v \), le poids de Hamming est le nombre de bits à 1 de \( v \)
En particulier, on a :
\[ d_{H} \left(v, v ^{\prime}\right) = W_{H} \left(v \oplus v ^{\prime}\right) \]
Si la probabilité d'avoir une erreur sur 1 bit est \( p \), alors la probabilité d'avoir au moins \( x \) erreurs sur \( y \) bits est :
\[ \sum_{i=x}^{y}{\binom{8}{2}(1-p)^{y-i}p^{i} } \]
Codage par parité
ASCII : 128 caractères -> un bit non utilisé sur un octet
\(Parite(v)\)
Le codage par parité d'un mot \( v \) consiste à ajouter un bit au mot à transmettre de manière à ce que \(W_{H}(Parite(v))\) soit pair. Le bit ajouté est appelé bit de parité
Pour pouvoir corriger 1 erreur, il faut que le mot reçu soit le plus proche d'un seul mot de code. Si le code peut corriger une erreur, alors quand on reçoit un mot avec une seule erreur, ce mot reçu, il se retrouve dans une seule boule de rayon 1 centrée sur un mot de code
Distance minimale d'un code
La distance minimale d'un code c'est le minimum de la distance entre deux mots du code
\[ d_{\text{ min } } = \min \{ d_{H}(v, w) | v, w \in C, v \neq w\} \]
Pour que mon codage détecte une erreur, quelle doit être sa distance minimale ?
\[ d_{min } \geq 2 \]
car si on transmet un mot du code et qu'il est reçu avec une erreur, le mot reçu ne fera pas parti du code -> détection du code
t-détection d'erreurs ? \( t + 1 \)
Quelle distance pour un t-correcteur ?
\( d_{min} \geq 2t + 1 \)
Codage par répétition
\( \operatorname{Repet}_{k}(u) = \underbrace{u .u .u.u \dots .u}_{k \text{ fois } } \)
\( d_{min}(\operatorname{Repet}_{k}) = k \)
Pour la correction d'erreur, on privilégie le bit majoritaire parmi les 3 mots
Autres codages
Codage systématique : de la forme \( c(u) = u . r \)
Le rendement
Le rendement est le rapport entre la taille du mot à envoyer (n) et la taille du mot envoyé (k)
\[ \operatorname{Rendement} = \frac{n}{k} \]
Codages linéaires
Coder un mot \( u = u_1 \oplus u_2 \) peut se faire avec le codage de \( u_1 \) et de \( u_2 \). On peut coder un mit binaire de longueur \( n \) (il y en a \( 2^{n} \) ) en ne connaissant que le codage de chacur des vecteurs unités de longueur \( n \)
\( [n, k, d] \)-codage linéaire
un \( [n, k, d] \)-codage linéaire \( c \) est un codage linéaire dont la distance minimale est \( d \) qui encode \( k \) bits en \( n \) bits
Pour un mot de taille 5, il y a 5 vecteurs unités. La matrice génératrice d'un codage linéaire est donc :
\begin{pmatrix} c(u_1) \\ c(u_2) \\ \dots \\ c(u_{n}) \end{pmatrix}où les vecteurs \( (u_1, \dots u_{n}) \) sont la base canonique de l'espace des mots de taille \( n \)
Codage par matrice génératrice
Coder un mot \( u \) avec un codage linéaire, c'est effectuer le produit :
\[ c(u) = u \times G \]
Où \( G \) est la matrice génératrice du codage
Alphabet
Un alphabet est un ensemble de mots (Octet, ascii, les pixels d'une image)
Source d'information
Une source d'information est définie par un alphabet de symboles \( \mathcal{S} = \{s_1, s_2, \dots , s_{\sigma }\} \) est une distribution de probabilités \( \mathcal{P} = \{p_1, p_2, \dots , p_{\sigma }\} \)
\( p_{i} \) est la probabilité que la source d'information produise un symbole \( s_{i} \). On a :
\[ \sum_{i = 1}^{\sigma }{p_{i}} = 1 \]
Le nombre de bits pour représenter un symbole devrait dépendre de sa probabilité d'apparition, pas du nombre de symboles. La quantité d'information d'un symbole est :
\[ I(s) = \log_{2} \left(\frac{1}{P(s)}\right) = -\log_{2}(P(s)) \]
Sans information de probablité, on représenterait chaque symbole avec \( \log_{2} (5) \) = 3 bits
| s | A | B | C | D | E |
|---|---|---|---|---|---|
| P(s) | \( \frac{1}{5} \) | \( \frac{2}{5} \) | \( \frac{1}{10} \) | \( \frac{1}{5} \) | \( \frac{1}{10} \) |
| I(s) | 2,3 | 1,3 | 3,3 | 2,3 | 3,3 |
La longueur moyenne d'un codage \( c \) est le nombre moyen de bits pour représenter un symbole d'une source dont l'alphabet est \( \mathcal{S} \)
\[ n(c) = \sum_{s \in \mathcal{S} }{p(s) |c(s)| } \]
Entropie d'une source
L'entropie d'une source \( S = (\mathcal{S}, \mathcal{P} ) \) est la quantité moyenne d'information véhiculée par un symbole de la source.
Autrement dit, c'est la longueur moyenne d'un codage qui utiliserait le nombre minimal debits pour représenter chaque symbole (sa quantité d'information)
\[ H(s) = \sum_{s \in \mathcal{S} }{p(s)I(s)} = - \sum_{s \in \mathcal{S} }{p(s) \log_{2}p(s)} \]
Compression d'information
Codage optimal
Un codage optimal est un codage dont la longueur moyenne est la plus faible pour une source donnée
Théorème du codage sans bruit (Shannon)
Un codage optimal \( c \) respects la définition suivants (où \( q \) est la taille de l'alphabet )
\[ H(s) \leq n(c) \leq H(s) + 1 \]
Prenons deux codages :
| s | A | B | C | D | E |
|---|---|---|---|---|---|
| P(s) | \( \frac{1}{5} \) | \( \frac{2}{5} \) | \( \frac{1}{10} \) | \( \frac{1}{5} \) | \( \frac{1}{10} \) |
| \( c_1(s) \) | 00 | 01 | 10 | 110 | 1110 |
| \( c_2(s) \) | 10 | 0 | 110 | 1110 | 1111 |
Si on représente \( c_1(s) \) dans un arbre :
plus tard :(
L'arbre binaire n'est pas complet, donc on peut raccourcir au moins une branche de l'arbre et donc au moins un mot du code. Donc le codage d'roigine n'était pas optimal puisqu'il existe un autre codage avec une longueur moyenne plus courte
Arbre binaire pas complet \( \implies \) codage non optimal
Maintenant, si on regarde la longueur moyenne des deux codages, elles sont égales (après optimisation de \( c_1 \) ). Donc, soit les deux codages sont optimaux, soit il ne le sont pas. Ici, ils ne le sont pas. En effet, le symbole D est codé avec un bit de plus que C alors que D a une probabilité deux fois plus grande d'apparaître que C.
Algorithmes pour trouver des codages optimaux
Algorithme de Fano
Entrées : S: Ensemble des symboles s_i
Entrées : P : distribution des probas
Fonction Fano(S, P):
si S a un seul symbole alors
Associer 0 au codage du symbole;
sinon
l : liste des symboles triés par probabilité décroissante
Séparer l en deux sous listes l1 et l2 dont la somme des probas est la plus proche possible;
Ajouter 0 au codage de chaque symbole de l1 et un 1 à chaque symbole de l2;
Fano(l1, P1);
Fano(l2, P2);
/!\ Pas optimal ! :(
Algorithme de Huffman
Entrées : S: Ensemble des symboles s_i
Entrées : P : distribution des probas
Huffman(S, P)
l : liste des symboles par proba croissante;
nœuds : file vide
tant que l et nœuds contiennent au moins deux éléments faire
retirer les deux éléments de probabilité minimale de l et/ou nœuds;
créer un nœud ayant deux descendants : les deux éléments de probabilité minimale;
enfiler le nœud créé dans nœuds
retourner la tête de nœuds