Articolo pubblicato sul n. 65 di MCmicrocomputer (Edizioni Technimedia Srl - Roma) nel luglio 1987 Reti logiche sequenziali Dopo la scherzosa pausa del numero scorso, riprendiamo a parlare di informatica, nella fattispecie di reti logiche. Questo mese sarà la volta delle reti sequenziali, diverse da quelle trattate due mesi orsono essendo oggetti di natura non statica. Ogni output non dipende funzionalmente solo dall'input corrente, ma dalla "storia" di input via via elaborati.
Riassunto
Una rete logica combinatoria, vista dall'esterno, appare come una scatoletta dotata di terminali di ingresso e terminali di uscita. Applicando ai terminali di ingresso combinazioni di valori binari, otterremo ai terminali di uscita altri valori binari. Come già ribadito due numeri fa, né più né meno che una funzione binaria: applicando in ingresso cento volte lo stesso input otterremo cento volte lo stesso output, da cui la staticità delle reti logiche combinatorie. La prima fase della realizzazione di una rete, è la costruzione della cosiddetta tabella di verità: nient'altro che una tabella in cui annotiamo per ogni input quale sarà il risultato. Da questa direttamente, o tramite le mappe di Karnaugh, si ricostruisce la funzione logica corrispondente, costituita da somme di prodotti o prodotti di somme (logiche) a seconda del metodo usato.
Per la realizzazione fisica della rete logica, una volta
ottenuta la funzione corrispondente, si utilizzano
componenti elettronici AND, OR, NOT. Ricordiamo che il
componente AND esegue il prodotto logico dei suoi due input,
l'OR la somma logica, il NOT la complementazione. A questo
punto, il passaggio da funzione a rete è più che mai
immediato:
Descrizione generale
A differenza delle reti combinatorie che hanno un
comportamento puramente funzionale, le reti sequenziali
dispongono di un proprio stato interno. L'output di una rete
sequenziale dipende sia dal dato di ingresso che dallo stato
interno. Quest'ultimo dallo stato interno precedente e dal
dato in ingresso.
Al colpo successivo, istante t1, l'input X1 e lo stato S1 generano Y1 e S2... all'istante t2, S2 e X2 generano Y2 e S3... e così via, sequenzialmente. Da notare che lo stato interno, variando in funzione della storia degli input, non fa altro che tenere traccia di tutti gli input finora elaborati. Per chi ci ha seguiti nella teoria della computabilità aggiungiamo che una rete sequenziale non è altro che un automa a stati finiti deterministico. Chi non ci ha letto l'articolo in questione ignori la frase precedente. Riassumendo, una rete sequenziale fornisce sequenze di output in funzione di sequenze di input: per la precisione ogni output è funzione di tutti gli input finora elaborati più naturalmente lo stato iniziale (quello con cui facciamo partire la rete). Gli input come al solito saranno parole binarie formate da n bit, così come gli stati interni (non dimentichiamo che stiamo parlando dei mattoni di un calcolatore) in generale di lunghezza diversa. L'insieme degli input in numero di 2 alla n costituiranno il cosiddetto alfabeto di ingresso, mentre per gli stati parleremo semplicemente di insieme di stati.Ad esempio la nostra rete potrebbe avere 3 morsetti di ingresso (alfabeto di ingresso formato da 8 elementi) e 4 stati interni codificati con parole di due bit l'uno (come noto con due bit codifichiamo 4 valori).
L'interno
In figura 3 potete ammirare una rete sequenziale vista
dall'interno. Si riconoscono tre elementi: due reti
combinatorie
(colpo di scena!) e un elemento di ritardo
contrassegnato con una lettera delta.
All'istante iniziale nell'elemento delta è conservato lo
stato iniziale e quindi questo è presente anche agli
ingressi di S e Y. Non appena arriva il primo input le due
reti combinatorie (tenete sempre sott'occhio la figura 3)
elaborano i loro risultati fornendo Y l'uscita vera e
propria ed S il nuovo stato interno (inviandolo a delta).
Arrivato il secondo input il ciclo si ripete finché ci sono
dati da elaborare. Notare che se gli ingressi erano ad n In figura 4 è mostrata una visione meno "esplosa" di una rete sequenziale: le due reti da n e m bit di ingresso possono essere viste come un'unica rete in cui m linee di uscita sono riproposte in ingresso attraverso l'elemento di ritardo delta. è comunque esattamente la stessa cosa.
Il modello di figura 3 è detto Modello di Mealy dal nome
del suo autore: in figura 5A è sono mostrate le relazioni
esistenti tra uscite, ingressi e stati interni di una
generica rete sequenziale secondo tale modello. In figura 5B
abbiamo le relazioni relative al modello detto di Moore: in
questo casi le uscite sono funzione del solo stato interno,
il quale però è in ogni caso funzione sia dello stato
interno precedente che del dato in ingresso. Ciò implica
essenzialmente che la sequenza delle uscite è traslata
Tabelle di flusso
Se per descrivere le reti combinatorie era sufficiente
scrivere la corrispondente tabella di verità, per le reti
sequenziali adopereremo un metodo assai simile detto della
tabella di flusso. Come era da immaginare, per la
descrizione, non potremo non tenere conto della struttura
interna della rete ovvero che esiste una parte S, una parte
Y e c'è di mezzo il tempo. In figura 6A
abbiamo messo la
tabella di flusso di una semplice rete ad un ingresso, tre
stati interni e due uscite. L'alfabeto di ingresso sarà
dunque formato da due simboli, quello di uscita da 4 di cui
solo 3 (per noi) significativi. Per stendere una tabella di
flusso dovremo indicare per ogni simbolo di ingresso e stato
interno al tempo t quale sarà l'uscita
Grafi
Un altro modo per descrivere una rete sequenziale, molto più intuitivo e immediato da leggere e "percorrere", è quello di rappresentare un bel grafo del comportamento. I nodi rappresenteranno gli stati interni, gli archi le transizioni di stato, etichettate dal dato in ingresso e dall'output generato. In figura 6B abbiamo rappresentato il grafo della stessa rete di figura 6A. Lo stato iniziale è stato cerchiato due volte per poterlo riconoscere. Proviamo a compiere la stessa storia di input dell'esempio precedente. Da S1 (questa volta occhio alla figura 6B) con input X1, seguendo la freccia corrispondente, "approdiamo" in S3 con output Y1: l'arco uscente da S1 etichettato X2Y1 dice proprio questo. Dal pallottolo S3 con input X1 (stiamo effettuando lo stesso percorso di prima) finiamo in S2 rilasciando l'output Y2. Eccetera, eccetera.
Realizzazione
Una volta "chiarito il concetto", la realizzazione di una rete sequenziale è assai banale. Si tratta infatti di realizzare semplicemente le due reti combinatorie S e Y e il gioco è fatto. Dalla tabella di flusso possiamo facilmente ricavare le due tabelle di verità corrispondenti che non sono altro che la prima e la seconda colonna combinate una volta con la terza, una volta con la quarta. Per quanto riguarda la loro realizzazione, mappe di Karnaugh e implicanti stanno lì ad aspettare di essere usate... e poi ormai siamo diventati bravissimi...
Facciamo un esempio
Come ben sapete 1+1 fa 10. In binario, naturalmente! Per l'esattezza fa 0 col riporto di 1. 1+1+1 fa 11, o meglio, 1 col riporto di 1. Una volta imparate queste due semplici regolette saremo in grado di fare la somma binaria, cifra per cifra, di due qualsiasi numeri binari. Vediamo se siamo in grado di far eseguire la somma ad una rete sequenziale. Ovviamente numeri di lunghezza qualsiasi. Provate a pensarci un po' prima di continuare a leggere.
In figura 8B troviamo il grafo corrispondente: notare la
simmetria dell'insieme... poi dicono che la matematica è
disordine! Ad ogni modo, i due stati S0 e S1 sono proprio
"riporto di zero" e "riporto di uno", mentre le etichette
sugli archi riportano i dati in ingresso e il valore in
uscita. Ad esempio da S0
Da notare che per iniziare una nuova somma, ed essere sicuri che lo stato interno sia S0 (la somma precedente potrebbe aver sporcato tale stato) è sufficiente eseguire una somma 0+0 ed ignorare il risultato: in tutti i casi, infatti, non si genererà riporto lasciando dunque lo stato interno in S0. In figura 8C abbiamo riportato le due mappe di Karnaugh per l'uscita Y e per lo stato interno successivo: la costruzione di queste discende direttamente dalla tabella di flusso di figura 8A. I più attenti avranno notato che per la Y non ci poteva andare peggio: sia gli uno che gli zeri sono così sparpagliati che non riusciamo ad evidenziare un solo implicanti da più di un 1 o uno 0: in casi come questi, Karnaugh ci aviuta ben poco. Nel caso della S, di contro, possiamo evidenziare ben tre implicanti "da due" quindi l'espressione equivalente appare abbastanza ridotta: sia questa che quella della Y potete trovarla in figura 8D. Per questo mese è tutto... a fra trenta giorni. Impaginato originale...
Articolo pubblicato su www.digiTANTO.it - per ulteriori informazioni clicca qui |