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

Un livre de Wikilivres.
Sauter à la navigation Sauter à 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 quelques 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. Ces opérations logiques travaillent sur des suites de bits d'une longueur fixe, des nombres pour simplifier. Ces opérations modifient directement l'écriture binaire d'un nombre, la suite de bits correspondante. Il en existe de deux types, les instructions bit à bit et les instructions de décalage, que nous allons voir l'une après l'autre. Pour les connaisseurs, nous allons voir quelques opérations iconiques, comme les décalages et les rotations, mais aussi comment concevoir une unité de calcul 2 à 3 bit, les masques et quelques autres opérations.

Décalages et rotations[modifier | modifier le wikicode]

Commencons par les circuits de décalage, qui décalent un nombre de un ou plusieurs rangs vers la gauche, ou la droite. Le nombre à décaler est envoyé sur une entrée du circuit, de même que le nombre de rangs l'est sur une autre. Le circuit fournit le nombre décalé sur sa sortie. Lorsqu'on décale un nombre, certains bits sont inconnus, ce qui laisse des vides dans le nombre. On peut les remplir avec des zéros, ce qui donne un décalage logique. Pour les décalages à droite, on peut aussi remplir les vides avec le bit de poids fort (on verra plus tard pourquoi dans le cours). On parle alors de décalage arithmétique. Il faut aussi signaler l'existence d'opérations de rotation, qui sont similaires aux décalages, mais qui font rentrer les bits sortis de l'autre côté.

Décalage logique. Décalage arithmétique. Rotations de bits.

L'utilité principale des opérations de décalage est qu'elles permettent de faire simplement des multiplications ou divisions par une puissance de 2. Ainsi, un décalage logique correspond à une multiplication ou division entière par 2^n, pour les entiers non signés. Cependant, lorsqu'on effectue un décalage à droite, certains bits vont sortir du résultat et être perdus : le résultat est tronqué ou arrondi vers zéro. Pour pouvoir effectuer des divisons par 2^n sur des nombres négatifs avec un décalage, on a inventé les décalages arithmétiques ou arithmetical shift. Ces instructions sont équivalentes à une multiplication/division par 2^n, que le nombre soit signé ou non. La différence avec un décalage logique est la méthode d'arrondi des nombres négatifs. Avec les décalages arithmétiques, les nombres négatifs sont arrondis vers moins l'infini. Pour donner un exemple, 92 sera arrondi en 4, tandis que −92 sera arrondi en −5.

Modulo et quotient d'une division par une puissance de deux en binaire

Décalages[modifier | modifier le wikicode]

Ces circuits sont fabriqués avec des multiplexeurs à deux entrées et une sortie. Nous allons voir comment créer un circuit capable de décaler un nombre vers la droite, d'un nombre de rangs variable : on pourra décaler notre nombre de 2 rangs, de 3 rangs, de 4 rangs, etc. Il faudra préciser le nombre de rangs sur une entrée. On peut faire une remarque simple : décaler vers la droite de 6 rangs, c'est équivalent à décaler notre nombre vers la droite de 4 rangs, et redécaler le tout de 2 rangs. Même chose pour 7 rangs : cela consiste à décaler de 4 rangs, redécaler de 2 rangs et enfin redécaler d'un rang. En suivant notre idée jusqu'au bout, on se rend compte qu'on peut créer un décaleur à partir de décaleurs plus simples, reliés en cascade, qu'on d'active ou désactive suivant le nombre de rangs. Le nombre de rangs par lequel on va devoir décaler est un nombre codé en binaire, qui s'écrit donc sous la forme d'une somme de puissances de deux. Chaque bit du nombre de rang servira à actionner le décaleur qui déplace d'un nombre égal à sa valeur (la puissance de deux qui correspond en binaire).

Décaleur logique - principe

Reste à savoir comment créer ces décaleurs qu'on peut activer ou désactiver à la demande. On va prendre comme exemple un décaleur par 4, mais ce que je vais dire peut être adapté pour créer des décaleurs par 1, par 2, par 8, etc. La sortie vaudra soit le nombre tel qu'il est passé en entrée (le décaleur est inactif), soit le nombre décalé de 4 rangs. Ainsi, si je prend un nombre A, composé des bits a7, a6, a5, a4, a3, a2, a1, a0 ; (cités dans l'ordre), le résultat sera :

  • soit le nombre composé des chiffres a7, a6, a5, a4, a3, a2, a1, a0 (on n'effectue pas de décalage) ;
  • soit le nombre composé des chiffres 0, 0, 0, 0, a7, a6, a5, a4 (on effectue un décalage par 4).

Chaque bit de sortie peut prendre deux valeurs, qui valent soit zéro, soit un bit du nombre d'entrée. On peut donc utiliser un multiplexeur pour choisir quel bit envoyer sur la sortie. Par exemple, pour le choix du bit de poids faible du résultat, celui-ci vaut soit a7, soit 0 : il suffit d’utiliser un multiplexeur prenant le bit a7 sur son entrée 1, et un 0 sur son entrée 0. Il suffit de faire la même chose pour tous les autres bits, et le tour est joué.

Exemple d'un décaleur par 4.

On peut modifier le schéma vu au-dessus pour lui permettre d'effectuer des décalages arithmétiques en plus des décalages logiques. Il suffit simplement d'ajouter un ou plusieurs multiplexeurs pour chaque décaleur élémentaire par 1, 2, 4, etc. Ces multiplexeurs choisissent quoi envoyer sur l'entrée de l'ancienne couche : soit un 0 (décalage logique), soit le bit de signe (décalage arithmétique).

Exemple avec un décaleur par 4.

Rotations[modifier | modifier le wikicode]

Et ce qui peut être fait pour le décalage arithmétique peut aussi l'être pour les rotations. On peut transformer notre circuit en circuit encore plus généraliste, capable de faire des rotations en plus des décalages en rajoutant quelques multiplexeurs pour choisir les bits à envoyer sur les entrées des décaleurs. Par exemple, on peut rajouter une couche de multiplexeurs pour faire en sorte que notre décaleurs par 4 puisse faire à la fois des décalages par 4 et des rotations par 4. Pour cela, il suffit de choisir quoi mettre sur les 4 bits de poids fort. Si c'est un décalage par 4, notre circuit devra mettre ces bits de poids fort à 0, tandis qu'il devra recopier les 4 bits de poids faible si c'est une rotation. Pour choisir entre un zéro ou le bit voulu du nombre d'entrée, il suffit de rajouter des multiplexeurs. Bien évidemment, on peut faire la même chose pour les rotateurs par 2, 1 , etc. Et ainsi obtenir de quoi effectuer des rotations en plus des décalages.

Circuit de rotation partiel.

Barell shifter[modifier | modifier le wikicode]

Avec tout ce qui a été dit plus haut, on est donc arrivé à créer un circuit capable d'effectuer aussi bien des rotations que des décalages : ce fameux circuit s'appelle un barrel shifter, et est utilisé dans certains processeurs modernes, dans une version un peu plus améliorée. Il existe d'autres types de Barrel shifter qu'on a pas évoqués dans ce chapitre : ce sont les Mask Barrel Shifters.

Opérations bits à bit[modifier | modifier le wikicode]

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. 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. Formellement, ce sont les seuls types d'opérations bits à bit : l'inversion des bits d'un nombre, un ET entre deux nombres, un OU entre deux nombres, et un XOR entre deux nombres (avec leurs dérivées, tel un NAND ou un NOR). Ces opérations sont plus simples à implémenter que les décalages : elles ne nécessitent qu'une couche de portes logiques, pas plus. Leur résultat n'est pas vraiment interprétable mathématiquement, ou alors avec un sens vraiment idiosyncratique. La seule exception tient dans l'opération NOT et dans le XOR. Les autres opérations, à savoir le ET, le OU, et leurs consœurs, n'ont pas d'interprétation mathématique simple. Cependant, elles sont assez utiles dans certaines circonstances, comme nous allons le voir de suite.

L'inversion bit à bit va inverser tous les bits d'un nombre : Les 0 deviennent des 1, et les 1 deviennent des 0. Le résultat de cette opération dépend de l'encodage du nombre. Plus précisément, l'interprétation du résultat n'est pas la même selon que le nombre inversé soit non-signé, en complément à 1, en complément à 2, etc.

  • 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 dernier résultat est facile à comprendre. On sait que la somme donne un nombre de n bits dont tous les bits sont à 1. Un tel nombre vaut exactement, par définition, . On a donc , ce qui donne le résultat précédent avec quelques manipulations algébriques triviales.

Circuit de calcul bit à bit[modifier | modifier le wikicode]

Il faut noter qu'il est possible de créer un circuit qui est capable de faire toutes ces opérations à la fois, et de sélectionner le résultat à envoyer sur sa sortie. Ce circuit 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, ce circuit contient une entrée qui indique quelle est l'opération à effectuer, chaque opération étant codée par un nombre.

Dans ce qui va suivre, nous allons créer un circuit qui effectue toutes les opérations bit à bit possible avec deux bits. Divers théorèmes de l’algèbre de Boole nous disent que ces opérations sont au nombre de 16. Les traditionnels ET, OU, XOR, NAND, NOR et NXOR sont bien sûr comptés dans ces 16 opérations. 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 quelque 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
Unité de calcul bit à bit de 2 bits, capable d'effectuer toute opération bit à bit.

On pourrait alors penser que concevoir ce circuit serait quelque chose d'assez complexe. Il faudrait notamment attribuer un nombre à chaque opération, et réécrire la table de vérité en tenant compte de cette nouvelle entrée. Mais grâce à une astuce particulièrement intelligente, il n'en est rien. Regardez le tableau ci-dessus : vous voyez que chaque colonne forme une suite de bits, qui peut être interprétée comme un nombre. Et bien nous allons attribuer ce nombre à l'opération de la colonne ! En faisant ainsi, le nombre attribué à chaque opération contient tout 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 !

Il faut noter que le raisonnement peut se généraliser avec 3, 4, 5 bits, voire plus ! Et cela a déjà été utilisé sur de vrais ordinateurs. Par exemple, l'unité de calcul bit à bit de la CIM machine était un circuit identique à celui vu plus haut, si ce n'est qu'il gérait en plus un troisième bit d'opérande, et contenait un registre pour prendre en charge des retenues d'un calcul à un autre.

Il est possible d'utiliser les opérations bit à bit dans un grand nombre de situations, certes assez atypiques pour ce qui est du logiciel. En architecture des ordinateurs, de telles situations sont cependant plus fréquentes, et méritent d'être mentionnées.

Les masques[modifier | modifier le wikicode]

Dans ce qui va suivre, nous allons voir comment modifier un bit dans un nombre, sans toucher aux autres. 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.

L'opération OU bit à bit[modifier | modifier le wikicode]

Tout d'abord, nous allons voir comment mettre à 1 un bit dans un nombre. Pour cela, nous allons utiliser une opération bit à bit entre le nombre en question, et un nombre appelé masque qui indique les bits à mettre à 1. Si le bit du masque est à 0, cela signifie que le bit du nombre, situé à la même place, ne doit pas être modifié. Mais si le bit du masque est à 1, le bit du nombre devra être mis à 1. Par exemple, pour modifier le 4éme bit d'un nombre en partant de la droite, le masque est une constante dont le 4éme bit en partant de la droite est 1, et le reste des bits est à 0, soit la constante : 000000001000.

Nous allons devoir trouver quelle opération bit à bit convient. Rien de compliqué au demeurant : il suffit d'écrire la table de vérité de cette opération et de reconnaitre la porte logique.

Nombre Masque Résultat
0 0 0
0 1 1
1 0 1
1 1 1

On remarque que l’opération bit à bit à effectuer est un OU.

L'opération ET bit à bit[modifier | modifier le wikicode]

Mettre un bit à 0 dans un nombre fonctionne sur le même principe que mettre un bit à 1 : on effectue une opération bit à bit entre le nombre en question et un masque qui indique quels bits mettre à 0. Encore une fois, écrire la table de vérité de l'opération nous donne l'opération bit à bit à effectuer. Il s’avère que c'est un ET bit à bit.

Nombre Masque Résultat
0 0 0
0 1 0
1 0 0
1 1 1

On peut se demander à quoi peut bien servir de mettre à 0 certains bits. L'utilité première est d'accéder à un bit particulier dans un nombre, ou à des groupes de bits. Un cas classique est celui de la sélection du bit de signe, pour calibrer certaines opérations arithmétiques. Dans ce cas, on va mettre à zéro les bits inutiles avant d'effectuer un décalage pour caler ces bits à droite.

L'opération XOR bit à bit[modifier | modifier le wikicode]

Le même raisonnement que pour les deux opérations précédentes vaut aussi pour ce qui est de l'inversion d'un bit. On obtient alors l'opération XOR à partir de la table de vérité.

Nombre Masque Résultat
0 0 0
0 1 1
1 0 1
1 1 0