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.

Correction d'erreur

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

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