Comparer et contrôler un octet : égalité, parité, aléas

La stratégie. Le XOR est un détecteur de différence : on l'emploie bit à bit pour comparer, en cascade pour compter la parité. Le nombre de portes ne dit pas tout : la profondeur du circuit, le plus long chemin d'une entrée à la sortie, fixe son temps de réponse, et l'inégalité des chemins fait naître des impulsions parasites.

1) Le comparateur d'un bit. « $a>b$ » n'est vrai que pour $a=1$, $b=0$ : $a\overline{b}$. « $a<b$ » : $\overline{a}b$. « $a=b$ » : $\overline{a}\overline{b}+ab=\overline{a\oplus b}$, la porte XNOR. Les trois sorties s'excluent et l'une vaut toujours $1$ ; la somme des deux premières, $a\overline{b}+\overline{a}b$, est le XOR, qui vaut $1$ quand les bits diffèrent.

2) Huit XOR et un NOR. Les octets sont égaux si et seulement si aucun bit ne diffère, c'est-à-dire si tous les $x_i\oplus y_i$ sont nuls : $$E=\overline{(x_0\oplus y_0)+(x_1\oplus y_1)+\cdots +(x_7\oplus y_7)}={\mathrm{NOR}}_8(x_0\oplus y_0,\dots ,x_7\oplus y_7).$$ Huit XOR et une NOR à huit entrées : deux niveaux, donc un temps de réponse de deux délais de porte, quelle que soit la position du bit qui diffère. On pouvait aussi écrire $E=\prod \overline{x_i\oplus y_i}$, un AND de huit XNOR : c'est la même fonction, par De Morgan.

3) Parité : chaîne ou arbre. Le OU exclusif est associatif et commutatif ; $x_0\oplus \cdots \oplus x_7$ vaut $1$ si et seulement si le nombre de $1$ est impair. L'émetteur a rendu ce nombre pair : $P=1$ signale une erreur de transmission. Chaque XOR à deux entrées réduit de un le nombre de termes : il en faut $8-1=7$, dans tous les cas. Mais dans la chaîne, un changement de $x_0$ traverse les sept portes : temps de réponse $7t_p=70\mathrm{ns}$. Dans l'arbre, chaque entrée traverse ${\log }_{2}8=3$ portes : $3t_p=30\mathrm{ns}$. Pour $n$ bits, il faut toujours $n-1$ portes, et la profondeur vaut $n-1$ pour la chaîne, $\lceil {\log }_{2}n\rceil$ pour l'arbre : pour $64$ bits, $63$ portes dans les deux cas, mais $63t_p=630\mathrm{ns}$ contre $6t_p=60\mathrm{ns}$. Même nombre de portes, temps dix fois plus court : l'associativité permet de réorganiser le calcul sans le changer.

4) Ce que la parité voit. Pour huit bits indépendants : $$P_1=8p(1-p{)}^7\approx 8,0\times 10^{-4},P_2=(\genfrac{}{}{0ex}{}{8}{2})p^2(1-p{)}^6=28p^2(1-p{)}^6\approx 2,8\times 10^{-7}.$$ Une erreur change la parité du nombre de $1$ : elle est détectée. Deux erreurs la laissent inchangée : elles sont invisibles, et plus généralement toute erreur portant sur un nombre pair de bits. Comme $P_2/P_1\approx 3,5\times 10^{-4}$, la parité laisse passer environ un octet faux sur trois mille. Cas limite : $P_2/P_1$ croît comme $p$, et le contrôle perd son intérêt sur une liaison très bruitée.

5) L'aléa. Deux bits changent : la parité ne change pas, $P$ final $=0$. Dans la chaîne, $x_7$ attaque la dernière porte : son changement atteint la sortie après $t_p=10\mathrm{ns}$ ; celui de $x_0$ traverse les sept portes et l'atteint à $70\mathrm{ns}$. Entre les deux, la dernière porte « voit » un seul bit changé : $P$ passe à $1$ de $10$ à $70\mathrm{ns}$, puis revient à $0$. C'est une impulsion parasite de $60\mathrm{ns}$, un aléa, et le récepteur qui lirait $P$ à $t=40\mathrm{ns}$ signalerait une erreur qui n'existe pas. Dans l'arbre, les deux changements traversent chacun trois portes et arrivent ensemble à la dernière, à $20\mathrm{ns}$ sur ses deux entrées : idéalement, la sortie ne bouge pas (en pratique, de petites différences entre portes laissent une impulsion très brève).

Conclusion. La sortie d'un circuit combinatoire n'est sûre qu'après le plus long délai de propagation ($70\mathrm{ns}$ pour la chaîne, $30\mathrm{ns}$ pour l'arbre) : on ne la lit qu'à des instants choisis, cadencés par une horloge dont la période dépasse ce délai. C'est l'idée qui fonde la logique séquentielle synchrone.

Ce que l'exercice installe. Le XOR détecte la différence : bit à bit, il compare (égalité $=\mathrm{NOR}$ des XOR) ; en cascade, il calcule la parité, qui détecte un nombre impair d'erreurs et rien d'autre. À nombre de portes égal, la profondeur fixe le temps de réponse : arbre en ${\log }_{2}n$, chaîne en $n-1$. Des chemins de longueurs inégales créent des aléas : une sortie combinatoire se lit après le plus long délai.