CAPITOLO 4 - dei.unipd.itpanico/APPUNTI/cap4 - Elaborazione con Reti... · dati in ingresso sono...

CAPITOLO 4

Elaborazione dell’informazione

Introduzione

I dati che abbiamo trattato finora, sono dati semplici e basilari, che vanno a

codificare informazioni fini a se stesse e non ulteriormente scomponibili, senza

coè essere a sua volta la composizione di altre informazioni.

Il problema che ora affronteremo, riguarda la codifica di informazioni più

complesse per le quali saranno necessari dati composti da altri dati. In questo

caso si parla di strutturazione dei dati. Se dovessimo codificare ad esempio una

rubrica telefonica composta di nomi e numeri, potremmo rappresentare i nomi

con sequenze di carattere ASCII, e i numeri con sequenze binarie usate per

codificare i numeri interi: è dunque evidente che l’informazione contenuta in una

rubrica telefonica, è composta da più informazioni che non sono più le semplici

unità informative finora considerate, ma da informazioni più complesse che si

inseriscono appunto in contesto strutturato che la codifica deve saper

implementare.

In questi casi occorre dunque standardizzare i dati; cioè non basta solamente

definire i numeri e i caratteri, perché quando questi vengono inseriti in un

determinato contesto, assumono un significato preciso che non è strettamente

legato all’unità informativa di base codificata, ma viene a dipendere dallo scopo e

dall’uso per cui tale informazione è stata inserita n un certo ambiente. Pensiamo

per esempio alla codifica di una data, potremmo pensare di rappresentarla con

una serie di numeri binari come abbiamo fatto fino ad ora, ma se volessimo

ordinare una serie di date così rappresentate, ecco che tale codifica non sarebbe

più sufficiente per elaborare in questo senso l’informazione prodotta. Se invece

codificassimo le date pensando ai secondi che sono passati da un certo giorno di

un certo anno in poi, allora in questo caso troveremmo un formato che ci

consente non solo di ottenere l’informazione legata alla data in quanto tale, ma

anche di elaborare quell’informazione nel senso di poter ordinare per esempio in

una tabella le date così codificate.

In sostanza non basta codificare le informazioni, ma la codifica deve essere

attuata in maniera tale che il dato codificato possa essere a sua volta elaborato

dal calcolatore al fine di produrre informazioni utili che vanno al di la di quella

contenuta nel dato stesso.

Università degli studi di Padova - Facoltà di Scienze Statistiche Corso di Laurea in Gestione delle Imprese – “Sistemi di Elaborazione” Prof . Nicola Zingirian 93

Ricordiamo che la rappresentazione di un dato viene realizzata in modo tale che

questa sia semplice: scegliendo infatti i numeri binari come bit dell’informazione,

si è visto nel capitolo 2 della prima parte, che questi possono essere trattati

come numeri e quindi applicare su di essi l’algebra dei bit, rendendo così

l’elaborazione dell’informazione più semplice e immediata.

Tornando allora all’esempio della data, avendo scelto come formato per

rappresentare l’informazione, i secondi trascorsi da una data di un certo anno in

poi, questo permette di ordinare le date in modo crescente, proprio in virtù del

fatto che i bit che codificano i secondi, sono dei numeri.

C’è un altro ramo della rappresentazione dell’informazione che si occupa di

rappresentare l’informazione multimediale.

Si tratta di una rappresentazione che codifica in bit degli oggetti che a prima

vista non si può pensare di poter rappresentare in bit, basti pensare alla codifica

delle immagini o dei suoni, si cerca cioè di individuare codifiche di dati che

mirano a ridurre in numero dei bit necessari per rappresentare l’informazione,

analogamente alla logica della codifica di Huffman, che ottimizzava l’impiego dei

bit ottenendo una codifica senza alcuna perdita dell’informazione; nel caso delle

immagini o del suono però non è invece così rilevante la perdita dell’informazione

ai fini di una riduzione dei bit necessari per rappresentarla, perché l’importante è

che l’immagine o il suono siano percepite nella loro globalità di rappresentazione,

trascurando i dettagli di cui è composta: basta pensare ad esempio ad un

filmato; l’occhio umano in questo caso non ha bisogno di ottenere tutta

l’informazione contenuta nelle immagini, perché in una sequenza di fotogrammi

l’occhio percepisce il movimento, per cui l’immagine immediatamente successiva

a quella precedente è semplicemente una variazione di quest’ultima; non serve

allora codificare nuovamente l’immagine successiva, ma si andranno in questo

caso a codificare solo le differenze o gli spostamenti di oggetti dell’immagine

stessa.

4.1 Elaborazione dell’informazione

Inizialmente si è parlato di insieme informativo1, composto da un numero finito

di oggetti di vario tipo i quali a sua volta sono univocamente codificati con

sequenze di bit e decodificati o rimappati ai fini di rendere leggibile l’informazione

così ottenuta.

1 Vedi paragrafo 1.1. della prima parte


Tra la fase di codifica e quella di decodifica possiamo introdurre un passaggio

ulteriore nel quale i bit della codifica, anziché essere direttamente trasmessi

come informazione finale, sono ricevuti e trasformati in maniera tale da produrre

un’altra sequenza di bit utile ai fini dell’informazione stessa.

Si tratta di inserire un meccanismo che non solo riceve in formato di bit il

problema portato dall’informazione, ma andando ad elaborare la codifica

realizzata, riesce anche a generare altre sequenze di bit, diverse da quelle

entrate, che risolvono il problema inizialmente codificato. Il cervello elettronico

nasce proprio con questa finalità: si trasmettono sequenze di bit all’elaboratore,

questo li trasforma opportunamente producendo una sequenza di bit in uscita

utile ai fini della soluzione di un qualche problema.

Quindi se finora abbiamo affrontato il problema della codifica e decodifica

dell’informazione, in questa seconda parte, affronteremo l’argomento relativo

all’elaborazione dell’informazione codificata con bit, in modo da ottenere diverse

sequenze di bit in uscita maggiormente gestibili nonchè risolutive per determinati

scopi.

Se volessimo per esempio dare in ingresso ad un elaboratore un calcolo da

eseguire, ad esempio una somma, i dati inviati in ingresso saranno una sequenza

di bit che rappresentano due addendi della somma. A questo punto il

meccanismo che li elabora, farà in modo che una volta attuata la trasformazione

dei bit in ingresso, darà come risultato in uscita, una sequenza di bit diversa da

quella in entrata e che corrisponde esattamente alla somma che si voleva

ottenere.

Ritornando all’esempio della rubrica telefonica, se il problema consiste nel voler

sapere il numero di telefono di una persona, i bit inviati in ingresso saranno il

nome e il numero ad esso associato, mentre l’elaborazione produrrà una

sequenza di bit che assocerà il numero di telefono alla persona che si cercava.

E’ importante osservare, che qualunque sia la sorgente informativa, il sistema di

elaborazione lavora unicamente sui bit; pertanto come il bit uniformano una

qualunque sorgente informativa, traducendola appunto in termini di bit, così

anche l’elaborazione consiste sempre in una trasformazione più o meno o

complessa di bit.


4.2 Funzioni booleane

In fase di elaborazione dei dati abbiamo una sequenza di bit in ingresso che

indichiamo con x1,x2, x3,....xn-1, che vengono trasformati in altri bit di uscita che

indichiamo con y1,y2,y3,....ym. Possiamo pensare all’elaborazione dei dati

rappresentati in bit come ad una funzione matematica che ad ogni data sequenza

di bit in ingresso x1,x2, x3,....xn-1 associa una sequenza di bit in uscita

y1,y2,y3,....ym,:

y1,y2,y3,....ym, = f(x1,x2, x3,....xn-1)

la relazione così individuata viene definita Funzione Booleana2.

Una funzione booleana è una funzione ad n variabili indipendenti dette variabili

booleane.

Una variabile x è detta booleana se gli unici valori che può assumere,

corrispondono a 0 e a 1cioè:

x := {0,1} variabile booleana

una variabile booleana ha quindi la capacità di esprimere solo due possibili valori.

Con n variabili booleane indipendenti la funzione booleana ammette 2n possibili

soluzioni, ossia l’insieme degli elementi rappresentabili dati n bit.

Vedremo più avanti che le variabili booleane vengono definite ingressi e gli

output delle funzioni booleane vengono definiti uscite.

L’output della funzione booleana - che in matematica potrebbe essere

considerato il codominio di una generica f(x) - sarà dato da un solo valore che

potrà essere o 0 o 1.

La differenza fondamentale che c’è tra le funzione booleane e quelle definite nei

numeri reali, è che le prime assumono sempre e solo valori o zero o uno, mentre

invece sappiamo che le funzioni definite nell’asse reale possono assumere valori

tendenti all’infinito.

Supponendo di avere due bit per la rappresentazione, ossia due variabili, la

funzione booleana sarà indicata in questo modo:

y = f(x0,x1)

2 Le funzioni Booleane prendono il nome dal matematico inglese del XIX George Boole che introdusse un formalismo che opera su variabili, dette variabili

booleane


dove x0,x1 è la generica sequenza di bit che assumerà valori 0 e/o 1, e che

abbiamo visto essere così definite:

x0 : {0 ; 1}

x1 : {0 ; 1}

la funzione boolena restituisce il valore 1 se e solo se una delle due

variabili assume il valore 1, altrimenti assume il valore 0. Sempre con

riferimento a due bit, organizziamo in una tabella sia il dominio della funzione

considerata y = f(x0,x1) che i valori assunti dalla funzione:

x0 x0 y0

0 0 0 1 0 1 0 1 1 1 1 0

è importante osservare che in qualsiasi tipo di funzione booleana, a differenza

delle funzioni reali, non esistono punti in cui essa non è definita proprio perché i

dati in ingresso sono codifiche di elementi finiti a sua volta individuati, pertanto le

funzioni booleane ammettono sempre valori in tutti punti che le definiscono.

Poiché di fatto le funzioni booleane operano su variabili binarie, che possono

assumere solo due valori, è possibile definire una corrispondenza fra i valori logici

vero e falso e i valori binari 0 e 1, per cui al valore vero viene normalmente fatto

corrispondere il valore binario 1, mentre al valore falso viene fatto corrispondere

il valore binario 0. Avremo dunque

y = 0 FALSO

y = 1 VERO

Una volta definite le funzioni booleane, possiamo definire delle operazioni tra

variabili analogamente a quanto avviene nell’algebra tra numeri reali.

Vediamo allora di descrivere gli operatori di base, con cui è possibile costruire

qualunque altra funzione di variabili booleane


4.3. Tabelle di verità

Operatori e funzioni booleane possono essere descritte attraverso le cosiddette

tabelle di verità, che associano a ciascuna possibile combinazione di valori delle

variabili il corrispondente valore della funzione.

La tabella di verità determina completamente il legame funzionale tra gli

ingressi e le uscite, dove gli ingressi sono le variabili booleane e le uscite l’output

delle funzioni booleane.

Si è infatti visto che la funzione booleana è una funzione multivariata a n variabili

che restituisce un vettore di bit, con il vantaggio che i valori assunti dalle singole

variabili non sono infiniti come i numeri reali, ma essendo bit, possono assumere

solamente i valori o 0 o 1, semplificando così la trattazione di queste funzioni al

punto che una funzione booleana può essere completamente tabulata.

Supponendo ad esempio di considerare una funzione booleana a tre ingressi:

y0 = f(x0,x1,x2)

la corrispondente tabella di verità sarà la seguente:

x0 x1 x2 y0

0 0 0 1 0 0 1 1 0 1 0 0 0 1 1 1 1 0 0 1 1 0 1 0 1 1 0 0 1 1 1 0

Per n=3 ingressi, avremo 23=8 righe di possibili combinazioni.

In generale si può notare come la tabella di verità di una funzione ad n variabili

abbia n+1 colonne: una per ogni variabile di ingresso più una per il valore che

deve assumere la funzione. Inoltre, una tabella di verità ha tante righe quante

sono le combinazioni possibili che le variabili di ingresso possono realizzare.

Poiché i valori assunti da ciascuna variabile sono soltanto 2, con n variabili si

avranno 2n possibili combinazioni. Quindi una funzione booleana di n variabili

potrà essere rappresentata da una tabella di verità costituita da n+1 colonne e 2n

righe

Inoltre, poiché ogni riga (corrispondente ad una possibile combinazione delle

variabili di ingresso) potrà presentare due possibili valori nella colonna relativa al

valore che la funzione assume in corrispondenza di tale combinazione, il numero

di combinazioni possibili dei valori di uscita (e quindi di funzioni diverse che si


possono generare) sarà 2 elevato al numero delle righe, che abbiamo detto

essere 2N, quindi 22N.

Quindi il numero totale di funzioni booleane ad un solo valore di uscita di

bit, con n bit di ingresso, è dato da:

n22

questa quantità determina il numero delle diverse possibili combinazioni di un

solo output, che identificano univocamente la funzione booleana a n variabili.

Nell’esempio considerato per n = 3, il numero totale delle funzioni booleane che

si possono definire sarà:

25622 823

==

4.4. Algebra Booleana

L’algebra booleana è definita su un insieme finito di valori (i due valori vero e

falso) che è possibile manipolare attraverso funzioni opportunamente definite. Si

è visto che tali funzioni operano su una o due variabili booleane e producono

come risultato un solo valore, anch’esso booleano.

Gli operatori di base, con cui è possibile costruire qualunque altra funzione di

variabili booleane e che qui tratteremo, sono 3: AND, OR e NOT.

4.4.1 prodotto logico AND

Una prima operazione che andiamo a considerare è quella definita AND: date due

variabili booleane x e y:

x : {0 ; 1}

y : {0 ; 1}

si definisce la funzione AND tra x e y e indicata con:

x � y oppure x and y oppure x y∧

come quella operazione che mettendo in relazione due o più variabili

booleane da come risultato y = 0 se almeno una delle due variabili vale

zero, vale invece 1 se entrambe le due variabili valgono 1.


Ciò significa che se almeno una delle condizioni è falso, il risultato che produce la

funzione booleana AND è falso, mentre per ottenere la condizione vero, le

variabili booleane devono assumere entrambe il valore vero. Possiamo

schematizzare gli output della funzione AND nella seguente tabella di verità

Tabella 4.1: tabella di verità per l’operatore logico AND

x y y0

0 0 0 1 0 0 0 1 0 1 1 1

L’operatore AND, che opera su due variabili, ha una tabella di verità costituita da

4 righe e 3 colonne.

Osserviamo che quando le variabili x e y assumono entrambe il valore zero, ossia

definiscono entrambe la condizione falso, l’operatore AND restituisce come

output la condizione di falso, ossia lo zero perché dovendo essere a zero almeno

una variabile, in questo caso la condizione è rafforzata dal fatto che x e y sono

entrambe nulle, ossia false.

Passando alla seconda riga, essendo x=1 e Y=0, il prodotto logico AND

restituisce ancora il valore zero perché, come da definizione, almeno una

variabile è pari a zero, in questo caso x.

Andando avanti, l’output continuerà ad assumere valori a zero fino a che non si

arriva al caso in cui sia x che y assumono la condizione di vero, ossia sono

entrambe uguali a 1. In questo caso non valendo la condizione che almeno una

delle due variabili sia pari a zero, il prodotto logico AND, non potrà che assumere

valore 1, poiché sia x che y sono entrambe uguali a 1. In sostanza il prodotto

logico AND produce la condizione vera, ossia restituirà il valore 1, quando

saranno contemporaneamente “vere” tutte le variabili che la definiscono.

In alternativa alla tabella di verità, possiamo rappresentare l’output

dell’operatore logico AND con una tabella a doppia entrata di questo tipo:

x\y 0 1

0 0 0 1 0 1

4.4.2 Somma logica OR

date due variabili booleane x e y così definite:

x : {0 ; 1}


y : {0 ; 1}

si definisce la funzione OR tra x e y e indicata con:

x + y oppure x OR y oppure yx ∨

come quella operazione che mettendo in relazione due o più variabili

booleane da come risultato y = 0 se e solo se tutte e due le variabili

assumono valore logico 0, mentre vale 1 se e solo se almeno una delle

due variabili assume valore logico 1.

Anche in questo caso possiamo schematizzare gli output dell’operatore OR nella

seguente tabella di verità:

Tabella 4.2: tabella di verità per l’operatore logico OR.

x y y0

0 0 0

1 0 1 0 1 1 1 1 1

Con riferimento alla prima riga, vediamo che l’output assume il valore 0 poiché

nessuna delle due variabili x e y è vera, mentre con riferimento alle ultime tre

righe della tabella di verità, il valore restituito è sempre 1, perché si è detto che

per l’operatore OR basta che almeno una delle due variabili sia vera.

Anche in questo caso, in alternativa alla tabella di verità, possiamo rappresentare

l’output dell’operatore logico OR con una tabella a doppia entrata di questo tipo:

x\y 0 1

0 0 1 1 1 1

4.4.3 Negazione o Complementazione

Data una variabile booleana x, con x : {0 ; 1} , si definisce operazione NOT

quella operazione unitaria che restituisce il valore logico opposto a

quello della variabile di ingresso. Per rappresentare il complemento di una

variabile x vengono usate varie notazioni: fra le più comunemente usate

ricordiamo:

not (x)

x

x¬


La tabella di verità di questo operatore logico sarà:

Tabella 4.3: tabella di verità per l’operatore logico NOT.

x y0

0 1 1 0

Vediamo allora di considerare alcuni semplici esempi.

Esempio n. 1

Supponiamo di considerare tre variabili booleane x, y e z come al solito definite:

x : {0 ; 1}

y : {0 ; 1}

z : {0 ; 1}

vogliamo eseguire la seguente operazione:

x OR (y AND z)

Innanzitutto avendo tre variabili da relazionare otterremo 8 diversi output dati da

23 = 8.

Nell’eseguire l’operazione, svolgiamo per prima, quella dentro parentesi e poi

l’operazione Or. Per facilitare il procedimento costruiamo la tabella delle possibili

combinazioni di valori assunti da x y e z:

x y z

0 0 0 0 0 1 0 1 0 0 1 0 0 1 1 1 0 0 1 0 1 1 1 0 1 1 1

Con riferimento all’operazione dentro parentesi, (y AND z) e alla prima possibile

combinazione dei valori assunti dalle tre variabili considerate: 000, abbiamo che

l’operazione (y AND z) restituisce il valore 0 perché entrambe non sono vere.

Dovendo ora applicare l’operatore OR, essendo sempre x non vera, infatti x = 0,

si conclude che per quanto riguarda la prima riga della tabella di verità, il valore

restituito dall’operazione sarà:

x OR (y AND z) = 0 per x = 0; y = 0; z = 0


Passando alla seconda riga, l’operatore AND restituisce un output nullo perché

entrambe le variabili non sono pari ad 1, ed essendo ancora x non vera, anche

l’operatore OR darà come risultato finale il valore 0. Questo vale anche per la

terza e quarta riga.

Con riferimento alla quinta riga della tabella, vediamo questa volta che le variabili

x e y sono entrambe vere, per cui l’operatore AND darà 1, a questo punto

l’operatore OR, essendoci almeno una condizione vera – quella restituita dalla

parentesi – darà come risultato un uscita pari a 1. Elenchiamo in una tabella i

diversi risultati dell’operazione considerata, evidenziando per ciascun passaggio i

risultati:

x y z Y AND Z X (OR Y AND Z)

0 0 0 0 0

0 0 1 0 0

0 1 0 0 0

0 1 0 0 0

0 1 1 1 1

1 0 0 0 1

1 0 1 0 1

1 1 0 0 1

1 1 1 1 1

Esempio n. 2

si considera l’operazione:

x AND (Y(NOT z)

anche in questo caso si riporta la tabella di verità:

x y z z Y OR z X AND (Y(OR (NOT Z)

0 0 0 1 1 0

0 0 1 0 0 0

0 1 0 1 1 0

0 1 0 1 1 0

0 1 1 0 1 0

1 0 0 1 1 1

1 0 1 0 0 1

1 1 0 1 1 1

1 1 1 0 0 1

Poiché possiamo avere a che fare con operazioni molto più complicate di quelle

fino ad ora considerate, per gli operatori logici qui considerati, valgono alcune

proprietà che sono molto simili a quelle riguardanti le semplici operazioni

algebriche tra numeri reali.


Per rendere più agevole la comprensione ed avvicinarci in qualche modo alle

operazioni algebriche dei numeri reali, indichiamo col simbolo “•”, l’operatore

logico AND e con “+”, l’operatore logico OR.

4.4.4 Proprietà degli operatori logici e leggi di de Morgan.

Proprietà dell’operatore logico AND

x • 0 = 0

x • 1 = x

x • x = x

x • x = 0

per l’operatore AND il numero 1 rappresenta l’elemento neutro.

Consideriamo ora le proprietà dell’operatore logico OR.

Anche in questo caso per agevolare la comprensione, indichiamo col simbolo “+”

l’operatore OR.

Proprietà dell’operatore logico OR

X + 0 = x

x + 1 = 1

x + x = x

x + x = x

Per quanto riguarda la negazione abbiamo solamente che :

Proprietà dell’operatore logico NOT

xx =

Analogamente per quanto avviene nell’algebra dei numeri reali, anche tra gli

operatori logici valgono le proprietà commutativa, associativa e distributiva. Date

tre variabili boleane x y z:

proprietà commutativa:

x + y = y + x

x • y = y • x

proprietà associativa:


x + (y + z) = (x + y) + z = x + y + z

x • (y • z) = (x • y) • z = x • y • z

proprietà distributiva:

x • (y + z) = x • y + x • z

x + (y • z) = (x +y) • (x + z)

Per quanto riguarda la negazione, riportiamo le due leggi fondamentali, dette

leggi di De Morgan

1) yANDxxORy =

2) yORxxANDy =

Costruiamo la tabella di verità per dimostrare il risultato della prima:

yANDxxORy =

x y xORy xORY

x y yANDx

0 0 0 1 1 1 1

0 1 1 0 1 0 0

1 0 1 0 0 1 0

1 1 1 0 0 0 0

Si vede chiaramente che la quarta e la settima colonna coincidono.

Analogamente per la seconda legge:

yORxxANDy =

x y xANDy x y yORx

0 0 1 1 1 1

0 1 1 1 0 1 1 0 1 0 1 1

1 1 0 0 0 0

Dopo aver elencato tutte le proprietà degli operatori logici fin qua considerati, vediamo consideriamo qualche semplice esempio.

Esempio n. 1

Si consideri la seguente relazione:

x AND ( x OR Y)

che possiamo anche riscrivere:

x • ( x +Y)

Possiamo sfruttare la proprietà distributiva per cui possiamo scrivere :

x • ( x +Y) = (x • x )+ (x • y)


vediamo che per le proprietà elencate prima dell’operatore AND, si ha che

(x • x ) = 0, per cui l’operazione logica scritta si riduce a :

x • ( x +Y) = (x • x )+ (x • y) = 0 + (x • y) = (x • y)

Esempio n. 2

siano tre variabili booleane x, y, z

( x AND y AND z) OR ( x AND y AND z ) OR (x AND z)

anche questa espressione la riscriviamo per comodità nel modo seguente:

( x • y • z) + ( x • y • z ) + (x • z)

Possiamo sfruttare la proprietà distributiva, raccogliendo nei primi due addendi x • y, ottenendo:

( x • y) • (z + z ) + (x • z)

ma (z + z ) = 0, per cui l’espressione si riduce a:

( x • y • z) + ( x • y • z ) + (x • z) = ( x • y) + (x • z)

cerchiamo di visualizzare il risultato con la tabella di verità :

x y z x ( x • y) (x • z) ( x • y)+ (x • z)

0 0 0 1 0 0 0

0 0 1 1 0 0 0

0 1 0 1 1 0 1

0 1 0 1 1 0 1

0 1 1 1 1 0 1

1 0 0 0 0 0 0

1 0 1 0 0 1 1 1 1 0 0 0 0 0

1 1 1 0 0 1 1

Esempio n. 3

Siano tre variabili booleane: x, y, z e si consideri la seguente relazione:

x OR (x AND Y) OR (z AND Y) OR (z AND y )

Che riscriviamo:

x + (x • y) + (z • y) + (z • y )

raccogliamo x nei primi due addendi e z nei secondi due per cui otteniamo :

x • (1 +y) + z (y + y )


(y + y ) = 1 e (1 +y) =1 ‘espressione si riduce a

x • (1 +y) + z (y + y ) = x •1 + z x •1 =x +z

4.5 Funzioni Booleane e circuiti.

Al momento ci siamo soffermati sul definire cosa sia una funzione booleana senza

però dire cosa serva in pratica. La prima cosa da notare è che, come detto in

precedenza, una finzione booleana prende variabili che assumono solo valori di

tipo 0 e 1 e restituisce valori in {0,1}. Nel paragrafo 3.2, si è definita una

funzione booleana:

(y0,y1......ym) = f(x0,x2......xn-1)

come una legge che trasforma n valori di entrata (le variabili booleane) in un

vettore y di uscita.

La funzione così descritta, è un primo esempio di elaborazione, anche se non

basterà modellare così l’elaborazione dei bit, in quanto si dovranno eseguire delle

altre operazioni. Ciò significa che in questa prima impostazione, l’elaborazione

implementata con la funzione booleana, crea una relazione tra un ingresso e

un’uscita, dove la relazione scritta sopra è stata rappresentata con un formato

matematico.

Con la figura che segue, diamo invece una rappresentazione sistemistica

dell’elaborazione come funzione booleana:

Figura 4.1: esempio di elaborazione implementata con una funzione booleana

una qualsiasi funzione booleana può essere rappresentata come dalla figura 4.1

con il seguente significato: esiste una macchina in cui entrano dei bit che

vengono trasformati da una funzione che è a sua volta funzione dei bit entranti,

mentre l’uscita dipende unicamente dai bit in entrata.

La rappresentazione della figura 4.1 viene chiamata Circuito della funzione

booleana. Un circuito è un mezzo di rappresentazione di una funzione booleana

ed è costituito da n linee (fili) in input ed m linee o (fili) di output, tale per cui si

possono associare alle variabili logiche booleane le varie linee in input/output, e i

valori che le variabili possono assumere sono quelli dell’algebra di Boole.


4.6 Porte logiche

Avendo definito una funzione booleana, una funzione su variabili booleane (in 0

ed 1) che restituisce valori in {0,1}, anche gli operatori logici AND,OR e NOT

possono essere considerati tipiche funzioni booleane.

Il circuito della figura 4.1 infatti, calcola una o più funzioni logiche, ciascuna

esprimibile tramite la combinazione delle operazioni dell’algebra di Boole sulle

variabili input, tali operazioni sono quelle viste nel paragrafo 3.4., ossia AND, OR

e NOT.

Analogamente allora a quanto detto nel paragrafo precedente, ciascun operatore

AND, OR e NOT può essere considerato come un oggetto che accetta in ingresso

il valore di una o più variabili, e che come uscita, restituisce il risultato

dell’operazione eseguita sugli ingressi. Suddetti operatori possono essere tra di

loro combinati per formare equazioni logiche più complesse .

Si è anche visto che tali operatori godono delle proprietà algebriche che applicate

a delle proposizioni opportunamente composte in bit, permettono di

automatizzare i ragionamenti riducendoli in termini di vero o falso.

Modellando dunque come operandi le proposizioni AND OR e NOT, si da origine a

delle espressioni booleane, ovvero proposizioni, che possono essere semplificate

come si fa nell’algebra dei numeri reali. Ciò permette ad un elaboratore di

produrre proposizioni implicate da altre proposizioni date in ingresso.

Definiamo allora espressione booleana, una combinazione di variabili booleane

e costanti, definita per mezzo degli operatori logici AND, OR e NOT.

Si diceva che le operazioni elementari AND, OR e NOT, possono anch’esse essere

rappresentate da circuiti che vengono definiti Porte logiche.

Le Porte logiche sono dei circuiti molto semplici che producono come segnale di

uscita, il risultato di un’operazione booleana sui suoi ingressi. Possiamo quindi

considerarle l’implementazione circuitale degli operatori logici booleani.

Ogni porta corrispondente a ciascun operatore, il quale ha un suo corrispondente

simbolo grafico, la cui forma ne identifica il tipo:

Figura 4.2: rappresentazione grafica delle porte logiche AND OR NOT.


Il simbolo è dotato di segmenti che rappresentano gli ingressi e le uscite.

Alla luce di quanto detto, e avendo definito un circuito come una qualsiasi

funzione booleana che lega i dati in ingresso, con gli operatori logici finora visti,

tutti i circuiti possono essere realizzati a partire da queste tre funzioni booleane

di base rappresentate graficamente dalla figura 4.2.

Ad esempio l’espressione booleana:

Y = )( bac +•

è un circuito che possiamo costruire con la seguente figura:

Figura 4.3: esempio di circuito.

c è messo in AND dal risultato di a e b legati in AND.

4.7 Dalle funzioni logiche ai circuiti logici: implementazione.

Con gli strumenti introdotti nei paragrafi precedenti, vedremo come progettare

un circuito attraverso una sequenza di passi successivi. Si parte generalmente da

una descrizione del problema, per arrivare ad un circuito composto dagli elementi

digitali di base, ovvero le porte logiche.

4.7.1 Impostazione formale del problema

Si è visto che esiste una corrispondenza biunivoca tra espressioni logiche e

circuiti logici: per ogni espressione logica può essere realizzata un circuito logico

che la implementi, poiché si è detto che ad ogni operazione elementare

nell’espressione booleana corrisponde nel circuito un operatore rappresentato da

una porta.

Per meglio comprendere questo legame tra funzioni booleane e circuiti,

consideriamo un semplice esempio.

Supponiamo di voler progettare una macchina che faccia l’operazione tra due

numeri codificati con due bit, e supponiamo di considerare numeri interi senza il

segno.

Il problema può essere così schematizzato:


Figura 4.4: schema logico di una somma tra due bit.

Il circuito della figura 4.4. riceve in ingresso il bit a=(a0,a1) che possiamo

immaginare come i due fili di trasmissione del bit a, e allo stesso modo entrerà il

bit b=(b0,b1), mentre in uscita avremo come output la somma dei due numeri

(a+b). Questo che abbiamo appena definito in maniera sistemistica è detto

sommatore, che troviamo dentro un qualsiasi microprocessore anche se con un

maggior numero di bit, in particolare 32.

Si è detto che il problema così impostato, in realtà è una funzione booleana

perché per ogni numero a e b in entrata codificati con due bit, avremo come bit

di uscita sempre e un solo valore y = a + b. Dobbiamo cioè assicurarci che ogni

volta che entra una determinata combinazione di bit si ottenga come risultato di

uscita un’unica configurazione di bit associata a quella combinazione: deve cioè

esserci una corrispondenza biunivoca tra bit in ingresso e bit in uscita.

Il primo passo da fare per progettare una macchina che esegua la somma tra i

due bit a e b è quella di formalizzare il problema impostando una funzione

booleana che implementi il comportamento del circuito.

Dati allora due bit per ciascun bit in ingresso, la funzione sarà:

f(a0,a1,b0,b1) = (y0,y1)

quindi con n=4 variabili booleane, la tabella di verità sarà composta da 24=16

righe, con quattro colonne di dati in ingresso e 2 di uscita

Tabella 4.4: tabella di verità per n=4

a0 a1 b0 b1 y0 y1

0 0 0 0 0 0 0 0 0 1 0 1 0 0 1 0 1 0 0 0 1 1 1 1 0 1 0 0 0 1 0 1 0 1 1 0 0 1 1 0 1 1

0 1 1 1 0 0 1+3 overflow 1 0 0 0 1 0 1 0 0 1 1 1

1 0 1 0 0 0 2+2 overflow 1 0 1 1 0 1 2+3 overflow


1 1 0 0 1 1 1 1 0 1 0 0 3+1 overflow 1 1 1 0 0 1 3+2 overflow 1 1 1 1 1 0 3+3 overflow

le prime due colonne a0,a1, sono la rappresentazione del primo numero di

ingresso -rappresentato con due bit- le seconde due colonne, b0,b1,

rappresentano il secondo numero di ingresso, la cui somma deve dare un numero

rappresentato sempre con due bit pari alla somma dei bit a e b.

Per ottenere le due colonne di uscita, basterà tradurre i bit di ingresso

nell’informazione che essi rappresentano, in questo caso i numeri senza segno,

fare la somma, e di ritradurre la somma così ottenuta in bit con n = 2.

Alla prima riga della tabella, abbiamo la somma dei numeri3 0+0 quindi, come bit

di uscita Y=( y0, y1), avremo il bit che rappresenta la cifra zero.

Alla seconda riga il bit a rappresenta sempre il numero zero perché

(a0,a1)=(00)(2)=0(10), mentre (b0,b1)= (01)(2)=1(10), quindi in base decimale la

somma è 0+1=1: pertanto il bit di uscita (y0,y1), sarà la rappresentazione binaria

a due bit del numero 1, ossia (y0,y1) = (01)(2).

Possiamo procedere fino alla quarta riga copiando semplicemente in uscita i

numeri dati dal bit b, poiché questi sono sempre sommati al bit a che nelle prime

quattro righe della tabella di verità è sempre pari a zero.

Procedendo con la quinta riga, abbiamo:

(a0,a1) + (b0,b1) = 01 + 00 = (y0,y1) = 01

dove 01(2) = 1(10)

Lo stesso ragionamento lo seguiamo per le righe successive stando però attenti

ai casi di overflow, come succede ad esempio all’ottava riga della tabella di

verità: abbiamo infatti (a0,a1)=(01)=1(10) che sommato a (b0,b1)=(11)=3(10),

esegue la somma: 3+1=4 (espressa in base 10), ma avendo solo due bit per la

rappresentazione, sappiamo che possiamo rappresentare solamente 2n-1 cifre,

per cui la più grande cifra che possiamo codificare con due bit è: 22-1 = 3.

Siamo dunque in overflow, in questo caso possiamo ovviare al problema

scegliendo di rappresentare la cifra iniziale, (aritmetica modulare) ossia lo zero,

3In questo caso stiamo considerando dei numeri, però lo stesso ragionamento vale anche nel caso in cui si stiano considerando altri elementi dell’insieme

informativo che potrebbero essere anche di tipo qualitativo e non semplicemente numerico. L’importante è seguire coerentemente il ragionamento della

codifica e decodifica in modo tale che quando si vanno a tabulare le funzioni booleane, i dati in ingresso e quelli in uscita rappresentino in maniera corretta ed

univoca sia le informazioni codificate a priori che quelle in uscita ottenute con l’elaborazione.


che in bit sarà (y0,y1)=(00). Gli altri casi di overflow sono evidenziati nella

tabella 4.4.

Vale la pena di sottolineare che si è deciso di costruire la tabella impiegando

l’algebra modulare in caso di overflow, ma nulla vieta che possiamo utilizzare altri

sistemi di rappresentazione, stabilendo ad esempio che in caso overflow, anziché

azzerare il contatore si riprende la codifica a partire dalla cifra massima

rappresentabile.

Con la tabella 4.4 abbiamo tabulato la funzione booleana di partenza, impostando

così il problema iniziale, che era quello di trovare la funzione somma di due

numeri interi, affrontando le eccezioni in maniera discrezionale, poiché ci sono

varie convenzioni che in questi casi si possono utilizzare; nell’esempio abbiamo

scelto l’algebra modulare.

4.7.2 Dalla tabella di verità all’espressione booleana: sintesi

Arrivati a questo punto, abbiamo progettato a tutti gli effetti il problema che ci

eravamo posti all’inizio, vediamo ora come lo realizziamo all’interno di un

sistema. All’inizio abbiamo visto che in un calcolatore ci sono n bit in ingresso che

vengono a sua volta elaborati mediante funzioni booleane che restituiscono dei

valori in uscita, in realtà le funzioni booleane sono quelle che compongono il

sistema per cui la progettazione di un circuito si intende realizzata quando sono

state individuate le componenti elettroniche che si comportano come un OR,un

AND o un NOT, indipendentemente dalla tecnologia.

Ritornando dunque all’esempio della funzione booleana che somma i due numeri

a e b codificati con due bit, vediamo allora come si costruisce il circuito che va ad

implementare la tabella 4.4 costruita in precedenza. Siamo dunque nella fase di

sintesi: infatti il problema è stato definito completamente individuando gli

elementi base che sono gli operatori logici AND,OR,NOT i quali a sua volta

devono essere interconnessi in modo tale che il circuito che ne viene fuori, pari

ad una funzione booleana, sia equivalente al problema impostato all’inizio.

Il problema di sintesi affronta dunque la fase di realizzazione in circuito della

funzione booleana che descrive il problema iniziale.

Il primo paso che possiamo fare è quello di sfruttare una proprietà dell’operatore

logico AND, che restituisce il valore 1 solamente quando tra le possibili

combinazioni, tutti i bit assumono il valore 1, come ad esempio nella tabella

seguente nel caso di due bit:


x y xANDY

0 0 0 1 0 0 0 1 0 1 1 1

La situazione opposta vale per l’operatore OR , in quanto si è visto che restituisce

il valore 0 solamente quando tra tutte le possibili combinazioni in entrata, tutti i

bit assumono il valore 0

x y xORy

0 0 0

1 0 1 0 1 1 1 1 1

Fatte queste osservazioni, possiamo trattare la tabella 4.4 come composta da

due tabelle di ingresso e uscita tale per cui una evidenzia quanto vale y0 dati

a0,a1,b0,b1, e l’altra quanto vale y1 sempre dati gli ingressi a0,a1,b0,b1, poiché

possiamo considerare y0 e y1 come due funzioni indipendenti.

Detto questo riportiamo allora la tabella 4.4 di ingresso e uscita (che per

comodità viene riportata) e di essa evidenziamo solo l’uscita y0:


Tabella 4.4.

a0 a1 b0 b1 y0

0 0 0 0 0 0 0 0 1 0 0 0 1 0 1 0 0 1 1 1 0 1 0 0 0 0 1 0 1 1 0 1 1 0 1 0 1 1 1 0 1 0 0 0 1 1 0 0 1 1 1 0 1 0 0 1 0 1 1 0 1 1 0 0 1 1 1 0 1 0 1 1 1 0 0 1 1 1 1 1

E di questa, isoliamo i casi in cui y0 vale 1:

Tabella 4.4.a

a0 a1 b0 b1 y0

0 0 1 0 1 0 0 1 1 1 0 1 0 1 1 0 1 1 0 1 1 0 0 0 1 1 0 0 1 1 1 1 0 0 1 1 1 1 1 1

Ciascuna colonna della tabella 4.4.a può essere considerata come un AND e ogni

riga come un OR tale per cui possiamo interpretare ciascuna riga della la tabella

come tante espressioni booleane così impostate:

Y0 = 1 se e solo se

Espressione Y0 = 1

(0 • 0 • 1 • 0) 1

+ (0 • 0 • 1 • 1 ) 1

+ (0 • 1 • 0 • 1 ) 1

+ (0 • 1 • 1 • 0) 1

+ (1 • 0 • 0 • 0) 1

+ (1 • 0 • 0 • 1) 1

+ (1 • 1 • 0 • 0) 1


+ (1 • 1 • 1 • 1) 1

Cerchiamo allora di tradurre in espressione logica ciascuna riga che rende vera la

proposizione Y0=1. Possiamo cioè specificare l’output della funzione così come è

stata tabulata nella tabella 4.4, esprimendo tramite un’espressione booleana,

quali combinazioni delle variabili di input determinano l’output Y0 = 1.

Con riferimento alla prima riga della tabella 4.4.a ad esempio, si legge che Y0=1

quando a0=0 a1=0 b0=1 e b1=0.

La proposizione a0=0, può essere anche intesa che a0 assume il valore zero

quando il suo negato non è 1, ossia vale la seguente uguaglianza:

0=a quando 0a ≠1

Infatti la proposizione a0 è definita vera se a0=1 e falsa se a0=0; se vogliamo

dunque impostare la proposizione a0=0, deve accadere il contrario della

proposizione a0=1, ossia il suo negato 0a . Possiamo dunque sostituire a0 con 0a .

La stesso ragionamento lo facciamo per b0:

00 =b equivale a 10 ≠b

queste condizioni ci permettono allora di dire che la tabella di entrata e uscita per

Y0= 1, è data o dallo stesso valore del bit o il suo negato a seconda che il valore

sia 0 o 1. Alla luce di queste considerazioni, possiamo riformulare la tabella 4.4.a

nel modo seguente:

Tabella 4.4.a1

Espressione Y0 = 1

0a • 1a • b0 • 1b 1

+ ( 0a • 1a • b0 • b1) 1

+ (a0 • a1 • b0 • b0) 1

+ (a0 • a1 • b0 •b1 ) 1

+ (a0• a1 • b0 • 1b ) 1

+ (a0 • a1 • b0 • b1) 1

+ (a0 • a1 • b0 •b1 ) 1

+ (a0 • a1 • b0 • b0) 1


La prima riga evidenzia che Y0 = 1 se e solo se 0a =1 e 1a = 1 e b0 = 1 0b = 1 e

così per tutte le altre righe. Abbiamo cioè negato le variabili che compaiono

come 0 (che danno cioè una condizione di falso) e considerato dirette le

variabili che compaiono come 1 (che danno cioè una condizione di vero).

A questo punto, avendo formulato con un espressione booleana tutti e solo i casi

in cui Y0=1, gli altri casi (Y0=0) sono automaticamente definiti perché impliciti

come proposizione contraria di Y0=1.

Pertanto una volta definito per ciascuna riga della tabella 4.4.a le espressioni

booleane che legano gli ingressi (dati dalle righe della tabella 4.4.a) in modo tale

che Y0=1, si ottiene un’espressione totale che lega in OR ciascuna

sottoespressione corrispondente alle righe della tabella 4.4.a1:

a) Y0 = (0a •

1a • b0• 1b ) + (0a •

1a • b0• b1) + (0a •a1•

0b •1b ) + (

0a •a1•b0• 1b ) +

(a0 • 1a •0b •

1b ) + (a0 • 1a •0b •b1) + (a0 •a1 • 0b •

1b ) + (a0• a1 • b• b1) = 1

questa espressione equivale alla tabella di verità 4.4 per Y0 = 1.

La funzione booleana data dalla a) non è altro cioè che la definizione di Y0 = 1

così come è stata tabulata nella tabella 4.4 per Y0 = 1.

Per verificarlo, consideriamo l’esempio di un ingresso dato dalla sequenza di bit

a0=1 a1=0 b0=0 e b1=0 (1000)4 e sostituiamo questo valore all’espressione a)

vediamo se ciò che si ottiene, è esattamente Y0 = 1.

Con riferimento al primo addendo dell’espressione a): (a0 •a1 • b0 •b0 ), quando

entra un ingresso pari a (1000), l’espressione lo trasforma nel valore di uscita

pari a (0101): infatti il primo e il secondo fattore a0 e a1 negano in ingresso i

primi due bit pari a 10 (a partire da sinistra) della sequenza entrante, portandoli

così a 01.

Il terzo fattore invece, dato da b0, prende direttamente il valore dell’ingresso

senza modificarlo. Infine il quarto fattore della sottoespressione considerata,

nega in ingresso il quarto bit, portandolo da 0 a 1. Ora poiché tutti e quattro i

componenti della sottoespressione (a0 •a1 • b0 •b0 ) sono legati da un operatore

AND, è sufficiente che un solo bit vada a zero per dare come risultato zero.

Riassumendo allora per il primo addendo dell’espressione a):

ingresso 1000 ⇒ (a0 •a1 • b0 •b0 ) ⇒ (0•1•0•1) = 0 (1 addendo)

4 Vedi nona riga della tabella 4.1.


Sempre con riferimento all’ingresso 1000, si segue un analogo ragionamento per

tutti gli altri addendi dell’espressione a), prestando attenzione al quinto addendo:

ingresso 1000 ⇒ (a0 •a1 • b0 • b0) ⇒ (0•1•0•0) = 0 (2 addendo)

ingresso 1000 ⇒ (a0 • a1 • b0 • b0) ⇒ (0•0•1•0) = 0 (3 addendo)

ingresso 1000 ⇒ (a0 • a1 • b0 •b1 ) ⇒ (1•0•0•1) = 0 (4 addendo)


ingresso 1000 ⇒ (a0 • a1 • b0 •b1) ⇒ (1•0•1•1) = 0 (7 addendo)


Si diceva che per il quinto addendo dell’espressione, l’ingresso restituito in uscita

vale 1, infatti:

ingresso 1000 ⇒ (a0 • a1 • b0 •b1) ⇒ (1•1•1•1) = 1 (5 addendo)

ora essendo ora ciascun addendo dell’espressione a) legato dall’operatore logico

OR, è sufficiente che solamente un addendo sia diverso da zero per far si che il

risultato sia pari ad 1.

Riassumendo allora il comportamento di ciascun addendo dell’espressione

booleana a), con un ingresso pari a 1000, avremo:

Y0 = 0 + 0 + 0 + 0 + 1 + 0 + 0 + 0 = 1

che era quello che si voleva verificare.

Ricordando che il problema iniziale era quello di progettare un circuito che

eseguisse la somma tra due numeri senza segno codificati con due bit, possiamo

dunque osservare che il circuito che implementa la funzione booleana data dalla

a) è descritto da tante sottoespressioni che si “attivano”(ossia vanno a 1) solo

nel caso in cui viene richiamata la riga corrispondente che l’ha generata, mentre

tutte le altre vanno a zero.

Pertanto l’espressione a) stabilisce che y0=1 quando si verificano una delle righe

della tabella 4.4.a per y0=1 permettendoci così di trasformare la tabella di verità

4.4 in una funzione booleana.

Lo schema circuitale corrispondente all’espressione a) sarà dato dalla figura

seguente:


a0 a1 b0 b1

1

Figura 4.5: schema circuitale dell’espressione booleana a).

i fili rappresentano i quattro ingressi dati dai bit a e b, ricordando che alcuni

entrano negati, altri invece sono presi diretti. Vediamo inoltre che tutti gli AND

sono legati da un’unica porta OR.

Facendo lo stesso ragionamento per y1, si ottiene un’espressione analoga alla a)

che da origine ad un altro circuito simile a quello della figura 4.5, in cui avremo

un’altra configurazione di porte NOT e AND relazionati in maniera diversa, e tutti

legati da un unico OR.

4.7.3 Ottimizzazione

Abbiamo visto che per la progettazione di un circuito che esegue la somma tra

due numeri codificati con due bit, siamo partiti dalla formalizzazione del problema

impostando la funzione booleana e abbiamo proseguito impostando la tabella di

verità 4.4 evidenziando con essa la relazione tra ingressi ed uscite. Si è infine

passati alla sintesi, passando dalla tabella di verità ad un’espressione booleana

data dalla a) del paragrafo 4.7.2, come rappresentazione funzionale del

problema. Si è tuttavia saltato un passaggio quando si è passati a ricavare lo

schema circuitale dato dalla figura 4.5.

Si è visto infatti che la progettazione del circuito della figura 4.5 è stata “ridotta”

alla ricerca della funzione logica che produce le uscite desiderate in presenza di

certi ingressi. Tuttavia, poiché ci sono molti modi per ottenere la stessa funzione

booleana utilizzando diverse combinazioni di operatori logici elementari, la

soluzione ottima per il progetto sarà quella che non solo rispetta le specifiche del

progetto (cioè realizza correttamente la funzione desiderata), ma che riesce

anche a farlo utilizzando il minor numero di porte logiche. Infatti un circuito


più semplice è più economico e anche più veloce nell’eseguire l’operazione per

cui è stato progettato. Applicando dunque alla a) le proprietà degli operatori

algebrici visti nel paragrafo 4.4.4, possiamo ridurre di molto l’espressione.

Quindi dopo aver fatto la sintesi, è sempre utile semplificare l’espressione

booleana equivalente alla tabella prima di realizzare il circuito, poiché in questo

modo riusciamo ad ottimizzare non solo il numero di relazioni necessarie ad

ottenere il bit di uscita, riducendo di molto le espressioni logiche, ma riduciamo

anche la complessità del circuito logico .

4.8 Forme canoniche

Si è visto che le funzioni booleane, per il fatto di essere funzioni di variabili

binarie, possono essere pensate come ad un elaboratore a sua volta composto da

un elevato numero di circuiti elementari (porte logiche) che realizzano gli

operatori logici di base (AND; OR e NOT)

Quindi la progettazione di una rete logica5 come quella individuata nel paragrafo

4.7, può essere ridotta alla ricerca della funzione logica6 che produce le uscite

desiderate in presenza di certi ingressi. Si è anche detto che ci sono diversi modi

per ottenere la stessa funzione booleana, utilizzando diverse combinazioni di

operatori logici elementari.

Passiamo allora a definire le forme canoniche con cui vengono impostate le

espressioni logiche equivalenti. In particolare esistono due forme canoniche a sua

volta sintetizzate con due diversi circuiti equivalenti: la forma canonica o sintesi

AND OR, e la forma canonica o sintesi OR AND.

4.8.1 Sintesi AND OR

Data una tabella di verità ad n ingressi, vengono impostate tante espressioni

booleane quante sono le corrispondenti combinazioni di ingressi in cui la funzione

logica vale 1, e ciascuna espressione booleana è legata dall’operatore logico OR.

Vediamo con un esempio come otteniamo una sintesi AND OR.

Si consideri una funzione booleana a 3 variabili ad una sola uscita:

y0 = f(x0,x1,x2)

così tabulata :

5Le reti logiche saranno affrontate in maniera più approfondita nel cap. 5

6Per funzione logica si intende funzione booleana.


tabella 4.5

x0 x1 X2 y0

0 0 0 1 0 0 1 1 0 1 0 0 0 1 1 1 1 0 0 1 1 0 1 0 1 1 0 0 1 1 1 0

Si vuole sintetizzare la funzione booleana tabulata dalla tabella di verità 4.5 come

combinazione di porte AND, OR e isolare il valore di y0=1 presente nella tabella,

riducendola così alla tabella di entrata uscita y0=1:

tabella 4.5.a

x0 x1 X2 y0

0 0 0 1 0 0 1 1 0 1 1 1 1 0 0 1

e impostiamo l’espressione logica in modo tale che y0=1 quando si verifica

almeno una delle righe riportate nella nuova tabella. Ciò significa che ci sono

degli operatori OR che legano tante espressioni quante sono le volte in cui y0=1,

ovvero quante sono le righe della tabella 4.5.a, e degli operatori AND in ogni riga

della tabella che legheranno i singoli valori dei bit in ingresso dati da xi.

Analogamente all’esempio precedente, vediamo che per y0=1, la prima riga

viene soddisfatta mettendo in AND i tre valori di x negati; la seconda riga

mettendo in AND i valori negati delle prime due variabili e così via, fino ad

ottenere la seguente espressione logica:

b) Y0 = 0x 1x 2x + 0x 1x 2x + 0x 1x 2x + 0x 1x 1x = 1

i tre addendi legati ciascuno dall’operatore logico OR, sintetizzano le quattro

righe della tabella 4.5.a per y0=1; infatti l’espressione 0x 1x 2x corrisponde alla

prima riga pari a 000 della tabella 4.5.a, 0x 1x 2x equivale alla riga 001 e così

via. La sintesi così ottenuta si chiama sintesi AND OR, proprio per la struttura

del circuito logico che la produce. Graficamente ci saranno quattro uscite AND

legate da un'unica porta OR, come indicato nelle figura seguente:


Figura 4.6: esempio di circuito AND OR con tre ingressi

Se ad esempio consideriamo l’ingresso pari a 001 dato dalla seconda riga della

tabella 4.5.a, significa che mettiamo in ingresso la sequenza di bit

contemporaneamente in tutti e quattro i sottocircuiti della figura 4.6 e di cui uno

solo si attiverà dando come uscita 1 tra le quattro porte AND.

Notiamo dalla figura 4.6, che al primo AND tutte le variabili in ingresso sono

negate, per cui avremo la sequenza contraria di 001, ossia 110, quindi il valore

restituito in uscita dalla prima porta AND della figura è 0.

Alla seconda porta AND della figura 4.6, l’ingresso 001 viene negato alle prime

due variabili, mentre la terza viene presa diretta, per cui si ottiene la sequenza

111 e come output restituito in uscita dalla porta AND, si avrà il valore pari a 1.

Questo perché essendo tutte a 1 le tre variabili legate dall’operatore AND, si è

visto che questo restituisce il valore uno, quando tutte le condizioni sono vere

contemporaneamente, assumono cioè il valore 1.

Arrivati al terzo sottocircuito, osserviamo che il valore di ingresso 001 viene

trasformato, con la negazione alla seconda variabile, nella tripletta di bit 011 e,

poiché in AND basta che uno solo sia a zero perché tutto il resto vada a zero, il

valore restituito in uscita sarà perciò pari a 0.

Infine nell’ultimo sottocircuito il valore di ingresso 001 viene trasformato, con la

negazione nella terza variabile in 000 per cui, ancora una volta, il valore

restituito da AND è 0.

Pertanto i quattro valori restituiti dalle quattro porte AND per la sequenza di

ingresso 001 sarà: 0100.


Ora poiché tutti gli AND sono legati da un OR complessivo di uscita, essendo

sufficiente per l’operatore logico OR, che almeno un risultato sia vero, cioè

uguale a 1, il valore finale di uscita, ossia l’output y0, sarà proprio pari 1, che è

esattamente il valore dell’espressione logica b) impostata inizialmente.

Graficamente, Il circuito della figura 4.6, con l’ingresso pari a 001, si comporterà

nel modo seguente:

x 0 x 1 x 2

1

0

0

1

0

0

1

0

0

1

0

0

1

1

1

0

1

1

1

1

0

1

0

0

0

0

1

0

0

S in te s i A N D O R

Figura 4.7 : esempio di circuito AND OR nel caso di ingresso 001

Osserviamo che questa sintesi così costruita, e definita sintesi AND OR,

funziona perché l’operatore AND, restituisce la condizione vera, se e solo se tutti

i valori che entrano sono veri, ossia uguali a 1, mentre in tutti gli altri casi

restituisce la condizione falsa. Quindi la porta AND del circuito in figura 4.7 viene

in qualche modo ad essere stimolata, solamente quando l’ingresso è dato dalla

sequenza 001, dando così il valore di uscita 1, mentre le altre porte, non

riconoscendo vero l’ingresso 001, a causa delle negazioni anticipate all’entrata

della porta AND, è come se rimanessero spente perché non stimolate; si

potrebbe ad esempio pensare di stimolarle ciascuna delle quattro porte del

circuito con un impulso elettrico pari alla sequenza 001 e che accende la porta

AND solo quando non c’è alcun interruttore, dato dalle negazioni, che impedisce

di attivare la porta.

4.8.2 Sintesi OR AND

Possiamo verificare che anche l’operatore OR ha una proprietà di selezione,

perché si è visto nel paragrafo 4.4.2, che l’operatore OR restituisce sempre 1

tranne il caso in cui entrano solo zeri o condizioni false. Ciò suggerisce che la

rappresentazione AND OR finora vista, non è l’unico modo possibile di fare una


sintesi, ma possiamo usare l’OR come riconoscitore degli ingressi e l’AND

come collettore di tutte le uscite dei riconoscitori. Ricordiamo che l’OR vale

zero se e solo se tutti i valori di ingresso sono a zero, possiamo allora dire che

anche l’OR, come l’AND riconosce un solo caso su tutti.

Con riferimento alla figura 4.6 possiamo invertire l’ordine delle porte,

considerando come prima porta di uscita che lega ciascuno dei tre valori delle

variabili, anziché l’AND come prima, l’operatore logico OR, e prendendo come

valore in entrata il bit pari a 101 che determina, in base alla sesta riga della

tabella 4.5, l’output y0=0, possiamo verificare che con le opportunamente

negazioni davanti, l’uscita OR trasforma la sequenza entrante 101 che genera un

output pari a y0=0, nel valore di uscita pari a 000 che genera un output pari a

y0=1 come si vede nel sottocircuito in figura:

Figura 4.8: esempio funzionamento porta OR nel caso di un ingresso pari a 101

Quindi solo se la sequenza 101 entra nel sottocircuito della figura 4.8, l’OR

restituisce zero, mentre con altri valori di ingresso l’OR restituisce il valore 1.

Sempre con riferimento alla tabella 4.5, in questo caso l’OR restituisce sempre

valore 1, tranne nel caso in cui entra una sequenza che, con gli appositi NOT,

viene trasformata in una sequenza di soli zeri. Pertanto, osservando il

sottocircuito della figura 4.8, l’ingresso 101 è l’unica tripletta di bit che porterà

l’OR, con opportune negazioni anticipate prima dell’applicazione dell’operatore, a

restituire il valore 0.

Possiamo dunque capire che lo stesso circuito AND OR di prima, che sintetizzava

l’uscita y0=1, può essere riformulato in maniera tale che anziché impostare

un’espressione vera solo nei casi in cui si verificano gli ingressi che negati

portano a valori restituiti pari a 1, come appunto accadeva nella sintesi AND OR,

l’espressione sia impostata in maniera tale da riconoscere solo quegli ingressi

che, sempre con le opportune negazioni, danno origine agli zeri invertendo così il

ragionamento che si faceva prima.


Vogliamo cioè rifare lo stesso circuito di prima tale che restituisca gli output di

y=1, invertendo però questa volta le porte: mettendo cioè gli OR al posto degli

AND, e gli AND al posto degli OR. Il circuito diventerà allora:

Figura 4.9: esempio di circuito OR AND con tre ingressi

Quindi ponendo come operatori OR a sua volta legati da un unico AND otteniamo

il circuito dato dalla figura 4.9.

Data una tabella di verità ad n ingressi, nella sintesi OR AND, vengono impostate

tante espressioni booleane quante sono le corrispondenti combinazioni di ingressi

in cui la funzione logica vale 0, e ciascuna espressione booleana è legata

dall’operatore logico AND.

Nella precedente sintesi AND OR, si erano infatti isolate tutte le righe della

tabella di verità 4.5 che riconoscevano y0=1; adesso, nella sintesi OR AND si

tratta di fare esattamente il contrario, e cioè si evidenziano solo quegli ingressi

della tabella 4.5 che danno origine agli zeri, ottenendo così la tabella 4.5.b

tabella 4.5

x0 x1 X2 y0

0 0 0 1 0 0 1 1 0 1 0 0 0 1 1 1 1 0 0 1 1 0 1 0 1 1 0 0 1 1 1 0

isoliamo le righe per cui y0 = 0 ottenendo così la sottotabella:

tabella 4.5.b

x0 x1 X2 y0

0 1 0 0 0 1 1 0 1 0 0 0


1 1 1 0

A questo punto, formuleremo l’espressione booleana in maniera tale che

restituirà il valore 1 quando non si verificherà nessuno dei casi della tabella 4.5.b

appena costruita, ossia quando nessuna riga di ingresso darà y0=0. Stiamo

facendo esattamente l’opposto di quello che si era fatto prima con la sintesi AND

OR.

Tenendo presente quanto detto, partendo dunque dalla prima riga della tabella

4.5.b, imposteremo il primo ingresso pari a 010 con la seguente espressione:

x0+ x1 + x2 = 0 se e solo se x0 = 0; x1 = 1 e x2 = 0

x0+ x1 + x2 = 1 in tutti gli altri casi

Non si è fatto altro che mettere opportunamente la negazione in x1 in maniera

tale da rendere falso il valore di ingresso 010 rispetto a y0=0.

Senza considerare per un attimo gli operatori, abbiamo che la sequenza x0 x1 x2,

indica il valore di ingresso 000 (ingresso vero per y0=1) che va così a “falsare”

rispetto a y0=0 la sequenza entrante 010 della tabella 4.5: infatti le tre variabili

x0 x1 x2 con riferimento all’ingresso 010, sono tali che x0=0, è preso diretto,

x1 =0 è invece stato negato, per cui con questa condizione si è falsata la tripletta

in ingresso 010 rispetto a y0=0, infatti il secondo bit dell’ingresso 010, è 1 e non

zero, ed infine per x2=0, il bit è stato preso diretto e quindi coincidente con il

terzo bit della sequenza entrante 010.

Legando adesso in OR i tre valori delle variabili otteniamo la seguente

sottoespressione:

x0 + x1 + x2 = 0 + 0 + 0 = 0

L’OR restituisce un valore 0, cioè falso, in quanto, ricordando che si sta

impostando il circuito in modo da avere valori di Y0=1, l’ingresso 010, filtrato

dall’espressione sopra scritta, ha prodotto una uscita “falsa” rispetto all’otutput

Y0=0.

Per falsare gli ingressi rispetto Y0=0 (quindi considerando gli ingressi che danno

Y0=1) basta dunque concentrarsi sulle righe che danno un output contrario,

quelle che danno cioè Y0=0, e falsarle opportunamente rispetto a y0=0,

negandole rispetto all’output pari a Y0=0, proprio allo scopo di ottenere uscite

che danno tutti valori veri per Y0=1.


Si costruiscono allora le espressioni relative a ciascuna riga di ingresso, in modo

tale che ogni espressione restituisca 1 (condizione vera per Y0=1) quando

andiamo ad inserire la combinazione di ingressi relativa ad una qualsiasi riga

Y0=1. Una volta impostate le singole espressioni, l’espressione totale dovrà

valere 1, ed essendo ogni riga legata questa volta dall’operatore AND, ciò

accadrà quando tutte le singole sottoespressioni che la compongono, valgono 1.

L’espressione logica per ingressi pari a Y0 = 1 diventa allora:

c) Y0 = (x0 + x1 + x2) � (x0 + x1 + x2 ) � (x0 + x1 + x2) � (x0 + x2 + x1 ) = 1

A partire allora dalla tabella 4.5.b dove sono stati evidenziati gli ingressi tali per

cui Y0=0, negando opportunamente gli ingressi per cui Y0=0, si è ottenuta

l’espressione che coincide con la sottotabella di ingressi tali per cui Y0=1 (tabella

4.5.a)

I quattro fattori della c) essendo composti da bit legati in OR, vanno tutti a 1 solo

in corrispondenza degli ingressi relativi alla sottotabella 4.5.a per Y0=1, mentre

danno tutti valori pari a 0, per ingressi corrispondenti a Y0=0 della tabella 4.5.b,

restituendo 0 come valore finale.

Volendo fare una verifica di quanto detto, considerando ad esempio l’ingresso

001 che da come output Y0=1, notiamo che messo nelle varie espressioni

dell’espressione booleana c), con le opportune negazioni otteniamo i seguenti

risultati:

001 “filtrato” da (x0 + x1 + x2) restituisce 011 quindi (0+1+1)=1

001 “filtrato” da (x0 + x1 + x2 ) restituisce 010 quindi (0+1+0)=1

001 “filtrato” da (x0 + x1 + x2) restituisce 101 quindi (1+0+1)=1

001 “filtrato” da (x0 + x2 + x1 ) restituisce 110 quindi (1+1+0)=1

Ciascuna di queste espressioni danno un’uscita pari a 1, ossia una condizione

vera per Y0=1. Tali valori essendo legati da un’unica porta AND danno 1 come

valore finale di uscita.

La figura seguente descrive il comportamento del circuito nel caso di un ingresso

pari a 001:


x 0 x 1 x 2

S in te s i O R A N D

0

0

1

0

0

1

0

0

1

0

0

1

0

1

1

0

1

0

1

0

1

1

1

0

1

1

1

1

1

Figura 4.10: esempio funzionamento circuito OR AND con ingresso 001

Osservando la figura 4.10, ciascuna porta OR restituisce un uscita pari a 1, ed

essendo ciascuna porta legata da un’unica porta AND, il valore finale che questa

restituisce sarà 1.

Avendo semplicemente invertito gli operatori, si è dunque ottenuto un circuito

che è strutturalmente diverso da quello individuato precedentemente dalla figura

4.6, ma che come risultato da sempre Y0=1.

Ricordiamo che il circuito appena decritto funziona esattamente come il primo

circuito della figura 4.6, perché rispecchia esattamente la tabella degli ingressi

che danno come output Y0 = 1.

Avendo individuato due circuiti che danno lo stesso risultato, vediamo allora che

la scelta del circuito da usare dipende dalla convenienza che si ha nel fare o una

sintesi AND OR o una sintesi OR AND, ossia se ci sono poche uscite Y0=1, ovvero

se il numero di output uguali a 1 è minore del numero di output pari a 0, allora

conviene utilizzare una sintesi AND OR, viceversa se si hanno uscite Y0=0

maggiori del numero di uscite Y0=1, allora conviene usare la sintesi OR AND. Ad

esempio la seguente tabella:

x0 x1 X2 y0

0 0 0 1 0 0 1 0 0 1 0 0 0 1 1 0 1 0 0 0 1 0 1 1 1 1 0 0


1 1 1 0 Suggerisce chiaramente di utilizzare una sintesi AND OR, poiché nella

rappresentazione del circuito logico dovremo impiegare solamente due porte AND

contro le sei porte OR richieste con una sintesi OR AND.

Nel paragrafo si è parlato di ottimizzare le espressioni booleane riducendole il più

possibile attraverso le proprietà degli operatori logici in modo da ottenere

espressioni equivalenti, ma migliori ai fini di una loro implementazione in un

circuito. Si è visto prima che la funzione booleana Y0=1 aveva dato un

espressione logica c) particolarmente elaborata:

c) Y0 = (x0 + x1 + x2) � (x0 + x1 + x2 ) � (x0 + x1 + x2) � (x0 + x2 + x1 ) = 1

come detto, questa può essere notevolmente ridotta. Vediamo allora i vari

passaggi che portano a semplificare tale espressione.

Possiamo intanto partire semplicemente sviluppando il prodotto per esempio dei

primi due fattori:

(x0 + x1 + x2) � (x0 + x1 + x2 ) = x0 x0+ x0 x1 + x0 x2 + x1 x0 + x1 x1 + x1 x2

+ x2 x0 + x2 x1 + x2 x2

le semplificazioni che possiamo fare ricordando le proprietà degli operatori, sono:

x0 x0 = x0 per la proprietà X � X = X

x1 x1 = x1

x0 x1 +x1 x0 = x1 x0 il secondo e quarto addendo sfruttano la proprietà X+X = X

x2 x2 = 0 per la proprietà 0=• xx

per cui l’espressione diventa:

(x0 + x1 + x2) � (x0 + x1 + x2 )=x0+ x1 x0 +x0 x2 +x1 +x1 x2 +x2 x0 +x2 x1

a questo punto possiamo raccogliere ad esempio x0 al primo addendo e x1 al

quarto addendo:

(x0 + x1 + x2) � (x0 + x1 + x2 ) =x0 (1+ x1 ) + x0 x2 + x1 (1+ x2 )+x2 x0+x2 x1

dove

(1+ x1 ) = 1

(1+ x2 ) = 1

quindi l’espressione si riduce ulteriormente:


(x0 + x1 + x2) � (x0 + x1 + x2 ) = x0 + x0 x2 + x1 + x2 x0 + x2 x1

si raccoglie ancora x0 al primo addendo e al secondo addendo x0 x2 e x1 al terzo

e al quinto addendo:

x0(1+ x2 ) + x1 (1+x2) + x2 x0 = x0 + x1 + x2 x0 = x0(1+ x2)+ x1 =x0+ x1

Quindi in totale i primi due fattori si riducono a:

(x0 + x1 + x2) � (x0 + x1 + x2 )= x0+ x1

Per quanto riguarda gli altri fattori dell’espressione totale che riportiamo per comodità:

(x0 + x1 + x2) � (x0 + x1 + x2 ) � (x0 + x1 + x2) � (x0 + x2 + x1 )

e sviluppando gli ultimi due fattori otteniamo con le varie semplificazioni dovute

sempre alle proprietà degli operatori logici, analogamente a quanto fatto prima,

si ottiene un risultato finale pari a

(x0 + x1 + x2) � (x0 + x2 + x1 ) = x0 + x1x2 + x2 x1

Riunendo ora entrambi i risultati ottenuti, ci riduciamo a dover sviluppare questa

ultima espressione:

(x0 + x1x2 + x2 x1 )(x0+ x1 )

che come risultato finale da:

d) x0 x1 + x1x2 x0 + x2 x1

Come si vede chiaramente, l’espressione iniziale c) è stata notevolmente ridotta.

Per verificare la correttezza del risultato, basta semplicemente considerare una

qualsiasi delle righe che danno come output Y0=1 e sostituirle all’espressione

finale, come risultato si ottiene 1.

4.9 Osservazioni

Nel paragrafi precedenti è stata fatta una prima semplice realizzazione di un

circuito che implementa una funzione booleana che somma due numeri codificati

con 2 bit. Quando però si ha a che fare con codifiche che impiegano un numero

elevato di bit, è evidente che la progettazione dei circuiti diventa più complessa

ed elaborata: con riferimento infatti al sommatore del paragrafi precedenti, se

anziché impiegare due bit per la codifica degli addendi, avessimo realizzato un

sommatore sempre a due ingressi, ma ciascuno codificato con 16 bit, ci saremmo


trovati di fronte al problema di dover tabulare una tabella con 32 ingressi e 232

possibili combinazioni di uscite, perché in precedenza si è visto che, dati n

ingressi ciascuno costituito da n bit, esistono n22 diverse possibili combinazioni di

un solo output che identificano univocamente la funzione booleana a n variabili. È

evidente che da un punto di vista pratico, tabulare una tabella di queste

dimensioni, è molto complesso ed elaborato.

Questo ci porta a concludere che i circuiti finora esaminati, risolvono problemi

molto limitati che gestiscono un numero limitato di bit, ma nel momento in cui ci

troviamo di fronte ad un numero elevato di bit, l’impostazione e la tabulazione

delle funzioni logiche diventa oggettivamente complessa.

In questo caso allora si tratta di studiare la struttura del problema, in modo che

di fronte alla sua complessità, si possa scomporre in altri sottoproblemi più

semplici e quindi più facili da gestire e da implementare con circuiti logici.

4.10 Sommatore

Supponiamo di voler eseguire una somma tra due generici numeri a e b

rappresentabili con 7 bit. la somma sarà così rappresentata:

1 1 1 1 1 1 0 riporto

0 1 0 1 1 0 1 ai+ 0 1 1 1 0 1 1 bi= 1 1 0 1 0 0 0

La prima riga rappresenta i riporti (ovviamente per il bit meno significativo il

riporto iniziale è zero).

Con riferimento a questo problema della somma tra due qualsiasi bit, notiamo

che le regole applicate sono in realtà poche: e più precisamente che:

1 + 0 = 1

0 + 1 = 1

1 + 1 = 0 con un riporto di 1

Si tratta dunque di costruire una macchina che, dati ad esempio due ingressi di n

bit, li elabori in maniera tale da restituire un output che corrisponda esattamente

alla somma dei due ingressi. Stiamo cioè progettando un Sommatore.

I sommatori sono dispositivi logici in grado di svolgere la funzione di somma

binaria e di indicare se l'operazione ha generato un riporto ( Carry ).


Supponendo che a e b siano due qualsiasi numeri codificati con n bit, e indicando

con ai e bi la i-esima posizione della cifra rappresentata dalla sequenza di n bit,

un sommatore a n bit viene costruito impostando un sommatore base ad un solo

bit e componendo la somma bit a bit dei numeri a e b.

Avremo che ciascuna cifra occuperà una determinata posizione nella sequenza di

n bit in ingresso: quindi a0 e b0 ad esempio, rappresentano la cifra più a destra

dei numeri a e b. Il circuito sommatore a propagazione è impostato in maniera

tale da sommare ogni singola cifra di posizione i-esima a partire dalla posizione

zero. Guardando l’esempio della somma, i due numeri a e b sono sommati in

colonna bit a bit, a partire dalla prima posizione da destra, eseguendo come

prima somma della posizione zero, 1+1=0. Bisogna considerare anche il riporto

che dovrà essere riportato dal circuito sulla posizione immediatamente

successiva.

Lo schema logico del sommatore ad un bit che stiamo progettando sarà dato

dalla seguente figura:

c i

a i

b i

x i

C i+ 1

+

Figura 4.11: sommatore a un bit con riporto

Tra gli ingressi si considerano i possibili riporti che la funzione somma può dare.

Il riporto viene indicato con ci dove la lettera c è l’iniziale della parola carry. Con

il pedice i indichiamo la posizione i-esima del singolo bit che compone la

sequenza di bit messa in somma, così nell’esempio fatto sopra, indichiamo con

a3 il bit corrispondente alla terza posizione da destra del bit 0101101 sommato al

bit 0111011.

Quindi Il sommatore completo per numeri a 1 bit presenta tre ingressi: due per i

numeri da sommare ed uno indicato con Ci (Carry In) per riprendere l'eventuale

riporto proveniente da uno stadio precedente, e due uscite: la somma xi e il

riporto d'uscita Ci+1.

La tabella di verità del generico sommatore ad un bit sarà:


ai bi ci xi Ci+1

0 0 0 0 0 0 0 1 1 1 0 1 0 1 0 0 1 1 0 1 1 0 0 1 1 1 0 1 0 0 1 1 0 0 0 1 1 1 1 0

La tabella si riferisce ad i-esimo sommatore rappresentato dalla figura 4.11.

Il circuito logico di un sommatore a tre ingressi è rappresentato dalla seguente

figura:

Figura 4.12: sommatore a tre ingressi e due uscite

Ciascun sommatore della figura 4.11, ha tre ingressi formati dai due addendi ai e

bi, più il riporto ci che è stato calcolato nella posizione immediatamente

precedente.

Come si vede dalla figura 4.11, il circuito esegue la somma bit a bit delle due

sequenze entranti a partire dalla posizione più a destra, producendo il primo

risultato x0 posizionato sempre nella prima posizione più a destra della somma, il

ragionamento si estende per tutti gli altri bit che si trovano nella i-esima

posizione, e si ottengono così i singoli risultati xi del bit somma, ricordando

sempre di trasportare l’eventuale riporto nella posizione successiva, che dovrà

essere a sua volta sommato ai due generici bit di posizione i+1.


Quindi il circuito della figura 4.11, è stato impostato in maniera tale che per

l’addizione tra i due numeri (binari) è stata costruita una rete costituita da tanti

sommatori quanti sono i bit dei due addendi. Quindi la somma dei due addendi

rappresentati con n bit è ottenuta mediante n sommatori connessi in modo tale

che l’unità i-esima riceverà in ingresso i due bit corrispondenti all’i-esima cifra

binaria degli addendi e fornirà in uscita il bit i-esimo della somma. Per gestire i

riporti prodotti dalle somme operate su ciascuna coppia di bit, il riporto prodotto

dall’-esimo sommatore viene fornito come riporto in ingresso per il sommatore

i+1-esimo.

Notiamo che questa realizzazione di un circuito sommatore ha il vantaggio di

ridurre il problema della somma tra due numeri a n bit a n somme ad un solo bit

di uscita, facendo attenzione che il riporto prodotto dal generico sommatore i,

venga messo in ingresso al sommatore successivo, mentre lo svantaggio

principale é dovuto alla tecnica di propagazione del riporto. Per avere infatti un

risultato valido in uscita, occorre attendere che il riporto si sia propagato

dall’ingresso fino al bit più significativo, attraversando tutti i sommatori. Pertanto

se si sommano addendi codificati con un elevato numero di bit,si comprende

come il tempo necessario ad effettuare un’operazione di somma con

l’impostazione del circuito della figura 4.11 possa diventare inaccettabile.

Avendo due uscite, la rappresentazione circuitale del sommatore a propagazione

di riporto, si ottiene sintetizzando due reti di cui una relativa al riporto e l’altra

relativa al risultato. Volendo sintetizzare il tutto con il circuito AND OR per xi=1,

otteniamo la seguente figura:

Figura 4.13: struttura del circuito xi

Allo stesso modo sintetizziamo l’output ci+1=0 , ossia i riporti che vengono

propagati nella colonna successiva, impostando questa volta un circuito OR AND,


anche se nell’esempio la scelta tra l’uno e l’altro circuito è indifferente visto che il

numero di ingressi che danno ci+1=0 è uguale al numero di quelli che danno

ci+1=1

Figura 4.14: struttura del circuito ci+1

I circuiti delle due figure 4.13 e 4.14, saranno connessi tra loro, in quanto uno

stesso numero (binario) ai, dovendo il sommatore produrre due uscite, dovrà

passare per i due circuiti che danno rispettivamente xi e ci+1. Ciò significa allora

che all’interno di ogni sommatore della figura 4.12 ci saranno due circuiti del tipo

appena impostato: uno che produce xi e l’altro che produce ci+1, ottenendo così

un sommatore ad n bit.

Questo è un primo esempio di come creare un circuito logico in grado di

effettuare una somma con n bit riducendo, abbiamo visto, il problema da

esponenziale a lineare.

Osserviamo allora o che più circuiti possono essere composti per creare circuiti

più complessi a partire dalle semplici funzioni logiche AND, OR e NOT. Questo fa

si che le porte logiche AND, OR e NOT finora viste, possano essere considerate

gli elementi base di un circuito logico che a sua volta viene inserito in un circuito

più complesso di cui fanno parte, affrontando così gerarchicamente problemi

complessi e dimensionalmente difficili da gestire.

Infatti nel sommatore, si è visto che dopo aver individuato il modo per sommare

bit a bit due numeri binari ad n bit, siamo riusciti ad progettare un nuovo oggetto

che viene a sua volta impiegato come componente di oggetti più complessi.

Questo ha portato ad individuare e comporre, come nel caso del sommatore ad

un bit a propagazione di riporto, degli oggetti più complessi delle singole porte


OR AND e NOT, ma comunque sufficientemente elementari da poter essere

considerati elementi di composizione di circuiti più complessi impiegati a sua

volta in diversi modi. Quindi le porte OR AND e NOT, che consentono comunque

di realizzare virtualmente qualsiasi circuito logico, non sono gli unici componenti

base, ma ce ne sono altri un po’ più complessi di quelli fino ad ora considerati e

che impiegano a sua volta le porte OR AND e NOT. Si è infatti visto un primo

esempio di circuito più elaborato dato dal sommatore con propagazione di riporto.

Nel capitolo successivo vedremo allora come dei semplici circuiti verranno

integrati tra di loro per costituire delle sottocomponenti un po’ più elaborate e di

uso comune.

CAPITOLO 4 - dei.unipd.itpanico/APPUNTI/cap4 - Elaborazione con Reti... · dati in ingresso sono...

Documents

Transcript of CAPITOLO 4 - dei.unipd.itpanico/APPUNTI/cap4 - Elaborazione con Reti... · dati in ingresso sono...