Fonctionnement d'un ordinateur/Les circuits de décalage et de rotation

Dans ce chapitre, nous allons voir les décalages et les rotations. Nous allons voir ce que sont ces opérations, avant de voir les circuits associés. Précisons que dans les ordinateurs modernes, décalages et rotations sont prises en charge par un circuit, le barrel shifter, qui est capable d'effectuer aussi bien des rotations que des décalages. Il en existe de nombreux types, mais nous allons voir les barrel shifters basés sur des multiplexeurs. Mais expliquons d'abord les différentes opérations de décalage et de rotation.

Les opérations de décalage

Les décalages 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. Il existe plusieurs opérations de décalage différentes et on peut les classer en plusieurs types. Dans les grandes lignes, on distingue les rotations, les décalages logiques et les décalages arithmétiques. Elles se distinguent sur plusieurs points, les principaux étant les suivants :

• ce qu'on fait des bits qui sortent du nombre lors du décalage ;
• comment on remplit les vides qui apparaissent lors du décalage ;
• la manière dont est géré le signe du nombre décalé.

Décalages, gestion des bits entrants et sortants

Pour comprendre les deux premiers points, prenons l'exemple d'un nombre de 8 bits, comme ci-contre. L'exemple montre le décalage de 01011101 de deux rangs. On obtient 010111 : les deux bits de poids forts sont vides et les deux bits de fin (01) sortent du nombre. Et cela vaut pour tout décalage : d'un côté le décalage fait sortir des bits du nombre, de l'autre certains bits sont inconnus ce qui laisse des vides dans le nombre. Le nombre de bits sortants et de vides est strictement égal au nombre de rangs de décalage : si on décale de n rangs, alors cela laissera n vides et fera sortir n bits. Pour un décalage de n rangs, les vides sont dans les n bits de poids fort pour un décalage à droite et dans les n bits de poids faibles pour un décalage à gauche. Et les n bits sortant sont à l'opposé : bits de poids faible pour un décalage à droite et bits de poids fort pour un décalage à gauche. Ces deux points, la gestion des vides et des bits sortants, sont assez liés.

Le différents types de décalages

En premier lieu, parlons de ce qu'on fait des bits qui sortent du nombre lors du décalage. Que fait-on de ces bits ?

La première solution est de les faire rentrer de l'autre côté, de les remettre au début du nombre décalé. L'opération en question est alors appelée une rotation. Il existe des rotations à droite et à gauche.

MSB : bit de poids fort (Most Significant Bit) LSB : bit de poids faible (Least Significant Bit)

Rotation à gauche.

Rotation à droite.

L'autre solution est d'oublier les bits sortants. L’opération est alors appelée un décalage, qui peut être soit un décalage logique, soit un décalage arithmétique. Le fait que l'on oublie les bits sortants fait que les vides ne sont pas remplis et qu'il faut trouver de quoi les combler. Et c'est là qu'on peut faire la distinction entre décalages logiques et arithmétiques.

Avec un décalage logique, les vides sont remplis par des zéros, aussi bien pour un décalage à gauche et un décalage à droite.

Décalage logique à gauche.

Décalage logique à droite.

Décalage arithmétique à droite.

Avec un décalage arithmétique, la situation est différente pour un décalage à gauche et à droite. Le principe des décalages arithmétique est qu'ils conservent le bit de signe du nombre décalé (qui est supposé être signé), contrairement aux autres décalages. La situation est cependant quelque peu compliquée et tout dépend de l'implémentation exacte du décalage, tous les ordinateurs ne faisant pas la même chose.

Il n'y a pas d’ambigüité pour les décalages à droite, qui sont tous réalisés de la même manière sur toutes les architectures. Pour un décalage à droite, les vides dans les vides de poids forts sont remplis par le bit de signe. Ce remplissage est une sorte d'extension de signe, ce qui fait que la conservation du signe est automatique.

Décalage arithmétique à gauche qui ne conserve pas le bit de signe.

Pour un décalage à gauche, les choses sont plus compliquées. Les bits de poids faible vides sont remplis par des zéros, comme pour un décalage logique. Mais pour ce qui est de la conservation du bit de signe, c'est plus compliqué. On a deux écoles : la première ne conserve pas le bit de signe, la seconde le fait. Dans le premier cas, le décalage est identique à un décalage logique à gauche. Dans le second cas, le bit de signe n'est pas concerné par le décalage.

L'interprétation mathématique des décalages

L'utilité principale des opérations de décalage est qu'elles permettent de faire simplement des multiplications ou divisions par une puissance de 2. Un décalage logique/arithmétique correspond à une multiplication ou division entière par 2^n : multiplication pour les décalages à gauche, division pour les décalages à droite. Les décalages logiques fonctionnent pour les entiers non signés, alors que les décalages arithmétiques fonctionnent sur les entiers signés. Le fait est qu'un décalage logique ne donne pas le bon résultat avec un entier signé, la raison étant qu'il ne préserve pas le bit de signe. À l'inverse, le décalage arithmétique conserve le bit de signe, du moins pour les décalages à droite, ce qui le rend adapté pour les entiers signés. Les décalages arithmétiques à droite permettent donc de faire des divisions par 2^n sur des nombres signés.

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

Les arrondis lors des décalages

Les décalages à droite entraînent l'apparition d'arrondis. Lorsqu'on effectue un décalage à droite, certains bits vont sortir du résultat et être perdus. L’équivalent en décimal est que les chiffres après la virgule sont perdus, ce qui arrondit le résultat. Mais cet arrondi dépend de la représentation des nombres utilisé. Pour comprendre pourquoi, il faut faire un rapide rappel sur les types d'arrondis en décimal.

En décimal, on peut arrondir de deux manières : soit on arrondit à l'entier au-dessus, soit on arrondi à l'entier au-dessous. Par exemple, prenons la division 29/4, qui a pour résultat 7.25. Cela donne 7 dans le premier cas et 8 dans le second. Pour un résultat négatif, c'est la même chose, mais le fait que le signe soit inversé change la donne. Par exemple, prenons le résultat de -29 / 4, soit -7.25. On peut l'arrondir soit à -7, soit à -8. En combinant les deux cas négatifs avec les deux cas positifs, on se trouve face à quatre possibilités :

• l'arrondi vers la plus basse valeur absolue (vers zéro), qui donne respectivement 7 et -7 dans l'exemple précédent.
• l'arrondi vers la plus basse valeur (vers moins l'infini), qui donne -8 et 7 dans l'exemple précédent ;
• l'arrondi vers la plus haute valeur (vers plus l'infini), qui donne -7 et 8 dans l'exemple précédent ;
• l'arrondi vers la plus haute valeur absolue (vers l'infini), qui donne 8 et -8 dans l'exemple précédent.

En binaire, c'est la même chose. Par exemple, 11100,1010 peut s'arrondir en 11100 ou en 11101, suivant qu'on arrondisse vers le bas ou vers le haut, et la même chose est possible pour les nombres négatifs. Précisons que ces arrondis n'ont lieu que si le résultat du décalage n'est pas exact. Pour un décalage d'un rang, à savoir une division par deux, seuls les nombres impairs donnent un arrondi, pas les nombres pairs. De manière générale, pour un décalage de n rangs, les nombres divisibles par 2^n ne donnent pas d'arrondi, alors que les autres si.

Lors d'un décalage, les bits sortants sont simplement éliminés. On pourrait croire que cela signifie que l'arrondi se fait vers zéro (vers la valeur inférieure). C'est bien le cas pour les nombres positifs, mais pas pour les nombres négatifs pour lesquels le résultat dépend de la représentation. Pour les décalages logiques, peu importe la représentation, l'arrondi se fait vers zéro (vu que tous les nombres sont traités comme positifs). Mais pour les décalages arithmétiques, c'est autre chose. En complément à 1, l'arrondi se fait bien vers zéro : les nombres positifs sont arrondis à la valeur inférieure et les nombres négatifs à la valeur supérieure. Par contre, en complément à deux, les nombres positifs et nombres négatifs sont arrondis à la valeur inférieure. En clair, l'arrondi se fait vers moins l'infini. Ce qui peut causer quelques problèmes si l'on ne fait pas attention, le résultat du décalage et d'une division pouvant varier à cause des règles d'arrondis.

Les débordements d'entiers lors des décalages

Outre les arrondis, les décalages peuvent causer ce qu'on appelle des débordements d'entier. Ce terme barbare recouvre toutes les situations où le résultat d'un calcul devient trop gros pour être codé. Pour donner un exemple, prenons une situation équivalente mais en décimal. On suppose que l'on manipule des données codées sur 5 chiffres décimaux, pas plus. Si on prend le nombre 4512, le décalage à gauche d'un cran donne 45120, qui tient sur 5 chiffres : on n'a pas de débordement. Mais si je prends le nombre 97426, un décalage à gauche d'un cran donne 974260, ce qui ne tient pas dans 5 chiffres : on a un débordement d’entier. Celui-ci se traduit par le fait qu'un chiffre non-nul sorte du nombre. La même chose a lieu en binaire, avec les décalages à gauche. Un débordement d'entier en binaire se traduit par le fait qu'au moins un bit non-nul sorte à gauche.

La manière habituelle de gérer les débordements d'entiers est simplement de ne rien faire, mais de prévenir qu'un débordement a eu lieu. Pour cela, le circuit qui effectue le décalage a une sortie qui indique qu'un débordement a eu lieu lors du décalage. Cette sortie fournit un simple bit qui vaut 1 en cas de débordements et 0 sinon (ou l'inverse). Une autre solution est de corriger le débordement, mais si cela est fait pour les opérations arithmétiques, cela n'est pas fait pour les décalages.

Toujours est-il que déterminer l’occurrence d'un débordement n'est pas compliqué. Pour les décalages logiques, il suffit de prendre les bits sortants et de vérifier qu'un au moins d'entre eux vaut 1. Une simple porte OU sur les bits sortants fait l'affaire. Pour les décalages arithmétiques, il faut aussi tenir compte de la présence du bit de signe. La valeur des bits sortants dépend du signe positif ou négatif du nombre. Si le nombre décalé est positif, seuls des zéros doivent sortir, la présence d'un 1 indiquant un débordement d'entier. Pour un nombre négatif, c'est l'inverse : seuls des 1 doivent sortir (du fait des règles d'extension de signe), alors que l’occurrence d'un zéro trahit un débordement d'entier. Pour résumer le tout, les bits sortants sont censés être égaux au bit de signe, un débordement a eu lieu dans le cas contraire. L’occurrence d'un débordement se détermine en décomposant le décalage en une succession de décalages de 1 bit. Si un seul de ces décalages de 1 rang altère le bit de signe (change sa valeur), alors on a un débordement.

Il est possible de déterminer l’occurrence d'un débordement en analysant l'opérande, sans même avoir à faire le décalage. Pour un décalage vers la gauche de $n$ rangs, on sait que les bits sortants sont les $n$ bits de poids fort de l'opérande. En clair, on peut déterminer si un débordement a lieu en sélectionnant seulement les $n$ bits de poids fort de l'opérande. Pour cela, on peut simplement prendre l'opérande et lui appliquer un masque adéquat. Par exemple, prenons le cas d'un débordement pour un décalage logique, qui a lieu si au moins un bit sortant est à 1. Il suffit de prendre l'opérande, conserver les $n$ rangs bits de poids fort et mettre les autres à zéro, puis faire un ET entre les bits du résultat. La même logique prévaut pour les décalages arithmétiques, même s'il faut faire quelques adaptations.

Calcul du bit de débordement pour un décalage à gauche de trois rangs.

Toujours est-il que le calcul des débordements peut se faire en parallèle du décalage, ce qui est utile. Précisons que le masque se calcule dans un circuit à part, qui ressemble beaucoup à un encodeur. Le masque calculé peut être utilisé sur certains circuits de décalages, pour transformer des rotations en décalage logiques, par exemple. Mais nous verrons cela plus tard.

Les décaleurs et rotateurs élémentaires

Décaleur - interface

Pour commencer, nous allons voir deux types de circuits : les décaleurs qui effectuent un décalage (logique ou arithmétique, peu importe) et les rotateurs qui effectuent une rotation. Les deux circuits sont conceptuellement séparés, même s’ils se ressemblent. Faire la distinction sera utile dans la suite du cours. Leur interface est la même pour tous les décaleurs et rotateurs élémentaires. On doit fournir l'opérande à décaler et le nombre de rangs qu'on veut décaler en entrée, et on récupère l'opérande décalé en sortie.

Nous allons d'abord voir comment créer un circuit capable de décaler un nombre (vers la droite ou la gauche, peu importe) 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 de 6 rangs, c'est équivalent à décaler 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 active ou désactive suivant le nombre de rangs. L'idée est de prendre des décaleurs élémentaires qui décalent par 1, 2, 4, 8, etc ; bref : par une puissance de 2. La raison à cela est que 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

La même logique s'applique pour les rotateurs, la seule différence étant qu'il faut remplacer les décaleurs par 1, 2, 4, 8, etc ; par des rotateurs par 1, 2, 4, 8, etc.

Reste à savoir comment créer ces décaleurs qu'on peut activer ou désactiver à la demande. Surtout que le circuit n'est pas le même selon que l'on parle d'un décalage logique, d'un décalage arithmétique ou d'une rotation. Néanmoins, tous les circuits de décalage/rotation sont fabriqués avec des multiplexeurs à deux entrées et une sortie.

Le circuit décaleur logique

Commençons par étudier le cas du décalage logique. On va prendre comme exemple un décaleur par 4 à droite, 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 prends 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 fort 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.

En utilisant des décaleurs basiques par 4, 2 et 1 bit, on obtient le circuit suivant :

Décaleur logique 8 bits.

Le circuit décaleur arithmétique

Les décalages arithmétiques sont basés sur le même principe, à une différence près : on n'envoie pas un zéro dans les bits de poids fort, mais le bit de signe (le bit de poids fort du nombre d'entrée). Un décaleur arithmétique ressemble beaucoup à un décaleur logique, la seule différence étant que c'est le bit de poids fort qui est relié aux entrées des multiplexeurs, là où il y avait un zéro avec le décaleur logique. Par exemple, reprenons un nombre A, composé des bits a7, a6, a5, a4, a3, a2, a1, a0 ; (cités dans l'ordre). La sortie d'un décaleur arithmétique par 4 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 a7, a7, a7, a7, a7, a6, a5, a4 (on effectue un décalage arithmétique par 4).

Exemple d'un décaleur arithmétique par 4

En combinant des décaleurs basiques par 4, 2 et 1 bits, on obtient le circuit suivant :

Décaleur arithmétique 8 bits

Le circuit rotateur

Les rotations sont elles aussi basées sur le même principe, sauf que ce sont les bits de poids faible qu'on injecte dans les bits de poids forts, au lieu d'un zéro ou du bit de signe. Le circuit est donc le même, sauf que les connexions ne sont pas identiques. Là où il y avait un zéro sur les entrées des multiplexeurs, on doit envoyer le bon bit de poids faible. Par exemple, reprenons un nombre A, composé des bits a7, a6, a5, a4, a3, a2, a1, a0 ; (cités dans l'ordre). La sortie d'un rotateur arithmétique par 4 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 a3, a2, a1, a0, a7, a6, a5, a4 (on effectue un décalage arithmétique par 4).

Les barell shifters unidirectionnels

Barrel shifter - interface

Dans ce qui précède, on a appris à créer un circuit qui fait des décalages logiques, un autre pour les décalages arithmétiques et un autre pour les rotations. Il nous reste à voir les décaleurs-rotateurs, aussi appelés des barrel shifters, qui sont capables de faire à la fois des décalages et des rotations. Certains décaleur-rotateurs sont capables de faire des rotations et des décalages logiques, d'autres savent aussi réaliser les décalages arithmétiques en plus. Un tel circuit a la même interface qu'un décaleur, sauf qu'on rajoute une entrée qui précise quelle opération faire. Cette entrée indique s'il faut faire un décalage logique, un décalage arithmétique ou une rotation.

Précisons dès maintenant qu'il faut faire la différence entre un barrel shifter unidirectionnel et un barrel shifter bidirectionnel. La différence entre les deux tient dans le sens possible des décalages. Le barrel shifter unidirectionnel ne peut faire que des décalages à gauche ou que des décalages à droite, mais pas les deux. À l'inverse, un barrel shifter bidirectionnel peut faire des décalages à droite et à gauche, suivant ce qu'on lui demande. Dans ce qui va suivre, nous allons nous concentrer sur les barrel shifters qui font des décalages/rotations vers la droite. Les explications seront valides aussi pour des décalages/rotations à gauche, avec quelques petites modifications triviales. Mais nous ne verrons pas comment fabriquer des barrel shifters bidirectionnels. En effet, de tels barrel shifters sont plus compliqués à fabriquer et sont de plus basés sur un barrel shifter unidirectionnel.

Il existe trois grandes méthodes pour fabriquer un décaleur-rotateur.

• La manière la plus naïve est de prendre un décaleur logique, un décaleur arithmétique et un rotateur, et de prendre le résultat adéquat suivant l’opération voulue. Le choix du bon résultat est effectué par une couche de multiplexeur adaptée. Mais cette solution est inutilement gourmande en multiplexeurs. Après tout, les trois circuits se ressemblent et partagent une même structure.
• Une autre solution, bien plus économe en multiplexeurs, élimine ces redondances en fusionnant les trois circuits en un seul. Elle part d'un circuit qui effectue des décalages logiques, auquel on ajoute des multiplexeurs pour le rendre capable de faire aussi les décalages arithmétiques et les rotations.
• La dernière méthode part d'un rotateur et on lui ajoute de quoi faire des décalages logiques.

Le décaleur-rotateur à base de multiplexeurs

Avec la seconde méthode, on part d'un circuit qui effectue des décalages logiques, auquel on ajoute des multiplexeurs pour le rendre capable de faire aussi les décalages arithmétiques et les rotations. Ces nouveaux multiplexeurs ne font que choisir les bits à envoyer sur les entrées des décaleurs. Par exemple, prenons un décalage/rotation par 4 crans. La seule différence entre décalage logique, arithmétique et rotation est ce qu'on met sur les 4 bits de poids fort : un 0 pour un décalage logique, le bit de poids fort pour un décalage arithmétique et les 4 bits de poids faible pour une rotation. Pour choisir entre ces trois valeurs, il suffit de rajouter des multiplexeurs.

La prise en charge des rotations

Nous allons d'abord ajouter des multiplexeurs pour prendre en charge les rotations, un peu de la même manière qu'on modifie un décaleur logique pour lui faire faire aussi des décalages arithmétiques. Pour cela, prenons un décaleur par 4 et étudions les 4 bits de poids fort. Suivant le type de décalage, on doit envoyer soit un zéro, soit le bit de poids faible adéquat sur certaines entrées. Ce choix peut être réalisé par un multiplexeur, tant qu'il est commandé correctement. En clair, il suffit 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 poids faible (rotation). Notons qu'on doit utiliser un multiplexeur par entrée, contrairement au décaleur complet. La raison est qu'un décalage arithmétique envoie toujours le même bit dans les entrées de poids fort, alors qu'une rotation envoie un bit différent sur chaque entrée de poids fort, ce qui demande un multiplexeur par entrée.

Décaleur-rotateur par 4.

La prise en charge des décalages arithmétiques

Il est possible d'étendre le décaleur logique pour lui permettre de faire des décalages arithmétiques. Pour cela, même recette que dans le cas précédent. Encore une fois, suivant le type de décalage, on doit envoyer soit un zéro, soit le bit de poids fort sur certaines entrées. Il est possible d'utiliser un seul multiplexeur dans ce cas précis, car on envoie le même bit sur les entrées de poids fort.

Exemple avec un décaleur par 4.

En combinant des décaleurs basiques par 4, 2 et 1 bits, on obtient un circuit qui fait tous les types de décalages. Pas étonnant que ce circuit soit nommé un décaleur complet. Notons qu'on peut se contenter d'un seul mutiplexeur pour tout le barrel shifter, en utilisant le câblage astucieusement. Après tout, le choix entre 0 ou bit de poids fort est le même pour toutes les entrées concernées. Autant ne le faire qu'une seule fois et connecter toutes les entrées concernées au multiplexeur.

Décaleur complet 8 bits

Le barrel shifter complet

En utilisant les deux modifications en même temps, on se retrouve avec un barrel-shifter complet, capable de faire des décalages et rotations sur 4 bits.

Circuit de rotation partiel.

Les mask barrel shifters

Il est temps de voir la dernière manière possible pour fabriquer un décaleur-rotateur. Celle-ci se base sur les masques, vus au chapitre précédent. L'idée est de faire une rotation et de corriger le résultat si c'est un décalage qui est demandé. La correction à effectuer dépend du type de décalage demandé, suivant qu'il soit logique ou arithmétique. Le circuit complet est organisé comme illustré ci-dessous.

Pour un décalage logique, il suffit de mettre les n bits de poids fort à zéro pour un décalage de n bits vers la droite (inversement, les n bits de poids faible pour un décalage vers la gauche). Et pour mettre des bits de poids fort à zéro sous une certaine condition, on doit utiliser un masque, comme vu précédemment. Le masque en question est le même que celui calculé pour le bit de débordement d'entier. Le masque est calculé par un circuit dédié, avant d'être appliqué au résultat du rotateur. Le circuit de calcul du masque est un encodeur modifié, qu'on peut concevoir avec les techniques des chapitres précédents.

Le circuit d'application du masque est composé d'une couche de portes ET et d'une couche de multiplexeurs. La couche de portes ET applique le masque sur le résultat du rotateur. Les multiplexeurs choisissent entre le résultat du rotateur et le résultat avec masque appliqué. Les multiplexeurs sont commandés par un bit de commande qui indique s'il faut faire un décalage ou une rotation.

Décaleur-rotateur basé sur un masque.

Les barrel shifters bidirectionnels (à double sens de décalage/rotation)

Le circuit précédent est capable d'effectuer des décalages et rotations, mais seulement vers la droite. On peut évidemment concevoir un circuit similaire capable de faire des décalages/rotations vers la gauche, mais il est intéressant d'essayer de créer un circuit capable de faire les deux. Un tel circuit est appelé un barrel shifter bidirectionnel. Notons qu'on doit obligatoirement fournir un bit qui indique dans quelle direction faire le décalage. Précédemment, nous avons vu qu'il existe deux méthodes pour créer un barrel shifter. La première se base sur un décaleur auquel on ajoute de quoi faire les rotations, alors que l'autre se base sur l'application d'un masque en sortie d'un rotateur. Dans ce qui va suivre, nous allons voir comment ces deux types de circuits peuvent être rendus bidirectionnels.

Barrel shifter bidirectionnel - interface

Les barrel shifters bidirectionnels basé sur des multiplexeurs

Commençons par voir comment rendre bidirectionnel un barrel shifter basé sur des multiplexeurs. Pour rappel, ces derniers sont basés sur un décaleur qu'on rend capable de faire des rotations en ajoutant des multiplexeurs.

Une première solution est d'utiliser des barrel shifters bidirectionnels série, série signifiant que les deux sens sont calculés en série, l'un après l'autre. Ils sont composés de décaleurs qui sont capables de faire des décalages/rotations vers la gauche et vers la droite. De tels décaleurs peuvent se concevoir de diverses façons, mais la plus simple se base sur le principe qui veut qu'un décaleur est composé de décaleurs de 1, 2, 4, 8 bits, etc. Chaque décaleur est en double : une version qui décale vers la gauche, et une autre qui décale vers la droite. Lors d'un décalage vers la droite, les décaleurs élémentaire à gauche sont désactivés alors que les décaleurs vers la droite sont actifs (et réciproquement lors d'un décalage à gauche). Le bit qui indique la direction du décalage est envoyé à chaque décaleur et lui indique s'il doit décaler ou non.

Décaleur bidirectionnel

Une autre solution, bien plus simple, est de prendre un décaleur/rotateur vers la gauche et un autre vers la droite, et de prendre la sortie adéquate en fonction de l'opération demandée. Le choix du résultat se fait encore une fois avec une couche de multiplexeurs. Le résultat est ce qu'on appelle un barrel shifter bidirectionnel parallèle, parallèle signifiant que les deux sens sont calculés en parallèle, en même temps. Notons que cette solution ressemble beaucoup à la précédente. À vrai dire, si on prend la première solution et qu'on regroupe ensemble les décaleur/rotateurs allant dans la même direction, on retombe sur un circuit presque identique à un barrel shifter bidirectionnel parallèle.

Les deux techniques précédentes utilisent beaucoup de portes logiques et il est possible de faire bien plus efficace. L'idée est simplement d'inverser l'ordre des bits avant de faire le décalage ou la rotation, puis de remettre le résultat dans l'ordre. Par exemple, pour faire un décalage à gauche, on inverse les bits du nombre à décaler, on fait un décalage à droite, puis on remet les bits dans l'ordre originel, et voilà ! Pour cela, il suffit de prendre un décaleur/rotateur à droite, et d'ajouter deux circuits qui inversent l'ordre des bits : un avant le décaleur/rotateur, un après. Ce circuit d'inversion est une simple couche de multiplexeurs. Le résultat est ce qu'on appelle un barrel shifter bidirectionnel à inversion de bits.

Barrel shifter à inversion de bits.

Le décaleur-rotateur bidirectionnel basé sur des masques

Dans cette section, nous allons voir concevoir un rotateur bidirectionnel avec des masques. Pour cela, il faut juste créer un rotateur bidirectionnel et utiliser des masques pour obtenir des décalages.

Le rotateur bidirectionnel

Pour créer le rotateur bidirectionnel, nous allons devoir étudier ce qui se passe quand on enchaine deux rotations successives. N'allons pas par quatre chemins : l'enchainement de deux rotations successives donne un résultat qui aurait pu être obtenu en ne faisant qu'une seule rotation. Le résultat issu de la succession de deux rotations est identique à celui d'une rotation équivalente. Et on peut calculer le nombre de rangs de la rotation équivalente à partir des rangs des deux rotations initiales. Pour cela, il suffit d'additionner les rangs en question. Par exemple, faire une rotation à droite par 5 rangs suivie d'une rotation à droite de 8 rangs est équivalent à faire une rotation à droite de 5+8 rangs, soit 13 rangs.

La logique est la même quand on enchaine des rotations à droite et à gauche. Il suffit de compter les rangs d'une rotation en les comptant positifs pour une rotation à droite et négatifs pour une rotation à gauche. Par exemple, une rotation de -5 rangs sera une rotation à gauche de 5 rangs, alors qu'une rotation de 10 rangs sera une rotation à droite de 10 rangs. On pourrait faire l'inverse, mais prenons cette convention pour l'explication qui suit. Toujours est-il qu'avec cette convention, l'addition des rangs donne le bon résultat pour la rotation équivalente. Par exemple, si je fais une rotation à droite de 15 rangs et une rotation à gauche de 6 rangs, le résultat sera une rotation de 15-6 rangs : c'est équivalent à une rotation à droite de 9 rangs.

Faisons dès maintenant remarquer quelque chose d'important. Prenons un nombre de n bits. Avec un peu de logique et quelques expériences, on remarque facilement qu'une rotation par $n$ ne fait rien, dans le sens où les bits reviennent à leur place initiale. Une rotation par $n$ est donc égale à pas de rotation du tout, ce qui est équivalent à faire une rotation par zéro rangs. Ce détail sera utilisé par la suite. Pour le moment, il nous permet de gérer le cas où l'addition de deux rangs donne un résultat supérieur à $n$. Par exemple, prenons une rotation par 56 rangs pour un nombre de 9 bits. La division nous dit que 56 = 9*6 + 2. En clair, faire un décalage par 56 rangs est équivalent à faire 6 rotations totales par 9, suivie d'une rotation par 2 rangs. Les rotations par 9 ne comptant pas, cela revient en fait à faire une rotation par 2 rangs. Le même raisonnement fonctionne dans le cas général, et revient à faire ce qu'on appelle l'addition modulo n. C'est à dire qu'une fois le résultat de l'addition connu, on le divise par $n$ et l'on garde le reste de la division. Avec cette méthode, le nombre de rangs de la rotation équivalente est compris entre 0 et $n-1$.

Les additions modulo n seront notées comme suit : $(a+b)\mod n$.

Armé de ces explications, on peut maintenant expliquer comment fonctionne le rotateur bidirectionnel. L'idée derrière ce circuit est de remplacer une rotation à droite par une rotation équivalente. Dans ce qui suit, nous utiliserons la notation suivante : $r_{\text{équivalent}}$ est le nombre de rangs de la rotation équivalente, $n$ la taille du nombre à décaler et $r$ le nombre de rangs du décalage initial. En soi, ce n'est pas compliqué de trouver une rotation équivalente : une rotation à droite de $r$ rangs est équivalente à une rotation de $r+n$ rangs, à une rotation de $r+2\times n$ rangs, et de manière générale à toute rotation de $r+k\times n$ rangs. La raison est que les rotations par n ne comptent pas, elles sont éliminées par la division par $n$. Mais les propriétés des calculs modulo n font que cela marche aussi quand on retranche n. Les bizarreries de l'arithmétique modulaire font que, quand on fait les additions modulo n, on peut remplacer tout nombre positif r par $r\pm k\times n$ sans changer les résultats. Pour résumer, on a :

$r_{\text{équivalent}}=(r\pm k\times n)\mod n$

L'équation précédente dit qu'il suffit d'ajouter ou de retrancher n autant de fois qu'on veut au nombre de rangs initial, pour obtenir le nombre de rangs équivalent. Mais tous les cas possibles ne nous intéressent pas. En effet, on sait que le nombre de rangs de la rotation équivalente est compris entre 0 et $n-1$. Le résultat que l'on recherche doit donc être compris entre 0 et $n-1$. Et seul un cas respecte cette contrainte : celui où l'on retranche n une seule fois. On a alors :

$r_{\text{équivalent}}=r-n$

L'équation nous dit qu'il est possible de remplacer une rotation à droite par une rotation à gauche équivalente. Par exemple, sur 8 bits et pour une rotation à droite de 6 bits, on a $r_{\text{équivalent}}=6-8=-2$. En clair, la rotation équivalente est ici une rotation à gauche de 2 crans. Vous pouvez essayer avec d'autres exemples, vous trouverez la même chose. Par exemple, sur 16 bits, une rotation à gauche de 3 rangs est équivalente à une rotation à droite de 13 rangs.

Le calcul ci-dessus peut être simplifié en utilisant quelques astuces. Sur la plupart des ordinateurs, n est égal à 8, 16, 32, 64, ou toute autre nombre de la forme $2^{n}$. Les cas où n vaut 3, 7, 14 ou autres sont tellement rares que l'on peut les considérer comme anecdotiques. De plus, $r$ est compris entre 0 et $n-1$. On peut donc coder le rang sur un nombre bien précis de bits, tel que n est la valeur haute de débordement (en clair, n-1 est la plus grande valeur codable, n entraine un débordement d'entier). Grâce à cela, on peut coder le nombre de rangs en complément à un ou en complément à deux. Rappelons que ces deux représentations des nombres utilisent l'arithmétique modulaire, c'est à dire que l'addition et la soustraction se font modulo n, et que leur principe est de représenter tout n négatif par un n positif équivalent. Ainsi, tout $r_{\text{équivalent}}$ négatif est codé par un $r$ positif équivalent. Et dans ces représentations, on a obligatoirement $r-n=-r$. En appliquant cette formule dans l'équation précédente, on a :

$r_{\text{équivalent}}=-r$

Reprenons l'exemple d'une rotation à gauche de 2 crans pour un nombre de 8 bits, ce qui est équivalent à une rotation de 6 crans à droite: on a bien 6 = -2 en complément à deux. Reste à faire le calcul ci-dessus par le circuit de rotation.

En complément à un, le calcul de l'opposé d'un nombre consiste simplement à inverser les bits de $r_{\text{initial}}$. En conséquence, le circuit est plus simple en complément à un. Le calcul du nombre de rangs demande juste un inverseur commandable, qu'on sait fabriquer depuis quelques chapitres.

Rotateur bidirectionnel en complément à un.

En complément à deux, le calcul est le suivant :

$r_{\text{équivalent}}={\overline {r_{\text{initial}}}}+1$

On pourrait utiliser un circuit pour faire l'addition, mais il y a une autre manière plus simple de faire. L'idée est simplement de prendre le circuit en complément à un et d'y ajouter de quoi corriger le résultat final. En clair, on fait le calcul comme en complément à un, mais la rotation effectuée ne sera pas équivalente, du fait du +1 dans le calcul. Ce +1 indique simplement qu'il faut décaler le résultat obtenu d'un cran supplémentaire. Pour cela, on ajoute un rotateur d'un cran à la fin du circuit.

Rotateur bidirectionnel en complément à deux.

Le circuit final

On peut transformer ce circuit en décaleur-rotateur en appliquant la méthode vue plus haut, à savoir en appliquant un masque en sortie du rotateur. Le circuit obtenu est le suivant :

Décaleur rotateur bidirectionnel basé sur un masque.