Implementarea automatelor finite

Implementarea automatelor finite

1Introducere

Circuitele basculante sunt circuite electronice caracterizate prin faptul ca iesirea acestuia,in conditii precizate,efectueaza tranzitii intre doua stari, una caracterizata printr-un nivel jos de tensiune (L- low),iar

cealalta caracterizata printr-un nivel de tensiune mare ( H - high).

Nivelul L este apropiat de valoarea tensiunii negative de alimentare a circuitului, iar daca alimentarea de curent continuu este cu o singura sursa nivelul este apropiat de potentialul masei circuitului.

Nivelul H este apropiat de valoarea tensiunii pozitive de alimentare a circuitului.

Nivelele L si H de tensiune sunt asociate valorilor logice binare zero logic si respectiv unu logic.

Circuitul basculant este bistabil daca tranzitia dintr-o stare in alta a iesirii are loc numai sub actiunea unui impuls numit impuls de basculare.

Impulsul de basculare reprezinta o tranzitie pozitiva (tensiunea creste)sau o tranzitie negativa a semnalului (tensiunea scade) care se aplica la intrarea circuitului.

Circuitul este basculant astabil (CBA :daca tranzitia iesirii de la o stare la alta are loc la momente de timp stabilite de elementele fizice ale circuitului, fara ca sa fie necesara aplicarea vreunui impuls de basculare. Circuitul genereaza la iesire oscilatii cu forma de unda dreptunghiulara

Circuitele basculante bistabile (CBB) sunt automate sincrone sau asincrone care prezinta doua stari stabile.

Acestea fac parte din marea familie a circuitelor logice secventiale (c.l.s.), cunoscute in literatura si sub denumirea de sisteme de ordin 1. Trecerea de la sistemele de ordin zero (c.l.c.) la cele de ordin superior se face prin introducerea unor reactii care-i confera sistemului proprietatea de 'memorie'. Astfel, iesirile circuitului secvential sunt partial independente de semnalele de intrare din acel moment, depinzand,tot partial,de starile anterioare ale circuitului.

Functia principala realizata de un CBB este de element fundamental de memorie (volatila) pentru 1 bit. Structurile cele mai simple de CBB sunt circuitele de ordinul unu cu o singura bucla de reactie RS sau D. Alte structuri CBB mai evoluate sunt circuitele de ordin doi JK si T.

Exista diferite tipuri de asemenea circuite, fiecare din acestea avand doua proprietati importante:

a)Un circuit basculant bistabil are numai doua stari stabile.Starile stabile sunt starile in care circuitul poate ramane un timp nedefinit daca nu se modifica intrarile. Astfel, un bistabil poate functiona ca o memorie de 1 bit.

b)Un bistabil are doua iesiri, care sunt intotdeauna complementare una fata de cealalta. Acestea se noteaza de obicei prin Q si

2Implementarea cu bistabili de tip D

Bistabilul este un bistabil cu o singura intrare de date, notata cu D, si o intrare de tact. Starea urmatoare a bistabilului este aceeasi cu cea a intrarii D, indiferent de starea prezenta. Deci, valoarea logica aplicata la intrare se transfera la iesire doar la aplicarea semnalului de tact, adica cu o intarziere de o perioada de tact. De aceea, bistabilul D se mai numeste circuit elementar de intarziere (D - Delay).

Tabelul de adevar a CBB-D este prezentat in figura 2.1. din care se extrage forma ecuatiei de functionare:,unde este starea intrarii de date la momentul t.

Figura

Rezulta diagrama Karnaugh din Figura 2.2.

Figura :Diagrama Karnaugh a bistabilului D

Plecand de la ecuatia de functionare a CBB-D:

.

Deci CBB-D va avea urmatoarea structura:

Figura 2.

Din analiza diagramei de semnale rezulta ca CBB-D lucreaza ca si repetor dar realizeaza si principala functie a CBB si anume cea de intarziere (delay). CBB-D urmareste la fiecare impuls de tact evolutia intrarii sesizand la iesire modificarea intrarii de date pe toata durata palierului activ al ceasului.

CBB-D sunt folosite in mod special pentru realizarea unor structuri complexe de memorie cum ar fi: registrele de deplasare si blocurile de memorie adresabile prin decodificatoare si multiplexoare. PRESET (preinscriere) si CLEAR (stergere) sunt intrari asincrone prioritare utile in sistemele digitale pentru inscrierea unei informatii de initializare sau resetare a unor structuri ce contin bistabili.

Pe durata impulsului de tact, iesirea bistabilului este egala cu intrarea (deci, iesirea urmareste intrarea). La trecerea semnalului de tact in 0 logic, se mentine starea existenta in acel moment. De aceea, acesta este un circuit latch

Exista si bistabile D care comuta pe frontul pozitiv sau negativ al semnalului de tact.

Implementarea cu bistabili de tip JK

Denumirea specifica a acestui tip de circuit basculant bistabil vine de la denumirea in limba engleza (J) jump= salt si (K) keep= a tine.

Constructia CBB-JK urmareste metoda generala de sinteza a automatelor sincrone .

Bistabilul JK sincron se obtine din bistabilul RS sincron prin modificarea structurii acestuia, astfel incat sa se elimine starea de nedeterminare ce apare datorita combinatiei de intrare RS

Bistabilul JK este realizat astfel incat pentru aceasta combinatie a intrarilor va comuta in starea complementara

la aparitia impulsului de tact. Intrarile acestui bistabil se noteaza cu J si K, acestea corespunzand intrarilor S, respectiv R ale bistabilului RS din care se obtine.

Tabelul caracteristic simplificat este prezentat in figura 1:

Figura Tabelul caracteristic simplificat al bistabilului JK

Diagrama Karnaugh corespunzatoare este prezentata in figura 2:

Figura 2: Diagrama Karnaugh simplificata a bistabilului JK

Rezulta ecuatia de stare:

Figura 3:Tabel de adevar pentru determinarea expresiilor R si S in functie de J,K si Qn.

Pentru ca starea urmatoare sa corespunda acestei ecuatii, la intrarile R S ale bistabilului RS sincron trebuie sa se aplice anumite semnale. In continuare determinam expresiile acestor semnale(ecuatiile intrarilor bistabilului RS) in functie de intrarile J K si starea Qn. Tabelul de adevar in care se exprima Qn+1 in functie de J K si Qn se completeaza cu doua coloane corespunzatoare intrarilor R S,care se completeaza pe baza tabelei de excitatie a bistabilului RS.(figura 3).

Diagramele Karnaugh pentru semnalele R si S sunt prezentate in figura 4:

Figura 4: Diagramele Karnaugh pentru determinarea semnalelor R S de la intrarea bistabilului RS din care se obtine bistabilul JK

Ecuatiile pentru R si S sunt urmatoarele:

De aici rezulta prima forma a circuitului (Figura 5):

Figura 5: Prima forma a schemei bistabilului JK sincron.

Tinand cont de proprietatea de asociativitate a functiei SI logic, se poate scrie:

Rezulta schema logica finala a bistabilului JK din Figura 6.a, simbolul bistabilului fiind indicat in Figura 6.b

Figura 6:Bistabilul JK sincron:a)schema logica

b)simbolul

Tabelul excitatiilor este prezentat in figura 7:

Figura 7: Tabelul excitatiilor pentru bistabilul JK

Daca ambele intrari sunt 1 logic, JK = 11, presupunand ca bistabilul se afla in starea Q = 1, va trece in starea Q = 0. Daca semnalul de tact persista, devine 0, iar devine 1, ceea ce va determina,din nou, comutarea bistabilului, in starea Q = 1. Deci, pe durata semnalului de tact (CLK si cu intrarile JK = 11, circuitul oscileaza. Pentru a exista o singura comutare, durata impulsului de tact trebuie sa fie mai mica decat timpul de propagare a semnalului prin doua porti, si mai mare decat timpul de propagare a semnalului printr-o poarta. Aceasta deficienta este eliminata la bistabilul JK Master-Slave

Utilizarea bistabilului JK sincron la proiectarea circuitelor secventiale este avantajoasa datorita numeroaselor situatii redundante pentru circuitul combinational care determina conditionarea intrarilor(dupa cum rezulta din tabelul excitatiilor), ceea ce conduce la solutii mai economice.

4.Implementarea cu memorii de tipul ROM

Memoriile ROM Read Only Memory reprezinta o categorie de circuite programabile care se pot utiliza pentru implementarea unui set de functii logice. Aceste memorii contin un set de locatii utilizate pentru stocarea informatiei binare. Continutul acestor locatii este fixat in momentul fabricatiei, aceste memorii fiind programate prin masti. Pe langa acestea, exista si memorii ROM programabile care utilizeaza fuzibile, numite PROM Programmable ROM). Acestea pot fi inscrise de catre utilizator, cu ajutorul unui echipament de programare corespunzator. De asemenea, exista memorii PROM care pot fi sterse cu ajutorul razelor ultraviolete, si apoi pot fi reprogramate.

Acestea se numesc EPROM Erasable Programmable ROM). In fine, memoriile ROM care utilizeaza o tehnologie de stergere prin impulsuri electrice se numesc EEPROM sau PROM Electrically Erasable Programmable ROM). Diferitele variante de memorii ROM sunt nevolatile, deci isi pastreaza continutul si dupa intreruperea tensiunii de alimentare.

O memorie ROM are k intrari si n iesiri. Intrarile furnizeaza adresa pentru memorie,iar iesirile furnizeaza continutul cuvantului selectat de adresa de la intrare. Numarul cuvintelor dintr-o memorie ROM este determinat de faptul ca prin k linii de adresa se pot selecta 2k cuvinte. Memoria ROM nu are date de intrare, deoarece nu este posibila operatia de scriere. Memoriile ROM integrate dispun de una sau mai multe intrari de validare si iesiri cu trei stari pentru a permite realizarea unor memorii de dimensiuni mai mari.

Figura 4.1: Logica interna a unei memorii ROM cu capacitatea de 32

Consideram, de exemplu, o memorie ROM cu capacitatea de 32 8,care contine 32 de cuvinte de 8 biti fiecare. Exista 5 linii de intrare, care permit specificarea adreselor cuprinse intre 0 si 31. Structura interna a acestei memorii este indicata in Figura . Intrarile sunt decodificate in 32 iesiri distincte cu ajutorul unui decodificator 5:32.Fiecare iesire a decodificatorului reprezinta o adresa de memorie. Cele 32 de iesiri sunt conectate prin intermediul unor conexiuni programabile la fiecare din cele opt porti SAU Fiecare poarta SAU trebuie considerata ca avand 32 de intrari. Pentru aceste porti s-a utilizat reprezentarea simplificata Fiecare iesire a decodificatorului este conectata prin intermediul unui fuzibil la una din intrarile fiecarei porti SAU. Deoarece fiecare

poarta SAU are 32 de conexiuni interne programabile, si deoarece exista opt porti SAU,aceasta memorie ROM contine 32 8 = 256 de conexiuni programabile. In general, o memorie ROM cu capacitatea de n are un decodificator intern k: si n porti SAU.Fiecare poarta SAU are intrari, care sunt conectate prin conexiuni programabile la fiecare din iesirile decodificatorului.

Continutul locatiilor unei memorii ROM poate fi specificat printr-o tabela de adevar. De exemplu, continutul unei memorii ROM cu dimensiunea de 32 8 poate fi specificat printr-o tabela de adevar similara cu cea din figura 4.2. Fiecare combinatie a intrarilor din tabel specifica adresa unui cuvant de 8 biti, a carei valoare este indicata in coloanele iesirilor. Tabelul 4.2 prezinta numai primele patru si ultimele patru cuvinte ale memoriei ROM; tabelul complet trebuie sa contina lista tuturor celor 32 de cuvinte

Figura 4.2:Tabelul de adevar al unei memorii ROM

Programarea memoriei ROM conform tabelului de adevar de mai sus conduce la configuratia din Figura 4. Fiecare valoare 0 din tabelul de adevar specifica un circuit deschis, si fiecare valoare specifica un circuit inchis. De exemplu, tabelul specifica un cuvant cu valoarea la adresa 000 0. Cei patru biti de 0 din cadrul cuvantului sunt programati prin deschiderea conexiunilor dintre iesirea 2 a decodificatorului si intrarile portilor SAU asociate cu iesirile A A A si A . Cei patru biti de din cadrul cuvantului sunt marcati cu un in schema, pentru a indica un circuit inchis.

Atunci cand intrarea memoriei ROM este 000 0, iesirea 2 a decodificatorului va fi la logic, celelalte iesiri fiind la 0 logic. Semnalul cu nivelul logic de la iesirea 2 a decodificatorului se propaga prin circuitele inchise si portile SAU la iesirile A A A si A0, iar celelalte iesiri raman la 0 logic. Rezultatul este ca la iesirile de date se aplica cuvantul cu valoarea

Un decodificator genereaza toti mintermii variabilelor

de intrare. Prin inserarea unor porti SAU pentru insumarea mintermilor functiilor booleene, se poate implementa orice circuit combinational. O memorie ROM contine atat un decodificator, cat si porti SAU in cadrul aceluiasi circuit. Prin inchiderea conexiunilor pentru mintermii inclusi in cadrul functiei, iesirile memoriei ROM pot fi programate

pentru a reprezenta functiile booleene ale variabilelor de intrare dintr-un circuit combinational.

Din punctul de vedere al unui circuit care implementeaza o functie booleana,fiecare terminal de iesire al unei memorii ROM este considerat separat ca iesire a functiei booleene exprimate ca o suma de mintermi. De exemplu, memoria ROM din figura poate fi considerata ca un circuit combinational cu opt iesiri, fiecare fiind o functie

a celor cinci variabile de intrare. Iesirea A7 poate fi exprimata ca o suma a mintermilor,in felul urmator (punctele reprezinta mintermii de la 4 la 27, care nu apar in figura

Figura 4.3:Programarea memoriei ROM conform tabelului din

figura 4.2

Deoarece o memorie ROM pastreaza de fapt intregul tabel de adevar al functiilor pe care le genereaza, o asemenea memorie poate fi utilizata pentru implementarea circuitelor combinationale complexe direct din tabelul de adevar. Procesul de citire a informatiilor memorate intr-o memorie ROM este similar cu o cautare intr-o tabela table lookup). Memoriile ROM sunt utile pentru implementarea unor circuite ale caror

functii sunt dificil de specificat prin ecuatii logice, ca de exemplu convertoare de cod sau circuite pentru operatii aritmetice complexe (inmultire, impartire), si pentru aplicatii care necesita un numar moderat de intrari si un numar mare de iesiri. Utilitatea memoriilor ROM este limitata de faptul ca dimensiunea lor trebuie dublata cu fiecare noua variabila de intrare.In practica, la implementarea unui circuit combinational printr-o memorie ROM, nu este necesar sa se deseneze schema logica sau sa se indice conexiunile interne din cadrul memoriei. Trebuie sa se specifice doar o anumita memorie ROM prin numarul circuitului si tabelul de adevar al memoriei. Tabelul de adevar contine toate informatiile necesare programarii memoriei.De exemplu, se considera proiectarea unui circuit combinational care accepta

la intrare un numar de 3 biti si genereaza la iesire un numar binar egal cu patratul numarului de la intrare. Prima etapa pentru proiectarea circuitului este intocmirea tabelului de adevar. In cele mai multe cazuri, aceasta este singura operatie necesara. In alte cazuri, se poate utiliza un tabel de adevar partial pentru memoria ROM tinand cont de anumite

proprietati ale variabilelor de iesire. Tabelul din figura 4.4 reprezinta tabelul de adevar pentru circuitul proiectat

Figura 4.4: Tabelul de adevar pentru circuitul care genereaza patratele valorilor de la intrare.

Pentru circuitul proiectat, sunt necesare trei intrari si sase iesiri. Se observa ca iesirea B0 este egala intotdeauna cu intrarea A0, astfel incat nu este necesara generarea acestei iesiri cu ajutorul memoriei ROM. De asemenea, iesirea B este intotdeauna 0.

Astfel, trebuie sa se genereze doar patru iesiri cu memoria ROM. Memoria trebuie sa aiba minimum trei intrari si patru iesiri. Cele trei intrari specifica opt cuvinte, deci dimensiunea

minima a memoriei necesare este de 8 Schema circuitului este prezentata in figura

Figura 4.5: Implementarea cu o memorie ROM a circuitului care genereaza patratele valorilor de la intrare