2

INVERTER

X X’

X X’0 11 0

se X=0 allora X’=1se X=1 allora X’=0

OR

AB

C=A+B

A B C0 0 00 1 11 0 11 1 1

se A=1 O B=1 allora C=1 altrimenti C=0

AB

C=A·B

A B C0 0 00 1 01 0 01 1 1

se A=1 E B=1 allora C=1 altrimenti C=0

AND

Funzioni logiche: algebra booleana

3

gate AND

Diagrammi temporali

4

OR Gategate OR

5

Inverterinverter

6X=q1

Il contatore binario sincrono a due bit

Possiamo generare automaticamente questa sequenza?

tempo

Usiamo il segnale di clock della scheda per scandire il tempo

clk

Y=q0

1 per un ciclo di clock, 0 per un ciclo di clock

1 per due cicli di clock, 0 per due ciclo di clock

7

X=q1

Y=q00

0

1

0

0

1

1

1

q1q0: numero a due bit

Campioniamo q1q0 numero a un tempo prefissato dopo il bordo di salita di clk

campionamento sincrono

0 1 2 3

Numero binario a due bit che aumenta di 1 a ogni ciclo di clock

La cifra più grande di un numero a 2 bit è tre al ciclo successivo la sequenza riparte da zero

0

0

1

0

0

1

1

1

0

0

0 1 2 3

8

Un circuito che produce questa sequenza che si ripete all’infinito è il contatore sincrono a due bit

clk

Segnale di input: clk

res segnale di input: reset ogni volta che è asserito la sequenza riparte da zero

q0

q1

numero binario di output

q[1..0]

Diversa rappresentazione: raggruppamento in un bus

0 1 2 3 0 1 2 3 0

Nel circuito reale il conteggio cambia sempre un pò dopo il bordo del clock

9

Più input

• Funzionano allo stesso modo• Com’è l’output?

10

Qualunque espressione booleana può essere implementata come un circuito logico.

F = [A(C+D)]’+BE

CD

C+D[A(C+D)]’ [A(C+D)]’+BE

BE

BE

AA(C+D)

Espressioni booleane e circuiti logici

F=Y’Z+X

Z

Y’YY’Z+X

X

11

• 2n righe• dove n # di• variabili

Rappresentazione: tavola della verità

F=Y’Z+X

Z

Y’YY’Z+X

X

12

X+0 = X

X0

C=XX 0 C0 0 01 0 1

X+1 = 1

X1

C=1X 1 C0 1 11 1 1

X0

C=0

X·0 = 0

X 0 C0 0 01 0 0

X1

C=X

X·1 = X

X 1 C0 1 01 1 1

Teoremi fondamentali: operazioni con 0 e 1

13

X+X = X

XX

C=XX X C0 0 01 1 1

XX

C=X

X·X = X

X X C0 0 01 1 1

Teoremi fondamentali: leggi idempotenti

14

X

(X’)’=X

BC=X

X B C0 1 01 0 1

Teoremi fondamentali: legge di involuzione

15

X+X’ = 1

XX’

C=1X X’ C 0 1 1 1 0 1

XX’

C=0

X·X’ = 0

X X’ C0 1 01 0 0

Teoremi fondamentali: legge di complementarità

16

X può essere una funzione arbitrariamente complessa.

Semplifichiamo le seguenti espressioni booleane il più possibile usando i teoremi fondamentali.

(AB’ + D)E + 1 =(AB’ + D)(AB’ + D)’ =(AB + CD) + (CD + A) + (AB + CD)’ =

(AB’ + D)E + 1 = 1(AB’ + D)(AB’ + D)’ = 0(AB + CD) + (CD + A) + (AB + CD)’ = 1

Semplificazione delle espressioni usando i teoremi fondamentali

17

(X+Y)+Z = X+(Y+Z)

X Y Z X+Y (X+Y)+Z Y+Z X+(Y+Z)0 0 0 0 0 0 00 0 1 0 1 1 10 1 0 1 1 1 10 1 1 1 1 1 11 0 0 1 1 0 11 0 1 1 1 1 11 1 0 1 1 1 11 1 1 1 1 1 1

XY

ZC

YZ

XC

Legge associativa

18

(XY)Z = X(YZ)

X Y Z XY (XY)Z YZ X(YZ)0 0 0 0 0 0 00 0 1 0 0 0 00 1 0 0 0 0 00 1 1 1 0 1 01 0 0 0 0 0 01 0 1 0 0 0 01 1 0 1 0 0 01 1 1 1 1 1 1

XY

ZC

YZ

XC

Legge associativa

19

X(Y+Z) = XY+XZ

X Y Z Y+Z X(Y+Z) XY XZ XY+XZ 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 1 0 1 0 0 0 0 0 1 1 1 0 0 0 0 1 0 0 0 0 0 0 0 1 0 1 1 1 0 1 1 1 1 0 1 1 1 0 1 1 1 1 1 1 1 1 1

Prima legge distributiva

20

X(Y+Z) = XY+XZ



21

X(Y+Z) = XY+XZ



22

X(Y+Z) = XY+XZ



23

X(Y+Z) = XY+XZ



24

X+YZ = (X+Y)(X+Z)

X Y Z YZ X+YZ X+Y X+Z (X+Y)(X+Z)0 0 0 0 0 0 0 00 0 1 0 0 0 1 00 1 0 0 0 1 0 00 1 1 1 1 1 1 11 0 0 0 1 1 1 11 0 1 0 1 1 1 11 1 0 0 1 1 1 11 1 1 1 1 1 1 1

Seconda legge distributiva

25

X+YZ = (X+Y)(X+Z)

X Y Z YZ X+YZ X+Y X+Z (X+Y)(X+Z) 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 1 0 0 0 1 0 0 0 1 1 1 1 1 1 1 1 0 0 0 1 1 1 1 1 0 1 0 1 1 1 1 1 1 0 0 1 1 1 1 1 1 1 1 1 1 1 1

Seconda legge distributiva

26

(X + Y)(X + Z) = X(X + Z) + Y(X + Z) (usando la prima legge distributiva)

= XX + XZ + YX + YZ (usando la prima legge distributiva)

= X + XZ + YX + YZ (usando la legge idempotente)

= X·1 + XZ + YX + YZ (usando X1=X)

= X(1 + Z + Y) + YZ (usando la legge distributiva)

= X·1 + YZ (usando 1+Z+Y=1)

= X + YZ (usando X1=X)

Seconda legge distributiva (una dimostrazione alternativa)

27

(X + Y’)Y = XYXY + Y’Y = XY + 0 = XY

XY’ + Y = X + Y(using the second distributive law)XY’ + Y = Y + XY’ = (Y + X)(Y + Y’) = (Y + X)·1 = X + Y

XY + XY’ = XXY + XY’ = X(Y + Y’) = X·1 = X

X + XY = XX(1 + Y) = X·1 = X

(X + Y)(X + Y’) = X(X + Y)(X + Y’) = XX + XY’ + YX + YY’ = X + X(Y’ + Y) + 0 = X + X·1 = X

X(X + Y) = XX(X + Y) = XX + XY = X·1 + XY = X(1 + Y) = X·1 = X

Teoremi per semplificare

28(X + Y)

(X + Y)

+

(X + Y’)(X + Y)

( X + Y’) Y = XY

XY + XY’ = X

X + XY = X

Teoremi per semplificare e dualità

(X + Y)(X + Y’) = X

DUALE

Qualunque teorema o identità in algebra booleana resta vero se 0 e 1 sono scambiati e • e + sono pure scambiati ovunque.

X(X + Y) = X

X

XY’

XY’ + Y = X + Y

Y

29

Nell’applicare il principio di dualità dobbiamo fare attenzione alla precedenza degli operatori nell’espressione originale:

Esempio di applicazione non corretta del principio:X + X • Y = X

X • X + Y = X (dualità)X + Y = X (idempotenza)

X + X • Y = X

X • (X + Y) = X (dualità)

Dualità

• ha precedenza

uso di parentesi

Non senso!

30

Semplifichiamo la seguenta espressione:

W = [M + N’P + (R + ST)’][M + N’P + R + ST]

W = M + N’P

X = M + N’P Y = R + STW = (X + Y’)(X + Y)

W = XX + XY + Y’X + Y’Y

W = X·1 + XY + XY’ + 0

W = X + X(Y + Y’) = X + X·1 = X

Esempi

31

Il complemento della somma è uguale al prodotto dei complementi

(X+Y)’ = X’Y’

XY

Z

X Y X+Y (X+Y)’ X’ Y’ X’Y’0 0 0 1 1 1 10 1 1 0 1 0 01 0 1 0 0 1 01 1 1 0 0 0 0

Z

Y

X

La prima legge di De Morgan

32

(X+Y)’ = X’Y’

XY

Z

X Y X+Y (X+Y)’ X’ Y’ X’Y’0 0 0 1 1 1 10 1 1 0 1 0 01 0 1 0 0 1 01 1 1 0 0 0 0

Z

Y

X



33

(X+Y)’ = X’Y’

XY

Z

X Y X+Y (X+Y)’ X’ Y’ X’Y’0 0 0 1 1 1 10 1 1 0 1 0 01 0 1 0 0 1 01 1 1 0 0 0 0

Z

Y

X



34

(X+Y)’ = X’Y’

XY

Z

X Y X+Y (X+Y)’ X’ Y’ X’Y’0 0 0 1 1 1 10 1 1 0 1 0 01 0 1 0 0 1 01 1 1 0 0 0 0

Z

Y

X



35

(X+Y)’ = X’Y’

XY

Z

X Y X+Y (X+Y)’ X’ Y’ X’Y’ 0 0 0 1 1 1 1 0 1 1 0 1 0 0 1 0 1 0 0 1 0 1 1 1 0 0 0 0

Z

Y

X



36

Il complemento del prodotto è uguale alla somma dei complementi

(XY)’ = X’ + Y’

ZXY

X Y XY (XY)’ X’ Y’ X’ + Y’0 0 0 1 1 1 10 1 0 1 1 0 11 0 0 1 0 1 11 1 1 0 0 0 0

Z

Y

X

La seconda legge di De Morgan

37

Abbiamo già parlato abbondantemente dei NOR e NAND

XY

Z XY

Z

ZXY

XY

Z

NOR e NAND e altri simboli

ZY

XZ

Y

X

NOR

NAND

Spesso si usano abbreviazioni simili anche per gli input negati. Ad esempio

41

La legge di De Morgan si generalizza a n variabili:

(X1 + X2 + X3 + ··· + Xn)’ = X1’X2’X3’ ··· Xn’

(X1X2X3 ··· Xn)’ = X1’ + X2’ + X3’ + ··· + Xn’

Legge di De Morgan (cont.)

43

Esprimiamo il complemento f’(w,x,y,z) della seguente espressione in forma semplificata.

f(w,x,y,z) = wx(y’z + yz’)

f’(w,x,y,z) = w’ + x’ + (y’z +yz’)’

= w’ + x’ + (y’z)’(yz’)’

= w’ + x’ + (y + z’)(y’ + z)

= w’ + x’ + yy’ + yz + z’y’ + z’z

= w’ + x’ + 0 + yz + z’y’ + 0

= w’ + x’ + yz + y’z’

Legge di De Morgan (esempio)

44

Logica positiva: la tensione high (+V) rappresenta 1 e la tensione low (0V) rappresenta 0

Logica negativa: la tensione high (+V) rappresenta 0

e la tensione low (0V) rappresenta 1

Logica positiva e negativa

45

gate logico

e2

e3

e1

eo

lo stesso circuito fisico implementa diverse funzioni logiche. La funzione implementata depende dalla logica usata per Interpretare gli input e gli output.

e1 e2 e3 eo

0V 0V 0V 0V0V 0V +V 0V0V +V 0V 0V0V +V +V 0V+V 0V 0V 0V+V 0V +V 0V+V +V 0V 0V+V +V +V +V

+

Tensioni elettriche

e1 e2 e3 eo

0 0 0 00 0 1 00 1 0 00 1 1 01 0 0 01 0 1 01 1 0 01 1 1 1

+

Logica positiva

e1 e2 e3 eo

1 1 1 11 1 0 11 0 1 11 0 0 10 1 1 10 1 0 10 0 1 10 0 0 0

+

Logica negativa

Logica positiva e negativa (esempio)

AND OR

46

XY + X’Z + YZ = XY + X’Z

= XY + X’Z + (X + X’)YZ

= XY + X’Z + XYZ + X’YZ

= XY + XYZ + X’Z + X’YZ

= XY(1 + Z) + X’Z(1 + Y)

= XY·1 + X’Z·1

XY + X’Z + YZ = XY + X’Z + 1·YZ

= XY + X’Z

Il teorema del consenso

47

Data una tavola della verità, possiamo implementare F facendo l’OR di tutti i termini che sono 1

Dalla tavola della verità alla funzione

Tavola della verità della funzione F = X + Y’Z

Esempio

Z Y XF '' '''' Z XYZ Y XF ZXYZ XYZ Y XF ''''' '''''' XYZZXYZ XYZ Y XF XYZXYZZXYZ XYZ Y XF ''''''

Esercizio: semplificare questa espressione

48

• Questo sistema non produce necessariamente l’espressione di F più semplice

• Ma è meccanico passare dalla tavola della verità a F

• Definizioni:– Termini prodotto – AND A’BZ– Termini somma – OR X + A’– Somma e prodotto logico, non aritmetico

Forme standard

49

Termine prodotto in cui tutte le variabili appaiono una volta (complementate or no)

Definizione: mintermine

• Per n variabili ci saranno 2n mintermini• Come i numeri binari da 0 to 2n-1

50

Somma di mintermini

Complemento di F

Sommiamo semplicemente sugli altri mintermini

F’= m1 + m3 + m4 + m6

F: OR di tutti i mintermini della tavola della verità con un 1

F = X’Y’Z’ F = X’Y’Z’ + X’YZ’ F = X’Y’Z’ + X’YZ’ + XY’Z F = X’Y’Z’ + X’YZ’ + XY’Z + XYZ

Eserizio: semplificare F, scrivere l’espressione per F’ e semplificarla

52

• La semplificazione di una somma di mintermini può dare una somma di prodotti

• La differenza è che ciascun termine non ha necessariamente tutte le variabili

• Gates risultanti • diversi AND e un OR

Semplificazione di somme di prodotti

La somma di prodotti ha due livelli di gate

53

Termine somma in cui tutte la variabili appaiono una volta (complementate o no)

Maxtermini

In un maxtermine una variabile è complementata se il corrispondente bit nella rappresentazione binaria di è 1

54

Possiamo esprimere F come AND di tutte le righe che producono un output uguale a 0

F =

(X + Y + Z’)(X +Y’+Z’)(X’+Y+Z)(X’+Y’+Z)

OR seguiti da un AND

Prodotto di maxtermini

I mintermini e maxtermini con lo stesso indice sono complementi:

m0’ = (X’Y’Z’)’ = X + Y + Z = M0

55

Rivelatore di numeri primi

Data una combinazione di input a 4 bit N = N3N2N1N0 questo circuito produce un output pari a 1 per N = 1, 2, 3, 5, 7, 11, 13 e 0 altrimenti

La tavola della verità è N3 N2 N1 N0 F 0 0 0 0 0 0 0 0 1 1 0 0 1 0 1 0 0 1 1 1 0 1 0 0 0 0 1 0 1 1 0 1 1 0 0 0 1 1 1 1 1 0 0 0 0 1 0 0 1 0 1 0 1 0 0 1 0 1 1 1 1 1 0 0 0 1 1 0 1 1 1 1 1 0 0 1 1 1 1 0

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

Esercizio:

Determinare l’espressione logica e semplificarla

56

Display: array di 7 led rossi

Progetto: visualizzazione di cifre su un display

Sulla scheda sono presenti 4 array

57

Come si controlla ciascun array?

7 segmenti 7 segnali a, b, c, d, e, f, g controllati dalla fpga – se uno di essi è asserito si accende il led corrispondente

a b c d e f g

led[6..0]

In questo progetto mandiamo la stessa cifra a tutti e quattro gli array

Vedremo un uso più sofisticato con controllo indipendente di ciascun array più avanti

58

Progetto: visualizzare un numero da zero a sette sugli array

Primo step scrivere la tavola della verità delle seguenti funzioni logiche:

Input: numero binario a 3 bit q[2..0] Outputs: a, b, c, d, e, f, g richiesti per visualizzare tale numero binario

Es. Il led a è asserito quando il numero di input q[2..0] è :

0 oppure 2 oppure 3 oppure 5 oppure sei oppure 7 oppure 8 oppure 9

q2 q1 q0 a b c d e f g 0 0 0 0 0 1 0 1 0 0 1 1 1 0 0 1 0 1 1 1 0 1 1 1

Completare la tavola per ciascuno dei led

60

Secondo step: determinare le equazioni logiche a partire dalla tavola della verità per ciascuno dei sette segnali col metodo meccanico della somma di mintermini

Terzo step: minimizzare le espressioni logiche con i teoremi dell’algebra booleana

Quarto step: disegnare il circuito che ha come input q2, q1, q0 e come output a, b, c, d, e, f, g con QUARTUS

Disegno implementato con una struttura gerarchica

vediamo cosa vuol dire e come si procede

61

Struttura gerarchica di uno schema

Foglio principale:

LabElettronica

62

Clickate sul menu File e selezionate New

63

Selezionare Block diagram / schematic file

64

Appare un nuovo foglio di disegno. Salvarlo col nome seven-seg-decoder

65

In questo foglio implementiamo il circuito. Cominciamo a mettere gli input (q[2..0]) e gli output (a, b, c, d, e, f, g)

Disegnate poi tutto il circuito e salvate il file nuovamente

66

Creiamo un simbolo per il circuito corrispondente al file seven-seg-decoder

Il simbolo può essere quindi usato come componente in altri fogli di disegno

67

Torniamo al foglio di disegno principare (LabElettronica)

selezioniamo col mouse symbol tool

68

Compare la finestra che permette di selezionare simboli di componenti

Scrivere seven-seg-decoder: appare il simbolo del nuovo componente

Clickare OK

69

Il componente può essere ora posizionato nel foglio principale

70

Pilotiamo l’input q[2..0] con un valore costante attraverso un componente lpm_constant

71

Gli output a, b, c, d, e, f, g del componente seven-seg-decoder nel foglio LabElettronica vanno collegati ai pin di output denominati led[0], ..., led[6] che devono essere assegnati ai numeri dei pin fisici 144, 143, 142, 141, 140, 139, 136 come da schema della scheda in figura sotto

i pin led[6..0] corrispondono ad g, f, e, d, c, b, a

72

Teniamo deasserito permanentemente led[7]:

Collegato a massa nel foglio principale e mandato al pin di output led[7] corrispondente al pin 135

DP

led[7]

DIS[3..0]COM3, COM2, COM1, COM0

Ci sono altri due segnali da considerare sugli array

DP: segnale che accende la virgola

COM# segnale di abilitazione (enable): i led di un array si accendono solo se il corrispondente segnale COM# è asserito

73

Controllo dei segnali COM#

Decidiamo in quale array visualizzare la cifra controllando i segnali COM# con i quattro tasti presenti sulla scheda

SW0

SW1SW2SW3

74

Collegati ai tasti

DIS[3..0]COM3, COM2, COM1, COM0

Nel foglio principale definiamo:

- 4 input SW0, SW1, SW2, SW3 – 4 output DIS0, DIS1, DIS2, DIS3

Collegate SW# al corrispondente DIS#

Attenzione: SW# sono attivi bassi per cui vanno invertiti prima di collegarli a DIS#

75

Quinto step: simulare il comportamento del circuito QUARTUS

verifica: mandatemi per email tutti i file del progetto – potete lavorare in coppia

Avete 7 giorni di tempo (prova lunedì prossimo)

Sesto step: provare il funzionamento del circuito sulla scheda

76

Addizionatore a un bit

82

Progettiamo un circuito logico che implementi un addizionatore a due bit. Questo circuito ha tre input (A, B, Cin) e due output (S, Cout). L’output S è uno se la somma è uno, cioè se il numero di input uguale a uno è dispari. L’output del riporto è uno se la somma produce un riporto, cioè se due o più input sono uno.

Adder

Cin

Cout

SB

A

A B Cin S Cout0 0 0 0 00 0 1 1 00 1 0 1 00 1 1 0 11 0 0 1 01 0 1 0 11 1 0 0 11 1 1 1 1

+

Addizionatore completo a un bit

83

Adder

Cin

Cout

SB

A

A B Cin S Cout0 0 0 0 00 0 1 1 00 1 0 1 00 1 1 0 11 0 0 1 01 0 1 0 11 1 0 0 11 1 1 1 1

+

S = A’B’Cin + A’BCin’ + AB’Cin’ + ABCin

Cout = A’BCin + A B’Cin + ABCin’ + ABCin

= A’BCin + ABCin + AB’Cin + ABCin + ABCin’ + ABCin

= BCin + ACin + AB

= (A’ + A)BCin + (B’ + B)ACin + (Cin’ + Cin)AB

= 1·BCin + 1· ACin + 1· AB

84

Problema: progettare un circuito logico per far funzionare in modo automatizzato l’allarme di una macchina. Il manuale dell’allarme fornisce i seguenti dettagli sul funzionamento.

“L’allarme si spegnerà se il sistema di allarme è attivato e una qualunque delle due porte o il cofano sono aperti, o se il sensore di vibrazione è attivato e la chiave non è inserita.”


AllarmeAttivatoPortaConducenteApertaPortaPasseggeroApertaCofanoApertoVibrazioneChiaveInserita

Inputs:

Realizzare circuiti pratici

85

AllarmeSpento = AllarmeAttivato • (PortaConducenteAperta + PortaPasseggeroAperta + CofanoAperto) + Vibrazione • (ChiaveInserita)’



AllarmeAttivatoPortaConducenteApertaPortaPasseggeroApertaCofanoApertoVibrazioneChiaveInserita

Inputs:

86

VibrazioneChiaveInserita

AllarmeSpento

PortaConducenteApertaPortaPasseggeroAperta

CofanoAperto

AllarmeAttivato


AllarmeSpento = AllarmeAttivato • (PortaConducenteAperta + PortaPasseggeroAperta + CofanoAperto) + Vibrazione • (ChiaveInserita)’

Esercizio: implementare e simulare questo circuito con QUARTUS

87

Le mappe di Karnaugh erano (relativamente) utili quando la gente eseguiva la semplificazione a mano

Il processo di semplificazione al giorno d’oggi è completamente eseguito da algoritmi computerizzati

Illustreremo le mappe principalmente per avere una comprensione più profonda, non come strumento reale.

Minimizzazione di funzioni logiche: mappe di Karnaugh

88

A=0 A=1

A=0,B=1 cella 1

A=1,B=1 cella 3

A=0,B=0 cella 0

A=1,B=0 cella 2

Anatomia delle mappe di Karnaugh

Una mappa è una rappresentazione grafica di una tavola della verità.

Un “box” per ciascuna riga della tavola contente il valore della funzione (zero oppure uno

Tavola della veritàdi una funzione di una variabileA B F0 0 cella 00 1 cella 11 0 cella 21 1 cella 3

A

B

0 1

0

1

Tavola della veritàdi una funzione di una variabileA F0 cella 01 cella 1

A Indica il box corrispondente ad A=1

89

B=1

C

0

1

A=1

00 01 11 10A,B

Mappe di Karnaugh per funzioni di tre variabili

A B C0 0 0 cella 00 0 1 cella 10 1 0 cella 20 1 1 cella 31 0 0 cella 41 0 1 cella 51 1 0 cella 61 1 1 cella 7

Disposizione di righe e colonne: ciascuna cella corrisponde a una combinazione di input che differisce da quelle adiacenti in una sola variabile

8 celle

90

A

C

B

00 01 11 10

0

1

A=1,B=0,C=0

A=1,B=0,C=1A=0,B=0,C=1

A=0,B=0,C=0

A=0,B=1,C=0 A=1,B=1,C=0

A=0,B=1,C=1 A=1,B=1,C=1

Mappe di Karnaugh per funzioni di tre variabili

A B C0 0 0 cella 00 0 1 cella 10 1 0 cella 20 1 1 cella 31 0 0 cella 41 0 1 cella 51 1 0 cella 61 1 1 cella 7

Disposizione di righe e colonne: ciascuna cella corrisponde a una combinazione di input che differisce da quelle adiacenti in una sola variabile

AB

92

Adder

Cin

Cout

SB

A

A B Cin S Cout0 0 0 0 00 0 1 1 00 1 0 1 00 1 1 0 11 0 0 1 01 0 1 0 11 1 0 0 11 1 1 1 1

+

Alternativamente, come si usa una mappa di

Karnaughinvece della

semplificazione algebrica?

Esempio d’uso delle mappe di Karnaugh: l’addizionatore a un bit

S = A’B’Cin + A’BCin’ + AB’Cin’ + ABCin

Cout = A’BCin + A B’Cin + ABCin’ + ABCin

= A’BCin + ABCin + AB’Cin + ABCin + ABCin’ + ABCin

= BCin + ACin + AB

= (A’ + A)BCin + (B’ + B)ACin + (Cin’ + Cin)AB

= 1·BCin + 1· ACin + 1· AB

Equazioni logiche determinate con l’algebra booleana

93

Adder

Cin

Cout

SB

A

A B Cin S Cout0 0 0 0 00 0 1 1 00 1 0 1 00 1 1 0 11 0 0 1 01 0 1 0 11 1 0 0 11 1 1 1 1

+

A

Cin

B

Mappa per Cout

00 01 11 10

0

1

A,B

Scriviamo in ogni cella il valore della funzione logica (Cout in questo caso)

0

10

0

1

0

1

1

94

Ciascuna cella contenente un 1 corrisponde a un mintermine da considerare nella somma di mintermini della funzione

A

Cin

B

00 01 11 10

0

1

A,B

1

A=1, B=1 Cin=0 mintermine ABCin’

1

A=0, B=1 Cin=1 mintermine A’BCin

1 A=1, B=1 Cin=1 mintermine ABCin1

A=1, B=0 Cin=1 mintermine AB’Cin

La funzione logica non ancora minimizzata è

Cout = ABCin’ + A’BCin + ABCin + AB’Cin

95

A

Cin

B

0

0

0 01

1 1 1

Ricordiamo la disposizione di righe e colonne: ciascuna cella corrisponde a una combinazione di input che differisce da quelle adiacenti in una sola variabile

Poichè coppie di celle 1 adiacenti hanno minitermini che differiscono in una sola variabile, possiamo combinarle (cioè combinare la somma di mintermini) in un solo termine usando la legge dell’alegra booleana

XY’+XY=X

Passo successivo: dobbiamo ricoprire tutte le celle contenti un 1 usando rettangoli i più grandi possibile e col minor numero di rettangoli possibile

Il numero di celle racchiuse deve essere multiplo di 2 (1,2, 4, ...)

Consideriamo ad esempio

97

ACin

A

Cin

B

0

0

0 01

1 1 1

Regola meccanica: questo gruppo di celle (corrispondente a una somma di 2 mintermini) è equivalente a un singolo termine prodotto in cui:

In questo termine si considerano solo le variabili che hanno lo stesso valore in tutte le celle del gruppo:

In questo caso B varia per cui non si considera

Siccome A e Cin hanno entrambi valore 1 devono apparire non complementati

98

ACin

A

Cin

B

0

0

0 01

1 1 1

A

Cin

B

0

0

0 01

1 1 1

ABCin+ABCin’=AB

A

Cin

B

0

0

0 01

1 1 1

ABCin+A’BCin=BCin

A

B

Cin

0

0

0 01

1 1 1

Cout=ACin+BCin+AB

Dobbiamo ancora finire di ricoprire tutte le celle

99

A

Cin

B

Adder

Cin

Cout

SB

A

A B Cin S Cout0 0 0 0 00 0 1 1 00 1 0 1 00 1 1 0 11 0 0 1 01 0 1 0 11 1 0 0 11 1 1 1 1

+

0

1

1 10

0 1 0

Mappa di Karnaugh per S

S =


100

A

Cin

B

Adder

Cin

Cout

SB

A

A B Cin S Cout0 0 0 0 00 0 1 1 00 1 0 1 00 1 1 0 11 0 0 1 01 0 1 0 11 1 0 0 11 1 1 1 1

+

0

1

1 10

0 1 0

S = A’B’Cin


101

A

Cin

B

Adder

Cin

Cout

SB

A

A B Cin S Cout0 0 0 0 00 0 1 1 00 1 0 1 00 1 1 0 11 0 0 1 01 0 1 0 11 1 0 0 11 1 1 1 1

+

0

1

1 10

0 1 0

S = A’BCin’ + A’BCin


102

A

Cin

B

Adder

Cin

Cout

SB

A

A B Cin S Cout0 0 0 0 00 0 1 1 00 1 0 1 00 1 1 0 11 0 0 1 01 0 1 0 11 1 0 0 11 1 1 1 1

+

0

1

1 10

0 1 0

S = A’BCin’ + A’B’Cin + ABCin


103

A

Cin

B

Adder

Cin

Cout

SB

A

A B Cin S Cout0 0 0 0 00 0 1 1 00 1 0 1 00 1 1 0 11 0 0 1 01 0 1 0 11 1 0 0 11 1 1 1 1

+

0

1

1 10

0 1 0

S = A’BCin’ + A’B’Cin + ABCin + AB’Cin’


104

In molte funzioni logiche la procedura di combinazione delle celle può essere estesa per combinare più di due 1-celle in un singolo termine prodotto.

Combinazione di 2i celle possibile se:

• ci sono i variabili che assumono tutte le 2i combinazioni possibili

• Le restanti n-i hanno lo stesso valore in ogni cella

Termine prodotto ha n-i variabili: complementata se 0 in ogni cella, non complementata se appare come 1.

Graficamente: cerchiamo insiemi rettangolari di 2i 1-celle (sono ammessi anche “incollaggi” su bordi opposti)

Per ciascuna variabile:

Se è zero in tutta l’area ricoperta complementata

Se è uno in tutta l’area ricoperta non complementata

Se è zero in una parte e uno in un’altra non appare nel prodotto

105

L’adiacenza è cilindrica

Z’ si estende dal bordo sinistro al bordo destro

F = Z’

112

A

C

B

1

1

0 11

0 0 1

00 01 11 10

0

1

A

C

B

1

1

0 11

0 0 1

00 01 11 10

0

1

F=A,B,C(0,1,4,5,6)

A

C

B

1

1

0 11

0 0 1

00 01 11 10

0

1

A

C

B

1

1

0 11

0 0 1

00 01 11 10

0

1

AC’+B’AC’

114

Esempio di funzione a quattro variabili: rivelatore di numeri primi

F=N3,N2,N1,N0(1,2,3,5,7,11,13)

117

Esempio di funzione a quattro variabili: rivelatore di numeri primi

F=N3,N2,N1,N0(1,2,3,5,7,11,13)

N3

N2

N1

N0

N3N2

N1N000 01 11 10

00

01

11

10

0 4 12 8

1 1 1 5 1 13

1 3

1 2

1 7 1 11

9

10 14

15

6

N3

N2

N1

N0

N3N2

N1N000 01 11 10

00

01

11

10

1 1 1

1

1

1 1

N3’N0

N2N1’N0

N3’N2’N1

N2’N1N0

118

Implicanti primi

Un implicante primo è un insieme cerchiato di 1-celle soddisfacenti la regola di combinazione tale che se cerchiamo di farlo più grande (ricoprendo il doppio delle celle) copre uno o più zeri.

W

X

Y

Z

WX

YZ00 01 11 10

00

01

11

10

0 4 1 12 8

1 1 5 1 13

3

2

1 7 11

9

101 14

1 15

6

F=W,X,Y,Z(5,7,12,13,14,15)

W

X

Y

Z

WX

YZ00 01 11 10

00

01

11

10

1 1

1 1

1

1

Una somma minima è una somma di implicanti primi.

XZ

WX

119

La somma di tutti gli implicanti primi di una funzione logica è detta la somma completa.

La somma completa non è sempre minima però.

W

X

Y

Z

WX

YZ00 01 11 10

00

01

11

10

0 1 4 1 12 8

1 1 1 5 1 13

1 3

2

7 1 11

1 9

101 14

1 15

6

W

X

Y

Z

WX

YZ00 01 11 10

00

01

11

10

1 1

1

XY’F=W,X,Y,Z(1,3,4,5,9,11,12,13,14,15)

1

1

1

1 1

1

1

WX

WZ

X’Z

Y’Z

5 implicanti primi, ma solo tre necessari per ricoprire tutte le 1-celle

120

Una 1-cella distinta è una combinazione di input coperta da un solo implicante primo

Un implicante primo essenziale è uno che copre una o più 1-celle distinte deve essere incluso obbligatoriamente.

Dobbiamo quindi determinare come coprire le 1-celle non coperte da implicanti primi essenziali (se ce ne sono)

W

X

Y

Z

WX

YZ00 01 11 10

00

01

11

10

1 1

1

XY’

1

1

1

1 1

1

1

WX

WZ

X’Z

Y’Z

in questo caso i 3 implicanti primi essenziali ricoprono tutte le 1-celle

W

X

Y

Z

WX

YZ00 01 11 10

00

01

11

10

1 1

1

XY’

1

1

1

1 1

1

1

WX

X’Z

121

W

X

Y

Z

WX

YZ00 01 11 10

00

01

11

10

1 0 1 4 12 8

1 1 1 5 13

1 3

1 2

1 7 11

9

101 14

1 15

6

F=W,X,Y,Z(0,1,2,3,4,5,7,14,15)

WXY

W

X

Y

Z

WX

YZ00 01 11 10

00

01

11

10

1 1

1 1

1

1

1

1

1

W’Y’

W’X’

Qui gli implicanti primi essenziali non ricoprono tutte le 1-celle

Ci sono altri due implicanti primi e dobbiamo scegliere uno dei due

122

WXY

W

X

Y

Z

WX

YZ00 01 11 10

00

01

11

10

1 1

1 1

1

1

1

1

1

W’Y’

W’X’

Qui gli implicanti primi essenziali non ricoprono tutte le 1-celle

usiamo il termine prodotto W’Z perchè ha meno input e quindi costa meno

W

X

Y

Z

WX

YZ00 01 11 10

00

01

11

10

1 1

1 1

1

1

1

1

1

XYZ

W’Z

Esaminiamo gli altri due implicanti primi: dobbiamo scegliere uno dei due

125

Numeri binari

E’ importante essere in grado di rappresentare numeri nei circuiti digitali

Ad esempio, l’output di un convertitore analogico/digitale (ADC) è un numero a n bit, dove n tipicamente si trova nell’intervallo 8-16.

Si utilizzano varie rappresentazioni, ad es.;- interi non segnati- complemento a due per rappresentare numeri negativi

126

X Y = XY’ + X’YX Y C0 0 00 1 11 0 11 1 0

Se X=1 OR Y=1, maNon entrambi, allora C=1

XY

C

X 0 =

X 1 =

X X =

X X’ =

Legge commutativa:X Y = Y X

Legge associativa:(X Y) Z= X ( Y Z) = X Y Z

Legge distributiva:X(Y Z) = XY XZ

X

X’

0

1

OR esclusivo

127

Legge del complemento:(X Y)’ = X Y’ = X’ Y

X Y X’ Y’ XY (XY)’ XY’ X’Y0 0 1 1 0 1 1 10 1 1 0 1 0 0 01 0 0 1 1 0 0 01 1 0 0 0 1 1 1

Dimostrazione algebrica:(X Y)’ = (XY’ + X’Y)’

= (XY’)’(X’Y)’= (X’ + Y)(X + Y’)= X’X + X’Y’ + XY + YY’= 0 + X’Y’ + XY + 0

= X’ Y= X’Y’ + XY= XY + X’Y’ = X Y’

OR esclusivo (cont.)

128

Si dimostrano queste proprietà:(XY)Y = X(XY)X= Y

X Y X1=XY Y1=X1Y X2=X1Y1 0 0 0 0 0 0 1 1 0 1 1 0 1 1 0 1 1 0 1 1

Dim. algebrica: (XY) Y = (XY’ + X’Y)Y’ + (XY’ + X’Y)’Y= XY’Y’ + X’YY’ + ((XY’)’(X’Y)’)Y= XY’ + 0 + ((X’+Y)•(X+Y’))Y= XY’ + X’XY + X’Y’Y +XYY + YY’Y= XY’ + 0 + 0 + XY + 0= X(Y’ + Y)= X•1= X

Permutazione del valore in-place

129

Using In-place Value Permutation in Assembly

Can be used in assembly programming to exchange thevalue of two registers in place:

R1 R1R2R2 R1R2R1 R1R2

The In-place Value Permutation Property of the exclusive-OR:(XY)Y = X(XY)X= Y

If we do back substitution in the second and third operations,we will find out that (assuming R1=A and R2=B initially):R1 (A B)R2 (A B) B = AR1 (A B) A = BThus, if initially R1 = A and R2 = B, then after this sequence of operations, R1 = B and R2 = A.

130

Equivalence Gate(X Y) = XY + X’Y’

X Y C0 0 10 1 01 0 01 1 1

If X=Y then C=1,otherwise C=0

(X Y) = (X Y)’

XY

C

Switching Network

Documents

Transcript of Switching Network