Prof.Corradi
Finite State Machines
Técnicas Digitais e de Microprocessadores – TDM II
1.1
Máquinas de Estados Finitos e Autômatos
 São uma Forma Muito Usada para Representar Sistemas que
Possuem Memorização de Estados, não sendo Portanto Meramente
Combinacionais. Podem ser usados para Representar:
•
•
•
•

Protocolos em Redes
Comportamento de Circuitos Eletrônicos
Comportamento de Programas de Computador
Comportamento de um Processo de Fabricação
O Contrôle de Um Processo Físico Analógico de Uma forma Geral:
Entrada
Analógica
Num Sistema Analógico a
Somador/
Comparador
Saída
Analógica
PROCESSO
Realimentação
Técnicas Digitais e de Microprocessadores – TDM II
Relação entre Saída e Entrada
Pode Ser Representada por
Equações Diferenciais e Integrais
Variáveis Assumem Valores
Contínuos no Tempo
1.2
Lógica Combinacional e Lógica Sequencial
 Lógica Combinacional
• A saída depende apenas de uma combinação
lógica dos valores de entrada. A saída não
precisa esperar nenhum “clock” para ser
gerada. Saídas são geradas um tempo
pequeno (atraso da lógica) após as entradas
mudarem.
A
S
B
T
C
U
D
 Lógica Sequencial
• É a que faz uso de registros (memória)
• A saída pode depender apenas dos estados
dos flip-flops ou da combinação dos estados
e das entradas.
• Denomina-se “ESTADO” da lógica
sequencial ao conjunto de “1s” e “0s”
armazenados nos flip-flops (memória) da
lógica
• O relógio demarca o momento em que os
estados mudam.
Técnicas Digitais e de Microprocessadores – TDM II
A
D
B
Q
S
Q
T
C
C
D
D
C
CK
1.3
Autômatos – Variáveis Assumem Valores Discretos no Tempo
Representação:
Reset
11/0
10/0
10/1
E3
10/0
Estado
00/0
A- Tabela de Transição
E0
E1
E2
E3
E4
01/1
E4
00/1
PRÓXIMO ESTADO
ENTRADAS
SAÍDAS (z)
ENTRADAS
x, y
00
E0
E3
E2
E3
E4
00/0
E2
11/0
E1
Entradas(x, y)
01/0
E0
11/1
01/0
Saída (z)
ESTADO
ATUAL
00/0
10/0
A- Diagrama de Transição
01
E2
E1
E2
E3
E0
Técnicas Digitais e de Microprocessadores – TDM II
x, y
10
E0
E1
E2
E4
E2
11
E1
E2
E3
E3
E4
00
0
1
0
0
?
01
0
0
?
?
1
10
0
0
?
0
1
11
1
0
0
?
?
1.4
Autômatos Determinísticos e Não Determinísticos
 Autômato Finito Determinístico (AFD)
•
•
•
•
•
Um Conjunto Q de Elementos Denominados Estados
Um conjunto finito I denominado alfabeto de entrada
Uma função F de mapeamento de Q X I em Q
Um estado inicial q0 em Q
Um Conjunto (não vazio) de Estados Terminais Z
 Autômato Finito Não Determinístico (AFND)
•
•
•
•
•
Um Conjunto Q de Elementos Determinados Estados
Um Conjunto finito I denominado alfabeto de entrada
Uma função F de mapeamento de Q x I em subconjuntos de Q
Um conjunto de estados iniciais em Q
Um conjunto (não vazio) de estados terminais Z contido em Q
 NOTA: Um AFND pode estar em vários estados simultaneamente
(paralelismo – vários caminhos podem ser percorridos ao mesmo
tempo para chegar ao resultado final)
Técnicas Digitais e de Microprocessadores – TDM II
1.5
Mealy and Moore Machines
Mealy Machine
Inputs
Next State
Combinatorial
Logic
Flip
Flops
Output
Combinatorial
Logic
Flip
Flops
Output
Combinatorial
Logic
Outputs
Clock
Moore Machine
Inputs
Next State
Combinatorial
Logic
Outputs
Clock
Técnicas Digitais e de Microprocessadores – TDM II
1.6
Modelo de Moore e de Mealy

MODELO DE MOORE
- As saídas são definidas apenas em função dos estados.
- No diagrama dos estados, o valor das saídas é representado junto o código
do estado.
Exemplo:
• MODELO DE MEALY
- As saídas são definidas em função dos estados e das entradas do
circuito.
- No diagrama dos estados, o valor das saídas é representado junto ao
valor da entrada.
Exemplo:
Técnicas Digitais e de Microprocessadores – TDM II
1.7
Máquina de Mealy
A- Exemplo:
Reset
0/1
1/0
E0
1/1
1/0
0/0
1/0
E1
B- Tabela de Transição
E2
0/0
0/1
Est.
Próx. Estado/Saída
Atual
Entrada (x)
E
x=0
x=1
E0
E0/1
E2/0
E1
E3/1
E1/1
E2
E1/0
E4/1
E3
E0/0
E2/0
E4
E1/1
E3/0
Técnicas Digitais e de Microprocessadores – TDM II
0/1
E4
E3
1/0
1.8
Máquina de Moore
Reset
1
A- Exemplo:
0
E0/1
1
0
0
E3/0
1
E4/0
0
B- Tabela de Transição
Est.
E2/1
Próx. Estado
Saída (y)
Atual
Entrada (x)
E
x=0
x=1
E0
E0
E2
1
E1
E3
E1
0
E2
E1
E4
1
E3
E0
E2
0
E4
E1
E3
0
Técnicas Digitais e de Microprocessadores – TDM II
1
0
1
E1/0
y = F (E)
1.9
Validade de Especificações (I)
Técnicas Digitais e de Microprocessadores – TDM II
1.10
Validade de Especificações (II)
Técnicas Digitais e de Microprocessadores – TDM II
1.11
Algumas Características de Máquinas Não Determinísticas
(simplificando inicialmente)
 Os estados são equivalentes a variáveis booleanas em
um programa
 Sua construção é mais intuitiva que a determinísticas
 A atribuição de estados é simples, normalmente
associados com as saídas. Normalmente não se usa
codificação de estados.
 As equações são extraídas diretamente do diagrama,
sem tabelas ou mapas
 Máquinas não determinísticas são ineficientes para
sequências de contagem pois usam mais flip-flops que
máquinas determinísticas com codificação de estados.
Técnicas Digitais e de Microprocessadores – TDM II
1.12
Geração das Equações de Estado
 Em Máquinas Determinísticas
• Atribui-se a Codificação dos Estados
• Mapeiam-se os Estados e Eventos em uma Tabela Verdade
• Simplifica-se com o Mapa de Karnaugh (ou programa específico)
 Em Máquinas Não Determinísticas:
•
•
•
•
Cada estado é representado por um bit (“One Hot Encoding”)
Cada termo produto é o produto do evento com o estado origem
O estado é ativado pelo “ou” dos produtos que chegam a ele
O estado é desativado pelos produtos que efetivamente o
abandonam. Na verdade, um estado é desativado pela ativação
de um estado gerado a partir dele. Portanto, não é necessário
especificar as equações para desativar estados.
Técnicas Digitais e de Microprocessadores – TDM II
1.13
Procedimentos de Projeto
1- A partir da especificação obter o diagrama de
estados;
2- Atribuir códigos a cada estado do diagrama;
3- Com base no diagrama de estados, obter a
tabela de estados;
4- Escolher o tipo de flip-flop a utilizar;
5- Obter as equações de entrada para cada flipflop, com base na tabela de estados;
6- Obter as equações de saída do circuito;
7- Desenhar o circuito lógico.
Técnicas Digitais e de Microprocessadores – TDM II
1.14
Análise de um Exemplo (I)
 Controlador de Vagão:
Objetivo:
Modelar o comportamento
do controlador de um
vagão de transporte de
materiais.
Técnicas Digitais e de Microprocessadores – TDM II
1.15
Análise de um Exemplo (II)
Técnicas Digitais e de Microprocessadores – TDM II
1.16
Diagramas de Estados: Vantagens
 Formalismo gráfico permitindo uma
compreensão fácil do comportamento do
sistema.
 Forma intuitiva de modelação de sistemas.
 Suporte à elaboração de documentação de
projeto permitindo a comunicação entre
equipas de projetos, bem como ao ciclo de
vida de um produto.
Técnicas Digitais e de Microprocessadores – TDM II
1.17
Diagramas de Estados: Problemas
 Ausência de mecanismo de estruturação
hierárquica de suporte a encapsulamento e á
utilização de módulos.
 Modelação do estado global do sistema. No
caso de sistemas com componentes
concorrentes, os estados resultam do
produto dos estados das várias
componentes, conduzindo á explosão do
número de estados.
 Assim, são pouco adequadas á modelação de
sistemas complexos.
Técnicas Digitais e de Microprocessadores – TDM II
1.18
Aplicações de máquina de Estados
Controle de seqüência de
ações:
ler
instrução
• Unidade de controle de
CPUs
• Seqüência de ações 
fluxograma
• Mapeamento direto:
• fluxograma  maq.
de estados
decodificar
instrução
Técnicas Digitais e de Microprocessadores – TDM II
ADD
SUB
JUMP
1.19
Washing Machine Control Panel
LIGADA
Molho 10
Enxaguar
RESET
OPERANDO
INICIAR
AG
AA
EA
TA
Entradas (de Sensores e Botões de Contrôle):
MC
Sinais de Saída :
RESET – Botão Reset – Reinicia Programa
LED Ligada
M10 – Especifica Molho 10 minutos
LED Operando
INIC – Botão Iniciar após escolher Molho
ou Enxaguar
LED M10 – Molho 10
LED - Enxaguando
LED AG - Agitando
ENX – Enxaguar
LED AA – Abre_Água
TA – Tampa_Aberta
LED EA – Esvazia_Água
CC – Cesto_Cheio
LED TA – Tampa_Aberta
CV – Cesto_Vazio
LED MC – Motor_Centrifugar
Técnicas Digitais e de Microprocessadores – TDM II
1.20