Organizzazione
Logica di un Computer
Proposta di Lavoro N° 1 (sistema formato da lampada interruttore)
Proposta di Lavoro N° 2 (automa che rileva tre uno consecutivi)
Con il termine automa s’intende un qualunque dispositivo, un qualunque oggetto, che esegue da se stesso un particolare compito, sulla base degli stimoli od ordini ricevuti.
Sono così esempi di automi una lavatrice, un distributore automatico di bibite, un interruttore, una calcolatrice tascabile,...
è possibile studiare un automa da due punti di vista: da un punto di vista tecnico ci s’interessa dei suoi componenti materiali, meccanici o elettronici, e dei suoi principi fisici che ne rendono possibile il funzionamento; da un punto di vista matematico c'interessa invece la "logica" del suo comportamento e l’automa è perciò visto come un oggetto astratto "capace" di eseguire qualche compito.
Ad esempio, due automi capaci di eseguire un’addizione sono l’automa uomo e l’automa calcolatrice, molto diversi da un punto di vista tecnico-fisico, ma che si comportano nello stesso modo di fronte a due numeri da addizionare.
I grafi e le matrici sono due modi, equivalenti, di rappresentare il comportamento di un automa.
Il grafo, chiamato diagramma degli stati, ha come nodi gli stati possibili dell’automa; gli archi rappresentano le relazioni di passaggio da uno stato all’altro, secondo il particolare input.
La matrice, chiamata tabella di verità, è una tabella in cui ogni casella specifica qual è il successivo stato e l’output dell’automa se esso si trova in un determinato stato e riceve un certo input.
Un distributore automatico di bevande dà una lattina quando s’inseriscono due monete da 500 lire.
Quali sono gli input e gli output di quest'automa?
Quali sono i possibili stati?
Il diagrammi degli stati è il seguente:
Nell’arco che va dallo stato di "in attesa" allo stato di "pronto" la scrittura "moneta/lattina" indica che, in corrispondenza dell’input "moneta" è fornito l’output "lattina". Come si vede, non sempre un automa fornisce un output.
La tabella di verità è la seguente:
| Input Stati | SPENTO | PRONTO | IN ATTESA |
| moneta | SPENTO | IN ATTESA | PRONTO/lattina |
Gli stati di un automa rappresentano i suoi stati di memoria; un automa, infatti, si trova in uno o in un altro stato secondo ciò che è successo in precedenza. Secondo lo stato in cui si trova e dell’input che riceve, l’automa stabilisce il suo comportamento, passando in un nuovo stato ed eventualmente fornendo un output:
(stato, input) ® (nuovo stato, output).
Gli automi che esamineremo sono tutti automi con memoria limitata, e comunque finita poiché hanno un numero finito di stati: sono chiamati automi a stati finiti.
Più precisamente definiamo automa a stati finiti un sistema dinamico, discreto ed invariante, in cui gli insiemi d’ingresso, di uscita e di stato sono finiti.
Una classe di automi particolarmente importante è quella degli automi in grado di riconoscere se una stringa fa parte o meno di un determinato linguaggio: automi riconoscitori. Quando si scrive un programma in un linguaggio di programmazione, infatti, l’esecutore (compilatore e/o interprete), prima ancora di elaborare i dati eseguendo le istruzioni, deve verificare che nelle istruzioni impartite non ci sia alcun errore di sintassi.
Gli automo riconoscitori, in pratica, sono sistemi che, dopo l’ingresso dell’ultimo simbolo della sequenza, rispondono con un "si" se questa è stata riconosciuta e con un "no" in caso contrario.
In automi di questo tipo, nei diagrammi degli stati, è possibile riconoscere l’esistenza di almeno uno stato iniziale, caratterizzato dal fatto di non aver nessun arco in entrata, e uno stato finale, da cui invece non escono archi.
Anche molti modelli astratti usati per rappresentare sistemi molto complessi come i sistemi economici, le reti di neuroni, i problemi d trasporto, e così via, possono essere agevolmente rappresentati attraverso delle tabelle di verità.
Per descrivere un automa occorre un modello matematico formato dalla quintupla:
A = í S, I, U, f, gý
dove:
S è l’insieme degli stati interni in cui può trovarsi;
I è l’insieme degli ingressi che è in grado di leggere;
U è l’insieme delle uscite che può produrre;
f è la funzione che fa passare da uno stato al successivo, St+1 = f (St, it);
g è la funzione che determina il valore delle uscite, Ut = g (St, it).
In particolare, si può ricavare che lo stato di un automa può essere assimilato al "ricordo" del fatto che un certo evento (l’evento che ha modificato il sistema producendo quello stato) si è verificato.
Poiché vogliamo caratterizzare un automa più in generale, supponiamo ora che gli input e gli output siano soltanto dei simboli: essi costituiscono l’alfabeto con cui lavora l’automa.
Un automa può essere, quindi, così schematizzato:
un nastro, suddiviso in celle in ognuna delle quali può essere conservato un solo simbolo; nel caso generale non poniamo alcuna condizione sulla lunghezza del nastro, che possiamo pensare come potenzialmente infinito;
un’unità centrale in grado di trovarsi in stati diversi; tra essi ne possiamo individuare uno come stato iniziale ed un sottoinsieme di stati finali;
un collegamento tra unità centrale e nastro dato da una testina di lettura e scrittura sul nastro.
Un automa di questo tipo ha un comportamento elementare, ma è in grado di compiere operazioni complesse. Il matematico Alan MathisonTuring (1912-1953) introdusse questo tipo di automa generale in un suo saggio del 1937 ed esso è appunto chiamato macchina di Turing. I suoi studi non nascevano dalla necessità di costruire un automa concreto, una vera macchina per il calcolo -si era ancora lontani dall’epoca dei computer-; nasceva invece dalla ricerca di una caratterizzazione dell’insieme delle funzioni calcolabili.
Turing mostrò che tutte le funzioni calcolabili possono essere calcolate da un automa di questo tipo: tutto ciò che può essere effettivamente calcolato costruendo una corrispondente procedura eseguibile, può essere calcolato da una macchina di Turing con apposite istruzioni.
A partire da funzioni elementari è possibile costruire l’intero insieme delle funzioni calcolabili. Analogamente, a partire da macchine di Turing elementari è possibile costruire macchine più complesse.
La macchina di Turing è allora un automa universale, in grado di eseguire tutte le procedure di calcolo; in un certo senso è un "sinonimo" di algoritmo perché tra algoritmi e macchine di Turing si stabilisce una corrispondenza biunivoca.
Pur essendo una macchina astratta, l’automa ideato da Turing è alla base del computer che elabora informazioni essenzialmente eseguendo successive sostituzioni dei simboli (discreti) con cui opera, secondo un insieme finito di regole. Ma è alla base del moderno computer, anche per un’altra caratteristica che lo rende "universale", cioè in grado di risolvere algoritmi diversi.
Certamente la progettazione di una macchina di Turing che calcoli un algoritmo non banale risulta un lavoro estremamente laborioso: occorre prevedere tutti i possibili stati in cui può, in un qualsiasi punto del calcolo, trovarsi l’automa e per ognuno di essi fissare il relativo comportamento. Si avrebbero così enormi tabelle di verità in cui deve essere prevista ogni situazione che si può verificare.
Ci interessa allora un’altra classe di automi universali, il cui modo di procedere non è basato su una tabella di verità, ma su un insieme d’istruzioni già elencate in ordine di esecuzione. Una volta fissata la sequenza d’istruzioni da compiere, l’automa le esegue l’una dopo l’altra, quasi si trattasse di un automa più complesso che di volta in volta attiva un suo automa elementare; l’indicazione di quale automa attivare gli proviene dalla sequenza d’istruzioni da eseguire per risolvere quel determinato algoritmo.
È un automa a programma; la sua universalità sta nel fatto che, cambiando il programma, è in grado di risolvere algoritmi diversi.
Consideriamo un automa a programma così organizzato:
ci sono sei registri di memoria, in ognuno dei quali è possibile contenere un numero; li indichiamo con M, A, B, C, D, P;
c’è una unità aritmetico-logica in grado di leggere e scrivere numeri nei registri, trasferire numeri da un registro all’altro, eseguire operazioni elementari aritmetiche e confronti con zero.
Il registro M ha una particolare funzione: può "comunicare" con l’esterno, nel senso che se dall’esterno devono essere forniti dati o ricevuti risultati, attraverso opportuni organi d’ingresso/uscita, la comunicazione avviene attraverso il registro M.
Il registro P contiene solo numeri interi positivi ed ha una funzione di contatore di programma. Esso contiene infatti il numero dell’istruzione che deve essere eseguita; il suo valore iniziale è ovviamente uno.
L’unità aritmetico-logica ha un ingresso attraverso il quale riceve messaggi che determinano il suo operare sui registri: si comporta cioè come un automa che allo stimolo esterno ricevuto fa corrispondere un’azione eseguita. I messaggi sono messaggi simbolici che indicano all’unità aritmetico-logica come operare sui registri; vengono comunicati uno alla volta e l’automa può riceverne solo un numero finito.
Completiamo l’automa con altri due "oggetti":
un supporto di memoria, diviso in caselle numerate da uno a n, in ciascuna delle quali è possibile contenere una istruzione da fornire all’unità aritmetico-logica;
un automa "selettore" S che è collegato al registro P e a seconda del numero in esso contenuto seleziona la corrispondente istruzione da comunicare all’unità aritmetico-logica.
Il complessivo funzionamento dell’automa è allora il seguente:
nelle caselle di memoria sono elencate nell’ordine le operazioni elementari da fare per eseguire l’algoritmo desiderato; esse corrispondono alle capacità elementari dell’unità aritmetico-logica;
nel contatore di programma P c’è inizialmente uno;
il selettore S seleziona la prima istruzione che viene comunicata all’unità aritmetico-logica; questa opera in conseguenza sui registri M, A, B, C, D ed incrementa opportunamente il numero contenuto nel registro P. Generalmente incrementa di uno il numero contenuto nel registro P, a meno che, non debba eseguire una istruzione di salto; cioè passare all’istruzione non immediatamente successiva: in questo caso metterà in P il numero dell’istruzione verso cui occorre saltare;
il selettore legge il nuovo numero nel contatore di programma P e seleziona la corrispondente istruzione: si seguita così ad operare.
È un automa a programma ed il suo funzionamento è già nella sostanza quello di un computer. È un automa di automi, nel senso che l’automa complesso è formato con vari automi elementari tra loro interagenti.
Per completare la sua descrizione dobbiamo dare una tabella delle istruzioni che esso è in grado di eseguire: le istruzioni sono in sostanza un elenco degli automi elementari che gli consente di operare.
Quest'automa a programma è un automa universale: modificando, infatti, il programma può essere utilizzato per algoritmi diversi.
Organizzazione logica di un computer
L’automa a programma rappresenta un modo d’operare molto simile all’organizzazione logica di un computer; il suo schema fu ripreso quale modello di macchina dal matematico di origine ungherese John von Neumann ed è chiamato appunto automa di von Neumann.
Un automa universale si compone essenzialmente di due "oggetti":
una memoria centrale, discreta, organizzata come una sequenza di celle ad ognuna delle quali è univocamente associato un numero d’indirizzo (address), dove è possibile conservare dati, istruzioni, risultati; su ogni cella possono essere fatte due sole operazioni, la lettura (read) dell’informazione ivi contenuta o la scrittura (write) di una nuova informazione;
un’unità centrale di elaborazione che provvede al lavoro vero e proprio, eseguendo operazioni elementari e controllando il complessivo processo di calcolo.
Nell’automa universale di Turing, ad esempio, la memoria è il nastro, l’unità centrale è in grado di trovarsi in stati diversi e di agire di conseguenza.
È però l’automa a programma a rappresentare uno schema logico-operativo molto vicino a quello di un computer; soprattutto si deve a von Neumann un’intuizione fondamentale: la possibilità di memorizzare nello stesso modo dati e programmi, come sequenze di cifre binarie. Il programma, in altre parole l’insieme d’istruzioni per manipolare i dati, può essere caricato in memoria insieme ai dati stessi; spetta poi all’unità centrale il compito di distinguere tra istruzioni e dati -generalmente in base alla posizione che occupano nella memoria-, decodificare le istruzioni ed eseguirle. Per questo lavoro essa dovrà contenere sia un organo in grado di operare, sia un organo in grado di controllare il processo. Già lo schema esaminato in precedenza ha quest'organo di controllo: esso è composto dal registro P che contiene il numero d’istruzione da eseguire e dal selettore S che individua la corrispondente istruzione.
Dobbiamo, quindi, distinguere all’interno dell’unità centrale di elaborazione (generalmente indicata come CPU, dal suo nome inglese Central Processing Unit):
un’unità aritmetico-logica, ALU per eseguire operazioni aritmetiche e logiche;
un’unità di controllo, (CU, Control Unit), che individua l’istruzione da eseguire, la decodifica, ne controlla l’esecuzione, passa alla successiva.
ALU e CU sono strettamente collegate poiché le operazioni di controllo dipendono anche dal risultato dell’istruzione eseguita.
Otteniamo così lo schema generale - o, come si usa dire, l’architettura logico-funzionale- di un computer, a partire dallo schema di un automa universale.
Il ciclo di controllo dell’automa computer, per l’esecuzione di ogni istruzione comporta:
fetch del codice operativo dell’istruzione (sempre presente);
decodifica del codice operativo;
fetch degli operandi;
execute dell’istruzione (dipende dal numero e dal tipo di cicli macchina per completare l’istruzione);
solo dopo che l’execute dell’istruzione corrente è terminata, la CPU è pronta a prelevare l’istruzione successiva da eseguire ed il processo è poi ripetuto in sequenza.
La ripetizione è scandita da un "orologio", il clock dell’automa che ad intervalli regolari riavvia il ciclo (automa sincrono).
Il procedere dell’automa si ripete così scandito da un orologio: il suo operare è un operare nel tempo.
L’operare nel tempo è la caratteristica specifica di un automa: un automa può essere progettato in modo diverso, si potranno avere automi con potenzialità molto maggiori di quelli con cui oggi lavoriamo e con un disegno logico diverso, ma non potrà fare a meno di un orologio che scandisca il suo operare.
La sua è appunto un'operatività fortemente dipendente dal tempo: è un tempo diverso dal tempo reale, perché mentre quest’ultimo è una grandezza continua, il tempo dell’automa è un tempo discreto, scandito istante per istante, segnale per segnale.
Livello 0: livello della logica digitale, hardware;
Livello 1: livello della microprogrammazione, firmware (è costituito dal software incorporato nei dispositivi elettronici durante la loro costruzione);
Livello 2: livello del sistema operativo;
Livello 3: livello del software.
Gli automi a stati finiti sono una particolare categoria di dispositivi automatici facilmente realizzabili anche con le tecniche dell’elettronica digitale.
Un automa si dice proprio, o di Moore, quando le uscite al tempo t dipendono esclusivamente dai valori assunti dello stato, in pratica:
Ut = g (St)
Per esempio un flip-flop è un automa di Moore di tipo sincrono, infatti, l’uscita può variare solo in sincronismo con il fronte attivo del clock. Un latch è invece di tipo asincrono perché la variazione dell’uscita avviene in corrispondenza di una variazione d’ingresso. Le reti combinatorie risolvono problemi in cui non è richiesto di ricordare la storia degli ingressi precedenti.
Nel diagramma degli stati ogni nodo rappresenta una coppia s/u, ove s è lo stato ed u l’uscita in un certo istante, e ad ogni arco è associato il relativo ingresso.
Un automa si dice improprio, o di Mealy, quando è caratterizzato dal fatto che l’uscita al tempo t, oltre che dallo stato, dipende anche dagli ingressi nello stesso istante, in pratica:
Ut = g (St, it).
Non si deve pensare che gli automi di Moore siano più limitati di quelli di Mealy rispetto alle cose che possono fare. Infatti, è sempre possibile trasformare ogni automa di Mealy nel corrispondente automa di Moore aumentando adeguatamente il numero degli stati.
Le reti sequenziali e la macchina di Turing sono esempi di automi di Mealy.
Nel diagramma degli stati ogni nodo rappresenta uno stato e ad ogni arco è associata una coppia i/U, dove i è l’ingresso che provoca il cambiamento di stato ed U è l’uscita che ne deriva.
Esempi di automi elementari in logica cablata.
OR
I = í A, Bý = 00, 01, 10, 11
U = í Cý = 0, 1
S = í S0, S1ý = 0, 1
come automa di Moore
come automa di Mealy ha un solo stato in cui permane all’infinito.
La realizzazione fisica di questo automa determina la creazione di un dispositivo che è in grado di simulare, nel mondo fisico, ciò che è svolto dalla funzione OR nel mondo astratto regolato dall’Algebra di Boole.
FLIP-FLOP S-R (Set-Reset )
I = í R, Sý = 00, 01, 10, 11 non ammessa perché azzera e setta contemporaneamente
U = í Q, 
ý = 01, 10
S = í A, Bý
Set = 1 setta il flip-flop, in pratica lo porta nello stato B in cui l’uscita Q è a livello alto.
Reset = 1 azzera il flip-flop, in pratica lo porta nello stato A in cui l’uscita Q è a livello basso.
Si deduce la tabella di verità con l’uscita in funzione degli ingressi.
| St Rt | Q(t+1) | |
| 0 0 | Qt | |
| 01 | 0 | |
| 10 | 1 | |
| 11 |
L’uscita mantiene il valore precedente.
FLIP-FLOP T (TOGGLE)
CK rende il flip-flop sincrono, non è un ingresso!
I = í Tý = 0, 1
U = í Q, ý = 01, 10
S = í A, Bý
T = 1 il dispositivo cambia stato, T = 0 permane nello stato in cui si trova.
Si deduce la tabella di verità con l’uscita in funzione degli ingressi.
| Tt | Q(t+1) | |
| 0 | Qt | |
| 1 | t |
FLIP-FLOP JK
Ingloba le caratteristiche dei flip-flop RS e T, in altre parole se R = S = 1 si comporta come un T.
I = í J, Ký = 00, 01, 10, 11
U = í Q, ý = 01, 10
S = í A, Bý
Si deduce la tabella di verità con l’uscita in funzione degli ingressi.
| Jt Kt | Q(t+1) | ||
| 0 0 | Qt | memorizza: è sullo stesso stato | |
| 01 | 0 | resetta, Q = 0, = 1 |
|
| 10 | 1 | Q = 1, = 0 |
|
| 11 | t |
commuta, in pratica A va in B e viceversa |
FLIP-FLOP D
Funziona in modo asincrono, assegna all’uscita Q il valore presente all’ingresso D
I = í Dý = 0, 1
U = í Q, ý = 01, 10
S = í A, Bý
Si deduce la tabella di verità con l’uscita in funzione degli ingressi.
| Dt | Q(t+1) | |
| 0 | 0 | |
| 1 | 1 |
| Proposta di lavoro N°1 |
Studiare un semplice sistema costituito da una lampada comandata da un interruttore.
Gli stati del sistema sono due: LS = lampada spenta
LA = lampada accesa
I comandi dati al sistema sono di due tipi: IA = interruttore aperto
IC = interruttore chiuso
Poiché abbiamo due ingressi e due stati, le transizioni possibili sono quattro.
| Input Stati | LS | LA |
| IA | 0 | 0 |
| IC | 1 | 1 |
| Proposta di lavoro N°2 |
Studiare l’automa che rileva la presenza di tre uno consecutivi.
I = í datiý = 0, 1
U = í datiý = 0, 1
S = í A, B, C, Dý
Si parte da A, entra 0 si resta in A, entra 1 si va in B, in C entra 0 e si riparte da A, se invece entra 1 il sistema è in equilibrio.
Analogia tra automa ed algoritmo.
int IN = 0, OUT = 0;
while (1) í
IN = random (1);
if (IN == 1) OUT++; else OUT = 0;
if (OUT == 3) í printf ("1, 1, 1 ");OUT = 0; ý
ý