1 0 1 1

Reti logiche:
analisi, sintesi e minimizzazione
Giovedì 9 ottobre 2014
Punto della situazione
• Stiamo studiando le reti logiche costruite a
partire dalle porte logiche AND, OR, NOT per
progettare l’ALU (Unità Logico Aritmetica),
componente essenziale del calcolatore.
• Reti logiche = espressioni booleane
• Obiettivo di oggi: passaggio da rete logica ad
espressione booleana e viceversa
Operatori logici
• Una funzione di variabili binarie e a valore
binario viene detta funzione logica o di
commutazione.
• Ogni funzione logica può essere definita in
termini di semplici operatori logici di 1 o 2
variabili: AND, OR, NOT.
• Esistono però degli altri operatori logici
importanti: XOR, NAND, NOR.
AND ovvero il prodotto
AND(x,y) con x, y variabili che possono assumere valore
Vero o Falso. Risultato Vero se entrambe le variabili sono
poste a Vero, Falso, altrimenti. Interpretando Vero come
1 e Falso come 0.
AND(x,y) corrisponde al prodotto x  y.
AND(F,F) = F
AND(F,V) = F
AND(V,F) = F
AND(V,V) = V
00=0
01=0
10=0
11=1
x
0
0
1
1
y
0
1
0
1
x*y
0
0
0
1
Tavola di verità
OR ovvero la somma
OR(x,y) con x, y variabili che possono assumere valore
Vero o Falso.
Risultato Vero se almeno una variabile è posta a Vero,
Falso, altrimenti.
Interpretando Vero come 1 e Falso come 0
OR(x,y) corrisponde alla somma x + y, in cui 1+1 = 1.
OR(F,F) = F
OR(F,V) = V
OR(V,F) = V
OR(V,V) = V
0+0=0
0+1=1
1+0=1
1+1=1
x
0
0
1
1
y
0
1
0
1
x+y
0
1
1
1
Tavola di verità
NOT ovvero la negazione
NOT(x) con x variabile che può assumere valore Vero o
Falso.
Risultato Vero se la variabile è posta a Falso;
Falso, altrimenti.
Interpretando Vero come 1 e Falso come 0
NOT(x) corrisponde alla negazione.
NOT(V) = F
NOT(F) = V
0 =1
1=0
x
0
1
x
1
0
La combinazione delle variabili e degli operatori
viene chiamata espressione logica.
Mappa di verità o tavola di verità: tabella che
definisce i valori dell’output per ogni possibile input
Espressione SOP
Letterale = variabile o la sua negazione
• Un’espressione booleana è in forma normale SOP
(Sum Of Products) quando è l’OR/somma di
AND/prodotto di letterali
x1 x2 x3  x1 x3  x1 x3
• Mintermine = prodotto di letterali in cui compare ogni
variabile o vera o negata
• Una espressione normale SOP è in forma canonica SOP
se i suoi termini sono tutti mintermini
x1 x2 x3  x1 x2 x3  x1 x2 x3
Scambiando Somma con Prodotto si definiscono le
espressioni POS
Espressione POS
Letterale = variabile o la sua negazione
• Un’espressione booleana è in forma normale POS
(Product Of Sums ) quando è il prodotto (AND) di
somme (OR) di letterali
( x2  x3 )( x1  x3 )
• Maxtermine = somma di letterali in cui compare ogni
variabile o vera o negata
• Una espressione normale POS è in forma canonica POS
se i suoi termini sono tutti maxtermini
( x1  x2  x3 )( x1  x2  x3 )
Rete logica
Una rete logica è un’interconnessione di porte
logiche AND, OR, NOT, in modo che ogni uscita
da una porta alimenti al più un ingresso di una
porta
Risultati principali
Corrispondenza fra funzioni logiche e reti logiche:
• Per ogni funzione logica possiamo costruire una rete
logica che la realizza e viceversa
• Ogni funzione logica può essere espressa in termini
soltanto di AND, OR, NOT.
Analisi: data una rete determinare la funzione
calcolata
Sintesi: data una funzione logica costruire una rete
che la calcola
Analisi di una rete: dalla rete alla funzione
• Ogni rete logica calcola una funzione booleana
dei suoi ingressi
f(x1,x2,x3) = x3 ( x1 . x2) + (x1+x3)
Analisi e Sintesi di reti
• Analisi è abbastanza semplice:
– Calcola per ogni porta logica di cui sono specificati
tutti gli input l’espressione booleana associata
all’output
• Fino ad ottenere l’espressione associata al terminale d’uscita
della rete
•
1.
2.
3.
Vediamo ora la sintesi di una funzione logica f:
Da f alla tavola di verità
Dalla tavola di verità all’espressione «SOP»
Dall’espressione «SOP» ad una rete a due stadi: il primo di
porte AND, il secondo con una sola porta OR
Tavole di verità di mintermini
Per ogni mintermine, la tavola di verità ha un solo valore 1.
Per esempio:
se f = x3 x2 x1 allora avrà un solo 1 in corrispondenza di x3=0, x2=1,
x1=1.
• Ricorda:
x3 x2 x1 f
• Il prodotto è 1 sse ogni fattore è 1
0 0 0 0
Viceversa, se la tavola di verità di f ha un
solo valore 1 necessariamente f è un
mintermine.
0
0
1
0
0
1
0
0
0
1
1
1
1
0
0
0
1
0
1
0
1
1
0
0
1
1
1
0
f = x3 x2 x1
Dalla tavola di verità alla SOP
Se invece la tavola di verità ha più occorrenze di 1:
f ha valore 1 se:
x3 x2 x1 f
x3=0, x2=1, x1=1 oppure
0 0 0 0
x3=1, x2=0, x1=1
0 0 1 0
Espressione SOP
0 1 0 0
0
1
1
1
1
0
0
0
1
0
1
1
1
1
0
0
1
1
1
0
x 3 x2 x1
x 3 x2 x1
f = x3 x2 x1 + x3 x 2 x1
1. Per ogni 1 nella tavola di verità trovare il
mintermine corrispondente
2. Sommare i mintermini ottenuti
Esercizio (maggioranza)
Sia f(x,y,z) la funzione che vale 1 se (e solo se) la
maggioranza delle variabili vale 1.
Effettuare la sintesi di f:
1. Da f alla tavola di verità
2. Dalla tavola di verità all’espressione SOP
3. Dall’espressione SOP ad una rete a due stadi: il
primo di porte AND, il secondo con una sola
porta OR
Dalla tavola di verità alla SOP: esempio 1
Supponiamo di avere una funzione f data
tramite la sua tavola di verità
Espressione SOP
Dalla tavola di verità alla SOP: esempio 2
Dalla tavola di
verità
all’espressione
SOP
Espressione SOP
Dall’espressione
canonica SOP alla
rete a due livelli SOP
/AND-to-OR: nel
primo livello varie
porte AND, nel
secondo livello solo
una porta OR
Nota
Nota: le porte sono state estese in modo da poter avere più di 2 ingressi
Minimizzazione di reti combinatorie
Sinonimi:
Reti logiche, reti combinatorie
Funzioni logiche, funzioni di commutazione
Valutazione delle Prestazioni di una Rete
Combinatoria
25
• Per ogni funzione di commutazione esistono
diverse reti combinatorie che la realizzano
– Qual è la migliore?
• Quella che ha le migliori prestazioni
• Le prestazioni di una rete combinatoria vengono
misurate in termini di
– Velocità
– Costo
• Esiste una tecnica che ci permette di sintetizzare la
rete in modo da massimizzare le prestazioni?
Velocità di una Rete Combinatoria
26
• La velocità della rete viene misurata calcolando il tempo che
passa da quando i segnali sono disponibili sui terminali di
input a quando un segnale è disponibile sul terminale di
output
• Quando un segnale attraversa una porta logica subisce un
piccolo ritardo
• La velocità di una rete dipende dal massimo numero di porte
logiche che un segnale deve attraversare per andare da un
terminale di input al terminale di output
• Faremo sempre riferimento a reti a due livelli
– Sono le più veloci tra quelle che possono realizzare qualsiasi funzione
– Le reti ad un livello possono realizzare un insieme molto limitato di
funzioni
Costo di una rete/espressione logica
27
• Il costo della rete dipende da
– Numero di porte logiche
– Numero di linee di input
• Tra tutte le reti AND-to-OR (SOP) che realizzano una
certa funzione di commutazione una rete è minimale se
– Ha il minor numero di porte AND
– Tra tutte quelle che hanno il minor numero di porte AND ha
il minor numero di linee di input
• Un’espressione in forma normale SOP è minimale se
– Ha il minor numero di termini prodotto possibile
– Tra tutte le espressioni equivalenti che hanno il minor
numero di prodott,i ha il minor numero di letterali
28
Minimizzazione di espressioni booleane
• La minimizzazione di espressioni booleane non è
un processo semplice e diretto. Si possono
utilizzare le regole contenute nella seguente
tabella.
• Per poche variabili invece è possibile utilizzare la
Mappa di Karnaugh per semplificare il processo
– una rappresentazione particolare delle tavole di verità
che consente di individuare facilmente i mintermini
adiacenti
– Utile fino a 4 variabili
Esercizio: verificare che (x+y)(x+z) = x+yz confrontando le rispettive tavole di
verità
Esempi
Esempio 1
Applicando la proprietà distributiva e del complemento si ha:
x1 x2 x3 x4  x1 x2 x3 x4  x1 x2 x3 ( x4  x4 )  x1 x2 x3
Esempio 2
Applicando le leggi di De Morgan si dimostra:
f  x2 x4  x1 x3
𝑓= x2 x4  x1 x3  x2 x4  x1 x3  ( x2  x4 )( x1  x3 )
Esercizio (SOP)
Determinare l’espressione canonica SOP della
funzione definita dalla seguente tavola di verità
x2
x1
f
0
0
1
0
1
0
1
0
1
1
1
0
Esercizio (POS)
Determinare l’espressione canonica POS della
funzione definita dalla seguente tavola di verità
x2
x1
f
0
0
0
0
1
1
1
0
0
1
1
1
Suggerimento: usare le leggi di De Morgan
Risultati principali
Corrispondenza fra funzioni logiche e reti logiche:
• Per ogni funzione logica possiamo costruire una rete
logica che la realizza e viceversa
• Ogni funzione logica può essere espressa in termini
soltanto di AND, OR, NOT.
Analisi: data una rete determinare la funzione
calcolata
Sintesi: data una funzione logica costruire una rete
che la calcola
Riepilogo e riferimenti
• Analisi e sintesi di rete logiche
[PH] appendice C.1, C.2, C.3
[P] par. 4.1, 4.2, 4.3.
La prossima volta: la minimizzazione con le
mappe di Karnaugh [P] par. 4.4

Download Report