Maquina de Estados 4

Esta é uma pré-visualização de arquivo. Entre para ver o arquivo original

1
Síntese de FSMs
Diagrama de blocos da máquina de vendas
Quando uma moeda é inserida, o sensor de moedas mantém a saída correspondente em 1 durante um ciclo de clock
As entradas M50 e M1R nunca estão ativas simultaneamente
Quando o crédito é maior/igual a R$ 1,50, o bloco de controle mantém OK=1 durante um ciclo de clock
Quando o crédito é R$ 2,00, o bloco de controle mantém TR50=1 durante um ciclo de clock 
Sintetizar seguindo os modelos de Moore e Mealy
Bloco de controle da máquina de vendas
Sensor de moedas
Mecanismo de liberação
M50
M1R
OK
Clock
Reset
Mecanismo de troco
TR50
2
Síntese de FSMs
Construir o diagrama de estados adotando um modelo de FSM (Moore ou Mealy)
Moore
3
Síntese de FSMs
Construir a tabela de próximo estado e saídas
Estadoatual
M50/M1R
OK
TR50
Q2
Q1
Q0
00
01
10
11
0
0
0
0
0
1
0
1
0
0
1
1
1
0
0
Q2*Q1*Q0*
000
001
010
100
011
4
Síntese de FSMs
Construir a tabela de próximo estado e saídas
Estadoatual
M50/M1R
OK
TR50
Q2
Q1
Q0
00
01
10
11
0
0
0
000
010
001
xxx
0
0
0
0
1
001
011
010
xxx
0
0
0
1
0
010
100
011
xxx
0
0
0
1
1
000
000
000
xxx
1
0
1
0
0
000
000
000
xxx
1
1
Q2*Q1*Q0*
000
001
010
100
011
Síntese de FSMs
Determinar as equações de próximo estado e de saídas
Mapa de Karnaugh com mais de 4 entradas!
Geração automática do circuito com Logisim
Estadoatual
M50/M1R
OK
TR50
Q2
Q1
Q0
00
01
10
11
0
0
0
000
010
001
xxx
0
0
0
0
1
001
011
010
xxx
0
0
0
1
0
010
100
011
xxx
0
0
0
1
1
000
000
000
xxx
1
0
1
0
0
000
000
000
xxx
1
1
Q2*Q1*Q0*
6
Síntese de FSMs
Logisim
7
Síntese de FSMs
Construir o diagrama de estados adotando um modelo de FSM (Moore ou Mealy)
Mealy
8
Síntese de FSMs
Construir a tabela de próximo estado e saídas
Estadoatual
M50/M1R
Q1
Q0
00
01
10
11
0
0
00, 00
10, 00
01, 00
xx, xx
0
1
01, 00
00, 10
10, 00
xx, xx
1
0
10, 00
00, 11
00, 10
xx, xx
1
1
xx, xx
xx, xx
xx, xx
xx, xx
Q1*Q0*, OK/TR50
Q1Q0 = 00
Q1Q0 = 10
Q1Q0 = 01
Síntese de FSMs
Determinar as equações de próximo estado e de saídas
Estadoatual
M50/M1R
Q1
Q0
00
01
10
11
0
0
00, 00
10, 00
01, 00
xx, xx
0
1
01, 00
00, 10
10, 00
xx, xx
1
0
10, 00
00, 11
00, 10
xx, xx
1
1
xx, xx
xx, xx
xx, xx
xx, xx
Q1*Q0*, OK/TR50
Q1*
M50/M1R
Q1Q0
00
01
11
10
00
01
11
10
Síntese de FSMs
Determinar as equações de próximo estado e de saídas
Estadoatual
M50/M1R
Q1
Q0
00
01
10
11
0
0
00, 00
10, 00
01, 00
xx, xx
0
1
01, 00
00, 10
10, 00
xx, xx
1
0
10, 00
00, 11
00, 10
xx, xx
1
1
xx, xx
xx, xx
xx, xx
xx, xx
Q1*Q0*, OK/TR50
Q1*
M50/M1R
Q1Q0
00
01
11
10
00
0
1
X
0
01
0
0
X
1
11
x
x
X
x
10
1
0
x
0
Q1* = Q1.!M50.!M1R + !Q1.!Q0.M1R + Q0.M50
Síntese de FSMs
Determinar as equações de próximo estado e de saídas
Estadoatual
M50/M1R
Q1
Q0
00
01
10
11
0
0
00, 00
10, 00
01, 00
xx, xx
0
1
01, 00
00, 10
10, 00
xx, xx
1
0
10, 00
00, 11
00, 10
xx, xx
1
1
xx, xx
xx, xx
xx, xx
xx, xx
Q1*Q0*, OK/TR50
Q0*
M50/M1R
Q1Q0
00
01
11
10
00
01
11
10
Síntese de FSMs
Determinar as equações de próximo estado e de saídas
Estadoatual
M50/M1R
Q1
Q0
00
01
10
11
0
0
00, 00
10, 00
01, 00
xx, xx
0
1
01, 00
00, 10
10, 00
xx, xx
1
0
10, 00
00, 11
00, 10
xx, xx
1
1
xx, xx
xx, xx
xx, xx
xx, xx
Q1*Q0*, OK/TR50
Q0*
M50/M1R
Q1Q0
00
01
11
10
00
0
0
x
1
01
1
0
x
0
11
x
x
x
x
10
0
0
x
0
Q0* = Q0.!M50.!M1R + !Q1.!Q0.M50
Síntese de FSMs
Determinar as equações de próximo estado e de saídas
Estadoatual
M50/M1R
Q1
Q0
00
01
10
11
0
0
00, 00
10, 00
01, 00
xx, xx
0
1
01, 00
00, 10
10, 00
xx, xx
1
0
10, 00
00, 11
00, 10
xx, xx
1
1
xx, xx
xx, xx
xx, xx
xx, xx
Q1*Q0*, OK/TR50
OK
M50/M1R
Q1Q0
00
01
11
10
00
01
11
10
Síntese de FSMs
Determinar as equações de próximo estado e de saídas
Estadoatual
M50/M1R
Q1
Q0
00
01
10
11
0
0
00, 00
10, 00
01, 00
xx, xx
0
1
01, 00
00, 10
10, 00
xx, xx
1
0
10, 00
00, 11
00, 10
xx, xx
1
1
xx, xx
xx, xx
xx, xx
xx, xx
Q1*Q0*, OK/TR50
OK
M50/M1R
Q1Q0
00
01
11
10
00
0
0
x
0
01
0
1
x
0
11
x
x
x
x
10
0
1
x
1
OK = Q0.M1R + Q1.M1R + Q1.M50 
Síntese de FSMs
Determinar as equações de próximo estado e de saídas
Estadoatual
M50/M1R
Q1
Q0
00
01
10
11
0
0
00, 00
10, 00
01, 00
xx, xx
0
1
01, 00
00, 10
10, 00
xx, xx
1
0
10, 00
00, 11
00, 10
xx, xx
1
1
xx, xx
xx, xx
xx, xx
xx, xx
Q1*Q0*, OK/TR50
TR50
M50/M1R
Q1Q0
00
01
11
10
00
01
11
10
Síntese de FSMs
Determinar as equações de próximo estado e de saídas
Estadoatual
M50/M1R
Q1
Q0
00
01
10
11
0
0
00, 00
10, 00
01, 00
xx, xx
0
1
01, 00
00, 10
10, 00
xx, xx
1
0
10, 00
00, 11
00, 10
xx, xx
1
1
xx, xx
xx, xx
xx, xx
xx, xx
Q1*Q0*, OK/TR50
TR50
M50/M1R
Q1Q0
00
01
11
10
00
0
0
x
0
01
0
0
x
0
11
x
X
x
x
10
0
1
x
0
TR50 = Q1.M1R 
17
Síntese de FSMs
Determinar as equações de excitação
Equação caracterísca do flip-flop D: Q* = D
D0 = Q0.!M50.!M1R + !Q1.!Q0.M50 
D1 = Q1.!M50.!M1R + !Q1.!Q0.M1R + Q0.M50
Síntese de FSMs
Desenhar o circuito
D0 = Q0.!M50.!M1R + !Q1.!Q0.M50 
D1 = Q1.!M50.!M1R + !Q1.!Q0.M1R + Q0.M50
OK = Q0.M1R + Q1.M1R + Q1.M50
TR50 = Q1.M1R
Próximo estado
Saídas
19
Síntese de FSMs
Logisim
20
Síntese de FSMs
Diagrama de blocos da máquina de vendas
Quando uma moeda é inserida, o sensor de moedas mantém a saída correspondente em 1 durante um ciclo de clock
As entradas M25, M50 e M1R nunca estão ativas simultaneamente
Quando o crédito é maior/igual a R$ 1,50, o bloco de controle mantém OK=1 durante um ciclo de clock
Quando necessário, o bloco de controle mantém as saídas de troco em 1 durante um ciclo de clock 
TR25 e TR50 podem estar ativas simultaneamente (R$ 0,75)
Bloco de controle da máquina de vendas
Sensor 
de moedas
Mecanismo de liberação
M25
M50
OK
Clock
Reset
Mecanismo de troco
TR25
TR50
M1R
21
Síntese de FSMs
Construir o diagrama de estados adotando um modelo de FSM (Moore ou Mealy)
Moore
22
Síntese de FSMs
Construir o diagrama de estados adotando um modelo de FSM (Moore ou Mealy)
Mealy
23
Síntese de FSMs
Construir a tabela de próximo estado e saídas (Moore)
Estadoatual
M25/M50/M1R
OK
TR25
TR50
S
000
100
010
001
S0
S25
S50
S75
S1R
S1R25
S1R50
S1R75
S2R
S2R25
S*
Apenas combinações relevantes das entradas
24
Síntese de FSMs
Construir a tabela de próximo estado e saídas (Moore)
Estadoatual
M25/M50/M1R
OK
TR25
TR50
S
000
100
010
001
S0
S0
S25
S50
S1R
0
0
0
S25
S25
S50
S75
S1R25
0
0
0
S50
S50
S75
S1R
S1R50
0
0
0
S75
S75
S1R
S1R25
S1R75
0
0
0
S1R
S1R
S1R25
S1R50
S2R
0
0
0
S1R25
S1R25
S1R50
S1R75
S2R25
0
0
0
S1R50
S0
S0
S0
S0
1
0
0
S1R75
S0
S0
S0
S0
1
1
0
S2R
S0
S0
S0
S0
1
0
1
S2R25
S0
S0
S0
S0
1
1
1
S*
Codificar os estados
Apenas combinações relevantes das entradas
Síntese de FSMs
Determinar as equações de próximo estado e de saídas
Mapa de Karnaugh com 7 entradas!
Geração automática do circuito com Logisim
Estadoatual
M25/M50/M1R
OK
TR25
TR50
Q3Q2Q1Q0
000
100
010
001
0000
0000
0001
0010
0100
0
0
0
0001
0001
0010
0011
0101
0
0
0
0010
0010
0011
0100
0110
0
0
0
0011
0011
0100
0101
0111
0
0
0
0100
0100
0101
0110
1000
0
0
0
0101
0101
0110
0111
1001
0
0
0
0110
0110
0000
0000
0000
1
0
0
0111
0000
0000
0000
0000
1
1
0
1000
0000
0000
0000
0000
1
0
1
1001
0000
0000
0000
0000
1
1
1
Q3*Q2*Q1*Q0*
26
Síntese de FSMs
Logisim
27
Síntese de FSMs
Diminuir o número de entradas da FSM
Entradas M25, M50 e M1R nunca estão ativas simultaneamente
Codificar as entradas
M25
Bloco de controle da máquina de vendas
Sensor 
de moedas
Mecanismo de liberação
M50
OK
Clock
Reset
Mecanismo de troco
TR25
TR50
M1R
Bloco de controle da máquina de vendas
Sensor 
de moedas
Mecanismo de liberação
M25
M50
OK
Clock
Reset
Mecanismo de troco
TR25
TR50
M1R
Decoder
2
code
28
Síntese de FSMs
Diminuir o número de entradas da FSM
Entradas M25, M50 e M1R nunca estão ativas simultaneamente
Codificar as entradas
Code
00	: No coin
01	: M25
10	: M50
11	: M1R
Bloco de controle da máquina de vendas
Sensor 
de moedas
Mecanismo de liberação
M25
M50
OK
Clock
Reset
Mecanismo de troco
TR25
TR50
M1R
Decoder
2
code
29
Síntese de FSMs
Diminuir o número de entradas da FSM
Decoder
Code
00	: No coin
01	: M25
10	: M50
11	: M1R
M25
M50
M1R
Code1
Code0
0
0
0
0
0
0
0
1
1
1
0
1
0
1
0
0
1
1
0
0
1
0
0
0
1
1
0
1
0
0
1
1
0
0
0
1
1
1
0
0
M25
M50
M1R
Decoder
2
code
Problema de múltiplas entradas de moeda ativas resolvido
30
Síntese de FSMs
Diminuir o número de entradas da FSM
Decoder
Code
00	: No coin
01	: M25
10	: M50
11	: M1R
M25
M50
M1R
Decoder
2
code
31
Síntese de FSMs
Construir a tabela de próximo estado e saídas
Estadoatual
Code[1:0]
OK
TR25
TR50
S
00
01
10
11
S0
S0
S25
S50
S1R
0
0
0
S25
S25
S50
S75
S1R25
0
0
0
S50
S50
S75
S1R
S1R50
0
0
0
S75
S75
S1R
S1R25
S1R75
0
0
0
S1R
S1R
S1R25
S1R50
S2R
0
0
0
S1R25
S1R25
S1R50
S1R75
S2R25
0
0
0
S1R50
S0
S0
S0
S0
1
0
0
S1R75
S0
S0
S0
S0
1
1
0
S2R
S0
S0
S0
S0
1
0
1
S2R25
S0
S0
S0
S0
1
1
1
S*
32
Síntese de FSMs
Logisim
33
Síntese de FSMs
Combinação de Mealy e Moore
Frequentemente utilizam-se FSMs que são uma combinação dos modelos de Mealy e Moore
Em um mesmo circuito é possível definir saídas que dependam apenas do estado atual (Moore) e outras que dependem do estado atual e das entradas (Mealy)
Next state logic
State memory
Moore outputs
Mealy outputs
inputs
clock
current state
34
Síntese de FSMs
Combinação de Mealy e Moore
Exemplo: máquina de vendas
Saída OK depende das entradas e do estado atual
Saídas indicativas de crédito CR0, CR50, CR1R dependem apenas do estado atual
35
Síntese de FSMs
Combinação de Mealy e Moore
Tabela de transição de estados/saídas
Estadoatual
M50/M1R
CR0
CR50
CR1R
Q1
Q0
00
01
10
11
0
0
00, 0
10, 0
01, 0
xx, x
1
0
0
0
1
01, 0
00, 1
10, 0
xx, x
0
1
0
1
0
10, 0
00, 1
00,1
xx, x
0
0
1
1
1
xx, x
xx, x
xx, x
xx, x
X
x
x
Q1*Q0*, OK
36
Síntese de FSMs
Codificação de estados
A codificação dos estados tem influência direta na síntese dos circuitos que geram as saídas e o próximo estado
Dependendo da codificação escolhida, os circuitos obtidos podem ser mais simples ou mais complexos
Exemplo: swap
Q1Q0 = 00
Q1Q0 = 01
Q1Q0 = 11
Q1Q0 = 10
Q1Q0 = 00
Q1Q0 = 01
Q1Q0 = 10
Q1Q0 = 11
Codificação alternativa
37
Síntese de FSMs
Codificação de estados
Tabela de próximo estado
Estadoatual
W
Q1
Q0
0
1
0
0
00
01
0
1
11
11
1
0
00
00
1
1
10
10
Q1*Q0*
Q1Q0 = 00
Q1Q0 = 01
Q1Q0 = 11
Q1Q0 = 10
38
Síntese de FSMs
Codificação de estados
Equações de próximo estado
Estadoatual
W
Q1
Q0
0
1
0
0
00
01
0
1
11
11
1
0
00
00
1
1
10
10
Q1*Q0*
Q1*
W
Q1Q0
0
1
00
0
0
01
1
1
11
1
1
10
0
0
Q0*
W
Q1Q0
0
1
00
0
1
01
1
1
11
0
0
10
0
0
Q1* = Q0 
Q0* = !Q1.Q0 + !Q1.W 
Síntese de FSMs
Codificação de estados
Comparação
Codificação alternativa: A=00, B=01, C=11, D=10
Q0* = !Q1.Q0 + !Q1.W 
Q1*= Q0
Codificação trivial: A=00, B=01, C=10, D=11
Q0*= !Q0.W + Q1.!Q0 
Q1*= !Q1.Q0 + Q1.!Q0 = Q1^Q0
Síntese de FSMs
Codificação de estados
Comparação
Circuito para geração do próximo estado
Codificação trivial
Codificação alternativa
Síntese de FSMs
Codificação de estados
A codificação alternativa resultou em menor custo nesse caso devido à mudança de apenas 1 bit de estado em cada transição
Codificação alternativa: A=00 → B=01 → C=11 → D=10 →
Codificação trivial: A=00 → B=01 → C=10 → D=11 →
Codificação Gray
Na transição de um código para outro apenas um bit ou muda
Exemplo: 3 bits
000 → 001 → 011 → 010 → 110 → 111 → 101 → 100
Síntese de FSMs
Codificação de estados
One hot
Utiliza um bit por estado
Tem-se somente um bit em ‘1’ por estado
Bit ativo identifica o estado
Exemplo: codificação de 4 estados
0001, 0010, 0100, 1000
Desvantagem óbvia em relação ao número de flip-flops usados
Entretando os circuitos de próximo estado e saídas tendem a ser mais simples
No máximo 2 bits mudam em qualquer transição
Síntese de FSMs
Codificação de estados
Detector de borda positiva
A cada transição da entrada X de ‘0’ para ‘1’, a saída Z é mantida em ‘1’ durante um ciclo de clock
↑X
X
Clock
Z
44
Síntese de FSMs
Codificação de estados
Tabela de próximo estado e saídas
Codificação one hot
Estadoatual
X
Z
Q2
Q1
Q0
0
1
0
0
1
010
001
0
0
1
0
010
100
0
1
0
0
010
001
1
Q2*Q1*Q0*
Q2Q1Q0 = 001
Q2Q1Q0 = 010
Q2Q1Q0 = 100
45
Síntese de FSMs
Codificação de estados
Equações de próximo estado e de saídas
Q2*
Q0/X
Q2Q1
00
01
11
10
00
x
x
0
0
01
0
1
x
x
11
x
x
x
x
10
0
0
x
x
Q2* = Q1.X
Estadoatual
X
Z
Q2
Q1
Q0
0
1
0
0
1
010
001
0
0
1
0
010
100
0
1
0
0
010
001
1
Q2*Q1*Q0*
46
Síntese de FSMs
Codificação de estados
Equações de próximo estado e de saídas
Q1*
Q0/X
Q2Q1
00
01
11
10
00
x
x
0
1
01
1
0
x
x
11
x
x
x
x
10
1
0
x
x
Q1* = !X
Estadoatual
X
Z
Q2
Q1
Q0
0
1
0
0
1
010
001
0
0
1
0
010
100
0
1
0
0
010
001
1
Q2*Q1*Q0*
47
Síntese de FSMs
Codificação de estados
Equações de próximo estado e de saídas
Q0*
Q0/X
Q2Q1
00
01
11
10
00
x
x
1
0
01
0
0
x
x
11
x
x
x
x
10
0
1
x
x
Q0* = !Q1.X
Estadoatual
X
Z
Q2
Q1
Q0
0
1
0
0
1
010
001
0
0
1
0
010
100
0
1
0
0
010
001
1
Q2*Q1*Q0*
48
Síntese de FSMs
Codificação de estados
Equações de próximo estado e de saídas
Z
Q0
Q2Q1
0
1
00
x
0
01
0
x
11
x
x
10
1
x
Z = Q2
Estadoatual
X
Z
Q2
Q1
Q0
0
1
0
0
1
010
001
0
0
1
0
010
100
0
1
0
0
010
001
1
Q2*Q1*Q0*
49
Síntese de FSMs
Codificação de estados
Equações do detector de borda positiva (one hot)
D2 = Q1.X
D1 = !X
D0 = !Q1.X
Z = Q2
Preset
Síntese de FSMs
Codificação de estados
Almost one hot
Variação da codificação one hot
Nessa codificação o estado inicial tem todos bits em ‘0’ (no hot)
Exemplo: codificação de 4 estados
000, 001, 010, 100
Tal variação faz muito sentido
É simples inicializar todos flip-flops em ‘0’ (reset) 
Síntese de FSMs
Codificação de estados
Como escolher a melhor codificação ?
Em geral, testando todas!
Uma codificação pode ser boa para um projeto mas ruim para outro
Experiência do projetista
Algumas recomendações
Escolher uma codificação de estado inicial fácil de ser gerada
Todos bits em ‘0’ ou todos em ‘1’
Minimizar a variação de bits entre transições de estado
Considerar a utilização de mais flip-flops do o número mínimo possivel (codificação trivial)