Fonctionnement d'un ordinateur/Les circuits compteurs et décompteurs

Les compteurs/décompteurs sont des circuits électroniques qui mémorisent un nombre qu'ils mettent à jour régulièrement. Pour donner un exemple d'utilisation, imaginez un circuit qui compte le nombre de voitures dans un parking dans la journée. Pour cela, vous allez prendre deux circuits qui détectent respectivement l'entrée ou la sortie d'une voiture, et un compteur. Le compteur est initialisé à 0 quand le parking est vide, puis est incrémenté à chaque entrée de voiture, décrémenté à chaque sortie. A chaque instant, le compteur contient le nombre de voitures dans le parking. C'est là un exemple d'un compteur, mais les exemples où on a besoin d'un circuit pour compter quelque chose sont nombreux.

L'incrémentation ou décrémentation d'un compteur augmente ou diminue le compteur d'une quantité fixe, appelée le pas du compteur. Suivant la valeur du pas, on fait la différence entre les compteurs d'un côté et les décompteurs de l'autre. Comme leur nom l'indique, les compteurs comptent alors que les décompteurs décomptent. Les compteurs augmentent le contenu du compteur à chaque mise à jour, alors que les décompteurs le diminuent. Dit autrement, le pas d'un compteur est positif, alors que le pas d'un décompteur est négatif. Les compteurs-décompteurs peuvent faire les deux, suivant ce qu'on leur demande.

Les compteurs/décompteurs : généralités

Les compteurs et décompteurs sont très variés et ils se distinguent sur un grand nombre de points.

La plupart des compteurs utilisent un pas constant, qui est fixé à la création du compteur, ce qui simplifie la conception du circuit. Par exemple, les compteurs incrémenteurs/décrémenteurs ont un pas fixe de 1, à savoir que le contenu de leur registre est incrémenté de 1 à chaque cycle d'horloge ou demande d'incrémentation. D'autres ont un pas variable, à savoir qu'il change à chaque incrémentation/décrémentation. Cela peut aussi servir à compter quelque chose qui varie de manière non-régulière. Par exemple, imaginez un circuit qui compte combien de voitures sont rentrées sur une autoroute par un péage bien précis. Plusieurs voitures peuvent rentrer sur le péage durant la même minute, presque en même temps. Pour cela, il suffit de prendre un compteur à pas variable, qui est incrémenté du nombre de voiture rentrées sur l'autoroute lors de la dernière période de temps. Évidemment, de tels compteurs à pas variables ont une entrée supplémentaire sur laquelle on peut envoyer le pas du compteur.

Suivant le compteur, la représentation du nombre mémorisé change : certains utilisent le binaire traditionnel, d'autres le BCD, d'autre le code Gray, etc. Mais tous les compteurs que nous allons voir seront des compteurs/décompteurs binaires, à savoir que les nombres qu'ils utilisent sont codés sur $n$ bits. Au passage, le nombre de bits $n$ du compteur est appelé la taille du compteur, par analogie avec les registres.

Vu que la taille d'un compteur est limitée, il cesse de compter au-delà d'une valeur maximale. La plupart des compteurs comptent de 0 à $2^{n}-1$ , avec $n$ la taille du compteur. D'autres compteurs ne comptent pas jusque-là : leur limite est plus basse que $2^{n}-1$ . Par exemple, certains compteurs ne comptent que jusqu'à 10, 150, etc. Ils sont appelés des compteurs modulo. Prenons un compteur modulo 6, par exemple : il compte de 0 à 5, et est remis immédiatement à zéro quand il atteint 6. Il compte donc comme suit : 0, 1, 2, 3, 4, 5, 0, 1, 2, ...

Outre la valeur de la limite du compteur, il est aussi intéressant de se pencher sur ce qui se passe quand le compteur atteint cette limite. Certains restent bloqués sur cette valeur maximale tant qu'on ne les remet pas à zéro "manuellement" : ce sont des compteurs à saturation. D'autres recommencent à compter naturellement à partir de zéro : ce sont des compteurs modulaires.

L'interface d'un compteur/décompteur

Compteurs et décompteurs sont presque tous des circuits synchrones, à savoir cadencés par une horloge. Du moins, c'est le cas des compteurs/décompteurs que nous allons voir dans ce chapitre, par souci de simplicité. Un compteur/décompteur est donc relié à une entrée d'horloge.

De plus, certains compteurs ont une entrée Enable qui active/désactive le comptage. Le compteur s'incrémente/décrémente seulement si l'entrée Enable est à 1, mais ne fait rien si elle est à 0. Les compteurs les plus simples sont incrémentés/décrémentés à chaque cycle d'horloge et n'ont pas d'entrée Enable, mais les compteurs plus complexes en ont une. Ce faisant, le compteur/décompteur est incrémenté seulement si deux conditions sont réunies : un front montant sur le signal d'horloge, et une entrée Enable à 1. Dans les schémas qui vont suivre, nous ferons mention soit au signal d'horloge, soit à l'entrée Enable. Si on fait référence à l'entrée Enable, il est sous-entendu que les bascules du registre sont cadencées par une horloge, qui leur dit quand s'actualiser.

En outre, les compteurs ont souvent une entrée Reset qui permet de les remettre à zéro.

Sur les compteurs/décompteurs, il y a une entrée qui décide s'il faut compter ou décompter. Typiquement, elle est à 1 s'il faut compter et 0 s'il faut décompter.

Un compteur/décompteur peut parfois être initialisé avec la valeur de notre choix. Pour cela, ils possèdent une entrée d'initialisation sur laquelle on peut placer le nombre initial, couplée à une entrée Reset qui indique si le compteur doit être réinitialisé ou non. Certains compteurs/décompteurs spécifiques n'ont pas d'entrée d'initialisation, mais seulement une entrée de reset, mais il s'agit là d'utilisations assez particulières où le compteur ne peut qu'être réinitialisé à une valeur par défaut. Pour les compteurs/décompteurs, il faut aussi rajouter une entrée qui précise s'il faut compter ou décompter.

Le circuit d'un compteur : généralités

Un compteur/décompteur peut être vu comme une sorte de registre (ils peuvent stocker un nombre), mais qu'on aurait amélioré de manière à le rendre capable de compter/décompter. Tous les compteurs/décompteurs utilisent un registre pour mémoriser le nombre, ainsi que des circuits combinatoires pour calculer la prochaine valeur du compteur. Ce circuit combinatoire est le plus souvent, mais pas toujours, un circuit capable de réaliser des additions (compteur), des soustractions (décompteurs), voire les deux (compteur-décompteur). Plus rarement, il s'agit de circuits conçus sur mesure, dans le cas où le pas du compteur est fié une bonne fois pour toutes.

Comme dit plus haut, certains compteurs ont une valeur maximale qui est plus faible que la valeur maximale du registre. Par exemple, on peut imaginer un compteur qui compte de 0 à 9 : celui-ci est construit à partir d'un registre de 4 bits qui peut donc compter de 0 à 15 ! Ces compteurs sont construits à partir d'un compteur modulo, auquel on rajoute un circuit combinatoire. Ce dernier détecte le dépassement de la valeur maximale et remet à zéro le registre quand c'est nécessaire, via l'entrée de Remise à zéro (entrée Reset).

L'incrémenteur/décrémenteur

Certains compteurs, aussi appelés incrémenteurs comptent de un en un. Les décompteurs analogues sont appelés des décrementeurs. Nous allons voir comment créer ceux-ci dans ce qui va suivre. Il faut savoir qu'il existe deux méthodes pour créer des incrémenteurs/décrémenteurs. La première donne ce qu'on appelle des incrémenteurs asynchrones, et l'autre des incrémenteurs synchrones. Nous allons commencer par voir comment fabriquer un incrémenteur asynchrone, avant de passer aux incrémenteurs synchrones.

L'incrémenteur/décrémenteur asynchrone

Pour fabriquer un incrémenteur asynchrone, la première méthode, il suffit de regarder la séquence des premiers entiers, puis de prendre des paires de colonnes adjacentes :

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

Pour la colonne la plus à droite (celle des bits de poids faible), on remarque que celle-ci inverse son contenu à chaque cycle d'horloge. Pour les colonnes suivantes, le bit sur une colonne change quand le bit de la colonne précédente passe de 1 à 0, en clair, lorsqu'on a un front descendant sur la colonne précédente. Maintenant que l'on sait cela, on peut facilement créer un compteur avec quelques bascules. On peut les créer avec des bascules T, D, JK, et bien d'autres. Nous allons d'abord voir ceux fabriqués avec des bascules T, plus simples, puis ceux fabriqués avec des bascules D.

Les incrémenteurs/décrémenteurs asynchrones à base de bascules T

Pour rappel, les bascules T inversent leur contenu à chaque cycle d'horloge. Par simplicité, nous allons utiliser des bascules avec une sortie qui fournit l'inverse du bit stocké.

La première colonne inverse son contenu à chaque cycle, elle correspond donc à une bascule T simplifiée reliée directement à l'horloge. Les autres colonnes s'inversent quand survient un front descendant sur la colonne précédente. Le circuit qui correspond est illustré ci-dessous, avec des bascules T activées sur front descendant. Attention, cependant : la bascule la plus à gauche stocke le bit de poids FAIBLE, pas celui de poids fort. En fait, le nombre binaire est ici stocké de gauche à droite et non de droite à gauche ! Cela sera pareil dans tous les schémas qui suivront.

Il est aussi possible d'utiliser des bascules T actives sur front montant. En effet, notons qu'un front descendant sur la sortie Q correspond à un front montant sur la sortie /Q. En clair, il suffit de relier la sortie /Q d'une colonne sur l'entrée d'horloge de la suivante. Le circuit est donc le suivant :

Un décrémenteur est strictement identique à un incrémenteur auquel on a inversé tous les bits. On peut donc réutiliser le compteur du dessus, à part que les sorties du compteur sont reliées aux sorties Q des bascules.

Il est possible de fusionner un incrémenteur et un décrémenteur asynchrone, de manière à créer un circuit qui puisse soit incrémenter, soit décrémenter le compteur. Le choix de l'opération est réalisé par un bit d'entrée, qui vaut 1 pour une incrémentation et 0 pour une décrémentation. L'idée est que les entrées des bascules sont combinées avec ce bit, pour donner les entrées compatibles avec l'opération demandée.

L'incrémenteur asynchrone à base de bascules D

Il est aussi possible d'utiliser des bascules D pour créer un compteur comme les deux précédents. 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 peut être modifiée pour facilement réinitialiser le compteur à une valeur non-nulle. Pour cela, il faut ajouter une entrée au compteur, sur laquelle on présente la valeur d’initialisation. Chaque bit de cette entrée est reliée à un multiplexeur, qui choisir quel bit mémoriser dans la bascule : celui fournit par la mise à jour du compteur, ou celui présenté sur l'entrée d'initialisation. On obtient le circuit décrit dans le schéma qui suit. Quand l'entrée Reset est activée, les multiplexeurs connectent les bascules aux bits sur l'entrée d'initialisation. Dans le cas contraire, le compteur fonctionne normalement, les multiplexeurs connectant l'entrée de chaque bascule à sa sortie.

L'incrémenteur/décrémenteur synchrone

Passons maintenant à l'incrémenteur synchrone. Pour le fabriquer, on repart de la séquence des premiers entiers. Dans ce qui va suivre, nous allons créer un circuit qui compte de 1 en 1, sans utiliser d'additionneur. Pour comprendre comment créer un tel compteur, nous allons reprendre la séquence d'un compteur, déjà vue dans le premier extrait :

000
001
010
011
100
101
110
111

On peut remarquer quelque chose dans ce tableau : peu importe la colonne, un bit s'inversera au prochain cycle d’horloge quand tous les bits des colonnes précédentes valent 1. Et c'est vrai quelle que soit la taille du compteur ou sa valeur ! Ainsi, prenons le cas où le compteur vaut 110111 :

les deux premiers 1 sont respectivement précédés par la séquence 10111 et 0111 : vu qu'il y a un zéro dans ces séquences, ils ne s'inverseront pas au cycle suivant ;
le bit qui vaut zéro est précédé de la séquence de bit 111 : il s'inversera au cycle suivant ;
le troisième 1 en partant de la gauche est précédé de la séquence de bits 11 : il s'inversera aussi ;
même raisonnement pour le quatrième 1 en partant de la gauche ;
1 le plus à droite correspond au bit de poids faible, qui s'inverse tous les cycles.

Pour résumer, un bit s'inverse (à la prochaine mise à jour) quand tous les bits des colonnes précédentes valent 1. Pour implanter cela en circuit, on a besoin d'ajouter un circuit qui détermine si les bits des colonnes précédentes sont à 1, qui n'est autre qu'un simple ET entre les bits en question. On pourrait croire que chaque bascule est précédée par une porte ET à plusieurs entrées qui fait un ET avec toutes les colonnes précédentes. Mais en réalité, il y a moyen d'utiliser des portes plus simples, avec une banale porte ET à deux entrées pour chaque bascule. Le résultat est indiqué ci-dessous.

Compteur synchrone à incrémenteur avec des bascules T.

L’implémentation de circuit avec des bascules D est légèrement plus complexe. Il faut ajouter un circuit qui prend en entrée le contenu de la bascule et un bit qui indique s'il faut inverser ou pas. En écrivant sa table de vérité, on s’aperçoit qu'il s'agit d'un simple XOR.

On peut appliquer la même logique pour un décrémenteur. Avec ce circuit, un bit s'inverse lorsque tous les bits précédents sont à zéro. En utilisant le même raisonnement que celui utilisé pour concevoir un incrémenteur, on obtient un circuit presque identique, si ce n'est que les sorties des bascules doivent être inversées avant d'être envoyée à la porte XOR qui suit.

La gestion des débordements d'entiers des incrémenteurs/décrémenteurs

Pour rappel, tout compteur a une valeur maximale au-delà de laquelle il ne peut pas compter. Pour un compteur modulo N, le compteur compte de 0 à N-1. Pour les compteurs non-modulo, ils peuvent compter de 0 à $2^{n}-1$ , pour un compteur de n bits. Tout nombre en dehors de cet intervalle ne peut pas être représenté. Si le résultat d'un calcul sort de cet intervalle, il ne peut pas être représenté par l'ordinateur et il se produit ce qu'on appelle un débordement d'entier. Les débordements d'entiers surviennent quand on incrémente une valeur au-delà de la valeur maximale du compteur, ce qui est loin d'être rare.

La gestion des débordements peut se faire de deux manières différentes, mais celle qui est la plus utilisée sur les compteurs est tout simplement de réinitialiser le compteur quand on dépasse la valeur maximale. Pour les compteurs non-modulo, il n'y a pas besoin de faire quoique ce soit, car ils sont réinitialisés automatiquement. Prenez un compteur contenant la valeur maximale 111....1111, incrémentez-le, et vous obtiendrez 000...0000 automatiquement, sans rien faire. Par contre, pour les compteurs modulo, c'est une autre paire de manche. La réinitialisation ne se fait pas automatiquement, et on doit ajouter des circuits pour réinitialiser le compteur, et pour détecter quand le réinitialiser.

Les incrémenteurs/décrémenteurs précédents ne peuvent pas être réinitialisés. Pour que cela soit possible, il faut d'abord rajouter une entrée qui commande la réinitialisation du compteur : mise à 1 pour réinitialiser le compteur, à 0 sinon. Ensuite, 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 faire comme avec n'importe quel registre réinitialisable : connecter ensemble les entrées Reset des bascules et relier le tout à l'entrée de réinitialisation du compteur.

Maintenant que l'on a de quoi les réinitialiser, on ajoute un comparateur qui détecte quand la valeur maximale est atteinte, afin de commander l'entrée de réinitialisation. Prenons un compteur modulo 6, par exemple, ce qui veut dire qu'il compte de 0 à 5, et est remis immédiatement à zéro quand il atteint 6. Il compte donc comme suit : 0, 1, 2, 3, 4, 5, 0, 1, 2, ... Le circuit comparateur vérifie si la valeur maximale 6 est atteinte et qui met à 1 l'entrée Reset si c'est le cas. Un tel circuit est juste un comparateur avec une constante, que vous savez déjà fabriquer à cet endroit du cours. Un exemple est illustré ci-dessous.

Il peut être utile de prévenir quand un compteur a débordé. Cela a des applications assez intéressantes, qu'on verra dans les chapitres suivants, notamment pour ce qui est des diviseurs de fréquence et des timers. Pour cela, on ajoute une sortie au compteur, qui est mise à 1 quand le compteur déborde. Pour les compteurs modulo, la sortie n'est autre que la sortie du comparateur. Et on peut généraliser pour n'importe quel N. Mais les choses sont plus compliquées pour les compteurs non-modulo, qui comptent de 0 au $2^{N}$ , pour lesquels on doit ajouter un circuit détecte quand un débordement d'entier a lieu. Pour cela, il y a plusieurs solutions. La plus simple est d'ajouter un comparateur qui vérifie si le compteur est à 0, signe qu'il vient d'être réinitialisé et a donc débordé. L'autre solution est d'ajouter une bascule à la toute fin de l'incrémenteur : cette bascule est mise à 1 en cas de débordement. Il suffit alors d'ajouter un circuit qui compare la valeur de cette bascule avec sa valeur du cycle précédent, et le tour est joué.

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

Certains compteurs sont basés sur un registre à décalage. Pour simplifier les explications, nous allons les classer suivant le type de registre à décalage utilisé. Pour rappel, un registre à décalage dispose d'une entrée et d'une sortie. L'entrée peut être de deux types : soit une entrée série qui prend 1 bit, soit une entrée parallèle qui prend un nombre. Il en est de même pour la sortie, qui peut être série ou parallèle, à savoir qu'elle peut fournir en sortie soit un bit unique, soit un nombre complet. En combinant les deux, cela donne quatre possibilités qui portent les noms de registres à décalage PIPO, PISO, SIPO et SISO (P pour parallèle, S pour série, I pourInput, O pour Output).

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

Les registres PIPO sont en réalité des registres simples, pas des registres à décalage, donc on les omets dans de qui suit. Les compteurs déterministes peuvent se fabriquer avec les trois types restants de registres à décalage, ce qui donne trois types de compteurs déterministes. Malheureusement, ces types ne portent pas de noms proprement dit. À la rigueur, les compteurs déterministes basés sur un registre SISO sont appelés des compteurs en anneau, et encore cette dénomination est légèrement impropre.

À l'exception de certains compteurs one-hot qui seront vu juste après, ces compteurs sont des compteurs à rétroaction. Un terme bien barbare pour dire que l'on boucle leur sortie sur leur entrée, parfois en insérant un circuit combinatoire entre les deux. Les compteurs à rétroaction sont particuliers dans le sens où on n'a pas à changer leur valeur en cours de fonctionnement : on peut les réinitialiser, mais pas insérer une valeur dans le compteur. La raison est qu'ils sont utilisés pour une fonction bien précise : dérouler une suite de nombres bien précise, prédéterminée lors de la création du compteur. Par exemple, on peut créer un compteur qui sort la suite de nombres 4,7,6,1,0,3,2,5 en boucle, quel qu’en soit l'utilité. Cela peut servir pour fabriquer des suites de nombres pseudo-aléatoires, ce qui est de loin leur utilisation principale, comme on le verra dans un chapitre spécialement dédié aux circuits générateurs d'aléatoire. Mais certaines de leurs utilisations sont parfois surprenantes.

Un bon exemple de cela est leur utilisation dans l'Intel 8008, le tout premier microprocesseur 8 bits commercialisé, où ce genre de compteurs étaient utilisés pour le pointeur de pile, pour économiser quelques portes logiques. Ces compteurs implémentaient la séquence suivante : 000, 001, 010, 101, 011, 111, 110, 100. Pour les connaisseurs qui veulent en savoir plus, voici un article de blog sur le sujet : Analyzing the vintage 8008 processor from die photos: its unusual counters.

Les compteurs en anneau et de Johnson (SISO)

Les compteurs basés sur des registres à décalage SISO sont aussi appelés des compteurs en anneau. Ils sont appelés ainsi car, généralement, on boucle la sortie du registre sur son entrée, ce qui veut dire que le bit sortant du registre est renvoyé sur son entrée. Pour les compteurs fabriqués avec un registre SISO (entrée et sortie de 1 bit), le bit entrant dans le registre à décalage est calculé à partir du bit sortant. Et il n'y a pas 36 façons de faire ce calcul : soit le bit sortant est laissé tel quel, soit il est inversé, pas d'autre possibilité. La première possibilité, où le bit entrant est égal au bit sortant, donne un compteur en anneau, vu plus haut. La seconde possibilité, où le bit sortant est inversé avant d'être envoyé sur l'entrée du registre à décalage, donne un compteur de Johnson. Les deux sont très différents, et ne fonctionnent pas du tout pareil.

Les compteurs en anneau : 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. Dans une telle représentation, un bit est à 1 pendant que les autres sont à 0. es 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 n'encode aucune valeur, c'est une valeur interdite. A la place, le zéro est codé en mettant le bit de poids faible à 1. Pour N bits, on peut encoder seulement N valeurs.

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 ;
0010 ;
0100;
1000.

Incrémenter ou décrémenter le compteur demande alors de faire un simple décalage, ce qui fait que le compteur est un simple registre à décalage et non pas un compteur combiné à un incrémenteur/décrémenteur compliqué. L'économie en circuits d'incrémentation n'est pas négligeable. De plus, 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. Mais les économies en termes de circuits (incrémenteur et comparateur) sont cependant contrebalancée par le fait que le compteur demande plus de bascules. Imaginons que l'on veut un compteur qui compte jusqu'à une valeur N arbitraire : un compteur en 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 logiques l'est beaucoup plus. De plus, il n'y a pas qu'une économie de circuit : le compteur est plus rapide.

Si vous ne mettez que des 0 dans un compteur en anneau, il restera bloqué pour toujours. En effet, décaler une suite de 0 donnera la même suite de 0.

En théorie, un simple registre à décalage peut faire office de compteur one-hot, mais son comportement est alors invalide en cas de débordement. Un débordement met la valeur du registre à décalage à zéro, ce qui n'est pas l'effet recherché. On peut en théorie rajouter des circuits combinatoires annexes pour gérer le débordement, mais il y a encore plus simple : boucler la sortie du registre sur son entrée. Le résultat donne donc un type particulier de compteurs one-hot, appelé les compteurs en anneau sont des registres à décalage dont le bit sortant est renvoyé sur l'entrée. En faisant cela, on garantit que le registre revient à zéro, zéro étant codé avec un 1 dans le bit de poids faible. En cas de débordement, le registre est mis à zéro par le débordement, mais le bit sortant vaut 1 et ce 1 sortant est envoyé sur l'entrée pour y être inséré dans le bit de poids faible.

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. Ils étaient aussi utilisés comme diviseurs de fréquence, comme on le verra dans le chapitre suivant. 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 compteurs de Johnson : les compteurs unaires

Sur les compteurs de Johnson, le bit sortant est inversé avant d'être bouclé sur l'entrée.

La séquence d'un compteur de Johnson de 4 bits est :

1000 ;
1100 ;
1110 ;
1111 ;
0111 ;
0011 ;
0001 ;
0000.

Vous remarquerez peut-être que lorsque l'on passe d'une valeur à la suivante, seul un bit change d'état. Sachant cela, vous ferez peut-être le parallèle avec le code Gray vu dans les tout premiers chapitres, mais cela n'a rien à voir. Les valeurs d'un compteur Johnson ne suivent pas un code Gray classique, ni même une variante de celui-ci. Les compteurs qui comptent en code Gray sont foncièrement différents des compteurs Johnson.

Une application des compteurs de Johnson, assez surprenante, est la fabrication d'un signal sinusoïdal. En combinant un compteur de Johnson, quelques résistances, et des circuits annexes, on peut facilement fabriquer un circuit qui émet un signal presque sinusoïdal (avec un effet d'escalier pas négligeable, mais bref). Les oscillateurs sinusoïdaux numériques les plus simples qui soient sont conçus ainsi. Quant aux compteurs en anneau, ils sont utilisés en lieu et place des compteurs normaux dans des circuits qui portent le nom de séquenceurs ou de machines à états, afin d'économiser quelques circuits. Mais nous en reparlerons dans le chapitre sur l'unité du contrôle du processeur.

Les registres à décalage à rétroaction de type SIPO/PISO

D'autres compteurs sont fabriqués en prenant un registre à décalage SIPO ou PISO dont on boucle l'entrée sur la sortie. Pour être plus précis, il y a très souvent un circuit combinatoire qui s'intercale entre la sortie et l'entrée. Son rôle est de calculer ce qu'il faut mettre sur l'entrée, en fonction de la sortie.

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

Étudions en premier lieu le cas des registres à décalage à rétroaction linéaire. 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, et plus précisément des registres à décalage SIPO. A rétroaction indique que l'on boucle la sortie sur l'entrée. Linéaire indique que l'entrée du registre à décalage s'obtient par une combinaison linéaire de la sortie. Le terme combinaison linéaire signifie que l'on multiplie les bits de l'entrée par 0 ou 1, avant d'additionner le résultat. Vu que nous sommes en binaire, les constantes en question valent 0 ou 1. Voici un exemple de formule qui colle avec ce cahier des charges :

1\times a_{n}+...+1\times a_{3}+0\times a_{2}+1\times a_{1}+0\times a0

Une première simplification est possible : supprimer les multiplications par 0. Ce faisant, les bits associés ne sont tout simplement pas pris en compte dans le calcul d'addition. Tout se passe comme suit l'on ne tenait compte que de certains bits du LFSR, pas des autres. On a alors des opérations du genre :

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

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 nous dispense de gérer les retenues. Et nous verrons dans quelques chapitres qu'additionner deux bits en binaire, sans tenir compte des retenues, revient à faire une simple opération XOR. On peut donc remplacer les additions par des 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écalage à rétroaction de Gallois sont un peu l'inverse des LFSR vus juste avant. Au lieu d'utiliser un registre à décalage SIPO, on utilise 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. Leur avantage est qu'ils sont plus rapides, sans avoir les inconvénients des autres LFSR. 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.

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

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

Il existe une variante des LFSR, qui modifie légèrement son fonctionnement. Il s'agit des registres à décalages à rétroaction affine.

Pour les LFSR SIPO, la fonction qui calcule le bit de résultat n'est pas linéaire, mais se calcule par une formule comme la suivante. Notez le +1 à la fin de la formule : c'est la seule différence.

0\times a_{n}+...+0\times a_{3}+1\times a_{2}+1\times a_{1}+0\times a0+1

Le résultat obtenu est l'inverse de celui obtenu avec le LFSR précédent. 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. 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.

Pour les LFSR PISO, il existe aussi une variante affine, où les portes XOR sont remplacées par des portes NXOR.

Il existe enfin des compteurs de ce type qui ne sont pas des LFSR, même en incluant les compteurs de Gallois et autres. Ce sont des compteurs basés sur des registres à décalage où le circuit combinatoire inséré entre l'entrée et la sortie n'est pas basé sur des portes XOR ou NXOR. Ils sont cependant plus compliqués à concevoir, mais ils ont beaucoup d'avantages.

La période d'un compteur à rétroaction

Un compteur à rétroaction est déterministe : pour le même résultat en entrée, il donnera toujours le même résultat en sortie. De plus, ce registre ne peut contenir qu'un nombre fini de valeurs, ce qui fait qu'il finira donc par repasser par une valeur qu'il aura déjà parcourue. Une fois qu'il repassera par cette valeur, son fonctionnement se reproduira à l'identique comparé à son passage antérieur. Lors de son fonctionnement, le compteur finira par repasser par une valeur parcourue auparavant et il bouclera. Il parcourt un nombre N de valeurs à chaque cycle, ce nombre étant appelé la période du compteur.

Le cas le plus simple est celui des compteurs en anneau, suivi par les compteurs Johnson. Les deux compteurs ont des périodes très différentes. Un compteur en anneau de N bits peut prendre N valeurs différentes, qui ont toutes un seul bit à 1. À l'opposé, un compteur Johnson peut prendre deux fois plus de valeurs. Pour nous en rendre compte, comparons la séquence de nombre déroulé par chaque compteur. Pour 5 bits, les séquences sont illustrées ci-dessous, dans les deux animations.

Compteur en anneau de 5 bits.

Compteur de Johnson de 5 bits.

La période des registres à décalage à rétroaction linéaire dépend fortement de la fonction utilisée pour calculer le bit de sortie, des bits choisis, etc. Dans le meilleur des cas, le registre à décalage à rétroaction passera par presque toutes les valeurs que le registre peut prendre. Si je dis presque toutes, c'est simplement qu'une valeur n'est pas possible : suivant le registre, le zéro ou sa valeur maximale sont interdits. Si un registre à rétroaction linéaire 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 registres à rétroaction 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, même si nous ne vous donnerons pas la démonstration.

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

L'initialisation d'un compteur à rétroaction

Sur la quasi-totalité des compteurs et registres vu dans ce chapitre et les précédents, le compteur peut être initialisé à une valeur arbitraire. De plus, les débordements d'entiers sont possibles. Mais sur une bonne partie des compteurs à rétroaction, rien de tout cela n'est possible. Rappelons que les compteurs à rétroaction déroulent une suite de nombres bien précise, déterminée lors de la création du compteur. Donc, ça ne servirait à rien de charger une valeur arbitraire dans ces compteurs, du fait de leur fonctionnement. De plus, leur fonctionnement est périodique, ce qui fait que de tels compteurs ne peuvent pas déborder. En conséquence, un compteur à rétroaction ne peut pas être initialisé à une valeur arbitraire, mais seulement réinitialisé à une valeur de base qui est toujours la même.

Et ce qui est de l'initialisation, tous les compteurs basés sur un registre à décalage ne sont pas égaux. Pour résumer, deux cas sont possibles : soit le compteur peut être initialisé avec zéro sans que cela pose problème, soit ce n'est pas le cas. Les deux cas donnent des résultats différents. Autant le premier cas fait que l'on fait comme avec tous les autres registres, autant le second cas est inédit et demande des solutions particulières, qui sont les mêmes que le compteur oit en anneau, un LFSR, ou autre.

Le premier cas est celui où le compteur peut être initialisé avec zéro sans que cela ne pose problème. C'est le cas sur les compteurs de Johnson, mais aussi sur les registres à décalage à rétroaction non-linéaire. Sur de tels compteurs, 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.

Dans le second cas, on ne peut pas l'initialiser avec uniquement des 0, comme les autres registres, et la méthode précédente ne fonctionne pas. C'est le cas sur les compteurs en anneau, et sur les LFSR. Sur les compteurs en anneau, lors de la réinitialisation, il faut faire en sorte que toutes les bascules soient réinitialisées, sauf une qui est mise à 1. Pour cela, il faut utiliser des bascules, avec une entrée pour les reset et une autre pour les mettre à 1. Le signal de reset est envoyée normalement sur toutes les bascules, sauf pour la première. La première bascule est configurée de manière à ce que le signal de reset la mette à 1, en envoyant le signal de reset directement sur l'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. Elle fonctionne sur les registres en anneau, mais aussi sur les LFSR. 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.

Les compteurs en code Gray

Il existe des compteurs qui comptent en code Gray. Pour rappel, le code Gray permet de coder des nombres d'une manière un peu différente du binaire normal. Son avantage principal est que lorsqu'on incrémente ou décrémente un nombre, seul un bit change ! Ils ont beaucoup d'avantages, qui sont tous liés à cette propriété.

L'absence d'états transitoires douteux

Le premier l'absence d'état transitoires douteux. En binaire normal, lorsqu'on passe d'un nombre au suivant, plusieurs bits changent. La moyenne est d'environ deux bits, avec beaucoup de transitions de 1 bit, mais aussi quelques-unes qui en changent beaucoup plus. Le problème est que tous les bits modifiés ne le sont pas en même temps. Typiquement, les bits de poids faibles sont modifiés avant les autres.

Évidemment, à la fin du calcul, on obtient le résultat final, correct. Mais pendant le temps de calcul, le compteur peut se retrouver dans un état transitoire, où certains bits ont été modifiés mais pas les autres. Et c'est parfois un problème si le contenu de ce compteur est relié à des circuits assez rapides, qui peuvent, mais ne doivent pas voir cet état transitoire sous peine de dysfonctionner. L'usage de compteurs en code Gray permet d'éviter ce problème : vu que seul un bit est modifié lors d'une incrémentation/décrémentation, les états transitoires n'existent tout simplement pas.

Un exemple typique, évoqué dans les chapitres précédents, est l'échange d'informations entre deux domaines d'horloge. Pour rappel, il arrive que deux portions d'un circuit imprimé aillent à des fréquences différences : on dit que le circuit à plusieurs domaines d'horloge. Mais il faut échanger des informations entre ces deux portions, et divers problèmes surviennent alors. Un domaine d'horloge sera plus rapide que l'autre, et il pourra voir les états transitoires invisible pour le circuit. Et par voir, on veut dire qu'il les prendra pour des états valides, et cela fera dysfonctionner le circuit. Pour éviter cela, diverses techniques de croisement de domaines d'horloge existent. Et les compteurs Gray en font partie : si un domaine d'horloge utilise la valeur d'un compteur de l'autre, mieux vaut que ce compteur soit un compteur Gray. Et cette situation est assez fréquente !

La consommation énergétique du compteur Gray

Un autre point est que la consommation d'énergie de ces compteurs est bien plus réduite qu'avec un compteur normal. Rappelons que pour fonctionner, les circuits électroniques consomment un peu d'électricité. Un compteur ne fait pas exception. Et la majeure partie de cette consommation sert à changer l'état des portes logiques. Faire passer un bit de 0 à 1 ou de 1 à 0 consomme beaucoup plus d'énergie que de laisser un bit inchangé. Ce qui fait que quand un compteur est incrémenté ou décrémenté, cela consomme un peu d'énergie électrique. Et les conséquences de cela sont nombreuses.

Premièrement, plus on change de bits, plus la consommation est forte. Or, comme on l'a dit plus haut, la moyenne pour un compteur binaire normal est de 2 bits changés par incrémentation/décrémentation, contre un seul pour un compteur Gray. Un compteur Gray consomme donc deux fois moins d'énergie. En soi, cela n'est pas grand-chose, un compteur consomme généralement peu. Mais l'avantage est que cela va avoir des effets en cascade sur les circuits qui suivent ce compteur. Si l'entrée de ces circuits ne change que d'un seul bit, alors leur état changera moins que si c'était deux bits. Les circuits qui suivent vont donc moins consommer.

Un autre avantage en matière de consommation énergétique est lié justement au point précédent, sur les transitions d'état douteux. Les circuits connectés au compteur vont voir ces transitions d'état douteux : ils vont réagir à ces entrées de transition et modifier leur état interne en réaction. Bien sur, l'état final correct fera de même, ce qui effacera ces états transitoires intermédiaires. Mais chaque état intermédiaire transitoire correspondra à un changement d'état, donc à une consommation d'énergie. En supprimant ces états transitoires, on réduit fortement la consommation d'énergie du circuit. Cela vaut pour le compteur Gray lui-même, mais aussi sur tous les circuits qui ont ce compteur comme entrée !

◄ Retour vers « Les registres et mémoires adressables »

Sommaire du livre

Continuer vers « Les timers et diviseurs de fréquence » ►