Fonctionnement d'un ordinateur/Les circuits de calcul logique et bit à bit

Un livre de Wikilivres.

Dans ce chapitre et les suivants, nous allons voir comment implémenter sous forme de circuits certaines opérations extrêmement courantes dans un ordinateur. Les quelques circuits que nous allons voir seront réutilisés massivement dans les chapitres qui suivront, aussi nous allons passer quelque temps sur ces bases. Pour simplifier, les opérations réalisées par un ordinateur se classent en trois types :

  • Les opérations arithmétiques, à savoir les additions, multiplications et autres, qui auront chacune leur propre chapitre.
  • Les décalages et rotations, où on décale tous les bits d'un nombre d'un ou plusieurs crans vers la gauche/droite, qui feront l'objet d'un futur chapitre.
  • Les opérations logiques qui font l'objet de ce chapitre.

Les opérations logiques manipulent entre une et deux opérandes. Il n'y en a qu'une seule qui agit sur une opérande. C'est l'opération NON, aussi appelée NOT, qui inverse tous les bits d'un nombre. Les autres opérations effectuent un ET/OU/XOR entre deux nombres. A savoir qu'elles font un ET/OU/XOR entre les deux bits de même poids des deux opérandes.

Les portes logiques universelles commandables[modifier | modifier le wikicode]

Dans cette section, nous allons voir comment créer un circuit qui regroupe toutes les portes logiques en une seule. L'idée est de créer un circuit qui peut effectuer un ET/OU/XOR et toutes les autres opérations, et l'on peut choisir quelle opération réaliser grâce à une entrée de commande.

Par exemple, imaginons un circuit un peu plus limité, capable de faire à la fois un ET, un OU, un XOR et un NXOR. Le circuit contiendra une entrée de commande de 2 bits, et la valeur sur cette entrée permet de sélectionner quelle opération faire : 00 pour un ET, 01 pour un OU, 11 pour un XOR, 01 pour le NXOR.

Nous allons créer un tel circuit, sauf qu'il est capable de faire toutes les opérations entre deux bits et regroupe donc les 16 portes logiques existantes. Nous allons aussi voir la même chose, mais pour les portes logiques de 1 bit.

La porte logique universelle à entrée 1-bit[modifier | modifier le wikicode]

Pour commencer, nous allons voir des circuits qui modifient un bit d'entrée. Il y a quatre opérations possibles : recopier le bit d'entrée, inverser le bit d'entrée, le mettre à 0, le mettre à 1.

Avec cette liste, on peut déjà avoir l'idée d'une première solution, qui se base sur un circuit multiplexeur. L'idée est de placer le bit d'entrée sur la première entrée du MUX, le bit inversé par une porte NON sur la seconde entrée, un 1 sur la troisième, et un 0 sur la quatrième. Il suffit alors d'attribuer les valeurs adéquates sur l'entrée de commande : 00 = OUI, 01 = NON, 10 = Set, 11 = Reset. Cela demande cependant d'utiliser un MUX 4 vers 2, ce qui est beaucoup pour un simple porte logique universelle.

Porte logique universelle de 1 bit

Mais il y a une solution plus simple, qui demande de combiner plusieurs circuits plus simples.

Les circuits commandables de reset/set/inversion[modifier | modifier le wikicode]

Pour comprendre comment concevoir ces circuits, il faut rappeler les relations suivantes, qui donnent le résultat d'un ET/OU/XOR entre un bit quelconque noté a et un bit qui vaut 0 ou 1.

Opération Interprétation du résultat
Porte ET Mise à zéro du bit d'entrée
Recopie du bit d'entrée
Porte OU Mise à 1 du bit d'entrée
Recopie du bit d'entrée
Porte XOR Recopie du bit d'entrée
Inversion du bit d'entrée

Avec cela, on peut créer trois circuits assez simples : un circuit qui inverse le bit d'entrée à la demande, un autre qui le met à 1, un autre qui le met à 0. Ces trois circuits ont une entrée de commande qui détermine s'il faut faire l'opération. Le circuit recopie le bit d'entrée si cette entrée est à 0, mais il inverse/set/reset le bit d'entrée si elle est à 1.

Le circuit de mise à 1 commandable est une porte simple OU.

Le circuit d’inversion commandable est une simple porte XOR.

Le circuit de Reset, qui permet de mettre à zéro un bit si besoin, est légèrement plus compliqué. Le circuit prend entrée le bit d'entrée, puis un bit de commande qui indique s'il faut mettre à zéro le bit d'entrée ou non. Le bit de commande en question est appelé le bit Reset. Si le signal Reset est à 1, alors on met à zéro le bit d'entrée, mais on le laisse intact sinon. Le tableau ci-dessus nous dit que la porte ET est tout adaptée : elle recopie le bit d'entrée si l'autre opérande vaut 1, et elle le met à 0 si l'autre opérande vaut 0. La seule différence avec le circuit qu'on veut est que la seconde opérande est l'exact inverse du signal Reste voulu, ce qui signifie qu'on doit ajouter une porte NON. Le tout donne le circuit ci-dessous.

Circuit de mise à zéro d'un bit

Le circuit final de la porte logique universelle de 1 bit[modifier | modifier le wikicode]

Il nous reste maintenant à combiner ces circuits pour obtenir le circuit voulu. Pour cela, il suffit de placer les trois portes logiques ET/OU/XOR en série, l'une après l'autre. Le problème est qu'il faut préciser la seconde opérande pour chacune des trois portes, alors que l'entrée de commande faire 2 bits. Il faut alors ajouter un circuit combinatoire sur l'entrée de commande pour commander la seconde opérande des trois portes. Tout dépend alors des choix fait pour les valeurs de l'entrée de commande.

Porte logique universelle de 1 bit, faite avec trois portes

Mais il y a moyen de se passer d'une porte logique ! On peut se passer de la porte ET pour mettre à 0 le bit d'entrée, ou de celle pour le mettre à 1. L'idée est que mettre à 0 et mettre à 1 sont deux opérations inverses l'une de l'autre, et l'on a déjà une porte spécialement dans l'inversion. Il suffit donc de mettre la XOR pour inverser le bit d'entrée à la fin du circuit. Juste avant, on place la porte pour mettre à 0 le bit d'entrée : mettre à 1 revient à mettre à 0 dans la porte ET, puis à inverser le résultat. On peut faire la même chose, mais en mettant une porte OU à la place de la porte ET : la porte OU met à 1, et la porte XOR peut inverser si besoin pour mettre à 0. En faisant comme cela, il ne reste que deux portes logiques, donc deux entrées. En choisissant bien les valeurs sur l'entrée de commande, on peut connecter les entrées de commande directement sur les opérandes des deux portes, sans passer par un circuit combinatoire.

Porte logique universelle de 1 bit, faite avec deux portes

La porte universelle commandable 2-bit[modifier | modifier le wikicode]

Sachez qu'avec un simple multiplexeur, on peut créer un circuit qui effectue toutes les opérations bit à bit possible avec deux bits. Et cela a déjà été utilisé sur de vrais ordinateurs. Pour deux bits, divers théorèmes de l’algèbre de Boole nous disent que ces opérations sont au nombre de 16, ce qui inclus les traditionnels ET, OU, XOR, NAND, NOR et NXOR. Voici la liste complète de ces opérations, avec leur table de vérité ci-dessous (le nom des opérations n'est pas indiqué) :

  • Les opérateurs nommés 0 et 1, qui renvoient systématiquement 0 ou 1 quel que soit l'entrée ;
  • L'opérateur OUI qui recopie l'entrée a ou b, et l'opérateur NON qui l'inverse : , , ,  ;
  • L’opérateur ET, avec éventuellement une négation des opérandes : , , ,  ;
  • La même chose avec l’opérateur OU : , , ,  ;
  • Et enfin les opérateurs XOR et NXOR : , .
a b
0 0 - 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1
0 1 - 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1
1 0 - 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1
1 1 - 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1

Le circuit à concevoir prend deux bits, que nous noterons a et b, et fournit sur sa sortie : soit a ET b, soit a OU b, soit a XOR b, etc. Pour sélectionner l'opération, une entrée du circuit indique quelle est l'opération à effectuer, chaque opération étant codée par un nombre. On pourrait penser que concevoir ce circuit serait assez complexe, mais il n'en est rien grâce à une astuce particulièrement intelligente. Regardez le tableau ci-dessus : vous voyez que chaque colonne forme une suite de bits, qui peut être interprétée comme un nombre. Il suffit d'attribuer ce nombre à l'opération de la colonne ! En faisant ainsi, le nombre attribué à chaque opération contient tous les résultats de celle-ci. Il suffit de sélectionner le bon bit parmi ce nombre pour obtenir le résultat. Et on peut faire cela avec un simple multiplexeur, comme indiqué dans le schéma ci-dessous !

Unité de calcul bit à bit de 2 bits, capable d'effectuer toute opération bit à bit.

Il faut noter que le raisonnement peut se généraliser avec 3, 4, 5 bits, voire plus ! Par exemple, il est possible d'implémenter toutes les opérations bit à bit possibles entre trois bits en utilisant un multiplexeur 8 vers 3.

Les unités de calcul logique[modifier | modifier le wikicode]

Maintenant que nous sommes armés des portes logiques universelles, nous pouvons implémenter un circuit généraliste, qui peut effectuer la même opération logique sur tous les bits. Ce circuit est appelé une unité de calcul logique. Elle prend en entrée deux opérandes, ainsi qu'une entrée de commande sur laquelle on précise quelle opération il faut faire.

Elle est simplement composée d'autant de portes universelles 2 bits qu'il n'y a de bits dans les deux opérandes. Par exemple, si on veut un circuit qui manipule des opérandes 8 bits, il faut prendre 8 portes universelles deux bits. Toutes les entrées de commande des portes sont reliées à la même entrée de commande.

Unité de calcul bit à bit de 4 bits, capable d'effectuer toute opération bit à bit

Les opérations FFS, FFZ, CTO et CLO[modifier | modifier le wikicode]

Dans cette section, nous allons aborder plusieurs opérations fortement liées entre elles, illustrées dans le schéma ci-dessous. Elles sont très courantes sur la plupart des ordinateurs, surtout dans les ordinateurs embarqués. Beaucoup d'ordinateurs, comme les anciens mac avec des processeurs type Power PC et les processeurs MIPS ou RISC ont des instructions pour effectuer ces opérations.

Mais avant de passer aux explications, un peu de terminologie utile. Dans ce qui suit, nous aurons à utiliser des expressions du type "le 1 de poids faible", "les 0 de poids faible" et quelques autres du même genre. Quand nous parlerons du 0 de poids faible, nous voudrons parler du premier 0 que l'on croise dans un nombre en partant de sa droite. Par exemple, dans le nombre 0011 1011, le 0 de poids faible est le troisième bit en partant de la droite. Quand nous parlerons du 1 de poids faible, c'est la même chose, mais pour le premier bit à 1. Par exemple, dans le nombre 0110 1000, le 1 de poids faible est le quatrième bit. Quant aux expressions "le 1 de poids fort" et "les 0 de poids fort" elles sont identiques aux précédentes, sauf qu'on parcourt le nombre à partir de sa gauche.

Par contre, les expressions "LES 1 de poids faible" ou "LES 0 de poids faible" ne parlent pas de la même chose. Quand nous voudrons parler des 1 de poids faible, au pluriel, nous voulons dire : tous les bits situés avant le 0 de poids faible. Par exemple, prenons le nombre 0011 0011 : les 1 de poids faible correspondent ici aux deux premiers bits en partant de la droite. Même chose quand on parle des zéros de poids faible au pluriel. Quant aux expressions "les 1 de poids fort" ou "les 0 de poids fort" elles sont identiques aux précédentes, sauf qu'on parcourt le nombre à partir de sa gauche.

Les opérations bit à bit complexes[modifier | modifier le wikicode]

La première opération que nous allons aborder, Find First Set, donne la position du 1 de poids faible. Cette opération est liée à l'opération Count Trailing Zeros, qui donne le nombre de zéros situés à droite de ce 1 de poids faible. L'opération Find First Set est opposée au calcul du Find highest set, qui donne la position du 1 de poids fort. Le nombre de zéros situés à gauche de ce bit à 1 est appelé le Count Leading Zeros.

Ces quatre opérations ont leur équivalents en remplaçant les 0 par des 1 et réciproquement. Par exemple, l'opération Find First Zero donne la position du 0 de poids faible (le plus à droite) et l'opération Find Highest Zero donne la position du 0 de poids fort (le plus à gauche). L'opération Count Trailing Ones donnent le nombre de 1 situés à gauche du 0 de poids fort, tandis que l'opération Count Leading Ones donne le nombre de 1 situés à droite du 0 de poids faible.

Opérations Find First Set ; Find First Zero ; Find Highest Set (le logarithme binaire) ; Find Highest Zero ; Count Leading Zeros ; Count Trailing Zeros ; Count Leading Ones et Count Trailing Ones.

La numérotation des bits et l'équivalence de certaines opérations[modifier | modifier le wikicode]

Dans toutes ces opérations, les bits sont numérotés, leur numéro étant appelé leur position ou leur indice. La position d'un bit est donc donnée par ce numéro. Ces opérations varient selon la méthode utilisée pour numéroter les bits. On peut commencer à compter les bits à partir de 0, le 0 étant le numéro du bit de poids faible. Mais on peut aussi compter à partir de 1, le bit de poids faible étant celui de numéro 1. Ces deux conventions ne sont pas équivalentes. Si on choisit la première convention, certaines opérations sont équivalentes. Par exemple, les opérations Count Trailing Zeros et Find First Set donnent toutes les deux le même résultat. Avec l'autre convention, les deux différent de 1 systématiquement.

Avec la première convention, pour un nombre codé sur bits, on a :

On voit que certaines opérations sont équivalentes, ce qui nous arrange bien. De plus, on peut calculer le résultat de l'opération FHS à partir de l'opération CLZ et réciproquement. De même le résultat de FHZ peut se calculer à partir du résultat de CLO et inversement. Il suffit d'effectuer une simple soustraction, avec une constante qui plus est, ce qui est simple à fabriquer. Ce qui revient à ajouter un circuit pour faire le calcul .

De fait, nous n'aurons qu'à aborder quatre calculs :

  • le Find First Set, abréviée FFS ;
  • le Find highest set, abrévié FHS ;
  • le Find First Zero, abréviée FFZ ;
  • le Find highest Zero, abrévié FHZ.

On peut même aller plus loin et éliminer encore plus le nombre d'opérations différentes à effectuer. En effet, les opérations FHS et FHZ peuvent se déduire l'une de l'autre, en changeant le nombre passé en entrée. Pour cela, il suffit d'inverser les bits de l'entrée, avec un inverseur commandable. Avec l'inversion, le 1 de poids fort deviendra le 0 de poids fort et inversement. Idem pour les opérations FFS et FFZ. En inversant l'entrée, le 1 de poids faible deviendra le 0 de poids faible et inversement.

Circuit qui effectue les opérations FHS, FFS, CLZ et autres.

L'encodeur à priorité[modifier | modifier le wikicode]

Reste à voir comment effectuer les deux opérations restantes, à savoir Find Highest Set et Find First Set. Et pour cela, nous devons utiliser un encodeur à priorité. Dans le cas le plus fréquent, l'encodeur à priorité prend en entrée un nombre et donne la position du 1 de poids fort. Ces encodeurs à priorité réalisent l'opération Find Highest Set, qui est reliée à l’opération count leading zeros. Ce qui leur vaut le nom anglais de leading zero detector (LZD) ou encore de leading zero counter (LZC). Mais dans d'autres cas, l'encodeur à priorité donne la position du 1 de poids faible, ce qui correspond à l'opération Count Trailing Zeros. Il existe aussi des encodeurs qui donnent la position du zéro de poids faible, voire du zéro de poids fort, ce qui correspond respectivement aux opérations Find First Zero et Find highest Zero. En clair, pour les quatre opérations précédentes, il existe un encodeur à priorité qui s'en charge.