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.

Fondamenti Informatica II - Lez. 05 18.04.2006 3

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.

Fondamenti Informatica II - Lez. 05 18.04.2006 4

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.

Fondamenti Informatica II - Lez. 05 18.04.2006 5

Segnali a livelli e ad impulsi

Fondamenti Informatica II - Lez. 05 18.04.2006 6

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;

Fondamenti Informatica II - Lez. 05 18.04.2006 7

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

Fondamenti Informatica II - Lez. 05 18.04.2006 8

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’}.

Fondamenti Informatica II - Lez. 05 18.04.2006 9

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.

Fondamenti Informatica II - Lez. 05 18.04.2006 10

Modello di rete sequenziale sincrona (1/3)

Fondamenti Informatica II - Lez. 05 18.04.2006 11

Modello di rete sequenziale sincrona (2/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

Fondamenti Informatica II - Lez. 05 18.04.2006 12

Modello di rete sequenziale sincrona (3/3)

Fondamenti Informatica II - Lez. 05 18.04.2006 13

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.

Fondamenti Informatica II - Lez. 05 18.04.2006 14

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 “/”.

Fondamenti Informatica II - Lez. 05 18.04.2006 15

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.

Fondamenti Informatica II - Lez. 05 18.04.2006 16

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”

Fondamenti Informatica II - Lez. 05 18.04.2006 17

Esempio flipper (2/3)

Fondamenti Informatica II - Lez. 05 18.04.2006 18

Esempio flipper (3/3)

Fondamenti Informatica II - Lez. 05 18.04.2006 19

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.

Fondamenti Informatica II - Lez. 05 18.04.2006 20

Esempio sequenza di tre 1 (2/4)

Fondamenti Informatica II - Lez. 05 18.04.2006 21

Esempio sequenza di tre 1 (3/4)

Fondamenti Informatica II - Lez. 05 18.04.2006 22

Esempio sequenza di tre 1 (4/4)

Fondamenti Informatica II - Lez. 05 18.04.2006 23

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.

Fondamenti Informatica II - Lez. 05 18.04.2006 24

Esempio Ascensore (2/3)

Fondamenti Informatica II - Lez. 05 18.04.2006 25

Esempio Ascensore (3/3)

Tabella di Flusso