Proiectarea unei mașini algoritmice de stare

Tema proiect nr.15

O masina algoritmica de stare (ASM) este descrisa dupa cum urmeaza:

- Sunt identificate 4 stari stabile distincte. Acestea sunt notate cu: 1 (cod: 00); 2 (cod: 01); 3 (cod:11); 4( cod: 10).

- Sunt identifiate 2 intrari (A,B), 2 iesiri neconditionate (K,L) si o iesire conditionata (N).

- Starea 1 genreaza iesirea noconditionata K, in timp ce starile 2 si 3 genereaza iesirea neconditionata L.

- Iesirea conditionata N este generata atunci cand are loc tranzitia din starea 1 in starea 2 si cand e indeplinita conditia B=0.

- Tranzitia de la starea 1 la starea 2 este conditionata de B=0.

- Tranzitia de la starea 1 la starea 3 este conditionata de B=1 si A=0.

- Sunt identificate tranzitii neconditionate de la 3 la 1, de la 4 la 3 si de la 2 la 4.

Se cere sa se:

a) Deseneze o organigrama ASM pentru masina de stare descrisa mai sus.

b) Construiasca tabelul de stare asociat organigramei ASM.

c) Proiecteze masina de stare utilizandu-se bistabili de tip D. sa se implementeze Generatorul Noii Stari (GNS) utilizandu-se un singur etaj de multiplexoare iar pentru implementarea LCE se vor utiliza porti logice. Este necesara minimizarea lui GNS utilizandu-se tehnica VID (variabile incluse in diagrama). Sa se deseneze o schema de conexiune/electrica/de montaj a ASM-ului complet, aratandu-se clar conexiunile necesare la intrarile de date ale fiecarui multiplexor, precum si semnalele aplicate pe intrarile lor de selectie. Se presupune ca toate iesiriel sunt instantanee si ca distorsiunile/perturbatiile/glitches semnalelor sub forma de impuls pot fi tolerate( cu alte cuvnite schema nu prezinta hazard).

d) Proiecteze o masina de stare corespunzatoare care sa implemeteze sistemul digital/numeric folosindu-se bistabili de tip D si FPLA 8x16x8; se va utiliza de asemenea maparea directa a cailor de legatura. Este furnizata o schema de conexiune pentru FPLA, care va fi utilizata pentru a se indica programarea dispozitivului. Se vor inscriptiona clar toate intrarile si iesirile FPLA-ului si se va indica ce se va face cu intrarile, iesirile si termenii produs neutilizati. Se va dauga orice structura logic suplimentara necesara la schema de conexiune a FPLA-ului, pentru a se obtine schema logica completa a masinii.

a) Organigrama ASM

O organigrama ASM combina elementele descrierii traditionale prin diagrama de stare a unui AS cu schematizarea activitatilor de procesare de tip calculator asigurandu-se astfel realizarea unui instrument util pentru proiectare. Un algoritm de comanda respectiv conducerea unui proces transpus intr-o diagrama ASM prezinta cele 5 caracteristici esentiale definite de Knuth si anume : finititudine, determiniSm, intrari, iesiri si eficienta.

Elementele structurale ale descrierii prin organigrama ASM sunt :

1. Starea – este unicul element fundamental al organigramei care introduce in mod explicit variabila timp si pe care o asociaza in mod discret etapelor.

2. Decizia – este un element de ramificatie dependent de una sau mai multe intrari.

3. Iesirea conditionata – elementul de control sau de comanda a procesului care descrie alte iesiri decat cele corespunzatoare starii care depind de una sau mai multe intrari.

Se numeste bloc ASM o structura care consta dintr-un singur element de stare si o retea de elemente de decizie si de iesiri conditionate, reteaua amintita fiind obtinuta prin interconectarea celor 3 elemente de baza ale organigramei.

Constructia organigramei :

- fiecare cale de iesire dintr-o stare ( bloc ASM ) trebuie sa conduca doar la o singura stare dintr-un bloc ASM ulterior. Structura de decizie a blocului nu trebuie sa indice doua sau mai multe cai de iesire simultane pentru orice secventa de intrari.

- deoarece masina de stare reala se poate afla la un moment dat intr-o singura stare, o organigrama ASM care sa specifice doua sau mai multe stari ulterioare va fi fara sens.

- niciodata nu se imparte o iesire de la o stare intre doua sau mai multe cai de legatura fara sa se utulizeze un simbol grafic de decizie.

În tabela ASM se reprezintă în mod sistematic în funcţie de intrări şi de stările prezente, starea internă următoare şi ieşirile corespunzătoare (care pot fi condiţionate sau necondiţionate). Fiecare linie din tabel reprezintă o conexiune de stare. Fiecare coloană a stării următoare, precum şi fiecare coloană a ieşirilor din tabelul ASM poate fi considerată o problemă de logică combinaţională care are ca intrări variabile de intrare propriu-zise şi variabilele de stare pentru starea prezentă.