1

AUTOMATE FINITE

1. Scopul lucrăriiStudiul automatelor cu stări finite ce conţin bistabile care lucrează sincron

şi intrări care se modifică sincron sau asincron cu semnalul de ceas. Descriereafuncţionării se face prin organigrame sau prin forme de undă.

2. Aparate necesare- panouri logice- sursă de alimentare reglabilă- voltmetru electronic (sau tip MAVO-35)- cordoane de legătură

3. Consideraţii teoreticeUn automat cu stări finite se defineşte formal prin cvintuplul

( )A X Y Q= , , , ,λ δunde entităţile componente au următoarea semnificaţie:

{ }X x x xn= 1 2, ,..., - mulţimea configuraţiilor binare de intrare,

{ }Y y y yr= 1 2, , ... , - mulţimea configuraţiilor binare de ieşire, { }Q q q q p= 1 2, , ... , -mulţimea configuraţiilor binare de stare,λ : X Q Q× → - funcţia de tranziţie a stărilor,δ : X Q Y× → - funcţia de tranziţie a ieşirilor.

Datorită faptului că mulţimile X , Y şi Q sunt finite, circuitul se numeşte automatcu stări finite. Spaţiul timpului nu apare explicit în descrierea de mai sus. El este discret şieste format din mulţimea numerelor întregi care semnifică multiplul de T , unde T esteperioada după care se comandă o nouă modificare în circuit. Funcţiile λ şi δ se potdefini şi reprezenta prin tabele de tranziţii, grafuri, sau organigrame. Schema din figura3.1 reprezintă un automat finit ale cărui ieşiri apar cu întârziere deoarece sunt trecute prinmemorie. Ele pot fi obţinute şi imediat de la ieşirea CLC-ului.

CLC

MEMORIE

X

Q

Y

CLK

Fig. 3.1 Structura generală a unui automat finit

2

Sistemele logice secvenţiale la care tranziţiile au loc periodic, simultan cu unimpuls de ceas se numesc sincrone. Când tranziţiile au loc la intervale arbitrare de timp,odată cu modificarea semnalelor de intrare, sistemele secvenţiale sunt de tip asincron.Aici ne ocupăm numai de sisteme secvenţiale sincrone. Variabilele de intrare pot fiasincrone, dar în acest caz trebuie făcută o codificare atentă a stărilor, conformprincipiului dependenţei reduse faţă de o variabilă.

Vom studia două exemple de proiectare a unor automate cu stări finite cu numărmic de stări şi o singură variabilă de intrare. Memoria este realizată în ambele cazuri cucircuite bistabile de tip D, ceea ce diferă fiind modul de implementare a circuitelor logicecombinaţionale (CLC). În primul caz se folosesc multiplexoare (circuite integrate MSI),iar în cel de-al doilea caz memorii(circuite integrate LSI).

3.1. Să se proiecteze un automat finit cu o intrare (notată cu X) şi două ieşiri(notate cu Y1 şi Y2), descris de organigrama de mai jos, folosind bistabili de tip D şimultiplexoare cu 4 căi de intrare.

A

B

C

X

X

Y1=1Y2=0Y1 = 1Y2 = 0Y 1 = 1 Y1=1 / Y2=0Y1 = 1Y2 = 0

Y2 = 0Y1 = 0

Y1 = 0Y2 = 1

0 1

0 1

Q1Q200

11

01

Fig. 3.2 Organigrama care descrie funcţionarea automatului finit

Pornind de la organigramă se construieşte tabelul tranziţiilor:

X Q 1 Q2 Q 1+ Q 2

+

0 0 01 0 0d 0 10 1 11 1 1

Y1 Y2

0 11 10 00 11 1

1 01 00 00 10 1

Fig. 3.3 Tabelul tranziţiilor

Simbolul d poate fi 0 sau 1 logic(don' t care). S-a folosit această notaţie pentru aevita confuzia cu semnalul de intrare notat cu X. Implementarea memoriei se face cu doibistabili de tip D care comută sincron. Circuitul logic combinaţional are intrările X, Q1 şiQ2, şi trebuie să genereze la ieşire funcţiile binare Q1

+=D1 şi Q2+=D2. Nu este necesară

minimizarea funcţiilor binare D1 şi D2 pentru că toţi termenii canonici sunt disponibili laieşirile multiplexoarelor.

3

O1

O2

O3

O4

A9A8A7A6A5A4A3

A2

A1

A0

PROM

D Q

D Q

CLK

CLK

Q

Q

X

CLK

1

2Y1

Y2

Fig. 3.6 Schema logică a automatului implementat cu memorie PROM

4. Modul de lucru4.1. Primul panou logic pe care îl studiem este cel care implementează

automatul finit în varianta cu bistabile de tip D şi multiplexoare. El conţine 4 circuiteintegrate CMOS: MMC 4013, MMC 4052(2 buc.) şi MMC 4011. MMC 4013 conţinecele 2 bistabile D, MMC 4052 conţine câte 2 multiplexoare, iar 2 din cele 4 porţi ŞI-NU ale circuitului MMC 4011 sunt folosite pentru generarea manuală a semnalului deCLK, prin apăsarea butonului cu revenire de pe panou. Biţii de stare şi de ieşire suntvizualizaţi prin intermediul a 4 LED-uri. Starea 1 logic este semnalizată prinaprinderea LED-ului corespunzător, iar cea de 0 logic prin stingerea lui. Montajul se alimentează cu orice tensiune continuă cuprinsă între 5 şi15Vcc, după conectarea corectă a cordoanelor de alimentare la sursă şi a intrării X launa din cele 2 borne ale sursei (0 logic sau 1 logic). Se verifică funcţionarea corectă a montajului prin urmărirea tuturor tranziţiilorposibile din organigramă sau tabel.

4.2. Al doilea panou logic implementează automatul finit în varianta cubistabile de tip D şi memorie. Din motive de versatilitate s-a înlocuit memoria PROMcu o memorie RAM statică de aceeaşi capacitate, de tipul MMN 2114. Placa maiconţine circuitele MMC 4013, MMC 4011 şi MMC 4066, ultimul având în structură 4comutatoare CMOS necesare pentru înscrierea, respectiv citirea datelor din memorie.Vizualizarea stării şi a ieşirii se face tot cu ajutorul a 4 LED-uri.

Montajul se alimentează cu tensiunea de 5 Vcc, datorită prezenţei lui MMN2114. De fapt, tensiunea sursei este de circa 5,6 - 5,7 V datorită diodei serie deprotecţie la alimentare inversă. Din acest motiv se măsoară cu voltmetrul tensiuneade 5 Vcc între catodul diodei de protecţie şi masă.

După alimentarea corectă se introduc în memorie datele necesare. În acestscop, pentru a asigura adresa 0 de start a memoriei la cuplarea alimentării (A2= A1 = A0 = 0), comutatorul S2 are pârghia înspre comutatoarele S1 şi S3(în jos), iarcomutatorul S3 în dreapta (vezi fig. 4.1). Intrarea X este conectată la masă.

Cele 4 comutatoare notate cu S1 sunt destinate introducerii celor 4 biţi pecuvânt în memorie. Dacă pârghia este în jos, bitul corespunzător este pe 0 logic, iardacă este în sus, pe 1 logic. După fixarea cuvântului dorit prin poziţionarea celor 4

4

LEDURI

S2S1

( IN DATE)(WE)

S3

(CLK)

Fig. 4.1 Amplasarea comutatoarelor şi a LED-urilor pe panou

comutatoare, acesta este introdus în memorie prin ridicarea şi coborârea înapoi apârghiei comutatorului S2 (activarea şi dezactivarea semnalului WE - WRITEENABLE ). Pe urmă se modifică adresa pentru introducerea unui nou cuvânt prinacţionarea în cele două sensuri a comutatorului S3 (pentru a genera cele 2 fronturi alesemnalului de ceas CLK - CLOCK ). Pentru introducerea datelor în memorie urmărimharta memoriei din figura 3.5. Ieşirile O1…O4 devin acum I/O1…I/O4, iar datele seintroduc de la comutatoarele S1, de la stânga la dreapta, în ordinea dată în tabel.Pentru înscrierea celor 6 cuvinte utile în memorie se parcurg următorii paşi:

a) se fixează comutatoarele S1 pe poziţiile 1001se acţionează în sus şi în jos comutatorul S2 (WE)

se acţionează stânga - dreapta comutatorul S3 (CLK)

b) se fixează comutatoarele S1 pe poziţiile 0000se acţionează în sus şi în jos comutatorul S2 (WE)

se acţionează stânga - dreapta comutatorul S3 (CLK)se mută X pe 1 logic (borna de +5Vcc)

c) se fixează comutatoarele S1 pe poziţiile 1011se acţionează în sus şi în jos comutatorul S2 (WE)

se acţionează stânga - dreapta comutatorul S3 (CLK)

d) se fixează comutatoarele S1 pe poziţiile 0111se acţionează în sus şi în jos comutatorul S2 (WE)

se acţionează stânga - dreapta comutatorul S3 (CLK)se mută X pe 0 logic (borna de masă)

e) se fixează comutatoarele S1 pe poziţiile 0101se acţionează în sus şi în jos comutatorul S2 (WE)

se acţionează stânga - dreapta comutatorul S3 (CLK)se mută X pe 1 logic (borna de +5Vcc)

f ) se fixează comutatoarele S1 pe poziţiile 0000se acţionează în sus şi în jos comutatorul S2 (WE)

se acţionează stânga - dreapta comutatorul S3 (CLK)se mută X pe 0 logic (borna de masă)

Din acest moment datele sunt stocate în memorie şi se poate verificafuncţionarea corectă a automatului urmărind tranziţiile din organigramă. Întrerupereaalimentării duce la pierderea informaţiei din memorie şi se impune repetareaoperaţiilor de scriere a celor 6 cuvinte în RAM.

5

4.3. Comparaţi cele două implementări prezentate. Ce avantaje şi dezavantajeprezintă fiecare din cele două soluţii? Propuneţi şi alte modalităţi de realizare aautomatului.

4.4. Ce înseamnă codificare care urmăreşte principiul dependenţei reduse faţăde o variabilă? În cazul nostru variabila X poate fi asincronă(se poate modifica înorice moment de timp, nu numai pe frontul activ al semnalului CLK)? Alegeţi o altăcodificare a stărilor şi arătaţi sub formă tabelară harta memoriei precum şi operaţiunilenecesare pentru înscrierea datelor în memorie.

5. Probleme rezolvate5.1. Se consideră automatul finit descris de organigrama din figură. Să se

implementeze circuitul folosind bistabili de tip D şi:a) număr minim de porţib) multiplexoare cu 4 căi de intrarec) memorie ROM de 32 cuvinte a câte 4 biţid) un circuit combinaţional format din memorie ROM de 4 cuvinte a câte 4 biţi

şi multiplexoare. Reprezentaţi harta memoriei.

A

B

Q1Q200

11

C

X0 1

1

X0 1

2

01

X 013D

X 014

10

Fig. 5.1 Organigrama care descrie funcţionarea automatului finit din problema 5.1

Rezolvare:Construim tabelul tranziţiilor:

Q 1 Q 2 Q 1+ Q 2

+

0 00 0

1 1

1 0

X4X3X2X1 0 0 0 00 x x x 0 0 0 11 x x xx 0 1x x0x 0 1x x1x 1 1x x 0x 1 1x x 10 1 0x x x1 1 0x x x

0 0

1 1

Fig. 5.2 Tabelul tranziţiilor pentru organigrama din figura 5.1

a) Pentru implementarea cu porţi este necesară minimizarea funcţiilor binareQ D1

+1= şi Q D2

+2= . Folosim diagramele Veitch-Karnaugh condensate.

6

Q1Q1

Q2

Q2

Q1Q1

Q2

Q20 x1

D1 D2

x2 x2x3 0x4x4

a

Q1Q2

21

20

0 1 2 3

WMUX

D1

Q1Q2

21

20

0 1 2 3

WMUX

D2

0 x2 x4 x3 x1 x2 x4 0

b Fig.5.3 Soluţiile problemei pentru punctele a şi b

c

Q2

D1

x1

d

x1 x2

Q1Q2

21

20

0 1 2 3

WMUX

x4 x3

D1

D2

A1

A0

O0

O1

O2

O3OE

ROM

0

1MUX

0

1MUX

Q1

Q2

A4A3A2

A1A0

O0

O1

O2

O3OE

ROM

A4A3A2

A1A0

O0

O1

O2

O3OE

ROM

x2x3x4Q1

D2

A1 A0 O0 O1 O2 O30 00 11 01 1

0 0 0 11 0 1 00 1 0 10 1 0 0

Fig. 5.4 Soluţiile problemei pentru punctele c şi d

Evident că, fiind o problemă de sinteză, există şi alte soluţii. De exemplu, lapunctul c se putea utiliza un singur cip de memorie ROM de tipul 32 4× şi douămultiplexoare cu câte 2 intrări. Ar fi fost mai avantajoasă această implementare? Dece?

5.2. Să se proiecteze un sistem numeric care să asigure funcţionarea automată abarierelor la trecerea peste calea ferată. Sistemul are 2 intrări, x1 şi x2 , date de stărileunor contacte amplasate de o parte şi de alta a şoselei. Ieşirea y comandă închidereabarierelor.

Rezolvare:Presupunem că atunci când contactele sunt închise avem 1 logic pe intrări, iar

comanda de închidere a barierelor se dă pentru 1 logic la ieşire.

Fig. 5.5 Sistemul are 9 stări distincte, numerotate de la 0 la 8

7

Qx1x2

0 0,000 01 11 10

4,1 - 1,11 2,1 1,17,1-2 2,1 3,1 - -3 0,0 3,1 - -4 5,1 4,1 8,1 -5 5,1 - - 6,16 0,0 - - 6,17 - 3,1 7,1 -8 - - 8,1 6,1

Q+, y

Qx1x2

0 0,000 01 11 10

4,1 - 1,1

0,0 3,14 5,1 4,1 8,1

-5

6,16,18

Q+, y

Codificarea binară a stărilor: 0 00 1 = 2 = 7 01 3 = 6 11 4 = 5 = 8 10, , ,

1 2,1 1,17,12 3,17= =3 6== =

Fig. 5.6 Tabelul tranziţiilor. Reducerea şi codificarea stărilorDupă minimizare se obţin: D x x x Q Q Q1 1 2 1 1 1 2= + + , D x x x Q Q Q2 1 2 2 2 1 2= + + şi

y Q Q= +1 2 . Sistemul este secvenţial sincron, cu comportament asincron.

5.3. Un sistem secvenţial are 2 intrări şi o ieşire care detectează orice secvenţăde 4 stări succesive pentru care cele două intrări sunt identice. La detectarea acesteisecvenţe ieşirea capătă valoarea logică 1 atât timp cât intrările sunt identice. Să seproiecteze sistemul.

Rezolvare:

Fig. 5.7 Sistemul are 5 stări distincte, numerotate de la 1 la 5

Qx1x2 00 01 11 10

1 2,02

2,0

Q+, y

1,03,0

1,01,0 3,0 1,0

3 4,0 4,01,0 1,04 5,1 1,0 1,05,15 5,1 1,0 1,05,1

Sistemul are 4 stări distincte.

Alegem următoarele coduri binare1 002 013 11

4 = 5 10

Fig. 5.8 Tabelul tranziţiilor. Reducerea şi codificarea stărilor

După minimizarea funcţiilor binare Q D1 1+ = şi Q D2 2

+ = obţinem următoareleexpresii: ( )D x x Q Q1 1 2 1 2= ⊕ ⋅ + , D x x Q2 1 2 1= ⊕ ⋅ şi y x x Q Q= ⊕ ⋅ ⋅1 2 1 2 .

Problema se putea rezolva mai simplu, dacă observam de la început că x x1 2=

înseamnă x x1 2 1⊕ = şi obţineam un sistem cu o singură intrare x x x= ⊕1 2 . Sistemuleste secvenţial sincron, cu comportament asincron.