Sisteme cu stari finite - Concepte fundamentale

Concepte fundamentale

Obiect abstract. Stare. Sistem

Definitie: P reprezinta un obiect fizic caracterizat de o multime de parametri masurabili, cum ar fi lungimea, latimea, greutatea, culoarea sau forma. Aceste valori la un moment t sunt v₁(t), v₂(t), .

Din punct de vedere matematic, valoarea acestor functii in timp nu este relevanta. Relatiile dintre functii au insa o mare importanta. Aceste relatii particulare reprezinta un obiect abstract si se noteaza cu A.

Definitie: Un obiect abstract este o multime de perechi ordonate de functii de timp.

A = , unde

1. t_0, t₁ Є ( - ∞, +∞)

2. x_[t0,t1] se numeste intrare si se noteaza cu X

3. z_[t0,t1] se numeste iesire si se noteaza cu Z

4. Proprietatea de segmentare este adevarata. Acest lucru inseamna ca daca perechea (x_[t0,t1],z_[t0,t1]) Є A atunci orice pereche este tot din A.

Definitie: Perechea (X, Z) se numeste pereche intrare-iesire.

Definitie: Orice obiect abstract A reprezinta o multime de perechi de intrare-iesire, deci A = .

Definitie: Spatiul valorilor de intrare pentru un obiect abstract A este dat de urmatoarea multime de functii de timp:

D =

Definitie: Spatiul valorilor de iesire pentru un obiect abstract A este dat de urmatoarea multime de functii de timp:

R =

Reprezentarea oricarui obiect abstract este:

Definitie: Fie A₁, A_2, . o multime de obiecte abstracte si se presupune o anume interconectare a obiectelor in care intrarile si iesirile sunt egale cu iesirile si intrarile altor obiecte. O astfel de structura se numeste sistem si se noteaza cu S. Un sistem se reprezinta in felul urmator:

In conformitate cu aceasta definitie, orice sistem este un obiect abstract iar orice obiect abstract poate fi considerat un sistem.

Exemplu: Consideram doua obiecte abstracte A₁ si A₂ in care iesirea lui A₁ este conectata la intrarea lui A_2.

Constrangerile sunt urmatoarele:

S reprezinta sistemul iar X^S si Z^S reprezinta intrarea si iesirea acestuia. In general, dependenta intrare-iesire nu este unic determinata, ceea ce inseamna ca raspunsul sistemului nu depinde doar de intrarile curente dar si de cele trecute. De aceea o parte a intrarilor trecute trebuie sa fie memorate de sistem intr-o forma adecvata sub forma unor valori interne.

Definitie: Multimea valorilor curente interne se numeste stare interna a sistemului sau starea sistemului.

Definitie: Orice sistem care functioneaza in timp discret si pentru care valorile perechilor intrare-iesire si stare interna se afla intr-un numar finit de configuratii se numeste sistem cu stari finite (SSF).

Observatii:

1. Teoria sistemelor cu stari finite este o componenta importanta din teoria sistemelor.
2. SSF reprezinta un model ideal ce poate reprezenta o mare varietate de fenomene fizice sau dispozitive din multe domenii ale stiintei.

Sisteme cu stari finite ( SSF )

Definirea automatelor finite fara memorie

Consideram doua multimi finite nevide,

X =

Z =

care contin un numar finit de simboluri sau obiecte denumite alfabete.

Se considera un dispozitiv cu n intrari si m iesiri. Pe fiecare intrare sunt aplicate simboluri ce apartin alfabetului de intrare X, formandu-se astfel un vector de intrare de dimensiuni n.

X_i = ( x_i1, x_{i2, .,} x_in ), unde x_ik Є X, k Є [1,n]

La iesire, va fi generat un vector de iesire care are dimensiunea m

Z_j = ( z_j1, z_{j2, .,} z_jm ), unde z_it Є Z, t Є [1,m]

Functionarea dispozitivului consta in transformarea vectorului de intrare X_i in vectorul de iesire Z_j.

Luand in considerare ca numarul de intrari si iesiri este finit iar alfabetele X si Z sunt finite, putem spune ca spatiul intrarilor si al iesirilor sunt multimi finite:

D = kⁿ

R = l^m

Un astfel de sistem se comporta ca un transformator sau convertor de vectori in timp ce operatia poate fi descrisa sub forma unui tabel de corespondenta ce poarta numele de tabel de intrare-iesire.

Deoarece D este finita inseamna ca tabelul are un numar finit de randuri, mai exact kⁿ. Presupunand ca pentru vectorul de intrare X_j se genereaza vectorul Z_ij urmatorul tabel poate fi determinat.

unde

X_i Є D , i Є [1,kⁿ]

Є R , s Є [1,kⁿ]

Acest tabel poarta numele de tabel de adevar.

Definitie: Orice dispozitiv al carui comportament poate fi descris printr-un tabel de adevar se numeste automat fara memorie sau dispozitiv logic fara memorie.

Implementarea porta numele de retea combinationala logica (RCL) sau circuit logic combinational (CLC).

Observatii:

1. Orice RCL este caracterizat de o relatie intrare-iesire.
2. RCL reprezinta cea mai simpla clasa de dispozitive logice din structura oricarui calculator digital.
3. Automatele fara memorie sunt sisteme cu stari finite in care nu este nevoie sa se memoreze activitatea intrarilor.

2.2. Definirea automatelor finite cu memorie

In continuare vor fi considerate sisteme mai complexe, a caror operare este caracterizata de starea interna. Presupunem ca multimea tuturor starilor interne este finita si o notam cu S.

S =

In aceleasi conditii ca in paragraful anterior, folosim alfabetul de intrare X si cel de iesire Z, compuse dintr-un numar finit de simboluri de intrare si iesire.

X =

Z =

Presupunem ca sistemul are n intrari si m iesiri, pe fiecare intrare se aplica un simbol din alfabetul de intrare X ce formeaza un vector de intrare n-dimensonal.

X_i = ( x_i1, x_{i2, .,} x_in ), unde x_ik Є X, k Є [1,n]

La iesire, va fi generat un vector de iesire care are dimensiunea m format din simboluri din Z

Z_j = ( z_j1, z_{j2, .,} z_jm ), unde z_it Є Z, t Є [1,m]

In acest caz, raspunsul sistemului nu depinde numai de vectorul de intrare. Trebuie de asemenea cunoscuta starea curenta a sistemului la momentul t. Astfel trebuie cunoscuta perechea formata din starea curenta, S_t, si vectorul de intrare X_i (sau perechea intrare-stare). Ca iesire, va fi generat vectorul de iesire Z_j si starea urmatoare S_r, denumita pereche iesire-stare.

Definitie: S se numeste spatiul starilor sistemului; aceasta multime se presupune ca este finita. Evolutia unui astfel de sistem este dependenta de timp, deoarece S_t, starea curenta memoreaza istoria intrarilor. Operarea unui astfel de sistem este data de relatia "intrare-stare-iesire" (I-S-I). Operarea acestor sisteme este descrisa prin doua tabele T1 si T2 care reprezinta tabelul de iesire si tabelul de tranzitie a starilor.

Tabelul T1 pune in corespondenta o pereche intrare-stare cu un vector de iesire in timp ce T2 pune in corespondenta o pereche intrare-stare cu starea urmatoare. Astfel, T1 se numeste tabel iesire iar T2 se numeste tabel de tranzitie a starilor.

Tabelul T1 - tabel iesire

unde : Z_ij Є R (S), i Є [1,kⁿ], j Є [1,q]

Tabelul T2 - tabel de tranzitie a starilor

unde : S_ij Є S, i Є [1,kⁿ], j Є [1,q]

Definitie: Orice sistem a carui operare este caracterizata de un tabel de iesire si de un tabel de tranzitie a starilor se numeste automat finit cu memorie sau dispozitiv logic cu memorie.

Trebuie mentionate cateva moduri de descriere ale automatelor finite cu memorie, care sunt denumite si masini secventiale. Implementarea fizica a unei masini secventiale se numeste retea logica secventiala (RLS) sau circuit logic secvential (CLS).

Este evident ca pentru implementarea unor astfel de sisteme este necesara folosirea unor dispozitive de memorie pentru stocarea starii curente. In general o masina cu stari este un sistem care poate fi descris ca o multime de stari in care sistemul se poate afla. In momentul in care sistemul se afla intr-o stare, acesta trebuie sa fie capabil sa ramana in acea stare pentru o perioada finita de timp. Starea urmatoare in care sistemul se gaseste depinde de vectorul de intrare si de starea curenta.

2.3. Clasificarea sistemelor cu stari finite

Sistemele cu stari finite (SSF) se impart in doua clase:

a)      SSF deterministe

b)      SSF probabilistice

Definitie: Un SSF este determinist daca relatia sa intrare-iesire sau intrare-stare-iesire este de tip determinist, adica pentru un anumit vector de intrare corespunde in mod unic un vector de iesire sau pentru o pereche intrare-iesire corespunde in mod unic o pereche iesire-stare.

Definitie: Un SSF este probabilistic daca relatia sa intrare-iesire sau intrare-stare-iesire este de tip probabilistic, adica pentru un vector de intrare sau o pereche intrare-iesire date pot aparea la iesire oricare dintre vectorii de iesire sau perechile iesire-stare urmatoare, fiecare dintre aceste cu propria sa probabilitate.

Pentru automatele fara memorie de tip probabilistic tabelul intrare-iesire devine:

unde α _ij ≤ 1, si , oricare i Є[1,kⁿ]

α_ij reprezinta probabilitatea obtinerii unui vector Z_j din spatiul de iesire RCS cand se aplica vectorul de intrare X_i cu i Є[1,kⁿ].

In cazul unei operari normale, cand se aplica la intrare vectorul X_i la iesire se obtine un anume vector Z_j dar luand in considerare perturbatiile externe este posibil sa se obtina un alt vector la iesire iar in fiecare caz este estimata probabilitatea.

De aceea, pentru fiecare vector de intrare, tot randul din tabelul de corespondenta trebuie completat.

In cazul automatelor cu memorie (SSF), descrierea se realizeaza prin tabele similare cu probabilitati, iar tabelele T1 si T2 sunt impartite in q tabele noi, cate o tabela pentru fiecare coloana din tabelele initiale. Automatele probabilistice corespund situatiilor reale deoarece se iau in considerare perturbatii externe care pot produce o functionare anormala.

2.4. Automate binare. Exemple

In paragraful anterior alfabetele de intrare si de iesire X si Y au fost considerate finite, adica X = (x₁, x₂, ., x_n), Z = (z₁, z₂, ., z_p), in practica, datorita unor avantaje tehnice, sunt recomandate anumite alfabete. Este extrem de folosit un alfabet particular care contine doua simboluri reprezentate de numerele binare 0 si 1. Aceste simboluri se numesc BITI. Astfel, alfabetul de intrare devine X = iar alfabetul de iesire devine Z=.

Asa cum este cunoscut, termenul BIT reprezinta entitatea fundamentala de informatie care este folosita curent in majoritatea automatelor. Motivul pentru care alfabetul binar este folosit pe scara larga este legat de existenta multor dispozitive a caror operare este caracterizata de doua stari stabile, care au cost redus si viteza de operare foarte mari. Aceste doua stari stabile sunt asociate cu simbolurile 0 si 1.

Definitie: Multimea de automate care folosesc ca alfabete de intrare si iesire alfabetul binar se numesc automate binare.

In general, cand X si Z contin mai multe simboluri diferite este necesara o reprezentare cu ajutorul cifrelor binare 0 si 1 astfel incat fiecare simbol din X si Z este reprezentat in 0 si 1. In general, daca avem N entitati care trebuie reprezentate in forma binara cu simbolurile 0 si 1 este nevoie de pozitii (biti), daca N ≠ 2^k, in caz contrar este nevoie de pozitii (biti).

Dupa ce se determina k, procesul de asignare are loc, proces in care fiecarui simbol initial ii este asociata o combinatie unica de k biti. Dupa ce se construieste tabela de intrare-iesire sau intrare-stare-iesire in forma binara se trece la procedura de sinteza a automatului binar.

Exemplul 1. Automat finit cu memorie

Se cere sa se proiecteze un mixer de culori care are doua intrari si o iesire.

Alfabetul de intrare are trei culori X = = . Alfabetul de iesire are sase culori Z = = . Prin aplicarea simbolurilor din X pe intrarile I₁ si I₂ un simbol din Z este obtinut la iesirea O. Acest mixer reprezinta un automat fara memorie a carui tabela de adevar este urmatoarea:

Numarul total de simboluri N este:

N = U

N = 6, iar k = [log₂6] + 1 = 3

Este nevoie de trei biti pentru reprezentarea elementelor alfabetelor de intrare si iesire. Fiecare simbol are atribuita o combinatie de trei biti:

Cu trei biti se pot forma 2³ = 8 combinatii diferite dintre care numai sase au fost folosite. Doua combinatii 110 si 111 nu sunt folosite in procesul de codificare.

Fiecare simbol din tabela initiala de adevar este inlocuit cu combinatia sa binara, obtinandu-se astfel tabela de adevar pentru automatul binar. Aceasta tabela este cunoscuta sub numele de forma binara a tabelului de adevar. Automatul binar cu sase intrari binare si trei iesiri binare:

Tabela de adevar in forma binara este:

Exemplul 2. Automat cu memorie

Sa se obtina forma binara a tabelei de iesire si a tabelei de stari pentru un recunoscator de cuvinte. Alfabetul de intrare este alcatuit din toate literele mari si caracterul blank (Ь). Cuvintele sunt separate de un separator reprezentat de secventa "UWYЬ". Aceasta secventa a fost aleasa deoarece este imposibil sa faca parte din componenta unui cuvant. Cand terminatorul este descoperit automatul va genera iesirea Z=1, astfel incat alfabetul de iesire este binar Z₂ = . Astfel, propozitia ESTE VARA FRUMOASA este introdusa astfel ESTEUWYЬVARAUWYЬFRUMOASAUWYЬ

Pentru simplificarea notatiei consideram literele mari pana la T in λ (A, B, ., T ->λ). Astfel, alfabetul de intrare are cinci simboluri .

Diagrama bloc a automatului este:

Simbolurile de intrare sunt aplicate secvential pe intrare. Automatul analizeaza secventa de intrare iar daca un terminator este recunoscut atunci Z = 1 este produs la iesire. Va trebui sa proiectam un recunoscator al urmatoarei secvente de intrare "UWYЬ". Un astfel de automat trebuie sa memoreze valorile trecute ale intrarii. Acest automat are patru stari interne, notate A, B, C, D cu urmatoarea interpretare:

Starea A - automatul nu a recunoscut nimic din cuvantul terminator;

Starea B - automatul a recunoscut litera "U" din cuvantul terminator;

Starea C - automatul a recunoscut literele "UW" din cuvantul terminator;

Starea D - automatul a recunoscut literele "UWZ" din cuvantul terminator;

Putem construi tabelele T1 si T2 pentru acest automat.

Tabelul T1:

Tabelul T2:

Acest model trebuie transformat intr-un automat binar. Deoarece automatul are patru stari, A, B, C, D doua cifre binare vor fi folosite pentru reprezentare. Se alege urmatoarea asignare a starilor.

A -> 00

B -> 01

C -> 10

D -> 11

λ ->

U -> 001

W -> 010

Z -> 011

Ь -> 100

Tabelele T1 si T2 sunt inlocuite de versiunile binare. In continuare sunt prezentate tabela de iesire T1 si tabela de tranzitie a starilor codate binar.

Tabelul T1:

Tabelul T2:

In acest moment suntem pregatiti pentru implementarea automatului binar, adica pentru construirea retelei secventiale logice.

Clasificarea problemelor legate de sistemele cu stari finite

Exista trei clase de probleme des intalnite:

Analiza sistemului

Sinteza sistemului

Investigarea sistemului

Analiza

Analiza unui sistem poate fi formulata astfel: dandu-se organizarea sistemului incluzand intrarile si iesirile sa se determine comportamentul acestuia. Un sistem la care se cunosc intrarile si iesirile are solutie unica stiindu-se ca structura nu are inconsistente.

Determinarea comportamentului se poate face in mai multe moduri:

Experimental, aplicand toti vectorii de intrare si observand valorile vectorilor de iesire.

Analitic, calculand ecuatiile de intrare-iesire sau intrare-stare-iesire din structura cunoscuta a sistemului, urmata de o evaluare analitica.

Procedura de analiza poate fi impartita in doua categorii:

Ideala - componentele opereaza ideal, in care timpii de raspuns sunt neglijati.

Reala - se iau in considerare timpii de raspuns. In anumite cazuri acestia reprezinta o componenta critica.

Sinteza

Sinteza unui sistem este considerata inversa analizei. Sinteza poate fi descrisa in felul urmator: se da comportamentul sistemului logic intr-o forma corespunzatoare si se cere sa se determine structura care realizeaza comportamentul descris. Deoarece avem de-a face cu dispozitive logice procesul se numeste sinteza logica sau proiectare logica.

Sinteza unui sistem are o infinitate de solutii. Totusi, anumite constrangeri trebuie respectate referitor la tehnologii, costuri, complexitate, etc.

Definitie: Sunt date comportamentul unui sistem si o multime de module logice si se cere sa se gaseasca structura sistemului care realizeaza comportamentul prescris si contine numai modulele permise. Aceste module satisfac criteriile de performanta (cost, complexitate, putere consumata, etc.)

Scopul sintezei logice este sa gaseasca dintre toate variantele posibile structura care satisface cerintele in cea mai buna maniera posibila.

Structura propusa este apoi verificata pentru a fi siguri ca sinteza a fost facuta corect.

Investigarea

Investigarea reprezinta cea mai complexa problema referitoare la sistemele cu stari finite, fiind denumita si problema cutiei negre.

Sistemul logic este dat ca o cutie neagra pentru care organizarea si functionarea sunt necunoscute dar anumite experimente pot fi facute si inregistrate. Scopul investigarii este sa determine functionalitatea sistemului iar apoi sa propuna o ipoteza referitoare la organizarea lui.

Investigarea are loc in principal printr-o multime de experimente. Experimentele sunt folosite pentru cautarea constantelor in activitatea inregistrata.

Daca se cunosc cateva aspecte referitoare la organizarea sistemului, se pot conduce experimente pentru a obtine cunoasterea completa a functionalitatii sistemului.

Daca functionalitatea este cunoscuta se pot imagina cateva ipoteze referitoare la organizarea sa. Acest proces este foarte asemanator cu cel de sinteza logica.

Scopul cursului

Proiectarea logica este procesul de interconectare de elemente logice sau module pentru a efectua o anumita functie.

Teoria comutationala, care este baza formala a proiectarii logice, are ca scop producerea unor structuri viabile formate din elemente logice, denumite si operatori si interconexiunile dintre acestea pentru a obtine o functionare specifica.

Ultimele decenii au adus schimbari majore in practica proiectarii logice. Microprocesoarele programabile pe 16 sau 32 de biti pot inlocui circuitele logice cu software. Se poate crede ca versatilitatea microprocesoarelor a dus la scoaterea de pe piata a teoriei comutationale inlocuind astfel proiectarea logica cu programarea. Aceasta situatie nu este nici pe departe reala.

Un sistem digital nu consta numai din microprocesor . Alte circuite logice ce interfateaza microprocesorul cu lumea exterioara, sunt extrem de folosite. Mai mult decat atat, proiectarea logica a microprocesorului insusi necesita mare experienta in proiectarea logica.

In zilele noastre, odata cu cererea ca proiectarea sistemelor sa se faca cu module LSI si VLSI, aplicarea teoriilor clasice s-a schimbat radical. De exemplu, in proiectarea cu ajutorul unor module specifice are in vedere, minimizarea numarului de porti, de intrari, de tipuri de module folosite cat si numarul acestora si al interconexiunilor dintre ele.

Scopul major al acestei discipline este sa pregateasca studentii pentru tehnologiile viitoare prin explicarea modului in care teoria comutationala poate fi folosita pentru proiectarea sistemelor folosind circuite LSI si VLSI .

Metode generale de proiectare a sistemelor digitale

Metodele folosite pentru proiectarea logica au avut o evolutie dinamica in principal datorita progreselor tehnologice. Metodele initiale erau folosite pentru sistemele digitale bazate pe relee, pe cand in zilele noastre aceste metode sunt invechite. Aceste metode nu mai sunt folosite la proiectarea calculatoarelor.

Aparitia tranzistorelor si circuitelor integrate a avut un impact major asupra metodelor folosite la implementarea dispozitivelor logice . Astfel, notiunea de proiectare logica se poate redefini.

Definitie: Proiectarea logica este procesul de implementare a unui sistem cu stari finite prin folosirea anumitor dispozitive pornindu-se de la specificatiile dispozitivelor de intrare - iesire si care urmaresc un criteriu de performanta impus ( cost, complexitate, intarzieri, caldura disipata, etc. ).

Astfel, metodele folosite pentru proiectarea logica sunt dependente de tehnologiile folosite sau putem spune ca sunt corelate cu un anumit nivel al tehnologiei.

Principalele metode de proiectare a sistemelor digitale sunt :

Implementarea cu porti logice si bistabile - aceasta este ,, proiectarea clasica,, . Aceasta metoda corespunde tehnologiei SSI ( Small Scale Integration ) .

Implementarea cu module functionale, ceea ce inseamna folosirea circuitelor integrate cu functionalitate complexa la nivelul tehnologiei MSI

(Medium Scale Integration). Din aceasta categorie fac parte decodoarele, multiplexoarele, memoriile, registrele, numaratoarele, etc.

Implementarea cu dispozitive de memorie

In general, memoriile semiconductoare se clasifica in doua categorii :

a)      RAM

b)      ROM

RAM este o memorie de tip RWM ( Read - Write memory ), dar abrevierea folosita vine de la Random Acces Memory. Numele memoriei specifica faptul ca accesul la oricare dintre locatii necesita acelasi interval de timp indiferent de pozitia locatiei in memorie .

Intr-o memorie de tip ROM continutul este fix, datele gasindu-se pe suport chiar daca dispozitivul nu este alimentat ( ROM = Read Only Memory ). Procesul de selectare a datelor este de asemenea aleator. Metoda de proiectare logica cu ajutorul RAM / ROM este una foarte moderna, simpla, eficienta si flexibila ce permite realizarea unor functionalitati complexe iar pretul modulelor este di ce in ce mai redus. Nivelul tehnologic corespunde nivelului LSI ( Large Scale Integration ) sau VLSI ( Very Large Scole Integration )

4. Implementarea cu dispozitive programabile logice ( PLD - Programable Logic Devices ) . Aceasta tehnologie s-a dezvoltat incepand cu anul 1975 iar acum este reprezentata de o varietate de dispozitive ( PLA, PAL, PGA, FPGA, etc. ) . Aceste metode de proiectare logica sunt legate de tehnologiile LSI si VLSI .

5). Implementarea cu microprocesoare - aceasta este tot o metoda moderna bazata pe tehnologiile VLSI si ULSI ( Ultra Large Scale Integration ) . Termenul de microprocesor acopera un numar mare de circuite cu arhitecturi diferite dar cu aspecte comune :

a)      Sunt folosite ca si componente de baza la constructia masinilor Von Neumann care contin cel putin un ALU (Arithmetic and Logic Unit) si un CU (Control Unit) reuniunea celor doua fiind denumita CPU (Central Processing Unit)

b)      Sunt independente ca module LSI sau VLSI cel mai des realizate in tehnologia MOS.

In concluzie, un microprocesor este o unitate centrala de calcul (CPU) pe un chip. Cea de-a 5-a metoda corespunde translatiei sintezei logice de la hardware catre software. Functiile logice sunt implementate ca o secventa de instructiuni interpretate de CPU. Viteza este cel mai mare dezavantaj pentru acest tip de implementare.

Observatii :

Indiferent de ce metoda este folosita, proiectarea asistata de calculator este din ce in ce mai folosita in proiectarea logica, asigurandu-se astfel o automatizare totala a proiectarii .

Exista o corelare stricta intre diferitele metode folosite la proiectarea logica si nivelul de integrare ( SSI, MSI, LSI, VLSI, ULSI )

1) Small Scole Integration - SSI - orice modul care contine maxim 12 parti logice. Acest nivel corespunde proiectarii clasice .

2) Medium Scale Integration - MSI - orice modul care contine maxim 100 parti logice. Din aceasta categorie fac parte registrele, numaratoarele, multiplexoarele, decodificatoarele, comparatoarele, etc.

3) Large Scale Integration - LSI - orice modul care contine maxim 1000 parti logice. Din aceasta categorie fac parte memoriile, unitatile aritmetice si logice complexe, etc.

4). Very Large Scole Integration Ultra Large Scale Integration - ULSI - orice modul care contine peste 1000 de parti logice. Din aceasta categorie fac parte microprocesoarele,modulele de memorie foarte mari, etc.

Nivele in procesul de proiectare logica

Utilizarea tehnicilor digitale este larg raspandita in aproape toate stiintele ingineresti. Disponibilitatea dispozitivelor integrate la costuri reduse, care sunt capabile sa proceseze si sa memoreze cantitati mari de date la viteze foarte mari a condus la dezvoltarea unei game largi de sisteme atat profesionale cat si de uz casnic. Capabilitatile unor astfel de echipamente au crescut exponential in timp ce costul s-a redus constant.

Totusi, capabilitatea de fabricatie de dispozitive VLSI necesita proiectanti capabili sa lucreze la diverse nivele si anume sa proiecteze structura sistemului in ansamblu format din circuite complexe pana la proiectarea la nivelul cel mai de jos a componentelor individuale.

La fiecare nivel, proiectantul are nevoie de un suport teoretic solid care sa ajute la analiza si sinteza circuitelor impreuna cu experienta obtinuta din proiectarile anterioare. Uneltele de tip CAP sunt din ce in ce mai folosite pentru efectuarea operatiilor de rutina care erau efectuate manual,dar, ca orice unealta, este nevoie de operatori experimentati pentru a obtine rezultate satisfacatoare. Astfel, procesul de proiectare logica poate fi impartit pe urmatoarele nivele:

1) Primul nivel este nivelul algoritmic. Acest nivel este cunoscut si sub numele de nivelul sistem. Specificatiile sistemului digital sunt definite intr-o forma generalizata abstracta ca o multime de operatori de nivel inalt care ruleaza o serie de operatii pe anumite structuri de date. Acest nivel este cunoscut si sub numele de proiectare sistemica .

2). Al doilea nivel este nivelul functional. Aici arhitectura sistemului digital este explicita, ceea ce inseamna ca operatiile logice sunt specificate ca si componente care sunt la randul lor definite prin functiile de intrare - iesire fara a fi interesati de detaliile structurii interne. La acest nivel sunt descrise interconectarile intre operatori, proiectantul operand cu registre, numaratoare, multiplexoare, decodoare sau alte blocuri functionale. Acest nivel este cunoscut si sub numele de nivelul arhitectural .

3)Al treilea nivel corespunde proiectarii structurale sau proiectarii logice. La acest nivel, functiile sunt implementate din componente logice primitive ca: parti logice, bistabile, comutatoare, zone tampon, etc.

4)Al patrulea nivel corespunde nivelului fizic sau nivelului circuit. Circuitul logic este implementat folosindu-se componente reale ceea ce duce la aparitia unor probleme referitoare la consumul de putere, viteza de operare, intarzierile, etc. Nivelele de proiectare sunt ilustrate in tabelul urmator, in care sunt specificate metodele folosite la fiecare nivel. Granitele dintre nivele pot varia deoarece multe dintre tehnici sunt folosite la o gama larga de nivele.

Proiectantul trebuie sa lucreze la un nivel inalt de abstractizare ceea ce reflecta tendinta continua catre proiecte din ce in ce mai mari si mai complexe. Metodele teoretice de proiectare impreuna cu uneltele corespunzatoare fiecarui nivel formeaza principalul obiectiv al prezentului curs.

Produsul procesului de proiectare este un sistem care respecta specificatiile in ceea ce priveste functionalitatea implementata. Aceasta inseamna ca costul total al proiectarii, construirii si testarii vor fi minime. Procesul de proiectare logica se ocupa de translatia de la nivelul functional la cel structural, beneficiindu-se astfel de o gama larga de metode pentru analiza si sinteza circuitelor logice.

Relatia dintre nivelele de abstractizare descrise in contextul procesului de proiectare sunt aratate in figura urmatoare. Diagrama arata ca iteratiile necesare pentru investigarea sau revizuirea proiectarii datorate schimbarii cerintelor sau descoperirii de erori facute in stadiile anterioare. Desi proiectarea este iterativa, proiectarea sistemului implica si activitati concurente. De exemplu, o descriere functionala de nivel inalt poate include un numar de componente care pot fi proiectate independent, in timp ce procedurile de test si documentatia aferenta sunt realizate in timpul fazelor de proiectare arhitecturala si detaliata, componentele care au fost proiectate sunt descrise, create, si asamblate .

Un numar de strategii au fost propuse referitor la ordinea in care componentele sunt luate in considerare . Dintre cele mai cunoscute strategii amintim BOTTOM-UP (de jos in sus), TOP-DOWN (de sus in jos), si unele hibride cum ar fi "componentele critice primele".

Proiectarea BOTTOM-UP incepe de la o multime existenta de componente primitive, sistemul fiind construit prin combinarea succesiva a acestor componente.

Proiectarea TOP-DOWN foloseste un proces de descompunere pentru a rafina specificatiile definind fiecare componenta in functie de subcomponente pana cand se ajunge la componente primitive. O astfel de strategie are avantajul ca detaliaza structura generala si arhitectura sistemului inainte de aparitia detaliilor de proiectare.

In cazul proiectarii TOP-DOWN, proiectantul are la dispozitie multimea componentelor primitive disponibile iar acest lucru influenteaza procesul de descompunere .

In cazul strategiei BOTTOM-UP, poate fi greu de estimat performanta sistemului si nici macar daca se vor atinge toate cerintele . Cele mai multe strategii de proiectare contin elemente din ambele abordari cu tehnici TOP-DOWN pentru proiectarea arhitecturala si cu tehnici BOTTOM-UP pentru implementare.

Indiferent de strategii, se pleaca de la specificatii iar unele dintre acestea pot fi chiar critice, in sensul ca trebuiesc indeplinite indiferent de costul proiectarii.

7. Proiectarea asistata de calculator (CAD-Computer Aided Design )

Proiectarea asistata de calculator are ca scop folosirea calculatoarelor digitale pentru proiectarea sistemelor. Initial, termenul de Proiectare asistata de calculator a fost folosit pentru descrierea aplicatiilor care faceau orice proiectare ; in zilele noastre, termenul are o specificatie mai exacta si se refera la sisteme interactive in care proiectantul si calculatorul lucreaza impreuna intr-o relatie foarte stransa . Proiectantul are totusi rolul principal, el asigurand controlul intregului proces. Folosind metodele CAD, inginerul are posibilitatea sa exploreze idei si tehnici noi, rezultatele fiind rapid obtinute in forma grafica.

In acest fel, un proiectant experimentat poate intelege rapid problema in acelasi timp capatand o buna experienta referitoare la diversele tehnici de proiectare. Pe langa analiza si sinteza sistemului, folosirea CAD permite generarea documentatiei si a testelor necesare.

Proiectarea automata completa este totusi o tehnica disponibila. Aceasta conduce proiectantul prin toate stadiile de dezvoltare si productie, producand automat documentatia, cablarea si programul de revizii. In multe cazuri o baza de date este folosita pentru pastrarea tuturor informatiilor relevante referitoare la proiectare si productie, componente, etc. pentru a asigura o schema CAD complet integrata.

Calculatoarele din zilele noastre, reprezinta unele dintre cele mai mari progrese tehnologice ale societatii moderne. Astfel, au aparut metodele CAD folosite pentru obtinerea performantelor necesare. Totusi, metodele CAD sunt aplicate cu precadere in stadiul de productie in timp ce sistemul initial si procesul de proiectare logica sunt abordate partial. Nu sunt inca disponibile pachete pentru sinteza logica ca si programul de proiectare. Singura unealta software de proiectare care a fost general acceptata este simulatorul logic; acesta permite proiectantului sa modeleze si sa evalueze circuitele la nivel de poarta sau la nivel de registru .

Proiectarea automata are ca scop principal reducerea costurilor si a timpului de executie cerute in mod normal la realizarea sistemelor digitale complexe . In general, automatizarea proiectarii este restrictionata la faza de trecere de la specificatiile initiale ale sistemului la programarea logica, completate cu detalii referitoare la detaliile de fabricatie. Desi proiectarea automata completa cuprinde multe functionalitati asa cum poate fi vazut in figura urmatoare, scopul principal este eliminarea procedurilor repetitive manuale. Schema generalizata este realizata in jurul unei baze de date comuna care comunica direct cu fiecare pachet al sistemului CAD . Comunicarea intre diverse pachete ale CAD este de asemenea posibila. In general, un pachet poate accesa baza de date pentru obtinerea de date de intrare relevante sau poate obtine aceste date direct de la alte pachete; rezultatele sunt totdeauna memorate in baza de date.

Date de intrare externe pot aparea in principal de la proiectantii care creeaza initial multimea de module care vor fi folosite, constrangerile de intrare si iesire, costurile sau alti parametri relevanti procesului de proiectare. Alte tipuri de date de intrare de la proiectant includ descrierea initiala a sistemului la nivel conceptual si functional.

Toate aceste operatii de intrare trebuie executate sub controlul sistemului CAD care are controlul general al sistemului.

Avantajele automatizarii proiectarii sunt :

Proiectare rapida si fara erori a sistemelor digitale complexe cu multe variabile.

Diverse variante de proiectare pot fi evaluate prin schimbarea parametrilor ( module, dimensiuni, criterii de minimizare, etc. ).

Folosirea unei baze de date comune permite generarea automata a documentatiei sistemului pentru toate studiile de proiectare.

Cablarile, placile si alte date de fabricatie, pot fi obtinute automat si modificate .

Modificarea proiectelor se poate realiza usor si fara riscul introducerii de erori.

Pachetele de simulare permit proiectarii logice sa fie evaluata, erorile putand fi corectate inainte de implementarea finala.

Se permite folosirea algoritmilor fara sa fie nevoie de cantitati mari de calcule manuale sau cunostinte teoretice superioare.

Generarea automata a erorilor obtinute la testare.

Pachetele CAD sunt disponibile pentru cele mai multe functii de la sinteza logica la analiza si implementare, plasare si interconectare, generare de teste. Documentatia este disponibila in toate stadiile, producand feedback pentru proiectant si informatii pentru producator.

In contextul uneltelor CAD, se disting urmatoarele categorii :

Unelte de sinteza logica: au ca scop principal translatarea descrierii functionale in una structurala de nivel jos, din care se poate implementa circuitul. Datele de intrare pot fi tabele de adevar, tabele de stari sau expresii booleene, in timp ce la iesire se obtin date ce depind de tehnologii, cum ar fi liste de cabluri, liste de retele ce contin componente specifice sau programe pentru dispozitive PLD.

Scopul sintezei logice este sa genereze circuite logice optime din specificatiile functionale.

Unelte de sinteza logica de nivel inalt. Aceste unelte se adreseaza problemelor de transformare a specificatiilor abstracte de nivel inalt in specificatii detaliate. Produsul unei astfel de unelte poate fi transformat prin sinteza logica in produsul finit. In zilele noastre exista o clasa de unelte de proiectare automata cunoscute sub numele de compilatoare cu silicon, care au ca scop specific proiectarea fizica a componentelor VLSI. Aceste unelte au ca scop compactarea schemelor si asezarea dispozitivelor semiconductoare.

Motivatia principala a dezvoltarii si folosirii proiectarii automate este reducerea timpului si costurilor de proiectare.

In figura urmatoare sunt prezentate componentele unei unelte de sinteza logica :

In concluzie, proiectarea unui sistem CAD implica gasirea de solutii pentru urmatoarele probleme :

a)      Selectarea si implementarea unei structuri de date adecvate pentru reprezentarea modelelor si a parametrilor de proiectare.

b)      Dezvoltarea de algoritmi care opereaza pe structura de date impreuna cu metodologia de proiectare adecvata.

c)      Obtinerea unei interfete viabile, cu o specificare interactiva realista a problemei si cu facilitati de editare.