Maquinas de Estado 1

Prévia do material em texto

Máquinas de estado (análise)
Digital Design - Principles And Practices
John Wakerly
1
Introdução
Tipos de circuitos digitais
Combinacionais
O valor das saídas depende unicamente do valor das entradas
O valor das saídas é sempre igual para um mesmo valor de entrada
Não são capazes de reter os valores das saídas
Exemplos: Multiplexadores, somadores, decodificadores, ...
Sequênciais
O valor das saídas é determinado não somente a partir do valor das entradas mas também a partir do estado do circuito
Possuem capacidade de armazenamento
São capazes de reter o valor das saídas
Exemplos: Contadores, processadores
Introdução
Modelo de circuito combinacional
Saídas dependem apenas das entradas
Não tem capacidade de armazenamento de informação (memória)
Assíncronos
Não dependem de clock
Introdução
Modelo de circuito sequêncial
Composto por um circuito combinacional e elementos de memória
Elementos de memória são implementados a partir de flip-flops
Saídas dependem das entradas e do estado atual
Circuito combinacional
Elementos de memória
Entradas
Saídas
n
n
n
Armazenam o estado atual
Laço de realimentação
Introdução
Tipos de circuitos sequências
Assíncronos
Estado atual pode mudar a qualquer momento
Fora do escopo desta disciplina
Síncronos
Estado atual pode mudar apenas momentos exatos determinados por um sinal de clock
Grande maioria dos circuitos digitais (e.g. processador)
Foco desta disciplina
6
Introdução
Máquinas de estado 
Nome dado ao modelo genérico de circuitos sequenciais
Composto por lógica combinacional (portas lógicas) + elementos de memória (flip-flops)
Em inglês FSMs: Finite State Machines
O funcionamento do circuito depende das entradas e do estado em que o circuito se encontra (“estado corrente” ou “estado atual”)
O estado atual do circuito corresponde ao valor das variáveis de estado (saídas dos flip-flops)
O conjunto de flip-flops forma o registrador de estado
Dado o estado atual e o valor das entradas, a FSM gera os valores das saídas e o próximo estado
Lógica combinacional
7
Introdução
Máquinas de estado 
Podem ser de dois tipos
Moore
Mealy
A única diferença entre os dois tipos é em relação à maneira como as saídas do circuito são geradas
8
Introdução
Máquinas de estado 
Moore
As saídas dos circuito dependem apenas do estado atual 
Atualizadas somente em transições do clock
Circuito combinacional que determina o valor das saídas tendo como entrada o estado atual
Flip-flops
(registrador de estado)
Circuito combinacional que determina o próximo estado
Output = G(current state)
NS = F(inputs, current state)
Próximo estado será o estado atual no próximo ciclo de clock
9
Introdução
Máquinas de estado 
Mealy
As saídas dos circuito dependem da combinação entre o estado atual e as entradas
Podem ser atualizadas a qualquer momento em função das entradas
Output = G(current state, inputs)
Entradas são consideradas na geração das saídas
10
Introdução
Máquinas de estado 
Moore
Next state logic
State memory
Output logic
Saída Y depende apenas do estado atual
Estado atual
Entrada
11
Introdução
Máquinas de estado 
Moore
Modelo
Circuito
12
Introdução
Máquinas de estado 
Mealy
Saída MAX depende do estado atual e da entrada EN
13
Introdução
Máquinas de estado 
Mealy
Modelo
Circuito
14
Análise de FSMs
O objetivo da análise é extrair as equações booleanas e o diagrama de estados que determinam o comportamento do circuito
Passos para a análise
Determinar as equações de excitação
Circuito ligado às entradas dos flip-flops
Determinar as equações de próximo estado e de saídas
No caso de flip-flops D as equações de excitação e de próximo estado são iguais
Construir a tabela de próximo estado e saídas
A construção é baseada nas equações obtidas no passo 2
Desenhar o diagrama de transição de estados
Grafo que ilustra o comportamento do circuito
Baseado na tabela obtida no passo 3 
15
Análise de FSMs
Determinar as equações de excitação
Circuito ligado às entradas dos flip-flops
D0 = cnt ^ Q0
D1 = !cnt.Q1 + Q0.cnt.!Q1 + cnt.Q1.!Q0
16
Análise de FSMs
Determinar as equações de próximo estado e de saídas
Equação caracterísca do flip-flop D: Q* = D
Q0* = cnt ^ Q0
Q1* = !cnt.Q1 + Q0.cnt.!Q1 + cnt.Q1.!Q0
Y = Q0.Q1
Mealy ou Moore ?
17
Análise de FSMs
Construir as tabelas de próximo estado e saídas
Q0* = cnt ^ Q0
Q1* = !cnt.Q1 + Q0.cnt.!Q1 + cnt.Q1.!Q0
Y = Q0.Q1
Estadoatual
Entrada
Próximoestado
Saída
Q1
Q0
cnt
Q1*
Q0*
Y
0
0
0
0
0
1
0
1
0
0
1
1
1
0
0
1
0
1
1
1
0
1
1
1
18
Análise de FSMs
Construir as tabelas de próximo estado e saídas
Q0* = cnt ^ Q0
Q1* = !cnt.Q1 + Q0.cnt.!Q1 + cnt.Q1.!Q0
Y = Q0.Q1
Estadoatual
Entrada
Próximoestado
Saída
Q1
Q0
cnt
Q1*
Q0*
Y
0
0
0
0
0
0
0
0
1
0
1
0
0
1
0
0
1
0
0
1
1
1
0
0
1
0
0
1
0
0
1
0
1
1
1
0
1
1
0
1
1
1
1
1
1
0
0
1
19
Análise de FSMs
Construir as tabelas de próximo estado e saídas
Q0* = cnt ^ Q0
Q1* = !cnt.Q1 + Q0.cnt.!Q1 + cnt.Q1.!Q0
Y = Q0.Q1
Estadoatual
cnt
Saída
Q1
Q0
0
1
Y
0
0
00
01
0
0
1
01
10
0
1
0
10
11
0
1
1
11
00
1
Q1*Q0*
Tabela de transição/saídas
Depende só do estado atual
(Moore)
20
Análise de FSMs
Desenhar o diagrama de transição de estados
Estadoatual
cnt
Saída
Q1
Q0
0
1
Y
0
0
00
01
0
0
1
01
10
0
1
0
10
11
0
1
1
11
00
1
Q1*Q0*
Contador de 2 bits. A saída Y indica quando a contagem chegou no valor máximo (3). A entrada cnt habilita a contagem.
Estado inicial
Valor da saída indicado dentro do estado (Moore)
Condição explícita para ocorrer a transição de estado. Obs: Clock implícito.
21
Análise de FSMs
Desenhar o diagrama de transição de estados
Pode-se atribuir nomes aos estados
Estadoatual
cnt
Saída
S
0
1
Y
S0
S0
S1
0
S1
S1
S2
0
S2
S2
S3
0
S3
S3
S0
1
S*
Contador de 2 bits. A saída Y indica quando a contagem chegou no valor máximo (3). A entrada cnt habilita a contagem.
22
Análise de FSMs
Exemplo de comportamento
Síncronas (CK)
Q0
Q1
Estado atual S0 S1 S2 S3 S3
Atraso de propagação de D para Q no FF
Atraso do FF mais atraso da porta and
Análise de FSMs
Logisim
24
Análise de FSMs
Determinar as equações de excitação
D0 = cnt ^ Q0
D1 = !cnt.Q1 + Q0.cnt.!Q1 + cnt.Q1.!Q0
Conexão adicionada
25
Análise de FSMs
Determinar as equações de próximo estado e de saídas
Equação caracterísca do flip-flop D: Q* = D
Q0* = cnt ^ Q0
Q1* = !cnt.Q1 + Q0.cnt.!Q1 + cnt.Q1.!Q0
Y = cnt.Q0.Q1
Mealy ou Moore ?
26
Análise de FSMs
Construir as tabelas de próximo estado e saídas
Q0* = cnt ^ Q0
Q1* = !cnt.Q1 + Q0.cnt.!Q1 + cnt.Q1.!Q0
Y = cnt.Q0.Q1
Estadoatual
Entrada
Próximoestado
Saída
Q1
Q0
cnt
Q1*
Q0*
Y
0
0
0
0
0
0
0
0
1
0
1
0
0
1
0
0
1
0
0
1
1
1
0
0
1
0
0
1
0
0
1
0
1
1
1
0
1
1
0
1
1
0
1
1
1
0
0
1
27
Análise de FSMs
Construir as tabelas de próximo estado e saídas
Q0* = cnt ^ Q0
Q1* = !cnt.Q1 + Q0.cnt.!Q1 + cnt.Q1.!Q0
Y = cnt.Q0.Q1
Estadoatual
cnt
Q1
Q0
0
1
0
0
00, 0
01, 0
0
1
01, 0
10, 0
1
0
10, 0
11, 0
1
1
11,0
00, 1
Q1*Q0*, Y
Tabela de transição/saídas
Próximo estado, saídas
Não há colunas para as saídas porque elas dependendem também das entradas
(Mealy)
O valor da saída Y é 0 ou 1, dependendo do valor da entrada cnt
28
Análise de FSMs
Desenhar o diagrama de transição de estados
Estadoatual
cnt
Q1
Q0
0
1
0
0
00, 0
01, 0
0
1
01, 0
10, 0
1
0
10, 0
11, 0
1
1
11, 0
00, 1
Q1*Q0*, Y
Condição explícita para ocorrer a transição de estado /Valor da saída
A notação para as saídas pode confundir. O valor das saídas é produzido continuamente enquando a máquina está no estado origem da aresta e tem a entrada indicada, não apenas durante a transição.
No estado 11, 
Y<=1 enquanto cnt = 1
cnt=0/Y<=0
29
Análise de FSMs
Desenhar o diagrama de transição de estados
Pode-se atribuir nomes aos estados
Estadoatual
cnt
S
0
1
S0
S0, 0
S1, 0
S1
S1, 0
S2, 0
S2
S2, 0
S3, 0
S3
S3, 0
S0, 1
S*, Y
S0
S1
S2
S2
30
Análise de FSMs
Exemplo de comportamento
Síncronas (CK)
Q0
Q1
cnt
Estado atual S0 S1 S2 S3 S3
Análise de FSMs
Logisim
32
Análise de FSMs
Comparação de comportamento (Mealy e Moore)
S
 S0 S0 S1 S2 S2 S2 S3 S3 S3 S0 S0 
Y depende só do estado atual
33
Análise de FSMs
Comparação de comportamento (Mealy e Moore)
S
 S0 S0 S1 S2 S2 S2 S3 S3 S3 S0 S0 
Y depende só do estado atual e da entrada cnt
34
Análise de FSMs
Tabelas de transição/saídas (Moore)
Várias entradas/saídas
Estadoatual
a/b
X
Y
Z
Q1
Q0
00
01
10
11
0
0
01
00
00
01
1
1
0
0
1
01
01
00
10
0
1
0
1
0
10
10
11
11
0
0
0
1
1
11
11
10
00
1
1
1
Q1*Q0*
Estadoatual
a/b/c
X
Y
Q1
Q0
000
001
010
011
100
101
110
111
0
0
00
01
00
00
01
00
01
01
1
1
0
1
01
01
11
01
00
01
01
10
0
1
1
0
10
10
00
00
11
10
00
11
0
0
1
1
11
10
11
10
11
11
10
00
1
1
Q1*Q0*
2 entradas (a,b) e 3 saídas (X,Y,Z)
3 entradas (a,b,c) e 2 saídas (X,Y)
35
Análise de FSMs
Tabelas de transição/saídas (Mealy)
Várias entradas/saídas
Estadoatual
a/b
Q1
Q0
00
01
10
11
0
0
01, 011
00, 011
00, 011
01, 001
0
1
01, 001
01, 101
00, 011
10, 000
1
0
10, 000
10, 100
11, 100
11, 011
1
1
11, 010
11, 111
10, 110
00, 111
Q1*Q0*, XYZ
Estadoatual
a/b/c
Q1
Q0
000
001
010
011
100
101
110
111
0
0
00, 00
01, 01
00, 11
00, 01
01, 01
00, 10
01, 01
01, 10
0
1
01, 00
01, 01
01, 11
00, 01
10, 00
01, 10
01, 01
10, 10
1
0
10, 00
10, 00
10, 00
11, 00
11, 11
10, 10
10, 00
11, 01
1
1
11, 00
11, 10
11, 11
10, 10
00, 11
11, 01
11, 10
00, 11
Q1*Q0*, XY
2 entradas (a,b) e 3 saídas (X,Y,Z)
3 entradas (a,b,c) e 2 saídas (X,Y)
36
Análise de FSMs
Analisar a FSM abaixo
37
Análise de FSMs
Analisar a FSM abaixo