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

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

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. Le présent chapitre abordera des opérations qui ne sont pas arithmétiques (comprendre des additions, multiplications ou autres), et qui portent le nom d’opérations logiques. Les opérations logiques travaillent sur des suites de bits d'une longueur fixe, l'écriture binaire d'un nombre pour simplifier. Il en existe de deux types, les instructions bit à bit et les instructions de décalage/rotation, mais ce chapitre se concentre sur les opérations bit à bit.

Les opérations bit à bit appliquent un ET, OU, XOR ou NOT sur un ou deux nombres. La plus simple est clairement l'opération NOT, qui inverse tous les bits d'un nombre : les 0 deviennent des 1, et les 1 deviennent des 0. Mais il est aussi possible de prendre deux nombres, de faire un ET/OU/XOR entre les bits de même poids, et de renvoyer le tout en guise de résultat. Le résultat de ces opérations n'est pas vraiment interprétable mathématiquement, la seule exception tient dans l'opération NOT.

  • Pour un entier en complément à 1, le NOT sert à obtenir l'opposé d'un nombre : dit autrement, .
  • Pour un entier en complément à deux, le NOT donne l'opposé d'un nombre auquel on aurait retranché 1 : .
  • Pour un entier non-signé, le NOT va donner la valeur

Le premier point est une définition, c'est comme cela qu'on définit l'inverse d'un nombre en complément à un.

Le second point s'explique par le fait qu'en complément à deux, on a

Le dernier résultat est facile à comprendre quand on sait que la somme donne un nombre de n bits dont tous les bits sont à 1, égal par définition à .

Les circuits de mise à zéro/un/d'inversion[modifier | modifier le wikicode]

Dans ce qui suit, nous allons voir ce qui se passe quand on effectue un ET, un OU, ou un XOR sur tous les bits d'un nombre en même temps. Pour simplifier le tout, nous n’allons pas regarder ce qui se passe quand on fait un ET/OU/XOR entre deux nombres. À la place, nous allons faire un ET/OU/XOR entre une opérande quelconque et un nombre contenant entièrement des 0 ou entièrement des 1. En clair, on va faire un ET/OU/XOR avec un nombre de la forme 00000000...000 ou 11111111...111. Cela peut paraître assez simpliste, mais c'est quelque chose de très utile. De plus, cela permet de comprendre ce qu'il se passe dans le cas général.

Pour comprendre ce que font ces opérations, 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

Les circuits qui vont suivre appliquent la même opération entre tous les bits d'une opérande et un bit d'entrée. Le bit d'entrée indique si le nombre est égal à 00000000...000 ou 11111111...111. Il vaut 0 si le nombre est 00000000...000, et vaut 1 pour 11111111...111. En fait, le bit d'entrée est recopié en plusieurs exemplaires pour donner le nombre voulu. Ce qui fait qu'on peut simplement envoyer le bit d'entrée sur les portes ET/OU/XOR. Cela peut paraître compliqué, mais cela deviendra très clair quand nous verrons les schémas ci-dessous.

Le circuit de mise à zéro[modifier | modifier le wikicode]

Dans cette section, nous allons voir un circuit qui prend en entrée un nombre et le met à zéro si une condition est respectée. Pour le dire autrement, le circuit va soit recopier l'entrée telle quelle sur sa sortie, soit la mettre à zéro. Le choix entre les deux situations est réalisé par une entrée Reset de 1 bit : un 0 sur cette entrée met la sortie à zéro, un 1 signifie que l'entrée est recopiée en sortie. La porte ET est toute indiquée pour cela. La mise à zéro d'un bit d'entrée demande de faire un ET de celui-ci avec un 0, alors que recopier un bit d'entrée demande de faire un ET de celui-ci avec un 1. Il suffit d'envoyer le bit d'entrée sur les portes ET, comme illustré ci-dessous.

Circuit de mise à zéro

Le circuit de mise à la valeur maximale[modifier | modifier le wikicode]

Dans cette section, nous allons voir un circuit qui prend en entrée un nombre et met sa sortie à la valeur maximale si une condition est respectée. Pour le dire autrement, le circuit va soit recopier l'entrée telle quelle sur sa sortie, soit la mettre à 11111...111. Le choix entre les deux situations est réalisé par une entrée Set de 1 bit : un 1 sur cette entrée met la sortie à la valeur maximale, un 0 signifie que l'entrée est recopiée en sortie. La porte OU est toute indiquée pour cela. La mise à 1 d'un bit d'entrée demande de faire un OU de celui-ci avec un 1, alors que recopier un bit d'entrée demande de faire un OU de celui-ci avec un 0. Il suffit d'envoyer le bit d'entrée sur les portes ET, comme illustré ci-dessous.

Circuit de mise à 1111111...11

Ce circuit est utilisé pour gérer les débordements d'entier dans les circuits de calculs qui utilise l'arithmétique saturée (voir le chapitre sur le codage des entiers pour plus d'explications). Les circuits de calculs sont souvent suivis par ce circuit de mise à 111111...111, pour gérer le cas où le calcul déborde, afin de mettre la sortie à la valeur maximale. Évidemment, le circuit de calcul doit non seulement faire le calcul, mais aussi détecter les débordements d'entiers, afin de fournir le bit pour l'entrée Set.

L'inverseur commandable[modifier | modifier le wikicode]

Dans cette section, nous allons voir un inverseur commandable, un circuit qui, comme son nom l'indique, inverse les bits d'un nombre passé en entrée. Ce circuit inverse un nombre quand on lui demande et ne fait rien sinon. On précise au circuit s'il doit inverser ou non l'opérande d'entrée avec un bit de commande, souvent nommé Invert. Ce dernier vaut 1 si le circuit doit inverser l'opérande et 0 sinon. La porte XOR est toute indiquée pour, ce qui fait que le circuit d'inversion commandable est composé d'une couche de portes XOR, chaque porte ayant une entrée connectée au bit de commande.

Inverseur commandable par un bit.

Les circuits de masquage total/partiel[modifier | modifier le wikicode]

Les opérations de la section précédente appliquent un ET/OU/XOR entre une opérande et un bit. Maintenant, nous allons voir ce qu'il se passe quand on applique un ET/OU/XOR entre deux nombres. Le premier nombre sera appelé l'opérande et le second le masque. L'opération ET/OU/XOR sur l'opérande va soit recopier certains bits de l’opérande, soit les modifier. L'utilité est de modifier certains bits d'un nombre, en laissant les autres intacts. Les bits à modifier sont indiqués par le masque : chaque bit du masque indique s'il faut modifier ou laisser intact le bit correspondant dans l'opérande.

Le résultat dépend suivant que l'opération est un ET, un OU ou un XOR.

  • Le ET permet soit de recopier le bit d'entrée, soit de le mettre à 0. En clair, faire un ET entre l'opérande et le masque va mettre certains bits de l’opérande à 0 et va recopier les autres. Les bits mis à 0 sont ceux où le bit du masque correspondant est à 0, tandis que les autres sont recopiées tels quels. L'opérande est donc partiellement mise à 0 et les bits à mettre à 0 sont indiqués par le masque.
  • La même chose a lieu avec l'opération OU, sauf que cette fois-ci, les bits de l'opérande sont soit recopiés, soit mis à 1. Les bits mis à 1 sont ceux pour lesquels le bit du masque correspondant est un 1.
  • Dans le cas d'un XOR, les bits sont inversés. Les bits inversés sont ceux pour lesquels le bit du masque correspondant est un 1.
Inverseur commandable par un masque.

Exemples d'utilisation[modifier | modifier le wikicode]

Pour donner un exemple d'utilisation, supposons que j'ai regroupé plusieurs bits, dont chacun a une signification bien précise. Par exemple, je peux regrouper les droits d'accès dans un fichier dans un nombre : un des bits du nombre me dira alors si je peux écrire dans le fichier, un autre me dira si je peux le lire, un autre si… Bref, si jamais je veux modifier mes droits en écriture de mon fichier, je dois mettre un bit bien précis à 1 ou à 0 (suivant la situation). Cela peut se faire facilement en utilisant une instruction bit à bit entre ce nombre et une constante bien choisie.

Un autre cas typique est celui où un développeur compacte plusieurs données dans un seul entier. Par exemple, prenons le cas d'une date, exprimée sous la forme jour/mois/année. Un développeur normal stockera cette date dans trois entiers : un pour le jour, un pour le mois, et un pour la date. Mais un programmeur plus pointilleux sera capable d'utiliser un seul entier pour stocker le jour, le mois, et l'année. Pour cela, il raisonnera comme suit :

  • un mois comporte maximum 31 jours : on doit donc encoder tous les nombres compris entre 1 et 31, ce qui peut se faire en 5 bits ;
  • une année comporte 12 mois, ce qui tient dans 4 bits ;
  • et enfin, en supposant que l'on doive gérer les années depuis la naissance de Jésus jusqu'à l'année 2047, 11 bits peuvent suffire.

Dans ces conditions, notre développeur décidera d'utiliser un entier de 32 bits pour le stockage des dates :

  • les 5 bits de poids forts serviront à stocker le jour ;
  • les 4 bits suivant stockeront le mois ;
  • et les bits qui restent stockeront l'année.

Dans cette situation, le développeur qui souhaite modifier le jour ou le mois d'une date devra modifier une partie des bits, tout en laissant les autres intacts. Encore une fois, cela peut se faire facilement en utilisant une instruction bit à bit entre ce nombre et une constante bien choisie.