|
Articolo pubblicato sul n. 63 di MCmicrocomputer (Edizioni Technimedia Srl - Roma) nel maggio 1987
And, Or, Not Concluso il breve ciclo sulla teoria della calcolabilità, a partire da questo numero Appunti di Informatica tratterà il tema delle reti logiche: i veri "mattoni" che costituiscono l'hardware di un computer.
Trattando di calcolabilità abbiamo mostrato come partendo
da semplici strumenti quali i numeri naturali e le
operazioni primitive su essi definite era possibile
calcolare qualsiasi funzione calcolabile. A partire da questo mese, con le reti logiche, andando a rispolverare i fatidici zeri e uno binari che corrono all'interno di ogni calcolatore digitale, scopriremo insieme fin dove è possibile arrivare. Buon viaggio...
Algebra della commutazione
Tra le tante cose che "sanno pure le pietre" annoveriamo certamente il fatto che i computer (tradizionali) intendono solo in termini di zeri e di uno, le cosiddette cifre binarie, e non in termini di programmi scritti in un linguaggio ad alto livello o in una qualsiasi forma di linguaggio assembly. Alla fin fine, ciò che la CPU sarà in grado di masticare saranno sempre e solo livelli logici 0 e 1, vero-falso, +5 volt - 0 volt, che dir si voglia. Nel corso di questi articoli, i quali come al solito non hanno neppure il minimo intento di sostituirsi ai testi specifici in materia, assumeremo che all'interno di un computer circolino le cifre binarie 0 e 1. Il fatto che questi non siano veri e propri numeri ma segnali elettrici non lo terremo in considerazione, tanto per cambiare, per non appesantire troppo la faccenda. Ancora una volta, e non poteva essere diversamente, ci comporteremo quanto più informaticamente possibile: ciò che manipoleremo è pura informazione. Punto e basta. Detto questo, prima di entrare nel merito, occorre fare una piccola introduzione riguardo l'algebra della commutazione (tranquilli, è di una banalità unica...) che è alla base della descrizione delle reti logiche che tratteremo. Gli 0 e gli 1 già li abbiamo: diamo per vero il fatto che in qualche modo esistono e dobbiamo solo manipolarli. Per fare questo, si usano essenzialmente tre operazioni: l'And, l'Or e il Not che danno il nome a quest'articolo. Le prime prendono due cifre binarie e ne restituiscono una, la terza prende una cifra binaria e ne restituisce un'altra. Per cifra binaria, qualora non fosse chiaro, si intende uno 0 o un 1. Null'altro. La più semplice, il Not non fa altro che complementare la cifra binaria: se è 0 dà 1, se è 1 dà 0, ovvero:
NOT(0) = 1 NOT(1) = 0
L'And di due cifre binarie è uguale a 1 se entrambe le cifre sono pari a 1, 0 altrimenti. Per iscritto:
0 AND 0 = 0 0 AND 1 = 0 1 AND 0 = 0 1 AND 1 = 1
Di contro, l'Or di due cifre binarie è uguale a 1 se almeno una di queste due è pari a 1:
0 OR 0 = 0
0
OR 1 = 1 1 OR 0 = 1 1 OR 1 = 1
Fanno parte dell'algebra della commutazione alcuni importanti teoremi facilmente dimostrabili col metodo della perfetta induzione: essendo il dominio e il codominio così ristretto, è sufficiente verificare le relazioni sostituendo una per una (e sono sempre poche) tutte le combinazioni di valori alle variabili indicate. Tali relazioni sono mostrate in figura 1: lì, per compattare la scrittura, l'AND è sostituito da un puntino, l'OR dal simbolo + e il NOT col simbolo di complementazione. A, B e C sono variabili binarie ovvero possono valere 0 o 1.
Reti logiche combinatorie
Nell'introduzione di questo articolo dicevamo che le reti logiche rappresentano i veri e propri mattoni coi quali è formato l'hardware di ogni calcolatore digitale.
Distinguiamo tra reti combinatorie e reti
sequenziali: di quest'ultime ci occuperemo in seguito. Una
rete logica combinatoria,
Da sottolineare la staticità di una rete combinatoria: a differenza delle reti sequenziali, applicando più volte lo stesso dato in ingresso otterremo sempre lo stesso risultato in uscita. Ovvero presa la nostra misteriosa scatoletta (figura 2A), la prima cosa che possiamo fare è costruire la corrispondente tabella di verità (figura 2B): applichiamo agli ingressi tutte le combinazioni di 0 e di 1 e annotiamo cosa accade in uscita, ai morsetti Y0...Y3. Le reti logiche, come intuibile, possono avere un numero qualsiasi di ingressi e un numero qualsiasi di uscite, il nostro scopo sarà quello di realizzare la rete partendo solo dal comportamento esterno: un po' come risolvere un gioco, dimmi come ti comporti... di dirò come sei.
All'interno
Cominciamo la nostra avventura all'interno delle reti
logiche svelandovi il primo segreto: le funzioni logiche
elementari. Non sono una novità in quanto ne abbiamo appena
parlato nell'algebra della commutazione: ci riferiamo
all'AND, OR e NOT, questa volta sottoforma di componenti
più che funzioni binarie. In figura 3 sono mostrate
rispettivamente una porta AND, una porta OR Le reti logiche combinatorie sono formate da elementi di questo tipo. Progettare una rete logica si traduce nel combinare opportunamente i componenti di figura 3 (possibilmente con minor spreco possibile) fino ad ottenere una rete rispondente alle caratteristiche richieste. Le caratteristiche richieste sono semplicemente di avere una relativa tabella di verità uguale a quella di partenza, tutto qui.
Un primo esempio
Secondo segreto: una rete logica ad n ingressi ed m uscite
non è altro che un insieme di m reti ad n ingressi ed una
sola uscita che forniscono ognuna uno dei valori Y1..Ym.
La prima operazione che compiremo sarà di ricavare l'espressione logica equivalente alla tabella: una espressione fatta di Not, And e Or che valutata (sostituendo i valori per X0, X1 e X2) ha un comportamento analogo quello della rete da risolvere. E' molto facile: dalla tabella si evidenziano tutte le righe la cui Y vale 1 e si costruisce la forma canonica dell'espressione come somma di termini prodotto, ognuno di questi ottenuto complementando o meno le variabili se in quella riga valevano 0 o 1. Come prima, somma sta per Or e prodotto per And. Procediamo: prendiamo la prima riga in cui la Y vale 1, la terza. Le variabili valgono 0 1 1, quindi il primo termine è:
__ X2 X1 X0
X2 è complementato dato che il suo valore era 0, X1 e X0 no in quanto valevano 1. La quinta riga (la seconda con Y uguale a 1) vale 1 1 0. Il secondo termine, di conseguenza, sarà:
__ X2 X1 X0
e così via sino all'ultimo termine. L'espressione completa è mostrata sempre in figura 4. Il passaggio da espressione a rete è quantomai immediato, trattandosi semplicemente di sostituire ogni termine con l'opportuno elemento AND (con elementi NOT all'ingresso, i pallini, dove necessario) e mettere in OR tutte le uscite di questi, come mostrato in figura 4B. Signore e signori ecco a voi la rete corrispondente. Si poteva anche procedere im maniera complementare in prodotti di somme invece che di somme di prodotti, nel qualcaso avremmo evidenziato le righe in cui la Y valeva 0. In tal caso la rete sarebbe stata formata da tre elementi OR le cui uscite finivano in una porta AND: a dire il vero aremmo anche risparmiato elementi, ma non importa, il primo è solo un esempio... e per risparmiare si utilizzano ben altri metodi. Prima di svelarvi altri segreti, una simpatica curiosità.
Esistono altri due importanti elementi logici, le porte NAND e NOR, mostrati in figura 5, sottoforma di componente e di relativa tabellina di verità. Non sono altro che delle normali porte AND e OR suffissate da un NOT: dove le prime valevano 0 queste valgono 1 e viceversa. Perché tanta importanza a questi due nuovi signori?
Semplice, usando solo elementi NAND o solo elementi NOR è
possibile costruire qualsiasi rete combinatoria. Per
dimostrare questo fatto, assunto che OR, AND e NOT di prima
sono sufficienti (credeteci), è sufficiente mostrare come è possibile costruire ognuna di queste tre porte con soli
elementi NAND o NOR. Il tutto è mostrato in
A NAND A = NOT(A) A NOR A = NOT(A)
per ottenere porte AND e OR useremo il teorema 8 (le cosiddette formule di De Morgan, per chi non le avesse riconosciute) se dobbiamo costruire una porta AND da porte NOR o porte OR da porte NAND, o semplicemente ne useremo due in cascata, dove la seconda funziona da NOT (caso in cui dobbiamo passare da NOR a OR o da NAND ad AND). Bell'e dimostrato: con le sole porte NOR o con le sole porte NAND possiamo costruire AND, OR e NOT e, conseguentemente, qualsiasi rete combinatoria. Tutto questo è "cosa buona" quando si è interessati più alla standardizzazione circuitale (uso di un solo tipo di porta) che ad un vero e prorio risparmio di elementi. Non è nuovo il fatto che costi meno la realizzazione e costruzione di un integrato fatto da molti pezzi "facili" piuttosto che da pochi pezzi "difficili".
Karnaugh e gli implicanti
Le mappe di Karnaugh costituiscono semplicemente un modo
diverso dalle tabelle di verità per descrivere come si
comporta per i vari input ogni terminale di uscita di una
rete. Il caso più semplice è ovviamente quello di una rete
con due soli ingressi (reti a un solo ingresso possono solo
essere il NOT o l'indentità): in questo caso la mappa ha
dimensione 2x2 dove le righe sono etichettate dai valori di
un ingresso le colonne dai valori dell'altro ingresso
(figura 7A). Nelle caselle, in figura 7, sono indicati dei
generici puntini, metteremo 0 o 1 a seconda del valore della
funzione sugli ingressi di riga e colonna corrispondenti. In
figura 7B troviamo
Si tratta di evidenziare sulla mappa zone quanto più estese possibile di 1, formate da 1-2-4-8 caselle adiacenti in modo da formare rettangoli o quadrati. Dal momento che le mappe godono, per così dire, di simmetria circolare, una di queste aree (gli implicanti) può anche iniziare da un estremo e terminare sull'altro, "passando da dietro alla mappa". Giusto per fare qualche esempio, in figura 8 sono mostrate delle mappe a tre ingressi in cui abbiamo evidenziato 5 tipici implicanti. Ad esempio, in figura 8A abbiamo evidenziato l'implicante di quattro 1 disposti a quadrato. In figura 8B e 8C, rispettivamente, implicanti rettangolari da 2 e da 4 caselle. In figura 8D e 8E due implicanti di quelli "che girano da dietro alla mappa".
Detto questo, la domanda più ovvia è: "A che servono
questi benedetti implicanti ?". Semplicissimo:
un implicante
identifica un termine AND dell'espressione che stiamo
costruendo e una volta evidenziati tanti implicanti quanti
bastano a coprire tutti gli 1 della mappa possiamo passare
alla espressione corrispondente e da questa alla rete. Il problema è semmai quello di capire un dato implicante quale termine identifica. Per risolvere questo piccolo arcano, cominciamo dall'implicante di figura 8A: notiamo che gli 1 in questione restano tali indipendentemente dal valore di X2 e dal valore di X0. Ciò significa che basta che X1 valga 1 che il valore della Y è 1. Questo implicante identifica allora il termine X1. Passiamo a figura 8B: lì gli 1 evidenziati non dipendono da X2 ma sono tali quando X1 vale 0 e X0 vale 1. L'implicante corrispondente è:
__ X1 X0
Discorso simile al primo per l'implicante di figura 8C: basta che X2 valga 0, quindi l'implicante è:
__ X2
__ __ X0 e X0 X2
Riassumendo, una volta evidenziati tanti implicanti (più grandi possibile, anche a costo di sovrapporre parte di questi) quanti bastano a coprire tutti gli 1 della mappa, ricaviamo i corrispondenti termini AND da mettere in OR come facevamo col metodo delle tabelle. Anche in questo caso possiamo muoverci in senso diametralmente opposto, evidenziando zone di 0 (gli implicati) ed ottenere espressioni di prodotti di somme: guardando la mappa è facile comprendere se è meglio evidenziare gli implicanti o gli implicati. Facciamo ora un esempio concreto: torniamo alla tabella di figura 4A e, per prima cosa costruiamo la mappa corrispondente, mostrata in figura 9A. Riusciamo ad evidenziare facilmente due implicanti, uno di 2 e uno di 4 caselle. Il primo identifica il termine X1 X0, il secondo il ternine X2. L'espressione corrispondente:
Y = X2 + X1 X0
e la rete corrispondente di figura 9B parlano da sole: esse sono funzionalmente equivalenti a quelle di figura 4B: come risparmio non c'è male!
Un bel digit
Per concludere questa sessione combinatoria delle reti logiche, una piccola applicazione paleo-computereccia: piloteremo un digit a sette segmenti. Dando in ingresso un numero compreso tra 0 e 7 in binario (per utilizzare tre sole linee) vedremo apparire sul nostro digit il valore decimale dato dall'accensione dei necessari segmenti.
La nostra rete logica combinatoria avrà dunque tre ingressi
(X2, X1, X0) e sette uscite (Y0...Y6) che come detto
piloteranno i sette segmenti mostrati in
figura 10A. In
figura 10B troviamo la tabella di verità dell'intera rete.
In figura 10C una per una le mappe relative ai 7 morsetti di
uscita, già complete di implicanti e di espressione
relativa.
La rete completa è mostrata in figura 11, un bel lavorone, ma alla fine funziona... Impaginato originale...
Articolo pubblicato su www.digiTANTO.it - per ulteriori informazioni clicca qui |
