Exercice 2 · Bac Numérique et Sciences Informatiques Nouvelle-Calédonie 2023 (jour 1)

Exercice 2 (4 points)

On considère une donnée binaire émise par un émetteur. La transmission d'informations peut subir différentes perturbations dues à des interférences entre signaux électromagnétiques, à des imperfections du système électronique, etc. Celles-ci sont susceptibles de provoquer des erreurs dans la transmission des données.

Il est donc nécessaire de pouvoir détecter et corriger ces erreurs de transmission.

Une des techniques utilisées est d'adjoindre au signal un bit de parité. L'émetteur calcule la valeur de la parité puis transmet cette valeur dans la trame, selon la règle suivante:

le bit de parité vaut 0 si la somme des bits de données est un nombre pair;

le bit de parité vaut 1 si la somme des bits de données est un nombre impair.

Pour un nombre écrit en binaire 1001001, la somme de ses bits est de 3. Sa parité est donc 1. Le signal transmis sera 10010011.

Après réception de la donnée, le récepteur calcule le bit de parité et le compare à celui de l'émetteur contenu dans la trame. Un signal dont le bit de parité est modifié a forcément subi une altération.

1. a)

Indiquer les bits de parité associés aux représentations binaires des deux entiers naturels 9 et 16 écrits en base 10.

1. b)

Les détections d'erreurs utilisant un unique bit de parité sont cependant perfectibles. Proposer deux exemples d'erreurs n'étant pas détectables par cette technique.

2.

Écrire en langage Python une fonction calcul_parite prenant en paramètre une liste Liste_bits constituée d'entiers valant 0 ou 1 et retournant l'entier 1 ou 0 correspondant à son bit de parité.

Exemple:

>>> Liste_bits = [0, 1, 0, 0, 1, 0, 0, 1]

>>> calcul_parite(Liste_bits)

1

3) L'utilisation du codage de Hamming permet d'obtenir une technique de détection d'erreurs plus performante que celle étudiée précédemment.

On s'intéresse au code qui consiste à joindre trois bits de parité [p1, p2, p3] à quatre bits de données [d1, d2, d3, d4]. Ce qui donne un message codé sur sept bits.

Les trois bits de parité sont définis ainsi:

p1 est le bit de parité des trois bits de données d1, d2, d4;

p2 est le bit de parité des trois bits de données d1, d3, d4;

p3 est le bit de parité des trois bits de données d2, d3, d4.

Le message encodé que l'on transmet s'écrit alors comme suit: [p1, p2, d1, p3, d2, d3, d4].

3. a)

Justifier que le codage en binaire de Hamming de la donnée binaire [1, 0, 0, 1] est [0, 0, 1, 1, 0, 0, 1].

3. b)

Écrire en langage Python une fonction codage_hamming prenant en argument une liste de quatre bits valant 0 ou 1 et retournant une liste de sept bits contenant le message encodé selon le codage de Hamming. Cette fonction utilisera la fonction calcul_parite définie à la question 2.

Par exemple:

>>> donnees = [1, 0, 0, 1]

>>> codage_hamming(donnees)

[0, 0, 1, 1, 0, 0, 1]

4) Après le codage de Hamming de quatre bits de données, on obtient une liste M de sept bits [p1, p2, d1, p3, d2, d3, d4]. La technique proposée pour détecter des erreurs consiste à évaluer trois bits de contrôle de parité [c1, c2, c3]:

c1 est le bit de parité de l'ensemble [p3, d2, d3, d4];

c2 est le bit de parité de l'ensemble [p2, d1, d3, d4];

c3 est le bit de parité de l'ensemble [p1, d1, d2, d4].

4. a)

Soit la liste M = [0, 0, 1, 1, 0, 0, 1]. Lors de la transmission de cette liste, une erreur survient sur le troisième bit: le bit d1 passe à 0. Justifier, en calculant les bits de contrôle de parité, que [c1, c2, c3] = [0, 1, 1].

4. b)

Le tableau suivant indique les bits altérés correspondant aux différentes valeurs de [c1, c2, c3]:

Pas de bit altéré

p1 altéré

p2 altéré

d1 altéré

p3 altéré

d2 altéré

d3 altéré

d4 altéré

[c1, c2, c3]

[0, 0, 0]

[0, 0, 1]

[0, 1, 0]

[0, 1, 1]

[1, 0, 0]

[1, 0, 1]

?

?

Indiquer sur la copie les triplets correspondant à d3 altéré et d4 altéré.

4. c)

Indiquer en quoi cette technique utilisant le code de Hamming est plus performante que celle utilisant le bit de parité.