-
Sihamais authorede4de6408
AISSAOUI Siham
KLEITZ Paco
SENSEBRENNER Amaury
Rapport de projet – Code Polynomial Correcteur d’Erreur
II - Derrière certaines matrices génératrices...
- De la matrice génératrice G, déduisez les propriétés suivantes du codes C :
- La taille des blocs que l’on peut encoder ; Le nombre de bits de contrôles rajoutés au message (et la taille des codewords de C);
La taille des blocs que l'on peut encoder est de 4 bits. Le nombre de bits de contrôle rajoutés au message est 4. La taille des codewords est 8.
- Son rendement ;
Son rendement est de \frac{4}{8} (50%).
- La distance de Hamming du code C ;
On sait que la distance = Min_{X ≠ 0} (Poids(X)).
On remarque que le poids minimal des codewords de la matrice G est de 3. Donc la distance de Hamming du code C est d = 3.
- Sa matrice de vérification de parité H
$$H = \begin{bmatrix}1 & 1 & 0 & 0 & 1 & 0 & 0 & 0\ 0 & 1 & 1 & 0 & 0 & 1 & 0 & 0\ 1 & 0 & 1 & 1 & 0 & 0 & 1 & 0\ 1 & 0 & 0 & 1 & 0 & 0 & 0 & 1 \end{bmatrix}$$
- Au vu de la distance de Hamming de C, quelles sont ses capacités de correction et de détection d’erreur(s) ?
Pour un Hamming code de distance d, on peut détecter d-1 erreurs et corriger \frac{d-1}{2} erreurs. Pour le code C on peut donc détecter 3 erreurs et en corriger une.
III - ...se cachent des polynômes générateurs équivalents.
- Montrez que le polynôme générateur associé à la matrice G est
x^4 + x + 1.
Si C est de forme [n,k] alors degré(x) = n-k.
- Regardez de plus près la matrice G. Voyez-vous un autre moyen d’en extraire le polynôme générateur associé ? Montrez les opérations nécessaires.
S'il l'on soustrait la ligne 4 à la première ligne, on obtiens une matrice de la forme :
$$G =\begin{bmatrix}1 & 0 & 0 & 1 & 1 & 0 & 0 & 0\
0 & 1 & 0 & 0 & 1 & 1 & 0 & 0\
0 & 0 & 1 & 0 & 0 & 1 & 1 & 0\
0 & 0 & 0 & 1 & 0 & 0 & 1 & 1
\end{bmatrix}$$
On remarque le même motif qui se répéte en décalant à droite d'un bit sur chaque ligne de la matrice. Ce motif est 10011. Il peut être traduit en polynôme générateur G(x) = x^4 + x + 1.
IV - Restaurez la gloire matricielle de P
- Prenez un mot aléatoire Ma et rajoutez y les bits de contrôle pour en faire un codeword ca. Calculez ca mod P pour chacune des 8 erreurs uniques pouvant se produire sur ca. Dressez une table (et écrivez la table dans votre rapport) référencant la valeur de ca mod P suivant la position de l’erreur.
| Message : 1010 | |
|---|---|
| Position | C mod P |
| 1 | 1 0 1 1 |
| 2 | 1 1 0 0 |
| 3 | 0 1 1 0 |
| 4 | 0 0 1 1 |
| 5 | 1 0 0 0 |
| 6 | 0 1 0 0 |
| 7 | 0 0 1 0 |
| 8 | 0 0 0 1 |
| Message : 1101 | |
|---|---|
| Position | C mod P |
| 1 | 1 0 1 1 |
| 2 | 1 1 0 0 |
| 3 | 0 1 1 0 |
| 4 | 0 0 1 1 |
| 5 | 1 0 0 0 |
| 6 | 0 1 0 0 |
| 7 | 0 0 1 0 |
| 8 | 0 0 0 1 |
| Message : 0111 | |
|---|---|
| Position | C mod P |
| 1 | 1 0 1 1 |
| 2 | 1 1 0 0 |
| 3 | 0 1 1 0 |
| 4 | 0 0 1 1 |
| 5 | 1 0 0 0 |
| 6 | 0 1 0 0 |
| 7 | 0 0 1 0 |
| 8 | 0 0 0 1 |
Répétez l’opération sur au moins deux autres mots Mb et Mc. Qu’observez-vous ?
On remarque que le résultat de C mod P est le même pour une postion i peu importe le message de base. Donc C mod P renvoit le syndrome et donc la position de l'erreur dans le codeword C.
- Soit le vecteur vi à 9 bits tel que seul le i eme bit est à 1. Pour tout
vi|i ∈{0,9}, calculez vi mod P. Que constatez-vous ? Que pouvez-vous en conclure ?
| Codeword | C mod P |
|---|---|
| 000000001 | 1 0 1 1 |
| 000000010 | 1 1 0 0 |
| 000000100 | 0 1 1 0 |
| 000001000 | 0 0 1 1 |
| 000010000 | 1 0 0 0 |
| 000100000 | 0 1 0 0 |
| 001000000 | 0 0 1 0 |
| 010000000 | 0 0 0 1 |
| 100000000 | 0 0 0 1 |
On constate qu'en rajoutant un 9ème bit au vecteur, le syndrome se retrouve décalé d'un bit à gauche par rapport au syndrome qu'on obtient avec un vecteur de 8 bits.
- À l’aide de vos observations, implémentez un mécanisme efficace permettant de corriger des erreurs uniques. Justifier vos choix d’implémentation et tester votre implémentation.