Exercice
Le but du codage de Gray est de représenter les entiers de telle sorte qu’un seul bit soit modifié à chaque incrémentation. Pour $n$ un entier strictement positif, on définit la fonction $\Gamma_n$ de $\{\;0,\;\ldots,\;2^{n}-1\;\}$ dans $\{\;0,\;1\;\}^{n}$, qui à un entier associe son codage de Gray sur $n$ bits. On définit de même la fonction $B_n$ de $\{\;0,\;\ldots,\;2^{n}-1\;\}$ dans $\{\;0,\;1\;\}^{n}$ qui à un entier associe son écriture binaire sur $n$ bits.
On définit récursivement $\Gamma_n$ : $\Gamma_1(0) = 0$, $\Gamma_1(1) = 1$ et $\forall n \geq 2,\;\forall k \lt 2^{n}$ :
\[\Gamma_n(k) = \begin{cases} 0\Gamma_{n-1}(k) \text{ si $k \lt 2^{n-1}$ } \\ 1\Gamma_{n-1}(2^{n}-k-1) \text{ sinon }\end{cases}\]
$1.$a) Donner la table des valeurs de $\Gamma_3$.
b) Prouver que pour tout entier $n$ et pour tout entier $k \lt 2^{n} – 1$, les représentations $\Gamma_n(k)$ et $\Gamma_n(k+1)$ ne diffèrent que d’un seul bit.
On note cependant que cette définition ne nous permet pas de passer rapidement d’un entier en binaire à sa représentation en codage de Gray.
Soit $n \geq 1$ et $k \lt 2^{n}$. On considère la fonction $\Phi_n$ de $\{\;0,\;\ldots,\;2^{n}-1\;\}$ dans $\{\;0,\;1\;\}^{n}$ définie par :
\[\Phi_n(k) = B_n(k) \oplus B_n\left(\left\lfloor \frac{k}{2}\right\rfloor\right) \]
où l’opérateur $\oplus$ correspond au XOR bit à bit.
$2.$ Prouver que la fonction $\Phi_n$ est bijective.
$3.$ Soit $0 \leq r \lt 2^{n}$. Prouver la relation :
\[B_{n+1}(2^n+r) \oplus B_{n+1}(2^n-r-1) = \underbrace{11\ldots1}_{n+1 \text{ fois}}\]
$4.$ Déduire que pour tout $n$ et tout $k \lt 2^{n}$, on a $\Gamma_n(k) = \Phi_n(k)$.
$5.$ Donner une méthode directe pour passer de $\Gamma_n(k)$ à $B_n(k)$ et de $B_n(k)$ à $\Gamma_n(k)$.
Maintenant que nous pouvons aisément représenter les entiers par un codage de Gray, il nous reste à savoir comment incrémenter les entiers sans repasser par le codage binaire. Pour ce faire on présente la méthode suivante : soit $k \lt 2^{n}-1$. On connaît $\Gamma_n(k)$ et on cherche $\Gamma_n(k+1)$. Si le nombre de $1$ dans $\Gamma_n(k)$ est pair, alors on inverse le bit le plus à droite. Sinon, on inverse le bit à gauche du bit à $1$ le plus à droite.
$6.$ Prouver la correction de cette méthode.
Correction
$1.$ a) Calculons $\Gamma_3$.
\[\begin{matrix}\Gamma_1(0) = 0 \\ \Gamma_1(1) = 1\end{matrix} \Rightarrow \begin{matrix}\Gamma_2(0) = 00 \\ \Gamma_2(1) = 01 \\ \Gamma_2(2) = 11 \\ \Gamma_2(3) = 10 \end{matrix} \Rightarrow \begin{matrix}\Gamma_3(0) = 000 \\ \Gamma_3(1) = 001 \\ \Gamma_3(2) = 011 \\ \Gamma_3(3) = 010 \\ \Gamma_3(4) = 110 \\ \Gamma_3(5) = 111 \\ \Gamma_3(6) = 101 \\ \Gamma_3(7) = 100\end{matrix}\]
b) Prouvons par récurrence sur $n\geq1$ que pour tout $k \lt 2^{n}-1$, $\Gamma_n(k)$ et $\Gamma_n(k+1)$ ne diffèrent que d’un seul bit.
La table des valeurs de $\Gamma_1$ ci-dessus nous permet de vérifier le cas $1$. On suppose maintenant la propriété vraie au rang $n$, montrons qu’elle le reste au rang $n+1$.
Soit $k \lt 2^{n+1}-1$.
Si $k \lt 2^{n}-1$ : on a par hypothèse de récurrence que $\Gamma_n(k)$ et $\Gamma_n(k+1)$ ne diffèrent que d’un seul bit. Or :
\[\Gamma_{n+1}(k) = 0\Gamma_{n}(k) \text{ et } \Gamma_{n+1}(k+1) = 0\Gamma_{n}(k+1)\]
Ainsi $\Gamma_{n+1}(k)$ et $\Gamma_{n+1}(k)$ ne diffèrent que d’un seul bit.
Si $2^{n}-1 \lt k \lt 2^{n+1}-1$ : on a $\Gamma_{n+1}(k) = 1\Gamma_{n}(2^{n+1}-k)$ et $\Gamma_{n+1}(k+1) = 1\Gamma_{n}(2^{n+1}-k-1)$. Or, par hypothèse de récurrence, $\Gamma_{n}(2^{n+1}-k)$ et $\Gamma_{n}(2^{n+1}-k-1)$ ne diffèrent que d’un seul bit, et donc $\Gamma_{n+1}(k)$ et $\Gamma_{n+1}(k+1)$ aussi.
Enfin, si $k = 2^{n+1}-1$ : on a $\Gamma_{n+1}(k) = 0\Gamma_{n}(k)$ et $\Gamma_{n+1}(k+1) = 1\Gamma_{n}(k)$. Ces deux mots ne diffèrent que sur le premier bit, donc $\Gamma_{n+1}(k)$ et $\Gamma_{n+1}(k+1)$ ne diffèrent que d’un unique bit.
Cela prouve la propriété au rang $n+1$ et achève la récurrence.
$2.$ On note $B_n(k) = b_1 b_2 \ldots b_n$. On a alors $\displaystyle B_n\left(\left\lfloor \frac{k}{2}\right\rfloor\right) = 0 b_1 b_2 \ldots b_{n-1}$. De ce fait, en écrivant $\Phi_n(k) = a_1 a_2 \ldots a_n$ on a les relations suivantes :v
\begin{align*}
a_1 & = b_1 \\
a_2 & = b_1 \oplus b_2 \\
a_3 & = b_2 \oplus b_3 \\
\cdots & = \cdots \\
a_n & = b_{n-1} \oplus b_n
\end{align*}
On considère la fonction $F_n$ de $\{0,\;1\}^{n}$ dans $\{0,\;2^{n}\}$ définie par $F_n(a_1 a_2 \ldots a_n) = u$ où $u$ a pour représentation binaire $u_1 u_2 \ldots u_n$ avec
\begin{align*}
u_1 & = a_1 \\
u_2 & = a_1 \oplus a_2 \\
u_3 & = a_1 \oplus a_2 \oplus a_3 \\
\vdots & = \vdots \\
u_n & = a_1 \oplus a_2 \oplus \ldots \oplus a_n
\end{align*}
On note que $\displaystyle F_n\left(\Phi_n(k)\right) = k$. De ce fait $\boxed{\Phi_n \text{ est bijective. }}$
$3.$ Cette relation signifie simplement que tous les bits de la représentation en binaire de $2^{n}+r$ et $2^{n}-r-1$ sont distincts. Pour le prouver, on procède par récurrence forte sur $(n,r)$. Soit $n \in \mathbb{N}$ et $r \lt 2^{n}$. On note $\mathcal{H}(n,r) = $ « Tous les bits de la représentation en binaire sur $n+1$ bits de $2^{n}+r$ et $2^{n}-r-1$ sont distincts ».
On vérifie à la main pour $n=0$ et $n=1$.
Pour tout $n$, on a :
\[B_n(2^n) = 1\underbrace{00\ldots0}_{n \text{ fois }} \text{ et } B_n(2^n-1) = 0\underbrace{11\ldots1}_{n \text{ fois }}\]
Ce qui prouve $\mathcal{H}(n,0)$.
Soit $n \geq 1$ et $2^{n}-1 > r \geq 0$. On suppose $\mathcal{H}(m,k)$ vrai pour tout $m \lt n$, $k \lt 2^{m}$ et $\mathcal{H}(n, l)$ vrai pour $0 \leq l \leq r$. Prouvons $\mathcal{H}(n,r+1)$.
On note $B_{n+1}(2^{n}+r) = b_1 b_2 \ldots b_{n+1}$. Par hypothèse de récurrence on a :
\[B_{n+1}(2^{n}-r-1) = \overline{b_1} \overline{b_2} \ldots \overline{b_{n+1}}\]
où $\bar{b_i}$ est le bit inverse de $b_i$.
Si $b_{n+1} = 0$ : on a alors $B_{n+1}(2^{n}+r+1) = b_1 b_2 \ldots b_{n}1$ et $B_{n+1}(2^{n}-r-2) = \overline{b_1} \overline{b_2} \ldots \overline{b_{n}}0$. Donc les représentations binaires de $2^{n}+r+1$ et $2^{n}-r-2$ sur $n+1$ bits sont bien distinctes bit à bit.
Si $b_{n+1}=1$ : on a $r$ impair.
Soit $\displaystyle k = \frac{r+1}{2}$. On a alors $2(2^{n-1} + k ) = 2^{n} + r + 1$. On rappel que pour représenter le double d’un entier en binaire, il suffit d’ajouter un $0$ à la fin, ce qui nous donne donc :
\[B_{n+1}\left(2^{n}+r+1\right) = B_{n}\left(\frac{2^{n}+r-1}{2}+1\right)0\]
De même $\displaystyle B_{n+1}(2^{n}-r-2) = B_{n}\left(2^{n-1}-k-1\right)1$.
Or, par hypothèse de récurrence, $B_{n}\left(2^{n-1}-k-1\right) = \overline{B_{n}\left(2^{n-1}+k\right)}$.
Il en résulte que $\displaystyle \boxed{B_{n+1}\left(2^{n}+r+1\right) = \overline{B_{n+1}\left(2^{n}-r-2\right)}}$. Cela prouve donc ${\mathcal{H}(n,r+1)}$ et achève notre récurrence.
$4.$ Pour ce faire, il nous suffit de montrer que $\Gamma_1 = \Phi_1$, ce qui est immédiat ; puis que la récurrence suivante est satisfaite pour $n\geq2$ :
\[\Phi_{n}(k) = \begin{cases} 0\Phi_{n-1}(k) \text{ si $k \lt 2^{n-1}$ } \\ 1\Phi_{n-1}(2^{n}-k-1) \text{ sinon }\end{cases}\]
Si $k \lt 2^{n-1}$ on a bien $\Phi_{n}(k) = 0\Phi_{n-1}(k)$.
Si $k \geq 2^{n-1}$ on pose $r = k-2^{n-1}$. On a alors $k = 2^{n-1}+r$ et $2^{n}-k-1 = 2^{n-1}-r-1$. On écrit $B_{n}(k) = b_1 b_2 \ldots b_n$. La question précédente nous donne $B_{n}(2^{n-1}-r-1) = \overline{b_1} \overline{b_2} \ldots \overline{b_n}$. On note de plus que $b_1 = 1$. Ainsi :
\[\Phi_n(k) = 1(b_1 \oplus b_2)\ldots(b_{n-1}\oplus b_n) = 1u\]
Avec $u$ un mot binaire sur $n-1$ bits.
Et de plus :
\begin{align*}
\Phi_n(2^{n-1}-r-1) & = 0(\overline{b_1} \oplus \overline{b_2})\ldots(\overline{b_{n-1}}\oplus \overline{b_n}) \\
& = 0(b_1 \oplus b_2)\ldots(b_{n-1}\oplus b_n) \\
\Phi_n(2^{n-1}-r-1) & = 0u
\end{align*}
Donc $\displaystyle \boxed{\Phi_{n-1}\left(2^{n-1}-r-1\right) = u}$ et $\Phi$ satisfait notre relation de récurrence.
On a donc bien prouvé que pour tout $n$ et pour tout $k \lt 2^{n}$ :
\[\boxed{\Gamma_n(k) = \Phi_n(k)}\]
$5.$ Pour passer de $\Gamma_n(k)$ à $B_n(k)$ on utilise la représentation binaire de la fonction $F$ définie plus haut. Autrement dit, pour un mot $a_1 a_2 \ldots a_n$ codage de Gray d’un nombre, la représentation en binaire sur $n$ bits de ce nombre est $b_1 b_2 \ldots b_n$ avec :
\begin{align*}
b_1 & = a_1 \\
b_2 & = a_1 \oplus a_2 \\
b_3 & = a_1 \oplus a_2 \oplus a_3 \\
\cdots & = \cdots \\
b_n & = a_1 \oplus a_2 \oplus \ldots \oplus a_n
\end{align*}
Pour passer d’un codage binaire $b_1 b_2 \ldots b_n$ à un codage de Gray $a_1 a_2 \ldots a_n$ on pose :
\begin{align*}
a_1 & = b_1 \\
a_2 & = b_1 \oplus b_2 \\
a_3 & = b_2 \oplus b_3 \\
\cdots & = \cdots \\
a_n & = b_{n-1} \oplus b_n
\end{align*}
On note que ces deux opérations peuvent être chacune réalisées avec $n-1$ portes XOR.
$6.$ On pose $|u|_1$ le nombre de $1$ dans le mot $u$.
Encore une fois, on va procéder par récurrence sur $n$, la taille de notre représentation. Montrons que pour les représentations de taille $n$ notre méthode effectue bien l’incrémentation sur les entiers représentés avec le codage de Gray.
Le cas $n=1$ se vérifie aisément.
On suppose la propriété vraie au rang $n$, prouvons qu’elle le reste au rang $n+1$. Soit $k$ un entier positif inférieur strictement à $2^{n+1}-1$. Si $k$ est inférieur strictement à $2^{n}-1$ notre méthode fonctionne par hypothèse de récurrence, et on peut calculer le codage de Gray de $k+1$. Sinon, si $k = 2^{n}-1$, on a $\Gamma_{n}(k) = 10\ldots0$. Et par notre définition, $\Gamma_{n+1}(k) = 010\ldots0$ et $\Gamma_{n+1}(k+1) = 110\ldots0$. Or $\Gamma_{n+1}(k)$ possède un nombre impair de $1$. Notre méthode fonctionne donc bien.
Enfin, si $k \geq 2^n$ on considère $2^{n+1}-k-1$ qui est inférieur à $2^n$.
Comme on modifie un bit à chaque incrémentation, on change également la parité du nombre de $1$ dans notre codage. Il en résulte que $|\Gamma_{n+1}(k)|_1$ est de même parité que $k$. Il en résulte que $|\Gamma_{n+1}(k)|_1$ est de même parité que $|\Gamma_{n+1}(2^{n+1}-k-2)|_1$.
Si $k$ est pair, $2^{n+1}-k-2$ est également pair et on a montré précédemment que pour passer de $\Gamma_{n+1}(2^{n+1}-k-2)$ à $\Gamma_{n+1}(2^{n+1}-k-1)$ il suffisait de changer le bit le plus à droite. Donc, pour passer de $\Gamma_{n+1}(k+1)$ à $\Gamma_{n+1}(k)$, il faut changer le bit le plus à droite. Autrement dit, on doit bien changer le dernier bit pour passer de $\Gamma_{n+1}(k)$ à $\Gamma_{n+1}(k+1)$.
Le cas impair se résout de même.
On a donc prouver le cas $n+1$, ce qui achève la récurrence.
On a donc bien une méthode simple pour implémenter l’incrémentation avec le codage de Gray.