Fondamenti di Informatica II Ingegneria Informatica...

Fondamenti di Informatica IIIngegneria Informatica e Biomedica

I anno, II semestreA.A. 2005/2006

Prof. Mario CannataroUniversità degli Studi “Magna Graecia”di Catanzaro

Sintesi di reti sequenziali1/2

Fondamenti Informatica II - Lez. 05 18.04.2006 2

Reti Combinatorie vs Reti Sequenziali

Reti Combinatorie: l’utilizzo è limitato alla realizzazione di funzioni booleane in cui il valore dei segnali in uscita al tempo t è in funzione del valore dei segnali di ingresso al tempo t-r per l’elaborazione dei segnali. Il ritardo r non influenza il funzionamento logico della rete. Le Reti Combinatorie non hanno necessità di avere una memoria.Reti Sequenziali: sono le reti logiche che esplicano tale funzione di memoria, infatti il valore dei segnali in uscita della rete dipendono da tutti i valori dei segnali di ingresso da t=0 al tempo t-r dove r è sempre il ritardo della rete.


Concetto di memoria

Per memoria si intende la capacità di tenere traccia dell’evoluzione passata (ovvero degli ingressi precedenti) nella determinazione dell’uscita al tempo t.La storia passata viene riassunta in una variabile detta stato. La rete può ricordarsi un numero finito di eventi, quindi dovrà ripartire le sequenze di ingresso in un numero finito di classi, e memorizzerà la stessa informazione per tutte le sequenze di una classe.


Rete sequenziale

In sostanza le reti sequenziali sono formate da reti combinatorie in cui alcune uscite sono riportate per feedback (anelli di reazione, o semplicemente anelli) in ingresso.


Segnali a livelli e ad impulsi


Funzionamento a livelli o ad impulsi

Parleremo, in accordo con la terminologia elettronica, di due famiglie di segnali:

Segnali a livelli: questi segnali si mantengono costanti per un tempo sufficientemente lungo, fino a quando non si verifica una modifica del valore logico.

Segnali ad Impulsi: questi segnali rappresentano i valori logici attraverso dei picchi di breve durata che rappresentano l’1, con assenza di impulso che rappresenta lo 0;


Modello generale di reteRappresentiamo una rete sequenziale attraverso il seguente modello di HUFFMAN.


Formalizzazione della rete sequenzialeLa rete R ha n varibili d’ingresso {X1, X2,..., Xn} ed m variabili d’uscita {Z1, Z2 ,…, Zm}.Come risulta chiaro in tale modello:

- Le uscite della rete sequenziale {Z1, Z2 ,…, Zm} sono funzione sia degli ingressi esterni {X1, X2,..., Xn}, sia dello stato presente {q1, q2,..., qk}, rappresentato negli elementi in memoria;

- Lo stato successivo di una rete sequenziale {q1’, q2’,..., qk’} degli elementi di memoria è a sua volta funzione degli ingressi esterni, sia dello stato presente.

Quindi abbiamo definito: - stato interno (stato): insieme dei valori {q1, q2,..., qk}; - prossimo stato interno: insieme dei valori {q1’, q2’,..., qk’}.


Problemi del modello

Il modello presentato nella figura precedente funziona con segnali a livelli che devono variare uno solo per volta.Una rete con k anelli ha al più 2k stati interni; una rete con un

numero nullo di anelli ha 20 stati, ed è una rete combinatoria.

Una prima classificazione che possiamo fare di queste reti è la seguente:

- Reti Asincrone: il loro comportamento è definito in qualsiasi istante (modello presentato in precedenza);

- Reti Sincrone: il loro comportamento è definito ad intervalli discreti di tempo.


Modello di rete sequenziale sincrona (1/3)



L’uso di un flip-flop Fc (carica il valore di F a ogni impulso c) permette di disaccoppiare i valori sulle variabili d’anello dalle variazioni sulle variabili d’ingresso. Questo significa che il valore dello stato interno rimane costante per un tempo “sufficientemente grande” da permettere la variazione degli ingressi. Nella rete per fissare uno stato iniziale delle variabili d’anello è possibile inserire un selettore come si può osservare nella figura che segue


Automa a stati finiti

Per rappresentare il comportamento della rete andiamo ad utilizzare l’Automa a stati finiti. Un Automa ècaratterizzato dai diversi stati in cui si può venire a trovare, dai possibili ingressi, dalle possibili transazioni e dalle possibili uscite.Abbiamo pertanto:

- S = {S1, S2 ,…, Sn}, insieme degli stati interni; uno di essi è lo stato iniziale;

- X = {X1, X2 ,…, Xm}, insieme degli stati di ingresso, ovvero dei segnali applicati dall’esterno;

- Z = {Z1, Z2 ,…, Zh}, insieme delle possibili uscite.


Diagrammi degli stati

Un diagramma degli stati, è un grafo orientato, composto da h nodi, tanti quanti sono i possibili stati; da ognuno di questi nodi partono p archi orientati sui quali è indicato tale configurazione e lo stato di uscita separati dal simbolo “/”.


Tabella di flusso

Ad ogni riga corrisponde uno stato interno Si, ad ogni colonna uno stato di ingresso Xj. In una casella Si, Xj con 1<=i<=h e 1<=j<=p èspecificato il prossimo stato interno e lo stato di uscita.


Esempio flipper (1/3)

Immaginiamo di avere un flipper in cui la pallina rimane sempre in gioco. Tale flipper ha due buche B1 e B2 e due lampadine L1 ed L2. Una lampadina si accende nel momento in cui si manda la pallina nella buca corrispondente. Se si accendono entrambe le lampadine compare sullo schermo del flipper la scritta “WOW”


Esempio sequenza di tre 1 (1/4)

Immaginiamo di avere una rete sequenziale con un morsetto d’ingresso X ed un morsetto d’uscita Z. Il valore di Z è 1 solo quando in ingresso su X abbiamo ricevuto per almeno tre volte consecutive un 1.


Esempio Ascensore (1/3)

Un ascensore di un palazzo a due piani accetta la richiesta del piano di destinazione (terra, 1, 2) e restituisce lo spostamento desiderato (su, giù, fermo). Si tratta di un automa in cui S={Pt, 1P, 2P}; I={T, 1, 2} possibilità offerte dalla pulsantiera; U={Su, Giù, Fermo} spostamenti dell’ascensore.



Tabella di Flusso

Fondamenti di Informatica II Ingegneria Informatica...

Documents

Transcript of Fondamenti di Informatica II Ingegneria Informatica...