Bazele logice ale proiectării calculatoarelor

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 v1(t), v2(t), …

Din punct de vedere matematic, valoarea acestor functii în timp nu este relevanta. Relatiile dintre functii au însa 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 = { x[t0,t1],z[t0,t1]}, unde

1. t0, t1  ( - , +)

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 înseamna 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 = {(X, Z)}.

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

D {A} = {X / (X, Z)  A}

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

R {A} = {Z / (X, Z)  A}

Reprezentarea oricarui obiect abstract este:

Definitie: Fie A1, A2, … o multime de obiecte abstracte si se presupune o anume interconectare a obiectelor în 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 în felul urmator:

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

Exemplu: Consideram doua obiecte abstracte A1 si A2 în care iesirea lui A1 este conectata la intrarea lui A2.

1

Constrângerile sunt urmatoarele:

S reprezinta sistemul iar XS si ZS reprezinta intrarea si iesirea acestuia. În general, dependenta intrare-iesire nu este unic determinata, ceea ce înseamna 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 într-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 în timp discret si pentru care valorile perechilor intrare-iesire si stare interna se afla într-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.

2. Sisteme cu stari finite ( SSF )

Definirea automatelor finite fara memorie

Consideram doua multimi finite nevide,

X = {x1, x2, …xk}

Z = {z1, z2, …zl}

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, formându-se astfel un vector de intrare de dimensiuni n.

Xi = ( xi1, xi2, …, xin ), unde xik  X, k  [1,n]

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

Zj = ( zj1, zj2, …, zjm ), unde zit  Z, t  [1,m]

Functionarea dispozitivului consta în transformarea vectorului de intrare Xi în vectorul de iesire Zj.

Luând în 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 { A } = kn

R { A } = lm

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