18
Chapitres • 3. Divisibilité dans Z • 6. Calcul matriciel
D'après bac S, Asie, 2017
Exemple simple de code correcteur
Un bit est un symbole informatique élémentaire valant soit
0, soit
1.
Partie A : Ligne de transmission
Une ligne de transmission transporte des bits de données selon le modèle suivant :
- elle transmet le bit de façon correcte avec une probabilité p ;
- elle transmet le bit de façon erronée (en changeant le 1 en 0 ou le 0 en 1) avec une probabilité 1−p.
On assemble bout à bout plusieurs lignes de ce type et on suppose qu'elles introduisent des erreurs de façon indépendante les unes des autres.
On étudie la transmission d'un seul bit, ayant pour valeur
1 au début de la transmission.
Après avoir traversé
n lignes de transmission, on note :
- pn la probabilité que le bit reçu ait pour valeur 1 ;
- qn la probabilité que le bit reçu ait pour valeur 0.
On a donc
p0=1 et
q0=0. On définit les matrices suivantes :
A=(p1−p1−pp),
Xn=(pnqn) et
P=(111−1).
On admet que, pour tout entier
n, on a
Xn+1=AXn et donc
Xn=AnX0.
1. a. Montrer que P est inversible et déterminer P−1.
b. On pose D=(1002p−1). Vérifier que A=PDP−1.
c. Montrer que, pour tout entier n⩾1, An=PDnP−1.
d. En vous appuyant sur la copie d'écran d'un logiciel de calcul formel donnée ci‑dessous, déterminer une expression de
qn en fonction de
n.
2. On suppose dans cette question que
p vaut
0,98. On rappelle que le bit avant transmission a pour valeur
1.
On souhaite que la probabilité que le bit reçu ait pour valeur
0 soit inférieure ou égale à
0,25.
Combien peut‑on, au maximum, aligner de telles lignes
de transmission ?
Partie B : Le code de Hamming (7,4)
On rappelle qu'un bit est un symbole informatique élémentaire valant soit
0, soit
1. On considère un « mot » formé de quatre bits que l'on note
b1,
b2,
b3 et
b4.
Par exemple, pour le mot
1101, on a
b1=1,
b2=1,
b3=0 et
b4=1.
On ajoute à cette liste une clé de contrôle
c1c2c3 formée de trois bits :
- c1 est le reste de la division euclidienne de b2+b3+b4 par 2 ;
- c2 est le reste de la division euclidienne de b1+b3+b4 par 2 ;
- c3 est le reste de la division euclidienne de b1+b2+b4 par 2.
On appelle alors « message » la suite de sept bits formée des quatres bits du mot et des trois bits de contrôle.
1. Préliminaires
a. Justifier que c1, c2 et c3 ne peuvent prendre comme valeurs que 0 ou 1.
b. Calculer la clé de contrôle associée au mot 1001.
2. Soit b1b2b3b4 un mot de quatre bits et c1c2c3 la clé associée.
Démontrer que si on change la valeur de b1 et que l'on recalcule la clé, alors c1 est inchangée, c2 est modifiée et c3 est modifiée.
3. On suppose que, durant la transmission du message, au plus, un des sept bits a été transmis de façon erronée. À partir des quatre premiers bits du message reçu, on recalcule les trois bits de contrôle, et on les compare avec les bits de contrôle reçus.
Sans justification, compléter le tableau ci‑dessous. La lettre F signifie que le bit de contrôle reçu ne correspond pas au bit de contrôle calculé et J que ces deux bits sont égaux.
| Bit erroné ⇢ | b1 | b2 | b3 | b4 | c1 | c2 | c3 | Aucun |
| Bit de contrôle calculé ⇣ |
| c1 | J |
|
|
|
|
|
|
|
| c2 | F |
|
|
|
|
|
|
|
| c3 | F |
|
|
|
|
|
|
|
4. Justifier rapidement, à l'aide du tableau, que si un seul bit reçu est erroné, on peut dans tous les cas déterminer lequel et corriger l'erreur.
5. Voici deux messages de sept bits : A=0100010 et B=1101001. On admet que chacun d'eux comporte au plus une erreur de transmission.
Préciser s'il y a une erreur et la corriger.