Reti Logiche Combinatorie - unina.stidue.netunina.stidue.net/Calcolatori Elettronici...

00.b

Reti Logiche CombinatorieReti Logiche Combinatorie

AnalisiMinimizzazione booleana

Sintesi

Testo di riferimento: [Congiu] - 2.4 (pagg. 37–57)

34

2

Architettura degli Elaboratori © 2009

Rete logica combinatoria: definizioneRete logica combinatoria: definizione

Una rete logica combinatoria è una rete logica nella quale, in ogni istante, i valori presenti alle uscite sono determinati unicamente dai valori presenti agli ingressinel medesimo istante.

Una rete logica combinatoria è quindi• priva di stato

(non contiene elementi di memoria);• interamente descritta dalla sua

tabella di verità

34

3


Primo esempio: il decodificatore 3/8Primo esempio: il decodificatore 3/8

Un decodificatore è una rete combinatoria che attival’i-esima uscita se e solo seil valore binario codificato dagli ingressi è i

Tabella di verità per un decodificatore con 3 ingressi e 23=8 uscite:

34

4


Decodificatore: realizzazioneDecodificatore: realizzazione

Sono rappresentatesolo le funzioniF0, F1 e F4.

Le porte NOTsono rappresentatecon circoletti “ ”.

34

5


Porte logiche: notazione algebricaPorte logiche: notazione algebrica

Nome Simbolo grafico

Tabelladi verità

Notazione algebrica

AND Y = A·B

OR Y = A+B

NOT Y = A

XOR Y = A⊕B

34

6


Reti logiche: rappresentazioniReti logiche: rappresentazioni

• …mediante uno schema grafico• …mediante una tabella di verità• …mediante una espressione algebrica

Sceglieremo in ciascun caso la rappresentazione più opportuna per quel caso.

Quanto abbiamo visto per le porte logiche vale in generale per le reti logiche.In altre parole, sono tra loro equivalentile tre rappresentazioni…

34

7


Funzione di equivalenza (1 di 3)Funzione di equivalenza (1 di 3)

E= A•B+A•B

È possibile ottenere E attraverso la“somma di prodotti”

34

8



E= (A+B) •(A+B)

...è possibile ottenere E anche attraverso il “prodotto di somme”

34

9



Diversi circuiti logici equivalenti che realizzano la stessa funzione logica

34

10


Algebra di Algebra di BooleBoole o booleanao booleana

L’analisi delle proprietà delle espressioni algebriche costruite da variabili binarie e operatori logici, si deve al matematico G. Boole(1815-1864), ed è nota come algebra booleana.

S = B•(A•B) + A•(A•B) ?

34

11


Algebra di Algebra di BooleBoole: propriet: proprietàà (1 di 2)(1 di 2)

A

A·1 = A A·0 = 0 A·A = A A·A = 0

A = A A+0 = A A+1 = 1 A+A = A

A+A = 1

Proprietà commutativa, associativa e distributiva:

A·B = B·A A+B = B+A A·(B·C) = (A·B)·C

A+(B+C) = (A+B)+C A·(B+C) = A·B+A·C

A+(B·C) = (A+B)·(A+C)

34

12


Algebra di Algebra di BooleBoole: propriet: proprietàà (2 di 2)(2 di 2)

A

Legge di De Morgan:

A + B = A · B

A · B = A + B

34

13


S’ = A•B+A•B = A⊕BC’ = A•B

Sintesi di un Sintesi di un halfhalf--adderadder (1 di 2)(1 di 2)

34

14


Sintesi di un Sintesi di un halfhalf--adderadder (2 di 2)(2 di 2)

S’ = A•B + A•B

S’ = A•B • A•B

S’ = (A•B+B•B) • (A•B+A•A)

S’ = B•(A+B) • A•(A+B)

S’ = B•(A•B) • A•(A•B)

Utilizziamo l’algebra booleana e le sue proprietàper riscrivere S’ utilizzando solo porte NAND:

34

15


HalfHalf--adderadder con sole porte NANDcon sole porte NAND

S’ = B•(A•B) • A•(A•B)

C’ = A•B

34

16


Sintesi di un Sintesi di un fullfull--adderadder (1 di 2)(1 di 2)

S = A•B•C” + A•B•C” + A•B•C” + A•B•C”

S = (A•B + A•B)•C” + (A•B + A•B)•C”

S = (A⊕B)•C” + (A⊕B)•C” = (A⊕B) ⊕ C”

S = S’ ⊕ C”C = A•B•C” + A•B•C” + A•B•C” + A•B•C”

C = (A•B + A•B)•C” + A•B•(C” + C”) = (A⊕B)•C” + A•B

C = S’•C” + C’

S’ = (A⊕B)

C’ = A•B

Half-Adder

34

17


Sintesi di un Sintesi di un fullfull--adderadder (2 di 2)(2 di 2)

S = S’ ⊕ C”

C = S’•C” + C’

34

18


FullFull--adderadder con sole porte NANDcon sole porte NAND

C = S’•C” + C’ = S’•C” • C’

34

19


Sommatore binario da 4 bitSommatore binario da 4 bit

34

20


Sommatore binario da 16 bitSommatore binario da 16 bit

34

21


Minimizzazione: Mappe di Minimizzazione: Mappe di KarnaughKarnaugh (1/7)(1/7)

Tra le proprietà dell’algebra di Boole, le seguenti consentono di semplificare notevolmente le espressioni booleane:A•B + A•B = A•(B + B) = AA•(B•C + B•C + B•C + B•C) = ALe mappe di Karnaugh sono una particolare forma di tabella di verità, che consente di individuare immediatamente la possibilità di fare queste semplificazioni.

34

22


Minimizzazione: Mappe di Minimizzazione: Mappe di KarnaughKarnaugh (2/7)(2/7)

Ad esempio, la seguente tabella di verità della funzione Y=Y(A,B,C) A B C Y A 0 0 1 1 0 0 0 0 B 0 1 1 0 0 0 1 0 può essere ridisegnata così: C 0 1 0 0 0 0 0 1 0 0 1 1 1 1 0 0 0 1 0 1 1 1 1 0 1 1 1 1 0 1 Mappa di Karnaugh della funzione Y 1 1 1 1 Nelle mappe di K. i valori della funzione sono scritti dentro le caselle.

Dalla tabella di verità o dalla mappa di Karnaugh è immediato ottenere l’espressione booleana della funzione Y come “somma” di “prodotti”, cioè come OR di tanti termini AND quante sono le caselle in cui la funzione vale 1; ciascuno di questi termini AND (detti minterm) è costituito dall’AND delle variabili di ingresso, negate oppure no a seconda che il valore della variabile associato a quella casella sia 0 oppure 1: Y = A•B•C + A•B•C + A•B•C + A•B•C

34

23


Minimizzazione: Mappe di Minimizzazione: Mappe di KarnaughKarnaugh (3/7)(3/7)Nel caso di funzioni di 4 variabili, ad es. Z=Z(A,B,C,D), la mappa di Karnaugh ha 4 righe e quattro colonne:

CD

AB 0 0

0 1

1 1

1 0

00 0 0 1 0

01 1 0 1 1

11 1 1 1 1

10 1 1 1 0

Mappa di Karnaugh della funzione Z

I valori delle variabili A,B,C,D individuano le “coordinate” delle caselle:le coppie di valori di A e B (di C e D) associate alle colonne (alle righe)sono ordinate in modo che tra due caselle adiacenti (della medesima riga o della medesima colonna) cambi il valore di una sola delle variabili, mentre quello di tutte le altre rimane lo stesso; ciò vale anche tra le caselle estreme di ciascuna riga e di ciascuna colonna (che possono quindi essere considerate “adiacenti”, in senso circolare).

34

24


Minimizzazione: Mappe di Minimizzazione: Mappe di KarnaughKarnaugh (4/7)(4/7)In questo modo a ciascuna coppia di caselle adiacenti contrassegnate con il valore 1 corrispondono, nella espressione booleana, due termini “prodotto” (minterm) nei quali una variabile è presente negata in uno e non negata nell’altro, mentre tutte le altre variabili hanno lo stesso valore.

E` allora possibile semplificare l’espressione sostituendo quei due termini con un unico termine nel quale non è più presente la variabile che cambia valore.

Ad esempio le ultime due caselle della seconda riga nella mappa della funzione Y portano alla seguente semplificazione:

A•B•C + A•B•C = A•C

34

25


Minimizzazione: Mappe di Minimizzazione: Mappe di KarnaughKarnaugh (5/7)(5/7)Allo stesso modo, quaterne di caselle adiacenti tutte con il valore 1 (sulla stessa riga o sulla stessa colonna) corrispondono a quattro termini che si riducono ad uno; ad esempio le quattro caselle della terza riga nella mappa della funzione Z portano alla seguente semplificazione:

C•D•(A•B + A•B + A•B + A•B) = C•D

le quattro caselle della terza colonna nella mappa della funzione Z portano alla seguente semplificazione:

A•B•(C•D + C•D + C•D + C•D) = A•B

Così pure quaterne adiacenti disposte secondo un quadrato producono un unico termine; ad esempio le quattro caselle in basso a sinistra nella mappa della funzione Z portano alla seguente semplificazione:

A•C•(B•D + B•D + B•D + B•D) = A•C

Analogo discorso vale per gruppi di otto caselle adiacenti tutte con il valore 1.

34

26


Minimizzazione: Mappe di Minimizzazione: Mappe di KarnaughKarnaugh (6/7)(6/7)Per semplificare l’espressione di una funzione, si individuano, nella mappa di K., i gruppi di (2 o 4 o 8) caselle adiacenti con il valore 1. Spesso conviene sfruttare la proprietà A+A=A, che consente di utilizzare più volte la stessa casella (lo stesso minterm), per formare gruppi diversi e ottenere il maggior numero di semplificazioni possibile. Individuando un insieme di gruppi (da 1, 2, 4 o 8) che copra tutte le caselle in cui compare il valore 1, si ottiene una espressione semplificata, costituita dall’OR dei termini corrispondenti a ciascun gruppo. Ad es. per la funzione Z, si possono individuare i gruppi segnati in figura:

CDAB0 0

0 1

1 1

1 0

00 0 0 1 0

01 1 0 1 1

11 1 1 1 1

10 1 1 1 0

A•C A•B B•D

Si ottiene, immediatamente, l’espressione semplificata: Z=A•C+A•B+B•D

34

27


Minimizzazione: Mappe di Minimizzazione: Mappe di KarnaughKarnaugh (7/7)(7/7)Funzioni booleane parzialmente definite: il loro valore è specificato solo per alcune combinazioni dei valori delle variabili. Le altre combinazioni o non si verificano mai o il valore della funzione non interessa: don’t care conditions (d.c.c.). In una mappa di K. è spesso utile inserire un valore 1 al posto di d.c.c. (per formare ulteriori raggruppamenti). Es. Funzione parzialmente definita W (i trattini individuano d.c.c.): A B C W A 0 0 1 1 0 0 0 - B 0 1 1 0 0 0 1 1 C 0 1 0 - 0 - - - 1 0 1 1 - 1 0 0 1 1 1 - 0 - 1 0 1 - 1 1 0 - 1 1 1 0 A 0 0 1 1 Si possono sostituire due B 0 1 1 0 d.c.c. con altrettanti 1: C 0 1 - - 1 1 1 - 0 1

si forma la quaterna con cui si ottiene l’espressione semplificata: W = B

34

28


EncoderEncoder

X0

X1

X2

X3

Y0

Y1Analogamente:Y1 = X2 + X3

X0 0 0 1 1X1 0 1 1 0X2 X3

0 0 - 1 - 0

0 1 1 - - -

1 1 - - - -

1 0 0 - - -

Y0 = X1 + X3

Y0

34

29


MultiplexerMultiplexer

0 1 2 3 4 5 6 7

DEC 3/8

X0

X1

X7

C2 C1 C0

Y

34

30


X

C1 C0

0 1 2 3

DEC 2/4

Y0

Y1

Y2

Y3

DemultiplexerDemultiplexer

34

31


Sintesi a due livelliSintesi a due livelli

Sintesi come “somma di prodotti”

34

32


Sintesi tramite PLASintesi tramite PLA

PLA = “Programmable Logic Array”

Tipicamente, p < 2i

34

33


Sintesi tramite ROM (1 di 2)Sintesi tramite ROM (1 di 2)

34

34


Sintesi tramite ROM (2 di 2)Sintesi tramite ROM (2 di 2)

00.b

FineFine

Reti logiche combinatorie

Reti Logiche Combinatorie - unina.stidue.netunina.stidue.net/Calcolatori Elettronici...

Documents

Transcript of Reti Logiche Combinatorie - unina.stidue.netunina.stidue.net/Calcolatori Elettronici...