• 0\ 1\ 1\ 0\ 0\ 1\ 0\ 0 \ra 0\ 1\ 1\ 0\ 0\ 1\ 0\ 0\ \textbf{1} (quantité paire de 1)
    • 0\ 1\ 1\ 1\ 0\ 1\ 0\ 0\ 0\ 1\ 1\ 1\ 1\ 0\ 1\ 0 \ra 0\ 1\ 1\ 1\ 0\ 1\ 0\ 0\ \textbf{0}\ 0\ 1\ 1\ 1\ 1\ 0\ 1\ 0\ \textbf{1} (on intercale 1 bit tous les 8 bits)

  3. On reçoit w, avec |w|\_{1} = nombre de bits à 1 du mot
    \begin{aligned}|w|=g\quad |w|_{1} \text{ pair } &\RA \text{ valide} \\\\ \text{ impair } &\RA \text{ invalide} \end{aligned}

  4. On ne peut pas détecter les erreurs si les bits à 1 sont modifiés. Il peut détecter ~50% des erreurs, car il détecte toutes les erreurs en nombre impaires. Sinon, il ne peut détecter qu’une erreur.

  6. q2.1
    Parité dernière ligne = Parité dernière colonne = Parité des 80 autres bits

  7. Il vaut 0, en faisant la preuve par récurrence en partant de la matrice \begin{pmatrix} 0 \end{pmatrix}.

  8. Erreur en (i, j) :

    • Parité des lignes i juste
    • Parité des colonnes j fausse
    • Parité des colonnes i juste
    • Parité des colonnes j fausse
    • Donc si une ligne erronée
    • Donc si une colonne erronée
    • \RA dois inverser (i, j)

  9. 2 erreurs sur une même ligne \ra on corrige pas
    Quand 2 erreurs sont non-alignées : 2 façons de corriger \ra on ne corrige pas

  10. x

  11. 4 erreurs en carrés, ce n’est pas détectés
    q2.6
    3 erreurs sur :

    • 3 lignes = les 3 détectés
    • 2 lignes = 1 détectés
    • 1 ligne = 1 détectés

  12. Rendement : \frac{64}{81} \approx 80\%
    On peut étendre à une matrix n\times n \ra (n+1)(n+1)
    -> on peut toujours détecter 3 erreurs et en corriger 1
    -> \begin{aligned} \lim_{n\to\infty} \frac{n\times n}{(n+1)(n+1)} &= 1 - O(\frac{1}{n}) \\\\ \hline \\\\ \frac{n^{2}}{n^{2}+2n+1} &= 1-\frac{2n+1}{n^{2}+2n+1} \end{aligned}
    n grossi équivaut à un meilleur rendement
    Mais si taux d’erreur par bit constant, en \frac{1}{k}, la probabilité d’erreur tend vers 1, c’est-à-dire, on est quasiment sûr d’avoir une erreur
    Intéressant si k \approx n^{2}, car on a une expérence d’erreur (qui sera corrigée)

  14. q3.1

    • Redondance : r =3 (le nombre de bits ajoutés)
    • Rendement : \frac{4}{7} \approx 57.14\% (\in [0, 1])

  16. Pour décoder, on enlève les bits en position 1, 2 et 4. On a une erreur si :

    • (p_{1} a_{1} a_{2} a_{3})_{1} \neq 0 ou

    • (p_{2} a_{1} a_{3} a_{4})_{1} \neq 0 ou

    • (p_{3} a_{2} a_{3} a_{4})_{1} \neq 0, on peut faire genre c’est une matrix :

    • Si \begin{pmatrix}0 \\\\ 0 \\\\ 0\end{pmatrix} : c’est ok

    • Si \begin{pmatrix}1 \\\\ 0 \\\\ 0\end{pmatrix}, alors erreur sur p_{1}

    • Si \begin{pmatrix}0 \\\\ 1 \\\\ 0\end{pmatrix}, alors erreur sur p_{2}

    • Si \begin{pmatrix}0 \\\\ 0 \\\\ 1\end{pmatrix}, alors erreur sur p_{3}

    • Si \begin{pmatrix}1 \\\\ 1 \\\\ 0\end{pmatrix}, alors erreur sur a_{1}

    • Si \begin{pmatrix}1 \\\\ 0 \\\\ 1\end{pmatrix}, alors erreur sur a_{2}

    • Si \begin{pmatrix}0 \\\\ 1 \\\\ 1\end{pmatrix}, alors erreur sur a_{3}

    • Si \begin{pmatrix}1 \\\\ 1 \\\\ 1\end{pmatrix}, alors erreur sur a_{4}
      Le bit p_{1} contrôle 1 bit sur 2.
      Le bit p_{2} contrôle 2 bit sur 4.
      Le bit p_{3} contrôle 4 bit sur 8.
      Le bit i est contrôlé par le p_{j} qui sont à 1 dans l’écriture binaire de i
      hamming

  17. Pour 1010110, p_{1} est erronée, mais pas le reste, alors il n’y a pas d’erreur dans le message, donc : 1110

  18. Exemple :

    • Avant : 0000000
    • Après : 1110000
    • Hamming détecte 2 erreurs et en corrige 1

    • 2 erreurs detectés : 1 bit de donnée vérifié par \geqslant 2 bits de contrôle

    • \ra \geqslant 3 erreurs pour être non détecté.

    • 2 bits de contrôle erronés \ra détectés des 2 bits erronés (mais la correction est fausse)

    • Hamming est un code parfait : tout mot du dictionnaire (erroné) a une seule façon d’être corrigé. Tout mot a m=2^{k}-1 bits est soit valide soit flipper un bit le rend valide

  21. q4.1

  22. Cf. Le dessin au-dessus.

  23. Pareil

  24. L’erreur sera détectée.

  25. Si on a 0001 et 0000 et 0000 et 0001 donc pareil au bit de parité (en gros, c’est a chié, mais on ne peut pas changer parce qu’on peut pas changer IPv4)

  26. Hamming ?