Leçon 5 Finite State Machine

Extrait de wikipédia

Un automate fini ou automate avec un nombre fini d'états (en anglais finite-state automaton ou finite state machine) est un modèle mathématique de calcul, utilisé dans de nombreuses circonstances, allant de la conception de programmes informatiques et de circuits en logique séquentielle aux applications dans des protocoles de communication, le contrôle des processus, la linguistique et même la biologie. Un automate fini est une construction abstraite, susceptible d'être dans un nombre fini d'états, un seul état à la fois ; l'état où il se trouve est appelé l'« état courant ». Le passage d'un état à un autre est dirigé par un événement ou une condition ; ce passage est appelé une « transition ». Un automate particulier est défini par la liste de ses états et par les conditions des transitions.

On rencontre couramment des automates finis dans de nombreux appareils qui réalisent des actions déterminées en fonction des événements qui se présentent. Un exemple est un distributeur automatique de boissons qui délivre l'article souhaité quand le montant introduit est approprié, un autre les ascenseurs qui savent combiner les appels successifs pour s'arrêter aux étages intermédiaires, les feux de circulation capables de s'adapter aux voitures en attente, ou des digicodes qui analysent la bonne suite de chiffres.

Les automates finis peuvent modéliser un grand nombre de problèmes, parmi lesquels la conception assistée par ordinateur pour l'électronique, la conception de protocoles de communication, l'analyse syntaxique de langages et autres applications d’ingénierie. Dans la recherche en biologieet en intelligence artificielle, les automates finis ou des hiérarchies de telles machines ont été employés pour décrire des systèmes neurologiques. En linguistique, ils sont utilisés pour décrire les parties simples de grammaires de langues naturelles. En vérification de programmes (model checking), des automates finis, avec parfois un nombre très important d'états, sont employés.

Si l'on considère les automates finis comme un concept abstrait de calcul, leur puissance est pourtant faible ; ils ont bien moins de puissance de calcul qu'une machine de Turing. En d'autres termes, il y a des tâches qu'un automate fini ne peut pas accomplir alors qu'une machine de Turing peut le faire. Ceci est principalement dû au fait qu'un automate fini a une mémoire limitée par son nombre d'états.

Les automates finis sont étudiés dans le cadre plus général de la théorie des automates.

Qu'est-ce qu'une machine d'état ou FSM Finite?

Quel moyen efficace et élégant pour décrire un système logique de commande? Quelles stratégies utilisez-vous?

La première idée est triviale: on pense en général à écrire un circuit de commande avec une série de "if then else" ou "case". dans un process.

Le résultat n'est pas toujours lisible, mais à certains égards, il pourrait peut-être efficace si vous êtes particulièrement habile pour simplifier la description de votre logique de commande.

Une seconde possibilité consiste à utiliser un automate avec un nombre fini d'états (Finite State Machine noté FSM).

Une FSM est simplement une méthode qui vous permet de contrôler une commande ou un fonctionnement d'une manière simple et efficace,? Avec nos FPGA il sera ainsi facile de contrôler le déroulement dans le temps d'un système programmé.

Différents types de Finite State Machine

Il existe deux principaux types de FSM les machines de Mealy et celles de Moore.

La différence fondamentale entre ces deux types réside dans la gestion des sorties:

La sortie de Mealy dépend de l'état actuel et des entrées.

Les sorties d'une machine de Moore ne dépendent que de l'état actuel et ne prends pas en compte les entrées.

Fig 1 Machine de Mearly

Fig 2 Machine de Moore

Les FSM de Moore sont préférables à celles de Mealy car la sortie de Moore ne dépend que de l'état actuel de la machine. Aucune hypothèse ou vérification des entrées ne doivent être effectuées pour générer les sortie de la FSM,. Il en découle que le décodage de sortie est plus simple à réaliser , en particulier en VHDL pour un FPGA.

En outre, si la sortie est combinatoire, à savoir non enregistré dans un registre, Moore est plus sûr que Mealy car le long chemin combinatoire entre l'entrée et la sortie peut générer des aléas sur la sortie de la machine, ou alors il faudrait réduire considérablement les performances du système en baissant la fréquence de l'horloge.

Voici ci-dessous une représentation visuelle simple, d'une machine de Moore:

Fig 3

Les cercles représentent les états. Le passage d'un état à un autre est représenté par les flèches. Afin de passer d'un état à l'autre lors du top d'horloge une condition, sur la flèche, doit être vérifiée. Si aucune condition est présente sur la flèche l'état suivant sera l'état actuel après un cycle d'horloge.

Afin de visualiser les sorties de la FSM, un rectangle contenant ces sorties peut être ajouté au diagramme:

Fig 4

Comment écrire du code VHDL pour une FSM de Moore

Si vous représentez votre FSM avec un schéma comme celui présenté dans les figures précédents, le codage VHDL est simple et peut être obtenu depuis un template VHDL proposé par Xilinx. Il nous propose d'utiliser trois process comme dans la figure 2:

• Process clocké pour mettre à jour l'état actuel à chaque top

• Process combinatoire pour prévoir le prochain état de la FSM à partir de l'état actuel et des entrées;

• Process combinatoire éventuellement clocké pour produire ( éventuellement mémoriser) les sorties de la FSM.

Le FSM pourrait également être codé avec un seul ou deux process, mais le modèle de FSM en VHDL proposé rend le code plus linéaire et lisible.

Notez que l'état actuel est stocké dans des registres tandis que l'état suivant est complètement combinatoire.

Voici le template que vous propose les outils Xilinx depuis le menu Tools>Language Templates>VHDL>Synthesis Constructs>Coding Exemples>State-Machines

-- This is a sample state-machine using enumerated types.

-- This will allow the synthesis tool to select the appropriate

-- encoding style and will make the code more readable.

--Insert the following in the architecture before the begin keyword

--Use descriptive names for the states, like st1_reset, st2_search

type state_type is (st1_<name_state>, st2_<name_state>, ...);

signal state, next_state : state_type;

--Declare internal signals for all outputs of the state-machine

signal <output>_i : std_logic; -- example output signal

--other outputs

--Insert the following in the architecture after the begin keyword

SYNC_PROC: process (<clock>)

begin

if (<clock>'event and <clock> = '1') then

if (<reset> = '1') then

state <= st1_<name_state>;

<output> <= '0';

else

state <= next_state;

<output> <= <output>_i;

-- assign other outputs to internal signals

end if;

end if;

end process;

--MOORE State-Machine - Outputs based on state only

OUTPUT_DECODE: process (state)

begin

--insert statements to decode internal output signals

--below is simple example

if state = st3_<name> then

<output>_i <= '1';

else

<output>_i <= '0';

end if;

end process;

NEXT_STATE_DECODE: process (state, <input1>, <input2>, ...)

begin

--declare default state for next_state to avoid latches

next_state <= state; --default is to stay in current state

--insert statements to decode next_state

--below is a simple example

case (state) is

when st1_<name> =>

if <input_1> = '1' then

next_state <= st2_<name>;

end if;

when st2_<name> =>

if <input_2> = '1' then

next_state <= st3_<name>;

end if;

when st3_<name> =>

next_state <= st1_<name>;

when others =>

next_state <= st1_<name>;

end case;

end process;

Question 1

Voici une machine de Moore qui calcule la parité d'un mot binaire.

2 états EVEN pour la parité pair et ODD pour impair ( sortie isEven produit un '0' ou un '1')

Complétez le code!

type state_type is (-----, -----);

signal state, next_state : state_type;

signal -----_i : std_logic;

begin

SYNC_PROC : process (clk)

begin

if rising_edge(clk) then

if (reset = '1') then

state <= EVEN;

isEven <= '0';

else

state <= next_state;

isEven <= -----_I;

end if;

end if,

end process;

OUTPUT_DECODE : process (state)

begin

case (state) is

when EVEN =>

-----_I <= ---;

when ODD =>

-----_I <= ---;

when others =>

-----_I <= ---;

end case;

end process;

NEXT_STATE_DECODE : process (state, x)

begin

next_state <= EVEN;

case (state) is

when EVEN =>

if (x = '1') then

next_state <= -----;

end if;

when ODD =>

if (x = '0') then

next_state <= -----;

end if;

when others =>

next_state <= -----;

end case;

end process;

Vous trouverez ici 3 façon de coder en VHDL la même FSM avec 1, 2 ou 3 process. Que çà soit du VHDL ou du Vevilog , çà reste la même stratégie.

Question 2

Avec ce template, la traduction d'une FSM de Moore devient quasi systématique, la difficulté est donc dans la transcription d'un problème en FSM.

Supposons que nous voulons mettre en place un digicode sur la porte de votre résidence.

• On utilisera les 4 boutons extérieurs de la carte btn (3:0) pour simuler le clavier de votre digicode.

• Le bouton central btn 4 fonctionne comme un reset de la saisie.

• Une séquence de quatre pressions de bouton est nécessaire pour ouvrir la porte.

• Cette séquence est codée sur les 8 switches de votre carte, 2 switches sont utilisés pour coder le numéro de chaque pression , dans l'ordre des bits croissant.

  • La led 1 s'allume quand le début du code saisi est correct, la led 2 s'allume et led 1 s’éteint quand le code est correct pour simuler l'ouverture de la porte.

  • Une mauvaise séquence de code repositionne la saisie en début de code .

  • Une fois la porte ouverte, le bouton reset (btn(4)) doit être appuyé pour effectuer la remise à zéro du digicode.

exemple: switch = "11_01_11_00" programme la session btn 0 puis btn 3 puis btn 1 puis btn 3.

btn : 3

2 4 0

1

1. Dessinez l'automate de votre circuit

2. Precisez les I/O de votre FSM.

3. Complétez le template VHDL sous les outils Xilinx pour chacun des process..

La suite se fera avec la carte comme TP5