10-Sistemas Digitais II - Poli -decomposição de state machine

Prévia do material em texto

1
1
© Andrade, Bruno, Midorikawa, Simplício e Spina 2.017 <Sínt. Circ. Seq.> PCS 3225 Sistemas Digitais II 1
PCS 3225
Sistemas Digitais II
Síntese de Circuitos Seqüenciais
7-8 – Decomposing State Machines
(Wakerly, 4ed, páginas 587-590)
Andrade, Marco Túlio Carvalho de
Professor Responsável
versão: Setembro de 2.017
© Andrade, Bruno, Midorikawa, Simplício e Spina 2.017 <Sínt. Circ. Seq.> PCS 3225 Sistemas Digitais II 2
Decomposing State Machines
� Do mesmo modo que subrotinas e/ou “proce-
dures” em uma Linguagem de Programação, 
FSMs com alto número de Estados são com-
plexas para projetar e depurar.
� FSMs com alto número de Estados são uma 
oportunidade para utilizar uma coleção de 
máquinas de menor porte.
� A Decomposição de Máquinas de Estados é 
uma técnica consolidada para, dada uma FSM 
monolítica realizar sua análise e determinar se 
pode ser realizada com FSMs menores.
2
2
© Andrade, Bruno, Midorikawa, Simplício e Spina 2.017 <Sínt. Circ. Seq.> PCS 3225 Sistemas Digitais II 3
Decomposing State Machines
� Decomposição de Máquinas de Estados não é 
uma técnica muito útil para projetistas que que-
rem evitar projetar FSMs com grande número 
de Estados na primeira etapa (logo de cara!!).
� O projetista com prática deve orientar seu pro-
cesso de criação para gerar uma FSM estrutu-
rada hierarquicamente, de maneira que os usos 
e funções das sub-FSMs sejam óbvios, tornan-
do desnecessário sequer escrever a Tabela de 
Transição de Estados da máquina monolítica.
© Andrade, Bruno, Midorikawa, Simplício e Spina 2.017 <Sínt. Circ. Seq.> PCS 3225 Sistemas Digitais II 4
Decomposing State Machines
� A técnica mais simples e mais usada de 
Decomposição é a ilustrada na Figura 7-62 
(página 587).
� Uma “main machine” fornece as entradas e 
saídas primárias e executa o algorítmo de 
controle de alto nível.
� As “submachines” executam as funções de 
mais baixo nível para o algorítmo de controle e 
podem manusear algumas das entradas e 
saídas primárias.
3
3
© Andrade, Bruno, Midorikawa, Simplício e Spina 2.017 <Sínt. Circ. Seq.> PCS 3225 Sistemas Digitais II 5
Decomposing State Machines
© Andrade, Bruno, Midorikawa, Simplício e Spina 2.017 <Sínt. Circ. Seq.> PCS 3225 Sistemas Digitais II 6
Decomposing State Machines
� Talvez a submachine mais utilizada em 
projetos seja um contador. É comum a main 
machine normalmente necessitar de algum 
sinal DONE depois de alguns pulsos de clock.
� Esta necessidade é acompanhada da inclusão 
de novas entradas e saídas na main machine
(START, DONE).
� “Guessing Game”, seção 7.7, página 580. O 
jogo é fácil de ganhar depois de alguns 
minutos de prática.
4
4
© Andrade, Bruno, Midorikawa, Simplício e Spina 2.017 <Sínt. Circ. Seq.> PCS 3225 Sistemas Digitais II 7
Decomposing State Machines
� The Guessing Game, seção 7.7, página 580.
– 4 entradas G1, G2, G3 e G4 ligadas a 4 botões;
– 4 saídas L1, L2, L3 e L4 ligadas a 4 LEDs, no 
padrão “1-out-of-4”;
– Cada ciclo de clock o padrão é deslocado uma 
posição com frequência do clock de 4 Hertz;
– Adivinhações são feitas apertando os botões, o 
que determina uma escolha Gi;
– Se no próximo pulso de clock (após o aperto do 
botão escolhido) Gi é igual ao LED aceso, houve 
acerto (o jogo pára, saída ERR mantém mesmo 
valor), caso contrário saída ERR é ativada.
© Andrade, Bruno, Midorikawa, Simplício e Spina 2.017 <Sínt. Circ. Seq.> PCS 3225 Sistemas Digitais II 8
Decomposing State Machines
Figura 7-59
Página 581
5
5
© Andrade, Bruno, Midorikawa, Simplício e Spina 2.017 <Sínt. Circ. Seq.> PCS 3225 Sistemas Digitais II 9
Decomposing State Machines
Figura 7-60
Página 581
© Andrade, Bruno, Midorikawa, Simplício e Spina 2.017 <Sínt. Circ. Seq.> PCS 3225 Sistemas Digitais II 10
Decomposing State Machines
� Guessing Game – Diagrama de Transição de 
Estados da Fig. 7-60 será alterado com a intro-
dução de um sinal de enable (EN – Fig. 7-64).
LFSR - Torna 
pseudo-aleatório
o tempo que
permanecerá
aceso cada LED!
6
6
© Andrade, Bruno, Midorikawa, Simplício e Spina 2.017 <Sínt. Circ. Seq.> PCS 3225 Sistemas Digitais II 11
Decomposing State Machines
� Para tornar o Guessing Game mais desafiador 
propõe-se que os LEDs permaneçam acesos 
por um período pseudo-aletório de tempo.
� Deste modo o usuário tem que realmente 
“adivinhar” se um dado LED permanecerá 
tempo suficiente aceso para que seu respectivo 
botão seja apertado.
� LFSR (Linear Feedback Shift Register) – Gera-
dor de sequência pseudo-aleatória – Será o 
responsável por introduzir aleatoriedade no 
tempo de acendimento e gerar o sinal EN. 
© Andrade, Bruno, Midorikawa, Simplício e Spina 2.017 <Sínt. Circ. Seq.> PCS 3225 Sistemas Digitais II 12
Decomposing State Machines
EN EN
EN=0 Fica no Estado Atual
EN=1
Muda de 
Estado
7
7
© Andrade, Bruno, Midorikawa, Simplício e Spina 2.017 <Sínt. Circ. Seq.> PCS 3225 Sistemas Digitais II 13
Decomposing State Machines
� LFSR – O bit menos significativo de um LSFR 
de n bits será usado como gerador do sinal de 
enable (EN). O tempo em que cada LED 
permanecerá aceso dependerá da sequência de 
contagem do LSFR.
� No melhor caso para o Usuário – O LSFR, na 
saída, conterá 10 ... 00. Neste caso o LED fica 
aceso por “n-1” pulsos de clock.
� Isto ocorre porque levará “n-1” pulsos de clock
para que o “1” solitário alcance o bit menos 
significativo do LSFR, fazendo EN=1.
© Andrade, Bruno, Midorikawa, Simplício e Spina 2.017 <Sínt. Circ. Seq.> PCS 3225 Sistemas Digitais II 14
Decomposing State Machines
� No pior caso para o Usuário – O LSFR, na 
saída, conterá 11 ... 11. Neste caso cada LED 
fica aceso por apenas um período de clock.
� Cada pulso sucessivo de clock ocasionará a 
mudança para o próximo Estado (pois EN=1) e 
cada LED, sucessivamente, acenderá por um 
período de clock, dando lugar ao próximo.
� Isto ocorrerá por “n” pulsos de clock consecu-
tivos até que um bit 0 retorne à posição menos 
significativa do LSFR fazendo EN=0.
8
8
© Andrade, Bruno, Midorikawa, Simplício e Spina 2.017 <Sínt. Circ. Seq.> PCS 3225 Sistemas Digitais II 15
Referencias
�Referências desta aula: 
�Wakerly, 7-8 – Decomposing State 
Machines (4ed, páginas 587-590)
© Andrade, Bruno, Midorikawa, Simplício e Spina 2.017 <Sínt. Circ. Seq.> PCS 3225 Sistemas Digitais II 16
Livro Texto
�Wakerly, J.F.; Digital Design –
Principles & Practices; Fourth
Edition, ISBN: 0-13-186389-4, 
Pearson & Prentice-Hall, Upper
Saddle, River, New Jersey, 07458, 
2006.
9
9
© Andrade, Bruno, Midorikawa, Simplício e Spina 2.017 <Sínt. Circ. Seq.> PCS 3225 Sistemas Digitais II 17
Bibliografia Adicional Deste Assunto
� Dias, Francisco José de Oliveira; Introdução 
aos Circuitos de Chaveamento; Apostila, 
PEL/EPUSP, 1.980;
� Fregni, Edson; Ranzini, Edith; Teoria da 
Comutação: Introdução aos Circuitos 
Digitais (Partes 1 e 2); Apostila 
PCS/EPUSP, Outubro de 1.999;
© Andrade, Bruno, Midorikawa, Simplício e Spina 2.017 <Sínt. Circ. Seq.> PCS 3225 Sistemas Digitais II 18
Bibliografia Adicional Deste Assunto
� Hill, Frederic and Peterson, Gerald; 
Introduction to Switching Theory and Logical 
Design; Ed. John Wiley and Sons, 1.974;
� Ranzini, Edith; Circuitos de Chaveamento
(notas de aula); Apostila, EPUSP, 1.983.