Post on 18-Feb-2019
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
Università degli studi di Padova - Facoltà di Scienze Statistiche Corso di Laurea in Gestione delle Imprese – “Sistemi di Elaborazione” Prof . Nicola Zingirian 94
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.
Università degli studi di Padova - Facoltà di Scienze Statistiche Corso di Laurea in Gestione delle Imprese – “Sistemi di Elaborazione” Prof . Nicola Zingirian 95
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
Università degli studi di Padova - Facoltà di Scienze Statistiche Corso di Laurea in Gestione delle Imprese – “Sistemi di Elaborazione” Prof . Nicola Zingirian 96
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
Università degli studi di Padova - Facoltà di Scienze Statistiche Corso di Laurea in Gestione delle Imprese – “Sistemi di Elaborazione” Prof . Nicola Zingirian 97
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
Università degli studi di Padova - Facoltà di Scienze Statistiche Corso di Laurea in Gestione delle Imprese – “Sistemi di Elaborazione” Prof . Nicola Zingirian 98
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.
Università degli studi di Padova - Facoltà di Scienze Statistiche Corso di Laurea in Gestione delle Imprese – “Sistemi di Elaborazione” Prof . Nicola Zingirian 99
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}
Università degli studi di Padova - Facoltà di Scienze Statistiche Corso di Laurea in Gestione delle Imprese – “Sistemi di Elaborazione” Prof . Nicola Zingirian 100
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¬
Università degli studi di Padova - Facoltà di Scienze Statistiche Corso di Laurea in Gestione delle Imprese – “Sistemi di Elaborazione” Prof . Nicola Zingirian 101
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
Università degli studi di Padova - Facoltà di Scienze Statistiche Corso di Laurea in Gestione delle Imprese – “Sistemi di Elaborazione” Prof . Nicola Zingirian 102
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.
Università degli studi di Padova - Facoltà di Scienze Statistiche Corso di Laurea in Gestione delle Imprese – “Sistemi di Elaborazione” Prof . Nicola Zingirian 103
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:
Università degli studi di Padova - Facoltà di Scienze Statistiche Corso di Laurea in Gestione delle Imprese – “Sistemi di Elaborazione” Prof . Nicola Zingirian 104
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)
Università degli studi di Padova - Facoltà di Scienze Statistiche Corso di Laurea in Gestione delle Imprese – “Sistemi di Elaborazione” Prof . Nicola Zingirian 105
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 )
Università degli studi di Padova - Facoltà di Scienze Statistiche Corso di Laurea in Gestione delle Imprese – “Sistemi di Elaborazione” Prof . Nicola Zingirian 106
(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.
Università degli studi di Padova - Facoltà di Scienze Statistiche Corso di Laurea in Gestione delle Imprese – “Sistemi di Elaborazione” Prof . Nicola Zingirian 107
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.
Università degli studi di Padova - Facoltà di Scienze Statistiche Corso di Laurea in Gestione delle Imprese – “Sistemi di Elaborazione” Prof . Nicola Zingirian 108
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:
Università degli studi di Padova - Facoltà di Scienze Statistiche Corso di Laurea in Gestione delle Imprese – “Sistemi di Elaborazione” Prof . Nicola Zingirian 109
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
Università degli studi di Padova - Facoltà di Scienze Statistiche Corso di Laurea in Gestione delle Imprese – “Sistemi di Elaborazione” Prof . Nicola Zingirian 110
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.
Università degli studi di Padova - Facoltà di Scienze Statistiche Corso di Laurea in Gestione delle Imprese – “Sistemi di Elaborazione” Prof . Nicola Zingirian 111
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:
Università degli studi di Padova - Facoltà di Scienze Statistiche Corso di Laurea in Gestione delle Imprese – “Sistemi di Elaborazione” Prof . Nicola Zingirian 112
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:
Università degli studi di Padova - Facoltà di Scienze Statistiche Corso di Laurea in Gestione delle Imprese – “Sistemi di Elaborazione” Prof . Nicola Zingirian 113
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
Università degli studi di Padova - Facoltà di Scienze Statistiche Corso di Laurea in Gestione delle Imprese – “Sistemi di Elaborazione” Prof . Nicola Zingirian 114
+ (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
Università degli studi di Padova - Facoltà di Scienze Statistiche Corso di Laurea in Gestione delle Imprese – “Sistemi di Elaborazione” Prof . Nicola Zingirian 115
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.
Università degli studi di Padova - Facoltà di Scienze Statistiche Corso di Laurea in Gestione delle Imprese – “Sistemi di Elaborazione” Prof . Nicola Zingirian 116
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) ⇒ (0•1•1•0) = 0 (6 addendo)
ingresso 1000 ⇒ (a0 • a1 • b0 •b1) ⇒ (1•0•1•1) = 0 (7 addendo)
ingresso 1000 ⇒ (a0 • a1 • b0 • b0) ⇒ (1•0•0•0) = 0 (8 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:
Università degli studi di Padova - Facoltà di Scienze Statistiche Corso di Laurea in Gestione delle Imprese – “Sistemi di Elaborazione” Prof . Nicola Zingirian 117
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
Università degli studi di Padova - Facoltà di Scienze Statistiche Corso di Laurea in Gestione delle Imprese – “Sistemi di Elaborazione” Prof . Nicola Zingirian 118
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.
Università degli studi di Padova - Facoltà di Scienze Statistiche Corso di Laurea in Gestione delle Imprese – “Sistemi di Elaborazione” Prof . Nicola Zingirian 119
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:
Università degli studi di Padova - Facoltà di Scienze Statistiche Corso di Laurea in Gestione delle Imprese – “Sistemi di Elaborazione” Prof . Nicola Zingirian 120
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.
Università degli studi di Padova - Facoltà di Scienze Statistiche Corso di Laurea in Gestione delle Imprese – “Sistemi di Elaborazione” Prof . Nicola Zingirian 121
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
Università degli studi di Padova - Facoltà di Scienze Statistiche Corso di Laurea in Gestione delle Imprese – “Sistemi di Elaborazione” Prof . Nicola Zingirian 122
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.
Università degli studi di Padova - Facoltà di Scienze Statistiche Corso di Laurea in Gestione delle Imprese – “Sistemi di Elaborazione” Prof . Nicola Zingirian 123
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
Università degli studi di Padova - Facoltà di Scienze Statistiche Corso di Laurea in Gestione delle Imprese – “Sistemi di Elaborazione” Prof . Nicola Zingirian 124
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.
Università degli studi di Padova - Facoltà di Scienze Statistiche Corso di Laurea in Gestione delle Imprese – “Sistemi di Elaborazione” Prof . Nicola Zingirian 125
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:
Università degli studi di Padova - Facoltà di Scienze Statistiche Corso di Laurea in Gestione delle Imprese – “Sistemi di Elaborazione” Prof . Nicola Zingirian 126
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
Università degli studi di Padova - Facoltà di Scienze Statistiche Corso di Laurea in Gestione delle Imprese – “Sistemi di Elaborazione” Prof . Nicola Zingirian 127
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:
Università degli studi di Padova - Facoltà di Scienze Statistiche Corso di Laurea in Gestione delle Imprese – “Sistemi di Elaborazione” Prof . Nicola Zingirian 128
(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
Università degli studi di Padova - Facoltà di Scienze Statistiche Corso di Laurea in Gestione delle Imprese – “Sistemi di Elaborazione” Prof . Nicola Zingirian 129
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 ).
Università degli studi di Padova - Facoltà di Scienze Statistiche Corso di Laurea in Gestione delle Imprese – “Sistemi di Elaborazione” Prof . Nicola Zingirian 130
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à:
Università degli studi di Padova - Facoltà di Scienze Statistiche Corso di Laurea in Gestione delle Imprese – “Sistemi di Elaborazione” Prof . Nicola Zingirian 131
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.
Università degli studi di Padova - Facoltà di Scienze Statistiche Corso di Laurea in Gestione delle Imprese – “Sistemi di Elaborazione” Prof . Nicola Zingirian 132
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,
Università degli studi di Padova - Facoltà di Scienze Statistiche Corso di Laurea in Gestione delle Imprese – “Sistemi di Elaborazione” Prof . Nicola Zingirian 133
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
Università degli studi di Padova - Facoltà di Scienze Statistiche Corso di Laurea in Gestione delle Imprese – “Sistemi di Elaborazione” Prof . Nicola Zingirian 134
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.