Aller au contenu
ELECTRONICS ENGINEERINGelectronics-engineering.com
Systèmes électroniques numériques

Logique séquentielle : registres, compteurs et machines à états finis

Registres et registres à décalage, LFSR, compteurs synchrones et asynchrones, machines de Moore et de Mealy, conception complète d'un reconnaisseur de séquence, codages et remise à zéro.

https://www.electronics-engineering.com/fr/logique-sequentielle-compteurs-machines-a-etats/

Pas encore de vote : soyez le premier à noter cette page.

Les bascules servent à construire des réseaux séquentiels : des circuits dont la sortie dépend non seulement des entrées actuelles mais de l’histoire passée, résumée dans un état. Registres, compteurs, contrôleurs de protocole, unité de commande d’un processeur sont tous des réseaux séquentiels synchrones. Dans cette leçon, nous traitons les registres et les compteurs et la méthode générale de conception d’une machine à états finis, avec un exemple complet.

Registres et registres à décalage

Un registre de n bits est fait de n bascules D sur la même horloge : à chaque front, il mémorise un mot. En reliant la sortie de chaque bascule à l’entrée de la suivante, on obtient un registre à décalage : à chaque front, les bits avancent d’une position. Il convertit les données de parallèle en série et inversement (c’est le cœur des UART, du SPI et de toutes les liaisons série), retarde un signal d’un nombre précis de cycles et génère des séquences pseudo-aléatoires (avec une réaction XOR, le LFSR, utilisé pour les codes GPS et pour le test des puces).

Les compteurs

Un compteur binaire synchrone de n bits est un registre dont l’entrée est la valeur actuelle plus 1 : il compte de 0 à 2^n - 1 puis recommence. Le bit de poids faible change à chaque front, le suivant tous les deux, et ainsi de suite : chaque bit divise la fréquence par deux. Un compteur modulo N se remet à zéro quand il atteint N - 1 : compter les secondes d’une horloge demande 6 bits (2^6 = 64 \ge 60).

Les compteurs asynchrones (à propagation), dans lesquels chaque bascule est cadencée par la sortie de la précédente, utilisent moins de logique mais les bits ne changent pas ensemble : pendant un instant, le compteur passe par des valeurs erronées. Les conceptions modernes utilisent presque toujours des compteurs synchrones.

Machines à états finis

Une machine à états finis (FSM) se décrit par :

  • un ensemble fini d’états, mémorisés dans un registre ;
  • une fonction d’état suivant, qui calcule l’état suivant à partir de l’état actuel et des entrées (logique combinatoire) ;
  • une fonction de sortie.

Dans une machine de Moore, la sortie ne dépend que de l’état ; dans une machine de Mealy, elle dépend aussi des entrées. Les machines de Moore sont plus faciles à vérifier et ont des sorties stables pendant tout le cycle ; les machines de Mealy réagissent un cycle plus tôt et ont souvent besoin de moins d’états.

Un exemple complet : reconnaître la séquence 101

Nous voulons un circuit avec une entrée série x, un bit par cycle d’horloge, et une sortie z qui vaut 1 quand les trois derniers bits reçus sont 1, 0, 1 (aussi avec chevauchement : dans 10101, la séquence apparaît deux fois).

1. Le diagramme d’états. Chaque état se souvient de la part de séquence déjà arrivée :

  • S_0 : rien d’utile ;
  • S_1 : le dernier bit était 1 ;
  • S_2 : les deux derniers étaient 1, 0 ;
  • S_3 : les trois derniers étaient 1, 0, 1, sortie 1 (machine de Moore).
Diagramme d'états d'un reconnaisseur de la séquence 101
Quatre états, S0 initial et S3 avec sortie 1. De chaque état partent des flèches étiquetées avec le bit d’entrée qui cause la transition : de S0 sur 1 vers S1, de S1 sur 0 vers S2, de S2 sur 1 vers S3 ; de S3 sur 0 retour vers S2 et sur 1 vers S1, de sorte que les séquences qui se chevauchent sont aussi reconnues ; de S2 sur 0 retour vers S0.

Les transitions se trouvent en se demandant, pour chaque état et chaque entrée, quel est le plus long préfixe de la séquence qui coïncide avec la fin de ce qui a été reçu. Par exemple, dans S_3 (derniers bits 101), un 0 donne …1010, qui se termine par 10 : on va dans S_2, pas dans S_0.

2. La table d’états.

Étatx = 0x = 1z
S_0S_0S_10
S_1S_2S_10
S_2S_0S_30
S_3S_2S_11

3. Le codage. Quatre états demandent 2 bascules. Avec le codage binaire S_0 = 00, S_1 = 01, S_2 = 10, S_3 = 11 (bits q_1q_0), les fonctions d’état suivant découlent de la table et se simplifient avec des tables de Karnaugh :

    \[ q_0^+ = x,\qquad q_1^+ = \overline{x}\,q_0 + x\,q_1\,\overline{q_0},\qquad z = q_1q_0 \]

Vérification ligne par ligne : par exemple depuis S_2 (q_1q_0 = 10) avec x = 1 : q_0^+ = 1, q_1^+ = 0 + 1\cdot 1\cdot 1 = 1, c’est-à-dire 11 = S_3, correct. (Ici q_0^+ = x a une signification simple : q_0 se souvient du dernier bit reçu.)

4. Le circuit. Deux bascules D, les portes qui réalisent q_1^+ et q_0^+, et une porte AND pour la sortie.

D’autres codages sont possibles : le codage one-hot utilise une bascule par état (4 ici), avec une logique plus simple et plus rapide ; c’est le choix habituel dans les FPGA, où les bascules abondent. Les outils de synthèse choisissent eux-mêmes le codage, à partir de la description dans un langage de description matérielle.

La remise à zéro

Toute machine à états doit partir d’un état connu : à la mise sous tension, le contenu des bascules est aléatoire. Un signal de reset ramène le registre d’état à l’état initial. Si le reset est asynchrone, son relâchement doit quand même être synchronisé avec l’horloge (avec le même synchroniseur que celui vu pour la métastabilité), sinon des bascules différentes pourraient sortir du reset à des cycles différents et la machine partirait d’un état inattendu.

S’abonner
Notifier de
guest
1 commentaire
Le plus ancien
Plus récent Les plus votés
1
0
Vous avez apprécié cet article ? Merci de laisser un commentaire.x