Maquina de Estados 2

Prévia do material em texto

1
Análise de FSMs
Determinar as equações de excitação
Circuito ligado às entradas dos flip-flops
D1 = X.Q0 + !X.!Q0.Q1
D0 = !X
2
Análise de FSMs
Determinar as equações de próximo estado e de saídas
Q* = D (flip-flop D)
Q1* = X.Q0 + !X.!Q0.Q1
Q0* = !X
Z = Q1.Q0
Mealy ou Moore ?
3
Análise de FSMs
Construir as tabelas de próximo estado e saídas
Q1* = X.Q0 + !X.!Q0.Q1
Q0* = !X
Z = Q1.Q0
Estadoatual
Entrada
Próximoestado
Saída
Q1
Q0
X
Q1*
Q0*
Z
0
0
0
0
0
1
0
1
0
0
1
1
1
0
0
1
0
1
1
1
0
1
1
1
4
Análise de FSMs
Construir as tabelas de próximo estado e saídas
Q1* = X.Q0 + !X.!Q0.Q1
Q0* = !X
Z = Q1.Q0
Estadoatual
Entrada
Próximoestado
Saída
Q1
Q0
X
Q1*
Q0*
Z
0
0
0
0
1
0
0
0
1
0
0
0
0
1
0
0
1
0
0
1
1
1
0
0
1
0
0
1
1
0
1
0
1
0
0
0
1
1
0
0
1
1
1
1
1
1
0
1
5
Análise de FSMs
Construir as tabelas de próximo estado e saídas
Q1* = X.Q0 + !X.!Q0.Q1
Q0* = !X
Z = Q1.Q0
Estadoatual
X
Saída
Q1
Q0
0
1
Z
0
0
01
00
0
0
1
01
10
0
1
0
11
00
0
1
1
01
10
1
Q1*Q0*
Tabela de transição/saídas
6
Análise de FSMs
Desenhar o diagrama de transição de estados
Estadoatual
X
Saída
Q1
Q0
0
1
Z
0
0
01
00
0
0
1
01
10
0
1
0
11
00
0
1
1
01
10
1
Q1*Q0*
Detecta a sequência 010 na entrada X
Análise de FSMs
Logisim
8
Análise de FSMs
Determinar as equações de excitação
Circuito ligado às entradas dos flip-flops
D1 = X.Q0 
D0 = !X
9
Análise de FSMs
Determinar as equações de próximo estado e de saídas
Q* = D (flip-flop D)
Q1*= X.Q0 
Q0* = !X
Z = Q1 . !X
Mealy ou Moore ?
10
Análise de FSMs
Construir as tabelas de próximo estado e saídas
Q1*= X.Q0 
Q0* = !X
Z = Q1.!X
Estadoatual
Entrada
Próximoestado
Saída
Q1
Q0
X
Q1*
Q0*
Z
0
0
0
0
0
1
0
1
0
0
1
1
1
0
0
1
0
1
1
1
0
1
1
1
11
Análise de FSMs
Construir as tabelas de próximo estado e saídas
Q1*= X.Q0 
Q0* = !X
Z = Q1.!X
Estadoatual
Entrada
Próximoestado
Saída
Q1
Q0
X
Q1*
Q0*
Z
0
0
0
0
1
0
0
0
1
0
0
0
0
1
0
0
1
0
0
1
1
1
0
0
1
0
0
0
1
1
1
0
1
0
0
0
1
1
0
0
1
1
1
1
1
1
0
0
12
Análise de FSMs
Construir as tabelas de próximo estado e saídas
Q1*= X.Q0 
Q0* = !X
Z = Q1.!X
Estadoatual
X
Q1
Q0
0
1
0
0
01, 0
00, 0
0
1
01, 0
10, 0
1
0
01, 1
00, 0
1
1
01, 1
10, 0
Q1*Q0*, Z
13
Análise de FSMs
Desenhar o diagrama de transição de estados
Estadoatual
X
Q1
Q0
0
1
0
0
01, 0
00, 0
0
1
01, 0
10, 0
1
0
01, 1
00, 0
1
1
01, 1
10, 0
Q1*Q0*, Z
Detecta a sequência 010 na entrada X
Estado inatingível
Análise de FSMs
Logisim
Máquinas de estado (síntese) 
15
Digital Design - Principles And Practices
John Wakerly
16
Síntese de FSMs
Geração do circuito a partir da descrição do seu comportamento
Exemplo de especificação
Projetar um contador crescente/decrescente de 2 bits
Crescente 00 → 01 → 10 → 11
Decrescente 00→ 11 → 10 → 01
A direção da contagem é determinada por uma entrada denominada UP
Se UP = 1 a contagem é crescente
Se UP = 0 a contagem é decrescente
Além disso, o circuito possui uma entrada de habilitação denominada H
Se H = 0 a contagem pára
Se H = 1 a cada borda ascendente do clock a contagem avança uma unidade sentido selecionado (crescente ou decrescente, conforme o valor de UP)
17
Síntese de FSMs
Passos para a síntese
Construir o diagrama de estados adotando um modelo de FSM (Moore ou Mealy)
Determinar as transições necessárias entre estados
Selecionar um estado para servir como estado inicial (reset)
Construir a tabela de próximo estado e saídas (transição)
Determinar as equações de próximo estado e de saídas
Mapas de Karnaugh
Determinar as equações de excitação
Mesmas equações do passo anterior no caso de flip-flops D
Desenhar o circuito
18
Síntese de FSMs
Construir o diagrama de estados adotando um modelo de FSM (Moore ou Mealy)
Moore
Estado inicial
Saídas serão as variáveis de estado (Q0 e Q1)
Como travar a contagem no valor máximo ?
19
Síntese de FSMs
Construir a tabela de próximo estado e saídas
Estadoatual
H/UP
Q1
Q0
00
01
10
11
0
0
0
1
1
0
1
1
Q1*Q0*
Q1Q0 = 00
Q1Q0 = 01
Q1Q0 = 10
Q1Q0 = 11
Tabela de transição/saída
20
Síntese de FSMs
Construir a tabela de próximo estado e saídas
Estadoatual
H/UP
Q1
Q0
00
01
10
11
0
0
00
00
11
01
0
1
01
01
00
10
1
0
10
10
01
11
1
1
11
11
10
00
Q1*Q0*
Q1Q0 = 00
Q1Q0 = 01
Q1Q0 = 10
Q1Q0 = 11
Tabela de transição/saída
Não há colunas para saídas porque elas são as variáveis de estado (Q0 e Q1)
21
Síntese de FSMs
Determinar as equações de próximo estado e de saídas
Estadoatual
H/UP
Q1
Q0
00
01
10
11
0
0
00
00
11
01
0
1
01
01
00
10
1
0
10
10
01
11
1
1
11
11
10
00
Q1*Q0*
Q1*
H/UP
Q1Q0
00
01
11
10
00
01
11
10
22
Síntese de FSMs
Determinar as equações de próximo estado e de saídas
Estadoatual
H/UP
Q1
Q0
00
01
10
11
0
0
00
00
11
01
0
1
01
01
00
10
1
0
10
10
01
11
1
1
11
11
10
00
Q1*Q0*
Q1*
H/UP
Q1Q0
00
01
11
10
00
0
0
0
1
01
0
0
1
0
11
1
1
0
1
10
1
1
1
0
Q1* = Q1.!H + Q1.Q0.!UP + Q1.!Q0.UP + !Q1.Q0.H.UP + !Q1.!Q0.H.!UP
23
Síntese de FSMs
Determinar as equações de próximo estado e de saídas
Estadoatual
H/UP
Q1
Q0
00
01
10
11
0
0
00
00
11
01
0
1
01
01
00
10
1
0
10
10
01
11
1
1
11
11
10
00
Q1*Q0*
Q0*
H/UP
Q1Q0
00
01
11
10
00
01
11
10
24
Síntese de FSMs
Determinar as equações de próximo estado e de saídas
Estadoatual
H/UP
Q1
Q0
00
01
10
11
0
0
00
00
11
01
0
1
01
01
00
10
1
0
10
10
01
11
1
1
11
11
10
00
Q1*Q0*
Q0*
H/UP
Q1Q0
00
01
11
10
00
0
0
1
1
01
1
1
0
0
11
1
1
0
0
10
0
0
1
1
Q0* = Q0.!H + !Q0.H 
25
Síntese de FSMs
Determinar as equações de excitação
Equação caracterísca do flip-flop D: Q* = D
D0 = Q0.!H + !Q0.H
D1 = Q1.!H + Q1.Q0.!UP + Q1.!Q0.UP + !Q1.Q0.H.UP + !Q1.!Q0.H.!UP
26
Síntese de FSMs
Desenhar o circuito
D0 = Q0.!H + !Q0.H
D1 = Q1.!H + Q1.Q0.!UP + Q1.!Q0.UP + !Q1.Q0.H.UP + !Q1.!Q0.H.!UP
Como fazer o circuito operar na borda descendente do clock ?
Próximo estado
27
Síntese de FSMs
Logisim
28
Síntese de FSMs
Projetar o circuito de controle que permita realizar um swap entre R1 e R2, utilizando R3 como temporário
W=1 inicia o swap
Done=1 indica o fim do swap
8 bits
29
Síntese de FSMs
Para realizar o swap entre R1 e R2, é necessário realizar a seguinte seqüência de transferências entre registradores
R3 ← R2
R2 ← R1
R1 ← R3
1
=1
=1
30
Síntese de FSMs
Para realizar o swap entre R1 e R2, é necessário realizar a seguinte seqüência de transferências entre registradores
R3 ← R2
R2 ← R1
R1 ← R3
1
2
=1
=1
31
Síntese de FSMs
Para realizar o swap entre R1 e R2, é necessário realizar a seguinte seqüência de transferências entre registradores
R3 ← R2
R2 ← R1
R1 ← R3
1
2
3
=1
1=
Síntese de FSMs
Logisim
33
Síntese de FSMs
Construir o diagrama de estados adotando um modelo de FSM (Moore ou Mealy)
A entrada w indica o início da operação swap
R3 ← R2
R2 ← R1
R1 ← R3
Transição só depende do clock
Moore
Done 1 ciclo adiantado!
34
Síntese de FSMs
Construir a tabela de próximo estado e saídas
Estadoatual
W
H1
C1
H2
C2
H3
C3
Done
Q1
Q0
0
1
0
0
0
1
1
0
1
1
Q1*Q0*
Q1Q0 = 00
Q1Q0 = 01
Q1Q0 = 10
Q1Q0 = 11
Tabela de transição/saída
35
Síntese de FSMs
Construir a tabela de próximo estado e saídas
Estadoatual
W
H1
C1
H2
C2
H3
C3
Done
Q1
Q0
0
1
0
0
00
01
0
0
0
0
0
0
0
0
1
1010
0
0
1
0
0
1
0
1
0
11
11
1
0
0
1
0
0
0
1
1
00
00
0
1
0
0
1
0
1
Q1*Q0*
Q1Q0 = 00
Q1Q0 = 01
Q1Q0 = 10
Q1Q0 = 11
Tabela de transição/saída
36
Síntese de FSMs
Determinar as equações de próximo estado e de saídas (mapa de Karnaugh)
Estadoatual
W
H1
C1
H2
C2
H3
C3
Done
Q1
Q0
0
1
0
0
00
01
0
0
0
0
0
0
0
0
1
10
10
0
0
1
0
0
1
0
1
0
11
11
1
0
0
1
0
0
0
1
1
00
00
0
1
0
0
1
0
1
Q1*Q0*
Q1*
W
Q1Q0
0
1
00
01
11
10
Q0*
W
Q1Q0
0
1
00
01
11
10
37
Síntese de FSMs
Determinar as equações de próximo estado e de saídas (mapa de Karnaugh)
Estadoatual
W
H1
C1
H2
C2
H3
C3
Done
Q1
Q0
0
1
0
0
00
01
0
0
0
0
0
0
0
0
1
10
10
0
0
1
0
0
1
0
1
0
11
11
1
0
0
1
0
0
0
1
1
00
00
0
1
0
0
1
0
1
Q1*Q0*
Q1*
W
Q1Q0
0
1
00
0
0
01
1
1
11
0
0
10
1
1
Q0*
W
Q1Q0
0
1
00
0
1
01
0
0
11
0
0
10
1
1
Q1* = !Q1.Q0 + Q1.!Q0
Q0* = !Q0.W + Q1.!Q0 
= Q1 ^ Q0
Síntese de FSMs
Determinar as equações de próximo estado e de saídas
Estadoatual
W
H1
C1
H2
C2
H3
C3
Done
Q1
Q0
0
1
0
0
00
01
0
0
0
0
0
0
0
0
1
10
10
0
0
1
0
0
1
0
1
0
11
11
1
0
0
1
0
0
0
1
1
00
00
0
1
0
0
1
0
1
Q1*Q0*
H1 = C2 = Q1 . !Q0
C1 = H3 = Done = Q1 . Q0
H2 = C3 = !Q1 . Q0
39
Síntese de FSMs
Determinar as equações de excitação
Equação caracterísca do flip-flop D: Q* = D
D0 = !Q0.W + Q1.!Q0 
D1 = !Q1.Q0 + Q1.!Q0 = Q1 ^ Q0 
Síntese de FSMs
Desenhar o circuito
D0 = !Q0.W + Q1.!Q0 
D1 = Q1^Q0
C1 = H3 = Done = Q1.Q0
H1 = C2 = Q1.!Q0
H2 = C3 = !Q1.Q0
Próximo estado
Saídas
Próximo
 estado
Saídas
Síntese de FSMs
Desenhar o circuito (otimização)
D0 = !Q0.W + Q1.!Q0 
D1 = Q1^Q0
C1 = H3 = Done = Q1 . Q0
H1 = C2 = Q1.!Q0
H2 = C3 = !Q1.Q0
Síntese de FSMs
Desenhar o circuito (otimização)
D0 = !Q0.W + Q1.!Q0 
D1 = Q1^Q0
C1 = H3 = Done = Q1 . Q0
H1 = C2 = Q1.!Q0
H2 = C3 = !Q1.Q0
43
Síntese de FSMs
Logisim
44
Síntese de FSMs
Blocos operando em bordas complementares
Sinas de controle gerados na borda de subida
Execução realizada na boda de descida do mesmo ciclo
45
Síntese de FSMs
Implementar um contador Grey
Um código de Gray é um sistema de numeração binário onde dois valores sucessivos diferem de apenas um bit
Exemplo: código de Gray de 3 bits
a sequência de código que representa os números de 0 a 7 é: 000, 001, 011, 010, 110, 111, 101, 100
O circuito deve ter: 
Uma entrada enable que habilita a contagem a cada ciclo de clock
Uma saída first ativa quando o código atual da contagem é o primeiro
Uma saída last ativa quando o código atual da contagem é o último
Os bits da saída code correspondem às saídas dos flip-flops
Clock
Reset
Enable
Code
First
Last
3
Contador
Gray