La PCE.

La méthode précédente permet de savoir avec certitude qu'une transmission s'est mal passée si la parité n'est pas respectée, mais elle ne permet pas de corriger une erreur. La méthode décrite dans cette section permet de corriger une erreur (en faisant l'hypothèse que la transmission a engendré au plus 2 erreurs).

Cette fois-ci on regroupe l'information à transmettre par paquets de 15 octets (de parité paire) et on ajoute un 16ème octet (dont on ajuste aussi la parité). On va maintenant expliquer comment on calcule ce 16ème octet en fonction des 15 précédents.

Soit $Q(X)=X^7+X^3+1$. Étant donnés 15 octets $o_1$, ..., $o_{15}$ de parité paire, on calcule le polynôme:

$$C(X)= \sum _{j=1}^{15} P_{o_j}(X) X^{8j-1}$$

(le terme de plus bas degré est donc de degré au moins 7: $X^7$ obtenu pour $j=1$).
On calcule ensuite le reste de la division euclidienne de $C(X)$ par $Q(X)$ ce qui donne un polynôme $R$ de degré 6, l'octet $o_{16}$ est alors l'octet correspondant à $R$ (plus précisément tel que $P_{o_{16}}$ coinncide avec $R$ sauf pour le terme de degré 7).

A l'autre extrémité, le récepteur reçoit 16 octets $\tilde{o}_1, ... \tilde{o}_{16}$ et forme le polynôme

$$\tilde{C}(X)= \sum _{j=1}^{15} P_{\tilde{o}_j}(X) X^{8j-1} + a_6 X^6+...+a_1 X +a_0,$$   où $$\tilde{o}_{16}=(a_7, a_6, ..., a_0)$$

Si la transmission s'est bien passée, $\tilde{o}_j=o_j$ donc $\tilde{C}=C+R$ est divisible par $Q$ (car $R=-R$ dans ${\mathbb{Z}}/2{\mathbb{Z}}$). Réciproquement, si tous les octets $\tilde{o}_j$ sont de parité paire et si $\tilde{C}$ est divisible par $Q$ alors soit la transmission s'est bien passée soit le nombre d'erreurs est supérieur ou égal à 2.

S'il y a une erreur de transmission et une seule, alors il exixste un entier $i \leq 126$ tel que:

$$\tilde{C}(X)= C(X)+R(X)+X^i$$

que détermine à l'aide du reste de la division euclidienne de $\tilde{C}$ par $R$ et de la parité des $\tilde{o}_j$.

Programmez un algorithme mettant en oeuvre cette procédure et testez la en créant des erreurs de manière aléatoire.