Exercices couche physique ( OSI ) : Code correcteur

                 

Modèle OSI - couche physique

                                 

Exercice 1: Code correcteur

1) Donnez la définitions ainsi que la portée en terme de détection et de correction de la distance de Hamming d’un code. Montrer entre autre la propriété de détection. {sidebar id=1}

2) Que vaut la distance de Hamming de ce code?

3) Combien d’erreurs peut-il détecter? Et combien d’erreurs peut-il corriger?

 

4) Le récepteur reçoit le mot 1110000000, quel est le mot initial?

Corrigés

1 -Par définition la distance de Hamming d’un code est égale à la distance minimale entre deux mots valide du code. Si la distance d’un code est égale à d, l’altération de d-1 bits d’un mot de code valide ne donnera pas un autre mot valide du code.

Un code correcteur d’erreur contient les quatre mots suivants :

0000000000 0000011111 1111100000 1111111111

2 -La distance Hamming de ce code est d = 5.

3 -Il peut détecter jusqu’à 4 erreurs (d - 1), et corriger au maximum 2 erreurs ( d12 ).

4 -Le mot reçu a une distance 2 du mot 1111100000 et une distance 3 du mot 0000000000 (tous les deux détectées grâce à la distance Hamming = 5). La seule correction possible, cependant, est celle vers le mot 1111100000 (le maximum de correction supporté par le code).

Exercice 2: Code correcteur

Le langage Shadok contient quatre mots de base: ga, bu, zo et meu.

1) Donnez un codage binaire de longueur fixe minimal permettant de coder les mots précédents. Commentez ses propriétés détectrices et correctrices. {sidebar id=6}

Solution:

Il y a 4 mots à coder, le codage de longueur fixe minimal est un codage à 2 bits. On peut choisir par exemple µ(ga) = 00, µ(bu) = 01, µ(zo) = 10 et µ(meu) = 11. La distance de Hamming de ce code est 1, ce code ne peut donc pas détecter et encore moins corriger d’erreur.

2) Soit le codage binaire : (ga) = 0000, (bu) = 0110, (zo) = 1001 et (meu) = 1111. Combien d’erreurs peut-il détecter? Combien d’erreurs peut-il corriger?

Solution:

La distance de Hamming étant égale à 2, le code est donc 1-détecteur et 0-correcteur.

3) On a reçu 0000 0110 0100 1001 puis 0000 0110 0110 1001. De quoi est-on sûr?

Solution:

Le troisième quartet reçu 0100 n’est pas un mot du code, on est donc s qu’il y a eu au moins une erreur. Tous les autres blocs reçus sont des mots du code, cependant on ne peut être sûr de rien en ce qui concerne l’occurrence d’erreur. On sait par contre que, s’il y a eu erreur sur un autre quartet, le nombre d’erreurs est égal à 2 ou 4.

4) Donnez un codage binaire 2-correcteur.

Solution:

Pour qu’un codage soit 2-correcteur, il faut que sa distance de Hamming soit au moins égale à 2 × 2 + 1 = 5. On peut proposer le code de longueur 8 suivant : ?(ga) = 11100000, ?(ga) = 00000111, ?(ga) = 00011000 et ?(ga) = 11111111.