Máquinas de Estado
Eletrônica Digital
Introdução
 Máquinas de Estados são usadas para representar o funcionamento
de circuitos sequenciais.
 um circuito sequencial consiste de um circuito combinacional e uma
rede de memória formada por elementos de armazenamento
(usualmente flip-flops).
 a rede de memória define o estado atual da máquina de estados.
 o circuito sequencial difere de um circuito combinacional puro na
medida em que o próximo estado será definido não só a partir das
entradas atuais, como também do estado atual, aumentando
enormemente as possibilidades de projeto.
Tipos de Implementações
 Máquinas de Estados podem ser dos tipos seguintes:
Máquina de Moore:
a saída muda apenas
na
transição
do
relógio
Máquina de Mealy:
a saída pode mudar
a qualquer instante
em
função
da
entrada
Tipos de Implementações
 O comportamento das máquinas de Moore e Mealy é idêntico,
mas suas implementações diferem, como mostrado a seguir.
Máquina de Moore: somente os sinais de
entrada causadores da transição de um
estado para outro são representados nos
arcos do grado
Máquina de Mealy: nos arcos do grafo
são representados os sinais de entrada
causadores da transição de um estado
para outro, com os respectivos valores
para a saída
Etapas de Projeto de Circuitos Sequenciais
1º passo: elaborar diagrama de estados que interprete
fielmente o problema que se deseja resolver;
2º passo: opcionalmente pode-se minimizar o número de
estados no diagrama de estados;
3º passo: escrever a tabela de estados, com os estados atuais,
próximos estados e saídas;
4º passo: atribuir a cada estado uma combinação de variáveis
de estado (flip-flops);
5º passo: construir a tabela de excitação do tipo de flip-flop
utilizado;
Etapas de Projeto de Circuitos Sequenciais
6º passo: montar o mapa de Karnaugh para cada uma das
entradas dos flip-flops do circuito, com o auxílio da tabela de
excitação;
7º passo: obter a equação final de cada entrada para cada um
dos flip-flops do circuito a partir da simplificação do mapa de
Karnaugh;
8º passo: fazer o mesmo procedimento para as equações das
variáveis de saída;
9º passo: finalmente, elaboração do diagrama lógico do
circuito, lembrando que todos os elementos de memória
(flipflops) recebem o mesmo sinal de relógio.
Detector de Começo de Mensagem
O começo de uma mensagem em um sistema de comunicação é
indicado pela ocorrência de três ‘1’ consecutivos em uma linha x.
Projete um circuito que forneça em sua saída o valor ‘1’ apenas
durante o período de relógio coincidente com o terceiro ‘1’
consecutivo na linha x.
Supor que um mecanismo
externo
inicializa
o
detector no estado de
“reset” após o término da
mensagem.
Detector de Começo de Mensagem
1º passo: elaborar diagrama de estados que interprete fielmente o problema
que se deseja resolver
Identificação dos Estados:
1) Não recebeu nenhum 1, q0;
2) Recebeu o primeiro 1, q1;
3) Recebeu o segundo 1, q2;
4) Recebeu o terceiro 1, q3;
5) Recebeu 0 após receber 1 ou 2 uns, q4.
Detector de Começo de Mensagem
Construção de Diagrama de Estados usando
Máquina de Mealy
Detector de Começo de Mensagem
3º passo: escrever a tabela de estados, com os estados atuais,
próximos estados e saídas
Detector de Começo de Mensagem
4º passo: atribuir a cada estado uma combinação de variáveis
de estado (flip-flops)
Detector de Começo de Mensagem
4º passo: atribuir a cada estado uma combinação de variáveis
de estado (flip-flops)
Detector de Começo de Mensagem
5º passo: construir a tabela de excitação do tipo de flip-flop
utilizado
xt
qt (y1y0)t
q0 00
q1 11
q2 01
q3 10
0
00
00
00
10
1
11
01
10
10
J1
0
X
0
X
0
K1 J0
X 0
1 X
X X
0 0
K0
X
1
1
X
J1
1
X
1
X
1
K1 J0
X 1
1 X
X X
0 0
K0
X
0
1
X
Detector de Começo de Mensagem
6º passo: montar o mapa de Karnaugh para cada uma das entradas dos flipflops do circuito, com o auxílio da tabela de excitação
7º passo: obter a equação final de cada entrada para cada um dos flip-flops
do circuito a partir da simplificação do mapa de Karnaugh
xt
qt (y1y0)t
q0 00
q1 11
q2 01
q3 10
0
00
00
00
10
1
11
01
10
10
J1
0
X
0
X
0
K1 J0
X 0
1 X
X X
0 0
K0
X
1
1
X
J1
1
X
1
X
1
K1 J0
X 1
1 X
X X
0 0
K0
X
0
1
X
Detector de Começo de Mensagem
6º passo: montar o mapa de Karnaugh para cada uma das entradas dos flipflops do circuito, com o auxílio da tabela de excitação
7º passo: obter a equação final de cada entrada para cada um dos flip-flops
do circuito a partir da simplificação do mapa de Karnaugh
xt
qt (y1y0)t
q0 00
q1 11
q2 01
q3 10
0
00
00
00
10
1
11
01
10
10
J1
0
X
0
X
0
K1 J0
X 0
1 X
X X
0 0
K0
X
1
1
X
J1
1
X
1
X
1
K1 J0
X 1
1 X
X X
0 0
K0
X
0
1
X
Detector de Começo de Mensagem
8º passo: fazer o mesmo procedimento para as equações das variáveis de
saída
Detector de Começo de Mensagem
9º passo: finalmente, elaboração do diagrama lógico do circuito, lembrando
que todos os elementos de memória (flip-flops) recebem o mesmo sinal de
relógio
J y1  x
K y1  y 0
J y 0  xy1
K y 0  x  y1
Z  xy1 y0
Considerações Importantes
Detector de Paridade
 Obter o diagrama de estados de um circuito que detecte a paridade
de um sinal serial. Considere paridade ímpar e máquina de Moore.
Identificação dos Estados
•
•
Máquina de Moore
Número de 1s acumulados é par, q0;
Número de 1s acumulados é ímpar, q1.
1
0
0
S0/0
1
S1/1
Detector de Paridade
 Prossiga com o projeto!
1
0
0
S0/0
1
S1/1
Divisível por 3
 Obter o diagrama de estados de um circuito que indique se o número
de 1s recebidos é divisível por 3 (considerar zero divisível por 3).
Máquina de Moore
Exemplo:
1
0
0
S0/1
S1/0
0
1
1
S2/0
Identificação dos Estados
1) Divisível por 3, S0;
2) Divisível por 3 + 1, S1;
3) Divisível por 3 + 2, S2.
Máquina de Mealy
1/0
0/0
0/1
S0
1/1
0/0
S1
1/0
S2
Detector de Paridade
 Prossiga com o projeto considerando primeiramente a Máquina de
Moore e depois a Máquina de Mealy.
Máquina de Moore
1
0
0
S0/1
0
S1/0
Máquina de Mealy
1
1
1/0
S2/0
0/0
0/1
S0
1/1
0/0
S1
1/0
S2
Indicação de Números de Zeros
 Obter o diagrama de estados de um circuito que indique se o
número de zeros recebidos é par, maior que zero, e desde que
NUNCA ocorram dois 1s consecutivos.
Identificação dos Estados
1) Não recebeu nada, S0;
2) Em S0, recebeu 1, S1;
3) Em S0, recebeu 0 (ímpar), S2;
 Prossiga com o projeto!
4) Em S2, recebeu 0 (par), S3;
5) Em S3, recebeu 1, S4;
6) Em S3, recebeu 0 (ímpar), S2;
7) Em S2, recebeu 1, S5;
8) Em S1, recebeu 0 (ímpar), S2;
9) Em S1, recebeu 1, S6;
10) Em S4, recebeu 0 (ímpar), S2;
11) Em S4, recebeu 1 (dois 1s consecutivos), S6;
12) Em S5, recebeu 0 (ímpar), S2;
13) Em S5, recebeu 1 (dois 1s consecutivos), S6;
14) Em S6, recebeu X, S6.
Detector de Sequência 0010
 Obter o diagrama de estados de um circuito que detecte todas as
sequências 0010. Se ocorrer mais do que dois zeros consecutivos a
máquina deve ser reiniciada após a ocorrência de um 1.
Exemplo:
Faça o projeto!