Fonctionnement d'un ordinateur/Les circuits de calcul

Un livre de Wikilivres.
Aller à : navigation, rechercher

Tout circuit de calcul peut être conçu les méthodes vues au chapitre précédent. Mais les circuits de calcul actuels manipulent des nombres de 32 bits, ce qui demanderait des tables de vérité démesurément grandes : plus de 4 milliards de lignes ! Il faut donc ruser, pour créer des circuits économes en transistors et rapides. C'est le but de ce chapitre : voir comment sont réalisés les circuits de calcul.

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

On va commencer 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 soit avec des zéros, ce qui donne un décalage logique. Mais 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é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.

Addition non signée[modifier | modifier le wikicode]

Voyons maintenant un circuit capable d'additionner deux nombres : l'additionneur. Dans la version qu'on va voir, ce circuit manipulera des nombres strictement positifs ou des nombres codés en complètement à deux, ou en complément à un.

Additionneur 2 et 3 bits[modifier | modifier le wikicode]

Tout additionneur est composé d'additionneurs plus simples, capables d'additionner deux ou trois bits suivant la situation. Un additionneur deux bits implémente la table d'addition, qui est très simple en binaire :

  • 0 + 0 = 0 ;
  • 0 + 1 = 1 ;
  • 1 + 0 = 1 ;
  • 1 + 1 = 0, plus une retenue.

Un circuit capable d'additionner deux bits est donc simple à construire avec les techniques vues dans les premiers chapitres. Ce circuit est appelé un demi-additionneur. Le voici :

Cependant, il ne faut pas oublier qu'additionner deux nombres peut aussi faire intervenir des retenues, qu'il faut ajouter aux deux bits à additionner. Pour additionner cette retenue, il faut donc créer un circuit qui additionne trois bits : deux bits de données plus une retenue. Ce circuit qui additionne trois bits est appelé un additionneur complet. On peut le construire à partir de deux demi-additionneur, en combinant les sorties de retenue avec une porte OU.

Il est possible de créer des additionneurs différents, qui seront utilisés dans ce qui suit. Ceux-ci ne calculent pas directement la retenue, mais précisent si l'addition de deux bits génère une retenue, ou si elle propage une retenue provenant d'une colonne précédente. Dans certains cas, l'addition de deux bits a et b donne une retenue, quelle que soit la retenue envoyée en entrée (sous-entendu, même si celle-ci vaut 0) : on dit que l'addition génère une retenue. Cela arrive quand les bits additionnés valent tous deux 1. Dans d'autres cas, la retenue n'existe que si on envoie une retenue en entrée : on dit alors que l'addition propage la retenue. Cela arrive quand un des deux bits vaut 1, mais pas forcément l'autre. Nous pouvons créer un circuit qui indique si d'addition de deux bits génère ou propage une retenue : ce circuit a besoin de deux sorties P et G pour indiquer s'il y a propagation et génération de retenue. Un tel additionneur est appelé un additionneur P/G (P/G pour propagation/génération).

Additionneur série[modifier | modifier le wikicode]

Avec un additionneur complet, il est possible d'additionner deux nombres bit par bit. Dit autrement, on peut effectuer l'addition colonne par colonne. Cela demande de coupler l'additionneur avec plusieurs registres à décalages. Les opérandes vont être placées chacune dans un registre à décalage, afin de passer à chaque cycle d'un bit au suivant, d'une colonne à la suivante. Même chose pour le résultat. La retenue de l'addition est stockée dans une bascule de 1 bit, en attente du prochain cycle d'horloge. Un tel additionneur est appelé un additionneur série.

Additionneur série.

Bien que très simple, cet additionneur est cependant peu performant. Le temps de calcul est proportionnel à la taille des opérandes. Par exemple, additionner deux nombres de 32 bits prendra deux fois plus de temps que l'addition de deux nombres de 16 bits. L'addition étant une opération fréquente, il vaut mieux utiliser d'autres méthodes d'addition, plus rapides. C'est pour cela que la totalité des autres additionneurs préfère utiliser plus de circuits, quitte à gagner quelque peu en rapidité.

Additionneur à propagation de retenue[modifier | modifier le wikicode]

L'additionneur à propagation de retenue pose l'addition comme en décimal, en additionnant les bits colonne par colonne avec une éventuelle retenue. Évidemment, on commence par les bits les plus à droite, comme en décimal. Pour additionner les chiffres sur une colonne, on utilise notre connaissance de la table d’addition. Il suffit ainsi de câbler des additionneurs complets les uns à la suite des autres. Notez la présence de l’entrée de retenue C. Presque tous les additionneurs de notre ordinateur on une entrée de retenue comme celle-ci, afin de faciliter l'implémentation de certaines opérations comme l'inversion de signe, l'incrémentation, etc.

Additionneur à propagation de retenue.

Ce circuit est plus rapide que l'additionneur série. En effet, l'additionneur à propagation de retenue va additionner les bits des opérandes en parallèle, toutes ces additions ayant lieu en même temps. Par contre, le calcul des retenues s'effectue en série, l'une après l'autre. En effet, chaque additionneur doit attendre que la retenue de l'addition précédente soit disponible pour donner son résultat. Les retenues doivent se propager à travers le circuit, du premier additionneur jusqu'au dernier. On garde donc un défaut de l'additionneur série, à savoir : le fait que le temps de calcul est proportionnel à la taille des opérandes. Pour éviter cela, les autres additionneurs utilisent diverses solutions : soit calculer les retenues en parallèle, soit éliminer certaines opérations inutiles quand c'est possible.

Additionneur à saut de retenue[modifier | modifier le wikicode]

L'additionneur à saut de retenue (carry-skip adder), améliore les performances de l'additionneur à propagation de retenue. Celui-ci a cependant un défaut : le temps de calcul dépend des nombres à additionner : certains calculs prendront quelques cycles d'horloges, tandis que d'autres prendront autant de temps qu'avec un additionneur à propagation de retenue.

Cet additionneur se construit à partir de plusieurs additionneurs de quelques bits (4 à 5 bits, parfois plus, parfois moins), additionneurs qui seront nommés blocs dans ce qui suit. Chaque bloc peut soit générer une retenue, soit propager celle du bloc précédent, soit ne pas fournir de retenue (celle-ci vaut 0). Si le bloc génère une retenue ou qu'il n'en fournit pas, le fonctionnement du circuit est identique à un additionneur à propagation de retenue. Par contre, si le bloc ne fait que propager la retenue du bloc précédent, on peut directement envoyer cette retenue au bloc suivant. Pour cela, on utilise un multiplexeur pour décider s'il faut envoyer la retenue calculée par le bloc ou celle du bloc précédent. Ce multiplexeur est commandé par un signal qui indique si le bloc propage la retenue, signal qui est généré assez simplement : il vaut 1 si tous les additionneurs P/G du bloc propagent la retenue précédente.

Additionneur à saut de retenue.

En enchainant plusieurs blocs les uns à la suite des autres, on obtient l'additionneur à saut de retenue.

BCSAdder16Bit

Additionneur à sélection de retenue[modifier | modifier le wikicode]

L'additionneur à sélection de retenue adapte le principe précédent, mais d'une autre manière. Cet additionneur va découper nos deux nombres à additionner en blocs, qui se feront additionner en deux versions : une avec la retenue du bloc précédent valant zéro, et une autre version avec la retenue du bloc précédent valant 1. Il suffira alors de choisir le bon résultat avec un multiplexeur, une fois cette retenue connue. On gagne ainsi du temps en calculant à l'avance les valeurs de certains bits du résultat, sans connaitre la valeur de la retenue. Petit détail : sur certains additionneurs à sélection de retenue, les blocs de base n'ont pas la même taille. Cela permet de tenir compte des temps de propagation des retenues entre les blocs.

Additionneur à sélection de retenue avec seulement deux blocs.

Dans les exemples du dessus, chaque sous-additionneur étaient des additionneurs à propagation de retenue. Mais ce n'est pas une obligation, et tout autre type d’additionneur peut être utilisé. Par exemple, on peut faire en sorte que les sous-additionneurs soient eux-mêmes des additionneurs à sélection de retenue, et poursuivre ainsi de suite, récursivement. On obtient alors un additionneur à somme conditionnelle, plus rapide que l'additionneur à sélection de retenue, mais qui utilise beaucoup plus de portes logiques.

Additionneurs à anticipation de retenue[modifier | modifier le wikicode]

Au lieu de calculer les retenues une par une, certains additionneurs calculent toutes les retenues en parallèle à partir de la valeur de tout ou partie des bits précédents. Une fois les retenues pré-calculées, il suffit de les additionner avec les deux bits adéquats, pour obtenir le résultat. Ces additionneurs sont appelés des additionneurs à anticipation de retenue.

Additionneur à anticipation de retenue.

Ces additionneurs sont composés de deux parties :

  • un circuit qui pré-calcule la valeur de la retenue d'un étage ;
  • et d'un circuit qui additionne les deux bits et la retenue pré-calculée : il s'agit d'une couche d'additionneurs complets simplifiés, qui ne fournissent pas de retenue.
Additionneur à anticipation de retenue.

Le circuit qui détermine la valeur de la retenue est lui-même composé de deux grandes parties, qui ont chacune leur utilité. La première partie réutilise des additionneurs qui donnent les signaux de propagation et génération de retenue. L'additionneur commence donc à prendre forme, et est composé de trois parties :

  • un circuit qui crée les signaux P et G ;
  • un circuit qui déduit la retenue à partir des signaux P et G adéquats ;
  • et une couche d'additionneurs qui additionnent chacun deux bits et une retenue.
Circuit complet d'un additionneur à anticipation de retenue.

Il ne nous reste plus qu'à voir comment fabriquer le circuit qui reste. Pour cela, il faut remarquer que la retenue est égale :

  • à 1 si l'addition des deux bits génère une retenue ;
  • à 1 si l'addition des deux bits propage une retenue ;
  • à zéro sinon.

Ainsi, l'addition des bits de rangs i va produire une retenue Ci, qui est égale à Gi+(Pi·Ci−1). Si on utilisait cette formule sans trop réfléchir, on retomberait sur un additionneur à propagation de retenue inutilement compliqué. L'astuce des additionneurs à anticipation de retenue consiste à remplacer le terme Ci−1 par sa valeur calculée avant. Par exemple, je prends un additionneur 4 bits. Je dispose de deux nombres A et B, contenant chacun 4 bits : A3, A2, A1, et A0 pour le nombre A, et B3, B2, B1, et B0 pour le nombre B. Si j'effectue les remplacements, j'obtiens les formules suivantes :

  • C1 = G0 + ( P0 · C0 ) ;
  • C2 = G1 + ( P1 · G0 ) + ( P1 · P0 · C0 ) ;
  • C3 = G2 + ( P2 · G1 ) + ( P2 · P1 · G0 ) + ( P2 · P1 · P0 · C0 ) ;
  • C4 = G3 + ( P3 · G2 ) + ( P3 · P2 · G1 ) + ( P3 · P2 · P1 · G0 ) + ( P3 · P2 · P1 · P0 · C0 ).

Ces formules nous permettent de déduire la valeur d'une retenue directement : il reste alors à créer un circuit qui implémente ces formules, et le tour est joué. On peut même simplifier le tout en fusionnant les deux couches d'additionneurs.

Additionneur à anticipation de retenue de 4 bits.

Ces additionneurs sont plus rapides que les additionneurs à propagation de retenue. Ceci dit, utiliser un additionneur à anticipation de retenue sur des nombres très grands (16/32bits) utiliserait trop de portes logiques. Pour éviter tout problème, nos additionneurs à anticipation de retenue sont souvent découpés en blocs, avec soit une anticipation de retenue entre les blocs et une propagation de retenue dans les blocs, soit l'inverse.

64-bit lookahead carry unit

Additionneur à calcul parallèle de préfixes[modifier | modifier le wikicode]

Les additionneurs à calcul parallèle de préfixes sont des additionneurs à anticipation de retenue quelque peu améliorés, pour gagner en performances. Ceux-ci sont toujours découpés en trois couches :

  • un circuit qui crée les signaux P et G ;
  • un circuit qui déduit la retenue à partir des signaux P et G adéquats ;
  • et une couche d'additionneurs qui additionnent chacun deux bits et une retenue.

Simplement, ils vont concevoir le circuit de calcul des retenues différemment. Avec eux, le calcul Gi + (Pi · Ci−1) va être modifié pour prendre en entrée non pas la retenue Ci−1, mais les signaux Gi−1 et Pi−1. Dans ce qui va suivre, nous allons noter ce petit calcul o. On peut ainsi écrire que :

Ci = ((((Gi , Pi) o (Gi−1 , Pi−1) ) o (Gi−2 , Pi−2 )) o (Gi−3 , Pi−3)) …

Si on utilisait cette formule sans trop réfléchir, on retomberait sur un additionneur à propagation de retenue inutilement compliqué. Le truc, c'est que o est associatif, et que cela peut permettre de créer pas mal d'optimisations : il suffit de réorganiser les parenthèses. Cette réorganisation peut se faire de diverses manières qui donnent des additionneurs différents :

  • l'additionneur de Ladner-Fisher ;
  • l'additionneur de Brent-Kung ;
  • l'additionneur de Kogge-Stone ;
  • ou tout design hybride.

L'additionneur de Brent-Kung est le plus lent de tous les additionneurs cités, mais c'est celui qui utilise le moins de portes logiques. L'additionneur de Ladner-Fisher est théoriquement le plus rapide de tous, mais aussi celui qui utilise le plus de portes logiques. Les autres sont des intermédiaires.

Annexe finale : les débordements d'entier[modifier | modifier le wikicode]

Les instructions arithmétiques et quelques autres manipulent des entiers de taille fixe, qui ne peuvent prendre leurs valeurs que dans un intervalle. Si le résultat d'un calcul sort de cet intervalle, il ne peut pas être représenté par l'ordinateur : il se produit ce qu'on appelle un débordement d'entier. Et quand un débordement d'entier a eu lieu, il vaut mieux que le circuit prévienne ! Pour cela, les additionneurs comportent une sortie nommée Overflow, dont la valeur indique si le calcul a donné un débordement d'entier ou non. Il en est de même pour les autres circuits de calcul, comme on le verra plus tard. Toujours est-il que pour les additionneurs vus précédemment, cette sortie a la même valeur que la retenue finale, celle fournie par le dernier additionneur complet.

Addition multiopérande[modifier | modifier le wikicode]

Après avoir vu comment additionner deux nombres, il est temps de voir comment faire la même chose avec plus de deux nombres. Il existe de nombreux types de circuits capables d'effectuer cette addition multiopérande, construits à partir d'additionneurs simples.

Additionneur multi-opérandes itératif[modifier | modifier le wikicode]

Le plus simple des additionneur multi-opérandes est similaire à l'additionneur série vu plus haut. Sauf que cette fois-ci, il n'additionne pas deux opérandes bit par bit, mais additionneur plusieurs opérandes une par une. Cet additionneur est composé d'un additionneur entier, tel que vu précédemment, couplé à un registre. Ce circuit additionne les opérandes une par une, le résultat temporaire étant stocké dans le registre. Ce circuit est appelé un additionneur multi-opérande itératif.

Additionneur multi-operande itératif.

Chainage d'additionneurs[modifier | modifier le wikicode]

La solution la plus simple consiste à additionner les nombres les uns après les autres, soit avec un circuit séquentiel, soit en enchainant des additionneurs les uns à la suite des autre. Mais diverses optimisations sont possibles. La solution la plus simple consiste à enchainer des additionner les uns après les autres. Mais cela n'est pas la meilleur solution. Le mieux est de les organiser en arbre pour effectuer certaines additions en parallèle d'autres : on obtient alors un arbre d'additionneur.

Adding

Additionneurs carry-save[modifier | modifier le wikicode]

Les additionneurs carry-save se basent sur une nouvelle représentation des nombres, particulièrement adaptée aux additions successives : la représentation carry-save. Avec l'addition carry-save, on ne propage pas les retenues. L'addition de trois bits en carry-save fournit deux résultats : un résultat obtenu en effectuant l'addition sans tenir compte des retenues, et un autre composé uniquement des retenues. Par exemple, 1000 + 1010 + 1110 donne 1010 pour les retenues, et 1100 pour la somme sans retenue.

Carry save (addition)

Ainsi, additionner trois nombres devient très facile : il suffit d'additionner les trois nombres avec un additionneur carry-save, et d'additionner les deux résultats avec un additionneur normal. Le même principe peut s'appliquer avec plus de trois nombres : il suffit juste d'assembler plusieurs additionneurs carry-save les uns à la suite des autres.

Additionneur carry-save.

Chainage d'additionneurs en arbre[modifier | modifier le wikicode]

Il est possible d'utiliser ces additionneurs carry-save dans un arbre d'additionneurs. En faisant cela, on peut se retrouver avec plusieurs formes pour l'arbre, qui donnent respectivement des additionneurs en arbres de Wallace, ou des arbres Dadda.

Les arbres les plus simples à construire sont les arbres de Wallace. Le principe est d'ajouter des couches d'additionneurs carry-save, et de capturer un maximum de nombres lors de l'ajout de chaque couche. On commence par additionner un maximum de nombres avec des additionneurs carry-save. Pour additionner n nombres, on commence par utiliser n/3 additionneurs carry-save. Si jamais n n'est pas divisible par 3, on laisse tranquille les 1 ou 2 nombres restants. On se retrouve ainsi avec une couche d'additionneurs carry-save. On répète cette étape sur les sorties des additionneurs ainsi ajoutés : on rajoute une nouvelle couche. Il suffit de répéter cette étape jusqu'à ce qu'il ne reste plus que deux résultats : on se retrouve avec une couche finale composée d'un seul additionneur carry-save. Là, on rajoute un additionneur normal, pour additionner retenues et sommes.

Arbre de Wallace pour l'addition de 8 nombres de 8 bits.

Les arbres de Dadda sont plus difficiles à comprendre. Contrairement à l'arbre de Wallace qui cherche à réduire la hauteur de l'arbre le plus vite possible, l'arbre de Dadda cherche à diminuer le nombre d'additionneurs carry-save utilisés. Pour cela, l'arbre de Dadda se base sur un principe mathématique simple : un additionneur carry-save peut additionner trois nombres, pas plus. Cela implique que l'utilisation d'un arbre de Wallace gaspille des additionneurs si on additionne n nombres, avec n non multiple de trois. L'arbre de Dadda résout ce problème d'une manière simple :

  • si n est multiple de trois, on ajoute une couche complète d'additionneurs carry-save ;
  • si n n'est pas multiple de trois, on ajoute seulement 1 ou 2 additionneur carry-save : le but est de faire en sorte que la couche suivante fournisse un nombre d'opérandes multiple de trois.

Et on répète cette étape d'ajout de couche jusqu'à ce qu'il ne reste plus que deux résultats : on se retrouve avec une couche finale composée d'un seul additionneur carry-save. Là, on rajoute un additionneur normal, pour additionner retenues et sommes.

Arbre de Dadda pour l'addition de 8 nombres de 8 bits.

Soustraction et addition signée[modifier | modifier le wikicode]

Si on sait câbler une addition entre entiers positifs, câbler une soustraction n'est pas très compliqué. On va commencer par un circuit capable de soustraire deux nombres représentés en complément à deux ou en complément à un.

Nombres entiers[modifier | modifier le wikicode]

Pour soustraire deux nombres entiers, on peut adapter l'algorithme e soustraction utilisé en décimal, celui que vous avez appris à l'école. Celui-ci ressemble fortement à l'algorithme d'addition : on soustrait les bits de même poids, et on propage éventuellement une retenue sur la colonne suivante. La différence est que la retenue est soustraite, et non ajoutée. La table de soustraction nous dit quel est le résultat de la soustraction de deux bits. La voici :

  • 0 - 0 = 0 ;
  • 0 - 1 = 1 et une retenue ;
  • 1 - 0 = 1 ;
  • 1 - 1 = 0.

Cette table de soustraction peut servir directement de table de vérité pour construire un circuit qui soustrait deux bits. Celui-ci est appelé un demi-soustracteur.

Half subtractor corrected

Celui-ci peut être complété afin de prendre en compte une éventuelle retenue, ce qui donne un soustracteur complet.

FullSubtractor

Celui-ci permet de créer des soustracteurs sur le même patron que pour les additionneurs. On peut ainsi créer un soustracteur série, un soustracteur à propagation de retenue, et ainsi de suite.

Complément à deux[modifier | modifier le wikicode]

Vous savez surement que a−b et a+(−b) sont deux expressions équivalentes. Et en complément à deux, − b = not(b) + 1. Dit autrement, a − b = a + not(b) + 1. On pourrait se dire qu'il faut deux additionneurs pour faire le calcul, mais la majorité des additionneurs possède une entrée de retenue pour incrémenter le résultat de l'addition.

Soustracteur en complément à deux.

Il est possible de créer un circuit capable d'effectuer soit une addition, soit une soustraction : il suffit de remplacer l'inverseur par un inverseur commandable, qui peut être désactivé. On a vu comment créer un tel inverseur commandable dans le chapitre sur les circuits combinatoires. On peut remarquer que l'entrée de retenue et l'entrée de commande de l'inverseur sont activées en même temps : on peut fusionner les deux signaux en un seul.

Additionneur-soustracteur en complément à deux.
Additionneur-soustracteur en complément à deux, version alternative.

Signe-valeur absolue[modifier | modifier le wikicode]

Passons maintenant aux nombres codés en signe-valeur absolue. On remarque que B − A est égal à − (A − B), et − A − B vaut − (A + B). Ainsi, le circuit n'a besoin que de calculer A + B et A − B : il peut les inverser pour obtenir − A − B ou B − A. A + B et A − B peuvent se calculer avec un additionneur-soustracteur, auquel on ajoute un inverseur commandable. On peut transformer ce circuit en additionneur-soustracteur en signe-valeur absolue, mais le circuit combinatoire devient plus complexe.

Additionneur en signe-valeur absolue.

Représentation par excès[modifier | modifier le wikicode]

Passons maintenant aux nombres codés en représentation par excès. On pourrait croire que ces nombres s'additionnent comme des nombres non-signés, mais ce serait oublier la présence du biais, qui pose problème. Dans les cas de nombres signés gérés avec un biais, voyons ce que donne l'addition de deux nombres : . Or, le résultat correct serait . En effectuant l'addition telle quelle, le biais est compté deux fois. On doit donc le soustraire après l'addition pour obtenir le résultat correct. Même chose pour la soustraction . Or, le résultat correct serait . Il faut rajouter le biais pour obtenir l'exposant correct. On a donc besoin de deux additionneurs/soustracteurs pour implémenter la multiplication et la division. Ainsi, l'additionneur/soustracteur en représentation par excès est composé de deux additionneurs/soustracteurs : un pour additionner/soustraire les nombres, et un autre pour gérer le biais.

Annexe : les débordements d'entier[modifier | modifier le wikicode]

La gestion des débordements d'entiers dépend fortement de la représentation signée. Dans les grandes lignes, rien ne change avec les représentations en signe-magnitude et par excés. Par contre, il n'en est pas de même pour le complément à deux. Si vous vous rappelez le chapitre 1, j'ai clairement dit que les calculs sur des nombres en complètement à deux utilisent les règles de l'arithmétique modulaire : les calculs sont faits avec un nombre de bits fixé une fois pour toute. Si un résultat dépasse ce nombre de bits fixé, on ne conserve pas les bits en trop. C'est une condition nécessaire pour pouvoir faire nos calculs. A priori, on peut donc penser que dans ces conditions, les débordements d'entiers sont une chose parfaitement normale, qui nous permet d'avoir des résultats corrects. Néanmoins, certains débordements d'entiers peuvent arriver et produire des bugs assez ennuyeux.

Si l'on tient en compte les règles du complément à deux, on sait que le bit de poids fort (le plus à gauche) permet de déterminer si le nombre est positif ou négatif : il indique le signe du nombre. Tout se passe comme si les entiers en complément à deux étaient codés sur un bit de moins, et avaient leur longueur amputé du bit de poids fort. Si le résultat d'un calcul a besoin d'un bit de plus que cette longueur, amputée du bit de poids fort, le bit de poids fort sera écrasé; donnant un débordements d'entiers. Il existe une règle simple qui permet de détecter ces débordements d'entiers. L'addition (ou la multiplication) de deux nombres positifs ne peut pas être un nombre négatif : on additionne deux nombres dont le bit de signe est à 0 et que le bit de signe du résultat est à 1, on est certain d'être en face d'un débordements d'entiers. Même chose pour deux nombres négatif : le résultat de l'addition ne peut pas être positif. On peut résumer cela en une phrase : si deux nombres de même signe sont ajoutés, un débordement a lieu quand le bit du signe du résultat a le signe opposé. On peut préciser que cette règle s'applique aussi pour les nombres codés en complément à 1, pour les mêmes raisons que pour le codage en complément à deux. Cette règle est aussi valable pour d'autres opérations, comme les multiplications.

Modifier les circuits d'au-dessus pour qu'ils détectent les débordements en complément à deux est simple comme bonjour : il suffit créer un petit circuit combinatoire qui prenne en entrée les bits de signe des opérandes et du résultat, et qui fasse le calcul de l'indicateur de débordements. Si l'on rédige sa table de vérité, on doit se retrouver avec la table suivante :

Entrées Sortie
000 0
001 1
010 0
011 0
100 0
101 0
110 1
111 0

L'équation de ce circuit est la suivante, avec et les signes des deux opérandes, et la retenue de la colonne précédente :

En simplifiant, on obtient alors :

Or, il se trouve que est tout simplement la retenue en sortie du dernier additionneur, que nous noterons . On trouve donc :

Il suffit donc de faire un XOR entre la dernière retenue et la précédente pour obtenir le bit de débordement.

Multiplication[modifier | modifier le wikicode]

Nous allons maintenant aborder la multiplication, effectuée par un circuit : le multiplieur. Pour commencer, petite précision de vocabulaire : une multiplication s'effectue sur deux nombres, le multiplicande et le multiplicateur.

Circuits itératifs[modifier | modifier le wikicode]

Comme pour l'addition, nous allons multiplier en binaire de la même façon qu'on a appris à le faire en primaire, si ce n'est que la table de multiplication est modifiée. Une multiplication génère des résultats temporaires, chacun provenant de la multiplication du multiplicande par un chiffre du multiplicateur, auquel on aura appliqué un décalage : ces résultats temporaires sont appelés des produits partiels. Multiplier deux nombres en binaire demande de générer les produits partiels avant de les additionner.

Et si les additionneurs multiopérandes permettent de faire l'addition des produits partiels, il ne manque plus qu'à les générer. Pour multiplier un nombre par un bit du multiplicateur, rien de plus simple : les tables de multiplication sont vraiment très simples en binaire, jugez plutôt !

  • 0 × 0 = 0.
  • 0 × 1 = 0.
  • 1 × 0 = 0.
  • 1 × 1 = 1.

Cette table de vérité est celle d'une porte ET. Ainsi, notre circuit est donc très simple : il suffit d'effectuer un ET entre les bits du multiplicande, et le bit du multiplicateur adéquat. Il reste ensuite à faire un décalage (et encore, on peut s'en passer avec quelques optimisations), et le tour est joué.

Les multiplieurs les plus simples génèrent les produits partiels les uns après les autres, et les additionnent au fur et à mesure. Le multiplicateur et le multiplicande sont mémorisés dans des registres. Le reste du circuit est composé d'un circuit de génération des produits partiels, suivi d'un additionneur multiopérande itératif. La multiplication est finie quand tous les bits du multiplicateur ont étés traités (ce qui peut se détermine avec un compteur). Il existe plusieurs multiplieurs itératifs, qui différent par la façon dont ils génèrent le produit partiel : certains traitent les bits du multiplicateur de droite à gauche, les autres dans le sens inverse. Dans les deux cas, on décale le multiplicateur d'un cran à chaque cycle, et on prend son bit de poids faible. Pour cela, on stocke le multiplicateur dans un registre à décalage.

Circuit itératif de multiplication sans optimisation.

On peut remarquer une chose assez intéressante : si le produit partiel est nul, pourquoi l'additionner ? Ainsi, si le bit du multiplicateur qui génère le produit partiel est 0, le produit partiel sera nul : on peut se passer de l'addition et ne faire que les décalages.

On peut encore optimiser le circuit en utilisant des produits partiels sur n bits. Pour cela, on fait le calcul en commençant par les bits de poids fort du multiplicateur : on parcourt le multiplicateur de droite à gauche au lieu le faire de gauche à droite. L'astuce, c'est qu'on additionne le produit partiel avec les bits de poids fort du registre pour le résultat, et non les bits de poids faible. Le contenu du registre est décalé d'un cran à droite à chaque cycle, ce qui décale automatiquement les produits partiels comme il faut.

Circuit itératif de multiplication, avec optimisation de la taille des produits partiels.

Il est même possible de ruser encore plus : on peut se passer du registre pour le multiplicateur. Il suffit d'initialiser les bits de poids faible du registre résultat avec le multiplicateur au démarrage de la multiplication. Le bit du multiplicateur choisi pour le calcul du produit partiel est simplement le bit de poids faible du résultat.

Multiplieur partagé

Il est possible d'optimiser les multiplieurs précédents en calculant et en additionnant plusieurs produits partiels à la fois. Il suffit d'un additionneur multi-opérande et de plusieurs circuits de génération de produits partiels. Toutefois, cette technique demande de prendre en compte plusieurs bits du multiplicateur à chaque cycle : le nombre de rangs à décaler augmente, sans compter que la génération du produit partiel est un peu plus complexe.

Multiplieur à base d’additionneur multi-opérandes non-itératif[modifier | modifier le wikicode]

Une autre solution consiste à calculer tous les produits partiels en parallèle, en même temps, avant de les additionner avec un additionneur multi-opérandes non-itératif.

Dans sa version la plus simple, l'additionneur multi-opérandes utilisé est un additionneur séquentiel, composé d’additionneur deux-opérandes enchainés les uns à la suite des autres. Dans sa version la plus simple, on peut utiliser des additionneurs à propagation de retenue pour créer le multiplieur. Utiliser d'autres additionneurs ne donnerait que des gains en performance relativement faibles. On peut aussi enchainer des additionneurs carry-save à trois opérandes pour additionner les produits partiels, les performances étant alors marginalement meilleures.

Enchainer les additionneurs les uns à la suite des autres n'est cependant pas la meilleur solution. Le mieux est d'utiliser un additionneur multiopérande en arbre.

Multiplieurs diviser pour régner[modifier | modifier le wikicode]

Il existe enfin un tout dernier type de multiplieurs : les multiplieurs diviser pour régner. Pour comprendre le principe, nous allons prendre un multiplieur qui multiplie deux nombres de 32 bits. Les deux opérandes A et B peuvent être décomposées en deux morceaux de 16 bits, qu'il suffit de multiplier entre eux pour obtenir les produits partiels voulus : une seule multiplication 32 bits se transforme en quatre multiplications d'opérandes de 16 bits. En clair, ces multiplieurs sont composés de multiplieurs qui travaillent sur des opérandes plus petites, associés à des additionneurs.

Multiplieur par une constante[modifier | modifier le wikicode]

Les opérations de multiplication entière sont gourmandes en temps d’exécution et en portes logiques : toute optimisation est bonne à prendre. La multiplication par une constante est une opportunité d'optimisation importante. Il est possible de simplifier la conception d'un multiplieur, si celui-ci doit multiplier par une constante. On a vu précédemment qu'il est possible de remplacer la multiplication par une puissance de deux par un simple décalage. Ce qui va suivre se baser sur ce principe, même si nous allons aborder la multiplication par autre chose qu'une puissance de deux. Aussi bizarre que cela puisse paraitre, il y a deux méthodes pour cela. Suivant la situation, l'une d'entre elle sera plus rapide que l'autre : tout dépend du nombre de bits à 1 dans la constante.

Décaler et additionner[modifier | modifier le wikicode]

Comme vous le savez, tout nombre entier est une somme de multiple de puissance de deux. C'est d'ailleurs le principe qui est derrière le binaire. Dans ce cas, multiplier par une puissance, c'est multiplier par une somme de puissance de deux. Avec quelques manipulations algébriques simple, cette multiplication peut se transformer en une somme de multiplication par une puissance de deux. Supposons que je veuille effectuer une multiplication entre un nombre A, et une constante B. Il est évident que B est une somme de puissances de deux. Dans ce cas, je peux remplacer B par la somme de puissance de deux qui correspond. Dans ce qui va suivre, nous allons prendre B = 5. Pour rappel,  :

Comme on le sait tous, la multiplication est distributive. J'utilise cette propriété sur l'équation du dessus, et je trouve :

Dans cette expression, on a donc une somme, qui additionne quelques termes. Ces termes sont tous des multiplications par une puissance de deux. On peut les remplacer par un décalage vers la gauche.

Ainsi, la multiplication par 5 peut se remplacer en un décalage à gauche de 2 rangs, et une addition.

Le principe reste le même pour toute multiplication par une constante : en décomposant la constante en puissance de deux, et avec quelques calculs, on peut transformer une multiplication par une constante en série de décalages et d'additions. Le nombre de décalages effectué est égal au nombre de bits à 1 dans la constante (sa population count). Le nombre d'addition est presque identique. Si la constante contient donc trop de bits à 1, il se peut que le nombre de décalage et d'addition soit trop important : une multiplication peut être plus rapide. Cette technique ne marche donc que pour les nombres ayant une population count faible : 2-3 bits, parfois plus sur les architectures ayant une multiplication particulièrement lente. Mais pas plus.

Décaler et soustraire[modifier | modifier le wikicode]

Dans le cas où un nombre contient beaucoup de bits à 1, il existe une seconde méthode. Elle se base sur un principe légèrement différent, mais assez similaire à celui utilisé dans la méthode précédente. Comme vous le savez, un nombre entier peut s'écrire sous la forme d'une somme de puissance de deux. Par exemple, . Ceci dit, 5 peut aussi s'écrire sous une autre forme. Si on remarque bien, . Dans cette expression, 8 est une puissance de 2, et 3 est un nombre comme un autre. Si on réfléchit bien, tout nombre entier peut s'écrire sous la forme .

Reprenons notre exemple avec le 5.

Dans cette expression, on peut remplacer chaque nombre par son expression en binaire. En clair, on le remplace par la somme de puissances de deux qui correspond.

Maintenant, supposons que l'on veuille multiplier un nombre A par 5. On peut alors remplacer 5 par l'expression avec décalages et soustractions :

En se rappelant que la multiplication est distributive, on obtient :

Dans cette expression, on peut alors remplacer les multiplication par des puissances de deux par des décalages à gauche :

Comme on le voit, cette expression ne contient que des décalages et des soustractions. Et le principe est le même pour tout entier. Il suffit d'écrire la constante comme une puissance de deux à laquelle on aurait soustrait ce qu'il faut. Pour cela, il suffit de prendre la puissance de deux immédiatement supérieure à notre constante : cela simplifie les calculs et diminue le nombre de soustractions.

Multiplication signée[modifier | modifier le wikicode]

Tous les circuits qu'on a vus plus haut sont capables de multiplier des nombres entiers positifs, mais on peut les adapter pour qu'ils fassent des calculs sur des entiers signés. Pour les entiers en signe-valeur absolue, il suffit de multiplier les valeurs absolues et de déduire le signe du résultat avec un vulgaire XOR entre les bits de signe des nombres à multiplier. Dans ce qui va suivre, nous allons nous intéresser à la multiplication signée en complément à deux.

Les multiplieurs vus plus haut fonctionnent parfaitement quand les deux opérandes ont le même signe, mais pas quand un des deux opérandes est négatif. Avec un multiplicande négatif, le produit partiel est censé être négatif. Mais dans les multiplieurs vus plus haut, les bits inconnus du produit partiel sont remplis avec des zéros, et donc positifs. Pour résoudre ce problème, il suffit d'utiliser une extension de signe sur les produits partiels. Pour cela, il faut faire en sorte que le décalage du résultat soit un décalage arithmétique. Pour traiter les multiplicateurs négatifs, on ne doit pas ajouter le produit partiel, mais le soustraire (l'explication du pourquoi est assez dure à comprendre, aussi je vous épargne les détails). L'additionneur doit donc être remplacé par un additionneur-soustracteur.

Multiplieur pour entiers signés

Multiplieurs de Booth[modifier | modifier le wikicode]

Il existe une autre façon, nettement plus élégante, inventée par un chercheur en cristallographie du nom de Booth : l'algorithme de Booth. Le principe de cet algorithme est que des suites de bits à 1 consécutives dans l'écriture binaire d'un nombre entier peuvent donner lieu à des simplifications. Si vous vous rappelez, les nombres de la forme 01111…111 sont des nombres qui valent 2n − 1. Donc, X × (2^n − 1) = (X × 2^n) − X. Cela se calcule avec un décalage (multiplication par 2^n) et une soustraction. Ce principe peut s'appliquer aux suites de 1 consécutifs dans un nombre entier, avec quelques modifications. Prenons un nombre composé d'une suite de 1 qui commence au n-ième bit, et qui termine au X-ième bit : celle-ci forme un nombre qui vaut 2^n − 2^n−x. Par exemple, 0011 1100 = 0011 1111 − 0000 0011, ce qui donne (2^7 − 1) − (2^2 − 1). Au lieu de faire des séries d'additions de produits partiels et de décalages, on peut remplacer le tout par des décalages et des soustractions.

C'est le principe qui se cache derrière l’algorithme de Booth : il regarde le bit du multiplicateur à traiter et celui qui précède, pour déterminer s'il faut soustraire, additionner, ou ne rien faire. Si les deux bits valent zéro, alors pas besoin de soustraire : le produit partiel vaut zéro. Si les deux bits valent 1, alors c'est que l'on est au beau milieu d'une suite de 1 consécutifs, et qu'il n'y a pas besoin de soustraire. Par contre, si ces deux bits valent 01 ou 10, alors on est au bord d'une suite de 1 consécutifs, et l'on doit soustraire ou additionner. Si les deux bits valent 10 alors c'est qu'on est au début d'une suite de 1 consécutifs : on doit soustraire le multiplicande multiplié par 2^n-x. Si les deux bits valent 01, alors on est à la fin d'une suite de bits, et on doit additionner le multiplicande multiplié par 2^n. On peut remarquer que si le registre utilisé pour le résultat décale vers la droite, il n'y a pas besoin de faire la multiplication par la puissance de deux : se contenter d’additionner ou de soustraire le multiplicande suffit.

Reste qu'il y a un problème pour le bit de poids faible : quel est le bit précédent ? Pour cela, le multiplicateur est stocké dans un registre qui contient un bit de plus qu'il n'en faut. On remarque que pour obtenir un bon résultat, ce bit précédent doit mis à 0. Le multiplicateur est placé dans les bits de poids fort, tandis que le bit de poids faible est mis à zéro. Cet algorithme gère les signes convenablement. Le cas où le multiplicande est négatif est géré par le fait que le registre du résultat subit un décalage arithmétique vers la droite à chaque cycle. La gestion du multiplicateur négatif est plus complexe à comprendre mathématiquement, mais je peux vous certifier que cet algorithme gère convenablement ce cas.

Division[modifier | modifier le wikicode]

En binaire, l'opération de division ressemble beaucoup à l’opération de multiplication. L'algorithme le plus simple que l'on puisse créer pour exécuter une division consiste à faire la division exactement comme en décimal. Pour simplifier, la méthode de division est identique à celle de la multiplication, si ce n'est que les additions sont remplacées par des soustractions.

Division en binaire.

Division avec restauration[modifier | modifier le wikicode]

Néanmoins, implémenter cet algorithme sous la forme de circuit est quelque peu compliqué. Il existe plusieurs méthodes de division matérielle, la première étant la division avec restauration. Introduisons la par un exemple. Nous allons cherche à diviser 100011001111 (2255 en décimal) par 111 (7 en décimal). Pour commencer, nous allons commencer par sélectionner le bit de poids fort du dividende (le nombre qu'on veut diviser par le diviseur), et voir combien de fois on trouve le diviseur dans ce bit. Pour ce faire, on soustraire le diviseur à ce bit, et voir le signe du résultat. Si le résultat de cette soustraction est négatif, alors le diviseur est plus grand que ce qu'on a sélectionné dans notre dividende. On place alors un zéro dans le quotient. Dans notre exemple, cela fait zéro : on pose donc un zéro dans le quotient. Ensuite, on abaisse le bit juste à coté du bit qu'on vient de tester, et on recommence. On continue ainsi tant que le résultat de la soustraction obtenue est négatif. Quand le résultat de la soustraction n'est pas négatif, on met un 1 à la droite du quotient, et on recommence en partant du reste. Et on continue ainsi de suite.

Division avec restauration.

Notre algorithme semble se dessiner peu à peu : on voir qu'on devra utiliser des décalages et des soustractions, ainsi que des comparaisons. L'implémentation de cet algorithme dans un circuit est super simple : il suffit de prendre trois registres : un pour conserver le "reste partiel" (ce qui reste une fois qu'on a soustrait le diviseur dans chaque étape), un pour le quotient, et un pour le diviseur. L'ensemble est secondé par un additionneur/soustracteur, et par un peu de logique combinatoire. Voici ce que cela donne sur un schéma (la logique combinatoire est omise).

Circuit de division.

L'algorithme de division se déroule assez simplement. Tout d'abord, on initialise les registres, avec le registre du reste partiel qui est initialisé avec le dividende. Ensuite, on soustrait le diviseur de ce "reste" et on stocke le résultat dans le registre qui stocke le reste. Deux cas de figure se présentent alors : le reste partiel est négatif ou positif. Dans les deux cas, on réussit trouver le signe du reste partiel en regardant simplement le bit de signe du résultat. Reste à savoir quoi faire.

  • Le résultat est négatif : cela signifie que le reste est plus petit que le diviseur et qu'on aurait pas du soustraire. Vu que notre soustraction a été effectuée par erreur, on doit remettre le reste tel qu'il était. Ce qui est fait en effectuant une addition. Il faut aussi mettre le bit de poids faible du quotient à zéro et le décaler d'un rang vers la gauche.
  • Le résultat est positif : dans ce cas, on met le bit de poids faible du quotient à 1 avant de le décaler, sans compter qu'il faut décaler le reste partiel pour mettre le diviseur à la bonne place (sous le reste partiel) lors des soustractions.

Et on continue ainsi de suite jusqu'à ce que le reste partiel soit inférieur au diviseur.

Division sans restauration[modifier | modifier le wikicode]

La méthode précédente a toutefois un léger défaut : on a besoin de remettre le reste comme il faut lorsqu'on a soustrait le diviseur du reste alors qu'on aurait pas du et que le résultat obtenu est négatif. On fait cela en rajoutant le diviseur au reste. Et il y a moyen de se passer de cette restauration du reste partiel à son état originel. On peut très bien continuer de calculer avec ce reste faux, pour ensuite modifier le quotient final obtenu de façon simple, pour obtenir le bon résultat. Il suffit simplement de multiplier le quotient par deux, et d'ajouter 1. Ça parait vraiment bizarre, mais c'est ainsi. Cette méthode consistant à ne pas restaurer le reste comme il faut et simplement bidouiller le quotient s'appelle la division sans restauration.

La division SRT[modifier | modifier le wikicode]

On peut encore améliorer cette méthode en ne traitant pas notre dividende bit par bit, mais en le manipulant par groupe de deux, trois, quatre bits, voire plus encore. Ce principe est (en partie) à la base de l'algorithme de division SRT. C'est cette méthode qui est utilisée dans les circuits de notre processeur pour la division entière. Sur certains processeurs, le résultat de la division de deux groupes de bits est pré-calculé et stocké dans une petite mémoire : pas besoin de le recalculer à chaque fois avec un circuits, il suffit juste de lire cette mémoire, ce qui va beaucoup plus vite ! Pour information, on peut signaler que sur les processeurs les plus récents à l'heure où j'écris ce tutoriel, on peut traiter au maximum 4 bits à la fois. C'est notamment le cas sur les processeurs Core 2 duo.

Bien sûr, il faut faire attention quand on remplit cette mémoire : si vous oubliez certaines possibilités ou que vous y mettez des résultats erronés, vous obtiendrez un quotient faux pour votre division. Et si vous croyez que les constructeurs de processeurs n'ont jamais fait cette erreur, vous vous trompez : cela arrive même aux meilleurs ! Intel en a d'ailleurs fait les frais sur le Pentium 1. L'unité en charge des divisions flottantes utilisait un algorithme similaire à celui vu au-dessus (les mantisses des nombres flottants étaient divisées ainsi), et la mémoire qui permettait de calculer les bits du quotient contenait quelques valeurs fausses. Résultat : certaines divisions donnaient des résultats incorrects !

Comparateurs[modifier | modifier le wikicode]

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.

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 complet[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. Aux deux entrées, on peut ajouter une troisième entrée, qui permet de combiner le résultat d'un autre comparateur. Celle-ci est cependant facultative.

4 bit magnitude comparator IEC symbol

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 0 1 0
0 1 1 0 0
1 0 0 0 1
1 1 0 1 0

D'après sa table de vérité, 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é.

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

Autres opérations[modifier | modifier le wikicode]

Les opérations bit à bit permettent d'effectuer certains calculs arithmétiques assez simplement et souvent avec des performances très intéressantes. Dans ces conditions, effectuer des calculs arithmétiques avec des opérations bit à bit est un bon investissement. Dans ce qui va suivre, nous allons évidemment travailler avec des nombres en complément à deux.

Moyenne[modifier | modifier le wikicode]

Calculer la moyenne de deux nombres peut sembler simple comme bonjour. Il suffit d'appliquer la formule . Mais cette expression peut donner lieu à un débordement d'entier : le calcul de x + y peut dépasser la taille d'un registre, ce qui donnera un résultat totalement faux. Pour éviter cela, on peut ruser en utilisant des opérations bit à bit. Pour rappel, la somme de deux bits a et b vaut , tandis que la retenue vaut . Maintenant, prenons la somme de deux nombres A et B sans tenir compte des retenues. Le résultat sera Si on calcule ensuite uniquement les retenues, le résultat sera . Le décalage vient du fait que les retenues sont à prendre en compte la colonne suivante, quand on effectue d'addition en colonne. Dans ces conditions, on peut en déduire que . Maintenant, divisons le tout par deux pour obtenir la moyenne, ce qui revient à tout décaler d'un cran vers la droite. On obtient alors la formule pour calculer la moyenne :

.

Le circuit de calcul de la moyenne est donc très simple : il est comosé d'une porte XOR, d'une porte OU et d'une porte ET.

Valeur absolue[modifier | modifier le wikicode]

Prenons un premier exemple : la valeur absolue. Celle-ci peut se calculer de trois manières différentes. Cependant, toutes ces méthodes nécessite d'isoler le bit de signe. Pour cela, il suffit d'utiliser un décalage logique pour déplacer ce bit et le mettre dans le bit de poids faible. Dans ce qui suit, ce bit de signe sera noté y. La valeur absolue d'un nombre x peut se calculer comme ceci :

  •  ;
  •  ;
  • .

Pour obtenir l'inverse de la valeur absolue, il suffit de prendre l'opposée de celle-ci. En appliquant un simple - devant les expressions du dessus, on peut alors avoir diverses formules pour le calcul de l'inverse de la valeur absolue :

  •  ;
  •  ;
  • .

Conclusion[modifier | modifier le wikicode]

Fabriquer ces circuits de calcul n'est pas une mince affaire et les constructeurs de processeurs, ainsi que des chercheurs en arithmétique des ordinateurs, travaillent d'arrache-pied pour trouver des moyens de rendre nos circuits plus rapides et plus économes en énergie. Autant vous dire que les circuits que vous venez de voir sont vraiment des gamineries sans grande importance comparé à ce que l'on peut trouver dans un vrai processeur commercial !