Università degli Studi dell’Insubria Dipartimento di Scienze Teoriche e Applicate
Architettura degli elaboratori
Il Livello Logico-Digitale Funzioni e Reti Combinatorie
Marco Tarini
Dipartimento di Scienze Teoriche e Applicate marco.tarini@uninsubria.it
Espressioni booleane
Una espressione booleanacontiene una o più variabili booleane,
operatori booleani prodotto (AND), somma (OR) e negaz (NOT):
es: \A B + C
Dando dei valori alle variabili booleane dell’espressione, e calcolando, si ottiene un valore risultante
Una data espressione booleana (con N variabili) esprime una funzione booleana(o funzione logica)
una funzione che va da: N booleani (parametri) a: un booleano Una funzione booleana si può definire tabellandola esaustivamente
cioè specificando il valore della funzione
per ciascuna combinazione dei valori 0,1 dei suoi parametri (la sua tavola di verità) (o tabella delle verità)
ogni tabella diversa rappresenta una funzione diversa
Funzioni e circuiti combinatori
Architettura degli elaboratori - 3 -
Tabella (o tavola) delle verità
La tabella delle verità è un modo per rappresentare una funzione booleana (data o da determinare)
La tabella delle verità ha due colonne:
colonna degli ingressi, le cui righe contengono tutte le combinazioni di valori delle variabili della funzione
colonna dell’uscita, che riporta i corrispondenti valori assunti dalla funzione
Da espressione booleana
a tabella di veritá corrispondente
Task:
passare da una espressione booleana alla sua tabella di veritá della funzione corrispndente
Esempio:
F(A, B, C) = AB + /C F(0, 0, 0) = 0 0 + /0 = 0 + 1 = 1
F(0, 0, 1) = 0 0 + /1 = 0 + 0 = 0 F(0, 1, 0) = 0 1 + /0 = 0 + 1 = 1 F(0, 1, 0) = 0 1 + /1 = 0 + 0 = 1 F(1, 0, 0) = 1 0 + /0 = 0 + 1 = 1 F(1, 0, 1) = 1 0 + /1 = 0 + 0 = 0 F(1, 1, 0) = 1 1 + /0 = 1 + 1 = 1
espressione booleana con 3 variabili A, B e C funzione booleana
a tre parametri
Funzioni e circuiti combinatori
Architettura degli elaboratori - 5 -
Esempio 2/2
# riga A B C A B + /C F 0 0 0 0 0 0 + /0 1 1 0 0 1 0 0 + /1 0 2 0 1 0 0 1 + / 0 1 3 0 1 1 0 1 + /1 0 4 1 0 0 1 0 + /0 1 5 1 0 1 1 0 + /1 0 6 1 1 0 1 1 + /0 1 7 1 1 1 1 1 + /1 1 (qui, per comodità nella colonna centrale
è riportato anche il calcolo e in quella iniziale il numero di riga)
colonna uscita colonna
ingressi
n = 3 ingressi
2
n= 2
3= 8 righe
Rete combinatoria
A ogni espressione booleana, è associare una rete combinatoria Gli ingressi della rete combinatoria sono le variabili della funzione L’uscita della rete combinatoria è il valore assunto dalla funzione La rete è costituita da porte logiche corrispondenti agli operatori presenti nella funzione
Espressione
booleana Rete
combinatoria Basta mettere
porte al posto
Funzioni e circuiti combinatori
Architettura degli elaboratori - 7 -
Esempio
A B C
A B
/C ingressi
uscita segnale
interno
segnale interno
A B + /C
espressione booleana
combinatoria rete
A B +/ C
Rete combinatoria
Una rete combinatoria è un circuito digitale:
dotato di n 1 ingressi e di un’uscita
formato da porte logiche interconnesse da cavi
uscita di una porta connessa con entrata in una porta successiva o con l’output del circuito
privo di retroazioni
il segnale viaggia dall’input all’output «a senso unico»
c’è una gerarchia, un ordinamento parziale fra le porte niente cicli (aciclico)
Noi usiamo porte logiche AND, OR e NOT
ma una rete combinatoria può anche essere formata da porte logiche di altro tipo
Funzioni e circuiti combinatori
Architettura degli elaboratori - 9 -
Dalla rete alla tabella delle verità
Data una rete combinatoria, qual’è la funzione calcolata?
La tabella delle verità della funzione implementata da
una rete combinatoria può essere ricavata per simulazione del funzionamento circuitale della rete combinatoria stessa
Per simulare il funzionamento di una rete combinatoria, si applicano dei valori agli ingressi, e li si propaga lungo la rete fino all’uscita
si applica ogni possibili combinazioni di 0 e 1 in ingresso si osserva ogni rispettiva uscita
Tabella verità della funzione Rete
combinatoria
Simulazione (circuitale)
Simulazione circuitale
A
F B
C
(corrisponde alla riga 0 della tabella)
Risultato della simulazione: F(0, 0, 0) = 1 0
0
0
0
1 1
Funzioni e circuiti combinatori
Architettura degli elaboratori - 11 -
Simulazione circuitale
A
F B
C
(corrisponde alla riga 001 della tabella)
Risultato della simulazione: F(0, 0, 1) = 0 0
0
1
0
0 0
Simulazione circuitale
A
F B
C
(corrisponde alla riga 010 della tabella)
Risultato della simulazione: F(0, 1, 0) = 1 0
1
0
0
1 1
Funzioni e circuiti combinatori
Architettura degli elaboratori - 13 -
Simulazione circuitale
A
F B
C
(corrisponde alla riga 111 della tabella)
Risultato della simulazione: F(1, 1, 1) = 1 1
1
1
1
0 1
Simulazione circuitale: risultato (dopo tutte le simulazioni)
A B C F 0 0 0 1 0 0 1 0 0 1 0 1 0 1 1 0 1 0 0 1 1 0 1 0 1 1 0 1 1 1 1 1
Funzioni e circuiti combinatori
Architettura degli elaboratori - 15 -
Dalla rete combinatoria ad espressione booleana
Data una rete combinatoria si può analizzarla per determinare la espressione booleana corrispondente
Esiste sempre una funzione corrispondente, se il circuito non contiene collegamenti illegali, retroazioni, ecc.
Espressione booleana Rete
combinatoria
Analisi di reti combinatorie
1. Si applicano nomi ai segnali interni: p, q e r
2. Si esprimono p, q, r in funzione di A, B, C, e F in funzione di p, q, r A
F B
C
p q r
Funzioni e circuiti combinatori
Architettura degli elaboratori - 17 -
Analisi di reti combinatorie:
un metodo lento ma sicuro
Espressioni booleane corrispondenti ai segnali interni:
p = /A B q = /C r = /A C
A
F B
C
p q r
Analisi di reti combinatorie:
un metodo lento ma sicuro
Uscita come espressione booleana in funzione dei segnali interni:
F = p + q + r
A
F B
C
p q r
Funzioni e circuiti combinatori
Architettura degli elaboratori - 19 -
Analisi di reti combinatorie
p = /A B q = /C r = /A C F = p + q + r
Per sostituzione, si ricava l’uscita come espressione booleana in funzione degli ingressi principali:
F(A, B, C) = /A B + /C + /A C
L’espressione booleana così trovata esprime la stessa funzione booleana calcolata dal circuito combinatorio di partenza
OPPURE: procedere in avanti, dagli input verso l’output (s
Sintesi di reti combinatorie
Problema della sintesi:
data: una funzione booleana (espressa come tabella delle verità):
costruire (sintetizzare): lo schema logico di un circuito che la calcola Usiamo due passi:
1: trovare una espressione booleana che esprime la funzione booleana data
2: costruiriamo la rete corrispondente all’espressione booleana In generale, per una data tabella delle verità possono esistere più espressioni booleane
la soluzione al problema di sintesi non è dunque unica!
problema: trovare la rete ottima (o almeno buona)
Funzioni e circuiti combinatori
Architettura degli elaboratori - 21 -
Reminder: reti combinatorie (funzionalmente) equivalenti
Ogni rete combinatoria realizza una espressione booleana Ogni espressione booleana rappresenta una rete combinatoria Ma: tante espressioni booleane diverse possono esprimere la stessa funzione booleana (data come una tabella di veritá)!
(cioè dare lo stesso valore per gli stessi assegnamenti della vars) Data una funzione booleana (come tabella di verità)
esistono molte reti combinatorie che la realizzano
Reti combinatorie che realizzano la medesima funzione combinatoria si dicono (funzionalmente) equivalenti
Esse hanno tutte la stessa funzione, ma struttura differente Diverso costo
Diverse prestazioni (es: velocità, consumo … ) Ci dobbiamo porre il problema di scegliere la migliore
(o almeno una sufficientemente buona)
…
Rete combinatoria
★★★☆☆
Sintesi di reti combinatorie
Problema della sintesi:
data: una funzione booleana (espressa come tabella delle verità):
costruire (sintetizzare): lo schema logico di un circuito che la calcola
Funzione booleana (tav. verita)
Espressione booleana Espressione booleana
Rete combinatoria
★☆☆☆☆
Rete combinatoria
★★★★☆
Funzioni e circuiti combinatori
Architettura degli elaboratori - 23 -
Sintesi di reti combinatorie
Esistono svariate tecniche di sintesi di reti combinatorie, che differiscono per:
Complessità della procedura
Qualità della rete combinatoria risultante
(per dimensioni, costo, e velocità, dissipazione di calore…)
Una tecnica semplice e universale, benché generalmente non ottimale, è la sintesi attraverso somma di prodotti (detta 1aforma canonica)
Funzione booleana (tav. verita)
espressione booleana (una somma di prodotti) Passo 1
rete
combinatoria finale Passo 2
Sintesi come somma di prodotto (SP) (o sintesi in 1
aforma canonica)
Input: la tabella delle verità della funzione da sintetizzare, funz con n parametri,
Output: una somma di prodotti, cioè un’espressione booleana del tipo XXXX + YYYY + ZZZZ + ….
dove ciascuno degli addendi della somma XXXX, YYYY … è un prodotto (di n fattori).
Per ogni 1 nella colonna dell’uscita della tabella delle verità:
costruire una somma con un termine per ogni parametro:
Se il parametro xiha valore 1
mettere nella somma il parametro naturale (es: A ) Se il parametro xiha valore 0
mettere nella somma il parametro negato (es: /A )
Funzioni e circuiti combinatori
Architettura degli elaboratori - 25 -
Esempio: funzione maggioranza
Si chiede di sintetizzare (in 1aforma canonica) una funzione
combinatoria dotata di 3 ingressi A, B e C, e di un’uscita F, funzionante come segue:
Se la maggioranza degli ingressi vale 0, l’uscita vale 0 Se la maggioranza degli ingressi vale 1, l’uscita vale 1
Tabella delle verità
La tabella delle verità della funzione maggioranza è mostrata a lato
L’uscita vale 1 se e solo se 2 o tutti e 3 gli ingressi valgono 1 (cioè se e solo se il valore 1 è in maggioranza)
A B C F 0 0 0 0 0 0 1 0 0 1 0 0 0 1 1 1 1 0 0 0 1 0 1 1 1 1 0 1 1 1 1 1
Funzioni e circuiti combinatori
Architettura degli elaboratori - 27 -
Espressione booleana
F(A, B, C) =
/A B C + A /B C + A B /C + A B C
E’ una somma di prodotti!
# riga A B C F 0 0 0 0 0 1 0 0 1 0 2 0 1 0 0 3 0 1 1 1 4 1 0 0 0 5 1 0 1 1 6 1 1 0 1 7 1 1 1 1
Si può ridurre?
Modo pratico di disegnare un circuito per una somma di prodotti (step 1)
A
/AA
B
/BB
C
/CC
X =
/A B C +
A /B C +
A B /C +
A B C
Modo pratico di disegnare un circuito per una somma di prodotti (step 2)
Funzioni e circuiti combinatori
Architettura degli elaboratori - 29 -
A
/AA
B
/BB
C
/CC
X =
/A B C + A /B C + A B /C + A B C
/A B C A /B C A B /C A B C
Modo pratico di disegnare un circuito per una somma di prodotti (step 3)
A
/AA
B
/BB
C
/CC
X =
/A B C +
A /B C +
A B /C +
A B C
Funzioni e circuiti combinatori
Architettura degli elaboratori - 31 -
Modo pratico di disegnare un circuito per una somma di prodotti: una variante
A B C
F /ABC, vero quando input 011
A/BC, vero quando input 101
AB/C, vero quando input 110 ABC, vero quando
input 111 F(A, B, C) =
/A B C + A /B C + A B /C + A B C
Metodo alternativo:
usare un prodotto di somme
“Seconda forma canonica”
Funzione booleana (tav. verita)
espressione booleana che un prodotto di somme Passo 1
rete
combinatoria finale Passo 2
Funzioni e circuiti combinatori
Architettura degli elaboratori - 33 -
Sintesi come prodotto di somme
F(A, B, C) =
(A+B+C) (A+B+/C) (A+/B+C) (/A+B+C)
Nota bene: è un prodotto di somme
# riga A B C F 0 0 0 0 0 1 0 0 1 0 2 0 1 0 0 3 0 1 1 1 4 1 0 0 0 5 1 0 1 1 6 1 1 0 1 7 1 1 1 1
Sintesi come prodotto di somme
F(A, B, C) =
(A+B) (A+/B) (/A+B)
F=0 sse uno dei fattori è 0.
Essendo un prodotto di somme ciascun fattore annulla la funzione solo in un caso
A+B = 0 sse A=0, B=0 A+/B = sse A=0, B=1 /A+B = sse A=1, B=0 Nel caso A=1, B=1 nessun
A B F
0 0 0
0 1 0
1 0 0
1 1 1
Funzioni e circuiti combinatori
Architettura degli elaboratori - 35 -
Quale metodo conviene?
PoS o SoP?
Se ci sono pochi 1 conviene SoP Se ci sono pochi 0 conviene PoS
Due reti equivalenti
F1 = AB + AC F2 = A(B + C)
F1 = AB + AC =
= A (B + C) =
= F2
A
F1 B
C
AB
AC
AB+AC
A
F2 B
C B+C
A(B+C)
Proprietà distributiva
Funzioni e circuiti combinatori
Architettura degli elaboratori - 37 -
Costo di reti combinatorie
Il costo di una rete combinatoria si valuta in vari modi (criteri di costo):
Numero di porte,
Numero di tipi diversi di porte utilizzate Altri ...
Numero di porte universali (NAND o NOR)
Numero di transistor (per fare tutte le porte necessarie) ES: ogni AND oppure OR : 4 transistor
ogni NOT : 2 transistor
Complessità delle interconnessioni ecc ...
Velocità di una rete
( o latenza , o ritardo di propagazione )
La velocità di una rete combinatoria è misurata dal tempo che una variazione di ingresso impiega per modificare l’uscita della rete Per calcolare la velocità di una rete combinatoria, occorre conoscere i ritardi di propagazione delle porte logiche componenti la rete, e poi analizzare i percorsi ingressi-uscita
Frequenza di commutazione = 1 / (latenza)
(quante volte al secondo può calcolare la funzione logica associata) La latenza si misura in secondi (s)
o, più comodamente, milli-sec (ms), nano-sec (ns)…
La frequenza si misura in Hertz (Hz) 1Hz = 1 / sec = una volta al sec
Funzioni e circuiti combinatori
Architettura degli elaboratori - 39 -
Velocità
A
F=AB+/C B
C
Ritardo totale = 5 ns = 5 10
9sec
Freq. di commutazione = 1 / 5 ns = 200 MHz
2 ns 1 ns
+3 = 5 ns 2 ns
1 ns 3 ns 2
max
Velocità
Calcolo “all’indietro”
1 ns
T
0A
F B
C
3 ns
1 ns 2 ns
T
0- 3 ns T
0- 3 ns T
0-(3+2) ns
T
0-(3+2) ns
T
0-(3+1) ns
Idea: ottimizzare l’espressione prima di convertirla in un circuito
Funzioni e circuiti combinatori
Architettura degli elaboratori - 41 -
Funzione booleana (tav. verita)
espressione booleana:
prodotto di somme OPPURE somma di prodotti costruzione
di 1ma oppure 2da forma canonica
rete combinatoria ottimizzata
Ottimizzazione usando le regole di riscrittura delle espr. booleane
espressione più semplice
da espressione booleana a circuito combinatorio
Ottimizzazione: esempio
/A B C + A /B C + A B /C + A B C =
/A B C + A B C + A /B C + A B C + A B /C + A B C = (/A + A) B C + A C (/B + B) + A B (/C + C) =
BC + AC + AB
Meno costosa e più veloce! (provare)
oppure, andando avanti con le riscritture BC + AC + AB = C (A+B) + AB
Ancora meno costosa (solo 4 porte a due ingressi, anziché 5) Velocità?
Velocità alta VS costo ridotto :
Esempio dell’intero processo 1/5
Numeri a led (cosiddetti “Seven-segment display”) : costruiamo un piccolo circuito combinatorio che calcola lo stato (acceso, spento) di uno dei 7 led del display dobbiamo accendere sul display una cifra in base 8 espresso da tre bit dati in igresso in base 2
la cifra da esprimere è espressa con tre bit A,B,C
Funzioni e circuiti combinatori
Architettura degli elaboratori - 43 -
000ABC 001 ABC 010
ABC 011 ABC 100
ABC 101 ABC 110
ABC 111 ABC
Esempio dell’intero processo 2/5
Numeri a led (“Seven-segment display”) in base 8:
risolviamo per il led in alto
000ABC 001 ABC 010
ABC 011 ABC 100
ABC 101 ABC 110
ABC 111 ABC
acceso spento acceso acceso spento acceso acceso acceso A B C X 0 0 0 1 0 0 1 0 0 1 0 1 0 1 1 1 1 0 0 0 1 0 1 1 1 1 0 1
tabella
di veritá
Esempio dell’intero processo 3/5
Come SOMMA DI PRODOTTI (1ma forma canonica)
\A \B \C + \A B \C + \A B C + A \B C + A B \C + A B C
Come PRODOTTO DI SOMME (2da forma canonica)
( A + B + \C ) ( \A + B + C) (usiamo questa! meno 0 che 1)
Funzioni e circuiti combinatori
Architettura degli elaboratori - 45 -
A B C X 0 0 0 1 0 0 1 0 0 1 0 1 0 1 1 1 1 0 0 0 1 0 1 1 1 1 0 1 1 1 1 1
Esempio dell’intero processo 4/5
Ottimizzazione:
// start: 5 operatori binari, 2 not ( A + B + \C ) ( \A + B + C)
= // distributiva: ( X + Y ) ( X + Z ) = X + YZ B + ( A + \C ) ( \A + C)
= // distr (2 volte): X( Z + K ) = XZ+XK B + A \A + AC + \C \A + C \C
= // inverso (2 volte): X \X = 0 B + 0 + AC + \C \A + 0
= // elem neutro B + AC + \A \C
// end: 4 opeatori binari, 2 not
Esempio dell’intero processo 5/5
Rete combinatoria per: B + AC + \A\C
Funzioni e circuiti combinatori
Architettura degli elaboratori - 47 -
A B C
or a tre ingressi (costa due or)
Esercizi proposti
Simulare la rete che abbiamo costruito e verificare se soddisfa la tabella di verita’
Stimare la velocita’ del circuito
Costruire la tabella di verita’ per l’espressione boolana ottimizzata e verificare sia la stessa tabella di verita’
Scrivere l’espressione booleana associata al circuito e verificare che sia la stessa espressione booleana ottimizzata
Costruire la tabella di verita’ per l’espressione booleana non ottimizzata e verificare che sia la tabella dalla quale siamo partiti Ottimizzare l’espressione in 1ma forma normale
Scrivere il circuito per l’espressione booleana non ottimizzata.
Scrivere il circuito (ottimizzato) per qualche altro led!
Ripetere gli esercizi sopra per qualche altro led