Fonctionnement d'un ordinateur/Les circuits de comparaison

Les comparateurs sont des circuits qui permettent de comparer deux nombres, à savoir s'ils sont égaux, si l'un est supérieur à l'autre, ou inférieur, ou différent, etc. Il faut signaler que nous avons déjà vu comment vérifier qu'un nombre est égal à une constante dans le chapitre sur les circuits combinatoires, aussi nous ne reviendrons pas dessus.

Le comparateur de 1 bit

Pour commencer, nous allons voir un circuit qui prend deux bits comme opérande, et vérifie si le premier est inférieur, supérieur ou égal au second. Les deux bits d'opérandes sont appelés respectivement a et b, et le circuit vérifie si $a=b$ , si $a>b$ ou si $a<b$ .

La supériorité et l'infériorité

En premier lieu, nous allons voir comment vérifier qu'un bit A est strictement supérieur ou inférieur à un bit B. Pour cela, le mieux est d'établir la table de vérité des deux comparaisons. La table de vérité est la suivante :

Entrée a	Entrée b	Sortie <	Sortie >
0	0	0	0
0	1	1	0
1	0	0	1
1	1	0	0

On obtient les équations suivantes :

Sortie > : ${\overline {a}}.b$
Sortie < : $a.{\overline {b}}$

Un tel circuit ne paye pas de mine, mais il permet d'encoder toutes les comparaisons possibles entre deux bits. Par exemple, nous n'avons pas besoin de circuit supplémentaire pour savoir si $a\leq b$ . Par définition, $a\leq b$ est l'inverse de $a>b$ . Donc, on peut savoir si $a\leq b$ en regardant la sortie $a>b$ : elle est à 0 si c'est le cas. Et il en est de même avec $a\geq b$ est l'inverse de $a<b$ .

L'égalité et l'inégalité

Il est aussi possible de savoir si les deux bit d'entrée sont égaux. Par définition, si les deux bit opérande sont égaux, alors les deux conditions $a<b$ et $a>b$ sont fausses. Il s'agit des deux lignes de la table de vérité où les deux sorties sont à 0. Il suffit de combiner les deux résultats avec une porte NOR pour obtenir le bit d'égalité. Pour vérifier si deux bits sont différents, c'est le même principe. Si A et B sont différents, alors on a soit A>B, soit A<B. On a juste à combiner les deux sorties "A > B" et "A < B" avec une porte OU pour tester si une des deux conditions est respectée.

Les deux circuits précédents devraient vous dire quelque chose, si vous vous souvenez vraiment bien du cours sur les portes logiques. En effet, il s'agit respectivement de portes NXOR et de portes XOR ! Pour vous en convaincre, le mieux est d'établir la table de vérité des deux circuits, qui est donnée ci-dessous. On voit rapidement qu'il s'agit des tables de vérité des portes XOR et NXOR.

Entrée 1	Entrée 2	Egalité =	Inégalité !=
0	0	0	1
0	1	1	0
1	0	1	0
1	1	0	1

La comparaison entre comparateur et soustracteurs

Dans ce qui suit, nous partons du principe que l'égalité est testée avec une porte NXOR, et non avec les circuits vus précédemment, mais c'est seulement pour simplifier les schémas. Le circuit utilise trois portes logiques : une pour tester l'égalité, une pour la supériorité, une pour l'infériorité.

Il est intéressant de comparer ce circuit avec les circuits soustracteurs et additionneurs. Pour rappel, l'image ci-contre est le circuit qui fait une soustraction sur deux bits, un demi-soustracteur. Vous remarquerez qu'il ressemble beaucoup à un comparateur-1 bit. Précisément, un demi-soustracteur est équivalent à un comparateur 1 bit qui teste les deux conditions suivantes : $a<b$ , $a\neq b$ . Et avec ces deux conditions, on peut retrouver toutes les autres !

a < b	$a\neq b$
0	0	a = b	$a\geq b$
0	1	a > b	$a\geq b$
1	0	Impossible
1	1	a < b

Il y a donc un lien assez fort entre soustraction et comparaison. Et c'est normal, car une retenue est générée quand $a<b$ ! D'ailleurs, dans les processeurs modernes, les comparateurs sont fabriqués en modifiant un soustracteur. Nous verrons comment dans la section adéquate.

Les comparateurs spécialisés

Dans cette section, nous allons voir des comparateurs assez simples, plus simples que les autres, qui ont une structure similaire. Ils sont composés d'une couche de comparateurs de 1 bits, suivi par une porte logique à plusieurs entrées. La porte logique combine les résultats de ces comparaisons individuelles et en déduit le bit de sortie. Les comparateurs que nous allons voir sont : un comparateur d'égalité qui vérifie si deux nombres sont égaux, et un comparateur qui vérifie si une opérande vaut zéro.

Le comparateur avec zéro

Le circuit que nous allons maintenant aborder ne compare pas deux nombres, mais vérifie si l'opérande d'entrée est nulle. Il fonctionne sur un principe simple : un nombre est nul si tous ses bits valent 0. La quasi-totalité des représentation binaire utilisent la valeur 0000...0000 pour encoder le zéro. Les entiers non-signés et en complément à deux sont dans ce cas, c'est la même chose en complément à un ou en signe-magnitude si on omet le bit de signe. La seule exception est la représentation one-hot, et encore !

La solution la plus simple pour créer ce circuit est d'utiliser une porte NOR à plusieurs entrées. Par définition, la sortie d'une NOR vaut zéro si un seul bit de l'entrée est à 1 et 0 sinon, ce qui répond au cahier des charges.

Il existe une autre possibilité strictement équivalente, qui inverse l'entrée avant de vérifier si tous les bits valent 1. Si l'entrée est nulle, tous les bits inversés valent tous 1, alors qu'une entrée non-nulle donnera au moins un bit à 0. Le circuit est donc conçu avec des portes NON pour inverser tous les bits, suivies d'une porte ET à plusieurs entrées qui vérifie si tous les bits sont à 1.

Notons qu'en peut passer d'un circuit à l'autre en utilisant les lois de de Morgan.

Le comparateur d'égalité

Passons maintenant à un circuit qui compare deux nombres et vérifie s'ils sont identiques/différents. Les deux sont l'inverse l'un de l'autre, aussi nous allons nous concentrer sur le comparateur d'égalité. Intuitivement, on se dit que deux nombres sont égaux s'ils ont la même représentation en binaire, ils sont différents sinon. Mais cela ne marche pas pour toutes les représentations d'entiers signés. La raison est que certaines ont deux zéros : un zéro positif et un zéro négatif. Mais laissons ces représentations de côté pour le moment.

Le circuit qui vérifie si deux nombres sont égaux est très simple : il prend les bits de même poids des deux opérandes (ceux à la même position, sur la même colonne) et vérifie qu'ils sont égaux. Le circuit est donc composé d'une première couche de portes NXOR qui vérifie l'égalité des paires de bits, suivie par une porte logique qui combine les résultats des porte NXOR. La logique dit que la sortie vaut 1 si tous les bits de sortie des NXOR valent 1. La seconde couche est donc, par définition, une porte ET à plusieurs entrées.

Une autre manière de concevoir ce circuit inverse la logique précédente. Au lieu de tester si les paires de bits sont égales, on va tester si elles sont différentes. La moindre différence entre deux bits entraîne l'inégalité. Pour tester la différence de deux bits, une porte XOR suffit. Le fait qu'une seule paire soit différente suffit à rendre les deux nombres inégaux. Dit autrement, si une porte XOR sort un 1, alors la sortie du comparateur d'égalité doit être de 0 : c'est le fonctionnement d'une porte NOR.

Voici une autre interprétation de ce circuit : le circuit compare un circuit XOR et un comparateur avec zéro. Il faut savoir que lorsqu'on XOR un nombre avec lui-même, le résultat est zéro. Et c'est le seul moyen d'obtenir un zéro comme résultat d'un XOR. Donc, les deux nombres sont XOR et un comparateur vérifie si le résultat vaut zéro. Le circuit final est donc un paquet de portes XOR, et un comparateur avec zéro.

Notons qu'on peut passer d'un circuit à l'autre en utilisant la loi de de Morgan

Le circuit qui vérifie si deux nombres sont différents peut être construit à partir du circuit précédent, en remplacant la porte ET par une porte NAND (ou la porte NOR par une porte OU).

Il existe des comparateurs d'égalité sériel, qui font la comparaison bit par bit, sur le même modèle que l'additionneur sériel. Nous aurons à utiliser ce circuit plusieurs fois dans la suite du cours, notamment dans le chapitre sur les mémoires associatives. Le circuit est très simple : la bascule n'a besoin que de mémoriser un seul bit, la comparaison d'égalité est réalisée par une porte NXOR, son résultat est combiné avec le contenu de la bascule avec une porte ET.

Les comparateurs basés sur un soustracteur

Les comparateurs présents dans les ordinateurs modernes sont des soustracteurs modifiés. Une comparaison est implémentée avec une soustraction, dont on ne conserve pas le résultat. Une fois le résultat de la soustraction a - b connu, on regarde le signe du résultat, pour vérifier s'il est positif, nul ou négatif. Ce qui permet de tester respectivement la supériorité, l'égalité et l'infériorité. Les autres conditions s'en déduisent.

La génération des conditions

Plus haut, j'ai dit qu'un comparateur soustrait les deux opérandes et regardait si le résultat est positif, nul ou négatif. Il nous faut donc déterminer si le résultat est positif, nul ou négatif. Toute la difficulté est de déterminer si le résultat est positif, négatif ou nul. Pour le déterminer, on analyse quatre propriétés intéressantes du résultat : s'il vaut zéro ou non, son bit de signe, s'il génère une retenue sortante (débordement entier non-signé) et s'il génère un débordement entier en complément à deux. Ces quatre propriétés sont empaquetées dans 4 bits, appelés les 4 bits intermédiaires. En effectuant quelques opérations sur ces 4 bits intermédiaires, on peut déterminer toutes les conditions possibles : si la première opérande est supérieure à l'autre, si elle est égale, si elle est supérieure ou égale, etc.

Dans ce qui va suivre, nous allons noter les quatre bits intermédiaires comme suit :

un bit S qui n'est autre que le bit de signe en complément à deux ;
un bit Z qui indique si le résultat est nul ou non (1 pour un résultat nul, 0 sinon) ;
un bit C qui n'est autre que la retenue sortante (1 pour un débordement d'entier non-signé, 0 sinon) ;
un bit D qui indique un débordement d'entier signé (1 pour un débordement d'entier signé, 0 sinon).

Le comparateur est donc composé de trois sous-circuits : le soustracteur, un circuit qui calcule les 4 bits intermédiaires, puis un autre qui calcule les conditions. La génération des 4 bits intermédiaire demande peu de calculs. Déterminer si le résultat est nul demande juste d'utiliser un comparateur avec zéro. Le bit de signe est tout simplement le bit de poids fort. La génération des bits de débordement a été vue dans le chapitre sur les circuits d'addition et de soustraction, pas besoin de revenir dessus. Par contre, il est intéressant de voir comment les 4 bits intermédiaires sont utilisés pour générer les conditions voulues.

Le bit Z indique que le résultat est nul, ce qui permet de détecter que deux opérandes sont égales. Déterminer si le résultat est nul ou non se fait de la même manière en complément à deux et avec des entiers non-signés, car il n'y a pas de zéro signé comme en signe-magnitude. Le bit de signe et les bits de débordement permettent de calculer la condition d'infériorité, à savoir si la première opérande est inférieure à la seconde ou non. Les autres conditions se déduisent en combinant ces deux bits. Et pour cela, on procède différemment entre le complément à deux et les opérandes non-signées.

Avec des opérandes non-signées, il n'y a pas de bit de signe. Pour déterminer si le résultat est négatif, il faut regarder si la soustraction génère une retenue sortante, un débordement entier non-signé. Si un débordement entier a lieu lors de la soustraction, le résultat est négatif : la première opérande est inférieure à la seconde. Si ce n'est pas le cas, alors la première opérande est supérieure ou égale à la seconde. En clair, le cas où "C = 1" implique que "A < B". Inversement, s'il vaut 0, alors on a "A >= B". Pour les conditions restantes, il suffit de combiner les deux résultats précédents avec le bit Z.

Opérandes non-signées
Z	C	A < B	A = B
0	0	0	0
0	1	1	0
1	0	0	1
1	1	Impossible

Voyons maintenant le cas des opérandes en complément à deux. Avec ces opérandes, le bit de signe dit si le résultat est négatif ou non, mais ne distingue pas un résultat positif d'un résultat nul. Pour cela, on doit ajouter un comparateur avec zéro, qui vérifie si le résultat est nul ou non. La logique a l'air de marcher, mais il y a un petit problème : il faut tenir compte les débordements d'entier en complément à deux. Mais restons sur des opérandes non-signées.

Pour la comparaison en complément à deux, le principe est le même : on regarde si le résultat est positif, nul ou négatif. Il faut regarder le signe du résultat, mais aussi regarder les débordements d'entier (sous-entendu, un débordement en complément à deux). Et c'est intuitif quand on sait qu'un débordement d'entier en complément à deux correspond au cas où le bit de signe a été inversé par un calcul. La règle est la suivante : le résultat est négatif si le bit de signe vaut 1 (donc résultat négatif) avant un débordement d'entier. Donc soit il n'y a pas eu de débordement et le bit de signe vaut 1, soit il y a eu un débordement et il est passé à 0. Le tout se détecte simplement en faisant un XOR entre le bit de débordement et le bit de signe.

Le tout est résumé dans le tableau suivant :

Condition testée	Calcul
A == B	Z = 1
A != B	Z = 0
Opérandes non-signées
A < B	C = 1
A >= B	C = 0
A <= B	C OU Z = 1
A > B	C ET Z = 0
Opérandes en complément à deux
A < B	S XOR D = 1
A >= B	S XOR D = 0
A <= B	(S XOR D) OU Z = 1
A > B	(S XOR D) ET Z = 0

Le comparateur complet

Il est possible de raffiner ce circuit, en ajoutant un multiplexeur en sortie, afin de choisir une condition en sortie du circuit. L'idée est que le circuit possède une seule sortie, sur laquelle on a le résultat de la condition choisie. Pour configurer le multiplexeur, le circuit possède une entrée de commande sur laquelle on envoie un nombre, qui permet de choisir la condition à tester. Par exemple, pour vérifier si deux nombres sont égaux, on envoie sur l'entrée de commande le nombre qui correspond au test d'égalité.

Nous réutiliserons ce circuit bien plus tard dans ce cours, dans les chapitres sur les branchements. Mais ne vous inquiétez pas, dans ces chapitres, nous ferons des rappels sur les bits intermédiaires, la manière dont sont calculées les conditions et globalement sur tout ce qui a été dit dans cette section. Pas besoin de mémoriser par coeur les équations de la section précédente, tout ce qui compte est que vous ayez retenu le principe général.

Les avantages du circuit comparateur-soustracteur

Utiliser un soustracteur pour les comparaisons a de nombreux avantages. Les processeurs modernes supportent l'addition, la soustraction, les comparaisons et potentiellement d'autres opérations. Utiliser le soustracteur pour faire des comparaisons permet de se passer d'un circuit comparateur en plus du soustracteur. mutualiser les deux circuits entraine une économie de portes logiques assez conséquente. Un autre avantage est est plus rapide, car le soustracteur peut utiliser des techniques d'anticipation de retenue pour accélérer les calculs, au lieu de traiter les opérandes colonne par colonne. De plus, il peut comparer aussi bien des entiers codés en complément à deux que des entiers non-signés, là où les comparateurs précédents ne le permettaient pas.

Si on veut un circuit comparateur isolé, qui n'est pas fusionné avec un soustracteur, il est possible de prendre un soustracteur et de retirer les portes inutiles. En effet, on n'a pas besoin de calculer le résultat proprement dit. Vérifier si les deux opérandes sont égales peut se faire sans utiliser le résultat de la soustraction, cela demande juste d'utiliser un comparateur d'égalité entre les deux opérandes. Le calcul des trois autres bits intermédiaires se fait avec un soustracteur castré, qui calcule et propage les retenues, mais ne calcule les bits du résultat proprement dit (sauf le bit de signe). Concrètement, cela demande juste de retirer quelques portes XOR, une par soustracteur complet. Les portes XOR utilisées pour tester l'égalité peuvent être mutualisées avec le soustracteur castré.

Les comparateurs pour opérandes entiers

Dans ce qui suit, nous allons créer des comparateurs qui n'utilisent pas de soustraction. Ils sont composés de comparateurs 1-bit. Nous avons vu que ces comparateurs de 1 bit sont semblables à des demi-soustracteurs ou des demi-additionneurs complets, et cela se ressent sur la manière dont on combine leurs résultats. Il est possible de créer des comparateurs sériels, à propagation de retenue ou parallèle, sur le même modèle que les additionneurs/soustracteurs.

Les comparateurs pour entiers non-signés

Il existe un équivalent pour les comparaisons de l'additionneur à propagation de retenue. Il traite les bits les uns après les autres, avec un comparateur 1-bit par colonne. Pour vérifier quelle opérande est supérieure, on part du bit de poids fort. Tant que les bits des opérandes sont égaux, on passe à la colonne précédente. Le premier bit rencontré qui est différent entre les deux opérandes donne le résultat. Un inconvénient de cette méthode est que le résultat est lent à calculer, car on doit traiter les opérandes colonne par colonne, comme pour les additionneurs.

Pour donner un exemple, prenons le cas d'un comparateur qui vérifie si le premier opérande A est supérieur au second opérande B. La comparaison se fait bit par bit, en partant du bit de poids fort. Il y a alors deux cas : soit le bit An est supérieur au bit Bn, soit ils sont égaux. Dans le premier cas, la réponse est immédiate. Dans le second, le résultat est celui obtenu à la colonne précédente. Le circuit est donc composé en enchainant plusieurs briques de base, une par colonne, qui ressemblent à ceci :

Vérifier l'infériorité au lieu de la supériorité se fait avec un circuit très similaire. Il suffit de remplacer la porte logique qui vérifie "A > B" par une qui vérifie "A < B".

Le processeur HP Nanoprocessor, un des tout premiers microprocesseurs, vérifiait infériorité et supériorité. Il utilisait des comparateurs 1 bit qui fournissaient deux résultats : "A > B" et "A < B", chacun contenant de quoi combiner son résultat avec le résultat de la colonne précédente. Une différence est qu'il propageait ses résultats dans l'autre sens : il envoyait les deux résultats "A > B" et "A < B" à la colonne précédente. Nous ne détaillerons pas ici le circuit de combinaison, surtout qu'il suffit d'écrire sa table de vérité pour le concevoir. Un tel circuit n'a pas l'air très optimisé, mais il était économe en portes logiques.

Il est possible de créer un comparateur configurable, qui vérifie soit l'infériorité, soit la supériorité, suivant le bit envoyé sur une entrée de commande. Pour cela, il suffit de remplacer la porte logique mentionnée avant. L'idée est d'avoir une porte qui vérifie "A > B", une autre qui vérifie qui vérifie "A < B" et un multiplexeur pour choisir entre les deux. Les multiplexeurs des différentes colonnes sont tous commandés par le même signal de commande.

Les comparateurs précédents ont le même défaut que l'additionneur à propagation de retenue, à savoir que l'on doit traiter toutes les colonnes une par une, avant de donner un résultat. Le temps de calcul est donc proportionnel à la taille des opérandes. Mais il est possible de ruser, comme pour les additionneurs, en faisant des calculs en parallèle. L'idée est d'assembler plusieurs comparateurs simples pour traiter des nombres plus longs. Par exemple, on peut combiner 2 comparateurs 4 bits pour obtenir un comparateur 8 bits. Comme pour les additionneurs/soustracteurs, il y a deux possibilités : soit on enchaine les comparateurs en série, soit on les fait travailler en parallèle.

Le comparateur sériel est construit sur le modèle de l'additionneur-soustracteur sériel. Mais un tel circuit est rarement utilisé, pour une raison simple : il est possible de modifier un additionneur-soustracteur sériel de manière à ce qu'il fasse des comparaisons. Le cout en circuits est ridicule, à peine une dizaine de portes logiques, pour un gain en fonctionnalités drastique. Personne n'a intérêt à utiliser un comparateur sériel quand il peut ajouter quelques portes pour supporter l'addition et la soustraction en plus. Aussi, tout ce qui suit étudiera des comparateurs dit parallèles, à savoir non-sériels.

Le comparateur signe-magnitude

Les comparateurs précédents comparaient des opérandes non-signées, à savoir nulles ou positives, mais pas négatives. Et comparer deux opérandes signées n'est pas la même chose que comparer deux nombres non-signés, sauf éventuellement pour la comparaison d'égalité/différence. Et la comparaison ne s'effectue pas de la même manière selon que les nombres à comparer sont codés en signe-magnitude, en complément à deux, ou dans une autre représentation. Avec les représentations en complément à un ou à deux, le seul moyen pratique de faire une comparaison est d'utiliser une soustraction. Aussi, nous ne verrons que la comparaison en signe-magnitude.

Effectuer une comparaison entre deux nombres en signe-magnitude demande de comparer les valeurs absolues, mais il faut aussi tenir compte des bits de signe. Le comparateur en sgine-magnitude contient donc un circuit comparateur, qui compare les valeurs absolues. Le résultat de cette comparaison est alors combiné avec les bits de signe par un circuit combinatoire assez simple. Le circuit en question prend 4 bits : deux pour le résultat de la comparaison, et les deux bits de signe.

La comparaison des bits de signe prend le pas sur la comparaison des valeurs absolues. Par exemple, 2 est supérieur à -255, bien que ce ne soit pas le cas pour les valeurs absolues. Ce fait n'est que l'expression du fait qu'un nombre positif est systématiquement supérieur à un négatif, de même qu'un négatif est systématiquement inférieur à un positif. Ce n'est que quand les deux bits de signes sont égaux que la comparaison des valeurs absolue est à prendre en compte.

Pour des opérandes de même signe, la comparaison des valeurs absolues ne donne pas immédiatement le résultat. En effet, il y a un cas problématique : les opérandes négatives. Si je compare - 2 et -5, la comparaison des valeurs absolues me dit que 5 > 2. Pourtant, le résultat est que - 2 > -5, soit, l'inverse. Et le même phénomène a lieu quand on compare deux opérandes négatives. Intuitivement une solution est d'inverser les résultats des comparaisons de supériorité/infériorité. Mais il faut prendre en compte le cas où les deux opérandes sont nulles, ce qui biaise le résultat.

Voici la table de vérité de ce circuit, simplifiée :

Bit de signe de A	Bit de signe de B	Résultats de la comparaison		Sortie <	Sortie >
0 (+)	0 (+)	X	Y	X	Y
1 (-)	0 (+)	X	Y	0	1
0 (+)	1 (-)	X	Y	1	0
1 (-)	1 (-)	X	Y	${\overline {X}}$	${\overline {Y}}$

Notons que la dernière ligne ne tient pas compte du cas où les deux valeurs absolues sont nulles.

◄ Retour vers « Les circuits pour l'addition et la soustraction »

Sommaire du livre

Continuer vers « Les unités arithmétiques et logiques entières (simples) » ►