Exercice national 3 — Codes détecteurs et correcteurs (séries technologiques)

2c-2d. Avec 4 bits, \(M\) varie entre 0 et \(1+2+4+8=15\) : tous les entiers de cet intervalle sont représentables (écriture en base 2 sur 4 bits), mais aucun au-delà.

3b-c. Le bit de parité vérifie que la somme des \(x_i\) plus \(y\) est toujours paire. Une seule erreur sur les bits d'information change la parité de cette somme (détectable), mais ne dit pas lequel des 4 bits est fautif (non localisable). Deux erreurs simultanées se compensent en parité (non détectables avec ce seul bit).

4b-c. Chaque bit de contrôle porte sur un sous-ensemble différent des 4 bits d'information (3 parmi 4, chacun exclu une fois) : la combinaison des trois vérifications (correctes/incorrectes) forme une signature qui permet, en cas d'erreur unique, d'identifier précisément quel bit d'information est fautif (comparer les 4 bits d'information à leur appartenance ou non à chacun des 3 groupes testés par \(y_1,y_2,y_3\)).

Correction détaillée

0. Montrer que \(a+b\) est pair ssi \(a,b\) ont la même parité.

Soient \(a,b \in \mathbb{Z}\). On distingue deux cas :

• Si \(a\) et \(b\) ont la même parité, alors soit \(a\) et \(b\) sont tous deux pairs, soit tous deux impairs.

* Si \(a\) et \(b\) sont pairs : \(a = 2k\), \(b = 2\ell\) avec \(k,\ell \in \mathbb{Z}\). Alors \(a+b = 2(k+\ell)\) est pair.

* Si \(a\) et \(b\) sont impairs : \(a = 2k+1\), \(b = 2\ell+1\) avec \(k,\ell \in \mathbb{Z}\). Alors \(a+b = 2(k+\ell+1)\) est pair.

• Réciproquement, si \(a+b\) est pair, alors \(a+b \equiv 0 \pmod{2}\). Or \(a+b \equiv a+b \pmod{2}\) et \(a \equiv a \pmod{2}\), \(b \equiv b \pmod{2}\). On a \(a+b \equiv 0 \pmod{2}\) donc \(a \equiv -b \pmod{2}\). Comme \(-b \equiv b \pmod{2}\) (car \(2 \mid 2b\)), on obtient \(a \equiv b \pmod{2}\), donc \(a\) et \(b\) ont la même parité.

Ainsi, \(a+b\) est pair si et seulement si \(a\) et \(b\) ont la même parité.

2a. Message codé par \((1,0,0,1)\) ?

Le message \(M\) est donné par \(M = x_1 + 2x_2 + 4x_3 + 8x_4\).

Pour \((x_1,x_2,x_3,x_4) = (1,0,0,1)\), on a :

\[M = 1 \times 1 + 2 \times 0 + 4 \times 0 + 8 \times 1 = 1 + 0 + 0 + 8 = 9.\]

Le message codé est \(M = 9\).

2b. Coder \(M=10\), puis \(M=15\).

On cherche le quadruplet de bits \((x_1,x_2,x_3,x_4)\) tel que \(M = x_1 + 2x_2 + 4x_3 + 8x_4\).

C'est la décomposition en base 2 de \(M\) (écriture binaire).

• Pour \(M=10\) :

\(10 \div 2 = 5\) reste \(0\) → \(x_1 = 0\)

\(5 \div 2 = 2\) reste \(1\) → \(x_2 = 1\)

\(2 \div 2 = 1\) reste \(0\) → \(x_3 = 0\)

\(1 \div 2 = 0\) reste \(1\) → \(x_4 = 1\)

Vérification : \(0 + 2\times1 + 4\times0 + 8\times1 = 0+2+0+8 = 10\).

Donc \((x_1,x_2,x_3,x_4) = (0,1,0,1)\).

• Pour \(M=15\) :

\(15 \div 2 = 7\) reste \(1\) → \(x_1 = 1\)

\(7 \div 2 = 3\) reste \(1\) → \(x_2 = 1\)

\(3 \div 2 = 1\) reste \(1\) → \(x_3 = 1\)

\(1 \div 2 = 0\) reste \(1\) → \(x_4 = 1\)

Vérification : \(1 + 2\times1 + 4\times1 + 8\times1 = 1+2+4+8 = 15\).

Donc \((x_1,x_2,x_3,x_4) = (1,1,1,1)\).

2c. Peut-on coder \(M=20\) ?

Le plus grand message possible avec 4 bits est obtenu pour \((1,1,1,1)\) donnant \(M=15\).

En effet, \(M = x_1 + 2x_2 + 4x_3 + 8x_4\) avec \(x_i \in \{0,1\}\), donc \(M\) est compris entre \(0\) et \(1+2+4+8 = 15\).

\(20 > 15\), donc on ne peut pas coder \(M=20\) avec 4 bits.

2d. Quels messages sont possibles ?

Tous les entiers naturels de 0 à 15 inclus sont possibles, car tout entier entre 0 et 15 s'écrit de manière unique en binaire sur 4 bits.

Donc les messages possibles sont \(M \in \{0,1,2,\dots,15\}\).

3. Bit de parité.

On ajoute un 5e bit \(y\) défini par :

\[y =

\begin{cases}

0 & \text{si } x_1+x_2+x_3+x_4 \text{ est pair}, \\

1 & \text{sinon}.

\end{cases}\]

a) Bit \(y\) pour \((1,0,0,1)\) (\(M=9\)) ?

On a \((x_1,x_2,x_3,x_4) = (1,0,0,1)\).

Somme : \(1+0+0+1 = 2\), qui est pair. Donc \(y = 0\).

b) Le quintuplet reçu \((1,1,0,1,0)\) (parité fiable) est-il corrompu ?

Le quintuplet reçu est \((x_1,x_2,x_3,x_4,y) = (1,1,0,1,0)\).

On calcule la somme des bits d'information : \(x_1+x_2+x_3+x_4 = 1+1+0+1 = 3\), qui est impair.

Le bit de parité reçu est \(y=0\), ce qui indiquerait une somme paire. Or la somme est impaire, donc il y a une incohérence.

Le message est corrompu (au moins une erreur).

c) Peut-on détecter et localiser une erreur sur un seul bit d'information ? Sur deux bits ?

• Erreur sur un seul bit d'information :

Si un seul bit d'information est erroné, la parité de la somme change (passe de pair à impair ou inversement). Le bit de parité \(y\) reçu ne correspondra pas à la somme calculée, donc on détecte l'erreur.

Cependant, on ne peut pas localiser quel bit est erroné, car on ne sait pas lequel a changé. On sait seulement qu'il y a une erreur.

Donc : détection possible, localisation impossible.

• Erreur sur deux bits d'information :

Si deux bits sont erronés, la somme des bits d'information change de 2 (modulo 2, cela ne change pas la parité). En effet, ajouter 2 à un nombre ne change pas sa parité. Donc la parité reste la même, et le bit de parité reçu sera cohérent avec la somme calculée. L'erreur n'est pas détectée.

Donc : ni détection ni localisation.

4. Bits de contrôle.

On ajoute trois bits de contrôle \(y_1, y_2, y_3\) définis par :

• \(y_1\) = parité de \(x_1+x_2+x_3\) (0 si pair, 1 si impair)

• \(y_2\) = parité de \(x_2+x_3+x_4\)

• \(y_3\) = parité de \(x_1+x_3+x_4\)

a) \(y_1,y_2,y_3\) pour \((1,0,0,1)\) ?

On a \((x_1,x_2,x_3,x_4) = (1,0,0,1)\).

• \(x_1+x_2+x_3 = 1+0+0 = 1\) (impair) → \(y_1 = 1\)

• \(x_2+x_3+x_4 = 0+0+1 = 1\) (impair) → \(y_2 = 1\)

• \(x_1+x_3+x_4 = 1+0+1 = 2\) (pair) → \(y_3 = 0\)

Donc \((y_1,y_2,y_3) = (1,1,0)\).

b) Pourquoi l'heptuplet reçu \((1,1,0,1,0,0,1)\) est-il forcément corrompu (bits de contrôle fiables) ?

L'heptuplet reçu est \((x_1,x_2,x_3,x_4,y_1,y_2,y_3) = (1,1,0,1,0,0,1)\).

On calcule les parités attendues à partir des bits d'information reçus :

• \(x_1+x_2+x_3 = 1+1+0 = 2\) (pair) → \(y_1\) attendu = 0. Reçu : 0 → OK.

• \(x_2+x_3+x_4 = 1+0+1 = 2\) (pair) → \(y_2\) attendu = 0. Reçu : 0 → OK.

• \(x_1+x_3+x_4 = 1+0+1 = 2\) (pair) → \(y_3\) attendu = 0. Reçu : 1 → ERREUR.

Le bit \(y_3\) reçu est 1 alors qu'il devrait être 0. Comme les bits de contrôle sont fiables (non corrompus), cela signifie que les bits d'information sont erronés. Donc l'heptuplet est corrompu.

c) Si exactement un bit d'information est erroné, peut-on détecter et localiser (donc corriger) l'erreur ? Et si deux bits le sont ?

On suppose que les bits de contrôle \(y_1,y_2,y_3\) sont fiables (non erronés). On note \(e_i\) l'erreur sur le bit \(x_i\) (0 si correct, 1 si erroné). On a un seul bit erroné parmi les \(x_i\).

Pour chaque bit d'information, on regarde quels \(y_j\) sont affectés :

• Si \(x_1\) est erroné : \(y_1\) (dépend de \(x_1\)) et \(y_3\) (dépend de \(x_1\)) seront faux, mais \(y_2\) reste correct.

• Si \(x_2\) est erroné : \(y_1\) et \(y_2\) seront faux, \(y_3\) correct.

• Si \(x_3\) est erroné : \(y_1\), \(y_2\), \(y_3\) seront tous faux (car \(x_3\) apparaît dans les trois).

• Si \(x_4\) est erroné : \(y_2\) et \(y_3\) seront faux, \(y_1\) correct.

Ainsi, en comparant les bits de contrôle reçus avec ceux calculés à partir des bits d'information reçus, on obtient un triplet de syndromes \((s_1,s_2,s_3)\) où \(s_j = 1\) si \(y_j\) reçu ≠ \(y_j\) calculé. Ce triplet est unique pour chaque bit erroné :

• Erreur sur \(x_1\) : \((1,0,1)\)

• Erreur sur \(x_2\) : \((1,1,0)\)

• Erreur sur \(x_3\) : \((1,1,1)\)

• Erreur sur \(x_4\) : \((0,1,1)\)

Donc on peut détecter et localiser l'erreur sur un seul bit d'information, et donc la corriger.

Si deux bits sont erronés :

Le syndrome d'une double erreur est la somme (mod 2, XOR) des deux syndromes individuels. En énumérant les 6 doubles erreurs possibles : \(\{x_1,x_2\}\to(0,1,1)\), \(\{x_1,x_4\}\to(1,1,0)\), \(\{x_2,x_4\}\to(1,0,1)\) — ces trois-là reproduisent exactement le syndrome d'une erreur simple sur un autre bit (\(x_4\), \(x_2\), \(x_1\) respectivement) : la correction se ferait alors à tort sur le mauvais bit, sans qu'on puisse s'en apercevoir. Les trois autres doubles erreurs, \(\{x_1,x_3\}\to(0,1,0)\), \(\{x_2,x_3\}\to(0,0,1)\), \(\{x_3,x_4\}\to(1,0,0)\), donnent des syndromes non nuls qui ne correspondent à aucune erreur simple répertoriée : on détecte bien qu'il y a un problème (le syndrome n'est pas nul), mais on ne peut pas localiser ni corriger, faute de bit candidat correspondant.

En conclusion : avec deux bits erronés, la détection n'est jamais garantie de façon fiable — dans la moitié des cas la correction se ferait silencieusement sur le mauvais bit, et dans l'autre moitié l'erreur est détectée mais non localisable.