Introdução a Máquina de Estados

Prévia do material em texto

Universidade Federal do Rio Grande do Norte 
Instituto Metrópole Digital 
Departamento de Informática e Matemática Aplicada 
IMD0041 – Introdução a Organização e Arquitetura de Computares 
Máquina de Estados 
Monica Pereira/DIMAp 
Kayo Gonçalves e Silva/IMD 
IM
D
00
41
 
1 
Na Aula Anterior 
• Circuito Combinacional e Circuito 
Sequencial 
o ULA, multiplexador, codificar 
o Registrador e memória 
o Clock 
IM
D
00
41
 
2 
Roteiro 
• Exemplo Inicial 
• Conceito 
• Mais exemplos 
IM
D
00
41
 
3 
Exemplo 1 
•  Projete um componente que reconheça uma 
sequência de três bits no valor zero. 
•  Entrada: 1 bit 
•  Saída: 
o 1, se três bits seguidos forem 0 
o 0, caso contrário 
IM
D
00
41
 
4 
Componente 
IM
D
00
41
 
5 
Reconhecedor 
A Sequência 
Componente 
IM
D
00
41
 
6 
Reconhecedor 
A Sequência 
Que tipo de função lógica/aritmética temos que realizar? 
Exemplo de entradas 
IM
D
00
41
 
7 
1a 2a 3a 4a 5a 6a 
Como reconhecer a sequência? 
•  Operação: recebe a entrada e compara se é 0 ou 1 
•  O que fazer se for 0? 
•  O que fazer se for 1? 
IM
D
00
41
 
8 
Como reconhecer a sequência? 
IM
D
00
41
 
9 
Recebe a primeira entrada e compara se é 0 ou 1 
Recebe a segunda 
entrada e 
compara se é 0 ou 
1 
Recebe a terceira 
entrada e 
compara se é 0 ou 
1 
Como reconhecer a sequência? 
IM
D
00
41
 
10 
Recebe a primeira entrada e compara se é 0 ou 1 
Recebe a segunda 
entrada e 
compara se é 0 ou 
1 
Recebe a terceira 
entrada e 
compara se é 0 ou 
1 
Sequência = 1 
Entrada = 0 
Entrada = 0 
Entrada = 0 
Como reconhecer a sequência? 
IM
D
00
41
 
11 
Recebe a primeira entrada e compara se é 0 ou 1 
Recebe a segunda 
entrada e 
compara se é 0 ou 
1 
Recebe a terceira 
entrada e 
compara se é 0 ou 
1 
Sequência = 1 
Quantos 
comparadores 
são 
necessários? 
Entrada = 0 
Entrada = 0 
Entrada = 0 
Como reconhecer a sequência? 
IM
D
00
41
 
12 
Recebe a primeira entrada e compara se é 0 ou 1 
Recebe a segunda 
entrada e 
compara se é 0 ou 
1 
Recebe a terceira 
entrada e 
compara se é 0 ou 
1 
Sequência = 1 
Entrada = 0 
Entrada = 0 
Entrada = 0 
Se não for 0? 
IM
D
00
41
 
13 
Recebe a primeira entrada e compara se é 0 ou 1 
Recebe a segunda 
entrada e 
compara se é 0 ou 
1 
Recebe a terceira 
entrada e 
compara se é 0 ou 
1 
Sequência = 1 
Entrada = 0 
Entrada = 0 
Entrada = 0 
Entrada = 1 
Entrada = 1 
Entrada = 1 
Máquina de Estados Finitos 
•  FSM (Finite State Machine) 
•  Modelo matemático utilizado para 
representar programas ou circuitos lógicos 
•  Possui 
o Estado inicial 
o Outros estados 
o Entradas e Saídas 
o Atualização 
IM
D
00
41
 
14 
Máquina de Estados Finitos 
•  Representação através de diagrama de 
estados 
IM
D
00
41
 
15 
E=1 
E=0 E=1 
E=0 
E=0 
E=1 
Valor == 44 Valor < 44 
Máquina de Estados Finitos 
•  Representação através de diagrama de 
estados 
IM
D
00
41
 
16 
Estado inicial 
Estado 
Transição 
Rótulos usados nos arcos para indicar as regras de transição 
Máquina de Estados Finitos 
•  Onde é utilizada? 
o Algoritmos 
o Componentes lógicos 
o Dispositivos de controle 
o Teoria da computação: formalização de 
conceitos/autômatos 
IM
D
00
41
 
17 
FSM em Componentes Lógicos e 
Dispositivos de Controle 
•  O que fazer em cada estado? 
o  Ativar ou desativar os sinais que irão controlar cada um dos 
componentes 
•  Considerar o estado atual e projetar o que os 
componentes devem realizar 
•  Os sinais serão enviados para os dispositivos 
quando ocorrer mudançã de estado 
•  A mudança ocorre de acordo com as regras de 
transição 
IM
D
00
41
 
18 
Exemplo 1 - Reconhecedor 
IM
D
00
41
 
19 
E=1 
E=0 E=1 
E=0 
E=0 
E=1 
•  A mudança depende da 
próxima entrada 
•  Em cada estado é feita uma 
comparação 
•  Para mudar para o próximo 
estado, é necessário testar o 
resultado do comparador 
Exemplo 1 - Reconhecedor 
IM
D
00
41
 
20 
E=1 
E=0 E=1 
E=0 
E=0 
E=1 
estado_atual<- comp_1 
 
se estado_atual = comp_1 então 
 se saida_compara = 0 então 
 próximo_estado = comp_2 
 senão 
 próximo_estado = comp_1 
 fim_se 
 estado_atual = proximo_estado 
senão 
se estado_atual = comp_2 então 
 
comp2 
comp3 
fim 
comp1 
Máquina de estados da arquitetura 
IM
D
00
41
 
21 
Fonte: Máquina de Estados Algorítmica: Prof. Ricardo Jacobi (UnB) 
http://www.cic.unb.br/~rjacobi/ensino/ArqVLSI/mea.pdf 
Controle dos processadores 
22 
IM
D
00
41
 
Máquina de Estados do MIPS 
Fonte: Patterson e Hennessy – Organização e Arquitetura de Computadores, 3a Edição 
Exemplo 2 – Máquina de 
refrigerantes 
23 
IM
D
00
41
 
•  Seu trabalho como projetista: realizar o 
controle de entrada de moedas da máquina 
o Se entrar o valor correto: deve sair a latinha 
o Caso contrário: voltar para o etado inicial e 
devolver as moedas 
o Preço: R$ 1,00 
o Moedas aceitas: R$ 1,00, R$ 0,50, R$ 0,25 
o Só é permitido entrar com moedas iguais 
Desafio 
•  Máquina de estados da máquina de 
refrigerantes, se entrar com moedas diferentes. 
o Exemplo: 
² 0,25 + 0,50+ 0,25 
² 0,50 + 0,25 + 0,25 
24 
IM
D
00
41
 
Próxima aula 
• Formato de Instrução e Modo de 
endereçamento 
IM
D
00
41
 
25 
26 
IM
D
00
41
 
Bibliografia 
•  Para saber mais: 
•  https://fenix.tecnico.ulisboa.pt/downloadFile/3779571788876/
SS_Teorica_7_2007_8_sem_1.pdf 
•  Ronald J. Tocci, Neal S. Widmer e Gregoty L. Moss 
 Sistemas Digitais – princípios e aplicações 
 11ª ed. Pearson, 2011. 
 Capítulo 7 – Contadores e Registradores 
27 
IM
D
00
41