Exercice : Clés de contrôle, cryptographie et codes correcteurs

Étape 1

Soit $n$ la longueur d'un mot de code binaire avec $n > 11$. Le nombre de messages distincts de $11$ bits à transmettre est égal à $2^{11} = 2048$. Le code comporte donc $2^{11}$ mots de code distincts.

Étape 2

Considérons un mot de code binaire $x$ de longueur $n$. Les mots binaires situés à une distance de Hamming au plus égale à $1$ de $x$ sont le mot $x$ lui-même (à distance $0$) et les mots obtenus en modifiant exactement un bit de $x$ (il y en a $n$, correspondant aux $n$ positions possibles).

Étape 3

Le nombre de mots situés à une distance au plus $1$ du mot $x$ est donc égal à : $$1 + n$$

Étape 4

Pour que le code puisse corriger une erreur sur n'importe quel bit, les boules de Hamming de rayon $1$ centrées sur les $2^{11}$ mots de code doivent être deux à deux disjointes.

Étape 5

La réunion de ces $2^{11}$ boules disjointes est incluse dans l'ensemble de tous les mots binaires de longueur $n$, dont le nombre total est $2^n$.

Étape 6

On en déduit l'inégalité théorique (borne de Hamming) : $$2^{11} \times (1 + n) \le 2^n$$

Étape 7

En divisant les deux membres par $2^{11}$, cette condition équivaut à : $$1 + n \le 2^{n - 11}$$

Étape 8

Testons les valeurs successives de l'entier $n \ge 12$ :

Étape 9

Pour $n = 12$ : $1 + 12 = 13$ et $2^{12 - 11} = 2^1 = 2$. L'inégalité $13 \le 2$ est fausse.

Étape 10

Pour $n = 13$ : $1 + 13 = 14$ et $2^{13 - 11} = 2^2 = 4$. L'inégalité $14 \le 4$ est fausse.

Étape 11

Pour $n = 14$ : $1 + 14 = 15$ et $2^{14 - 11} = 2^3 = 8$. L'inégalité $15 \le 8$ est fausse.

Étape 12

Pour $n = 15$ : $1 + 15 = 16$ et $2^{15 - 11} = 2^4 = 16$. L'inégalité $16 \le 16$ est vraie.

Étape 13

La valeur minimale de l'entier $n$ rendant théoriquement possible l'existence de ce code est donc $15$.