Exercice 1 - Binaire et détection d'erreurs · Bac Numérique et Sciences Informatiques Amérique du Nord 2025 (jour 2)

Exercice 1 (6 points)

Cet exercice porte sur les tableaux, les dictionnaires, les arbres binaires, la programmation en Python et la récursivité.

Lors de la transmission de données, des erreurs peuvent se glisser.

On se propose d'étudier des techniques permettant de minimiser les conséquences de telles erreurs.

Partie A

Pour encoder un texte en binaire, on traduit chaque caractère en un octet, par exemple en utilisant le code ASCII. La table ASCII permet de traduire les caractères classiques en entiers compris entre 0 et 127, qui peuvent ensuite être écrits en binaire sur un octet, c'est-à-dire une suite de 8 bits valant chacun 0 ou 1.

Dans la table ASCII, le code associé au caractère a est 97.

Partie A

Dans la table ASCII, le code associé au caractère a est 97.

1.

Donner l'écriture binaire de a sur 8 bits.

Partie B

On s'intéresse à présent à une autre solution, reposant sur l'ajout de bits de parité.

Pour transmettre 4 bits $b_3b_2b_1b_0$, on les place dans une matrice comme suit, et on complète les lignes et les colonnes par un bit de parité (0 ou 1) pour que chaque ligne et chaque colonne possède un nombre pair de bits valant 1.

$b_3$

$b_2$

bit de parité ligne 1

$b_1$

$b_0$

bit de parité ligne 2

bit de parité colonne 1

bit de parité colonne 2

bit de parité total

Lorsqu'il n'y a qu'une seule erreur, elle se situe à l'intersection de la ligne et de la colonne qui possèdent un nombre impair de bits valant 1.

5.

On reçoit le tableau suivant. Sachant qu'une unique erreur de transmission s'est produite, cliquez sur le bit qui a subi cette erreur.

6.

On représente une telle matrice en Python par la liste de ses lignes où chaque ligne est elle-même représentée par la liste de ses bits (0 ou 1).

Écrire le code d'une fonction erreur_colonne qui prend en paramètre une matrice mat dans laquelle exactement une erreur a eu lieu lors de la transmission et qui renvoie l'indice de la colonne ayant une parité erronée.

def erreur_colonne(mat):

Partie C

Richard Hamming a mis au point une méthode qui permet d'arriver au même résultat avec seulement 7 bits transmis.

Le tableau suivant établit une correspondance entre chaque mot de 4 bits et une unique suite de 7 bits:

On admet que ce tableau est construit de sorte que, étant donné une suite de 7 bits, soit elle est présente dans le tableau, soit dans le cas contraire, il existe un unique code du tableau qui ne diffère avec elle que d'un bit.

Un mot de 4 bits ayant été encodé selon cette correspondance est transmis.

7.

Une unique erreur se glisse dans cette transmission, de sorte que le code reçu est 1010000. Déterminer, en justifiant, le mot de 4 bits initial.

8.

On souhaite écrire une fonction de correction des codes reçus.

Recopier et compléter les lignes 17, 20 et 25 du code de la fonction corriger_erreur.

def corriger_erreur(code_recu):

if code_recu in hamming_4_7:

return code_recu

else:

# Copie du code reçu créée par compréhension

code =...

for indice in range(7):

# Inversion du bit d'indice courant

code[indice] = (code[indice] + 1)...

if code in hamming_4_7:

return code

else:

# Réinit. du bit d'indice courant

code[indice] =...