Corso di Microprogrammazione: i circuiti combinatori

Microprogrammazione: circuiti combinatori

Bentornati. In questa terza puntata del corso ci occuperemo dei circuiti combinatori. Vi è sempre sembrato che “avere di più spendendo meno” fosse solo uno slogan? Bene, oggi impareremo che esistono metodi di minimizzazione delle funzioni logiche e capiremo come fare a realizzare un circuito che fa’ le stesse cose con meno porte logiche, il che vuole anche dire ridurre il costo del circuito finale. Siete pronti?

L’algebra di Boole, come introdotto nelle lezioni precedenti, è il vero e proprio fondamento della programmazione. 0 e 1 sono gli elementi basilari, se volete le entità più piccole di questa scienza. Tralasciamo cosa possa voler dire che l’algebra booleana sia un reticolo o algebra astratta (infondo non siamo qui per questo) e diamo una rapida (ma completa) scorsa alle operazioni che sono definite, e possibili, in questo “campo”. Abbiamo già chiarito che esistono operatori logici che permettono di realizzare funzioni comunque complesse ed in definitiva tutte le funzioni possibili.

Ma quali sono le proprietà delle funzioni logiche?

È presto detto. Si tratta di:

  • Commutativa
  • Associativa
  • Idempotenza
  • Assorbimento
  • Distributiva
  • Esistenza di minimo e massimo
  • Esistenza del complemento

Ci sarebbero già alcune importanti osservazioni da fare ma, visto che l’elenco, in realtà, non è ancora finito, le rimandiamo a fra qualche momento.

E se una funzione logica è “data” in un certo modo, che vuol dire?

Risulta intuitivo comprendere che una funzione logica del tipo

implichi che per ciascuna variabile “nominata” vi sia una pista conduttiva e che, se la variabile compare complementata, anche a questa dovrà corrispondere necessariamente ad un percorso conduttivo realizzato tramite la complementazione del precedente. Allo stesso modo, per ciascuna funzione logica coinvolta, ci sarà una porta logica, tra quelle di cui abbiamo parlato (AND, OR e così via…). Possiamo, quindi, affermare che per ciascuno degli elementi che costituiscono la funzione esisterà un corrispondente elemento unito ad altrettanti percorsi conduttivi. Questo, chiaramente, implica che più “elementi” compaiono nella funzione, più complicata essa sarà da realizzare.

Se una funzione logica è data, è possibile renderla più semplice?

Questa domanda nasce quasi spontaneamente perché non c’è limite, in teoria, al grado di complicazione di una funzione logica. Tuttavia, esistono delle proprietà che rendono possibile semplificare le funzioni o manipolarle per renderle meno complesse. Per ciascuna delle operazioni e delle variabili che riusciremo a far “venire meno” staremo semplificando non soltanto la complessità del circuito ma anche il suo costo finale.
Vediamo, quindi, queste proprietà per esteso riferite a ciascuna delle due operazioni:

NB: è possibile, nella stesura delle funzioni logiche, omettere il simbolo di AND logico allo stesso modo in cui può essere omesso, nella scrittura dei polinomi, il simbolo “per”.

OSSERVAZIONE: l’uso dell’apice, in luogo del tratto orizzontale sopra una variabile è equivalente.

Alcune di queste relazioni risultano piuttosto elementari ma vale la pena di notare come un’operazione di AND logico tra due variabili identiche, come nel caso precedente (sulla variabile a), implichi scrivere un’identità. Questo rende un’apparente operazione da eseguire, in realtà, solo un mero refuso.
Tuttavia, in merito a questa affermazione, è utile sottolineare come la semplificazione delle funzioni logiche non è sempre possibile applicando queste semplici identità. Talvolta occorre “manipolare”, in maniera anche importante, una funzione per poterla semplificare.
È anche importante dire che anche in questa matematica, in quest’algebra, esistano nozioni come il complemento del numero (sempre riferito alla base, come abbiamo accennato nella prima lezione) ed il concetto di elemento neutro rispetto ad una operazione, e quindi lo 0 per la somma che l’unità per il prodotto.

L’algebra dei circuiti e la sua rappresentazione

Finora sono stati introdotti concetti molto elementari, se volete, ma che aprono la strada ad altre considerazioni. In particolare, quest’algebra diventa uno strumento per l’analisi e la sintesi delle reti digitali perché consente di descrivere, in forma algebrica, la struttura del circuito. Una generica funzione logica può diventare, infatti, un polinomio.
Ed una volta che sia stata decisa quella convenzione di cui parlavamo tempo fa, ovvero se lavorare con la “logica positiva” oppure con quella “negativa”, tutto risulta chiaro e ben descritto.
Tuttavia non sempre le funzioni logiche sono semplici o “corte” come quelle che abbiamo enunciato in precedenza. Una funzione può dipendere da cinque o più variabili, il che rende molto difficile capire quale proprietà utilizzare ed applicare per ottenere la semplificazione del circuito. Quindi, in definitiva, non basta il “colpo d’occhio”.
Ed è proprio in questo scenario che ci vengono in aiuto le cosiddette Mappe di Karnaugh.

Si tratta di un metodo di rappresentazione grafica esatta per effettuare la sintesi delle reti combinatorie che siano costituite da uno o più livelli. In pratica, grazie a questo strumento, siamo in grado di visualizzare i valori assunti dalle variabili nelle funzioni che dobbiamo analizzare e semplificarle, per ottenere la riduzione della complessità dell’hardware in uso. Mica male, vero?
Le Mappe di Karnaugh funzionano individuando dei termini che vengono denominati “mintermini” e “maxtermini”, sulla base della distanza di Hamming. I termini, infatti, sono organizzati in matrici di dimensioni pari al numero di variabili da cui la funzione dipende e che sono disposti secondo il principio per il quale essi devono differire per una sola variabile binaria per volta. È certamente più facile visualizzare questa definizione che darla o esprimerla a parole ma possiamo certamente dire che le funzioni booleane, che abbiano un numero n di variabili, possono essere espresse in forme canoniche per raggiungere la loro forma minima.
Vediamo com’è fatta una mappa per farci un’idea più chiara:

Sulla sinistra si vede una tabella che ordina la variabile B sulle righe ed A sulle colonne. Le caselle costituiscono le possibili combinazioni  dei valori assunti dalle due variabili in oggetto. Sulla destra, la relativa tabella della verità. La variabile Y, tipicamente, rappresenta l’uscita del circuito, ovvero la nostra funzione.

Possiamo, molto brevemente, dire che mintermini e maxtermini sono rappresentati da 0 ed 1 è che l’espressione della funzione risultato della semplificazione sarà o sotto forma di somma di prodotti logici (prima forma canonica di Shannon) oppure come prodotto di somme (seconda forma canonica di Shannon). A livello pratico, se la semplificazione è possibile, non cambia nulla. La differenza starà nel tipo di porte che verranno impiegate nella implementazione della funzione.
Vediamo subito alcuni esempi che renderanno tutto molto più chiaro partendo dalle porte logiche:

La porta AND:

La porta OR

La porta EXOR

Così, si usano mappe per funzioni a tre variabili

o a quattro

NB: l’ordine con il quale scegliamo di disporre le variabili lungo le righe e le colonne NON è assolutamente importante, determinante o significativo. Fondamentale, però, è mantenere la coerenza tra la posizione dei mintermini (o maxtermini) e la relativa combinazione.

Vediamo un esempio applicativo

Supponiamo di avere la funzione:

Y=ab+acd+b’c’d+abc+cd’

la sua rappresentazione sulla mappa di Karnaugh è la seguente:

Dal momento che, per minimizzare la funzione, devo considerare, se possibile, soltanto implicanti (gruppi di mintermini) primi (di dimensione massima possibile, sempre multipla di 2) essenziali (che contengano almeno un mintermine non coperto da altri), la funzione può essere scritta come:

Y=ab+b’c’d+cd’+ac

NB: analoghe considerazioni vanno fatte per i maxtermini (che verranno indicati con 0 e non con 1). Si parlerà, in quel caso, di implicati.

In questo caso particolare esistono, però, due possibili soluzioni, esattamente equivalenti. Se, infatti, invece di considerare implicante primo essenziale quello composto dalle quattro cella in basso a destra avessimo considerato quello composto dalle celle 1101,1110,1001,1011 avremmo ottenuto la funzione:

Y=ab+b’c’d+cd’+ad

Essa è del tutto analoga al caso precedente in termini di “costo” della realizzazione. Questo dimostra un fatto interessante: la minimizzazione NON è un processo univoco ma comunque efficacie.

Se da un lato è vero che questo metodo può essere utilizzato per funzioni con un numero qualsiasi di variabili, è evidente che, quando esse superano le 6, anche soltanto disegnare le mappe comincia a diventare difficile. Infatti, già con cinque variabili è necessario disegnare due “matrici” di dimensione 4 × 4, una accanto all’altra che differiscano per il valore assunto dalla quinta variabile. Se alla prima tabella si associa la quinta variabile con valore logico zero mentre alla seconda la stessa variabile ma con dolore logico uno, si rispettano tutti i principi di cui abbiamo parlato in precedenza e si riesce visualizzare le possibili semplificazione.
Se le variabili diventano sei, evidentemente, sarà necessario disegnare quattro diverse tabelle disposte ai quattro vertici di un quadrato ed esse saranno differenziate da una coppia di valori assunti da due delle sei variabili “in gioco”.
Quando le variabili diventano sette la geometria “disegnata” dalle matrici sarà tridimensionale è così via dicendo…
È per questo che, in realtà, quando le funzioni diventano molto complesse (cioè dipendono da molte variabili), si utilizzano metodi differenti, come, ad esempio, il metodo Quine McCluskey.

La minimizzazione delle mappe è un problema che può essere risolto, chiaramente, con algoritmi numerici. Per darvene un’idea, ecco un software che effetto proprio quest’operazione: il suo nome è MIN.

Tempi di propagazione

Prima di lasciarci, credo sia importante fare un breve accenno a questo argomento e sarà breve per una questione di rispetto perchè ci sarebbe da scrivere intere biblioteche su questo tema e su come va gestito. A suo modo, anche questa è arte. Tuttavia è importante prendere dimestichezza con questo tema per cui vale la pena di soffermarci un momento.
Sappiamo che non esistono sistemi che rispondano all’istante. Un segnale elettrico, così come un qualunque stimolo, si propaga all’interno di un mezzo e ci vuole un certo tempo perché questo avvenga. Quando una porta logica deve rispondere con un’uscita combinazione degli ingressi, questa lo farà solo dopo un certo tempo (che dipende dal suo livello di sensibilità, dalla sua funzionalità, dalla tecnologia in cui è stata realizzata e da una serie di altri parametri che, per ragioni di tempo, non possiamo analizzare in questa sede). Questo vuol dire che una rete combinatoria dovrà essere dimensionata stando attenti ai singoli ritardi e studiando come il ritardo introdotto da ciascuna porta influisca sul risultato finale. Ciascuna delle variabili potrebbe dover subire ritardi diversi prima di essere, per esempio, sommata ad una che non è mai neanche stata complementata. Questo vuol dire che l’operazione dovrà necessariamente essere effettuata solo dopo che la variabile più “lenta” sarà effettivamente disponibile. Se vogliamo questa è una considerazione abbastanza banale, molto intuitiva; tuttavia, quando “giochiamo” con tempi dell’ordine dei ns queste considerazioni non sono davvero più così scontate, anzi rischiano di inficiare il funzionamento dell’intero sistema!

Supponiamo di avere a che fare con una porta logica che effettua semplicemente la complementazione. La definizione dei tempi di propagazione è relativa, in definitiva, agli intervalli temporali necessari affinché l’uscita, nella commutazione dello stato logico, si porti al livello di tensione utile perchè si abbia il riconoscimento del nuovo stato. Ovviamente questo vale per entrambe le commutazioni.

Si consideri la figura precedente come punto di partenza. Qui sono identificati tutti i punti notevoli di nostro interesse che sono utili nella definizione dei tempi in oggeto insieme alle tipiche forme d’onda associate. Vediamoli nel dettaglio:

  1. Tempo di discesa, tf, (che stà per time fall) del segnale d’uscita. Esso è misurato tra il 90% e il 10% della tensione di uscita massima VOHM (valore finale);
  2. Tempo di salita, tr, (ovvero time rise) del segnale d’uscita. Esso è definito come il tempo necessario affinché l’uscita si porti dal 10% al 90% del valore massimo VOHM.
  3. Tempo di propagazione nella commutazione dal livello alto a quello basso, tpHL, che è misurato come intervallo temporale tra il 50% di VIHM e il 50% di VOHM;
  4. Tempo di propagazione nella commutazione del livello basso a quello alto, tpLH. Esso è misurato come intervallo tra l’istante di tempo in cui la tensione assume un valore pari al 50% di VIHM e quello in cui è al 50% di VOHM.

I tempi tpHL e tpLH sono, di solito, diversi ed il costruttore fornisce anche una figura di merito piuttosto importante, ovvero  un valore medio tra i due, che è indicato come ritardo di propagazione tp.

Esso varia in maniera piuttosto considerevole a seconda delle varie famiglie logiche e, quindi, del tipo di circuito che stiamo utilizzando. Un valore di riferimento per la famiglia TTL (standard, che identifica la logica di tipo Transistor-transistor) è:
tp = 10 ns. Nel caso della logica cMOS si ha: tp = 100 ns, quando VCC = +5 V.

Conclusioni

Bene, per oggi basta così. Gli argomenti toccati completano un quadro di introduzione che, dalla prossima volta in poi, ci permetterà di cominciare a mettere le mani seriamente sulle porte, sulle operazioni e su alcune “strutture” logiche standard come il full-adder, ovvero, letteralmente, il sommatore completo.

Anche sul concetto di costo ci sarebbe molto da dire ma come chiave di lettura interpretativa potremmo assumere, per comodità, un valore unitario sia per ciascuna operazione sia per ciascuna variabile. Così Y=a+b’ risulta avere un costo pari a 2 (unità) poichè v’è da invertire la variabile b ed utilizzare un porta logica OR.

L’argomento delle famiglie logiche, per capire meglio i tempi di propagazione ed i ritardi più in generale, si presta ad approfondimenti di ogni tipo. Potete provare, per esempio, a vedere cosa significano i vari acronimi RTL, DTL, TTL. O magari leggere qualcosa riguardo al consumo di potenza, per minimizzare il quale la tensione di alimentazione è stata progressivamente ridotto nel tempo (da 5 V a 3,3 V e così via). Questo corso vuole essere più pratico e sarà quindi più improntato a “mettere le mani” sui circuiti ma l’area On-demand di EOS-Book è qui per questo! Se preferireste che questi argomenti venissero approfonditi, chiedetelo e sarete certamente accontentati.

Come di consueto, la parola adesso è a voi: dubbi? Domande? Perplessità? Questioni?

 

Quello che hai appena letto è un Articolo Premium reso disponibile affinché potessi valutare la qualità dei nostri contenuti!

 

Gli Articoli Tecnici Premium sono infatti riservati agli abbonati e vengono raccolti mensilmente nella nostra rivista digitale EOS-Book in PDF, ePub e mobi.
volantino eos-book1
Vorresti accedere a tutti gli altri Articoli Premium e fare il download degli EOS-Book? Allora valuta la possibilità di sottoscrivere un abbonamento a partire da € 2,95!
Scopri di più

5 Comments

  1. Piero Boccadoro Piero Boccadoro 20 dicembre 2012
  2. Piero Boccadoro Piero Boccadoro 21 dicembre 2012
  3. Piero Boccadoro Piero Boccadoro 21 dicembre 2012
  4. Piero Boccadoro Piero Boccadoro 21 dicembre 2012
  5. Davide.Cirone 16 luglio 2015

Leave a Reply