Exercice 1 — XOR, le shérif des transmissions

Sujet

Dans cet exercice, un message est une suite de 0 et de 1 , appelés bits.
Entre deux bits, on définit l'opération XOR (notée ⊕ ) de la manière suivante :

\[ 0 \oplus 1=1 ; 0 \oplus 0=0 ; 1 \oplus 1=0 ; 1 \oplus 0=1 \]

On étend naturellement cette opération à deux messages formés du même nombre de bits. Par exemple :
\(\oplus \quad \begin{array}{lll}1 & 1 & 0 \\ 1 & 0 & 0\end{array} \quad\) ou encore \(10010001 \oplus 11001001=01011000\).
On admet que lorsqu'on effectue plusieurs XOR de suite, l'ordre de calcul ne change

\[ =\quad 0 \quad 1 \quad 0 \]

pas le résultat.

Les deux parties sont indépendantes.

Partie 1 : Cryptage d'un message

Pour crypter un message formé de 8 bits, on utilise une autre suite de 8 bits appelée clef.
Pour obtenir le message crypté, on effectue l'opération XOR entre le message initial et la clef.

1. Crypter le message 11110000 à l'aide de la clef 10101010.
2. Crypter le message obtenu à la question précédente à l'aide de la même clef.
3. Le message 00001111 est un message crypté à l'aide de la clef précédente, retrouver le message initial.
4. Décrire la méthode générale permettant de retrouver un message initial à partir du message crypté et de la clef. Justifier.

Partie 2 : Correction d'erreur lors d'une transmission

Une erreur de transmission est le changement d'un 0 en 1 (ou inversement) lors de l'envoi d'un message composé de bits. Il peut y avoir plusieurs erreurs de transmission dans le message reçu.
Afin de détecter et corriger d'éventuelles erreurs lors de la transmission de 4 bits (notés \(b_{1}, b_{2}, b_{3}, b_{4}\) ) on calcule 4 bits de contrôle (notés \(c_{1}, c_{2}, c_{3}, c_{4}\) ). Les bits de contrôle sont obtenus de la façon suivante:

\[ c_{1}=b_{2} \oplus b_{3} \oplus b_{4}, c_{2}=b_{1} \oplus b_{3} \oplus b_{4}, c_{3}=b_{1} \oplus b_{2} \oplus b_{4} \text { et } c_{4}=b_{1} \oplus b_{2} \oplus b_{3} \oplus b_{4} \oplus c_{1} \oplus c_{2} \oplus c_{3} . \]

On envoie alors les 8 bits suivants : \(b_{1} b_{2} b_{3} b_{4} c_{1} c_{2} c_{3} c_{4}\).

1. Quel message de 8 bits doit-on envoyer pour transmettre 1011 ?
2. On admet que, durant la transmission du message, au plus un des 8 bits a été transmis de façon erronée. À partir des bits reçus, on recalcule les 4 bits de contrôle que l'on compare aux 4 bits de contrôle reçus (attention pour le recalcul de \(c_{4}\), on utilise les 7 premiers bits reçus). Recopiez et complétez le tableau suivant dans lequel I signifie que le bit de contrôle recalculé est identique au bit de contrôle reçu (et D qu'il est différent).

Bit Bit erroné	aucun	\(b_{1}\)	\(b_{2}\)	\(b_{3}\)	\(b_{4}\)	\(c_{1}\)	\(c_{2}\)	\(c_{3}\)	\(c_{4}\)
\(c_{1}\)		I
\(c_{2}\)		D
\(c_{3}\)		D
\(c_{4}\)		D

1. Toujours dans le cas où il y a une seule erreur au plus, justifier qu'on peut toujours la corriger.
2. On reçoit le message 10111100. En admettant qu'il comporte au plus une erreur, retrouver le message envoyé.
3. On reçoit le message 01110010 . Est-il correct? La méthode précédente s'applique-t-elle?
4. Montrer que s'il y a au plus deux erreurs, on peut toujours déterminer le nombre exact d'erreurs.