Baccalauréat S Asie 22 juin 2017 - Correction Spécialité

Page 12 sur 12: Correction Spécialité

Correction de l'exercice de Spécialité 5 points

Candidats AYANT SUIVI l'enseignement de spécialité mathématiques

Les deux parties sont indépendantes
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 :

• $p_n$ la probabilité que le bit reçu ait pour valeur $1$ ;
• $q_n$ la probabilité que le bit reçu ait pour valeur $0$.

On a donc $p_0 = 1$ et $q_0 = 0$. On définit les matrices suivantes : \[A = \begin{pmatrix}p& 1- p\\1 - p&p\end{pmatrix}\quad X_n = \begin{pmatrix}p_n\\q_n\end{pmatrix} \quad P = \begin{pmatrix}1&1\\1&- 1\end{pmatrix}.\] On admet que, pour tout entier $n$, on a : $X_{n+1} = AX_n$ et donc, $X_n = A^n X_0$.

1. 1. Montrer que $P$ est inversible et déterminer $P^{-1}$.
   On considère la matrice $P=\begin{pmatrix}1&1\\1&-1\end{pmatrix}$
   Son déterminant est : $1\times (-1)-1\times 1=-1-1=-2\neq 0$
   La matrice $P$ est donc inversible.
   L’inverse de la matrice $P$ est alors :
   $$P^{-1}=\begin{pmatrix}0,5&0,5\\0,5&-0,5\end{pmatrix}$$
   
   2. On pose : $D = \begin{pmatrix} 1&0\\0 & 2p - 1\end{pmatrix}$. Vérifier que : $A = PDP^{-1}$.
   On a $DP^{-1}=\begin{pmatrix}0,5&0,5\\p-0,5&0,5-p\end{pmatrix}$
   Donc $PDP^{-1}=\begin{pmatrix}0,5+p-0,5&0,5+0,5-p\\0,5+0,5-p&0,5-0,5+p\end{pmatrix}$ $=\begin{pmatrix}p&1-p\\1-p&p\end{pmatrix}$ $=A$
   $\quad$
   
   3. Montrer que, pour tout entier $n \geqslant 1$, \[A^n = PD^n P^{-1}.\]
   Initialisation : Si $n=1$
   D’après la question précédente, la propriété est vraie au rang $1$.
   $\quad$
   Hérédité : Supposons la propriété vraie au rang $n$ : $A^n=PD^nP^{-1}$.
   $\begin{align*} A^{n+1}&=AA^n\\
   &=PDP^{-1}PD^nP^{-1}\\
   &=PDD^nP^{-1}\\
   &=PD^{n+1}P^{-1}
   \end{align*}$
   La propriété est donc vraie au rang $n+1$.
   $\quad$
   Conclusion : La propriété est vraie au rang $1$ et est héréditaire.
   Par conséquent, pour tout entier naturel $n\geq 1$ on a $A^n=PDP^{-1}$.
   $\quad$
   
   4. En vous appuyant sur la copie d'écran d'un logiciel de calcul formel donnée ci-dessous, déterminer l'expression de $q_n$ en fonction de $n$.
   D’après le logiciel de calcul formel on a :
   $A_n=\begin{pmatrix}p_n\\q_n\end{pmatrix}=\begin{pmatrix}\dfrac{(2p-1)^n+1}{2}\\\dfrac{-(2p-1)^n+1}{2}\end{pmatrix}$
   Donc $q_n=\dfrac{1-(2p-1)^n}{2}$
   $\quad$
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 ?
On a $q_n=\dfrac{1-0,96^n}{2}$
On veut donc trouver la plus grande valeur de l’entier naturel $n$ tel que :
$\begin{align*} \dfrac{1-0,96^n}{2} \leq 0,25 &\iff 1-0,96^n\leq 0,5 \\
&-0,96^n \leq -0,5\\
&0,96^n\geq 0,5 \\
&n\ln(0,96) \geq \ln(0,5)\\
&n\leq \dfrac{\ln(0,5)}{\ln(0,96)}
\end{align*}$
Ainsi $n \leq 16$
On peut donc aligner au maximum $16$ lignes de transmission.
$\quad$

Partie B : étude d'un code correcteur, 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 4 bits que l'on note $b_1$, $b_2$, $b_3$ et $b_4$. Par exemple, pour le mot « 1101 », on a $b_1 = 1$, $b_2 = 1$, $b_3 = 0$ et $b_4 = 1$. On ajoute à cette liste une clé de contrôle $c_1c_2c_3$ formée de trois bits :

• $c_1$ est le reste de la division euclidienne de $b_2 + b_3 + b_4$ par 2 ;
• $c_2$ est le reste de la division euclidienne de $b_1 + b_3 + b_4$ par 2 ;
• $c_3$ est le reste de la di vision euclidienne de $b_1 + b_2 + b_4$ par 2.

On appelle alors « message » la suite de 7 bits formée des 4 bits du mot et des 3 bits de contrôle.

1. Préliminaires
   1. Justifier que $c_1$, $c_2$ et $c_3$ ne peuvent prendre comme valeurs que 0 ou 1.
   $c_1$, $c_2$ et $c_3$ sont des restes de division euclidienne par $2$. Leurs valeurs ne peuvent donc être que $0$ ou $1$.
   2. Calculer la clé de contrôle associée au mot 1001.
   $b_2+b_3+b_4=1$. Or $1\equiv 1~~[2]$ donc $c_1=1$
   $b_1+b_3+b_4=2$. Or $2\equiv 0~~[2]$ donc $c_2=0$
   $b_1+b_2+b_4=2$ donc $c_3=0$
   Ainsi la clé de contrôle associée au mot $1001$ est $100$.
2. Soit $b_1b_2b_3b_4$ un mot de 4 bits et $c_1c_2c_3$ la clé associée. Démontrer que si on change la valeur de $b_1$ et que l'on recalcule la clé, alors :
   • la valeur de $c_1$ est inchangée ;
   • la valeur de $c_2$ est modifiée ;
   • la valeur de $c_3$ est modifiée.
3. On suppose que, durant la transmission du message, au plus un des 7 bits a été transmis de façon erronée. À partir des quatre premiers bits du message reçu, on recalcule les 3 bits de contrôle, et on les compare avec les bits de contrôle reçus. Sans justification, recopier et 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.
   
4. Justifier rapidement, en vous appuyant sur le tableau, que si un seul bit reçu est erroné, on peut dans tous les cas déterminer lequel, et corriger l'erreur.
$\bullet$ $c_1$ ne dépend pas de $b_1$ donc la valeur de $c_1$ est inchangée.
$\bullet$ Si $b_1=0$ alors $b_1$ prend la valeur $1$
$\quad$ Si $c_2=0$ alors $c_2$ prend la valeur $0+1$ modulo $2$ soit $1$
$\quad$ Si $c_2=1$ alors $c_2$ prend la valeur $1+1$ modulo $2$ soit $0$
$\bullet$ Si $b_1=1$ alors $b_1$ prend la valeur $0$
$\quad$ Si $c_2=0$ alors $c_2$ prend la valeur $0-1$ modulo $2$ soit $1$
$\quad$ Si $c_2=1$ alors $c_2$ prend la valeur $1-1$ modulo $2$ soit $0$
Dans tous les cas $c_2$ a été modifié.
$\bullet$ Si $b_1=0$ alors $b_1$ prend la valeur $1$
$\quad$ Si $c_3=0$ alors $c_3$ prend la valeur $0+1$ modulo $2$ soit $1$
$\quad$ Si $c_3=1$ alors $c_3$ prend la valeur $1+1$ modulo $2$ soit $0$
$ \bullet$ Si $b_1=1$ alors $b_1$ prend la valeur $0$
$\quad$ Si $c_3=0$ alors $c_3$ prend la valeur $0-1$ modulo $2$ soit $1$
$\quad$ Si $c_3=1$ alors $c_3$ prend la valeur $1-1$ modulo $2$ soit $0$
Dans tous les cas $c_3$ a été modifié.
$\quad$ $\quad$
$\begin{array}{|c|c|c|c|c|c|c|c|c|}
\hline
&b_1&b_2&b_3&b_4&c_1&c_2&c_3&\text{Aucun}\\
\hline
c_1&J&F&F&F&F&J&J&J\\
\hline
c_2&F&J&F&F&J&F&J&J\\
\hline
c_3&F&F&J&F&J&J&F&J\\
\hline
\end{array}$
$\quad$
5. Voici deux messages de 7 bits : \[A = 0100010 \quad \text{et} \quad B = 1101001.\] On admet que chacun d'eux comporte au plus une erreur de transmission. Dire s'ils comportent une erreur, et la corriger le cas échéant.
Si aucun bit n’est modifié alors :
$c_1+b_2+b_3+b_4\equiv 0~~[2] \quad (1)$
$c_2+b_1+b_3+b_4\equiv 0~~[2] \quad (2)$
$c_3+b_1+b_2+b_4\equiv 0~~[2] \quad (3)$
En revanche si un bit reçu est erroné alors
L’une des sommes précédentes est égale à $1$ modulo $2$.
On est donc en mesure de signaler une erreur.
Si les sommes $(2)$ et $(3)$ sont égales à $(1)$ modulo $2$ alors l’erreur est sur $b_1$.
On peut faire les mêmes raisonnements pour $b_2$ et $b_3$.
Si les trois sommes sont égales à $1$ modulo $2$ alors l’erreur est sur $b_4$.
Si seule la somme $(1)$ est égale à $1$ modulo $2$ alors l’erreur est sur $c_1$.
On peut faire un raisonnement similaire pour $c_2$ et $c_3$.
Dans tous les cas on peut diagnostiquer l’erreur et la corriger.
$\quad$ $A=0100010$
Alors $c_1+b_2+b_3+b_4\equiv 1~~[2]$
$c_2+b_1+b_3+b_4\equiv 1~~[2]$
$c_3+b_1+b_2+b_4\equiv 1~~[2]$
L’erreur porte donc sur $b_4$ et le message corrigé est $0101010$
$\quad$
$B=1101001$
Alors $c_1+b_2+b_3+b_4\equiv 0~~[2]$
$c_2+b_1+b_3+b_4\equiv 0~~[2]$
$c_3+b_1+b_2+b_4\equiv 0~~[2]$
Le message ne comporte pas d’erreur de transmission.