Cap2 CircuitiLogiciCombinatori

Università degli Dipartimento di Ingegneria
Studi di Palermo
Circuiti Logici Combinatori

Reti logiche
Prof. Orazio Gambino

➢ Queste slides NON sostituiscono il libro di
testo ma ne completano le spiegazioni
offrendo il punto di vista del docente.
➢ Pertanto, si consiglia caldamente di
acquistare il libro di testo, che offre una più
ampia spiegazione degli argomenti trattati.
➢ Queste slides sono ad uso esclusivo e privato
degli studenti del corso di Calcolatori
Elettronici.
➢ Diffido chiunque dal pubblicarle online su
qualunque pagina web o social network.
Orazio Gambino
2
Algebra di Boole
➢ I circuiti logici sono componenti hardware che manipolano

informazioni binarie.
➢ I circuiti di base sono detti PORTE LOGICHE (logical gate).
➢ Allo scopo di descrivere i comportamenti dei circuiti digitali si
può usare una algebra (notazione matematica) che specifica
l’operazione di ogni porta e permette di analizzare e sintetizzare
(disegnare) il circuito.
➢ L’algebra dovuta a Boole è detta ALGEBRA BOOLEANA.
➢ Le variabili di questa algebra sono binarie, e possono assumere
solo due valori (0,1, True o False).
➢ Le variabili si indicano con le lettere A,B,C,X,Y,W,Z
➢ Le operazioni base sono AND ( • ), OR ( + ) ,NOT ( ¯ , ‘)
3 - RETI LOGICHE
Algebra di Boole
➢ Gli operatori AND, OR e NOT sono definiti mediante tabelle di
verità
4 - RETI LOGICHE
Algebra di Boole
➢ Altra interpretazione che possiamo dare è quella dei CIRCUITI

ELETTRONICI.
➢ Questi sistemi sono caratterizzati da grandezze fisiche (segnali) che
assumono due gamme distinte di livelli logici H (alto) L (basso)
➢ La associazione tra livelli di tensione e livelli logici può essere fatta
secondo la logica positiva o negativa
➢ PORTE LOGICHE: circuiti elettronici che realizzano le operazioni
logiche elementari
▪ Operano su più segnali di ingresso e producono un segnale di uscita
▪ Rispondono a due valori di range di tensioni che sono associati ai
valori logici 0 e 1.
5 - RETI LOGICHE
Porte logiche
6
Porte logiche
➢ Diagramma di temporizzazione
▪ I segnali sono campionati ad intervalli
regolari
▪ Le transizioni da un livello logico
all’altro si assumono ideali, ovvero che
avvengano istantaneamente
▪ Fronte di salita : transizione da 0 a 1
▪ Fronte di discesa : transizione da 1 a 0
7 - RETI LOGICHE
Simboli
➢ porta AND
AB A  B A and B A  B
➢ porta OR
A+ B A B
➢ porta XOR
A B
➢ porta NOT
A'
8
A !A A
Porte logiche
9
Porte logiche
Si sarebbero potute disegnare le porte AND e OR con una NOT in

uscita. Il “pallino” indica la presenza di una porta NOT in uscita,
ottenendo così un disegno semplificato.
10
Porte logiche
Anche gli ingressi posso essere inserite porte NOT, ma al loro posto si
inseriscono sempre i “pallini”. In particolare le due porte si riferiscono alle
seguenti funzioni booleane:
11
Porte logiche
12
Funzioni Booleane: Porta AND
➢ La porta NOR è funzionalmente completa perché con essa è

possibile implementare tutte le altre porte.
➢ Vedremo più avanti un esempio per la funzione NOT
implementata con una porta NOR.
13
Funzioni Booleane: Porta OR
➢ Anche la porta NAND è funzionalmente completa. La porta OR

può essere sostituita da una NAND con gli ingressi negati.
14
Funzioni Booleane: Porta NOT
➢ La porta NOT può essere sostituita da una porta NAND o NOR

con lo stesso segnale distribuito ad entrambi gli ingressi
➢ Lo schema di unna qualsiasi porta con porte NOT in ingresso
15
Funzioni Booleane: Porta XOR
X  Y = X Y + X Y
La porta logica XOR può essere espressa tramite una piccola “rete combinatoria”
tramite porte AND, OR e NOT.
16
Scrivere la tabella di verità di questo circuito
equivalente della porta XOR
17
Porte logiche ad ingressi multipli
➢ A sinistra una AND a tre ingressi. A destra il circuito equivalente

realizzato con AND a due ingressi.
18
Porte logiche ad ingressi multipli
19
Funzioni logiche come operatori booleani
1 1 0 0 1 0 0 1 AND 1 1 0 0 1 0 0 1 OR
01101011 = 01101011 =
01001001 11101011
Con la funzione AND è possibile selezionare bit o

Semibyte (basso o alto) con la tecnica del
mascheramento:
1 1 0 0 1 0 0 1 AND 1 1 0 0 1 0 0 1 AND
00001111 = 11110000 =
00001001 11000000
20
Da binario a Gray con l’ operatore XOR
➢ Per convertire in codice Gray il numero 110010 basta applicare
l’operatore XOR tra il numero e la sua versione shiftata a destra
di una posizione
binario 1 1 1 0 2 XOR
1 1 1 02 =
Gray 1001 -
➢ Da notare che l’MSB è lo stesso sia per il numero binario che
per i codice Gray ottenuto. L’ LSB del risultato viene omesso.
➢ In termini analitici, la regola è la seguente
gn = bn
gi =bi ⊕ bi+1 i = n-1,…, 1
21
Da binario a Gray con l’ operatore XOR
➢ Esempio con 3 cifre:
g2=b2; g1=b1 ⊕b2; g0=b0 ⊕ b1
b2 g2
g1
b1
g0
b0
22
Da Gray a binario con l’operatore XOR
➢ Sia il codice Gray che il numero binario hanno lo stesso MSB,

quindi si determina facilmente l’ MSB del numero binario:
gn = bn
➢ Tutte le altre cifre del numero binario si trovano, una per una,
con il seguente procedimento iterativo:
bi =bi ⊕ gi+1 i = n-1,…, 1
23
da Gray a binario tramite operatore XOR
Gray Code Binary
g2g1g0 b2b1b0
Gray 10010 000 000

001 001
011 010
binario 1 010 011
110 100
111 101 Per tre cifre:
101 110 b2=g2, b1=g1⊕g2, and b0=g0⊕g1⊕g2
Gray 10 0 1 0 100 111 In generale:
bn=gn,
b(n-1)=g(n-1)⊕gn, ….
binario 1 1 b1=g1⊕g2⊕g3...⊕gn and
b0=g0⊕g1⊕g2⊕g3...⊕gn.
Gray 1 00 1 0 Gray 1 0 01 0
binario 11 1 binario 1 1 1 0-
24
da Gray a binario tramite regola
➢ il bit più significativo è uguale per entrambi

➢ se il bit del codice gray è uguale a 0, allora copia la precedente
cifra binaria; altrimenti inverti la precedente cifra binaria
➢ Rivedi l’esempio precedente con l’operatore XOR e verifica la

correttezza delle regole sopra.
25
Famiglie logiche
RTL TTL ECL CMOS
Transistori con
Resistori e MOS
Elementi Circuitali Transistori accoppiamento
Transistori Complementari
diretto
Porta base NOR NAND OR E NOR NOR o NAND
Tempo di propagazione tp (ns) 12 10 2 50
Freq. di Clock (MHz) 8 15-60 60 5
Fan out 5 10 25 >50
Tensione di alimentazione (V) 3 5 5,2 3-15

26
Circuiti Integrati
27
Datasheet
28
Breadboard (Basetta prova circuiti)
https://it.wikipedia.org/wiki/Breadboard
29
Funzioni booleane
➢ Le funzioni booleane sono quelle funzioni di variabile booleana
che possono assumere soltanto i valori vero e falso (1,0).
➢ Le funzioni booleane possono essere specificate usando la
tabella di verità.
F = X +Y Z
30 - RETI LOGICHE
Identità fondamentali - Premessa
➢ Il principio di dualità dell’algebra booleana afferma che un’equazione
booleana rimane valida se si considera il duale di entrambi i lati
dell’uguaglianza di un’espressione.
➢ Il duale di un’espressione si ottiene:
▪ cambiando AND con OR e viceversa
▪ cambiando uno con zero e viceversa
▪ mantenendo le priorità implicite ed esplicite
➢ La tabella delle Identità fondamentali che segue è divisa in due
colonne proprio per mostrare l’effetto del principio di dualità.
➢ Tutte le identità sono dimostrabili con il metodo dell’induzione
completa, cioè sostituendo tutte le possibili combinazioni di 0 e 1 alle
variabili d’ingresso.
➢ Le identità restano valide se una variabile rappresenta una
espressione più complessa: per X= AB+C si ottiene per l’identità 3
AB+C+1=1
31
Identità fondamentali
Duali
32 - RETI LOGICHE
Identità fondamentali – identità derivate
1. Si dimostra mettendo a fattor comune ed i.f.3

2. Si dimostra mettendo a fattor comune la X ed i.f.7
3. Si dimostra tramite i.f. 15
4. Si dimostra tramite i.f. 14, i.f.6 ed infine i.f.3
5. Si dimostra tramite i.f. 15 ponendo Z=Y
6. Si dimostra tramite i.f. 14
33 - RETI LOGICHE
Identità della porta XOR
X 0 = X X 1 = X
X X =0 X  X =1
_________ _________
X Y = X Y X Y = X Y
_________ _____________
X  Y = XY + XY X  Y = XY + XY
= (X +Y)(X +Y )
= XY + XY
34
Teorema di DeMorgan
➢ Forma generale del teorema di DeMorgan
➢ Passando da un membro all’altro
▪ OR => AND e AND => OR
▪ Il complemento è eliminato dall’intera espressione e applicato a ogni variabile
▪ Le precedenze implicite ed esplicite sono mantenute
➢ Dimostrazione del Teorema di DeMorgan tramite tabella di verità.
X1X 2 X n = X1 +X 2 + + Xn X1 +X 2 + + X n = X1X 2 X n
35 - RETI LOGICHE
Complemento di una funzione
➢ Attraverso DeMorgan ➢ Usando la dualità

▪ Si applica il Teor. Di DeMorgan ➢ Deriva dalla generalizzazione del
ripetutamente teorema di DeMorgan
▪ Si deriva l’espressione duale della
funzione data
▪ Si complementano tutti i letterali
Duale
Complemento dei letterali
36 - RETI LOGICHE
Semplificazione di funzioni - 1
F = XYZ + XYZ + XZ
POSSIAMO SEMPLIFICARE LA FUNZIONE
F = XYZ + XYZ + XZ
= XY(Z + Z) + XZ (IDENTITA' 14)
= XY • 1 + XZ ( " 7)
= XY + XZ ( " 2)
37 - RETI LOGICHE
Semplificazione di funzioni - 2
➢ La semplificazione conduce a espressioni equivalenti, ovvero
aventi la stessa tabella di verità, ma corrispondenti a
implementazioni diverse
➢ Dal punto di vista circuitale, ottengo un circuito con meno porte
e quindi più economico.
38 - RETI LOGICHE
Teorema del consensus - Enunciato
XY + XZ + YZ = XY + XZ
E nella sua versione duale
( X + Y )( X + Z )(Y + Z ) = ( X + Y )( X + Z )
➢ Il prodotto YZ, può essere eliso dalla somma logica in cui i due
fattori Y e Z appaiono in altri due prodotti che differiscono per
una unica variabile, diretta in un prodotto (X Y) e negata
nell’altro (X’ Z)
➢ E’ utile nella semplificazione di funzioni per via algebrica
(tecnica SAR, systematic algebraic reduction)
39 - RETI LOGICHE
Teorema del consensus - Dimostrazione
➢ Dimostrazione
XZ
40 - RETI LOGICHE
Tecnica di riduzione algebrica sistematica
➢ Riduzione algebrica sistematica (SAR, systematic algebraic

reduction)
1. Esprimere la funzione in forma SOP
2. Riordinare le variabili
3. Per ciascuna coppia di prodotti
1. Applicare ripetutamente adiacenza:
exp1 exp2 + exp1 exp2’ = exp1
2. Applicare ripetutamente idempotenza:
exp1 + exp1 = exp1
4. Applicare il consensus
exp1 exp2 + exp1’ exp3 + exp2 exp3 = exp1 exp2 + exp1’ exp3
41 - RETI LOGICHE
Forme canoniche
➢ Le funzioni booleane possono essere espresse in forme
equivalenti, ovvero aventi la stessa tabella di verità
➢ Si dice forma canonica una espressione booleana che contenga
una somma logica di prodotti (forma SOP, sum-of-products)
ovvero un prodotto logico di somme (forma POS, product-of-
sums)
➢ Stessa funzione in forma SOP e POS
F(XYZ)=X’Y’Z’+X’YZ’+(X’+Y+Z’)’+(X’+Y’+Z’)’
▪ SOP: F(XYZ) = XYZ + XYZ + XYZ + XYZ
▪ POS: F(XYZ) = (X + Y + Z)(X + Y + Z)(X + Y + Z)(X + Y + Z)
➢ Un’espressione algebrica, che rappresenta una funzione, si può

derivare dalla relativa tabella di verità eseguendo la somma
logica di tutti i prodotti per i quali la funzione assume valore 1
42 - RETI LOGICHE
Mintermini e maxtermini
➢ Mintermine, mj ➢ Maxtermine, Mj
▪ prodotto di tutte le variabili ▪ somma di tutte le variabili
▪ appaiono una sola volta ▪ appaiono una sola volta
▪ in forma diretta o in forma negata ▪ in forma diretta o in forma negata
➢ Rappresenta una delle combinazioni ➢ Rappresenta una delle combinazioni
delle variabili binarie elencate nella delle variabili binarie elencate nella
tabella di verità tabella di verità
➢ Vale 1 soltanto in corrispondenza della ➢ Vale 0 soltanto in corrispondenza della
specifica combinazione alla quale è specifica combinazione alla quale è
associato associato
➢ Il pedice j è l’equivalente decimale del ➢ Il pedice j è l’equivalente decimale del
numero binario ottenuto indicando con numero binario ottenuto indicando con
1 le variabili dirette e con 0 quelle 0 le variabili dirette e con 1 quelle
negate negate
m5 => A . B . C . D M5 => A + B + C + D
5 => 0 1 0 1 5 => 0 1 0 1
=> A’ . B . C’ . D => A + B’ + C + D’
43 - RETI LOGICHE
Mintermini per funzioni di 3 variabili
Si=0…n-1 mi = 1, per una funzione di n variabili

44 - RETI LOGICHE
Maxtermini per funzioni di 3 variabili
Pi=0…n-1 Mi = 0, per una funzione di n variabili

45 - RETI LOGICHE
Forme canoniche SOP e POS
➢ Somma di prodotti (SOP) ➢ Prodotto di somme (POS)

▪ Si individuano le righe per cui ▪ Si individuano le righe per cui
F ha valore 1; F ha valore 0;
▪ Si scrivono tanti prodotti ▪ Si scrivono tante somme
quante sono le righe quante sono le righe
individuate individuate
▪ Ogni prodotto è il mintermine ▪ Ogni somma è il maxtermine
relativo alla riga relativo alla riga
▪ La funzione F si esprime come ▪ La funzione F si esprime come
somma logica dei prodotti prodotto logico delle somme
individuati individuate
46 - RETI LOGICHE
Funzione in forma canonica Sum Of Product
Considerata la tabella di verità, individuo i mintermini in
cui F=1:
F(XYZ) = XYZ + XYZ + XYZ + XYZ =

= m0 + m2 + m5 + m7
o più sinteticamente:
F(XYZ) =  m(0, 2,5,7)
dove la Σ indica la sommatoria logica dei mintermini.
Se considero la funzione complementare F si procede
allo stesso modo:
F(XYZ) = XYZ + XYZ + XYZ + XYZ = m1 + m3 + m4 + m6

F(XYZ) =  m(1,3, 4,6)
Si noti che i Mintermini ottenuti nella funzione complementare sono quelli assenti nella
funzione F.
47
Funzione in forma canonica Product Of Sum
F = m1 + m3 + m4 + m6 = m1m3m4m6
= M 1M 3M 4 M 6 (in quanto m j = M j )
= (X + Y + Z)(X + Y + Z)(X + Y + Z)(X + Y + Z)
F(XYZ)= M (1,3, 4,6)
dove il simbolo Π ha l’ovvio significato di sommatoria logica.
Una qualsiasi funzione in forma non canonica può essere ricondotta ad una forma canonica
a partire dalla sua tabella di verità ed esprimendola in forma canonica SOP.
E=Y+XZ
E(XYZ)=  m(0,1, 2, 4,5)
48
E(XYZ)=  m(3,6,7)
Implementazione a due-livelli
➢ Le forme canoniche consentono di esprimere una funzione
booleana con soltanto due livelli di porte logiche AND o OR:
Forma SOP => logica AND-OR Forma POS => logica OR-AND
49 - RETI LOGICHE
Criteri di costo
➢ Quanto costa l’implementazione fisica di una funziona booleana?
➢ E’ possibile che vi siano più funzioni booleane che soddisfano la
tabella di verità. Quale scegliere?
➢ In generale, è da preferire una funzione con meno letterali possibili.
Es: F=AB+C(D+E) e F=AB+CD+CE
5 letterali 6 letterali
➢ A parità di letterali, si preferisce la funzione con con meno termini
possibili. Esempio: entrambe le funzioni hanno 8 leterali ma la
prima funzione ha 2 termini mentre la seconda ne ha 5
G=ABCD+ABCD G=(A+B)(B+C)(C+D)(D+A)
➢ Letterali negati implicano ulteriori costi a causa dell’uso di porte
NOT agli ingressi, giacchè non esistono implementazioni nei circuiti
integrati con ingressi già negati. Al contrario, ci sono porte logiche
già negate (vd. Famiglie logiche) per cui il complemento in uscita
non aggiunge costo.
50
Mappe di Karnaugh
➢ Mappa di Karnaugh (K-map)
▪ diagramma composto da celle
▪ ogni singola cella rappresenta un mintermine
➢  forma SOP è identificabile graficamente su una
mappa di Karnaugh come l’insieme delle celle
corrispondenti ai mintermini inclusi nella funzione
➢ Le espressioni semplificate prodotte dalla mappa di
Karnaugh sono sempre espresse nella forma SOP o
POS
➢ Le K-map consentono di effettuare semplificazioni
soltanto per implementazioni circuitali a due livelli
51 - RETI LOGICHE
K-map
➢ Le celle di una K-map corrispondono ai mintermini di una funzione ad
n variabili.
➢ ATTENZIONE!!!
▪ Tutta la mappa meno la cella i corrisponde al maxtermine i.
➢ Forme SOP:
▪ Si impostano ad 1 le celle corrispondenti ai mintermini che implicano la
funzione
▪ Le rimanenti celle sono impostate a 0 (in assenza di non-specificazioni)
➢ Forme POS:
▪ Si impostano a 0 le celle corrispondenti ai maxtermini che specificano la
funzione
▪ Le rimanenti celle sono impostate a 1 (in assenza di non-specificazioni)
52 - RETI LOGICHE
K-map a 2 variabili
➢ Individuazione dei Mintermini ➢ Rappresentazione di funzioni
nella K-map
AND = m3 = XY
OR = m1 + m2 + m3 =
=XY + XY + XY=
=XY + X(Y + Y)=XY + X=
=X+Y (identità derivata 3)
53 - RETI LOGICHE
Porta XOR tramite K-Map?
54 -
Semplificazione tramite K-map a 2 variabili
2-adiacenza
X Y X Y X Y X Y
0 1 0 1 0 1 0 1
0 1 1 0 1 0 0 1
1 1 1 1 1 1 1 1
XY+XY XY+XY XY+XY XY+XY

=X(Y + Y) =Y(X + X) =X(Y + Y) =Y(X + X)
=X =Y =X =Y
REGOLA: Due Mintermini adiacenti semplificano la funzione
booleana con l’ eliminazione del letterale che appare in un
Mintermine
55
e nella sua versione negata in quello adiacente.
Semplificazione tramite K-map 2 variabili
X Y X Y X Y X Y
0 1 0 1 0 1 0 1
0 1 1 0 1 0 1 0 1 1
1 1 1 1 1 1 1 1 1 1
X+Y X+Y X+Y X+Y
Le funzioni booleane generate da queste K-map si ottengono in forma

Sum Of Product (SOP) per mezzo dell’identificazione dei Mintermini
adiacenti e della sostituzione ad ogni coppia di Mintermini dei risultati
semplificati della pagina precedente.
La seconda K-map semplificata è la porta OR della slide 47.

56
Posizione dei Mintermini (Maxtermini) sulla
K-map
➢ Si dispongono i Mintermini A B C mi o M i
(Maxtermini) della tabella di verità 0 0 0 0
vista nella slide 41 (42) secondo il 0 0 1 1
codice Gray
0 1 1 3
➢ Ad ogni riga corrisponde una cella
0 1 0 2
➢ Le variabili meno significative
1 0 0 4
etichettano le colonne e quelle più
significative le righe della K-map 1 0 1 5
1 1 1 7
1 1 0 6
A B,C 00 01 11 10
0 0 1 3 2
1 4 5 7 6
57 - RETI LOGICHE
K-map a 3 variabili
58 - RETI LOGICHE
K-map a 3 variabili
• La tabella si presenta con il • La numerazione dei Mintermini
letterale doppio (variabili YZ) si effettua indicando mXYZ
espressi in codice Gray. Infatti,
tale codice permette di avere la
variazione di un solo letterale tra
due Mintermini adiacenti renden-
m000 m001 m011 m010
do possibile la semplificazione
vista nelle slide precedenti.
m100 m101 m111 m110
m0 m1 m3 m2
m4 m5 m7 m6
59
K-map a 3 variabili: Adiacenze
• La mappa a tre varia- • Le celle 0-2, 4-6 sono

bili è lo sviluppo nel adiacenti.
piano di un cilindro.
60
K-map a 3 variabili
Semplificazione con 2-adiacenza
XYZ+XYZ=XY(Z + Z) = XY XYZ+XYZ=XZ(Y + Y) = XZ
X YZ X YZ
00 01 11 10 00 01 11 10
0 1 1 0 1 1
1 1
REGOLA: Come nella K-map a 2 variabili, due

Mintermini adiacenti semplificano la funzione booleana
per eliminazione del letterale che appare in un
Mintermine e nella sua versione negata in quello
61
adiacente
K-map a 3 variabili
Semplificazione con una 3-adiacenza
XYZ+XYZ+XYZ REGOLA: L’adiacenza di 3
=XYZ+XYZ+XYZ+XYZ=XY + XZ Mintermini può essere
considerata come somma di
Applico idempotenza
adiacenze a 2 Mintermini
sommando il termine
senza altra possibilità di
X’Y’Z già presente ma
riduzione.
risulta somma di due
adiacenze doppIe XYZ+XYZ+XYZ
=XZ+XY
62
K-map a 3 variabili
Semplificazione con 4 adiacenze
Adiacenza 2x2. Usando il risultato REGOLA: Una 4-adiacenza è
della precedente per le adiacenze espressa da un’unica variabile
m0 m1,aggiungiamo solo i che è costante nel passaggio da
Mintermini m4 m5 un’adiacenza all’altra.
XY + XYZ+XYZ XY + XYZ+XYZ
=XY + XY(Z+Z ) = XY + XY(Z+Z)
= Y(X + X)=Y = X(Y + Y) = X
X YZ X YZ
00 01 11 10 00 01 11 10
0 1 1 0 1 1 1 1
1 1 1 1 63
X YZ
00 01 11 10
0 1 1 1
1 1
64
Esercizio: verificare che le adiacenze
indicate isolino una sola variabile!
65
K-map a 4 variabili
• Anche per la K-map a 4 variabili si • Allo stesso modo del caso a 3
usa il codice Gray. variabili si determinano le posizio-
ni dei Mintermini.
66
K-map a 4 variabili: adiacenze
• Tutti i Mintermini sul bordo sono • I Mintermini sono
adiacenti. I 4 vertici formano
un’adiacenza 4x4 disposti nello spazio
come un toroide.
67
K-map a 4 variabili: adiacenze 1x2 – 2x1
e 3 adiacenze
YZ Anche per la K-map a 4 variabili le adiacenze
WX 00 01 11 10
di due Mintermini producono l’eliminazione di
00 1 1 un letterale che si presenta nella sua versione
diretta e negata.
01 1
WXYZ+WXYZ WXYZ+WXYZ
11
=WXY(Z + Z) =WYZ(X + X)
10
= WXY = WYZ
REGOLA: Come per il caso della K-map a 3 variabili, l’adiacenza

di 3 Mintermini può essere considerata come somma di adiacenze
a 2 Mintermini senza altra possibilità di riduzione.
F=WXY+WYZ 68
K-map a 4 variabili: adiacenze 2x2
YZ
WX 00 01 11 10 Come nel caso della K-map
00 1 1 a 3 variabili, si ottiene
l’eliminazione di due letterali
01 1 1 che compaiono sia in forma
diretta che negata. Per il
11
primo termine della funzione
si riutilizza un risultato
10
precedente.
WXY+WXY=WY(X + X)=WY
69
K-map a 4 variabili: 8-adiacenza
YZ
WX 00 01 11 10 La funzione in forma SOP di
00 1 1 1 1 questa K-map è data dalla
somma della funzione espressa
01 1 1 1 1 dai primi quattro Mintermini
calcolata nella precedente slide
11
e per il termine W’Y in quanto
solo queste variabili rimangono
10
costanti. Per cui si ottiene:
F=WY+WY=W
REGOLA: Una 8-adiacenza è espressa da un’unica
variabile che non varia nel passaggio da un Mintermine 70
all’altro.
Verificare che le adiacenze indicate isolino i
letterali X’Z’
71
Verificare che le adiacenze indicate isolino le
variabili W,X,Y,Z
72
Esempio
F=m(4, 5, 6, 12, 13) = A’ B C’ D’ +
+ A’ B C’ D +
+ A’ B C D’ +
+A B C’ D’ +
+A B C’ D
CD
A B 00 01 11 10
00
01 1 1 1
11 1 1
10
73 - RETI LOGICHE
Esempio
F=m(4, 5, 6, 12, 13) = B C’ + …
CD
A B 00 01 11 10
00
01 1 1 1
11 1 1
10
74 - RETI LOGICHE
Esempio
F=m(4, 5, 6, 12, 13) = B C’ + A’ B D’
CD
A B 00 01 11 10
00
01 1 1 1
11 1 1
10
75 - RETI LOGICHE
Esempio
➢ Semplificare la funzione seguente in forma SOP:
F= m(0,1,2,4,5,6,8,9,12,13,14)
76 - RETI LOGICHE
Esempio
➢ Semplificare la funzione seguente in forma POS:

F= m(0,1,2,5,8,9,10)
F = AB + CD + BD
F = ( A + B)(C + D)( B + D)
77 - RETI LOGICHE
Primi implicanti e primi implicanti essenziali
➢ Implicante
▪ Un prodotto P è un implicante di una funzione se essa assume il valore 1 per tutti
i mintermini che compongono il prodotto P considerato.
➢ Tutti i raggruppamenti di una K-map, ottenuti raggruppando celle marcate con
1, sono implicanti
➢ Primo implicante
▪ Dato un implicante P, se la rimozione di qualunque letterale dà luogo a un
prodotto che non è un implicante della funzione, allora P è un primo implicante.
➢ Per una funzione F di n variabili, l’insieme dei primi implicanti corrisponde sulla
mappa di Karnaugh all’insieme di tutti i raggruppamenti costruiti utilizzando 2 m
celle (m = 0, 1, ….n), contenenti 1, in cui ciascun raggruppamento dell’insieme
contiene il maggior numero possibile di celle.
➢ Primo implicante essenziale
▪ Se un mintermine di una funzione è incluso solo in un primo implicante, tale
termine si chiama primo implicante essenziale
▪ Se per una data funzione F, una cella contenente un 1, è inclusa in un solo
raggruppamento che è un primo implicante, allora quel primo implicante è
essenziale.
78 - RETI LOGICHE
Esempio
➢ Si noti che gli accoppiamenti costituiscono primi implicanti
purché non siano completamente interni ad accoppiamenti di
ordine superiore.
In altre parole, se non si
trovano raggruppamenti
più grandi che coprono i
Mintermini, allora quei
raggruppamenti sono
primi implicanti.
79 - RETI LOGICHE
Esempio
➢ Per la funzione
F=m(0,1,2,4,5,10,11,13,15)
determinare tutti i suoi primi implicanti e dire quali
di essi sono essenziali.
➢ A’B non è essenziale
perché gli altri primi implicanti
bastano a ricoprire tutti i Mintermini.
L'eliminazione dei Mintermini
NON-essenziali minimizza
l'espressione analitica
della funzione booleana.
80 - RETI LOGICHE
K-map trasposta - 1
➢ Si mostra che la F è la stessa del caso della K-map con le

variabili trasposte
81
K-map trasposta - 2
➢ Errata corrige: Figura 2.25, l’espressione della F è sbagliata nel

libro.
82
Funzioni non completamente specificate
➢ Sono funzioni la cui tabella di verità prevede, oltre alle configurazioni
in cui la funzione vale 1, configurazioni per le quali sono possibili due
situazioni
▪ Sono combinazioni di ingresso che non si possono presentare
▪ Sono combinazioni di ingresso che si possono presentare, ma per
le quali è indifferente il valore che si attribuisce all’uscita
➢ I mintermini corrispondenti a tali configurazioni si chiamano
condizioni di non-specificazione
➢ Nella mappa di Karnaugh vengono rappresentate con X
➢ La scelta di decidere quale valore attribuire alla X in fase di
semplificazione è legata alla possibilità di ottenere espressioni più
semplici
83 - RETI LOGICHE
Semplificazione in presenza di non-specificazioni
1. Individuare i PI assumendo che X = 1

2. Eliminare dall’elenco dei PI ottenuto tutti i PI costituiti soltanto
da non-specificazioni
3. Selezionare i soli PI necessari a coprire la funzione, definita dai
soli mintermini che la implicano (coprire i soli 1 della funzione)
4. Le non-specificazioni che fanno parte dei PI selezionati nella
copertura saranno impostate a 1, le altre a 0
84 - RETI LOGICHE
Esempio
➢ Semplificare la funzione: F (A,B,C,D)= Sm(1,3,7,11,15),
con non specificazioni d(A,B,C,D) = Sm(0,2,5)
85 - RETI LOGICHE
Progettazione
1. Individuare dalla tabella di verità i Mintermini interessati (SOP),
ossia le configurazioni delle variabili d’ingresso da riconoscere
2. Trasferire i Mintermini nella K-map
3. Riconoscere le adiacenze e quindi creare gruppi di Mintermini
traminte primi implicanti essenziali
4. Dedurre la forma analitica della funzione che verrà così
ottenuta in forma semplificata
5. Disegnare lo schema equivalente alla funzione trovata
6. Selezionare i circuiti integrati da una famiglia logica
7. Creare i collegamenti tra gli ingressi e le uscite delle porte
logiche
8. Fornire tensione di alimentazione continua compatibile con la
famiglia logica scelta
86
Funzione dispari - 1
➢ Lo XOR di tre o più variabili ha valore 1 solo se le variabili che
assumono valore 1 sono in numero dispari (funzione dispari)
➢ I mintermini con un numero dispari di variabili in forma diretta, non
sono adiacenti e differiscono al più per due letterali
▪ Hanno distanza due l’uno dall’altro.
➢ La funzione pari è il complemento della dispari.
87 - RETI LOGICHE
Funzione dispari - 2
88
Funzioni dispari - 3
XYZ + XYZ + XYZ + XYZ
= ( XY + XY ) Z + ( XY + XY ) Z
Tenendo conto delle propietà :
X  Y = XY + XY
_________ _____________
X  Y = XY + XY
= (X +Y)(X +Y )
= XY + XY
Da cui deriva:
= ( X Y ) Z + ( X Y ) Z =
= X Y  Z
89
Generazione e controllo di parità
➢ Il circuito che permette l’aggiunta del bit di parità
prende il nome di generatore di parità (parity
generator)
➢ Il circuito che permette il controllo di parità prende il
nome di controllore di parità (parity checker)
➢ Usando parità pari, si ha un errore se il parity checker
genera 1 in uscita (perché un XOR di più variabili è 1
se il numero di bit 1 è dispari).
90 - RETI LOGICHE
Penny:”What does this circuit do?”
Sheldon:”It choices the greatest between A and B”
91
Il transistor
➢ Interruttore elettronico (Shockley, Brattain, Bardeen, 1947)
➢ Due stati: conduzione, interdizione (acceso, spento)
➢ Altissima densità di integrazione
▪ 3-10 M trans/cm2
➢ Altissima velocità (frequenza) di commutazione da uno stato all’altro
▪ 500-1300 milioni cicli/secondo (HERTZ)
▪ 0.8-2 miliardesimi di secondo
➢ Sostituisce il nucleo magnetico
inizi ’70
➢ Base, emettitore, collettore
➢ La base controlla il funzionamento
▪ In presenza di tensione sulla base
la corrente scorre dal collettore
verso l’emettitore (conduzione)
▪ In assenza di tensione, non c’è
passaggio di corrente (interdizione)
92 - RETI LOGICHE
Funzionamento del transistor
➢ Due modi per associare i due valori
binari ai due modi di funzionamento
del transistor
➢ Logica positiva
▪ Associare allo stato di conduzione il
valore binario 1
▪ Associare allo stato di interdizione
il valore binario 0
➢ Logica negativa
▪ Associare allo stato di conduzione il
valore binario 1
▪ Associare allo stato di interdizione
il valore binario 0
93 - RETI LOGICHE
Circuiti integrati
➢ I transistor sono dispositivi di materiale
semiconduttore, silicio o arseniuro di
gallio
➢ Transistor e connessioni sono
raggruppati in circuiti integrati
(integrated circuit o chip)
➢ Sono disposti su un wafer di silicio con
un processo litografico
▪ Maschere di integrazione
▪ Densità o scala di integrazione, numero
di transistor per cm2
▪ LSI (low) , MSI (medium), VLSI (very
large), ULSI (ultra large scale
integration)
➢ I chip sono montati tipicamente su
involucri con una doppia fila di pin (dual-
in-line package)
➢ I vari chip sono quindi montati in circuiti
stampati o schede (circuit board)
94 - RETI LOGICHE
Scale di integrazione
➢ Densità o scala di integrazione
▪ numero di transistor per cm2
▪ Oggi: 3-50 M transistor/cm2
➢ Diverse technologie
▪ LSI (low scale integration)
▪ MSI (medium scale integration)
▪ VLSI (very large scale integration)
▪ ULSI (ultra large scale integration)
➢ Un esempio concreto
▪ 10 M transistor/cm2 significa disporre
3200x3200 transitor in un quadrato
con 1 cm di lato
▪ I transistor devono distare 0.003 mm
▪ 20x più vicini del più piccolo
granello di sabbia!
95 - RETI LOGICHE
George Boole Augustus De Morgan
(matematico) (matematico)
2 novembre 1815, Lincoln, Regno Unito 27 giugno 1806, Madurai, India
 8 dicembre 1864, Ballintemple, Cork, Irlanda  18 marzo 1871, Londra, Regno Unito
96

Cap2 CircuitiLogiciCombinatori

Caricato da

Copyright:

Formati disponibili

Cap2 CircuitiLogiciCombinatori

Caricato da

Informazioni sul documento

Titolo originale

Copyright

Formati disponibili

Condividi questo documento

Condividi o incorpora il documento

Opzioni di condivisione

Hai trovato utile questo documento?

Questo contenuto è inappropriato?

Copyright:

Formati disponibili

Cap2 CircuitiLogiciCombinatori

Caricato da

Copyright:

Formati disponibili

Università degli Dipartimento di Ingegneria

Circuiti Logici Combinatori

Prof. Orazio Gambino

Prof. Orazio Gambino

➢ I circuiti logici sono componenti hardware che manipolano

➢ Altra interpretazione che possiamo dare è quella dei CIRCUITI

Si sarebbero potute disegnare le porte AND e OR con una NOT in

➢ La porta NOR è funzionalmente completa perché con essa è

➢ Anche la porta NAND è funzionalmente completa. La porta OR

➢ La porta NOT può essere sostituita da una porta NAND o NOR

➢ A sinistra una AND a tre ingressi. A destra il circuito equivalente

Con la funzione AND è possibile selezionare bit o

➢ Esempio con 3 cifre:

g2=b2; g1=b1 ⊕b2; g0=b0 ⊕ b1

➢ Sia il codice Gray che il numero binario hanno lo stesso MSB,

bi =bi ⊕ gi+1 i = n-1,…, 1

Gray 10010 000 000

➢ il bit più significativo è uguale per entrambi

➢ Rivedi l’esempio precedente con l’operatore XOR e verifica la

RTL TTL ECL CMOS

Porta base NOR NAND OR E NOR NOR o NAND

Tempo di propagazione tp (ns) 12 10 2 50

Freq. di Clock (MHz) 8 15-60 60 5

Fan out 5 10 25 >50

Tensione di alimentazione (V) 3 5 5,2 3-15

1. Si dimostra mettendo a fattor comune ed i.f.3

➢ Attraverso DeMorgan ➢ Usando la dualità

Complemento dei letterali

➢ Riduzione algebrica sistematica (SAR, systematic algebraic

▪ SOP: F(XYZ) = XYZ + XYZ + XYZ + XYZ

▪ POS: F(XYZ) = (X + Y + Z)(X + Y + Z)(X + Y + Z)(X + Y + Z)

➢ Un’espressione algebrica, che rappresenta una funzione, si può

Si=0…n-1 mi = 1, per una funzione di n variabili

Pi=0…n-1 Mi = 0, per una funzione di n variabili

➢ Somma di prodotti (SOP) ➢ Prodotto di somme (POS)

F(XYZ) = XYZ + XYZ + XYZ + XYZ =

F(XYZ) = XYZ + XYZ + XYZ + XYZ = m1 + m3 + m4 + m6

XY+XY XY+XY XY+XY XY+XY

X+Y X+Y X+Y X+Y

Le funzioni booleane generate da queste K-map si ottengono in forma

La seconda K-map semplificata è la porta OR della slide 47.

• La mappa a tre varia- • Le celle 0-2, 4-6 sono

REGOLA: Come nella K-map a 2 variabili, due

REGOLA: Come per il caso della K-map a 3 variabili, l’adiacenza

F=m(4, 5, 6, 12, 13) = B C’ + …

F=m(4, 5, 6, 12, 13) = B C’ + A’ B D’

➢ Semplificare la funzione seguente in forma POS:

➢ Si mostra che la F è la stessa del caso della K-map con le

➢ Errata corrige: Figura 2.25, l’espressione della F è sbagliata nel

1. Individuare i PI assumendo che X = 1

Tenendo conto delle propietà :

Potrebbero piacerti anche