Fonctionnement d'un ordinateur/Les circuits de comparaison

Un livre de Wikilivres.
Sauter à la navigation Sauter à la recherche

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. Dans ce qui va suivre, nous allons voir quatre types de comparateurs. Le premier type de circuit vérifie si un nombre est nul ou différent de zéro. Le second vérifie si deux nombres sont égaux, tandis que le troisième vérifie s'ils sont différent. Enfin, le quatrième vérifie si un nombre est supérieur ou inférieur à un autre. 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.

Comparaison avec zéro[modifier | modifier le wikicode]

Le premier circuit que nous allons aborder vérifie si un nombre est nul. Il possède donc plusieurs entrées, sur lesquelles on place les bits du nombre à comparer. Sa sortie est un simple bit, qui vaut 1 si le nombre en entrée est nul et 0 sinon. Ce circuit fonctionne sur un principe simple : un nombre est nul si tous ses bits valent 0. Dit autrement, si on inverse tout les bits du nombre, les bits inversés valent tous 1. Pour cela, ce circuit va être décomposé en deux sous-circuits : un qui inverse tous les bits, et un autre qui vérifient s'ils valent tous un. Le premier circuit est naturellement composé de portes NON, une par bit. Pour vérifier si tous les bits sont à 1, il suffit d'utiliser la porte logique qu'il faut. Par définition, une porte ET correspond au circuit recherché.

Circuit compare si l'opérande d'entrée est nulle.

Comparateur avec une constante[modifier | modifier le wikicode]

Voyons maintenant un comparateur qui vérifie si le nombre d'entrée est égal à une certaine constante (2, 3, 5, 8, ou tout autre nombre) qui dépend du circuit et renvoie un 1 seulement si c’est le cas. Ainsi, on peut créer un circuit qui mettra sa sortie à 1 uniquement si on envoie le nombre 5 sur ses entrées. Ou comme autre exemple, créer un circuit qui met sa sortie à 1 uniquement quand l'entrée correspondent au nombre 126. Et ainsi de suite : tout nombre peut servir de constante à vérifier.

Circuit, conception[modifier | modifier le wikicode]

Tout circuit de ce type est systématiquement composé de deux couches de portes logiques : une couche de portes NON et une porte ET à plusieurs entrées. Créer un tel circuit se fait en trois étapes. En premier lieu, il faut convertir la constante à vérifier en binaire : dans ce qui suit, nous nommerons cette constante k. En second lieu, il faut créer la couche de portes NON. Pour cela, rien de plus simple : on place des portes NON pour les entrées de la constante k qui sont à 0, et on ne met rien pour les bits à 1. Par la suite, on place une porte ET à plusieurs entrées à la suite de la couche de portes NON.

Exemples de comparateurs (la constante est indiquée au-dessus du circuit).

Fonctionnement[modifier | modifier le wikicode]

Pour comprendre pourquoi on procède ainsi, il faut simplement regarder ce que l'on trouve en sortie de la couche de portes NON :

  • si on envoie la constante, tous les bits à 0 seront inversés alors que les autres resteront à 1 : on se retrouve avec un nombre dont tous les bits sont à 1 ;
  • si on envoie un autre nombre, soit certains 0 du nombre en entrée ne seront pas inversés, ou alors des bits à 1 le seront : il y aura au moins un bit à 0 en sortie de la couche de portes NON.

Ainsi, on sait que le nombre envoyé en entrée est égal à la constante k si et seulement si tous les bits sont à 1 en sortie de la couche de portes NON. Dit autrement, la sortie du circuit doit être à 1 si et seulement si tous les bits en sortie des portes NON sont à 1 : il ne reste plus qu'à trouver un circuit qui prenne ces bits en entrée et ne mette sa sortie à 1 que si tous les bits d'entrée sont à 1. Il existe une porte logique qui fonctionne ainsi : il s'agit de la porte ET à plusieurs entrées.

Fonctionnement d'un comparateur avec une constante.

Vérification d'égalité et de différence pour entiers[modifier | modifier le wikicode]

Les circuits qui vérifient si deux nombres sont égaux ou différents sont plus simples que les autres comparateurs. Ceux-ci sont composé de deux couches de portes logiques, contrairement aux autres comparateurs. La vérification de supériorité ou d'infériorité est nettement plus complexe et leur fonctionnement est quelque peu différent. C'est la raison pour laquelle nous allons voir ces deux types de comparateurs ensemble.

Vérification d'égalité[modifier | modifier le wikicode]

Maintenant, nous allons créer un circuit qui vérifie si deux nombres sont égaux. Pour cela, il va prendre tous les bits de même poids (sur la même colonne) et vérifier qu'ils sont égaux. Si deux bits de même poids sont différents, quelque soit la colonne, alors les deux nombres sont différents. Ce circuit peut être vu comme une amélioration du circuit de vérification avec zéro. Comme celui-ci, il est décomposé en deux couches de portes logiques : une première couche vérifie l'égalité d'une paire de bits, le second combine les résultats pour chaque paire. Le premier circuit est composé d'une porte logique par paire. Celle-ci prend deux bits et sort un 1 si ceux-ci sont égaux : par définition, il s'agit d'une porte NXOR. Ensuite, les sorties des portes NXOR sont combinées en un seul bit de résultat. Celui-ci vaut 1 si tous les bits de sortie des NXOR valent 1 : il s'agit donc, par définition, d'une porte ET à plusieurs entrées.

Identity Comparator

Vérification de différence[modifier | modifier le wikicode]

Le circuit qui vérifie si deux nombres sont différents peut être construit à partir du circuit précédent. Par définition, deux nombres sont différents s'ils ne sont pas égaux. On pourrait donc ajouter une simple porte NON à la suite d'un circuit d'égalité, ce qui serait particulièrement simple. Mais il existe une autre solution, complétement équivalente, qui permet d'économiser l'utilisation de cette porte NON. Deux nombres sont différents si au moins un de leur bit diffère : il doit y avoir au moins un bit qui est différent de celui à la même place dans l'autre nombre. Pour cela, on peut adapter le circuit précédent, de comparaison d'égalité. La première couche doit cette fois-ci vérifier que les deux bits sont différents et non égaux : la porte NXOR est donc naturellement remplacée par une XOR. Ensuite, la porte ET est remplacée. Cette fois-ci, au moins un des bit de sortie des XOR doit être à 1, les autres paires de bits pouvant être égales dans deux nombres différents. La porte ET est donc remplacée par une porte OU à plusieurs entrées.

Komparator dig adv

Comparateur pour entiers non-signés[modifier | modifier le wikicode]

Dans ce qui va suivre, nous allons créer un circuit qui est capable de vérifier l'égalité, la supériorité ou l'infériorité de deux nombres. Celui-ci prend deux nombres en entrée, et fournit trois bits : un pour l'égalité des deux nombres, un autre pour préciser que le premier est supérieur au second, et un autre pour préciser que le premier est inférieur au second.

Comp 4 Bit

Il existe deux méthodes pour créer des comparateurs. La toute première utilise un soustracteur, qui soustrait les deux nombres et vérifie leur signe. Si la soustraction A - B donne un résultat nul, les deux nombres A et B sont égaux. Si le résultat est positif, alors on sait que A > B. De même, un résultat négatif indique que A < B. Ainsi, le bit de sortie A > B est simplement égal au bit de signe du résultat, tandis que le bit de sortie est égal à son inverse. Pour savoir si le résultat de la soustraction est nul, un simple comparateur avec zéro suffit. Cette méthode, qui utilise un soustracteur et un comparateur avec zéro est relativement simple et économe en circuits, ce qui fait qu'elle est utilisée dans la majorité des processeurs actuels. Mais il est possible de créer des circuits dédiés aux comparaisons. Ceux-ci sont créés à partie de comparateurs de 1 bits, qui sont assemblés pour obtenir un comparateur de nombres de N bits. Nous allons les aborder dans ce qui suit.

Comparateur de 1 bit[modifier | modifier le wikicode]

Pour commencer, nous devons partir d'un comparateur de 1 bit. Celui-ci prend deux bits en entrée, et fournit trois bits en sortie : un pour l'égalité, un autre pour la supériorité et un autre pour l'infériorité.

1 bit magnitud comparator IEC

Sa table de vérité est la suivante :

Entrée A Entrée B Sortie = Sortie < Sortie >
0 0 1 0 0
0 1 0 1 0
1 0 0 0 1
1 1 1 0 0

On obtient les équations suivantes :

D'après ces équations, ce circuit devrait être le suivant :

Magnitude Comparator

En voici une version alternative, qui a un temps de propagation plus long :

Comparateur de 1 bit.

Une fois ce comparateur de 1 bit obtenu, nous pouvons utiliser un comparateur pour chaque colonne à comparer : chaque comparateur compare les bits de même poids de deux nombres. Reste à combiner leurs résultats. Par exemple, le bit final d'égalité peut être obtenu simplement : il suffit de faire un ET logique entre tous les bits d'égalité fournis par les comparateurs de 1 bit. Simple logique : deux nombres sont égaux si tous leurs bits sont égaux. En cela, cette portion du circuit ne diffère aucunement du comparateur d'égalité vu plus haut. Mais pour le bit de supériorité et d'infériorité, c'est autre chose.

Comparateur sériel[modifier | modifier le wikicode]

La manière la plus simple est de faire la comparaison bit par bit avec un circuit séquentiel, sur le même modèle que l'additionneur série. Pour cela, on doit utiliser trois registres à décalage : un pour le résultat, et un pour chaque opérande. Outre les registres à décalage, on trouve un comparateur 1 bit amélioré qui fait la comparaison bit par bit, colonne par colonne. Le tout est de savoir comment combiner les résultats de la colonne précédente avec les résultats de la colonne en court de traitement, chose que le comparateur 1 bit précédent ne sait pas faire. Pour cela, nous allons devoir créer un circuit, nommé le comparateur complet.

Comparateur sériel.

Dans ce qui va suivre, la comparaison va s'effectuer en partant du bit de poids faible et se fera de gauche à droite, chose qui a son importance pour ce qui va suivre. Quelque soit le sens de parcours, on sait comment calculer le bit d'égalité : celui-ci est égal à un ET entre le bit d'égalité fournit en entrée, et le résultat de la comparaison A = B. Pour les bits de supériorité et d'infériorité, les choses changent : la colonne en cours de traitement supplante l'autre colonne. Dit autrement, les bits de poids fort donnent le résultat de la comparaison. Pour déterminer comment calculer ces bits, le mieux est encore d'établir la table de vérité du circuit pour ces deux bits. Nous allons postuler que les bits A > B et A < B ne peuvent être à 1 en même temps : il s'agit de supériorité et d'infériorité stricte. Voici la table de vérité :

Entrée > Entrée < A > B A < B Sortie > Sortie <
0 0 0 0 0 0
0 0 0 1 0 1
0 0 1 0 1 0
0 0 1 1 X X
0 1 0 0 0 1
0 1 0 1 0 1
0 1 1 0 1 0
0 1 1 1 X X
1 0 0 0 1 0
1 0 0 1 0 1
1 0 1 0 1 0
1 0 1 1 X X
1 1 0 0 X X
1 1 0 1 X X
1 1 1 0 X X
1 1 1 1 X X

Les équations logiques obtenues sont donc les suivantes :

Comparateur série[modifier | modifier le wikicode]

Il est possible de dérouler le circuit précédent, de la même manière que l'on peut dérouler un additionneur série pour obtenir un additionneur à propagation de retenue. Le circuit est alors composé de comparateur complets placés en série, la sortie des uns étant envoyée sur l'entrée d'un autre. Le circuit comparateur obtenu est alors très similaire à l'additionneur à propagation de retenue, à une différence près : ce ne sont pas des retenues qui sont propagées d'un comparateur complet à l'autre, mais des bit de supériorité, d'infériorité et d'égalité. Pur cela, on doit ajouter une troisième entrée, qui permet de combiner le résultat d'un autre comparateur.

4 bit magnitude comparator IEC symbol

A noter que ce genre de circuit peut être généralisé, à savoir que certains comparateurs complets sont conçus pour comparer plusieurs bits à la fois, et non seulement 2 : il suffit simplement d'écrire leur table de vérité et en déduire le circuit correspondant. Ces comparateurs possèdent évidemment une entrée sur laquelle envoyer les bits >, < et = des colonnes précédentes. Par exemple, supposons que nous voulons créer un comparateur pour nombres de 7/8 bits avec comparateurs de 4 bits. Pour cela, on doit comparer les bits par groupes de 4 et combiner les résultats de comparaison entre eux.

4 bit magnitude comparator extension

Comparateurs parallèles[modifier | modifier le wikicode]

Une autre solution est de faire les comparaisons en parallèle et de combiner les bits de résultats des différents comparateurs avec un dernier comparateur. On obtient alors un comparateur parallèle. Cela permet ainsi de créer des comparateurs capables de comparer des nombres de 4, 8, 16 bits entre eux.

Parallel Magnitude Comparator

Il est possible de combiner des comparateurs parallèles de plusieurs bits entre eux, en les plaçant en série. Pour cela, on peut envoyer les résultats sur les entrées normales, en faisant passer ces bits de résultats pour les bits des nombres à comparer. Une entrée pour chaque nombre est ainsi remplacée par les bits de supériorité ou d'infériorité fournit par le comparateur précédent.

Serial Magnitude Comparator

Comparateur pour nombres signés[modifier | modifier le wikicode]

Comparer deux nombres signés n'est pas la même chose que comparer deux nombres non-signés. Autant la comparaison d'égalité et de différence est strictement identique, autant les comparaisons de supériorité et d'égalité ne le sont pas. Les comparateurs pour nombres signés sont naturellement différents des comparateurs vus précédemment. On verra plus tard qu'il en est de même avec les comparateurs pour nombres flottants. Il fut aussi faire attention : 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. Dans ce qui va suivre, nous allons aborder la comparaison en signe-magnitude et en complément à deux, mais pas les autres représentations.

Comparateur signe-magnitude[modifier | modifier le wikicode]

Un comparateur en signe-magnitude n'est pas trop différent d'un comparateur normal. Effectuer une comparaison entre deux nombres en signe-magnitude demande de comparer les valeurs absolues, ainsi que comparer les signes. Une fois cela fait, il faut combiner les résultats de ces deux comparaisons en un seul résultat.

Comparateur en signe-magnitude

Comparer les signes[modifier | modifier le wikicode]

Comparer les signes est relativement simple : le circuit n'ayant que deux bits à comparer, celui-ci est naturellement simple à concevoir. On pourrait penser que l'on peut réutiliser le comparateur 1 bit vu précédemment dans ce chapitre, mais cela ne marcherait pas ! En effet, un nombre positif a un bit de signe nul alors qu'un nombre négatif a un bit de signe égal à 1 : les résultats sont inversés. Un bon moyen de s'en rendre compte est d'écrire la table de vérité de ce circuit, selon les signes des nombres à comparer. Nous allons supposer que ces deux nombres sont appelés A et B.

Signe de A Signe de B Bit de signe de A Bit de signe de B Sortie = Sortie < Sortie >
+ + 0 0 1 0 0
+ - 1 0 0 0 1
- + 0 1 0 1 0
- - 1 1 1 0 0

On obtient les équations suivantes :

On peut remarquer que si l bit d'égalité est identique au comparateur 1 bit vu plus haut, les bits de supériorité et l'infériorité sont inversés, échangés. On peut donc réutiliser le comparateur à 1 bit, mais en intervertissant les deux sorties de supériorité et d'infériorité.

Combiner les résultats[modifier | modifier le wikicode]

Une fois qu'on a le résultat de la comparaison des signes, on doit combiner ce résultat avec le résultat de la comparaison des valeurs absolues. Pour cela, on doit rajouter un circuit à la suite des deux comparateurs. On pourrait penser qu'il suffit d'établir la table de vérité de ce comparateur, mais il faut faire attention au cas où les deux opérandes sont nulles : dans ce cas, peut importe les signes, les deux opérandes sont égales. Pour le moment, mettons ce fait de coté et établissons la table de vérité du circuit. Dans tous les cas, 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. Cela devrait donner les équations suivantes. On note les résultats de la comparaison des bits de signe comme suit : , alors que les résultats de la comparaison des valeurs absolues sont notés : .

  • pour le résultat d'égalité ;
  • pour l’infériorité ;
  • pour la supériorité.

Néanmoins, il faut prendre en compte le cas où les deux opérandes sont nulles, ce qui complique un petit peu les équations Pour cela, il fat rajouter une sortie au comparateur de valeurs absolues, qui indique si les deux nombres valent tous deux zéro. Notons cette sortie . Les équations deviennent :

  • pour l'égalité ;
  • pour l’infériorité ;
  • pour la supériorité.

Comparateur en complément à un et en complément à deux[modifier | modifier le wikicode]

La comparaison en complément à un est relativement simple, si ce n'est un détail : il faut calculer les valeurs absolues avant de les comparer. Rien de plus simple pour cela : il suffit de regarder le bit de signe et d'inverser les bits du nombre s'il vaut 1 (nombre négatif). On peut remarquer que cette technique consiste à traduire les nombres vers une représentation signe-magnitude avant de les comparer avec le comparateur vu plus haut. Reste à calculer les valeurs absolues suivant la représentation. En complément à 1, il faut inverser tous les bits si le bit de signe est de 1, et ne rien faire sinon. On a vu dans les premiers chapitres du cours comment réaliser un inverseur commandable avec des portes XOR, aussi je ne reviendrait pas dessus. Ici, on peut juste réutiliser cet inverseur, et le commander avec l bit de signe de l'opérande. La comparaison en complément à deux est plus compliquée, compte tenu des spécificités de cet encodage. On pourrait parfaitement utiliser la méthode précédente : comparer les signes et les valeurs absolues, avant de combiner les résultats. Le seul problème est qu'il faut rajouter un circuit pour le calcul de la valeur absolue. Ce circuit est composé naturellement d'une couche de porte NON (un inverseur), ainsi que d'un circuit pour incrémenter le tout, le tout combiné à un MUX. Le problème est la conception du circuit incrémenteur, qui sera vue dans le prochain chapitre.

Circuit de comparaison en complément à 1 et à 2

Une autre solution consiste à soustraire les deux nombres et à regarder le bit de signe du résultat. S'il est négatif, la première opérande est inférieure. Si ce signe est positif, soit la première opérande est supérieure à l'autre, soit les deux opérandes sont égales. Le seul moyen pour départager les deux situations est de vérifier si le résultat obtenu est nul ou non. Mais cette méthode demande de concevoir un circuit de soustraction, chose que nous apprendrons à faire dans le chapitre suivant.

Comparateur en complément à 2