Fonctionnement d'un ordinateur/Les registres à décalage et les LSFR

Les registres à décalage sont des registres dont le contenu est décalé d'un cran vers la gauche ou la droite sur commande. Il seront beaucoup utilisés dans ce cours, bien que moins que les registres normaux. Les registres à décalage sont presque tous synchrones et ce chapitre ne parlera que ce ces derniers. L'animation suivante illustre le fonctionnement d'un registre à décalage qui décale son contenu d'un cran vers la droite à chaque cycle d'horloge.

On peut classer les registres selon le caractère de l'entrée et de la sortie, qui peut être parallèle (entrée de plusieurs bits) ou série (entrée d'un seul bit).

Sur les registres simples, les entrées et sorties pour les données sont toujours parallèles. Pour un registre de N bits, il y a une entrée d'écriture de N bits et une sortie de N bits. C'est la raison pour laquelle ils sont appelés des registres à entrées et sorties parallèles.
Sur les registres à entrée et sortie série, on peut mettre à jour un bit à la fois, de même qu'on ne peut en récupérer qu'un à la fois. Ces registres servent essentiellement à mettre en attente des bits tout en gardant leur ordre : un bit envoyé en entrée ressortira sur la sortie après plusieurs commandes de mise à jour sur l'entrée Enable.
Les registres à décalage à entrée série et sortie parallèle sont similaires aux précédents : on peut ajouter un nouveau bit en commandant l'entrée Enable et les anciens bits sont alors décalés d'un cran. Par contre, on peut récupérer (lire) tous les bits en une seule fois. Ils permettent notamment de reconstituer un nombre qui est envoyé bit par bit sur un fil (un bus série).
Enfin, il reste les registres à entrée parallèle et sortie série. Ces registres sont utiles quand on veut transmettre un nombre sur un fil : on peut ainsi envoyer les bits un par un.

Pour résumer, on distingue quatre types de registres (à décalage ou non), qui portent les noms de PIPO, PISO, SIPO et SISO. Les noms peuvent sembler barbares, mais il y a une logique derrière ces termes.La lettre P est pour parallèle, la lettre S est pour série. La lettre I signifie Input, ce qui veut dire entrée en anglais, la lettre O est pour Output, la sortie en anglais.

Classification des registres
	Entrée parallèle	Entrée série
Sortie parallèle	PIPO (registre simple)	SIPO
Sortie série	PISO	SISO

L'intérieur d'un registre à décalage

Tous les registres sont conçus en plaçant plusieurs bascules les unes à la suite des autres, que ce soit pour les registres simples ou les registres à décalage. La seule différence tient dans la manière dont les bascules sont reliées. Toutes les bascules sont reliées à l'entrée d'horloge, l'entrée Enable, l'entrée Reset, ou aux autres entrées de commandes. Mais c'est une autre paire de manche pour les entrées/sorties de données.

Dans un registre simple, les bascules sont indépendantes et ne sont pas reliées entre elles.

À l'inverse, dans les registres à décalage, il existe des connexions entre bascules. Plus précisément, les bascules sont reliées les unes à la suite des autres, elles forment une chaîne de bascules reliées deux à deux. Et les connexions entre bascules sont les mêmes que l'on parle d'un registre à décalage de type SIPO, PISO ou SISO.

Outre le fait que les bascules sont reliées de la même manière, les autres connexions sont les mêmes dans tous les registres. L'entrée d'horloge (non-représentée dans les schémas qui vont suivre) est envoyée à toutes les bascules. Même chose pour l'entrée Enable, qui est reliée aux entrées E de toutes les bascules. La différence entre ces registres tient dans les endroits où se trouvent les entrées et les sorties du registre.

Implémentation des registres avec des bascules.
Registre à entrée et sortie série.	Registre à entrée et sortie parallèle.
Registre à entrée série et sortie parallèle.	Registre à entrée parallèle et sortie série.

Les compteurs basés sur des registres à décalage

Les registres à décalage peuvent être utilisés pour implémenter des compteurs. Les compteurs en question peuvent être des compteurs classiques, qui comptent en binaire. De tels compteurs sont appelés des compteurs asynchrones, bien que ce soit un abus de langage. Une autre utilisation est celle des compteurs one hot, qui ne comptent pas en binaire normal. Voyons ces deux utilisations dans ce qui suit.

Les mal-nommés compteurs asynchrones

Les compteurs asynchrones n'utilisent pas de circuit incrémenteur. A la place, ils sont fabriqués à partir d'un registre à décalage. Ils utilisent moins de portes logiques que les compteurs synchrones. Et ils ne sont pas forcément plus difficiles à comprendre. Précisons cependant qu'ils sont très mal nommés, à savoir que ce sont bien des circuits synchrones.

Pour comprendre comment fonctionne un compteur asynchrone, il faut regarder la séquence des premiers entiers :

000 ;
001 ;
010 ;
011 ;
100 ;
101 ;
110 ;
111.

Il faut remarquer que le bit de poids faible s'inverse à chaque cycle d'horloge. Pour les colonnes suivantes, le bit s'inverse quand le bit de la colonne précédente passe de 1 à 0, lors d'un front descendant sur la colonne précédente. Maintenant que l'on sait cela, on peut créer un compteur avec des bascules T (elles inversent leur contenu à chaque cycle d'horloge). La première colonne inverse son contenu à chaque cycle, elle correspond donc à une bascule T reliée directement à l'horloge. Les autres colonnes utilisent des bascules T activées sur front descendant.

Attention, la bascule la plus à gauche stocke le bit de poids faible, pas celui de poids fort. Cela sera pareil dans tous les schémas qui suivront.

Le compteur précédent ne peut pas être réinitialisé, ce qui pose des problèmes pour implémenter des compteurs modulo. Pour cela, il faut que les bascules du compteur aient une entrée de réinitialisation Reset, qui les force à se remettre à zéro. Il suffit alors de connecter ensemble les entrées Reset des bascules à l'entrée Reset du compteur.

Implémenter un compteur modulo demande d'ajouter un comparateur qui détecte quand la valeur maximale est atteinte, afin de commander l'entrée de réinitialisation. Un tel circuit est juste un comparateur avec une constante, que vous savez déjà fabriquer à cet endroit du cours.

Il est aussi possible d'utiliser des bascules D à la place des bascules T simplifiées. En effet, une bascule T simplifiée est identique à une bascule D dont on boucle la sortie /Q sur l'entrée de données. Cette implémentation permet d'ailleurs de réinitialiser le compteur à une valeur non-nulle. Pour cela, l'entrée de chaque bascule D est précédée d'un multiplexeur, qui choisit entre le bit calculé par le compteur et celui présenté sur l'entrée de ré-initialisation. Quand l'entrée Reset est activée, les multiplexeurs connectent les bascules aux bits sur l'entrée de ré-initialisation. Dans le cas contraire, le compteur fonctionne normalement, les multiplexeurs connectant l'entrée de chaque bascule à sa sortie.

Pour finir, la sortie de débordement n'est autre que la sortie de la dernière bascule, celle qui contient le bit de poids fort.

Les compteurs one-hot

Les compteurs one-hot sont appelés ainsi, car ils permettent de compter dans une représentation des nombres appelée la représentation one-hot. Pour rappel, dans une telle représentation, un seul bit est à 1 pendant que les autres sont à 0. Les entiers sont codés de la manière suivante : le nombre N est encodé en mettant le énième bit à 1, avec la condition que l'on commence à compteur à partir de zéro. Il est important de remarquer que dans cette représentation, le zéro est n'est PAS codé en mettant tous les bits à 0, la valeur 0000...0000 est une valeur interdite. À la place, le zéro est codé en mettant le bit de poids faible à 1. Pour N bits, on peut encoder seulement N valeurs, dont le zéro.

Décimal	Binaire	One-hot
0	000	00000001
1	001	00000010
2	010	00000100
3	011	00001000
4	100	00010000
5	101	00100000
6	110	01000000
7	111	10000000

Un compteur en représentation one-hot contient un nombre codé de cette manière, qui est incrémenté ou décrémenté si besoin. Pour donner un exemple, la séquence d'un compteur en anneau de 4 bits est :

0001 (0) ;
0010 (1) ;
0100 (2) ;
1000 (3) .

Un compteur one-hot basique est composé d'un registre à décalage dont on boucle la sortie sur son entrée. En faisant cela, on garantit que le registre revient à zéro lors d'un débordement, zéro étant codé avec un 1 dans le bit de poids faible. Au passage, si vous ne mettez que des 0 dans un compteur en anneau, il restera bloqué pour toujours : décaler une suite de 0 donnera la même suite de 0. Initialiser un compteur one-hot demande donc quelques subtilités qu'on détaillera plus bas.

Un compteur one-hot de N bits peut prendre N valeurs différentes, qui ont toutes un seul bit à 1. Pour 5 bits, la séquence est illustrée ci-dessous.

Compteur en anneau de 5 bits.

Faire des comparaisons avec ce type de compteur est très simple : le compteur contient la valeur N si le énième bit est à 1. Pas besoin d'utiliser de circuit comparateur, juste de lire un bit. Par contre, ce compteur n'est pas très économe en bascules. Imaginons que l'on veut un compteur qui compte jusqu'à une valeur N arbitraire : un compteur binaire normal utilisera environ $\log _{2}{(N)}$ bascules, alors qu'un compteur one-hot demande N bascules. Mais si N est assez petit, l'économie de bascules est assez faible, alors que l'économie de circuits comparateurs/incrémenteurs l'est beaucoup plus.

Il y a peu d'applications qui utilisent des compteurs en anneau. Ils étaient autrefois utilisés dans les tous premiers ordinateurs, notamment ceux qui géraient une représentation des nombres spécifique appelée la Bi-quinary coded decimal. De nos jours, de tels compteurs sont utilisés dans les séquenceurs de processeurs, mais aussi dans les séquenceurs de certains périphériques, ou dans les circuits séquentiels simples qui se résument à des machines à états. Ils sont alors utilisés car très rapides, parfaitement adaptés au stockage de petites valeur, et surtout : ils n'ont pas besoin de circuit comparateur pour connaitre la valeur stockée dedans. Nous n'allons pas rentrer dans le détail de leurs utilisations, car nous en reparlerons dans la suite du cours.

Les registres à décalage à rétroaction linéaire

Les registres à décalage à rétroaction linéaire sont des registres à décalages un peu particuliers. Le terme anglais pour de tels registres est Linear Feedback Shift Register, ce qui s’abrège en LFSR. Nous utiliserons cette abréviation dans ce qui suit pour simplifier grandement l'écriture.

Les LFSR sont appelés ainsi pour plusieurs raisons. Déjà, registre à décalage implique qu'ils sont fabriqués avec un registre à décalage. À rétroaction indique que l'on boucle la sortie sur l'entrée. Le terme combinaison linéaire demande quelques explications. L'idée est qu'entre la sortie et l'entrée, il y a un circuit combinatoire qui s'intercale entre la sortie et l'entrée, qui calcule ce qu'il faut mettre sur l'entrée, à partir du contenu du registre

Pour simplifier, cela veut dire qu'on multiplie chaque bit par 0 ou 1, avant d'additionner le tout. Dans ce calcul, on ne garde qu'un seul bit du résultat, vu que l'entrée du registre à décalage ne fait qu'un bit. Par simplicité, on ne garde que le bit de poids faible. Or, il s'avère que cela simplifie grandement les calculs, car cela permet de remplacer les additions par une simple opération XOR.

1\times a_{n}\oplus ...+1\oplus a_{3}+1\oplus a_{1}

Le résultat est ce que l'on appelle un LFSR de Fibonacci, ou encore un LFSR classique, qui celui qui colle le mieux avec la définition.

Registre à décalage à rétroaction de Fibonnaci.

Les registres à décalages à rétroaction affine sont identique aux précédents à une différence près : le bit calculé est inversé avant d'être inséré dans le registre. Un tel circuit est donc composé de portes NXOR, comparé à son comparse linéaire, composé à partir de portes XOR. Petite remarque : si je prends un registre à rétroaction linéaire et un registre à rétroaction affine avec les mêmes coefficients sur les mêmes bits, le résultat du premier sera égal à l'inverse de l'autre.

Les LSFR de Gallois sont un peu l'inverse des LFSR vus juste avant. Au lieu d'utiliser un registre à décalage SIPO, ils utilisent un registre à décalage PISO. Pour faire la différence, nous appellerons ces derniers les LFSR PISO, et les premiers LFSR SIPO. Avec les LFSR PISO, on prend le bit sortant et on en déduit plusieurs bits à partir d'un circuit combinatoire, qui sont chacun insérés dans le registre à décalage à un endroit bien précis. Bien sûr, la fonction qui calcule des différents bits à partir du bit d'entrée conserve les mêmes propriétés que celle utilisée pour les LFSR : elle se calcule avec uniquement des portes XOR, ou NXOR pour leur variante affine.

Leur avantage est qu'ils sont plus rapides, car il n'y a qu'une seule porte logique entre la sortie et une entrée du registre à décalage, contre potentiellement plusieurs avec les LFSR SIPO. Notons que tout comme les LFSR qui ne peuvent pas mémoriser un 0, de tels registres à décalage à rétroaction ne peuvent pas avoir la valeur maximale stockable dans le registre. Cette valeur gèle le registre à cette valeur, dans le sens où le résultat au cycle suivant sera identique. Mais cela ne pose pas de problèmes pour l'initialisation du compteur.

Quelques propriétés sont communes à tous les LSFRs. Un LSFR est déterministe : pour le même résultat en entrée, il donnera toujours le même résultat en sortie. De plus, il ne peut contenir qu'un nombre fini de valeurs. Et ces deux propriétés sont source de comportements qu'on va détailler ci-dessous.

L'initialisation d'un LSFR

Les LSFR ne peuvent pas être initialisés à une valeur arbitraire, en raison de la présence d'une valeur interdite. Concrètement, une fois que le décompte arrive sur une valeur interdite, le compteur reste bloqué sur cette valeur. La valeur suivante, calculée par le compteur, est cette valeur elle-même.

Le premier cas est celui où le compteur peut être initialisé avec zéro sans que cela ne pose problème. Sur de tels LSFRs, la réinitialisation se fait comme pour n'importe quel registre/compteur. A savoir que les entrées de reset des bascules sont toutes connectées ensemble, au même signal de reset.

Le second cas est celui des LFSR non-affine. Lors de la réinitialisation, il faut que toutes les bascules soient réinitialisées à 0, sauf une qui est mise à 1. La bascule en question doit disposer d'une entrée S (Set) qui met la bascule à 1 quand elle est activée. Cela garantit que le registre est réinitialisé avec un zéro codé en one-hot.

Une autre solution est de mettre un multiplexeur juste avant l'entrée du registre à décalage. Cette solution marché bien dans le sens où elle permet d'initialiser le registre avec une valeur arbitraire, qui est insérée dans le registre en plusieurs cycles. Pour les LFSR, le multiplexeur est connecté soit au bit calculé par les portes XOR, soit par une entrée servant uniquement de l'initialisation.

La période d'un LSFR

Si le compteur est initialisé correctement, il passera d'une valeur à l'autre et finira par repasser par une valeur qu'il aura déjà parcourue et son fonctionnement se reproduira à l'identique comparé à son passage antérieur, il bouclera. Il parcourt un nombre N de valeurs à chaque cycle, ce nombre étant appelé la période du compteur.

La période d'un LSFR dépend fortement de la fonction utilisée pour calculer le bit de sortie. Dans le meilleur des cas, le LSFR passera par toutes les valeurs que le registre peut prendre, sauf une : suivant le registre, le zéro ou sa valeur maximale sont interdits. Si un LSFR passe par zéro, il y reste bloqué définitivement. La raison à cela est simple : un XOR sur des zéros donnera toujours 0. Le même raisonnement peut être tenu pour les registres à rétroaction affine, sauf que cette fois-ci, c'est la valeur maximale stockable dans le registre qui est fautive.

Tout le chalenge consiste donc à trouver quels sont les LSFR dont la période est maximale : ceux dont la période vaut $2^{n}-1$ . Qu'on se rassure, quelle que soit la longueur du registre, il en existe au moins un : cela se prouve mathématiquement.

Exemple avec un registre à rétroaction linéaire de 4 bits.

La génération de nombres pseudo-aléatoires

Les LSFRs peuvent aussi être utilisés pour générer des nombres "aléatoires". Je dis aléatoires entre guillemets, car ils ne sont pas vraiment aléatoires, mais s'en rapprochent suffisamment pour être considérés comme tels. Pour mettre en avant cela, on parle aussi de nombres "pseudo-aléatoires". De nombreuses situations demandent de générer des nombres pseudo-aléatoire de manière matérielle. Cela peut servir pour sélectionner une ligne de cache à remplacer lors d'un défaut de cache, pour implémenter des circuits cryptographiques, pour calculer la durée d'émission sur un bus Ethernet à la suite d'une collision, et j'en passe.

Les méthodes que nous allons voir produisent un nombre pseudo-aléatoire un bit à la fois, à quelques exceptions près. Les circuits que nous allons voir fournissent un bit sur leur sortie et ce bit varie de manière assez aléatoire. Les bits en sortie du circuit sont accumulés dans un registre à décalage normal, pour former un nombre aléatoire. Nous appellerons ce registre : l'accumulateur.

L'usage de registres à décalage à rétroaction

Un LSFR seul ne fournit pas un aléatoire digne de ce nom, mais il est possible de combiner plusieurs LSFR pour obtenir une meilleure approximation de l'aléatoire. Avec cette technique, plusieurs registres à décalages à rétroaction sont reliés à un circuit combinatoire non-linéaire. Ce circuit prendra en entrée un (ou plusieurs) bit de chaque registre à décalage à rétroaction, et combinera ces bits pour fournir un bit de sortie.

Pour rendre le tout encore plus aléatoire, il est possible de cadencer les LSFR à des fréquences différentes. Cette technique est utilisée dans les générateurs stop-and-go, alternative step, et à shrinking.

Le générateur alternative step utilise trois LSFR. Le premier commande un multiplexeur qui choisit la sortie parmi les deux restants.
Le générateur stop-and-go utilise deux LSFR. Le premier est relié à l'entrée d'horloge du second et le bit de sortie du second est utilisé comme résultat. Une technique similaire était utilisée dans les processeurs VIA C3, pour l'implémentation de leurs instructions cryptographiques.
Le shrinking generator utilise deux LSFR cadencés à des vitesses différentes. Si le bit de sortie du premier vaut 1, alors le bit de sortie du second est utilisé comme résultat. Par contre, si le bit de sortie du premier vaut 0, aucun bit n'est fourni en sortie, le bit de sortie du second registre est oublié.

L'aléatoire généré par des timers ou des compteurs d'horloge

Au-delà des LSFR, il est possible d'utiliser des compteurs pour générer du pseudo-aléatoire. Par exemple, une technique très simple utilise un simple timer. Si on a besoin d'un nombre pseudo-aléatoire, il suffit de lire le timer et d'utiliser le nombre lu comme nombre pseudo-aléatoire. Si le délai entre deux demandes est irrégulier, le résultat semblera aléatoire. Mais il s'agit là d'une technique assez peu fiable dans le monde réel et seules quelques applications bien spécifiques se satisfont de cette méthode.

Une solution un peu plus fiable utilise ce qu'on appelle la dérive de l'horloge. Il faut savoir qu'un signal d'horloge n'est jamais vraiment très précis. Une horloge censée tourner à 1 Ghz ne tournera pas en permanence à 1Ghz exactement, mais verra sa fréquence varier de quelques Hz ou Khz de manière irrégulière. Ces variations peuvent venir de variations aléatoires de température, des variations de tension, des perturbations électromagnétiques, ou à des phénomènes assez compliqués qui peuvent se produire dans tout circuit électrique (comme le shot noise).

L'idée la plus simple utilise deux horloges : une horloge lente et une horloge rapide, dont la fréquence est un multiple de l'autre. Par exemple, on peut choisir une fréquence de 1 Mhz et une autre de 100 Hz : la fréquence la plus grande est égale à 10000 fois l'autre. La dérive d'horloge fera son œuvre, les deux horloges seront très légèrement désynchronisées en permanence, et cette désynchronisation peut être utilisée pour produire des nombres aléatoires. Par exemple, on peut compter le nombre de cycles d'horloge produit par l'horloge rapide durant une période de l'horloge lente. Si ce nombre est pair, on produit un bit aléatoire qui vaut 1 , il vaut 0 si ce nombre est pair. Pour information, c'est exactement cette technique qui était utilisée dans l'Intel 82802 Firmware Hub.

Il existe d'autres solutions matérielles qui utilisent le bruit thermique. Tous les circuits électroniques de l'univers sont soumis à de microscopiques variations de température, dues à l'agitation thermique des atomes. Plus la température est élevée, plus les atomes qui composent les fils métalliques des circuits s'agitent. Vu que les particules d'un métal contiennent des charges électriques, ces vibrations font naître des variations de tensions assez infimes. Il suffit d'amplifier ces variations pour obtenir un résultat capable de représenter un zéro ou un 1. Ce principe a été utilisé sur des anciens processeurs Intel qui géraient l'instruction RDRAND, une instruction qui produisait un nombre aléatoire.

◄ Retour vers « Les compteurs et timers »

Sommaire du livre

Continuer vers « Les circuits de décalage et de rotation » ►