Barrel shifter

Un barrel shifter est un circuit électronique capable d'effectuer des opérations de décalage et de rotation binaires. Ce circuit est très souvent utilisé dans un processeur. Il peut être intégré dans une unité de calcul, ou constituer une unité de calcul à part entière.

Opérations

Décalages

Il existe deux grands types de décalages : les décalages logiques, et les décalages arithmétiques.

Décalages logiques

Décalage logique

Le décalage logique, aussi appelé logical shift, consiste à décaler tous les chiffres d'un ou plusieurs crans vers la gauche ou la droite. Lors du décalage, des vides apparaissent dans la représentation binaire du nombre : ceux-ci sont alors remplis avec des zéros.

Grâce à ce remplissage par des zéros, un décalage vers la gauche de n rangs est équivalent à une multiplication par $2^{n}$ pour des entiers non-signés ou pour des entiers signés positifs. Même chose pour le décalage vers la droite qui revient à diviser un nombre entier par $2^{n}$. Avec des nombres signés, ce n'est pas le cas : on obtient un résultat qui n'a pas grand sens mathématiquement.

Cette propriété est souvent utilisée par certains compilateurs, qui préfèrent utiliser des instructions de décalages (qui sont des instructions très rapides) à la place d'instructions de multiplication ou de division qui ont une vitesse qui va de moyenne (multiplication) à particulièrement lente (division).

Il faut remarquer un petit détail : lorsqu'on effectue un décalage à droite -, certains bits de notre nombre vont sortir du résultat et être perdus. Cela a une conséquence : le résultat est tronqué ou arrondi. Plus précisément, le résultat d'un décalage à droite de n rangs sera égal à la partie entière du résultat de la division par $2^{n}$.

Décalages arithmétiques

Décalage arithmétique

Les décalages arithmétiques sont similaires aux décalages logiques, à un détail près : pour les décalages à droite, le bit de signe de notre nombre n'est pas modifié, et on remplit les vides laissés par le décalage avec le bit de signe.

Ces instructions sont équivalentes à une multiplication/division par $2^{n}$, que le nombre soit signé ou non, à un détail près : l'arrondi n'est pas fait de la même façon pour les nombres positifs et négatifs. Pour donner un exemple, ${\frac {9}{2}}$ sera arrondi en 4, tandis que ${\frac {-9}{2}}$ sera arrondi en -5.

Rotations

Rotation de bits

Les rotations sont similaires aux décalages, à ceci près que chaque bit sortant est réinjecté à la place libérée par le décalage.

Ces opérations sont très utiles en cryptographie, notamment dans certains algorithmes de chiffrement. Les rotations sont aussi très utiles dans certains cas particuliers dans lesquels on doit manipuler des données bit par bit. Par exemple, un calcul du nombre de bits à 1 dans un nombre peut s'implémenter de façon naïve avec des instructions de rotation.

Implémentation

Multiplexeur 2 to 1

Tous les barrels shifters sont conçus avec des couches de multiplexeurs. Ces multiplexeurs sont des circuits électroniques dont le rôle est de recopier le contenu d'une des entrées sur sa sortie. Ce multiplexeur permet de choisir l'entrée qu'on veut recopier sur la sortie : pour cela, notre multiplexeur contient une entrée de commande qui permet de spécifier quelle entrée doit être recopiée. Dans les barrels shifters, les multiplexeurs utilisés possèdent deux entrées et une sortie, et ressemblent à celui illustré dans le schéma de droite.

La table de vérité d'un multiplexeur est assez simple. Dans ce qui suit, on nommera les deux entrées du multiplexeur E1 et E2, sa sortie S, et son entrée de commande C. La table de vérité du circuit ressemble donc à cela :

Mux 2 to 1 implementation

Titre

Entrée C	Entrée E1	Entrée E2		Sortie S
0	0	0		0
0	0	1		0
0	1	0		1
0	1	1		1
1	0	0		0
1	0	1		1
1	1	0		0
1	1	1		1

Décalages logiques

Décaleur logique - principe

Un circuit capable d'effectuer des décalages logiques est conçu sur un principe très simple. Par exemple, décaler un nombre de 7 rangs vers la droite, c'est le décaler de 4 rangs, puis le décaler de 2, puis le décaler de 1. On voit que notre décalage par 7 peut être décomposé en plusieurs sous-décalages par 4, 2 et 1. Et bien c'est la même chose pour tous les autres décalages : ceux-ci peuvent être décomposés en décalages de n rangs, avec n une puissance de 2.

On peut ensuite profiter du fait que l'écriture binaire de notre nombre nous permet de connaitre exactement quelles sont ces puissances de 2. Pour chaque bit à 1 dans la représentation binaire de notre nombre de rangs, on doit effectuer un décalage égal à $2^{P}$, avec P le poids du bit en question. Il ne reste plus qu'à construire des décaleurs par 1, 2, 4, 8, 16, etc.