cap08_v3

Prévia do material em texto

1
IC-UNICAMP
MC602 – Mario Côrtes – IC / Unicamp
Capítulo 8
Máquinas de estado
FSM (Finite State Machines)
MC 602
Circuitos Lógicos e Organização de Computadores
IC/Unicamp
Prof Mario Côrtes
2
IC-UNICAMP
MC602 – Mario Côrtes – IC / Unicamp
Tópicos
• Sistematização do projeto de circuitos 
sequenciais síncronos 
• Máquinas de Moore
• Máquinas de Mealy
• Atribuição de estados
• Visão geral de máquinas síncronas
3
IC-UNICAMP
MC602 – Mario Côrtes – IC / Unicamp
Forma geral de um circuito síncrono
• Circuitos combinacionais: saídas dependem das 
entradas atuais
• Circuitos sequenciais : saídas dependem do 
conteúdo atual (estado) dos FFs e das entradas
– circuitos simples (FF, latch, registrador, contador): há pouca 
quantidade de portas lógicas além dos elementos de 
memória
– Circuito síncrono genérico com grande quantidade de portas 
lógicas interligando elementos de memória. Estado atual 
dos FFs e valor das entradas definem:
• próximo conteúdo (estado) dos FFs
• saídas atuais
4
IC-UNICAMP
MC602 – Mario Côrtes – IC / Unicamp
Problema
• Saída z igual a
– “1” se w=1 nos dois últimos ciclos de clock
– “0” caso contrário
• Todas mudanças sincronizadas com o clock
?
w z
Ck
Ciclo: t 0 t 1 t 2 t 3 t 4 t 5 t 6 t 7 t 8 t 9 t 10
w : 0 1 0 1 1 0 1 1 1 0 1 
z : 0 0 0 0 0 1 0 0 1 1 0 
5
IC-UNICAMP
MC602 – Mario Côrtes – IC / Unicamp
Problema (cont)
• Possível implementar como circuito 
combinacional?
• Possível implementar apenas com circuitos 
sequenciais básicos (FFs, latches, 
registradores, contadores)?
• Solução estruturada para circuitos 
sequenciais síncronos:
– Máquinas de Estados
– FSM: Finite State Machines
6
IC-UNICAMP
MC602 – Mario Côrtes – IC / Unicamp
Máquinas de Estado
• W: Entradas Z:Saídas
• Q: Estados internos (saídas de FFs)
• Y: Próximos estados dos FFs
• Circ comb 1: 
– calcula Y (entradas dos FFs) a partir de Q (estado atual = 
saídas dos FFs) e das entradas W
• Circ comb 2: 
– calcula z a partir de Q e (opcionalmente) W
FFs
Clock 
Q 
W 
Z 
Circuito 
Comb. 1
Clock 
Q 
W 
Z 
Circuito 
Comb. 2Y 
7
IC-UNICAMP
MC602 – Mario Côrtes – IC / Unicamp
Análise de uma máquina simples
• Dois FFs� quatro estados possíveis 
• Uma entrada w e uma saída z
D Q 
Q 
D Q 
Q 
Clock 
Resetn
y 2 
y 1 
Y 2 
Y 1 
w 
z 
8
IC-UNICAMP
MC602 – Mario Côrtes – IC / Unicamp
Tabela verdade dos combinacionais
Entradas Saídas
w y2y1 Y2Y1 z
0 00 00 0
0 01 00 0
0 10 00 0
0 11 00 1
1 00 01 0
1 01 10 0
1 10 11 0
1 11 11 1
y 2 
y 1 
z 
Y 2 
Y 1 
w 
y 1 
y 1 
y 2 
9
IC-UNICAMP
MC602 – Mario Côrtes – IC / Unicamp
Tabela verdade em forma alternativa
• novo formato:
– explicita transições de estado
Present 
Next State 
state w = 0 w = 1 
Output
y 2 y 1 Y 2 Y 1 Y 2 Y 1 
z 
0 0 0 0 01 0 
0 1 0 0 10 0 
1 0 0 0 11 0 
1 1 0 0 11 1 
Entradas Saídas
w y2y1 Y2Y1 z
0 00 00 0
0 01 00 0
0 10 00 0
0 11 00 1
1 00 01 0
1 01 10 0
1 10 11 0
1 11 11 1
10
IC-UNICAMP
MC602 – Mario Côrtes – IC / Unicamp
Atribuição simbólica de estados
Present 
Next State 
state w = 0 w = 1 
Output
y 2 y 1 Y 2 Y 1 Y 2 Y 1 
z 
0 0 0 0 01 0 
0 1 0 0 10 0 
1 0 0 0 11 0 
1 1 0 0 11 1 
Present Next state Output
state w = 0 w = 1 z 
A A B 0 
B A C 0 
C A D 0 
D A D 1 
11
IC-UNICAMP
MC602 – Mario Côrtes – IC / Unicamp
Diagrama de transição de estados
Present Next state Output
state w = 0 w = 1 z 
A A B 0 
B A C 0 
C A D 0 
D A D 1 A
B
C
D
W=0
W=0
W=0
W=0
W=1
W=1W=1
W=1
12
IC-UNICAMP
MC602 – Mario Côrtes – IC / Unicamp
Último passo: reset
A
B
C
D
W=0
W=0
W=0
W=0
W=1
W=1W=1
W=1
Resetn=0
13
IC-UNICAMP
MC602 – Mario Côrtes – IC / Unicamp
Análise de uma FSM: resumo
• Identificar os dois circuitos combinacionais
(re-arranjar desenho?)
– próximo estado
– saída
• Tabela verdade convencional
• Tabela verdade: forma alternativa
• Atribuição de estados: binário � simbólico
• Tabela de transição de estados
• Diagrama de transição de estados
14
IC-UNICAMP
MC602 – Mario Côrtes – IC / Unicamp
Exercício de análise de uma FSM simples
• Dois FFs� quatro estados possíveis 
• Uma entrada e duas saídas
D Q 
Q 
D Q 
Q 
s1
s2
y2
y1
w
z1
z2
15
IC-UNICAMP
MC602 – Mario Côrtes – IC / Unicamp
Máquinas de Moore e de Mealy
• Máquinas de Moore
– próximo conteúdo dos flip-flops (Y) depende das entradas 
(W) e do estado atual (Q)
– saída depende do estado atual (Q)
• Máquina de Mealy
– próximo conteúdo dos flip-flops (Y) depende das entradas 
(W) e do estado atual (Q)
– saída depende do estado atual (Q) e das entradas (W)
Combinational 
circuit 
Flip-flops
Clock 
Q 
W 
Z 
Combinational 
circuit 
Combinational 
circuit 
Flip-flops
Clock 
Q 
W 
Z 
Combinational 
circuit Y 
Moore: z muda 
sincronizado 
com o clock
16
IC-UNICAMP
MC602 – Mario Côrtes – IC / Unicamp
Síntese de uma FSM simples (Moore)
• O circuito tem uma entrada w e uma saída z
• Todas as mudanças ocorrem na borda de 
subida do clock
• z=1 se w=1 nos dois últimos ciclos de clock
• z=0 caso contrário
FSM
w z
Ck
Ciclo: t 0 t 1 t 2 t 3 t 4 t 5 t 6 t 7 t 8 t 9 t 10
w : 0 1 0 1 1 0 1 1 1 0 1 
z : 0 0 0 0 0 1 0 0 1 1 0 
17
IC-UNICAMP
MC602 – Mario Côrtes – IC / Unicamp
Definição dos estados
• Primeiro passo: quantos estados são 
necessários para representar o histórico?
• Não há método sistemático
• Imaginemos estado inicial (power-up ou 
reset) A com z = 0
– desde que w=0, FSM mantém-se em A
• Se w=1 por um clock� estado B
– significa histórico = um clock apenas com w=1
• Em B
– se w=1 � estado C e z =1
– se w=0 � volta para A
• Três estados são suficientes
18
IC-UNICAMP
MC602 – Mario Côrtes – IC / Unicamp
Diagrama de transição de estados
C z 1 = ⁄⁄⁄⁄
Reset 
B z 0 = ⁄⁄⁄⁄A z 0 = ⁄⁄⁄⁄w 0 = 
w 1 = 
w 1 = 
w 0 = 
w 0 = w 1 = 
Reset pode ser 
clear dos FFs
Ciclo: t 0 t 1 t 2 t 3 t 4 t 5 t 6 t 7 t 8 t 9 t 10
w : 0 1 0 1 1 0 1 1 1 0 1 
z : 0 0 0 0 0 1 0 0 1 1 0 
19
IC-UNICAMP
MC602 – Mario Côrtes – IC / Unicamp
Notação do diagrama
• Nesta modalidade: há uma saída determinada 
para cada estado (C/z=1)
• Transições de estado
– saindo de C: uma para cada combinação de entradas
– entrando em C: arbitrário (mas deve haver alguma, 
senão o estado nunca é alcançado)
C z 1 = ⁄⁄⁄⁄
w 1 = 
w 0 = 
w 1 = 
Estado C, saída =1
Uma transição para 
cada combinação de 
entradas
20
IC-UNICAMP
MC602 – Mario Côrtes – IC / Unicamp
Estado Próx estado saída
atual w = 0 w = 1 z 
A A B 0 
B A C 0 
C A C 1 
C z 1 = ⁄⁄⁄⁄
Reset 
B z 0 = ⁄⁄⁄⁄A z 0 = ⁄⁄⁄⁄w 0 = 
w 1 = 
w 1 = 
w 0 = 
w 0 = w 1 = 
Tabela de transição de estados
• Notar a ausência de Reset na tabela
– clear do FF
21
IC-UNICAMP
MC602 – Mario Côrtes – IC / Unicamp
Estrutura da FSM
• Há três estados � 2 bits são suficientes
• Variáveis de estado: 
– Estado atual y1 e y2
– Próximo estado Y1 e Y2
Combinacional
Circuito
Clock
y2
z
w y
1
Y1
Y2
Combinacional
Circuito
CC1: prox estado = 
f(entrada e estado atual)
CC2: saída = 
f(estado atual)
22
IC-UNICAMP
MC602 – Mario Côrtes – IC / Unicamp
Atribuição de Estado
Estado Próx estado saída
atual w = 0 w = 1 z 
A A B 0 
B A C 0 
C A C 1 
C z 1 = ⁄⁄⁄⁄
Reset 
B z 0 = ⁄⁄⁄⁄A z 0 = ⁄⁄⁄⁄w 0 = 
w 1 =w 1 = 
w 0 = 
w 0 = w 1 = 
Entrada
Estado 
atual
Próximo 
estado
Saída
w y2y1 Y2Y1 z
0 A=00 A=00 0
0 B=01 A=00 0
0 C=10 A=00 1
0 11 dd d
1 A=00 B=01 0
1 B=01 C=10 0
1 C=10 C=10 1
1 11 dd d
23
IC-UNICAMP
MC602 – Mario Côrtes – IC / Unicamp
Tabelas verdade de CC1 e CC2 
(assumindo FF-D)
CC1
Clock
y2
z
w y1Y1
Y2
CC2
w y2 y1 Y2 Y1
0 0 0 0 0
0 0 1 0 0
0 1 0 0 0
0 1 1 d d
1 0 0 0 1
1 0 1 1 0
1 1 0 1 0
1 1 1 d d
w y2 y1 z
0 0 0 0
0 0 1 0
0 1 0 1
0 1 1 d
1 0 0 0
1 0 1 0
1 1 0 1
1 1 1 d
24
IC-UNICAMP
MC602 – Mario Côrtes – IC / Unicamp
w 00 01 11 10
0 
1 
0 
1 0 
Y 1 wy 1 y 2 = 
w 
00 01 11 10
0 
1 
0 d 
1 d 
Y 2 wy 1 y 2 wy 1 y 2 + = 
d 
d 
0 
0 
0 
0 
0 
0 
1 
0 1 
0 
1 
0 
d 
y 1 
z y 1 y 2 
= 
0 
1 
y 2 
Y 1 wy 1 y 2 = 
Y 2 wy1 wy 2 + = 
z y 2 = 
w y 1 y 2 + 
( ) = 
Sem don't cares
Síntese de CC1 e CC2
y 2 y 1 
y 2 y 1 
Com don't cares
25
IC-UNICAMP
MC602 – Mario Côrtes – IC / Unicamp
Circuito final com FF tipo D
D Q 
Q 
D Q 
Q 
Y 2 
Y 1 
w 
Clock
z 
y 1 
y 2 
Resetn
26
IC-UNICAMP
MC602 – Mario Côrtes – IC / Unicamp
t 0 t 1 t 2 t 3 t 4 t 5 t 6 t 7 t 8 t 9 t 10
1 
0 
1 
0 
1 
0 
1 
0 
Clock 
w 
y 1 
y 2 
1 
0 
z 
Diagrama de tempo da FSM
Ciclo: t 0 t 1 t 2 t 3 t 4 t 5 t 6 t 7 t 8 t 9 t 10
w : 0 1 0 1 1 0 1 1 1 0 1 
z : 0 0 0 0 0 1 0 0 1 1 0 
Observar sinais síncronos com borda de subida do clock
27
IC-UNICAMP
MC602 – Mario Côrtes – IC / Unicamp
Simulação no Quartus
• Observar
– agrupamento de sinais das variáveis de estado 
(tipo enumerado)
– identificação pelo Quartus da máquina de estado 
e geração automática do diagrama de transição
28
IC-UNICAMP
MC602 – Mario Côrtes – IC / Unicamp
Resumo do procedimento
• Especificar o circuito
• Identificar o número de estados necessário e 
suas transições
• Desenhar o diagrama de transição de estados
• Fazer a tabela de transição de estados
• Fazer a atribuição de estados e completar a 
tabela
• (decidir o tipo de FF a ser usado e completar a 
tabela)
• Implementar os circuitos combinacionais CC1 e 
CC2
29
IC-UNICAMP
MC602 – Mario Côrtes – IC / Unicamp
Exemplo de projeto: Expl 8.1
• Implementação da unidade de controle da fig 7.55
• Tarefa: após pulso de start em w, trocar o conteúdo 
de R1 e R2, usando R3 como temporário. Ao final, 
ativar sinal “done” (?? possível trocar diretamente??)
R1
in
Bus 
Clock 
Control circuit 
Function
R1 R2 Rk
Data
Extern
R1
out
R2
in
R2
out
Rk
in
Rk
out
Control 
circuit 
w 
Clock 
Done
R 1 out 
R 2 out 
R 1 in
R 2 in
R 3 out 
R 3 in
30
IC-UNICAMP
MC602 – Mario Côrtes – IC / Unicamp
Diagrama de transição de estados
D R 3 out 1 = R 1 in 1 = Done 1 = , , ⁄
w 0 = 
w 1 = 
C R 1 out 1 = R 2 in 1 = , ⁄
B R 2 out 1 = R 3 in 1 = , ⁄
w 1 = 
A No⁄
w 0 = 
w 1 = 
transfer
w 0 = 
w 1 = 
Reset 
w 0 = 
31
IC-UNICAMP
MC602 – Mario Côrtes – IC / Unicamp
Tabelas de transição de estado
Present Next state Outputs 
state 
A A B 0 0 0 0 0 0 0 
B C C 0 0 1 0 0 1 0 
C D D 1 0 0 1 0 0 0 
D A A 0 1 0 0 1 0 1 
w = 0 w = 1 
Present Nextstate 
state Outputs 
A 00 00 0 1 0 0 0 0 0 0 0 
B 01 10 1 0 0 0 1 0 0 1 0 
C 10 11 1 1 1 0 0 1 0 0 0 
D 11 00 0 0 0 1 0 0 1 0 1 
32
IC-UNICAMP
MC602 – Mario Côrtes – IC / Unicamp
Mapas de Karnaugh
w 
00 01 11 10
0 
1 
1 
1 1 
y 2 y 1 
Y 1 wy 1 y 1 y 2 + = 
w 
00 01 11 10
0 
1 
1 1 
1 1 
y 2 y 1 
Y 2 y 1 y 2 y 1 y 2 + = 
33
IC-UNICAMP
MC602 – Mario Côrtes – IC / Unicamp
Circuito final
• (ver outra solução na fig. 7.57, com o uso de 
registrador de deslocamento
D Q 
Q 
D Q 
Q 
Done
w 
Clock
Y 2 
Y 1 
y 2 
y 1 
y 2 
y 1 
R 1 
in
R 3 
out 
R 1 
out 
R 2 
in
R 2 
out 
R 3 
in
34
IC-UNICAMP
MC602 – Mario Côrtes – IC / Unicamp
O problema da atribuição de estados
• Nos exemplos anteriores � codificação dos 
estados foi arbitrária
• É possível escolher atribuição visando 
minimizar o circuito final
– solução ótima é difícil
• Vejamos os dois últimos exemplos em outra 
codificação
35
IC-UNICAMP
MC602 – Mario Côrtes – IC / Unicamp
Exemplo: detector de seq de dois 1s
Estado Próx estado saída
atual w = 0 w = 1 z 
A A B 0 
B A C 0 
C A C 1 
C z 1 = ⁄⁄⁄⁄
Reset 
B z 0 = ⁄⁄⁄⁄A z 0 = ⁄⁄⁄⁄w 0 = 
w 1 = 
w 1 = 
w 0 = 
w 0 = w 1 = 
Present 
Next state 
state w = 0 w = 1 Output
y 2 y 1 Y 2 Y 1 Y 2 Y 1 
z 
A 00 00 01 0 
B 01 00 10 0 
C 10 00 10 1 
11 dd dd d 
atribuição original
Present Next state 
state w = 0 w = 1 Output
y 2 y 1 Y 2 Y 1 Y 2 Y 1 
z 
A 00 00 01 0 
B 01 00 11 0 
C 11 00 11 1 
10 dd dd d 
atribuição melhorada
36
IC-UNICAMP
MC602 – Mario Côrtes – IC / Unicamp
Síntese do novo circuito
• Possível escrever equações diretamente
• Y1 = w
• Y2 = w. y1
• z = y2
Present Next state 
state w = 0 w = 1 Output
y 2 y 1 Y 2 Y 1 Y 2 Y 1 
z 
A 00 00 01 0 
B 01 00 11 0 
C 11 00 11 1 
10 dd dd d 
atribuição melhorada
37
IC-UNICAMP
MC602 – Mario Côrtes – IC / Unicamp
Circuito final com atribuição melhorada
D Q 
Q 
D Q 
Q 
Y 2 
Y 1 
w 
Clock 
z 
y 1 
y 2 
Resetn
• Y1 = w
• Y2 = w. y1
• z = y2
circuito antigo
38
IC-UNICAMP
MC602 – Mario Côrtes – IC / Unicamp
Exemplo 8.1 antigo
Present Nextstate 
state Outputs 
A 00 00 0 1 0 0 0 0 0 0 0 
B 01 10 1 0 0 0 1 0 0 1 0 
C 10 11 1 1 1 0 0 1 0 0 0 
D 11 00 0 0 0 1 0 0 1 0 1 
w 
00 01 11 10
0 
1 
1 
1 1 
y 2 y 1 
Y 1 wy 1 y 1 y 2 + = 
w 
00 01 11 10
0 
1 
1 1 
1 1 
y 2 y 1 
Y 2 y 1 y 2 y 1 y 2 + = 
39
IC-UNICAMP
MC602 – Mario Côrtes – IC / Unicamp
Exemplo 8.1 com nova atribuição
Present Nextstate 
state Outputs 
A 00 0 0 01 0 0 0 0 0 0 0 
B 01 1 1 11 0 0 1 0 0 1 0 
C 11 1 0 10 1 0 0 1 0 0 0 
D 10 0 0 00 0 1 0 0 1 0 1 
w 00 01 11 10
0 
1 
1 
1 1 
y 2 y 1 
Y 1 wy2 y 1 y 2 + = 
w 
00 01 11 10
0 
1 
1 1 
1 1 
y 2 y 1 
Y 2 y 1 = 
40
IC-UNICAMP
MC602 – Mario Côrtes – IC / Unicamp
One-hot encoding
• É possível codificar os estados com n bits 
para n estados
– apenas um bit fica ligado (one-hot)
• Grande número de don´t care (combinações 
de estados não utilizados)
• Vantagem: circuito combinacional pode ficar 
mais simples
• Desvantagem: usa maior número de FFs
• Ver detalhes na seção 8.2.1 do livro texto
41
IC-UNICAMP
MC602 – Mario Côrtes – IC / Unicamp
Máquinas de Mealy
• Máquinas de Moore
– próximo conteúdo dos flip-flops (Y) depende das entradas (W) e do 
estado atual (Q)
– saída depende do estado atual (Q)
• Máquina de Mealy
– próximo conteúdo dos flip-flops (Y) depende das entradas 
(W) e do estado atual (Q)
– saída depende do estado atual (Q) e das entradas (W)
Combinational 
circuit 
Flip-flops
Clock 
Q 
W 
Z 
Combinational 
circuit 
Combinational 
circuit 
Flip-flops
Clock 
Q 
W 
Z 
Combinational 
circuit Y 
Mealy: z pode 
mudar a qquer
instante, indep. do 
clock
42
IC-UNICAMP
MC602 – Mario Côrtes – IC / Unicamp
Implementação Mealy
do mesmo exemplo
• Especificações alteradas:
– O circuito tem uma entrada w e uma saída z
– Todas as mudanças ocorrem na borda de subida 
do clock
– z=1 se w=1 nos dois últimos ciclos de clock no 
último clock e no clock atual– z=0 caso contrário
Clock cycle: t 0 t 1 t 2 t 3 t 4 t 5 t 6 t 7 t 8 t 9 t 10
w : 0 1 0 1 1 0 1 1 1 0 1 
z : 0 0 0 0 1 0 0 1 1 0 0 
43
IC-UNICAMP
MC602 – Mario Côrtes – IC / Unicamp
A 
w 0 = z 0 = ⁄⁄⁄⁄
w 1 = z 1 = ⁄⁄⁄⁄B w 0 = z 0 = ⁄⁄⁄⁄
Reset 
w 1 = z 0 = ⁄⁄⁄⁄
Diagrama de transição de estados
da Máquina de Mealy
Clock cycle: t 0 t 1 t 2 t 3 t 4 t 5 t 6 t 7 t 8 t 9 t 10
w : 0 1 0 1 1 0 1 1 1 0 1 
z : 0 0 0 0 1 0 0 1 1 0 0 
44
IC-UNICAMP
MC602 – Mario Côrtes – IC / Unicamp
Notação Moore e Mealy
Moore
• Saída definida pelo 
estado atual
• Arcos de transição de 
estados não mostram 
saídas
Mealy
• O estado atual pode ter 
várias saídas, em 
função de w
• Arcos de transição 
mostram w e z
C z 1 = ⁄⁄⁄⁄
w 1 = 
w 0 = 
w 1 = 
w 0 = z 0 = ⁄⁄⁄⁄
w 1 = z 1 = ⁄⁄⁄⁄
B 
w 1 = z 0 = ⁄⁄⁄⁄
45
IC-UNICAMP
MC602 – Mario Côrtes – IC / Unicamp
Tabela de transição de estados
A 
w 0 = z 0 = ⁄⁄⁄⁄
w 1 = z 1 = ⁄⁄⁄⁄B w 0 = z 0 = ⁄⁄⁄⁄
Reset 
w 1 = z 0 = ⁄⁄⁄⁄
Present Next state Output z 
state w = 0 w = 1 w = 0 w = 1 
A A B 0 0 
B A B 0 1 
46
IC-UNICAMP
MC602 – Mario Côrtes – IC / Unicamp
Tabela de transição de estados
A 
w 0 = z 0 = ⁄⁄⁄⁄
w 1 = z 1 = ⁄⁄⁄⁄B w 0 = z 0 = ⁄⁄⁄⁄
Reset 
w 1 = z 0 = ⁄⁄⁄⁄
Present Next state Outputz 
state w = 0 w = 1 w = 0 w = 1 
A A B 0 0 
B A B 0 1 
Present Next state Output
state w = 0 w = 1 w = 0 w = 1 
y Y Y z z 
A 0 0 1 0 0 
B 1 0 1 0 1 
47
IC-UNICAMP
MC602 – Mario Côrtes – IC / Unicamp
Circuito e seu comportamento
Clock 
Resetn
D Q 
Q 
w 
z 
y 
t 0 t 1 t 2 t 3 t 4 t 5 t 6 t 7 t 8 t 9 t 10
1 
0 
1 
0 
1 
0 
1 
0 
Clock 
y 
w 
z 
48
IC-UNICAMP
MC602 – Mario Côrtes – IC / Unicamp
Comportamento comparado
t 0 t 1 t 2 t 3 t 4 t 5 t 6 t 7 t 8 t 9 t 10
1 
0 
1 
0 
1 
0 
1 
0 
Clock 
y 
w 
z 
t 0 t 1 t 2 t 3 t 4 t 5 t 6 t 7 t 8 t 9 t 10
1 
0 
1 
0 
1 
0 
1 
0 
Clock 
w 
y 1 
y 2 
1 
0 
z 
Moore
Mealy
49
IC-UNICAMP
MC602 – Mario Côrtes – IC / Unicamp
Exemplo 8.4 (Mealy em expl 8.1)
• troca de conteúdo 
dos registradores R1 
e R2, usando R3 
como temporário
• diagrama de 
transição de estados
R3out 1= R1in 1= Done 1=, ,
w 0=
w 1=
R1out 1= R2in 1=,
w 1= R⁄ 2out 1= R3in 1=,
A
w 0=
w 1=
Reset
w 0=
B
C
50
IC-UNICAMP
MC602 – Mario Côrtes – IC / Unicamp
8.5 Exemplo: somador serial
• Projetar um somador serial
– operandos de n bits armazenados nos shifts A e B
– resultado ficará armazenado no shift A+B
– “Adder FSM” cuida da soma e do carry do bit 
anterior
– bits são apresentados ao “Adder FSM” do LSB 
para o MSB
Sum A B + = 
Shift register
Shift register
Adder 
FSM Shift register
B 
A 
a 
b 
s 
Clock 
51
IC-UNICAMP
MC602 – Mario Côrtes – IC / Unicamp
Projeto somador serial Mealy
Sum A B + = 
Shift register
Shift register
Adder 
FSM Shift register
B 
A 
a 
b 
s 
Clock 
G 
00 1 ⁄
11 1 ⁄
10 0 ⁄
01 0 ⁄
H 
10 1 ⁄
01 1 ⁄
00 0 ⁄
carry-in 0 = 
carry-in 1 = 
G:
H:
Reset 
11 0 ⁄
ab s ⁄( ) 
52
IC-UNICAMP
MC602 – Mario Côrtes – IC / Unicamp
Tabelas de transição 
de estados
Present Next state Output s
state ab =00 01 10 11 00 01 10 11
G G G G H 0 1 1 0 
H G H H H 1 0 0 1 
carry-in 0 = 
carry-in 1 = 
G:
H: G 
00 1 ⁄
11 1 ⁄
10 0 ⁄
01 0 ⁄
H 
10 1 ⁄
01 1 ⁄
00 0 ⁄
Reset 
11 0 ⁄
ab s ⁄( ) 
Present 
Next state Output
state ab =00 01 10 11 00 01 10 11
y Y s 
0 0 0 0 1 0 1 1 0 
1 0 1 1 1 1 0 0 1 
Estados 
genéricos
Estados 
atribuídos
53
IC-UNICAMP
MC602 – Mario Côrtes – IC / Unicamp
Circuito do Somador Serial Mealy
• Poderia ser projetado por inspeção (e 
tentativa e erro)
Full
adder
a
b
s
D Q
Q
carry-out
Clock
Reset
Y y
54
IC-UNICAMP
MC602 – Mario Côrtes – IC / Unicamp
Projeto somador serial Moore
carry-in 0 = 
carry-in 1 = 
G:
H:
G 
00 1 ⁄
11 1 ⁄
10 0 ⁄
01 0 ⁄
H 
10 1 ⁄
01 1 ⁄
00 0 ⁄
Reset 
11 0 ⁄
ab s ⁄( ) 
H 1 s 1 = ⁄
Reset 
H 0 s 0 = ⁄
01
1011
11
01
10
G 1 s 1 = ⁄
G 0 s 0 = ⁄
01
10 00
01
00
10
11
00
00
11
Mealy
Moore
55
IC-UNICAMP
MC602 – Mario Côrtes – IC / Unicamp
Tabelas de transição de estados
H 1 s 1 = ⁄
Reset 
H 0 s 0 = ⁄
01
10
11
11
01
10
G 1 s 1 = ⁄
G 0 s 0 = ⁄
01
10
00
01
00
10
11
00
00
11
Present Nextstate Output
state ab=00 01 10 11 s 
G 0 G 0 G 1 G 1 H 0 0 
G 1 G 0 G 1 G 1 H 0 1 
H 0 G 1 H 0 H 0 H 1 0 
H 1 G 1 H 0 H 0 H 1 1 
Present Nextstate 
state ab=00 01 10 11 Output
y 2 y 1 Y 2 Y 1 
s 
00 0 0 01 0 1 10 0 
01 0 0 01 0 1 10 1 
10 0 1 10 1 0 11 0 
11 0 1 10 1 0 11 1 
56
IC-UNICAMP
MC602 – Mario Côrtes – IC / Unicamp
Circuito do Somador Serial Moore
• Nos dois casos, apesar de mais complicada, a 
máquina Moore é mais robusta: 
– mudanças na entrada não afetam imediatamente a 
saída e só no próximo clock
Full
adder 
a 
b 
D Q 
Q 
Carry-out 
Clock 
Reset 
D Q 
Q 
s 
Y 2 
Y 1 Sum bit 
y 2 
y 1 
57
IC-UNICAMP
MC602 – Mario Côrtes – IC / Unicamp
Projeto de FSM com FF-D e FF-JK
• Visto até agora: 
FSM com FF-D
– yi+1 = Yi
• E se FF-JK?
• Derivar de Y 
(próximo estado) � J e K
CC1 FFD y 
W 
Z CC2 
Y 
CC1 FFJK y 
W 
Z CC2 
Y 
J 
K 
Estado atual � Próximo estado J K
0 � 0 0 d
0 � 1 1 d
1 � 1 d 0
1 � 0 d 1
58
IC-UNICAMP
MC602 – Mario Côrtes – IC / Unicamp
Exemplo: contador como FSM (JK)
• Contador síncrono mod 8: 0 1 2 3 4 5 6 7 0 ...
w 0=
w 1=
w 0=
w 1=
w 0=
w 1=
w 0=
w 1=
w 0=
w 1=
w 0=
w 1=
w 0=
w 1=
w 0=
w 1=
A/0 B/1 C/2 D/3
E/4F/5G/6H/7
59
IC-UNICAMP
MC602 – Mario Côrtes – IC / Unicamp
Tabelas de transição
de estados
w 0=
w 1=
w 0=
w 1=
w 0=
w 1=
w 0=
w 1=
w 0=
w 1=
w 0=
w 1=
w 0=
w 1=
w 0=
w 1=
A/0 B/1 C/2 D/3
E/4F/5G/6H/7
Present Next state Output
state w = 0 w = 1 
A A B 0 
B B C 1 
C C D 2 
D D E 3 
E E F 4 
F F G 5 
G G H 6 
H H A 7 
Present Next state 
state w = 0 w = 1 Count 
y 2 y 1 y 0 
Y 2 Y 1 Y 0 Y 2 Y 1 Y 0 
z 2 z 1 z 0 
A 000 000 001 000 
B 001 001 010 001 
C 010 010 011 010 
D 011 011 100 011 
E 100 100 101 100 
F 101 101 110 101 
G 110 110 111 110 
H 111 111 000 111 
60
IC-UNICAMP
MC602 – Mario Côrtes – IC / Unicamp
Derivação de 
J K do FF
Present Next state 
state w = 0 w = 1 Count 
y 2 y 1 y 0 
Y 2 Y 1 Y 0 Y 2 Y 1 Y 0 
z 2 z 1 z 0 
A 000 000 001 000 
B 001 001 010 001 
C 010 010 011 010 
D 011 011 100 011 
E 100 100 101 100 
F 101 101 110 101 
G 110 110 111 110 
H 111 111 000 111 
Present 
Flip-flop inputs
state w = 0 w = 1 
Count 
y 2 y 1 y 0 
Y 2 Y 1 Y 0 J 2 K 2 J 1 K 1 J 0 K 0 Y 2 Y 1 Y 0 J 2 K 2 J 1 K 1 J 0 K 0 
z 2 z 1 z 0 
A 000 000 0d 0d 0d 001 0d 0d 1d 000 
B 001 001 0d 0d d0 010 0d 1d d1 001 
C 010 010 0d d0 0d 011 0d d0 1d 010 
D 011 011 0d d0 d0 100 1d d1 d1 011 
E 100 100 d0 0d 0d 101 d0 0d 1d 100 
F 101 101 d0 0d d0 110 d0 1d d1 101 
G 110 110 d0 d0 0d 111 d0 d0 1d 110 
H 111 111 d0 d0 d0 000 d1 d1 d1 111 
Transição J K
0 � 0 0 d
0 � 1 1 d
1 � 1 d 0
1 � 0 d 1
61
IC-UNICAMP
MC602 – Mario Côrtes – IC / Unicamp
Mapas de Karnaugh para Js e Ks
00 01 11 10
00
01
0
d d
0
d
0
d
0
d
0 0
d
1
d
0
d11
10
y1y0
wy2
J2 wy0y1=
00 01 11 10
00
01d
0 0
d
0
d
0
d
0
d d
1
d
0
d
011
10
y1y0
wy2
K2 wy0y1=
00 01 11 10
00
01
0
0 0
d
d
d
d
0
1
0 1
d
d
d
d
011
10
y1y0
wy2
J1 wy0=
00 01 11 10
00
01
d
d d
0
0
0
0
d
d
d d
1
1
0
0
d11
10
y1y0
wy2
K1 wy0=
00 01 11 10
00
01
d
0 d
d
d
0
0
0
d
1 d
d
d
1
1
111
10
y1y0
wy2
J0 w=
00 01 11 10
00
01
0
d 0
0
0
d
d
d
1
d 1
1
1
d
d
d11
10
y1y0
wy2
K0 w=
62
IC-UNICAMP
MC602 – Mario Côrtes – IC / Unicamp
Circuito final com JKs
• Observar regularidade
• J=K= w y0 y1 ...yn-1
• Observar que é possível 
fatorar termo repetido:
Ji = Ki = Jn-1 . yn-1
• Essa é a forma 
conhecida com FF - T
Clock 
Resetn
w J Q 
Q K 
y 0 
y 1 
y 2 
J Q 
Q K 
J Q 
Q K 
63
IC-UNICAMP
MC602 – Mario Côrtes – IC / Unicamp
Contador com JK e termos fatorados
• Exatamente o 
contador com 
FFT
• Comparar com 
contador FFD
Clock 
Resetn
w y 0 
y 1 
y 2 
J Q 
Q K 
J Q 
Q K 
J Q 
Q K 
64
IC-UNICAMP
MC602 – Mario Côrtes – IC / Unicamp
Contador 
com FFD
• Em geral, 
implementação 
com FFD tem 
maior custo
D Q 
Q 
D Q 
Q 
Clock 
y 0 
w 
y 1 
y 2 
Y 0 
Y 1 
Y 2 
Resetn
D Q 
Q 
65
IC-UNICAMP
MC602 – Mario Côrtes – IC / Unicamp
ASM – Algorithmic State Machine
• Representação alternativa (e equivalente) ao 
diagrama de estados
– Semelhante ao fluxograma
– Elementos principais:
Sinais de saída 
ou ações 
(Moore)
Nome do 
estado
a) Caixa de estado 
Condição 
0 (Falso) 1 (Verdadeiro)
b) Decisão
Saídas condicionais 
ou ações (Mealy)
c) Saída condicional
66
IC-UNICAMP
MC602 – Mario Côrtes – IC / Unicamp
Exemplo 8.3: FSM e ASM
C z 1 = ⁄⁄⁄⁄
Reset 
B z 0 = ⁄⁄⁄⁄A z 0 = ⁄⁄⁄⁄w 0 = 
w 1 = 
w 1 = 
w 0 = 
w 0 = w 1 = 
w 
w 
w 
0 1 
0 
1 
0 
1 
A 
B 
C 
z =1
Reset 
z =0
z =0
67
IC-UNICAMP
MC602 – Mario Côrtes – IC / Unicamp
Visão geral de máquinas síncronas
• Em circuitos síncronos, frequência máxima do clock
limitada pelo maior atraso combinacional
• Tck ≥ tck�Q + tcc + tsu
• fck ≤ 1 / (tck�Q + tcc + tsu )
D Q 
Q 
D2 Q2
D Q 
Q 
D2 Q1
circuito 
combinacional
com atraso tcc
tck����Q tcc tsu
CK
tck-->Q tcc tsu