6 - Máquina de Estados Finita

Prévia do material em texto

Máquina de Estados Finita
Prof. Wagner L. A. de Oliveira
oliveira.wagner@ufba.br
2
Como funciona uma máquina de vendas?
3
Máquina de Estados Finita
É um circuito sequencial capaz de implementar um algoritmo em hardware
Conhecida por sua sigla em inglês
FSM: Finite State Machine
FSM é um modelo de comportamento, formado por um número finito de estados, transições entre tais estados e ações
4
Circuito da FSM
FSM de Moore (orientada a estados)
5
Circuito da FSM
FSM de Mealy (orientada a transições)
6
Diagrama de estados
Utilizado para descrever o comportamento de um circuito sequencial
Formado por 2 tipos de elementos
Estado
Entradas/Saídas
FSM de Mealy:
Estado
Saídas
 Entradas
FSM de Moore:
7
Variáveis de estado
São informações internas da FSM
Sinalizam o estado atual da máquina
Exemplo: 
Uma máquina de 7 estados terá, pelo menos, 3 variáveis de estado
Número de variáveis de estado:
	Inteiro ≥ log 2 Número_de_Estados
8
Variáveis de estado
Há 3 formas de codificação de estados
Numeração Binária Sequencial
One Hot
Código Gray
9
Variáveis de estado
Há 3 formas de codificação de estados
Numeração Binária Sequencial
recomendada para FSMs com poucos estados (até 4)
utiliza o menor número de FFs
decodificador de próximo estado mais complexo, uma vez que utiliza todos os FFs
exige maior cuidado na verificação de temporização, devido a maior propensão à metaestabilidade 
One Hot
Código Gray
10
Variáveis de estado
Há 3 formas de codificação de estados
Numeração Binária Sequencial
One Hot
recomendada para FSMs entre 4 e 32 estados
número de bits (isto é, o número de variáveis) é igual ao número de estados
para cada estado, um único bit é 1
utiliza o maior número de FFs
simplifica decodificadores (próximo estado / saída)
simplifica a verificação de temporização
opção default de ferramentas de geração automática de FSMs para FPGA (Altera / Xilinx)
Código Gray
11
Variáveis de estado
Há 3 formas de codificação de estados
Numeração Binária Sequencial
One Hot
Código Gray
recomendada para FSMs acima de 32 estados
número de FFs igual ao da codificação sequencial
baixa propensão à metaestabilidade (como one hot)
aumento de complexidade (tamanho do circuito) devido a contadores Gray
12
13
Tabela de estados
É a transcrição do diagrama de estados para a forma de tabela
Permite encontrar as relações binárias entre as informações de entrada, variáveis de estado e saídas
(obs.: considerando codificação sequencial ou codificação Gray)
14
Síntese da FSM
Definir os sinais de entrada e saída de dados do circuito
Identificar as entradas e saídas por nomes/letras significativos
15
Síntese da FSM
Definir os sinais de entrada e saída de dados do circuito
Identificar as entradas e saídas por nomes/letras significativos
Definir a estrutura da FSM
Escolher entre Mealy / Moore
16
Síntese da FSM
Definir os sinais de entrada e saída de dados do circuito
Identificar as entradas e saídas por nomes/letras significativos
Definir a estrutura da FSM
Escolher entre Mealy / Moore
Desenhar o diagrama
Para cada estado, definir transições para todas as possíveis combinações envolvendo os sinais de entrada
17
Síntese da FSM
Definir os sinais de entrada e saída de dados do circuito
Identificar as entradas e saídas por nomes/letras significativos
Definir a estrutura da FSM
Escolher entre Mealy / Moore
Desenhar o diagrama
Para cada estado, definir transições para todas as possíveis combinações envolvendo os sinais de entrada
Definir o tipo de codificação e a quantidade de variáveis de estado
Calcular a quantidade de variáveis de estado
Identificar as variáveis de estado por nomes/letras significativos
Definir um FF para cada variável de estado
18
Síntese da FSM
Preencher a tabela de estados para síntese
19
Síntese da FSM
Preencher a tabela de estados para síntese
Calcular as expressões dos decodificadores
20
Síntese da FSM
Preencher a tabela de estados para síntese
Calcular as expressões dos decodificadores
Desenhar o circuito
21
Síntese da FSM
Preencher a tabela de estados para síntese
Calcular as expressões dos decodificadores
Desenhar o circuito
Verificar os estados iniciais, para definir a situação dos sinais de CLEAR e PRESET dos FFs
22
Exemplo:
23
Exemplo: 
Identificando as entradas e saídas
Sinais de Entrada de Dados
2 entradas
H (high) e L (low)
Sinais de Saída de Dados
2 saídas
M (motor) e A (alarme)
 H		 M
 
 L 		 A
Clock
Reset
24
Exemplo: 
Definindo a estrutura da FSM
FSM de Moore (orientada a estados)
Os FFs compõem o elemento de memória
As saídas do DPE são as entradas do EM (entradas dos FFs)
As saídas do EM (saídas dos FFs) são as entradas do DS
25
Exemplo: 
Definindo a estrutura da FSM
FSM de Mealy (orientada a transições)
Os FFs compõem o elemento de memória
As saídas do DPE são as entradas do EM (entradas dos FFs)
As entradas do circuito e as saídas do EM (saídas dos FFs) são as entradas do DS
26
Exemplo: 
Fazendo o diagrama de estados (Mealy)
Cheio
Vazio
Enchendo
Esvaziando
HL/MA
11/00
01/00
10/01
11/01
01/00
00/01
10/01
11/00
00/01
01/10
10/01
01/10
00/10
10/01
11/01
00/00
27
Exemplo: 
Definindo o tipo de codificação e identificando as variáveis de estado
Número de estados pequeno
4 estados  Numeração Binária Sequencial
Identificação das variáveis de estado por letras do início do alfabeto
4 estados  2 variáveis de estado
A e B
28
Exemplo: 
Preenchendo a tabela de estados (síntese)
ESTADO ATUAL
ENTRADAS
ESTADO FUTURO
SAÍDAS
SAÍDAS DO D.P.E.
Variáveis de estado
Variáveis de Entrada
Variáveis de estado
Variáveis de Saída
Entradas dos FF
  
  
  
  
  
coluna necessária somente quando 
o FF utilizado for diferente do tipo D
29
Nome do Estado
Estado Atual
Entradas
Estado Futuro
Saídas
A
B
High
Low
AF
BF
Motor
Alarme
Vazio
0
0
0
0
0
0
1
0
0
0
0
1
0
1
1
0
0
0
1
0
0
0
0
1
0
0
1
1
0
0
0
1
Enchendo
0
1
0
0
0
1
0
1
0
1
0
1
0
1
1
0
0
1
1
0
0
1
0
1
0
1
1
1
1
0
0
0
Cheio
1
0
0
0
1
0
0
1
1
0
0
1
1
1
0
0
1
0
1
0
1
0
0
1
1
0
1
1
1
0
0
0
Esvaziando
1
1
0
0
0
0
0
0
1
1
0
1
1
1
0
0
1
1
1
0
1
1
0
1
1
1
1
1
1
1
0
1
Exemplo: 
Preenchendo a tabela de estados (síntese)
30
Exemplo: 
Demais tarefas
Após obter a tabela, use os conhecimentos adquiridos anteriormente na construção de circuitos combinacionais
Extraia as expressões booleanas do decodificador de saída e do decodificador de próximo estado
Simplifique tais expressões
Desenhe o circuito correspondente 
31
Nome do Estado
Estado Atual
Entradas
Estado Futuro
Saídas
A
B
High
Low
AF
BF
Motor
Alarme
Vazio
0
0
0
0
0
0
1
0
0
0
0
1
0
1
1
0
0
0
1
0
0
0
0
1
0
0
1
1
0
0
0
1
Enchendo
0
1
0
0
0
1
0
1
0
1
0
1
0
1
1
0
0
1
1
0
0
1
0
1
0
1
1
1
1
0
0
0
Cheio
1
0
0
0
1
0
0
1
1
0
0
1
1
1
0
0
1
0
1
0
1
0
0
1
1
0
1
1
1
0
0
0
Esvaziando
1
1
0
0
0
0
0
0
1
1
0
1
1
1
0
0
1
1
1
0
1
1
0
1
1
1
1
1
1
1
0
1
Expressões dos Decodificadores: 
Decodificador de Próximo Estado
32
Nome do Estado
Estado Atual
Entradas
Estado Futuro
Saídas
A
B
High
LowAF
BF
Motor
Alarme
Vazio
0
0
0
0
0
0
1
0
0
0
0
1
0
1
1
0
0
0
1
0
0
0
0
1
0
0
1
1
0
0
0
1
Enchendo
0
1
0
0
0
1
0
1
0
1
0
1
0
1
1
0
0
1
1
0
0
1
0
1
0
1
1
1
1
0
0
0
Cheio
1
0
0
0
1
0
0
1
1
0
0
1
1
1
0
0
1
0
1
0
1
0
0
1
1
0
1
1
1
0
0
0
Esvaziando
1
1
0
0
0
0
0
0
1
1
0
1
1
1
0
0
1
1
1
0
1
1
0
1
1
1
1
1
1
1
0
1
HL
AB
00
01
11
10
AF= AB' + AL + AH + BHL
= A(B' + H + L) + BHL
00
01
1
11
1
1
1
10
1
1
1
1
HL
AB
00
01
11
10
BF=H'L+A'BL' + ABH =
= B(A'L' + AH) +H'L
00
1
01
1
1
1
11
1
1
1
10
1
33
Nome do Estado
Estado Atual
Entradas
Estado Futuro
Saídas
A
B
High
Low
AF
BF
Motor
Alarme
Vazio
0
0
0
0
0
0
1
0
0
0
0
1
0
1
1
0
0
0
1
0
0
0
0
1
0
0
1
1
0
0
0
1
Enchendo
0
1
0
0
0
1
0
1
0
1
0
1
0
1
1
0
0
1
1
0
0
1
0
1
0
1
1
1
1
0
0
0
Cheio
1
0
0
0
1
0
0
1
1
0
0
1
1
1
0
0
1
0
1
0
1
0
0
1
1
0
1
1
1
0
0
0
Esvaziando
1
1
0
0
0
0
0
0
1
1
0
1
1
1
0
0
1
1
1
0
1
1
0
1
1
1
1
1
1
1
0
1
Expressões dos Decodificadores: 
Decodificador de Saída
34
Nome do Estado
Estado Atual
Entradas
Estado Futuro
Saídas
A
B
High
Low
AF
BF
Motor
Alarme
Vazio
0
0
0
0
0
0
1
0
0
0
0
1
0
1
1
0
0
0
1
0
0
0
0
1
0
0
1
1
0
0
0
1
Enchendo
0
1
0
0
0
1
0
1
0
1
0
1
0
1
1
0
0
1
1
0
0
1
0
1
0
1
1
1
1
0
0
0
Cheio
1
0
0
0
1
0
0
1
1
0
0
1
1
1
0
0
1
0
1
0
1
0
0
1
1
0
1
1
1
0
0
0
Esvaziando
1
1
0
0
0
0
0
0
1
1
0
1
1
1
0
0
1
1
1
0
1
1
0
1
1
1
1
1
1
1
0
1
HL
AB
00
01
11
10
Motor =A'B'H' +A'H'L
=A'H'(B' + L)
00
1
1
01
1
11
10
HL
AB
00
01
11
10
Alarme =
=A'B‘H +A'BL’ + ABH +AB'L’
= H(A'B’ + AB) + L'(A‘B + AB‘)
= H(AB)' + L'(AB)
00
1
1
01
1
1
11
1
1
10
1
1
35
Exemplo: 
Demais tarefas
Por fim, defina o estado default dos sinais de CLEAR e PRESET dos FFs, de acordo com os estados iniciais
36
Expressões do Reset Assíncrono: 
Preset e Clear dos Flip-Flops
Reset
High
Low
Estado
A
B
nPRA
nCLRA
nPRB
nCLRB
0
0
0
Mantém
-
-
1
1
1
1
0
0
1
Mantém
-
-
1
1
1
1
0
1
0
Mantém
-
-
1
1
1
1
0
1
1
Mantém
-
-
1
1
1
1
1
0
0
Vazio
0
0
1
0
1
0
1
0
1
Enchendo
0
1
1
0
0
1
1
1
0
Esvaziando
1
1
0
1
0
1
1
1
1
Cheio
1
0
0
1
1
0
HL
RST
00
01
11
10
nPRA= RST' + H'
0
1
1
1
1
1
1
1
HL
RST
00
01
11
10
nCLRA= RST' + H
0
1
1
1
1
1
1
1
37
Expressões do Reset Assíncrono: 
Preset e Clear dos Flip-Flops
Reset
High
Low
Estado
A
B
nPRA
nCLRA
nPRB
nCLRB
0
0
0
Mantém
-
-
1
1
1
1
0
0
1
Mantém
-
-
1
1
1
1
0
1
0
Mantém
-
-
1
1
1
1
0
1
1
Mantém
-
-
1
1
1
1
1
0
0
Vazio
0
0
1
0
1
0
1
0
1
Enchendo
0
1
1
0
0
1
1
1
0
Esvaziando
1
1
0
1
0
1
1
1
1
Cheio
1
0
0
1
1
0
HL
RST
00
01
11
10
nPRB= RST' +H'L' + HL
= RST' + (HL)'
0
1
1
1
1
1
1
1
HL
RST
00
01
11
10
nCLRB= RST' +H'L+ HL‘
= RST' + (HL)
0
1
1
1
1
1
1
1
38
Análise de uma FSM
Calcular a quantidade de estados a partir do total de FFs
Cada FF corresponde a uma variável de estado
O total de variáveis de estado é o total de FFs
39
Análise de uma FSM
Calcular a quantidade de estados a partir do total de FFs
Cada FF corresponde a uma variável de estado
O total de variáveis de estado é o total de FFs
Identificar as entradas e saídas externas
Separar as entradas e saídas de dados das entradas de clock e RESET
40
Análise de uma FSM
Calcular a quantidade de estados a partir do total de FFs
Cada FF corresponde a uma variável de estado
O total de variáveis de estado é o total de FFs
Identificar as entradas e saídas externas
Separar as entradas e saídas de dados das entradas de clock e RESET
Levantar as expressões algébricas das saídas dos decodificadores
41
Análise de uma FSM
Calcular a quantidade de estados a partir do total de FFs
Cada FF corresponde a uma variável de estado
O total de variáveis de estado é o total de FFs
Identificar as entradas e saídas externas
Separar as entradas e saídas de dados das entradas de clock e RESET
Levantar as expressões algébricas das saídas dos decodificadores
Preencher a tabela de estados para análise
42
Análise de uma FSM
Calcular a quantidade de estados a partir do total de FFs
Cada FF corresponde a uma variável de estado
O total de variáveis de estado é o total de FFs
Identificar as entradas e saídas externas
Separar as entradas e saídas de dados das entradas de clock e RESET
Levantar as expressões algébricas das saídas dos decodificadores
Preencher a tabela de estados para análise
Desenhar o diagrama de estados
Informar quais são os estados iniciais (se houverem), sinalizando a operação de RESET
43
Tabela de Estados para Análise
ESTADO ATUAL
ENTRADAS
SAÍDAS DO D.P.E.
ESTADO FUTURO
SAÍDAS
Variáveis de estado
Variáveis de Entrada
Entradas dos FF
Variáveis de estado
Variáveis de Saída
  
  
  
  
  
44
Exercício (Análise)
Exercício (Análise)
Nome do Estado
Estado Atual
Entradas
Saídas DPE
Estado Futuro
Saídas
A
B
AF
BF
1. Identificando variáveis de estado
45
Exercício (Análise)
Nome do Estado
Estado Atual
Entradas
Saídas DPE
Estado Futuro
Saídas
A
B
X
Y
AF
BF
S
2. Identificando entradas e saídas
46
Exercício (Análise)
Nome do Estado
Estado Atual
Entradas
Saídas DPE
Estado Futuro
Saídas
A
B
X
Y
DA= Y
JB= X
KB= YB'
AF
BF
S
3. Levantando expressões: Decodificador de Próximo Estado
47
Exercício (Análise)
Nome do Estado
Estado Atual
Entradas
Saídas DPE
Estado Futuro
Saídas
A
B
X
Y
DA= Y
JB= X
KB= YB'
AF
BF
S = A.(X+B')'
3. Levantando expressões: Decodificador de Saída
48
Exercício (Análise)
Nome do Estado
Estado Atual
Entradas
Saídas DPE
Estado Futuro
Saídas
A
B
X
Y
DA= Y
JB= X
KB= YB'
AF
BF
S = A.(X+B')'
0
0
0
0
0
0
0
0
1
1
1
1
1
1
1
1
4. Preenchendo a tabela de estados (análise)
Exercício (Análise)
Nome do Estado
Estado Atual
Entradas
Saídas DPE
Estado Futuro
Saídas
A
B
X
Y
DA= Y
JB= X
KB= YB'
AF
BF
S = A.(X+B')'
0
0
0
0
0
0
0
0
0
1
0
1
0
1
0
1
1
0
1
0
1
0
1
0
1
1
1
1
1
1
1
1
4. Preenchendo a tabela de estados (análise)
Exercício (Análise)
Nome do Estado
Estado Atual
Entradas
Saídas DPE
Estado Futuro
Saídas
A
B
X
Y
DA= Y
JB= X
KB= YB'
AF
BF
S = A.(X+B')'
0
0
0
0
0
0
0
0
1
0
0
1
0
1
0
0
1
0
0
1
1
0
1
1
1
0
0
1
0
0
1
0
1
1
0
1
1
1
0
1
1
0
1
1
1
1
1
1
4. Preenchendo a tabela de estados (análise)
Exercício (Análise)
Nome do Estado
Estado Atual
Entradas
Saídas DPE
Estado Futuro
Saídas
A
B
X
Y
DA= Y
JB= X
KB= YB'
AF
BF
S = A.(X+B')'
0
0
0
0
0
0
0
1
0
0
1
0
0
0
1
1
0
1
0
0
0
1
0
1
0
1
1
0
0
1
1
1
1
0
0
0
1
0
0
1
1
0
1
0
1
0
1
1
1
1
0
0
1
1
0
1
1
1
1
0
1
1
1
1
4. Preenchendo a tabela de estados (análise)
Exercício (Análise)
Nome do Estado
Estado Atual
Entradas
Saídas DPE
Estado Futuro
Saídas
A
B
X
Y
DA= Y
JB= X
KB= YB'
AF
BF
S = A.(X+B')'
S0
0
0
0
0
0
0
0
1
0
0
1
0
0
0
1
1
S1
0
1
0
0
0
1
0
1
0
1
1
0
0
1
1
1
S2
1
0
0
0
1
0
0
1
1
0
1
0
1
0
1
1
S3
1
1
0
0
1
1
0
1
1
1
1
0
1
1
1
1
4. Preenchendo a tabela de estados (análise)
Exercício (Análise)
Nome do EstadoEstado Atual
Entradas
Saídas DPE
Estado Futuro
Saídas
A
B
X
Y
DA= Y
JB= X
KB= YB'
AF
BF
S = A.(X+B')'
S0
0
0
0
0
0
0
0
0
1
1
0
0
1
0
0
0
0
1
1
1
S1
0
1
0
0
0
0
1
0
1
1
0
1
1
0
0
0
1
1
1
1
S2
1
0
0
0
0
1
0
0
1
1
1
0
1
0
0
1
0
1
1
1
S3
1
1
0
0
0
1
1
0
1
1
1
1
1
0
0
1
1
1
1
1
4. Preenchendo a tabela de estados (análise)
Exercício (Análise)
Nome do Estado
Estado Atual
Entradas
Saídas DPE
Estado Futuro
Saídas
A
B
X
Y
DA= Y
JB= X
KB= YB'
AF
BF
S = A.(X+B')'
S0
0
0
0
0
0
0
0
0
0
1
1
0
0
0
1
0
0
1
0
0
1
1
1
1
S1
0
1
0
0
0
0
0
1
0
1
1
0
0
1
1
0
0
1
0
1
1
1
1
1
S2
1
0
0
0
0
0
1
0
0
1
1
0
1
0
1
0
0
1
1
0
1
1
1
1
S3
1
1
0
0
0
0
1
1
0
1
1
0
1
1
1
0
0
1
1
1
1
1
1
1
4. Preenchendo a tabela de estados (análise)
Exercício (Análise)
Nome do Estado
Estado Atual
Entradas
Saídas DPE
Estado Futuro
Saídas
A
B
X
Y
DA= Y
JB= X
KB= YB'
AF
BF
S = A.(X+B')'
S0
0
0
0
0
0
0
1
0
0
0
1
1
0
0
0
0
1
0
0
1
1
0
0
1
1
1
1
0
S1
0
1
0
0
0
0
0
0
1
0
1
1
0
1
0
1
1
0
0
1
0
0
1
1
1
1
1
1
S2
1
0
0
0
0
0
1
1
0
0
1
1
0
0
1
0
1
0
0
1
1
1
0
1
1
1
1
0
S3
1
1
0
0
0
0
0
1
1
0
1
1
0
1
1
1
1
0
0
1
0
1
1
1
1
1
1
1
4. Preenchendo a tabela de estados (análise)
Exercício (Análise)
Nome do Estado
Estado Atual
Entradas
Saídas DPE
Estado Futuro
Saídas
A
B
X
Y
DA= Y
JB= X
KB= YB'
AF
BF
S = A.(X+B')'
S0
0
0
0
0
0
0
1
0
0
0
0
1
1
0
0
0
0
0
1
0
0
1
1
0
0
0
1
1
1
1
0
0
S1
0
1
0
0
0
0
0
0
0
1
0
1
1
0
1
0
0
1
1
0
0
1
0
0
0
1
1
1
1
1
1
0
S2
1
0
0
0
0
0
1
1
0
0
1
1
0
0
1
0
1
0
0
1
1
1
0
1
1
1
1
0
S3
1
1
0
0
0
0
0
1
1
0
1
1
0
1
1
1
1
0
0
1
0
1
1
1
1
1
1
1
4. Preenchendo a tabela de estados (análise)
Exercício (Análise)
Nome do Estado
Estado Atual
Entradas
Saídas DPE
Estado Futuro
Saídas
A
B
X
Y
DA= Y
JB= X
KB= YB'
AF
BF
S = A.(X+B')'
S0
0
0
0
0
0
0
1
0
0
0
0
1
1
0
0
0
0
0
1
0
0
1
1
0
0
0
1
1
1
1
0
0
S1
0
1
0
0
0
0
0
0
0
1
0
1
1
0
1
0
0
1
1
0
0
1
0
0
0
1
1
1
1
1
1
0
S2
1
0
0
0
0
0
1
0
1
0
0
1
1
0
0
0
1
0
1
0
0
1
1
0
1
0
1
1
1
1
0
0
S3
1
1
0
0
0
0
0
1
1
0
1
1
0
1
1
1
1
0
0
1
0
0
1
1
1
1
1
1
1
0
4. Preenchendo a tabela de estados (análise)
Exercício (Análise)
Nome do Estado
Estado Atual
Entradas
Saídas DPE
Estado Futuro
Saídas
A
B
X
Y
DA= Y
JB= X
KB= YB'
AF
BF
S = A.(X+B')'
S0
0
0
0
0
0
0
1
0
0
0
0
1
1
0
0
0
0
0
1
0
0
1
1
0
0
0
1
1
1
1
0
0
S1
0
1
0
0
0
0
0
0
0
1
0
1
1
0
1
0
0
1
1
0
0
1
0
0
0
1
1
1
1
1
1
0
S2
1
0
0
0
0
0
1
0
1
0
0
1
1
0
0
0
1
0
1
0
0
1
1
0
1
0
1
1
1
1
0
0
S3
1
1
0
0
0
0
0
1
1
1
0
1
1
0
1
1
1
1
1
0
0
1
0
0
1
1
1
1
1
1
1
0
4. Preenchendo a tabela de estados (análise)
Exercício (Análise)
Nome do Estado
Estado Atual
Entradas
Saídas DPE
Estado Futuro
Saídas
A
B
X
Y
DA= Y
JB= X
KB= YB'
AF
BF
S = A.(X+B')'
S0
0
0
0
0
0
0
1
0
0
0
0
0
1
1
0
0
1
0
0
0
1
0
0
1
1
0
0
0
0
1
1
1
1
0
1
0
S1
0
1
0
0
0
0
0
0
0
0
1
0
1
1
0
1
1
0
0
1
1
0
0
1
0
0
0
0
1
1
1
1
1
1
1
0
S2
1
0
0
0
0
0
1
0
0
1
0
0
1
1
0
0
1
0
1
0
1
0
0
1
1
0
0
1
0
1
1
1
1
0
1
0
S3
1
1
0
0
0
0
0
0
1
1
1
0
1
1
0
1
1
1
1
1
1
0
0
1
0
0
0
1
1
1
1
1
1
1
1
0
4. Preenchendo a tabela de estados (análise)
Exercício (Análise)
Nome do Estado
Estado Atual
Entradas
Saídas DPE
Estado Futuro
Saídas
A
B
X
Y
DA= Y
JB= X
KB= YB'
AF
BF
S = A.(X+B')'
S0
0
0
0
0
0
0
1
0
0
0
0
0
0
1
1
0
0
1
0
0
0
1
0
0
1
1
0
0
0
0
1
1
1
1
0
1
1
0
S1
0
1
0
0
0
0
0
0
0
0
1
0
1
1
0
1
1
0
0
0
1
1
0
0
1
0
0
1
0
0
1
1
1
1
1
1
1
0
S2
1
0
0
0
0
0
1
0
0
0
1
0
0
1
1
0
0
1
0
1
0
1
0
0
1
1
0
0
1
0
1
1
1
1
0
1
1
0
S3
1
1
0
0
0
0
0
0
1
1
1
0
1
1
0
1
1
0
1
1
1
1
0
0
1
0
0
1
0
1
1
1
1
1
1
1
1
0
4. Preenchendo a tabela de estados (análise)
Exercício (Análise)
Nome do Estado
Estado Atual
Entradas
Saídas DPE
Estado Futuro
Saídas
A
B
X
Y
DA= Y
JB= X
KB= YB'
AF
BF
S = A.(X+B')'
S0
0
0
0
0
0
0
1
0
0
0
0
0
0
1
1
0
0
1
0
0
0
0
1
0
0
1
1
0
0
0
0
1
1
1
1
0
1
1
0
S1
0
1
0
0
0
0
0
0
1
0
0
1
0
1
1
0
1
1
0
0
0
1
1
0
0
1
0
0
1
0
0
1
1
1
1
1
1
1
0
S2
1
0
0
0
0
0
1
0
0
0
1
0
0
1
1
0
0
1
0
0
1
0
1
0
0
1
1
0
0
1
0
1
1
1
1
0
1
1
0
S3
1
1
0
0
0
0
0
0
1
1
1
1
0
1
1
0
1
1
0
1
1
1
1
0
0
1
0
0
1
0
1
1
1
1
1
1
1
1
0
4. Preenchendo a tabela de estados (análise)
Exercício (Análise)
Nome do Estado
Estado Atual
Entradas
Saídas DPE
Estado Futuro
Saídas
A
B
X
Y
DA= Y
JB= X
KB= YB'
AF
BF
S = A.(X+B')'
S0
0
0
0
0
0
0
1
0
0
0
0
0
0
1
1
0
0
1
0
0
0
0
1
0
0
1
1
0
1
0
0
0
1
1
1
1
0
1
1
0
S1
0
1
0
0
0
0
0
0
1
0
0
1
0
1
1
0
1
1
0
0
0
1
1
0
0
1
0
0
1
0
0
1
1
1
1
1
1
1
0
0
S2
1
0
0
0
0
0
1
0
0
0
1
0
0
1
1
0
0
1
0
0
1
0
1
0
0
1
1
0
1
0
1
0
1
1
1
1
0
1
1
0
S3
1
1
0
0
0
0
0
0
1
1
1
1
0
1
1
0
1
1
0
1
1
1
1
0
0
1
0
0
1
0
1
1
1
1
1
1
1
1
0
0
4. Preenchendo a tabela de estados (análise)
Exercício (Análise)
Nome do Estado
Estado Atual
Entradas
Saídas DPE
Estado Futuro
Saídas
A
B
X
Y
DA= Y
JB= X
KB= YB'
AF
BF
S = A.(X+B')'
S0
0
0
0
0
0
0
1
0
0
0
0
0
0
1
1
0
0
1
0
0
0
0
1
0
0
1
1
0
1
0
0
0
1
1
1
1
0
1
1
0
S1
0
1
0
0
0
0
0
0
1
0
0
1
0
1
1
0
1
1
0
0
0
1
1
0
0
1
0
0
1
0
0
1
1
1
1
1
1
1
0
0
S2
1
0
0
0
0
0
1
0
0
0
1
0
0
1
1
0
0
1
0
0
1
0
1
0
0
1
1
0
1
0
1
0
1
1
1
1
0
1
1
0
S3
1
1
0
0
0
0
0
0
1
1
1
1
0
1
1
0
1
1
0
1
1
1
1
0
0
1
0
0
1
0
1
1
1
1
1
1
1
1
0
0
4. Preenchendo a tabela de estados (análise)
Exercício (Análise)
65
XY/S
5. Desenhando o diagrama de estados
01/0
10/0
S2
S3
S0
S1
00/0
10/0
01/0
00/1
10/0
11/0
01/0
11/0
00/0
10/0
00/0
11/0
01/1
11/0
66
Exercício (Análise)
5. Identificando estado inicial (RESET)
67
Exercício (Análise)
5. Identificando estado inicial (RESET)
01/0
10/0
S2
S3
S0
S1
00/0
10/0
01/0
00/1
10/0
11/0
01/0
11/0
00/0
10/0
00/0
11/0
01/1
11/0
68
Exercício (Síntese)
Projete uma máquina de estados que funcione como um contador crescente ou decrescente de 0-9.
Entradas
START/STOP
Sentido de contagem (0=crescente; 1=decrescente)
RESET
CLOCK
SAÍDAS
Valor do contador
Para saber mais
Digital Logic Design Principles
	Norman Balabanian, Bradley Carlson 
	2001
	(capítulo 6 disponível em www.wiley.com/college/engin/balabanian293512/pdf/ch06.pdf)
FSM-based Digital Design using Verilog HDL
	Peter Minns, Ian Elliott
	2008
�
�
�
�
�
�
�
TANQUE
BOMBA
Reservatório
High
Low
Sistema de Controle
BOMBA
Alarme