Le code de Gray numérote les entiers de sorte que deux valeurs…

Exercice supplémentaire · niveau 3 (difficile) · NSI (première), chapitre 1 — Représenter les entiers · D'autres bases, d'autres codages

Énoncé

Le code de Gray numérote les entiers de sorte que deux valeurs consécutives ne diffèrent que d'un seul bit. On l'obtient par $g (n) = n \oplus (n ≫ 1)$ , où $\oplus$ est le « ou exclusif » bit à bit et $≫$ le décalage à droite. Construire les codes sur $4$ bits et vérifier la propriété, y compris entre le dernier et le premier.

Corrigé


def gray(n):
    """Code de Gray de n, sous forme d'entier."""
    return n ^ (n >> 1)

codes = [vers_base(gray(n), 2).rjust(4, "0") for n in range(16)]
for i in range(1, 16):
    diff = sum(1 for a, b in zip(codes[i - 1], codes[i]) if a != b)
    assert diff == 1
assert len(set(codes)) == 16

Les huit premiers codes sont 0000, 0001, 0011, 0010, 0110, 0111, 0101, 0100.

Deux propriétés vérifiées. Un seul bit change à chaque pas (les $15$ assertions passent), et les $16$ codes sont deux à deux distincts : c'est bien une numérotation des entiers de $0$ à $15$ , pas seulement une suite. De plus, 1000 (dernier) et 0000 (premier) ne diffèrent aussi que d'un bit : le code est cyclique.

À quoi cela sert. Sur un codeur de position mécanique, lire un compteur binaire au moment exact où plusieurs bits basculent donne une valeur aberrante : entre $0111$ et $1000$ , les quatre bits changent, et une lecture mal synchronisée peut rendre n'importe quoi. Avec le code de Gray, un seul bit change : au pire on lit l'ancienne ou la nouvelle valeur, jamais une valeur fantaisiste.

Prolongement : $\oplus$ , $≫$ et $≪$ sont les opérateurs binaires de Python, hors programme en première mais omniprésents en informatique embarquée.

Les autres exercices de ce chapitre Le cours du chapitre

Un blocage sur cet exercice ? Le tuteur d'Adloun guide par questions, sans donner la réponse.