Fonctionnement d'un ordinateur/Les circuits incrémenteurs/décrémenteurs

Le circuit incrémenteur incrémente un nombre entier. Plus précisément, il prend en entrée un nombre entier, et fournit en entier le nombre suivant, il lui ajoute 1. Une telle opération peut paraitre triviale et peu intéressante. Cependant, elle est très utilisée et est absolument cruciale pour créer des compteurs, des circuits capables de compter ou décompter, qui auront droit à un chapitre dédié. De plus, au-delà de leur utilisation dans les compteurs, les incrémenteurs étaient très utilisés sur les premiers processeurs 8 bits, comme le Z-80, le 6502, les premiers processeurs x86 comme le 8008, le 8086, le 8085, et bien d'autres.

Il existe aussi des circuits décrémenteurs, qui décrémentent un opérande, ainsi que des circuits incrémenteur-décrémenteur, qui peuvent incrémenter ou décrémenter, selon comment on les configure. Je ne vais pas détailler ces circuits plus que ça, car de tels circuits sont assez rares, comparé à un circuit incrémenteur simple.

Le demi-additionneur

Le circuit incrémenteur effectue l'opération suivante :

   $a_{7}$ $a_{6}$ $a_{5}$ $a_{4}$ $a_{3}$ $a_{2}$ $a_{1}$ $a_{0}$ 
+  0  0  0  0  0  0  0  1

Un incrémenteur basique doit donc faire une addition pour chaque colonne, et précisément une addition de deux bits. Il se trouve que la table d'addition est très simple en binaire. Jugez plutôt :

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

Un circuit capable d'additionner deux bits est appelé un demi-additionneur. Il dispose d'une sortie S pour la somme, et C pour la retenue (carry an anglais).

Le demi-additionneur classique

Un demi-additionneur est très simple à construire avec les techniques vues dans les premiers chapitres. Voici sa table de vérité :

Retenue entrante	Opérande 1		Retenue sortante	Bit de somme
0	0		0	0
0	1		0	1
1	0		0	1
1	1		1	0

On voit immédiatement que la colonne des retenues donne une porte ET, alors que celle du bit de somme est calculé par un XOR.

Demi-addtionneur.

Circuit d'un demi-addtionneur.

Il existe beaucoup d'autres implémentations alternatives, qui utilisent moins de portes logiques, calculent la retenue plus rapidement, consomment moins d'énergie, et autres. Et il est intéressant d'étudier quelques alternatives, surtout qu'elles serviront plus bas, quand on étudiera le circuit incrémenteur du 8085.

Le demi-additionneur basé sur une modification de la retenue

Une source d'amélioration est liée à la porte XOR. En pratique, une porte XOR est composée en combinant plusieurs portes logiques ET/OU/NOR/NAND ensemble. Et il se trouve qu'il y a des redondances entre celles-ci et les portes utilisées pour calculer la retenue. Par exemple, rappelons qu'une porte XOR peut être construite avec une porte ET et deux portes NOR, comme illustré ci-dessous. Et il se trouve que la porte ET interne calcule la retenue sortante. En supprimant cette redondance, on économise quelques portes logiques. De plus, on se retrouve avec un demi-additionneur qui calcule le bit de somme à partir de la retenue sortante.

Demi-additionneur avec redondances éliminées

Le circuit précédent a une interprétation logique. Si vous regardez la table de vérité, vous remarquerez que la somme de deux bits est égale à l'inverse de la retenue sortante, sauf dans le cas où les deux bits additionnés valent zéro. Et le circuit précédent est basé là-dessus.

Retenue entrante	Opérande 1		Retenue sortante	Bit de somme
0	0		0	0
0	1		0	1
1	0		0	1
1	1		1	0

L'idée est de calculer l'inverse du bit de somme, avant de l'inverser avec une porte NON. L'inverse du bit de somme vaut 1, soit quand la retenue est à 1, soit quand les deux bits additionnés sont à 0. La porte ET calcule la retenue sortante, la première porte NOR détecte sur les deux bits d'entrée valent zéro. Une porte OU combine les deux résultat pour obtenir l'inverse du bit d'entrée, puis une porte NOn inverse le tout pour obtenir le bit de somme adéquat. Les deux portes sont fusionnées : c'est la seconde porte NOR.

Demi-additionneur basé sur une inversion de la retenue sortante.

Les implémentations alternatives

Une implémentation alternative, qui n'utilise que des portes NOR, est la suivante :

Demi-additionneur fait avec des portes NOR et NAND.

Une implémentation alternative utilise des portes NAND. Pour rappel, il est possible de créer une porte XOR avec 4 portes NAND. La première d'entre elle fait un NAND entre les deux bits d'entrée, ce qui fait qu'elle calcule l'inverse de la retenue sortante. Le tout est illustré ci-dessous. En théorie, on devrait utiliser une porte NON pour récupérer la retenue correcte. Mais nous verrons plus bas que ce n'est pas une obligation. Nous verrons plus bas un exemple où c'est l'inverse de la retenue qui est utilisée dans les calculs, pour rendre les calculs plus rapides.

Demi-additionneur fait avec des portes NAND

Le circuit incrémenteur

Maintenant que l'on sait comment additionner deux bits, reprenons l'opération d'incrémentation :

   $a_{7}$ $a_{6}$ $a_{5}$ $a_{4}$ $a_{3}$ $a_{2}$ $a_{1}$ $a_{0}$ 
+  0  0  0  0  0  0  0  1
------------------------------

Sur la colonne la plus à droite, il doit ajouter un au bit de poids faible. Pour les colonnes suivantes, il faut additionner le bit de l'opérande avec la retenue de la colonne précédente. En clair, on n'additionne que deux bits à chaque colonne : un 1 sur celle tout à droite, la retenue de la colonne précédente pour les autres. Et cela nous donne une idée de comment faire pour créer le circuit incrémenteur.

L'incrémenteur à propagation de retenue

Il suffit d'utiliser un demi-additionneur par colonne, et de les enchainer les uns à la suite des autres. Chaque demi-additionneur additionne le bit de l'opérande avec la retenue fournie par le demi-additionneur précédent. Le seul qui fait exception est celui pour la colonne de poids faible. Pour celui-là, il doit ajouter 1 au bit de poids faible. Le résultat est appelé un incrémenteur à propagation de retenue. Il est constitué de demi-additionneurs enchaînés les uns à la suite des autres, du bit de poids faible vers le bit de poids fort.

Circuit incrémenteur.

Maintenant, regardons le demi-additionneur le plus à droite, celui pour le bit de poids faible. Son entrée de retenue entrante est mise à 1 pour faire l'incrémentation. Quelques incrémenteurs permettent de configurer cette entrée de retenue à 0 ou à 1, ce qui effectue : soit une opération identité (l'opérande est recopié sur la sortie), soit une incrémentation. Un tel circuit est nommé un incrémenteur commandable. Nous aurons à utiliser une fois ou deux de tels incrémenteurs commandables dans la suite du cours.

La sortie de retenue indique si l'incrémentation a entrainé un débordement d'entier. Lors d'un débordement d'entier, la retenue de sortie est à 1. Elle est à 0 en absence de débordement d'entier. La sortie de retenue est présente sur la plupart des incrémenteurs, mais laissons cela de côté pour le moment.

L'incrémenteur à propagation de retenue est le plus simple et le plus économe en portes logiques. Mais de tels incrémenteurs sont rarement utilisés. À la place, on leur préfère des incrémenteurs plus rapides, mais qui utilisent plus de portes logiques. De tels incrémenteurs accélèrent le calcul des retenues. En effet, la rapidité d'une incrémentation est limitée par la propagation de la retenue : les retenues commencent à être calculées au bit de poids fort et on doit les calculer une par une, jusqu’à atteindre le bit de poids fort. Et cette "propagation des retenues" prend du temps, d'autant plus de temps que l'opérande est longue. Il y a deux optimisations principales, appelées le carry skip et l'anticipation de retenue, que nous allons décrire ci-dessous.

Les incrémenteurs optimisés

L'optimisation que nous allns voir effectue l'incrémentation, non pas bit par bit, mais par paquets de deux bits. Le résultat est que l'incrémentation est deux fois plus rapide, ou presque. Le circuit incrémenteur est donc composé en enchainant non pas des demi-additionneurs, mais des incrémenteurs 2 bits qui incrémentent un opérande de deux bits.

Circuit incrémenteur optimisé, faisant l'incrémentation par paquet de deux bits

Reste à concevoir l'incrémenteur 2 bits. Une première méthode part de deux demi-additionneurs et effectue quelques simplifications au niveau des transistors et des portes logiques. Par exemple, l'Intel 8085 a utilisé un circuit optimisé, fabriqué avec des portes NAND et NOR. La raison est qu'avec les technologies de transistors CMOS actuelles, les portes NAND et NOR utilisent moins de transistors que les portes ET et OU. Et cette possibilité a été utilisée pour effectuer des simplifications assez mineures, mais toujours bonnes à prendre. Mais nous ne pouvons pas en parler en détail ici, car nous n'avons pas encore parlé en détail des transistors. Cependant, un exemple bien précis nous est accesible : celui de l’incrémenteur du processeur 8085 d'Intel.

Le processeur 8085 d'Intel est un processeur 8 bits très ancien. Il contenait un incrémenteur 16 bits, qui était utilisé pour calculer des adresses mémoire. Et cet incrémenteur était un incrémenteur à propagation de retenue optimisé. Il utilisait lui aussi des incrémenteurs 2 bits un peu modifiés.

L'idée était que les retenues sortant des colonnes paires étaient inversées, les colonnes impaires faisaient les calculs à partir de cette retenue inversée. Les demi-additionneurs des colonnes impaires n'étaient donc pas les mêmes que ceux des colonnes paires. Leurs tables de vérité sont différentes, leurs circuits aussi, et aucun des deux ne ressemble à un demi-additionneur normal. En réalité, ils sont fabriqués à partir des implémentations vues plus haut, qui utilisent uniquement des portes NAND ou uniquement des portes NOR.

Pour comprendre l'intérêt de faire ainsi, nous devons préciser une chose importante : avec les technologies CMOS utilisées pour les processeurs depuis les années 70, les portes logiques les plus simples sont les portes NON, NOR et NAND. Les portes ET/OU sont fabriquées en combinant des portes NOR/NAND avec une porte NON, ce qui prend plus de transistors.

Un demi-additionneur est donc fabriqué comme illustré ci-dessous, en logique CMOS. Seules les portes pour le calcul de la retenue sont indiquées, la porte XOR pour le bit de somme est fabriquée à partir de plusieurs portes logiques.

Demi-additionneur en CMOS

Si on enchaine deux demi-additionneurs, cela donne ceci :

Brique de base de l'incrémenteur du 8085

La retenue doit donc traverser quatre portes logiques, dont deux portes NON. En inversant la retenue, les portes en jaune dans le schéma précédent se simplifient. Il suffit d'utiliser la loi de de Morgan pour trouver un circuit équivalent aux portes jaunes, qui n'est autre qu'une porte NOR couplée à une porte NON. Un autre moyen d'obtenir le même résultat est de prendre un demi-additionneur fabriqué avec uniquement des portes NOR, et de retirer la porte NON adéquate. Il faut ensuite corriger l'entrée de retenue de la porte XOR, pour qu'elle fasse l'addition avec la retenue correctement. Le résultat est illustré ci-dessous.

Incrémenteur 2 bits de l'incrémenteur du 8085

Le circuit utilise le même nombre de portes logiques, il n'économise pas de transistors. Par contre, la retenue n'a plus qu'à traverser deux portes logiques, au lieu de quatre. La propagation de la retenue est donc plus rapide, l'incrémentation est donc plus rapide.

Les incrémenteurs 2 bits à calcul séparé de la retenue

Il existe une autre méthode qui permet de créer des incrémenteurs 2 bits plus rapides que les précédents, mais qui utilisent plus de portes logiques. Ces incrémenteurs 2 bits calculent séparément les deux bits du résultat et la retenue sortante. La retenue sortante est calculée à partir des bits de l’opérande, sans avoir besoin de propager des retenues. Ainsi, la retenue sortante est connue en avance, sans passer par deux demi-additionneurs. Formellement, ils sont un cas particulier d'une optimisation appelée l'anticipation de retenue. Si nous verrons le cas général dans la section suivante, ce cas particulier est une très bonne introduction.

Pour créer un tel incrémenteur, le mieux est de partir de sa table de vérité.

Opérande	Retenue entrante		Retenue sortante	Résultat
00	0		0	00
01	0		0	01
10	0		0	10
11	0		0	11
00	1		0	01
01	1		0	10
10	1		0	11
11	1		1	00

Elle nous dit que la retenue sortante ne vaut 1 que dans un seul cas : les deux bits d'opérande valent 1, la retenue entrante vaut 1. Elle se calcule alors avec une porte ET à trois entrées. Pour les deux bits du résultat, les équations logiques ne donnent pas un résultat satisfaisant. La solution la plus simple est d'utiliser deux demi-additionneurs et de retirer les portes logiques superflues. Le résultat est alors un incrémenteur 2 bits carry skip, où la retenue sortante est calculée séparément du reste.

Incrémenteur carry skip 2 bits

Les incrémenteurs à anticipation de retenue

L'anticipation de retenue calcule la retenue d'une colonne sans attendre les retenues des colonnes précédentes. Dans le cas idéal, toutes les retenues sont calculées en parallèle, en même temps, et sont ensuite envoyées aux demi-additionneurs. Il s'agit d'une optimisation qui est utilisée pour l'incrémentation, l'addition et d'autres opérations similaires. Pour l'incrémentation, déterminer la retenue ne demande pas de calculs complexes, contrairement à l'addition.

Incrémenteur à anticipation de retenues, 8 bits.

Pour le comprendre, on peut regarder comment la retenue sortant d'un demi-additionneur est formée. Elle est calculée en faisant un ET logique entre la retenue entrante et le bit d'opérande. Une retenue est donc un ET logique entre toutes les retenues précédentes. Un incrémenteur à anticipation de retenue utilise donc une porte ET à plusieurs entrées pour calculer une retenue.

Anticipation de retenue pour un bit du résultat, incrémenteur

En théorie, on peut utiliser une porte ET à plusieurs entrées pour chaque bit de l'opérande. Cependant, cela entrainera un cout en transistors très important. Pour éviter de gaspiller trop de portes logiques, une solution est de mélanger anticipation de retenues et propagation de retenue. Par exemple, pour un incrémenteur 32 bits, on peut découper l'opérande en 4 octets : on anticipe les retenues pour chaque octet, mais l'incrémentation de chaque octet se fait avec propagation de retenue et/ou carry skip. Plus haut, nous avons vu un cas particulier où les retenues étaient anticipées par blocs de deux bits.

Incrémenteur hybride utilisant partiellement l'anticipation de retenues.

Quelques processeurs utilisaient l'anticipation de retenues. Par exemple, le processeur Z-80 de Zilog utilisait un incrémenteur pour des nombres de 16 bits, ce qui demandait des performances assez élevées. Et cet incrémenteur utilisait à la fois anticipation de retenues et carry skip. Il était découpé en quatre blocs avant anticipation de retenues entre eux : un bloc regroupant les 7 bits de poids faible, suivi par un bloc de 5 bits, lui-même suivi par un bloc de 3 bits, terminé par un dernier bit isolé. A l'intérieur de ces blocs, les bits sont regroupés en paires utilisant le carry skip. Pour ceux qui veulent en savoir plus sur cet incrémenteur, voici un lien sur le sujet :

• The Z-80's 16-bit increment/decrement circuit reverse engineered.

Les décrémenteurs

Les circuits décrémenteurs font l'inverse d'un incrémenteur : au lieu d'ajouter 1 à un opérande, ils lui soustraient 1. La différence n'est pas énorme, ce qui fait que les circuits incrémenteurs et décrémenteurs se ressemblent beaucoup.

La soustraction se fait en binaire comme en décimal. On soustrait deux chiffres, puis on doit propager une éventuelle retenue sur la colonne suivante. La retenue apparait quand le chiffre soustrait est plus grand que l'autre chiffre. Elle est propagée sur la colonne suivante, où elle doit être soustraite du résultat. Pour le dire autrement, après avoir soustrait un chiffre, on doit de plus soustraire la retenue de la colonne précédente.

La décrémentation effectue le calcul suivant :

   $a_{7}$ $a_{6}$ $a_{5}$ $a_{4}$ $a_{3}$ $a_{2}$ $a_{1}$ $a_{0}$ 
-  0  0  0  0  0  0  0  1

La colonne la plus à droite soustrait un 1. Par contre, les colonnes suivantes soustraient un zéro. Soustraire un zéro ne change rien. Mais il ne faut pas oublier de soustraire une éventuellement retenue, propagée depuis la colonne précédente. En clair, un décrémenteur peut se construire si on sait soustraire deux bits. On soustrait un 1 sur la colonne la plus à droite, on soustrait une retenue sur les autres colonnes. Et pour soustraire deux bits, il faut utiliser un demi-soustracteur.

Le demi-soustracteur et le décrémenteur à propagation de retenue

Un demi-soustracteur soustrait deux bits. Il prend deux bits d'entrée et fournit deux sorties : un bit de différence et une retenue. Pour comprendre d'où vient cette retenue, et comment soustraire deux bits, traitons les quatre cas possibles un par un.

Premièrement, soustraire zéro à un bit ne changera rien :

• 0 - 0 = 0 ;
• 1 - 0 = 1.

Si on soustrait 1 à un bit qui vaut 1, on obtient zéro.

• 1 - 1 = 0.

Maintenant, que se passe-t-il si on soustrait 1 à 0 ? Voici le résultat :

• 0 - 1 = 1 et une retenue propagée sur la colonne suivante, où elle est soustraite.

La table de vérité est donc la suivante. Détail important : le demi-soustracteur fait ici la soustraction X - Y. En anglais, X est appelé le Minuend et Y est appelé le Subtrahend, mais ces termes n'ont pas de traduction française. Aussi, je vais les utiliser tels quels dans ce qui suit.

Minuend	Subtrahend		Retenue sortante	Bit de somme
0	0		0	0
0	1		1	1
1	0		0	1
1	1		0	0

Si on construit la table de vérité, et qu'on construit le circuit associé, on tombe sur ce circuit.

Demi-soustracteur.

Vous remarquerez que le bit de somme se calcule de la même manière que pour l'addition, seul le calcul de la retenue change. Comme pour le demi-additionneur, on peut exploiter des redondances entre calcul de la retenue et porte XOR, mais ce ne sont pas les mêmes. Le circuit obtenu après exploitation de ces redondances est le suivant :

Demi-soustracteur optimisé, sans redondances

Un décrémenteur à propagation de retenue se construit comme un incrémenteur, sauf qu'on remplace les demi-additionneurs par des demi-soustracteurs. En clair, on enchaine plusieurs demi-soustracteurs les uns à la suite des autres.

Le décrémenteur à anticipation de retenue

Il est possible d'utiliser l'anticipation de retenue, mais les circuits sont cependant différents de l'incrémenteur. Idem avec le carry skip, et toute autre optimisation possible. La raison est que les retenues sont calculées différemment, ce qui fait que l’anticipation de retenue doit être adaptée. La retenue d'une colonne ne se calcule plus avec un ET des bits des colonnes précédentes. A la place, ces bits doivent être inversés avant de faire le ET. Le résultat est que la porte ET est remplacée par une porte NOR.

Pour ceux qui s'en rappelle, faire un NOR de N bits permet de vérifier s'ils sont tous à zéro. Et c'est le cas ici. Lors d'une incrémentation, on a une retenue quand tous les bits précédents de l'opérande sont à 1. Pour la décrémentation, c'est l'inverse : on a une retenue quand tous les bits précédents sont à 0.

De fait, décrémenter un nombre est assez simple. Il y a deux cas principaux :

• soit le bit de poids faible est un 1, ce qui signifie que le nombre est impair ;
• soit un ou plusieurs bits de poids faible consécutifs sont à 0, suivis par un 1.

Dans le premier cas, le bit de poids faible est juste inversé. Dans le second cas, le 1 est inversé, et les 0 de poids faible deviennent des 1. Par exemple, Prenez un nombre de la forme xxxxxxx10000. Après décrémentation, le résultat sera xxxxxxxx011111 : les 0 de poids faible deviennent des 1, le premier 1 en partant de la droite est inversé. Et la même logique se généralise pour tout nombre avant un ou plusieurs zéros dans les bits de poids faible.

Les incrémenteurs-décrémenteurs

Les circuits décrémenteurs ressemblent beaucoup aux incrémenteurs. Aussi, vous ne serez pas étonné qu'il soit possible de fusionner un incrémenteur et un décrémenteur en un seul circuit. Un tel circuit s'appelle un incrémenteur-décrémenteur.

Un tel circuit a une interface similaire à celle d'un incrémenteur, avec une entrée sur laquelle présenter l'opérande, et une sortie sur laquelle récupérer le résultat. Il a aussi une entrée de retenue, sur laquelle envoyer un 1 (incrémentation) ou un 0 (opération NOP/identité). Et il a aussi une sortie de retenue, qui indique que le résultat du calcul a débordé. Mais en plus de cela, il dispose d'une entrée de commande qui permet de choisir entre incrémentation et décrémentation. En général, elle est mise à 0 lors d'une incrémentation et à 1 lors d'une décrémentation.

Il existe plusieurs manières de créer un incrémenteur-décrémenteur, que nous allons voir si dessous. Nous n'allons pas voir le cas le plus évident, aussi ne vous étonnez pas si vous avez remarqué qu'un demi-additionneur et un demi-soustracteur se ressemblent beaucoup.

L'incrémenteur-décrémenteur basé sur un incrémenteur

Une première implémentation se base sur les propriétés du complément à deux, et plus précisément sur cette équation :

${\overline {x}}+1={\overline {x-1}}$

Les deux termes de cette équation sont simplement des définitions équivalentes du complément à deux d'un nombre entier. Celui-ci se calcule de deux manières : soit on incrémente son complément à 1, soit on prend le complément à 1 de son décrément. Et cela nous permet de déterminer comment obtenir une incrémentation à partir d'une décrémentation et inversement.

Que nous dit cette équation ? Simplement que l'on peut décrémenter un nombre si on a deux inverseurs commandables, et un circuit incrémenteur. La décrémentation se fait alors en deux étapes : on calcule son complément à deux, puis on inverse les bits du résultat précédent. Le calcul du complément à deux demande d'avoir un circuit inverseur, et un incrémenteur. Les inverseurs commandables sont configurés par l'entrée de commande.

Circuit incrémenteur-décrémenteur.

L'incrémenteur-décrémenteur basé sur des demi-additionneurs

Vous l'aurez sans doute remarqué, mais le demi-soustracteur ressemble beaucoup au demi-additionneur. La seule différence est une porte NON ajoutée au bon endroit dans le demi-soustracteur. La porte NON inverse le bit X, sachant que le demi-soustracteur fait la soustraction X - Y. De plus, l'opérande inversée est utilisée seulement pour le calcul des retenues, le bit de somme est calculé normalement.

Demi-additionneur

Demi-soustracteur

La conséquence est qu'il est possible de fusionner un demi-additionneur avec un demi-soustracteur. L'idée est de remplacer la porte NON du demi-soustracteur par un inverseur commandable. Si on envoie un zéro sur l'entrée de commande, l'inverseur commandable se comportera comme une porte OUI et le circuit sera alors identique à un demi-additionneur. Si on envoie un 1 sur l'entrée de commande, l'inverseur commandable se comportera comme une porte NON. le circuit sera alors un demi-soustracteur. En remplaçant les demi-additionneurs (ou demi-soustracteurs) par de tels circuits, on peut obtenir un circuit faisant à la fois incrémenteur et décrémenteur.

Un défaut de cette approche est que les optimisations vues plus haut pour les demi-additionneurs ne fonctionne tout simplement plus. On est obligé d'utiliser une porte XOR et une porte ET séparées, pas question d'utiliser les demi-additionneurs optimisés vu au début du chapitre.