Appunti esame Architettura degli elaboratori (1 anno)

IN IN OUT

e 1 in {0,1} abbiamo Somma(0,0,1)=1 e Riporto(0,0,1)=0. Una

tavola di verità è una tabella che rappresenta una funzione logica,

elencandone i valori per ogni combinazione delle variabili (n variabili

n

= 2 configurazioni). Riprendendo l’esempio dell’addizionatore,

possiamo costruire le tabelle di verità delle due funzioni logiche

Somma e Riporto.

Le funzioni di una

variabile f: {0,1}

→ {0,1} danno in output 4 tipi di funzioni logiche: x f f f f

0 1 2 3

f e f sono rispettivamente le funzioni costanti 0

0 3 0 0 0 1 1

e 1, f è detta funzione identità mentre infine f è

1 2

detta funzione NOT(x)= in quanto è uguale al

1 0 1 0 1

complemento delle variabili. Il discorso cambia 2

per le funzioni di due variabili f: {0,1} → {0,1}, che danno in output ben 15 tipi

diversi di funzioni.

Le funzioni logiche più importanti sono le funzioni NOT, AND e OR e tali

funzioni, anche dette “funzioni booleane”, sono realizzate da semplici

dispositivi fisici o porte logiche.

La funzione NOT(x), con variabile x che può assumere valore Vero o

Falso, dà come risultato Vero solo quando la variabile è posta a Falso

altrimenti è Falso: interpretando Vero come 1 e Falso come 0, NOT(x)

corrisponde alla negazione di x e quindi NOT(V)=F e NOT(F)=V.

Rappresentazione grafica La

delle porte logiche funzione AND(x,y), con

variabili x e y che possono assumere valore Vero o Falso, dà

come risultato Vero solo se entrambe le variabili sono poste a

Vero altrimenti è Falso: interpretando Vero come 1 e Falso come

0, AND(x,y) corrisponde al prodotto x·y e quindi AND(F,F)=F,

AND(F,V)=F, AND(V,F)=F e AND(V,V)=V.

Infine la funzione OR(x,y), con variabili x e y che possono assumere valore Vero o Falso, dà come

risultato Vero solo se almeno una variabile è posta a Vero

altrimenti è Falso: interpretando Vero come 1 e Falso come 0,

OR(x,y) corrisponde alla somma logica x+y e quindi

OR(F,F)=F, OR(F,V)=V, OR(V,F)=V e OR(V,V)=V.

Una rete logica, o combinatoria, è un insieme di porte logiche

e corrisponde a un dispositivo fisico il

cui comportamento in output dipende

solo dall’input (viene definita

induttivamente): se i terminali di input

N e N sono reti combinatorie, allora lo

1 2

sono anche i terminali di output.

Inoltre, possiamo ottenere reti logiche complesse mediante la combinazione di reti più semplici.

A ogni rete combinatoria è associata un’espressione “booleana”

composta da variabili e costanti (definite in modo induttivo) e

viceversa: se E e E sono espressioni booleane allora lo sono

1 2

anche e . Ogni rete logica calcola una funzione

, , + ∙

1 2 1 2 1 2

booleana dei suoi ingressi e il processo di calcolo della funzione

associata alla rete si chiama “analisi della rete”, che consiste nel

calcolare per ciascuna porta logica l’espressione booleana

associata al suo output fino ad ottenere l’espressione associata al

terminale d’uscita della rete. Tuttavia per ogni funzione booleana possiamo costruire più di una

rete logica che la realizza, non tutte equivalenti in termini di prestazioni: il processo di costruzione

della rete logica si chiama sintesi della rete, mentre il processo di minimizzazione consente di

ottenere la rete logica con prestazioni migliori.

L’algebra di Boole, introdotta nel 1874 da George Boole, fornisce una rappresentazione algebrica

della logica binaria e nel 1936 Claude Shannon la applica per la prima volta allo studio delle reti di

commutazione telefonica: l’algebra di Boole infatti è detta anche “algebra di commutazione”

perché è molto utile per modellare il funzionamento dei circuiti

elettronici. L’algebra di Boole consiste in un insieme di espressioni

booleane, contenenti le costanti 0 e 1, su cui sono definite due

operazioni binarie AND e OR (con le proprietà commutativa,

associativa, di idempotenza, di assorbimento e di distributività reciproca) e un’operazione unaria

NOT (con le proprietà di involuzione, del complemento e le leggi di De Morgan). Le costanti 0 e 1

godono di alcune proprietà particolari e ciascuna espressione assume il valore 0 o il valore 1 per

ogni assegnazione delle costanti alle variabili (assioma).

Sintesi di reti logiche e minimizzazione

La sintesi di una rete logica, ossia il processo di costruzione della rete, consiste appunto nel

costruire una prima rete logica che realizza la funzione a partire da un tipo particolare di

espressione booleana (“forma canonica SOP”) che descrive la funzione. Infatti un’espressione

booleana, ossia quindi una combinazione di variabili booleane (una variabile che può assumere

solo i valori 1, cioè Vero, e 0, cioè Falso) e operatori booleani (come gli operatori AND, OR e

NOT), denota una funzione logica.

Un’espressione booleana è in forma normale SOP (Sum Of Products, ossia somma di prodotti)

quando è l’OR di AND di letterali (una variabile o la sua negazione), come .

+ +

1 2 3 1 3 1 3

Un’espressione normale SOP è in forma canonica SOP se i suoi termini sono tutti mintermini,

ossia prodotti di letterali in cui compare

ogni variabile o vera o negata, come

+ + .

1 2 3 1 2 3 1 2 3

Un’espressione booleana può essere

ridotta a una forma normale SOP

applicando la proprietà distributiva,

sciogliendo tutte le parentesi, e/o

eliminando i termini ridondati, usando le

proprietà di idempotenza e del

complemento.

Al contrario, per ridurre un’espressione booleana in forma normale SOP a una forma canonica

SOP bisogna applicare la proprietà distributiva per scogliere le parentesi, eliminare i termini

ridondanti usando le proprietà di idempotenza e

del complemento e infine se un termine prodotto

non contiene il letterale di lo posso

moltiplicare per per la proprietà del

( + )

complemento.

Supponiamo di avere una funzione logica f, per

risalire ad una rete logica che la realizza è

necessario seguire una serie di passaggi:

costruire la tavola di verità della funzione f,

ricavare dalla tavola di verità l’espressione in

forma canonica SOP e infine risalire ad una rete a due livelli, in cui il primo livello è composto da

porte AND tante quanti sono i mintermini mentre il secondo livello da una sola porta OR.

Se la funzione logica è un mintermine, allora la

sua tavola di verità ha un solo 1 e,

viceversa, se la tavola di verità di f ha un solo 1

necessariamente f è un mintermine. Ad esempio, se f =

, la sua tavola di verità ha un solo 1 in corrispondenza

3 2 1

di x =0, x =1 e x =1 perché il prodotto (AND) è 1 se ogni

3 2 1

fattore è 1. Se invece la tavola di verità ha più occorrenze di

1, bisogna trovare i mintermini corrispondenti e ne facciamo la

somma (OR). Ad esempio se f ha valore 1 per x =0, x =1,

3 2

x =1 e per x =1, x =0, x =1, l’espressione canonica SOP di f

1 3 2 1

sarà f (x , x , x ) = .

+

1 2 3 3 2 1 3 2 1

Sappiamo che, data una funzione logica, esistono molte reti diverse che la realizzano e non tutti

equivalenti in termini di prestazioni, Tuttavia, anche se dalla tavola di verità si ottiene una rete a

due livelli, non necessariamente si tratta di quella di costo minimo: grazie al processo di

minimizzazione, possiamo realizzare una funzione con un numero minore di porte logiche e quindi

di conseguenza una rete logica con prestazioni migliori. Le prestazioni di una rete logica vengono

misurate in termini di velocità e costo. La velocità di una rete si misura calcolando il tempo che

passa da quando i segnali sono disponibili sui terminali input a quando un segnale è disponibile

sul terminale di output e dipende dal massimo numero di porte logiche che un segnale deve

attraversare da input a output (quando un segnale attraversa una porta logica subisce un piccolo

ritardo): le reti a due livelli (AND-to-OR) sono le più veloci tra quelle che possono realizzare

qualsiasi funzione. Il costo della rete invece dipende dal numero di porte logiche e dal numero di

linee di input e quindi, tra tutte le reti AND-to-OR che realizzano una funzione logica f, una rete è

minimale se ha il minor numero di porte AND e contemporaneamente anche il minor numero di

linee di input a quelle porte: un’espressione in forma normale SOP è minimale se ha il minor

numero di termini prodotto possibile e il minor numero di letterali.

La minimizzazione di espressioni booleane, la tecnica che quindi ci permette di sintetizzare la rete

in modo da massimizzare le prestazioni, non è un processo semplice e diretto in quanto vengono

sfruttate le proprietà dell’algebra booleana. Se le variabili sono poche (massimo 4 variabili), è

possibile utilizzare la Mappa di Karnaugh, una rappresentazione particolare delle tavole di

verità che consente di semplificare il processo. Un’espressione in forma canonica SOP

che contiene due mintermini adiacenti, cioè due mintermini che differiscono di una sola

variabile, può essere minimizzata mettendo in evidenza la variabile che si presenta sia in

forma vera che in forma negata in modo da sfruttare la proprietà del complemento: ad

esempio, se minimizziamo +

4 3 2 1

, otteniamo

+

4 3 2 1 4 3 2 1 e

( )

= + =

4 3 2 1 4 3 2 1 1 4 3 2

così da 2 prodotti e 8 occorrenze di

letterali siamo passati a 1 prodotto e 3 letterali.

Facendo un altro esempio, se f(x ,x ,x ) sia

1 2 3

una funzione che vale 1 se e solo se la maggioranza delle variabili vale 1, dalla tavola di verità si

ha , da cui si ottiene una rete con 4 porte AND a

( )

, , = + + +

1 2 3 3 2 1 3 2 1 3 2 1 3 2 1

3 ingressi ciascuna e 1 porta OR a 4 ingressi. Applicando le proprietà

di idempotenza e del complemento, semplifichiamo la funzione

booleana riducendo i due mintermini che differivano solo in 1 variabile:

si ha quindi che ( )

, , = + + + =

1 2 3 3 2 1 3 2 1 3 2 1 3 2 1

, da cui invece si ottiene una rete con 3 porte AND a

+ +

2 1 3 1 3 2

2 ingressi ciascuna e 1 porta OR a 3 ingressi.

Ogni funzione logica o di commutazione, ossia