Dan NICULA
ELECTRONIC
˘
A DIGITAL
˘
A
Carte de ˆınat¸˘atur˘a 2.0
Editura Universit˘at¸ii TRANSILVANIA din Bra¸sov
ISBN 978-606-19-0563-8
2015
Lect¸ia 14
Automate sincrone
14.1 Not¸iuni teoretice
Automatele sunt circuite logice secvent¸iale care prezina ˆın structura lor:
- circuit logic combinat¸ional pentru determinarea st˘arii viitoare (pe baza intr˘arilor ¸si a st˘arii prezente);
- registru de stare pentru memorarea st˘arii curente;
- circuit logic combinat¸ional pentru determinarea valorilor ie¸sirilor (pe baza intr˘arilor ¸si a st˘arii prezente).
Dup˘a dependent¸a ie¸sirilor de intr˘ari, automatele se clasific˘a ˆın:
- automatele de tip Moore, ie¸sirea este dependena exclusiv de starea prezent˘a;
- automatele de tip Mealy , ie¸sirea este dependent˘a atˆat de starea prezent˘a at ¸si de intr˘ari.
Dup˘a ˆınarzierea ie¸sirilor fat¸˘a de intr˘ari, automatele se clasific˘a ˆın:
- automatele imediate, ie¸sirea este generat˘a dintr-un circuit combinat¸ional;
- automatele cu ˆıntˆarziere, ie¸sirea este generat˘a de un circuit combinat¸ional urmat de un registru.
Structurile celor 4 tipuri de automate sunt prezentate ˆın figurile 14.1 ¸si 14.2.
Moore Mealy
Figura 14.1 Structuri de automate imediate.
Comportamentul automatelor poate descris ˆın mai multe forme de reprezentare:
182 LECT¸ IA 14. Automate sincrone
Moore Mealy
Figura 14.2 Structuri de automate cu ˆınarziere.
Tabelul de tranzit¸ii
include informat¸ii complete despre comportamentul automatului ˆıntr-o form˘a sor de
utilizat pentru implementare. Tabelul cont¸ine urm˘atoarele sect¸iuni:
Intr˘ari, ate o coloan˘a pentru fiecare intrare. Valorile logice ale intr˘arilor pot 0 ¸si 1 sau pot considerate
indiferente pentru tranzit¸ia din anumit˘a stare (caz ˆın care valoarea se marcheaz˘a cu X, indiferent (Engl.
”don’t care”).
Stare prezent˘a, pe o coloan˘a denumirea generic˘a a st˘arii curente ¸si pe alte coloane (cˆate una pentru fiecare
bit de cod) codul st˘arii prezente.
Stare viitoare, pe o coloan˘a denumirea generic˘a a st˘arii viitoare ¸si pe alte coloane (cˆate una pentru fiecare
bit de cod) codul st˘arii viitoare.
Ie¸siri, ate o coloan˘a pentru fiecare ie¸sire. Valorile logice ale ie¸sirilor pot dependente doar de stare (ie¸siri
Moore, apar identic pe toate liniile asociate unei st˘ari) sau dependente ¸si de intr˘ari (ie¸siri Mealy, au valori
diferite pe diferite linii asociate unei st˘ari).
Tabelul de tranzit¸ii reprezina o form˘a util˘a de centralizare a datelor ˆın cazul implement˘arii automatului sub o
form˘a ce necesit˘a minimizarea funct¸iilor de transfer ale st˘arii sau ale ie¸sirilor.
ˆ
In cazul implemenarii registrului de stare cu bistabile de alt tip decˆat D (T, JK), tabelul de tranzit¸ii se com-
pleteaz˘a cu coloane pentru stimulii de intrare ai bistabilelor, dedu¸si pe baza st˘arii prezente, st˘arii viitoare ¸si a
tipului de bistabil.
Organigrama este o form˘a de reprezentare grafic˘a a comportamentului unui automat, ˆıntr-o manier˘a algorit-
mic˘a. Organigrama cont¸ine 3 tipuri de simboluri, prezentate ˆın figura 14.3.
Simbolul de stare este un dreptunghi care cont¸ine ˆın interior numele ie¸sirilor active ˆın acea stare, iar pe
exterior numele simbolic al st˘arii ¸si codul binar al acesteia. Simbolul de stare are o singur˘a intrare care
poate veni de la oricare din cele 3 simboluri ¸si o singur˘a ie¸sire care poate conduce fie la un simbol de stare
(tranzit¸ie necondit¸ionat˘a, fie la un simbol de decizie).
Simbol de decizie este un romb care cont¸ine ˆın interior o condit¸ie a intr˘arilor, iar ˆın exterior valorile cu care
se poate evalua condit¸ia, 0 ¸si 1. Simbolul de decizie are o singur˘a intrare care poate veni de la oricare din
cele 3 simboluri ¸si dou˘a ie¸siri care pot conduce la oricare dintre cele 3 simboluri.
Simbol de ie¸sire imediat˘a este un oval care cont¸ine ˆın interior numele ie¸sirilor activate ˆın cazul ˆındeplinirii
condit¸iei din simbolul de decizie precedent. Simbolul de ie¸sire imediat˘a are o singur˘a intrare care p oate
14.2. Pentru cei ce vor doar a promoveze examenul 183
a) b) c)
Figura 14.3 Simboluri utilizate ˆın organigrame: a) simbol de stare, b) simbol de decizie, c) simbol de ie¸sire imediat˘a.
veni doar de la o ie¸sire a unui simb ol de decizie ¸si o ie¸sire care poate conduce la oricare din cele 3 simboluri.
Simbolul de ie¸sire imediat˘a apare doar ˆın automate Mealy, la care ie¸sirea depinde direct ¸si de intr˘ari (nu
numai de stare).
Graful de tranzit¸ii este o form˘a de reprezentare grafic˘a a comportamentului unui automat, ˆıntr-o manier˘a
algoritmic˘a, utilizˆand noduri ¸si arce. Nodurile sunt asociate st˘arilor, iar arcele modeleaz˘a tranzit¸iile ˆıntre st˘ari.
ˆ
In noduri se marcheaz˘a codul st˘arii. Pe arce se marcheaz˘a condit¸iile intr˘arilor. Arcul porne¸ste din nodul asociat
st˘arii prezente ¸si ajunge ˆın nodul asociat st˘arii viitoare.
Figura 14.4 prezina modul de marcare a informat¸iei p e noduri ¸si arce ˆın cazul celor dou˘a tipuri de automate,
Mealy ¸si Moore.
Moore Mealy
Figura 14.4 Noduri ¸si arce utilizate pentru grafurile de tranzit¸ii.
Automatul Moore are ˆın noduri marcate ¸si ie¸sirile activate ˆın starea asociat˘a nodului. Pe arce sunt ˆınscrise
condit¸iile intr˘arilor.
Automatul Mealy are pe arce marcate ¸si ie¸sirile activate dac˘a este ˆındeplint˘a condit¸ia asociat˘a arcului.
14.2 Pentru cei ce vor doar a promoveze examenul
1. Determinat¸i graful de tranzit¸ii al unui automat care semnaleaz˘a pe ie¸sire existent¸a pe intrare a 3 sau mai mult¸i
bit¸i secvent¸iali ¸si consecutivi egali cu 1.
2. Determinat¸i graful de tranzit¸ii al unui automat care semnaleaz˘a pe ie¸sire valoarea majoritar˘a a valorilor primite
pe intrare ˆın ultimele 3 perioade de ceas. Determinat¸i secvent¸a de ie¸sire ˆın cazul aplic˘arii la intrare a secvent¸ei
00111110001100101010100111.
3. Determinat¸i graful de tranzit¸ii al unui automat care semnaleaz˘a pe ie¸sire detectarea unui ¸sir de bit¸i aplicat¸i
secvent¸ial pe intrare cu valorile 101. Pattern-ul semnalat se poate suprapune peste o instant¸˘a anterioar˘a, a¸sa
cum se prezint˘a ˆın exemplul din figura 14.5.
184 LECT¸ IA 14. Automate sincrone
Figura 14.5 Exemplu de semnale de intrare ¸si ie¸sire pentru automatul de detectare a unui pattern serial (problema 3).
14.3 Pentru cei ce vor a ˆınvet¸e
1. Un automat sincron implementat cu bistabile D este caracterizat de ecuat¸iile:
D
A
= Q
A
· Q
B
+ X
D
B
= Q
A
+ Q
B
Z = Q
A
· Q
B
· X
Realizat¸i tabelul de stare care descrie automatul. Realizat¸i diagramele de stare ˆın cazurile X = 0 ¸si X = 1.
2. Un semiautomat sincron implementat cu bistabile D este caracterizat de ecuat¸iile:
D
A
= Q
A
Q
B
X
D
B
= Q
A
D
C
= Q
B
Realizat¸i tabelul de stare care descrie automatul. Realizat¸i diagramele de stare ˆın cazul X = 0 ¸si X = 1.
Solut¸ie
Tabelul de stare prezint˘a coloanele intr˘arii X, ale bit¸ilor st˘ariilor curente Q
C
, Q
B
, Q
A
¸si ale bit¸ilor st˘ariilor
viitoare D
C
, D
B
, D
A
. Se completeaz˘a coloanele st˘arilor curente ¸si intr˘arilor cu toate cele 2
4
= 16 combinat¸ii.
Coloanele st˘arilor viitoare se determin˘a pe baza ecuat¸iilor D
C
, D
B
, D
A
. Rezult˘a tabelul:
X Q
C
Q
B
Q
A
D
C
D
B
D
A
0 0 0 0 0 0 0
1 0 0 0 0 0 1
0 0 0 1 0 1 1
1 0 0 1 0 1 0
0 0 1 0 1 0 1
1 0 1 0 1 0 0
0 0 1 1 1 1 0
1 0 1 1 1 1 1
0 1 0 0 0 0 0
1 1 0 0 0 0 1
0 1 0 1 0 1 1
1 1 0 1 0 1 0
0 1 1 0 1 0 1
1 1 1 0 1 0 0
0 1 1 1 1 1 0
1 1 1 1 1 1 1
Particularizˆand intrarea X, tabelele de stare devin:
X = 0 X = 1
Q
C
Q
B
Q
A
D
C
D
B
D
A
Q
C
Q
B
Q
A
D
C
D
B
D
A
0 0 0 0 0 0 0 0 0 0 0 1
0 0 1 0 1 1 0 0 1 0 1 0
0 1 0 1 0 1 0 1 0 1 0 0
0 1 1 1 1 0 0 1 1 1 1 1
1 0 0 0 0 0 1 0 0 0 0 1
1 0 1 0 1 1 1 0 1 0 1 0
1 1 0 1 0 1 1 1 0 1 0 0
1 1 1 1 1 0 1 1 1 1 1 1
14.3. Pentru cei ce vor a ˆınvet¸e 185
3. Un automat sincron semnaleaz˘a aparit¸ia secvent¸ial pe intrare a succesiunii ”1101”. a se descrie funct¸ionarea
automatului:
a) ca automat Moore;
b) ca automat Mealy.
ˆ
In fiecare caz, a se realizeze graful de tranzit¸ii, organigrama, tabelul de tranzit¸ii ¸si forme de und˘a relevante.
Solut¸ie
Automatul are o intrare (denumit˘a X) ¸si o ie¸sire (denumit˘a Z). Automatul Moore are ie¸sirea dependent˘a de
stare. Deci, dup˘a depistarea aparit¸iei succesiunii cerute, se intr˘a ˆıntr-o stare ˆın care se activeaz˘a ie¸sirea Z.
Automatul Mealy poate cont¸ine o stare mai put¸in deoarece poate activa ie¸sirea cu o perioad˘a mai devreme, pe
baza st˘arii prezente ¸si a intr˘arii. Organigramele celor dou˘a tipuri de automate sunt prezentate ˆın figura 14.6.
Moore Mealy
Figura 14.6 Organigrame pentru problema 3: Moore ¸si Mealy.
Figura 14.7 prezint˘a grafurile de tranzit¸ii asociate acelora¸si automate.
Moore Mealy
Figura 14.7 Grafuri de tranzit¸ii: Moore (ˆın noduri Q[2 : 0]/Z, pe arce X) ¸si Mealy (ˆın noduri Q[1 : 0], pe arce X/Z).
Formele de und˘a ¸si succesiunea st˘arilor automatelor sunt prezentate ˆın figura 14.8.
S-a notat cu Zdel semnalul de la ie¸sirea automatului Mealy ˆıntˆarziat cu o perioad˘a. Se observ˘a a forma de
und˘a a ie¸sirii automatului Mealy cu ˆıntˆarziere Zdel este identic˘a cu cea a ie¸sirii automatului Moore, de¸si st˘arile
automatului difer˘a.
Tabelele de tranzit¸ii ale celor dou˘a tipuri de automate sunt:
186 LECT¸ IA 14. Automate sincrone
Figura 14.8 Formele de und˘a ¸si succesiunea st˘arilor automatelor.
Automat Moore Automat Mealy
X Q
[2:0]
D
[2:0]
Z X Q
[1:0]
D
[1:0]
Z
0 a 000 a 000 0 0 a 00 a 00 0
1 000 b 001 0 1 00 b 01 0
0 b 001 a 000 0 0 b 01 a 00 0
1 001 c 010 0 1 01 c 10 0
0 c 010 d 011 0 0 c 10 d 11 0
1 010 c 010 0 1 10 c 10 0
0 d 011 a 000 0 0 d 11 a 00 0
1 011 d 100 0 1 11 c 10 1
0 e 100 a 000 1
1 100 c 010 1
- 101 - - - -
- 110 - - - -
- 111 - - - -
4. Determinat¸i graful de tranzit¸ii al unui automat care semnaleaz˘a pe ie¸sire existent¸a pe cele dou˘a intr˘ari a 3 sau
mai mult¸e coincident¸e secvent¸iale ¸si consecutive ale celor dou˘a intr˘ari.
5. Determinat¸i graful de tranzit¸ii al unui automat care semnaleaz˘a pe ie¸sire existent¸a pe intrare a 3 sau mai mult¸i
bit¸i secvent¸iali ¸si consecutivi egali.
6. Determinat¸i graful de tranzit¸ii al unui automat cu dou˘a intr˘ari ¸si o ie¸sire avˆand urm˘atoarea funct¸ionare:
- Pe una din intr˘ari se primesc grupuri de ate 4 bit¸i, cu bitul cel mai semnificativ primul.
- Pe a doua intrare se primesc pulsuri de ate o singur˘a perioad˘a de ceas, nu mai dese decˆat un puls la 4 perioade
de ceas. A doua intrare marcheaz˘a momentul and pe prima intrare este primul bit din grupul de 4 bit¸i.
-
ˆ
Intre dou˘a grupuri de 4 bit¸i pot ¸si pauze. Pe durata pauzei, valorile primei intr˘ari sunt ignorate.
- Ie¸sirea este activat˘a dac˘a la finalul unei secvent¸e de 4 bit¸i valid˘a se constat˘a a secvent¸a nu reprezint˘a cifre ˆın
format BCD (ˆıntre 0 ¸si 9).
14.4 Pentru cei ce vor a devin˘a profesioni¸sti
1. Care este avantajul codific˘arii ”one-hot” a st˘arilor unui automat?
2. Pentru implementarea unui automat care a funct¸ioneze la frecvent¸˘a maxim˘a, se recomand˘a codificarea st˘arilor:
a) cu dependent¸˘a redus˘a;
b) cu variat¸ie minim˘a;
c) ˆın cod Gray;
d) ˆın cod binar;
e) ”one-hot”.
3. Care este num˘arul minim de bistabile cu care poate implementat un automat cu 2015 st˘ari? ate bistabile
sunt necesare pentru implementarea automatului cu codificare ”one-hot”?
14.4. Pentru cei ce vor a devin˘a profesioni¸sti 187
4. Reducet¸i num˘arul de st˘ari ale automatului Moore imediat descris prin graful din figura 14.9-a, transformˆandu-l
ˆın automat Mealy cu ˆıntˆarziere.
- Demonstrat¸i pe un scenariu de forme de und˘a ca temporizarea ie¸sirilor celor dou˘a automate este identic˘a.
- Precizat¸i schemele bloc ale celor dou˘a automate.
- Implementat¸i cele dou˘a automate cu bistabile D.
a) b)
Figura 14.9 a) Graful de tranzit¸ii al automatului Moore imediat. b) Graful de tranzit¸ie al automatului echivalent, Mealy cu
ˆınarziere.
Solut¸ie
Se observ˘a a automatul detecteaz˘a aparit¸ia pe intrare a 4 sau mai mult¸i bit¸i consecutivi egali cu 1. Ie¸sirea este
activat˘a doar ˆın starea e.
ˆ
In cazul ˆın care intrarea este stabil˘a pe parcursul unei perioade de ceas (dac˘a provine
de la ie¸sirea unui alt bistabil ce comut˘a pe acelea¸si semnal de ceas) se poate ˆıncerca transformarea automatului
Moore ˆıntr-un automat Mealy echivalent ca ¸si funct¸ionare.
ˆ
In acest caz, se poate elimina starea e. Ie¸sirea va
depinde atˆat de stare at ¸si de intrare. Dup˘a 3 valori egale cu 1 primite, automatul ajunge ˆın starea d. Dac˘a
se mai prime¸ste ˆınc˘a o valoare egal˘a cu 1, ie¸sirea se activeaz˘a ¸si starea d este ment¸inut˘a. Deoarece automatul
Mealy react¸ioneaz˘a combinat¸ional la intrare, acesta va activa ie¸sirea cu un tact mai devreme decˆat automatul
Moore init¸ial.
ˆ
Ins˘a, dac˘a pe ie¸sirea automatului Mealy imediat se pune un registru, acesta se transform˘a ˆın
automat Mealy cu ˆıntˆarziere. Automatul Mealy cu ˆıntˆarziere nu numai a reface temporizarea corect˘a a ie¸sirii
dar rezolv˘a ¸si problemele cauzate de ie¸sirea din circuitul combinat¸ional.
Schemele bloc ale celor dou˘a automate sunt prezentate ˆın figura 14.10. Se remarc˘a faptul a automatul Mealy
echivalent are mai put¸ine st˘ari decˆat automatul Moore.
ˆ
In acest caz, reducerea st˘arilor de la 5 la 4 determin˘a ¸si
sc˘aderea num˘arului de bit¸i necesari pentru codificarea st˘arilor de la 3 la 2.
a) b)
Figura 14.10 Schemele bloc ale automatelor: a) Moore imediat. b) Mealy cu ˆınarziere.
5. Reducet¸i num˘arul de st˘ari ale automatelor a aror funct¸ionare este descris˘a prin grafurile de tranzit¸ii din figura
14.11.
188 LECT¸ IA 14. Automate sincrone
a) b)
Figura 14.11 Grafuri de tranzit¸ii cu st˘ari redundante.
Solut¸ie
St˘arile redundante sunt st˘ari din care automatul prezina aceea¸si evolut¸ie. Arcele care ies din st˘arile redundante
au acelea¸si condit¸ii ¸si acelea¸si st˘ari destinat¸ie. St˘arile redundante au acelea¸si valori ale ie¸sirilor. O stare redun-
dana poate eliminat˘a. Arcele care sosesc pe acea stare ˆı¸si mut˘a destinat¸ia pe cealalt˘a stare echivalent˘a. Arcele
care pleac˘a de pe starea redundant˘a dispar.
a) Pe graful de tranzit¸ii se identific˘a st˘arile a ¸si b ca fiind redundante. Figura 14.12 marcheaz˘a st˘arile redundante
¸si prezint˘a graful de tranzit¸ii echivalent, cu starea b eliminat˘a.
Figura 14.12 Reducerea st˘arilor pe un graf de tranzit¸ii (problema 5-a).
b) Pe graful de tranzit¸ii se identific˘a st˘arile b ¸si h, respectiv a ¸si i ca fiind redundante. Figura 14.13 marcheaz˘a
st˘arile redundante ¸si prezina grafurile de tranzit¸ii echivalente cu starea b ¸si apoi starea a eliminate. Se observ˘a
a resetarea automatului ˆın starea i este echivalent˘a cu resetarea acestuia ˆın starea redundant˘a a.
14.4. Pentru cei ce vor a devin˘a profesioni¸sti 189
Figura 14.13 Reducerea st˘arilor pe un graf de tranzit¸ii (problema 5-b).