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

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

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

Les portes logiques universelles commandables

Il y a quelques chapitres, nous avions parlé des opérations bit à bit et vu quelques circuits capables d'effectuer ces opérations. Ici, nous allons revenir sur ces circuits, mais allons en proposer une implémentation plus complexe et plus efficiente. Nous allons profiter du fait que l'on ne soit plus limités à quelques portes logiques, mais que nous pouvons maintenant utiliser des multiplexeurs, des démultiplexeurs et d'autres circuits pour améliorer les circuits de calcul bit à bit.

Dans cette section, nous allons voir comment créer un circuit capable d'effectuer plusieurs opérations logiques, le choix de l'opération étant le fait d'une entrée de commande. Par exemple, imaginons un circuit capable de faire à la fois un ET, un OU, un XOR et un NXOR. Le circuit contiendra une entrée de commande de 2 bits, et la valeur sur cette entrée permet de sélectionner quelle opération faire : 00 pour un ET, 01 pour un OU, 11 pour un XOR, 01 pour le NXOR Nous allons créer un tel circuit, sauf qu'il est capable de faire toutes les opérations entre deux bits et regroupe donc les 16 portes logiques existantes. Nous allons aussi voir la même chose, mais pour les portes logiques de 1 bit.

Les circuits de calcul bit à bit, le retour !

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

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

a	b		$0$	$a.b$	$a.{\overline {b}}$	$a$	${\overline {a}}.b$	$b$	$a\oplus b$	$a+b$	${\overline {a.b}}$	${\overline {a\oplus b}}$	${\overline {b}}$	$a+{\overline {b}}$	${\overline {a}}$	${\overline {a}}+b$	${\overline {a+b}}$	$1$
0	0	-	0	0	0	0	0	0	0	0	1	1	1	1	1	1	1	1
0	1	-	0	0	0	0	1	1	1	1	0	0	0	0	1	1	1	1
1	0	-	0	0	1	1	0	0	1	1	0	0	1	1	0	0	1	1
1	1	-	0	1	0	1	0	1	0	1	0	1	0	1	0	1	0	1

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

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

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

Les unités de calcul logique

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

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

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

Les opérations FFS, FFZ, CTO et CLO

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

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

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

Les opérations bit à bit complexes

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

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

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

La numérotation des bits et l'équivalence de certaines opérations

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

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

${\text{fhs}}+{\text{clz(n)}}=n-1$

${\text{fhz}}+{\text{clo(n)}}=n-1$

${\text{ffs}}={\text{ctz(n)}}$

${\text{ffz}}={\text{cto(n)}}$

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

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

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

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

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

L'encodeur à priorité

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

Les circuits générateurs/vérificateurs d'ECC

Au tout début de ce cours, nous avions vu les codes ECC, qui détectent ou corrigent des corruptions de données. Si un bit est altéré, ils permettent de détecter que le bit en question a été inversé, et peuvent éventuellement le corriger pour retrouver la donnée initiale. Les deux codes ECC les plus connus sont le bit de parité et les codes de Hamming. Dans ce qui suit, nous allons voir des circuits qui calculent soit un bit de parité, soit le code de Hamming d'un nombre.

Le générateur de parité

Pour rappel, le bit de parité est une technique qui permet de détecter si une donnée a été corrompue. Elle permet de détecter qu'un bit a été inversé, à savoir qu'un bit censé être à 1 est passé à 0 ou inversement. Pour cela, on ajoute un bit de parité aux données à sécuriser, afin que le nombre de bits à 1 soit pair, bit de parité inclu. En clair, si la donnée a un nombre de bit à 1 pair, alors le bit de parité vaut 0. Mais si le nombre est impair, alors le bit de parité vaut 1. Dans cette section, nous allons voir un circuit qui calcule le bit de parité d'une opérande.

Intuitivement, on se dit qu'il faut compter les 1 dans l'opérande, avant de calculer sa parité et d'en déduire le bit de parité. Compter les 1 dans un nombre est une opération tellement courante qu'elle porte un nom : on l'appelle la population count, ou encore poids de Hamming. Malheureusement, son calcul demande de faire des additions, ce qui fait qu'on le verra dans quelques chapitres. Mais heureusement, il existe une autre méthode bien plus simple, plus rapide, et plus économe en circuits.

Pour comprendre comment, nous allons commencer avec un cas simple : le calcul à partir d'une opérande de 2 bits. Le circuit étant simple, il suffit d'utiliser les techniques vues précédemment, avec la table de vérité. En écrivant la table de vérité du circuit, on remarque rapidement que la table de vérité donne la table de vérité d'une porte XOR.

Bit 1	Bit 2	Bit de parité
0	0	0
0	1	1
1	0	1
1	1	0

Pour la suite, nous allons partir d'un nombre de trois bits. On pourrait tenter de créer ce circuit à partir d'une table de vérité, mais nous allons utiliser une autre méthode, qui nous donnera un indice important. Ce nombre de 3 bits est composé d'un nombre de 2 bits auquel on a jouté un troisième bit. L'ajout de ce troisième bit modifie naturellement le bit de parité du nombre précédent. Dans ce qui va suivre, nous allons créer un circuit qui calcule le bit de parité final, à partir : du bit de parité du nombre de 2 bits, et du bit ajouté. On voit alors que la table de vérité est celle d'une porte XOR.

Bit de parité précédent	Bit ajouté	Bit de parité final
0	0	0
0	1	1
1	0	1
1	1	0

Chose assez intéressante, ce mécanisme fonctionne quel que soit le nombre de bits de l'opérande. Ajouter un bit à un nombre modifie sa parité, celle-ci état alors égale à : bit ajouté XOR bit-parité du nombre. L’explication est relativement simple : ajouter n 0 ne modifie pas le nombre de 1, et donc le bit de parité, tandis qu'ajouter un 1 inverse le bit de parité.

Avec cette logique, on peut créer un générateur de parité parallèle., un circuit qui calcule le bit de parité d'une opérande, en faisant un XOR entre tous ses bits. Effectué naïvement, il suffit d’enchaîner des portes XOR les unes à la suite des autres. En réfléchissant, on devien qu'on peut structurer les portes XOR comme ceci :

Circuit de parité

Le circuit précédent calcule le bit de parité d'une opérande. Pour ce qui est de vérifier si une donnée est corrompue, rien de plus simple : il suffit de générer le bit de parité de la donnée seule, et de le comparer avec le bit de parité stocké dans la donnée avec la porte logique adaptée. Le circuit qui génère un bit de parité et celui qui vérifie si le bit de parité est valide sont donc très similaires.

Le générateur/checker d'ECC

Pour ce qui est des codes de Hamming, ils calculent plusieurs bits de parité, qui sont calculé en prenant en compte une partie des bits de l'opérande. Un circuit qui génère le code de Hamming est donc composé de plusieurs circuits de génération de parité. Idem pour un circuit qui vérifie le code de Hamming d'une opérande.

Hamming(7,4)

Par exemple, voici ci-dessous le circuit pour vérifier un code de Hamming de type 7,4. Pour rappel, celui-ci prend des données sur 4 bits, et leur ajoute 3 bits de parité, ce qui fait en tout 7 bits : c'est de là que vient le nom de 7-4-3 du code. Chaque bit de parité se calcule à partir de 3 bits du nombre. Le schéma ci-contre indique quels sont les bits de données utilisés pour calculer un bit de parité : les bits de parité sont noté p, les bits de données d.

Le circuit est composé d'une première couche de portes XOR qui calculent le code de Hamming des 4 bits de données. Une seconde couche de portes XOR compare ce code calculé avec les trois bits d'ECC présents dans l'opérande. Si les deux valeurs correspondent, il n'y a pas d'erreur. Mais si les bits ne correspondent pas, alors on sait quel bit est erroné en regardant quel bit d'ECC est invalide. Uen couche de portes ET/NON sert de pseudo-décodeur, qui sélectionne le bit à corriger. Elle génére un masque de 4 bits qui indique quel bit inverser : celui dont le bit du masque est à 1. La dernière couche de portes XOR prend ce masque et l'applique aux 4 bits de données, ce qui inverse le bit adéquat.

Circuit de vérification d'un code de Hamming 7,4.