Introdução às Máquinas de Estados Finitos (FSM)

Sistemas Reconfiguráveis Eng de Computação Profs Francisco Garcia e Antônio Hamilton Magalhães Aula 13 Introdução às máquina de estados finitos FSM rev B 130522 Uma máquina de estados finitos em inglês finite state machine FSM é um modelo usado para representar um sistema lógico Como o nome já diz essa máquina às vezes chamada de autômato pode estar em um número finito de estados A máquina está em apenas um estado por vez este estado é chamado de estado atual Uma transição indica uma mudança de estado e é descrita por uma condição que precisa ser realizada para que a transição ocorra Existem FSMs síncronas e assíncronas Estudaremos apenas as FSMs síncronas onde as transições de estado ocorrem sincronizadas com as transições de um sinal chamado comumente de clock Máquina de estados finitos Existem dois tipos de máquinas de estados Máquina de Moore As saídas dependem apenas do estado atual Máquina de Mealy As saídas dependem do estado atual e também das entradas Máquina de estados finitos A implementação de uma FSM pode ser dividida em três blocos Memória do estado Circuito de lógica sequencial flipflops que memoriza o estado atual As mudanças de estado são disparadas por um sinal de clock Pode ter uma entrada que estabelece um estado inicial de forma assíncrona reset Lógica do próximo estado Lógica combinacional que para cada estado atual e condição de entrada determina qual o próximo estado Em uma FSM síncrona o estado só vai ser atualizado no próximo pulso de clock Lógica de saída Combinacional Determina as saídas com base no estado atual máquina de Moore ou no estado atual e entradas máquina de Mealy Máquina de estados finitos Máquina de estados finitos Memória do estado Lógica do próximo estado Lógica de saída Saídas Entradas clk rst Estado atual Próximo estado Máquina de Mealy Existem alguns métodos de documentar o funcionamento de uma máquina de estados Abaixo é mostrado um exemplo de um diagrama de transição de estados de uma máquina de Moore Máquina de estados finitos Estado inicial reset Saídas A máquina de estados desse exemplo tem quatro estados S0 S1 S2 e S3 duas entradas A e B e duas saídas Y e Z Os círculos representam os estados e as setas as transições de estado Estado Transição incondicional Condição de entrada para transição de estado S0 Y 0 Z 0 S1 Y 0 Z 1 S2 Y 1 Z 1 S3 Y 1 Z 0 AB 1X AB 0X nRST AB 0X AB 10 AB 11 Um único PROCESS com toda a lógica não recomendado Dois PROCESS um para a memória do estado flipflops e outro para as lógicas do próximo estado e de saída combinacionais recomendado para a maior parte das aplicações Três PROCESS um para a memória do estado flip flops outro para a lógica do próximo estado e um terceiro para a lógica de saída combinacionais recomendado para aplicações muito complexas Máquina de estados finitos A codificação do comportamento de uma máquina de estados finitos em VHDL deve ser feita usando código sequencial e permite três opções Memória do estado Lógica do próximo estado Lógica de saída Máquina de Mealy Saídas Entradas clk rst PROCESS 2 PROCESS 1 Memória do estado Lógica do próximo estado Lógica de saída Máquina de Mealy Saídas Entradas clk rst PROCESS 1 PROCESS 2 PROCESS 3 Exemplo fsm1 Descrever em VHDL a FSM cujo diagrama de transição de estados é mostrado abaixo Máquina de estados finitos Exemplo LIBRARY ieee USE ieeestdlogic1164all ENTITY fsm1 IS PORT clk nrst a b IN STDLOGIC y z OUT STDLOGIC END ENTITY Continua na próxima página S0 Y 0 Z 0 S1 Y 0 Z 1 S2 Y 1 Z 1 S3 Y 1 Z 0 AB 1X AB 0X nRST AB 0X AB 10 AB 11 Exemplo fsm1 Descrever em VHDL a FSM cujo diagrama de transição de estados é mostrado abaixo ARCHITECTURE arch1 OF fsm1 IS TYPE statetype IS s0 s1 s2 s3 SIGNAL nextstate presstate statetype BEGIN Parte sequencial da máquina de estados PROCESSnrst clk BEGIN IF nrst 0 THEN presstate s0 ELSIF RISINGEDGEclk THEN presstate nextstate END IF END PROCESS Continua na próxima página S0 Y 0 Z 0 S1 Y 0 Z 1 S2 Y 1 Z 1 S3 Y 1 Z 0 AB 1X AB 0X nRST AB 0X AB 10 AB 11 Máquina de estados finitos Exemplo Exemplo fsm1 Descrever em VHDL a FSM cujo diagrama de transição de estados é mostrado abaixo Parte combinacional da máquina de estados PROCESSa b presstate BEGIN CASE presstate IS WHEN s0 y 0 z 0 IF a 0 THEN nextstate s0 ELSE nextstate s1 END IF WHEN s1 y 0 z 1 IF a 0 THEN nextstate s0 ELSIF b 0 THEN nextstate s3 ELSE nextstate s2 END IF Continua na próxima página Máquina de estados finitos Exemplo S0 Y 0 Z 0 S1 Y 0 Z 1 S2 Y 1 Z 1 S3 Y 1 Z 0 AB 1X AB 0X nRST AB 0X AB 10 AB 11 Exemplo fsm1 Descrever em VHDL a FSM cujo diagrama de transição de estados é mostrado abaixo WHEN s2 y 1 z 1 nextstate s3 WHEN s3 y 1 z 0 nextstate s0 END CASE END PROCESS END arch1 Máquina de estados finitos Exemplo S0 Y 0 Z 0 S1 Y 0 Z 1 S2 Y 1 Z 1 S3 Y 1 Z 0 AB 1X AB 0X nRST AB 0X AB 10 AB 11 Quartus II menu Tools Netlist Viewers State Machine Viewer Máquina de estados finitos Exemplo Máquina de estados finitos Exemplo Exemplo fsm1 Resultado da simulação funcional Exercício fsm2 Desenhar o diagrama de transição de estados de um máquina de estados finitos que controla um sistema de reprodução de áudio descrito a seguir Escrever o código em VHDL para essa máquina de estados usando dois PROCESS um sequencial para a memória de estado e outro combinacional para as lógicas do próximo estado e de saída Testar o projeto no módulo DE2 Máquina de estados finitos Exercício Exercício fsm2 especificações Esse sistema tem dois botões PLAY e STOP Esses botões quando pressionados geram um nível lógico 0 e quando liberados voltam para a posição original por efeito de um mola gerando o nível lógico 1 Existe também um sinal END ativo em nível lógico alto que indica que o áudio chegou ao final O sistema é controlado através de duas saídas uma para ativar a reprodução e outra para voltar a gravação para o início Esse último não pode ser ativado durante a reprodução nem durante a pausa Máquina de estados finitos Exercício P M S E RST I Entradas nrst reset assíncrono ativo baixo clk clock borda de subida p PLAY ativo baixo s STOP ativo baixo e END ativo alto Saídas m ativa reprodução ativo alto i volta para início ativo alto Exercício fsm2 especificações continuação O estado inicial do sistema após a energização é parado Estando o botão de STOP liberado a reprodução é iniciada quando o botão PLAY é pressionado Manter o botão PLAY pressionado depois do início da reprodução não faz efeito algum Se o botão PLAY for liberado a reprodução continua normalmente Estando reproduzindo pressionar o botão PLAY novamente faz a reprodução pausar Manter o botão PLAY pressionado não faz efeito algum Se o botão PLAY for liberado o sistema continua pausado Estando em pausa pressionar o botão PLAY novamente faz a reprodução retornar a partir do ponto onde foi pausada Manter o botão PLAY pressionado não faz efeito algum Se o botão PLAY for liberado a reprodução continua normalmente Se durante a reprodução o sinal END for ativado ou em qualquer situação o botão STOP for pressionado o sistema volta para o estado inicial Se isso acontecer com o botão PLAY pressionado ele deve ser liberado antes de um novo comando de PLAY Máquina de estados finitos Exercício