ORGANIZAÇÃO E ARQUITETURA DE
COMPUTADORES I
Máquina de Estados
Finito
prof. Dr. César Augusto M. Marcon
prof. Dr. Edson Ifarraguirre Moreno
2 / 13
MÁQUINA DE ESTADOS
A
• Elementos do Modelo
– Estado
– Transição
• Relógio
E0
E1
reset
– Reset
A
• Determinismo
– Modelo determinístico
– Modelo não determinístico
• Tipos de Máquina
– Mealy versus Moore
• Representação de Máquina de Estados Finito
– Um processo com um único sinal representando o estado
– Dois processos, um representando a operação combinacional e outro
representando o elemento de memorização para troca de estados
3 / 13
Máquina de Moore
Entrada
Circuito
Combinacional
Saída
Memória
(FFs)
Saída muda somente na transição do relógio
Circuito
Combinacional
4 / 13
MÁQUINA DE ESTADOS MOORE
entity Moore is
port
(
ck: in std_logic;
entrada: in std_logic;
saida: out std_logic
);
end Moore;
architecture M of Moore is
type STATE_TYPE is (S0, S1, S2, S3);
signal estado: STATE_TYPE;
begin
process(ck, reset)
begin
if reset = '1' then
estado <= S0;
elsif ck'event and ck = '1' then
<< Máquina de estados >>
end if;
end process;
end A_Moore;
5 / 13
MÁQUINA DE ESTADOS MOORE
case estado is
when S0 =>
saida <= '0';
if entrada = '1' then
estado <= S2;
end if;
when S1 =>
saida <= '1';
if entrada = '0' then
estado <= S0;
else
estado <= S2;
end if;
when S2 =>
saida <= '1';
if entrada = '1' then
estado <= S3;
end if;
when S3 =>
saida <= '0';
if entrada = '1' then
estado <= S1;
end if;
end case;
6 / 13
Máquina de Mealy
Saída muda em função da entrada e do estado corrente
Entrada
Circuito
Combinacional
Saída
Memória
(FFs)
Circuito
Combinacional
7 / 13
MÁQUINA DE ESTADOS MEALY
entity Mealy is
port
(
ck: in std_logic;
entrada: in std_logic;
saida: out std_logic
);
end Mealy;
architecture A_Mealy of Mealy is
type STATE_TYPE is (S0, S1, S2, S3);
signal estado: STATE_TYPE;
begin
<PROCESSO DE CONTROLE DE ESTADO>
<PROCESSO DE CONTROLE DE SAÍDA>
end A_Mealy;
8 / 13
MÁQUINA DE ESTADOS MEALY
Processo de controle de estado
process(ck, reset)
begin
if reset = '1' then
estado <= S0;
elsif ck'event and ck = '1' then
<< Máquina de estados >>
end if;
end process;
case estado is
when S0 =>
if entrada = '1' then
estado <= S2;
end if;
when S1 =>
if entrada = '0' then
estado <= S0;
else
estado <= S2;
end if;
when S2 =>
if entrada = '1' then
estado <= S3;
end if;
Processo de controle da saída
Saída <= '0' when entrada = '1' and
(estado = S0 or estado = S3) else
'1';
when S3 =>
if entrada = '1' then
estado <= S1;
end if;
end case;
9 / 13
MÁQUINA DE ESTADOS
–
Moore  saídas são calculadas dependendo apenas do ESTADO ATUAL
–
Mealy  saídas são calculadas à partir do ESTADO ATUAL e ENTRADAS
1) O tipo “state” está bem especificado ? Não precisa definir quem é S0,S1,S2,S3?
2) O que deve ser alterado no código anterior para transformar de Moore para Mealy?
10 / 13
Exercícios
1. Descreva em VHDL o sistema SAgua através de uma máquina de estados.
Deve ser representado o comportamento da água frente a mudança de
temperatura, sabendo que a água pode estar em um de três estados: sólido,
líquido ou gasoso (use uma biblioteca para representar o estado da água).
Considere que SAgua tem como entradas: (i) temp - uma porta de um bit,
que em 0 representa frio e em 1 representa calor; (ii) estInic – porta com o
estado da água codificado; (iii) ck - sinal de controle para efetuar as
transições em SAgua; e (iv) start - porta de controle que, em 1, indica que o
valor de estInic deve ser armazenado em SAgua – considere que start é
síncrono com ck. Como saídas SAgua tem: (i) tempExc – porta contendo os
valores 0 ou 1 para informa que o calor ou frio recebidos foram devolvidos
para o ambiente, respectivamente; e (ii) estado que é um sinal codificado
com o valor do estado da água.
11 / 13
Exercícios
•
Faça a descrição de uma máquina reconhecedora de padrões. Esta
máquina deve reconhecer os seguintes padrões:
A 0 X X 0 0 1 1
•
B 1 X 1 X X 0 1
Ao reconhecer um padrão válido, a saída reconheceu deve ir para 1,
enquanto não tiver uma nova entrada e o contador cont deve ser
incrementado. Este deve conter o número de vezes que um padrão foi
reconhecido desde a máquina ter sido inicializada com o sinal de reset em
1
A
A
B
S0
B
S1
S2
S3
reset
A
A
B
B
S7
S6
A
B
S5
A
B
S4
A
12 / 13
Exercícios
(POSCOMP 2008) INSTRUÇÃO: As questões 47 e 48 devem ser respondidas com base no circuito digital
mostrado na figura abaixo
(POSCOMP 2008 - 47) Analise as seguintes afirmativas
O circuito mostrado é um circuito sequencial.
O circuito mostrado é um circuito combinacional.
O circuito mostrado implementa uma máquina de Mealy de quatro estados.
O circuito mostrado implementa uma máquina de Moore de quatro estados.
A análise permite concluir que
a.
b.
c.
d.
e.
Somente as afirmativas I e II são verdadeiras.
Somente a afirmativa III é verdadeira.
Somente a afirmativa IV é verdadeira.
Somente a afirmativa I é verdadeira.
Somente a afirmativa II é verdadeira.
(POSCOMP 2008 - 48) Considerando o circuito digital mostrado, analise as seguintes afirmativas
I.
II.
III.
A função booleana implementada pelo circuito pode ser definida por: S = AB + CD + E
A função booleana implementada pelo circuito pode ser definida por: S = (A + B)(C +D) E
A função booleana implementada pelo circuito pode ser definida por: S = (ABC) + (DE)
A análise permite concluir que
a.
b.
c.
d.
e.
Todas as afirmativas são verdadeiras.
Nenhuma das afirmativas é verdadeira.
Somente a afirmativa I é verdadeira.
Somente a afirmativa II é verdadeira .
Somente a afirmativa III é verdadeira.
13 / 13
Resposta de Exercícios
(POSCOMP 2008) INSTRUÇÃO: As questões 47 e 48 devem ser respondidas com base no circuito digital
mostrado na figura abaixo
(POSCOMP 2008 - 47) Analise as seguintes afirmativas
I.
II.
III.
IV.
O circuito mostrado é um circuito sequencial.
O circuito mostrado é um circuito combinacional.
O circuito mostrado implementa uma máquina de Mealy de quatro estados.
O circuito mostrado implementa uma máquina de Moore de quatro estados.
A análise permite concluir que
a.
b.
c.
d.
e.
Somente as afirmativas I e II são verdadeiras.
Somente a afirmativa III é verdadeira.
Somente a afirmativa IV é verdadeira.
Somente a afirmativa I é verdadeira.
Somente a afirmativa II é verdadeira.
(POSCOMP 2008 - 48) Considerando o circuito digital mostrado, analise as seguintes afirmativas
I.
II.
III.
A função booleana implementada pelo circuito pode ser definida por: S = AB + CD + E
A função booleana implementada pelo circuito pode ser definida por: S = (A + B)(C +D) E
A função booleana implementada pelo circuito pode ser definida por: S = (ABC) + (DE)
A análise permite concluir que
a.
b.
c.
d.
e.
Todas as afirmativas são verdadeiras.
Nenhuma das afirmativas é verdadeira.
Somente a afirmativa I é verdadeira.
Somente a afirmativa II é verdadeira .
Somente a afirmativa III é verdadeira.