Corso di microprogrammazione: la matematica binaria e i circuiti combinatori

Bit Immagine tratta da: http://fedoraproject.org/w/uploads/9/9e/Artwork_F10Themes_Binary_threads.png

Bentornati. Ho visto dai commenti che finora ci sono state poche domande, il che, devo confessarlo, mi aspettavo visto che i concetti fino a questo momento sono stati molto basilari. Tuttavia, rinnovo l’invito a tutti a commentare e a sentirvi liberi di esprimere dubbi, perplessità, questioni ed anche, perchè no, a fare critiche. Oggi cominciano a fare sul serio, a parlare della matematica binaria introducendo due sistemi che sono molto diffusi: half-adder e full-adder. Fatto ciò, andremo a parlare di alcuni circuiti combinatori che costituiscono la base dell’elettronica così come la conosciamo. Siete tutti pronti? Allora partiamo.

La matematica binaria

La prima parte della puntata di oggi ha come argomento la matematica binaria e le operazioni elementari, ancora una volta. Il motivo? Beh, è molto semplice: non abbiamo ancora finito. Perché fino ad adesso, in verità, non abbiamo ancora davvero fatto neanche un’operazione. È arrivato, però, il momento di occuparci di che cosa significa realizzarne una, a partire dalla somma binaria.

Tramite le funzioni logiche, come intuitivo supporre, possiamo realizzare operazioni matematiche di qualsiasi tipo. Le quattro operazioni fondamentali sono, in realtà, soltanto due visto che i prodotti sono somme di un certo numero di numeri tutti uguali e le divisioni non sono altro che sottrazioni di uno specificato numero di numeri altrettanto identici tra loro.
Tuttavia, effettuare un’operazione di somma in base due è un po’ diverso dal farlo in base 10; concettualmente, però, sono operazioni identiche. La somma di due numeri restituirà un terzo numero che può essere composto da una o due cifre a seconda che il risultato dell’operazione sia superiore oppure inferiore alla base stessa.

Questa affermazione è abbastanza banale ma non lo è altrettanto se si considera che la tabella della verità della funzione logica OR contiene un’apparente incongruenza: quando entrambi i bit, le variabili che abbiamo chiamato A e B, sono pari ad uno, il risultato dell’operazione di somma non può essere sempre 1 ma dovrà essere 10, espresso in base 2.

Per ottenere questo risultato sarà necessario considerare che va introdotto il cosiddetto “carry”, ovvero il riporto.

La somma binaria potrà essere, quindi, effettuata correttamente nongià con una porta logica OR, la quale effettua la composizione di livelli logici, ma grazie all’utilizzo di 2 bit, che si riferiscono a due variabili differenti, che in questo momento battezziamo come “S” e “C”. Il primo dei due, che ancora non abbiamo definito, sarà denominato “somma”. Possiamo sintetizzare questa operazione binaria prima di tutto realizzando una tabella della verità.

A

B

S

C

0

0

0

0

0

1

1

0

1

0

1

0

1

1

1

1

successivamente sarà utile pensare ad una mappa di Karnaugh

grazie quello che abbiamo fatto fino ad adesso, ecco quello che ricaviamo:

ovvero uno schema logico che ci indica come si realizza un Half adder.
Prendiamo subito confidenza con questa nuova grandezza; considerando due numeri distinti formati, ciascuno, da 2 bit, avremo:

Per eseguire la somma tra il numero A ed il numero B dovremo semplicemente eseguire l’operazione di somma binaria tra le prime due cifre del numero. A seconda del risultato, utilizzeremo la tabella “somma” per sapere quale sarà il risultato dell’operazione. Il risultato in questione potrebbe generare un riporto, come abbiamo già accennato in precedenza. Questo sarà genericamente indicato con Ci, ovvero il riporto proveniente dall’operazione compiuta tra i bit in posizione i-1.

utilizzando una riga aggiuntiva “in testa” a quelle già in uso per ricordare che sarà necessario tenere conto per riporto la somma precedente, possiamo procedere con questo metodo per numeri che siano composti da un qualunque numero di cifre. È evidente, quindi, che quanto detto può riferirsi ad un numero composto quattro cifre, ovvero 4 bit

Considerato che il sommatore che abbiamo appena schematizzato non teneva affatto conto del riporto, a questo circuito si fa riferimento con il nome di “half adder”, ovvero è solo “mezzo” sommatore e nongià uno completo.
È evidente, quindi, che se vogliamo realizzare delle operazioni completamente specificate e che tengano conto di tutti i casi che è possibile che si verifichino, dovremo utilizzare un circuito differente.
A tale proposito, introduciamo adesso il “sommatore completo” ovvero il “Full-adder“.

Dato che abbiamo

     

otteniamo

per arrivare alla sintesi di questa rete logica che prevede l’utilizzo di diverse porte, è necessario creare la tabella della verità del caso più generale possibile in cui vogliamo non soltanto realizzare una funzione che tenga conto del riporto generato nella i-sima posizione in cui si trova il bit ma anche e soprattutto dell’eventuale riporto presente al “passo” precedente. Solo tenendo conto di tutti i riporti precedenti si potrà avere una equazione ed una caratterizzazione dell’operazione di somma binaria completamente specificate corretta.
Per questo motivo vi riportiamo la seguente tabella

An

Bn

Cn-1

Sn

Cn

0

0

0

0

0

0

0

1

1

0

0

1

0

1

0

0

1

1

0

1

1

0

0

1

0

1

0

1

0

1

1

1

0

0

1

1

1

1

1

1

grazie alla quale sostanzialmente ricaviamo le stesse grandezze del caso precedente, ovvero i bit somma ed il bit di riporto, solamente che questa volta saranno descrittivi di un’operazione corretta e completa.

Osservazione: queste considerazioni sembrano, adesso, particolarmente banali. Non sottovalutatele, però, in casi in cui le operazioni siano più complicate della semplice somma. Considerate che le cose che stiamo dicendo qui rappresentano il metodo per risolvere ogni operazione possibile e che quindi quello che adesso sembra banale in realtà non lo sarà molto presto, quando avrete da realizzare un sistema qualunque.

Per dovere di chiarezza, vediamo adesso un esempio di sommatore completo a 4 bit per non fare due cose importantissime:

  • il riporto del bit in posizione 0 è pari a 0;
  • il riporto del bit in posizione i è riportato in ingresso come “carry in” del successivo;

Questo completa la parte introduttiva sulla somma binaria. D’altronde le operazioni non si esauriscono qui, ma ce ne sono almeno altre due. Continuiamo, quindi, con la sottrazione binaria.

Prima di tutto è fondamentale specificare una questione: anche i numeri binari possono essere negativi! Questa sembra un’ovvietà ma stabilisce la necessità di introdurre il segno nella descrizione di un numero

Fatta questa doverosa precisazione, che si traduce nel fatto che 1 bit porterà l’informazione relativa al segno, è necessario dire che la sottrazione binaria può essere effettuata in diversi modi. Se consideriamo la sottrazione ai numeri A e B, due qualsiasi supposti, per ora, entrambi positivi, possiamo scrivere:

A-B= A+ (-B)

ovvero stiamo parlando di una somma in cui il secondo termine è stato cambiato di segno. Se riusciremo a cercare una rappresentazione di numeri negativi che ci possa rendere più semplice di effettuare la sottrazione, evidentemente molta strada sarà già stata fatta.

Esistono diversi modi per effettuare la rappresentazione dei numeri negativi ma tutte partono da due principi fondamentali:

  • bisogna specificare la grandezza della rappresentazione del numero che viene espressa tramite il numero di bit usati (che permette di differenziarle) ed il termine “modulo”.
    Ad esempio un numero che sia costituito da 6 bit può rappresentare tutti i numeri decimali che vadano da 0 fino a 63. Questo numero viene, per questo, detto “modulo 64″.
  • il bit più significativo (che viene sempre indicato con l’acronimo MSB, ovvero Most Significant Bit) rappresenta, come abbiamo già avuto modo di vedere l’informazione sul segno. Anche qui è possibile utilizzare delle convenzioni così come abbiamo già detto in altri momenti.

Il numero può essere positivo o negativo e nei due casi potremmo avere, per esempio, rispettivamente l’MSB uguale a 0 ed a 1.
Più avanti vedremo di approfondire questo concetto ma per ora anticipiamo qui una convenzione molto comoda che è quella del “complemento a due”.
Prima di tutto va’ definito il complemento: si tratta del numero che bisogna sommare a quello che abbiamo già per ottenere la base. Banalmente, se contiamo in base 10, 2 e il numero che bisogna sommare ad 8 (che è quello che supponiamo di aver già) per ottenere la base. Semplice vero?

Bene, dato un numero binario positivo, il suo complemento si ottiene negando il numero. Questa frase assume senso compiuto solamente quando parliamo di numeri binari visto che due sono i soli possibili valori per i bit e negare un numero significa invertire le cifre, ovvero assegnare loro l’altro dei due possibili valori.
Quando parliamo di complemento a 2 del numero, invece, intendiamo che al complemento del numero viene sommato uno.
Pertanto, se assumiamo di lavorare con numeri composti da 4 bit distinti, ovvero stiamo parlando di numeri che possono andare da zero a 15 e pertanto modulo 16, consideriamo un generico numero:

7 (base decimale) = 0111 (base binaria)
NOT (0111) = 1000 + 1 = 1001

così abbiamo scoperto che il complemento a due del numero decimale sette corrisponde al numero decimale nove. D’altronde questo è abbastanza evidente perché volendo ottenere numeri binari che siano di modulo definito, il complemento ci permetterà di raggiungere esattamente quella cifra. Ovvero 7 + 9 = 16.

Ora che tutto questo è più chiaro vale la pena di fare una precisazione: se si applica lo stesso procedimento due volte, si ritorna al numero di partenza. Questo è abbastanza evidente ed ha riferimenti anche in quelle regole dell’algebra booleana di cui abbiamo parlato in precedenza; l’esempio principale è quello dei Teoremi di De Morgan.

Possiamo utilizzare una tabella per rappresentare con il suo segno il complemento a due dei numeri binari composti da quattro cifre distinte in modo tale da averne una più completa rappresentazione.

Decimale

Binario

7

0111

6

0110

5

0101

4

0100

3

0011

2

0010

1

0001

0

0000

-1

1111

-2

1110

-3

1101

-4

1100

-5

1011

-6

1010

-7

1001

-8

1000

Tanto per essere chiari, vediamo di fare un esempio:

7(10) – 6(10) = 0111(2) – 0110(2) = 0111(2) + 1010(2) = 10001(2)

il risultato di quest’operazione sarebbe un numero a 5 bit ma siccome abbiamo stabilito che la rappresentazione deve essere a quattro, il bit più significativo dovrà necessariamente essere scartato. È evidente che quello che abbiamo ottenuto non è il risultato corretto dell’operazione ma il risultato più giusto rispetto a quello che dovevamo fare.

Se facciamo un altro esempio adesso otteniamo:

2(10) – (-3(10)) = 0010(2) – (-1101(2)) = 0010 + 0011 = 0101

Alla luce di quanto detto, risulta evidente che un sottrattore binario non è altro che un circuito a due stadi in cui il primo cambia segno al secondo termine mentre il secondo effetto la somma dei due termini distinti.

Concludiamo questa prima parte parlando della moltiplicazione binaria. Utilizziamo uno schema simile a quanto visto per le due operazioni precedenti introducendo la seguente tabella

A

B

P

0

0

0

0

1

0

1

0

0

1

1

1

in questo caso non dobbiamo considerare il riporto e se prendiamo numeri costituiti da 2 bit ciascuno, lo schema per effettuare la moltiplicazione sarà:

ed ecco, per ragioni di completezza, un valido esempio pratico che rende bene l’idea:

Osservando la presente operazione, si nota facilmente che essa risulta essere insieme due operazioni distinte ovvero lo scorrimento sinistra e la somma. La moltiplicazione binaria può essere realizzata sia via hardware sia grazie all’utilizzo di software. Per la realizzazione in hardware vedremo più avanti come si potrà fare quando tratteremo i circuiti sequenziali.
Una possibilità alternativa è quella di utilizzare un dispositivo a memoria di sola lettura, al secolo ROM (Read Only Memory).

I circuiti combinatori

Adesso veniamo alle prime applicazioni. Da questo momento in poi, tutto quello che vedremo sarà finalizzato ad utilizzare tutti i concetti che sono stati espressi finora, di fatto si è trattato delle basi dell’elettronica digitale, per ottenere un risultato. Quale? Dipende dalla specifica funzione che ciascuno di voi avrà da implementare. Perché quella? Beh, dipenderà dalla specifica applicazione, ancora una volta.

Quello che vedremo, però, sarà da intendersi come del tutto generale, quindi, senza ulteriori indugi, vediamo di che cosa si tratta.

Prima di tutto, vale la pena di specificare che quando parliamo di elettronica digitale, un circuito (o rete) combinatorio è nient’altro che un insieme di porte logiche connesse in una maniera specificata la quale realizza una funzione desiderata.

Il funzionamento di questa rete riguarda solo la relazione ingresso-uscita che sussiste tra le porte.

Essa viene descritta, come sempre, da una funzione logica la quale potrà assumere soltanto due valori distinti corrispondenti ai due livelli logici possibili secondo la logica positiva o negativa che abbiamo stabilito a monte.

Poiché le uscite sono istantanee, vale la pena di precisare che questi circuiti sono senza memoria! Vedremo, più avanti, quando parleremo di circuiti sequenziali, che è possibile utilizzando porte logiche, realizzare dispositivi che, invece, la memoria ce l’hanno. In particolare, vedremo che queste stesse porte logiche possono realizzare proprio delle memorie.
Ma andiamo per gradi ed intanto vediamo di approfondire meglio questo.
Se parliamo di circuiti combinatori, le funzioni che possiamo realizzare sono:

  • operazioni numeriche fra i dati, tra cui proprio quelle operazioni che abbiamo visto fino ad adesso ovvero somma, moltiplicazione eccetera;
  • indirizzamento e selezione di dati (e quindi traffico di dati controllato);
  • funzioni logiche più genericamente intese (ovvero realizzate secondo specifiche che non sono “elementari”).

Un aspetto importante di circuiti combinatori è la loro organizzazione; essi sono spesso organizzati in base a strutture regolari, per esempio matrici, che prevedono l’identificazione di righe e colonne che rispettivamente possono assumere il ruolo di ingressi ed uscite. La figura lo spiega in maniera abbastanza esauriente

Tramite l’utilizzo di specificati elementi nelle intersezioni tra le righe, è possibile effettuare l’indirizzamento dei dati.
È anche possibile utilizzare una struttura che si chiama “bit-slice“,

che prevede l’elaborazione di dati a blocchi uguali posti in parallelo tra loro.

Tutto questo con una serie di problematiche relative a come effettivamente i circuiti combinatori devono essere interfacciati rispetto al mondo esterno, ovvero come gli ingressi vengono portati al circuito e come prelevare le uscite dallo stesso. Le porte che verranno utilizzate, tuttavia, sono quelle che abbiamo già visto più volte, ovvero quelle elementari, in combinazione tra loro.
Rientrano nella valutazione della realizzazione di circuiti combinatori una serie di grandezze quali

  • fan-in;
  • fan-out;
  • costo di realizzazione;
  • potenze.

Data la matrice pratica di questo corso, questi concetti non verranno approfonditi; tuttavia, vi rimandiamo all’area On-Demand del Forum per richiedere qualunque approfondimento.

Tanto per darvi un’idea di che cosa significa utilizzare un circuito combinatorio per realizzare una funzione anche non elementare, ecco il diagramma a blocchi che dimostra come si possa realizzare la funzione OR esclusivo.

Vale la pena di tornare su questa porta perché benché essa sia elementare, non lo è la sua struttura, come suggerisce anche l’espressione completa della funzione logica.

I comparatori

Apriamo adesso una breve parentesi su questo tipo di circuiti che sono, in realtà, elementari ma svolgono una funzione fondamentale: i comparatori verificano ciascun bit del numero per trovare se ce ne sono due uguali, a coppie, e capire se due numeri siano identici o meno. Questa funzione può essere realizzata sia con sole porte XOR sia con porte XNOR.

Nella prima versione, l’uscita della OR finale sarà alta se una qualunque coppia di bit delle parole non coincide.

Nella seconda, invece, l’uscita della AND risulterà bassa se qualsiasi coppia di bit non coincide.

Decoder

Si chiama decodificatore un sistema digitale all’interno del quale si abbia la selezione dell’uscita corretta, e quindi la sua abilitazione,  in corrispondenza di una data combinazione degli ingressi. La struttura di un decoder è molto semplice perché si utilizzano N ingressi per indirizzare 2^N uscite. Il che vuol dire che c’è una stretta relazione tra il numero degli ingressi ed il numero delle uscite.
Questo vuol dire che per una parola di 4 bit esistono 16 possibili soluzioni da abilitare e quattro linee abitabili. Ecco per quale motivo si tratta di un decodificatore.

In una variante di questa struttura, è possibile anche che sia presente un ingresso totalmente indipendente che funge da segnale di sincronizzazione o più in generale di semplice abilitazione che, per l’appunto, prende il nome di “enable”.

La tabella di verità di questo porta a 3 ingressi e 8 uscite è del tipo:

A2

A1

A0

Y0

Y1

Y2

Y3

Y4

Y5

Y6

Y7

0

0

0

1

0

0

0

0

0

0

0

0

0

1

0

1

0

0

0

0

0

0

0

1

0

0

0

1

0

0

0

0

0

0

1

1

0

0

0

1

0

0

0

0

1

0

0

0

0

0

0

1

0

0

0

1

0

1

0

0

0

0

0

1

0

0

1

1

0

0

0

0

0

0

0

1

0

1

1

1

0

0

0

0

0

0

0

1

Per ragioni di completezza vi facciamo vedere lo schema circuitale generale di un decodificatore binario a 3 bit realizzato con NMOS.

Encoder

Di solito, le operazioni binarie che vogliamo poter compiere sui numeri sono bidirezionali ed anche invertibili. Ecco per quale motivo per ciascun circuito combinatorio effettui un’operazione viene realizzato quello che implementa l’operazione opposta, di modo che l’applicazione di un decoder possa essere un processo “trasparente”. La cascata di un decoder e di un encoder, infatti, deve restituire la stessa identica combinazione di bit che avevamo prima.
Così come abbiamo fatto per il decoder, vediamo, adesso, la struttura di questa rete.
Prima di tutto, come nel caso precedente, va specificato che questa volta il numero degli ingressi ed il numero delle uscite in relazione esattamente opposta e che il legame tra di loro resta comunque invariato; pertanto avremo 2^N ingressi che servono ad indirizzare N uscite. Pertanto, ad esempio, avremo una configurazione possibile a tre uscite ed otto ingressi.

La tabella di verità di questo porta ad 8 ingressi e 3 uscite è del tipo:

A0

A1

A2

A3

A4

A5

A6

A7

Y2

Y1

Y0

1

0

0

0

0

0

0

0

0

0

0

0

1

0

0

0

0

0

0

0

0

1

0

0

1

0

0

0

0

0

0

1

0

0

0

0

1

0

0

0

0

0

1

1

0

0

0

0

1

0

0

0

1

0

0

0

0

0

0

0

1

0

0

1

0

1

0

0

0

0

0

0

1

0

1

1

0

0

0

0

0

0

0

0

1

1

1

1

Ed anche in questo caso, sempre per ragioni di completezza vi facciamo vedere lo schema circuitale generale di un encoder.

Mux & Demux

Un’altra possibilità è la coppia di dispositivi che prevede l’indirizzamento. Supponiamo di avere una linea sulla quale transitino i dati e di volerla indirizzare verso più destinatari possibili. Questo si può fare grazie ad una particolare combinazione degli ingressi. Di fatto, per capirci, stiamo parlando di una centrale telefonica.
Ecco per quale esigenza nascono Multiplexer e Demultiplexer; il primo è un circuito logico che permette la selezione di un ingresso tra gli N possibili su una linea d’uscita tra quelle disponibili (che sono 2^N).

La selezione avviene tramite segnale di controllo. La funzione duale, invece, è rappresentata da un circuito logico che trasmette un segnale binario (quindi dati) in ingresso su una delle linee di uscita disponibili.

La selezione dell’uscita “destinataria” viene fatta attraverso un opportuno indirizzo. Questo, nei fatti, è un decoder modificato perché si tratta, chiaramente, della sola aggiunta di un ingresso dati al decoder di cui abbiamo già parlato in precedenza.

…arrivederci alla prossima lezione

Bene, però oggi abbiamo finito. Scopo di questa lezione era far vedere come esistano delle operazioni elementari effettuate da circuiti e reti resi standard dall’utilizzo, ovvero dalla frequenza di impiego, tant’è vero che potete comprare porte logiche e decoder indicando direttamente quali sono il numero di ingressi ed il numero di uscite che volete. Tutto quello di cui abbiamo parlato fino a questo momento si può realizzare nel modo in cui abbiamo detto oggi ed è proprio per questo che quelle basi da adesso in poi serviranno che verranno messe in pratica.
L’argomento la prossima volta sarà differente perché parleremo dei sistemi digitali sequenziali, ovvero quelli di cui abbiamo accennato poco fa. Vedremo come funzionano, qual è la loro importanza e perché costituiscono l’elemento costitutivo fondamentale delle SRAM. Stay tuned.

 

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ù

6 Comments

  1. Emanuele Emanuele 3 febbraio 2013
  2. Boris L. 6 febbraio 2013
  3. Giorgio B. Giorgio B. 9 febbraio 2013
  4. Piero Boccadoro Piero Boccadoro 10 febbraio 2013
  5. Max Caruso 17 ottobre 2013
  6. Max Caruso 17 ottobre 2013

Leave a Reply