Analisi e sintesi di circuiti
combinatori
Reti combinatorie
Una rete combinatoria é un circuito elettronico
digitale in grado di calcolare in modo automatico una
funzione binaria di una o più variabili booleane.
x1
z1
x2
Circuiti logici
zm
xN
z i=fi(x1..xN) (i=1..m)
I valori delle uscite in ogni istante sono univocamente
determinati dai valori presenti contemporaneamente
sugli ingressi.
Funzioni Booleane
Una funzione booleana FB  una descrizione
estensiva del funzionamento di una rete
combinatoria, data dall'insieme delle coppie
ordinate
( (a1..a N), bi) i=1...m con ai,bi (0,1)
rappresentate tramite tabelle (per ognuno dei 2N
possibili input binari esprime il corrispondente
output di f ).
f : { 0 , 1 } N  { 0 , 1 }
Graficamente:
Tabelle di verità
 La funzione booleana di un circuito
digitale pu essere rappresentato mediante
una tabella di veritˆ o true table (TT )
che determina completamente il legame
funzionale fra ingressi e uscite.
 Dati n ingressi, una TT elenca
ordinatamente nella parte sinstra tutte le
2n combinazioni di valori delle variabili
booleane di ingresso. Nella parte destra,
nella cella di posizione (i,j) si indica il
valore assunto dalla variabile booleana di
uscita z j in corrispondenza alla sequenza
di valori assunti dalle variabili di ingresso
nella riga i della tabella.
Tabelle di Verità (2)
Ad esempio, una descrizione completa del
comportamento di una rete combinatoria a 3
ingressi e due uscite é data da:
x3 x2 x1
000
001
010
011
100
101
110
111
z2z1
00
01
00
01
00
11
01
11
Espressioni Booleane
Il comportamento di un circuito combinatorio pu
essere equivalentemente descritto da unΥespressione
booleana.
Dato un insieme numerabile di variabili Var a
valori binari, le espressioni booleane EB su di
esso sono definite induttivamente da :
 0 , 1  EB
  v  Var v  EB
 se E1 , E2  EB allora
E1  EB
E1 + E2 , E1 · E2 ,
y  x 2  x 2 x 1x0  x1 x0
Unicità FB
Teorema
- per ogni espressione booleana esiste un’unica
funzione booleana equivalente
- per ogni funzione booleana esistono infinite
espressioni booleane equivalenti
Dimostrazione?
Schema circuitale
Uno schema circuitale  un collegamento di circuiti
elementari detti porte tramite linee.
Identifichiamo tre tipi di linee:
- linee di ingresso, etichettate con i nomi delle
variabili booleane di ingresso
- linee di uscita, etichettate con i nomi delle variabili
di uscita
- linee interne, ci ascuna delle quali collega l'uscita di
una porta con l'ingresso di un'altraporta
Schema Circuitale (2)
¥ Ogni ingresso di ogni porta presente nella rete
deve essere collegato ad una linea di ingresso
oppure ad una linea interna.
¥ L'uscita di ogni porta presente deve essere
collegata ad una linea di uscita oppure ad una
linea interna.
¥ Il collegamento di porte tramite linee non
deve dare luogo a cicli.
x1
x2
P1
z
P3
x3
P2
Porte logiche elementari
Porte logiche elementari (2)
Livello fisico
Porta NOT
Porta NAND
Porte a più ingressi
X1
X1
.
.
.
.
XN_1
XN
associativa
XN
X1
X1
.
.
XN
.
.
XN-1
XN
non
associativa
Applicazione dei teoremi
dell’algebra booleana
Universalità delle porte NAND
AA  A
equivale a un NOT
Equivale a un AND
AB  AB
Equivale a un OR
A B A B  A B
Realizzazione di un circuito con un solo
tipo di porta, esempio:
Uso: ottimizzare utilizzo integrati
A
B
A
AB
Y  A  AB  A (A  B)
Y
Equivalenza fra le varie forme di
rappresentazione del
funzionamento di un circuito
combinatorio
Dal circuito all’espressione booleana
Dalla funzione booleana alla
espressione booleana
• Mintermini, maxtermini e forme canoniche
• Dalle funzioni booleane alle forme canoniche
Forme canoniche (1)
• Consideriamo un circuito combinatorio con n variabili di
ingresso, X: {X1..Xn}. Denotiamo ogni occorrenza di una singola
variabile, sia in forma semplice Xi che complementata , col Xi
nome di letterale.
• Implicante di una funzione f(X1..Xn) è un prodotto
P(X’) X’X di letterali tale che se P=1  f=1
• Mintermine è un implicante in cui appaiono tutte le variabili di
ingresso, cioè X’=X
• I mintermini possono essere posti in corrispondenza con punti
x2x1x0 
 010
nello spazio booleano, ad es:
• Si definisce maxtermine di una funzione f(X1..Xn) un punto Bx
nello spazio booleano Bn tale per cui f(Bx )=0
• Mintermini e maxtermini sono identificabili tramite la funzione
booleana
Esempio
x3 x2 x1
000
001
010
011
100
101
110
111
z1
0
1
0
1
0
1
1
1
Mintermini: x3x2x1,x3x2x1,x3x2x1,x3x2x1,x3x2x1
Maxtermini: x3x2x1,x 3x 2x1,x3x2x1
Rappresentazione nello spazio B3
della funzione a+b+c
maxtermine
Forme canoniche (2)
• On-set è l’insieme dei mintermini m1,m2..mk di una funzione
booleana
• L’espressione booleana f(X1..Xn) = m1+m2+..mk prende il
nome di forma canonica disgiuntiva
• Un maxtermine è un punto nello spazio in cui la f(X1..Xn)=0.
• Sia M1..Mh l’insieme dei maxtermini, o off-set
• Quindi, f(X1..Xn)=M1+M2+..Mh  f(X1..Xn)=M1M2..  Mh
• La forma precedente si dice forma canonica congiuntiva
Esempio
x3 x2 x1
000
001
010
011
100
101
110
111
z1
0
1
0
1
0
1
1
1
Mintermini: x3x2x1,x3x2x1,x3x2x1,x3x2x1,x3x2x1
Maxtermini: x3x2x1,x 3x 2x1,x3x2x1
fcd  x 3x 2x1  x3x2x1 x3x2x1  x 3x 2x1  x3x 2x1
fcc  (x 3x 2x1)(x 3x2x1)(x3x2x1) 
(x3  x2  x1)(x 3  x2  x1)(x 3  x2  x1)
Procedura per ottenere fcd da TV
• Ad ogni riga della tabella di verità, costituita da una sequenza di
n valori booleani bn-1..b0, in cui f(X1..Xn)=1, associamo una
sequenza di letterali nel seguente modo: se bi=0, facciamo
corrispondere a bi il letterale Xi, se bi=1 facciamo corrispondere
a bi il letterale Xi (es 001 x2x1x0)
• Le stringhe di letterali così ottenute corrispondono all’ On-set di
f, cioè l’insieme dei mintermini m1..mk
• La forma canonica disgiuntiva sarà
f (X1..Xn)  m1 m2  ..mk
Procedura per ottenere fcc da TV
• Ad ogni riga della tabella di verità, costituita da una sequenza di
n valori booleani bn-1..b0, in cui f(X1..Xn)=0, associamo una
sequenza di letterali nel seguente modo: se bi=0, facciamo
corrispondere a bi il letterale Xi, se bi=1 facciamo corrispondere
a bi il letterale Xi e costruiamo i maxtermini Mi come somma
logica di questi letterali (es 010 x2+x1+x0)
• La forma canonica congiuntiva sarà:
f (X1,..Xn)  M1 M2  ..Mh
X2X1X0
000
001
010
011
100
101
110
111
Y
0
1
0
0
0
1
0
1
Esempio
Y= X 2 X 1X 0 + X 2 X 1X 0 + X 2X 1X 0
Y  (X 2  X 1  X 0 )(X 2  X1  X 0 )(X 2  X1  X 0 )(X 2  X1  X 0 )(X 2  X1  X 0 )
Dalla espressione booleana alla TV
(1)
• La forma normale disgiuntiva FND o SOP
(Sum of Products) é una generalizzazione della
FCD. In una SOP i prodotti non sono
necessariamente mintermini.
Y  (X 2  X 2 )X 1X 0  X 2X 1X 0  X 1X 0  X 2 X 1X 0
Dalla espressione booleana alla TV
(2)
• Data una espressione booleana, ricavarne la forma normale
disgiuntiva
• Ad ogni termine Ti della FCD, associare una stringa binaria Ri=
bn-1..b0 nel seguente modo:
• se il letterale é negato porre bi=0 ,
• se il letterale é diretto porre bi =1,
• se non compare in Ti, porre bi=X , dove col simbolo X (o d, o -)
indichiamo la condizione di indifferenza "dont'care" ossia
indifferentemente uno 0 o un 1.
Y  X1 X 0  X 2X 1X 0
Y  X1(X 0  X 2X 0 )
Nell'esempio sopra, otteniamo le seguenti stringhe:
R1= X10 ed R2=111
Dalla espressione booleana alla TV
(3)
• A questo punto costruiamo la parte sinistra della tabella di verità,
TV, e nella parte destra, poniamo un 1 in corrispondenza a tutte
le righe uguali o implicate dalle stringhe Ri.
• Nell'esempio, la stringa R1 contiene le stringhe 110 e 010, dato
che può essere sia 0 che 1 (dont'care).
R1
R2
X2X1X0
000
001
010
011
100
101
110
111
Y
0
0
1
0
0
0
1
1
Dalla EB allo Schema Circuitale
• Per ricavare lo schema circuitale SC di una rete combinatoria da
una EB, conviene ancora partire dalla forma canonica
congiuntiva o disgiuntiva, oppure una sua generalizzazione FNC
o FND. Tuttavia non è strettamente necessario.
• Assegnata dunque una EB, costruiamo una rappresentazione
gerarchica degli operatori booleani, partendo dai più esterni.
• Ad esempio Y  X 2 X 1(X 3  X 0X 2 ) si può rappresentare:
AND(AND(X2,X1), OR(X3,AND(NOT(X0),X2))
Lo schema ad albero equivalente è:
AND
OR
AND
X1
X2
AND
X3
NOT
X0
X2
Dalla EB allo Schema Circuitale
(2)
• A questo punto, il passaggio allo schema circuitale é immediato:
– i terminali dell'albero sono le variabili booleane di ingresso
– i nodi vengono associati alle corrispondenti porte logiche
elementari
– gli archi vengono associati alle linee interne della rete.
X1
X2
Y
X3
X0
Ottimizzazione di reti
combinatorie
Sintesi di reti combinatore
• La sintesi di una rete combinatoria implica il
passaggio dalla specifica funzionale del circuito
allo schema circuitale. Il procedimento di sintesi
può essere sviluppato in tre fasi:
•1
Dalla specifica funzionale si ricava la funzione
booleana rappresentata in forma tabulare (TV)
•2
Dalla TV si ricava una espressione minima, o EB
minima della TT
•3
Dalla EB minima si ricava lo schema circuitale
• Il passo 3 é stato già descritto
Minimizzazione EB
• Il problema di ricavare una espressione minima deriva dalla
necessità di ridurre il numero di porte logiche necessarie per
realizzare una rete combinatoria.
• Con l'avvento dei circuiti integrati su scala media, alta e molto
alta (MSI, LSI e VLSI) questa esigenza é meno sentita,
soprattutto in termini di costi. Il costo di una porta logica
aggiunta é pressoché nullo. Tuttavia esiste un problema di area
occupata.
• Ridurre il numero di porte attraversate da un segnale logico ha
una sua rilevanza soprattutto in termini di specifiche temporali.
• Il tempo di risposta di una rete combinatoria dipende dal numero
di porte logiche attraversate: ridurre tale numero può avere
effetti importanti in termini di prestazioni.
Minimizzazione basata sulle mappe
di Karnaugh
• Si basano sulla applicazione ripetuta della
seguente semplificazione: ax  ax  a(x  x)  a
dove a è una sequenza di letterali
• Queste mappe ordinano i punti di uno spazio
booleano Bn in modo che i punti a distanza
unitaria (cioè le cui coordinate differiscono per
un solo bit) siano adiacenti anche sul piano della
mappa
Struttura delle MdK
MdK della funzione OR
Copertura di una FB
• Un implicante corrisponde ad un sottocubo di soli “1” della
MdK, cioè un insieme di 2k configurazioni di ingresso a distanza
unitaria
• Un implicante si dice primo se non esite un imlicante di
dimensioni maggiori che lo contenga interamente
• Un implicante si dice essenziale se contiene almeno un 1 che
non sia incluso in alcun altro implicante
• Una copertura minima di una funzione booleana è l’ insieme di
implicanti primi minimo che copra tutti gli 1 (mintermini) della
fb
Esempio (a)
Esempio (2)