View
265
Download
5
Category
Preview:
DESCRIPTION
Aula sobre Máquinas de estados finitos
Citation preview
Mquina de Estados Parte 1
SEL 0414 - Sistemas Digitais
Prof. Dr. Marcelo Andrade da Costa Vieira
Aula 17
Bibliografia
l Tocci, R. J.; Widmer, N. S. Sistemas Digitais Princpios e Aplicaes. 8 Ed., Prentice Hall, 2003.
l T a u b , H . C i r c u i t o s D i g i t a i s e Microprocessadores. Mc.Graw-Hill, 1982.
l Nelson, V.P.; Nagle, H.T.; Carroll, B.D.; Irwin, J.D. Digital Logic Circuit Analysis & Design, Prentice Hall, 1995.
Combinacionais X Sequenciais
l Circuitos Combinacionais: o valor da sada no instante t depende apenas da combinao dos valores das entradas neste instante. Os estados anteriores no interessam.
l Circuitos Sequenciais: o valor da sada no
instante t no depende apenas dos valores das entradas neste instante, mas tambm da sequncia das entradas anteriores.
Combinacionais X Sequenciais
l Nem todos os projetos em sistemas digitais conseguem ser resolvidos utilizando circuitos combinacionais.
l Algumas vezes necessrio o conhecimento
de um ou mais estados anteriores e tambm da sequncia anterior para se calcular a sada do circuito.
l Exemplo: Contadores
Circuitos Combinacionais
l No h realimentao - no h memria; l Tabela verdade soma de produtos; l Mapa de Karnaugh.
Circuitos Combinacionais
l No h realimentao; l No h memria l Ex:
Decodificador Somador; Multiplexador; Portas lgicas.
Circuitos Sequenciais
l H realimentao; l Elemento de Memria*; l Dependem da histria das entradas
passadas.
*flip-flop
Circuitos Sequenciais
l Memrias; l Contadores; l Registradores.
Circuito Combinacional + Elemento de Memria
Estado
l Cada estgio atravs do qual o circuito sequencial avana;
l Em cada estado, o circuito armazena uma recordao de sua histria passada, para saber o que fazer a seguir;
l Nem toda informao anterior relevante Nem todo estado prec isa ser armazenado.
Composio de um Circuito Sequencial
l Bloco de memria armazenar informaes anteriores para definir o estado presente. Tem como entrada o prximo estado
l Bloco combinatrio definir qual o prximo estado e a sada externa. Tem como entradas o estado presente e as entradas externas.
Circuitos Sequenciais Circuito Combinatrio + Elemento de Memria
Prximo Estado
Estado Atual
Y0
Yn
Q0
Qn
Z0 ... Zn
X0 ... Xn
...
...
Modelos de Circuitos Sequenciais
Mquina de Moore
Mquina de Mealy X
l As entradas no interferem diretamente na sada, somente
nos estados futuros;
l As sadas dependem apenas do
Estado Atual
Prximo Estado
Estado Atual
Y0
Yn
Q0
Qn
Z0 ... Zn
X0 ... Xn
Modelos de Circuitos Sequenciais Mquina de Moore
Modelos de Circuitos Sequenciais
Prximo Estado
Estado Atual
Y0
Yn
Q0
Qn
Z0 ... Zn
X0 ... Xn
l As entradas interferem nos
estados futuros e tambm na sada;
l As sadas dependem da entrada e do
Estado Presente
Mquina de Mealy
Moore e Mealy l Mquinas de Moore:
As sadas so funo apenas do estado presente (no das entradas);
As entradas s interferem no prximo estado; As sadas variam sincronamente; Resposta mais lenta ou inexistente variaes na
entrada.
l Mquinas de Mealy: As sadas so funo do estado presente e das entradas
atuais; As entradas interferem no prximo estado e tambm na
sada; As sadas variam assincronamente com as entradas; Resposta mais rpida variaes na entrada.
Diagrama de Estados
O Diagrama de Estado ou Diagrama de Fluxo de Estado, um grafo no qual cada n representa um estado e cada arco representa uma transio de estados (fluxo);
A cada pulso de clock, o fluxo avana um estado;
Diagrama de Estados
O diagrama de estados tem formatos diferentes para cada um dos modelos:
Mquina de Moore Mquina de Mealy
Diagrama de Estados - Moore
Estado
Sada
Entrada
A Z1 Z0
X
00 01
1
l A sada depende exclusivamente do estado (Mquina de Moore);
l A entrada s interfere no prximo estado.
Diagrama de Estados - Mealy
Estado
Sada Entrada
A
Z1 Z0 X
00
1
l A sada depende do estado presente e da entrada (Mquina de Mealy);
l A entrada interfere no prximo estado e na sada.
01
Estado Atual
Sada Z1 Z0
Prximo Estado
A 0 0 B B 0 1 C C 1 0 D D 1 1 A
Tabela de Transio de Estados
A 00
B 01
D 11
C 10
l Mquina de Moore l Modelo simples no
tem entrada l Apenas 1 arco de fluxo
Exemplo 1: Contador Crescente Mdulo 4 Diagrama de Estados
X
X
X
X
Estado Atual
Sada Z1 Z0
Prximo Estado
A 0 0 B B 0 1 C C 1 0 D D 1 1 A
Tabela de Transio de Estados
A 11
B
D
C
l Mquina de Mealy l Modelo simples no
tem entrada l Apenas 1 arco de fluxo
Exemplo 1: Contador Crescente Mdulo 4 Diagrama de Estados
X
00 X
01 X
10 X
Moore ou Mealy?
l Em geral, a verso Mealy de um circuito sequencial ser mais econmica de componentes fsicos (hardware) do que a verso Moore;
l Como a sada depende da entrada, valores incorretos na entrada durante o ciclo de clock podem afetar a sada;
l Isso pode no ocorrer na verso Moore, pois alteraes na sada e no estado s ocorrem na transio do clock (melhor sincronismo)
Exemplo de Projeto de Circuito Sequencial
Exemplo l Observar uma fileira de 3 lmpadas; l As lmpadas s acendem uma de cada vez; l Se as lmpadas acenderem na sequncia 1
2 3, deve-se soar um alarme.
1 2 3
ALARME !
Exemplo l A sequncia deve ser analisada. l Se a condio 1-2-3 no for observada,
despreza-se at a lmpada 1 acender novamente;
l Exemplo: sequncia: 1 2 2 1 3 2 1 2
1 2 3
Exemplo l Quantas Entradas? l 00 nenhuma lmpada acende l 01 lmpada 1 acende l 10 lmpada 2 acende l 11 lmpada 3 acende
1 2 3
4 2 bits
Exemplo l Quantas Sadas? l 0 nenhum alarme toca l 1 alarme toca
1 2 3
2 1 bit
Diagrama de Estados
Mquina de Moore
Diagrama de Estados - Moore
A/0 B/0 C/0 D/1
00,10,11
01 10 11
00,01 00 00,01,10,11
11 01
10
Pulso de clock
Estado
Entradas
ALARME !
Exemplo de Projeto de Circuito Sequencial
Mquina de Moore
Atribuio de Estados
Formas de Representao
Estado Flip-Flop Q1Q0
A 0 0
B 0 1
C 1 0
D 1 1
Tabela de Atribuio de Estados
Sadas dos Flips-Flops (Q) = Estado Presente (y) = Sada (Z)
Diagrama de Estados
00/0 01/0 10/0 11/1
0,2,3
1 2 3
0,1 0 0,1,2,3
3 1
2
Atribuio das Entradas
Formas de Representao
Entrada X1X0
0 0 0
1 0 1
2 1 0
3 1 1
Tabela de Entradas
Diagrama de Estados Final
00/0 01/0 10/0 11/1
00,10,11
01 10 11
00,01 00 00,01,10,11
11 01
10
Sntese do Circuito Sequencial
A partir do diagrama de estados, escreve-se a Tabela de Transio de estados e a Tabela de Sada. A partir dessa Tabela, projeta-se o circuito sequencial escolhendo qual o tipo de FF que ser utilizado (RS, JK, D ou T) Circuito combinatrio: portas lgicas; Circuito de memria: Flip-Flops;
Sntese do circuito sequencial
Mquina de Moore
Circuito Sequencial - Lmpadas
2 entradas (X1,X0) 1 Sada (Z0) 2 Flip-Flops (Q1,Q0)
Tabela de Transio de Estados e de Sada
Estado Atual Q1 Q0
Entrada X1 X0
Prximo Estado Y1 Y0
Sada Z0
A 00 A 01 A 10 A 11 B 00 B 01 B 10 B 11 C 00 C 01 C 10 C 11 D 00 D 01 D 10 D 11
Estado Atual Q1 Q0
Entrada X1 X0
Prximo Estado Y1 Y0
Sada Z0
A 00 A A 01 B A 10 A A 11 A B 00 B B 01 B B 10 C B 11 A C 00 C C 01 B C 10 A C 11 D D 00 D D 01 D D 10 D D 11 D
Estado Atual Q1 Q0
Entrada X1 X0
Prximo Estado Y1 Y0
Sada Z0
A 00 A 0 A 01 B 0 A 10 A 0 A 11 A 0 B 00 B 0 B 01 B 0 B 10 C 0 B 11 A 0 C 00 C 0 C 01 B 0 C 10 A 0 C 11 D 0 D 00 D 1 D 01 D 1 D 10 D 1 D 11 D 1
Atribuio dos Estados
Estado Atual Q1 Q0
Entrada X1 X0
Prximo Estado Y1 Y0
Sada Z0
00 00 00 0 00 01 01 0 00 10 00 0 00 11 00 0 01 00 01 0 01 01 01 0 01 10 10 0 01 11 00 0 10 00 10 0 10 01 01 0 10 10 00 0 10 11 11 0 11 00 11 1 11 01 11 1 11 10 11 1 11 11 11 1
Escolha do Flip-Flop
J K Q
0 0 Q0 0 1 0 1 0 1 1 1 Q0
Transio Entradas Qn Qn+1 J K
0 0 0 X 0 1 1 X 1 0 X 1 1 1 X 0
Transio de estados para FF JK
D Q
0 0
Transio Qn Qn+1 D
0 0 0 0 1 1 1 0 0 1 1 1
Transio de estados para FF Tipo D
1 1
T Q
0 Q0
Transio Qn Qn+1 T
0 0 0 0 1 1 1 0 1 1 1 0
Transio de estados para FF Tipo T
1 Q0
Diviso da Tabela em:
1. Tabela de Transio de estados 2. Tabela de Sada
1. Tabela de Transio de estados
Estado Atual Q1 Q0
Entrada X1 X0
Prximo Estado Y1 Y0
Flip-Flop Tipo D D1 D0
00 00 00 00 01 01 00 10 00 00 11 00 01 00 01 01 01 01 01 10 10 01 11 00 10 00 10 10 01 01 10 10 00 10 11 11 11 00 11 11 01 11 11 10 11 11 11 11
Estado Atual Q1 Q0
Entrada X1 X0
Prximo Estado Y1 Y0
Flip-Flop Tipo D D1 D0
00 00 00 0 0 00 01 01 0 1 00 10 00 0 0 00 11 00 0 0 01 00 01 0 1 01 01 01 0 1 01 10 10 1 0 01 11 00 0 0 10 00 10 1 0 10 01 01 0 1 10 10 00 0 0 10 11 11 1 1 11 00 11 1 1 11 01 11 1 1 11 10 11 1 1 11 11 11 1 1
Mapas de Karnaugh
01
0 0 00
00 Q1Q0 X1X0
01
11
10
0 0
1 1
1 0
D1 = Q1Q0+X1X0Q1 +X1X0Q1+X1X0Q0
Flip-Flop D1
11 10
0 0 0 1
1 1
1 0
01
0 1 00
00 Q1Q0 X1X0
01
11
10
1 1
1 1
0 1
D0 = Q1Q0+X1X0 +X1X0Q1+X1X0Q0
Flip-Flop D0
11 10
0 0 0 0
1 1
1 0
2. Tabela de Sada
Mquina de Moore
A Sada nunca depende do prximo estado A S a d a n o depende da entrada (mquina de Moore) A Sada s depende do estado atual
Estado Atual Q1 Q0
Entrada X1 X0
Prximo Estado Y1 Y0
Sada Z0
00 00 00 0 00 01 01 0 00 10 00 0 00 11 00 0 01 00 01 0 01 01 01 0 01 10 10 0 01 11 00 0 10 00 10 0 10 01 01 0 10 10 00 0 10 11 11 0 11 00 11 1 11 01 11 1 11 10 11 1 11 11 11 1
Estado Atual Q1 Q0
Sada Z0
00 0 00 0 00 0 00 0 01 0 01 0 01 0 01 0 10 0 10 0 10 0 10 0 11 1 11 1 11 1 11 1
Tabela de Sada
Estado Atual Q1Q0
Sada Z0
00 0
01 0
10 0
11 1
1
0 0 0
0 Q1
Q0
1 0 1
Z0 = Q1Q0
Z0
Sada Z0
l Mquina de MOORE:
a sada depende exclusivamente do estado presente;
a entrada no
interfere na sada;
Circuito Sequencial: Mquina de Moore
D1 = Q1Q0+X1X0Q1 +X1X0Q1+X1X0Q0
D0 = Q1Q0+X1X0 +X1X0Q1+X1X0Q0
Z0 = Q1Q0
Circuito Sequencial:
Mquina de Moore
FIM
Recommended