(VHUFL]LRvcg.isti.cnr.it/~tarini/teaching/archi/2016/04E-RetiCombinatorie.pdf · 0dufr 7dulql...

Marco Tarini - Università dell'Insubria A.A. 2016/17

Architettura degli elaboratori - Circuiti combinatori - esercizi 1

Università degli Studi dell’InsubriaDipartimento di Scienze Teoriche e Applicate

Architettura degli elaboratori

Circuiti combinatori: esercizi

Marco TariniDipartimento di Scienze Teoriche e Applicate

Esercizi - Livello logicoArchitettura degli elaboratori - 2 -

Esercizio 1Compilare la tabella di verità del seguente schema circuitaleCostruire un circuito equivalente di costo minimo




Esercizio 1

F = p+p+q = p+qp = XYZq = Y Z = Y/Z + /YZ

p

q

F = p+q = XYZ +Y/Z + /YZSemplificabile?


Esercizio 1

X Y Z F0 0 0 00 0 1 10 1 0 10 1 1 01 0 0 01 0 1 11 1 0 11 1 1 1

p q 00000001

01100110

p

q




Esercizio 1X Y Z F0 0 0 00 0 1 10 1 0 10 1 1 01 0 0 01 0 1 11 1 0 11 1 1 1

00 01 11 1001

XYZ

111

11

0 00

F = XYZ +Y/Z + /YZ

XYZ Y/Z/YZ


Esercizio 1: semplificazioneF = p+q = XYZ +Y/Z + /YZ

F = XY +Y/Z + /YZ =Y (X+/Z) + /YZ F = XZ +Y/Z + /YZ =

Z (X+/Y) + Y/Z

00 01 11 1001

XYZ

111

11

00 01 11 1001

XYZ

111

11




Esercizio 1: semplificazioneF = XYZ +Y/Z + /YZ = [A = A + AB] XYZ + Y/Z + Y/ZX + /YZ =XY (Z+/Z) + Y/Z + /YZ =XY + Y/Z + /YZ = XY + YZ

F = XYZ +Y/Z + /YZ = [A = A + AB] XYZ + Y/Z + /YZ + /YZX =Y/Z + /YZ + XZ (Y+/Y) =Y/Z + /YZ + XZ = YZ + XZ


Esercizio 2Compilare la tabella di verità del seguente schema circuitale




Esercizio 2: soluzionep

r

q X Y p q0 00 11 0

r F

1 1

1110

0111

1010

1111

È la costante 1!


Esercizio 2

1 F






Esercizio 3: soluzione U1

X Y p q0 0

0 10 0

r U1

0 1

1

11

1

Z0

01

11 0

1 11 0

1 1

0

01

1

q

rp s

t

s t0

00

00

10

1

1

11

11

10

0

1

11

11

10

1

0

00

00

01

1

1

11

11

00

0

1

11

1U1 = 1




Esercizio 3: soluzione U2

X Y p q0 0

0 10 0

r U2

0 1

Z0

01

11 0

1 11 0

1 1

0

01

1

q

rp s

ts t

0

00

00

10

1

1

11

11

10

0

1

11

11

10

1

0

00

00

01

1

1

11

11

00

0

w

w0

00

00

00

0

0

00

00

01

1U2 = X/YZ+XYZ=XZ


Esercizio 3: circuito equivalenteU1 = 1U2 = XZNessuna delle due funzioni dipende da Y!

XYZ

1 U1U2




Esercizio 4Scrivere l’espressione booleana associata al seguente schema circuitale

F


Esercizio 4: soluzione

F = /(p+q+Y+r)p = /(X/Y) = /X+Yq = p xor Y = p/Y + /pY = (/X+Y)/Y + X/YY = (/X+Y)/Y = /X/Y = /(X+Y)r = Y xor Z = Y/Z + /YZ

q

r

p

F




Esercizio 4: soluzioneF = /(p+q+Y+r)p = /(X/Y) = /X+Yq = (/X+Y)/Y + X/YY = (/X+Y)/Y = /X/Y = /(X+Y)r = Y/Z + /YZF = /(/X + Y + /X/Y + Y + Y/Z + /YZ) = /(/X+Y+/YZ) = /(/X + Y + Z)Essendo

/X + /X/Y = /X [assorbimento]Y + Y/Z = Y [assorbimento]Y+Y=Y [idempotenza]Y+/YZ = Y+Z


Esercizio 4: semplificazioneF = /(/X+Y+Z) = X/Y/Z [DeMorgan]

XYZ

F




Esercizio 4: semplificazione (1)Con tavola verità (omesso il procedimento)

X Y0 0

0 10 0

F

0 1

0

00

0

Z0

01

11 0

1 11 0

1 1

0

01

1

1

00

0

F = X/Y/Z


Esercizio 4: semplificazione “a occhio” (2)L’uscita è 1 sse gli ingressi della porta nor sono tutti 0.

Quindi, Y = 0Quindi Z =0, in modo che Y xor Z sia 0X deve essere 1, in modo che il nand produca uno 0Il secondo xor ha in ingresso due 0 e produce 0, come richiesto

10 000 0

11

X=1, Y=Z=0 è l’unica combinazione di ingressi che dà un 1 in uscita




Esercizio 5 Scrivere l’espressione booleana associata al seguente schema circuitale


Esercizio 5: soluzioneOsservazioni preliminari

X nand 0 = /(X 0) = /0 = 1

p1

U = 1 and p = p




Esercizio 5: soluzioneBasta studiare il circuito:

U

U = YZ + Z xor YZ + /(YY) + /Y/Z = [YY = Y] = YZ + Z/(YZ) + /ZYZ + /Y + /Y/Z = [Y/ZZ = 0, A+0 = A, /Y+/Y/Z = /Y]= YZ + Z/(YZ) + /Y = [DeMorgan]= YZ + Z(/Y+/Z) + /Y = [distributiva]= YZ + Z/Y + Z/Z + /Y = [Z/Z=0, A+0=A]= YZ + Z/Y + /Y = [distributiva] = Z(Y+/Y) + /Y = Z + /Y


Esercizio 5: verifica

pq

r

s

U

Y Z p q0 00 11 0

r F

1 1

0001

0100

1100

1101

s1000

F = /Y+Z

Nota: una funzione di 2 variabili che vale 0 in un solo caso è esprimibile

con un OR




Esercizio 5: conclusione

YZU


Esercizio 6Data una funzione booleana rappresentata tramite la seguente tabella di verità, ottenere la rappresentazione equivalente come somma di prodotti





F(x,y,z) = /x/y/z + /xyz+ x/y/z + xy/z

/x/y/z

/xyz x/y/z xy/z


Esercizio 6: semplificazione

F(X,Y,Z) = /X/Y/Z + /XYZ+ X/Y/Z + XY/Z =/Y/Z + X/Z + /XYZ

00 01 11 1001

XYZ

111

1




F(X,Y,Z) = /Y/Z + X/Z + /XYZ: realizzazione

X Y Z

F

F(X,Y,Z) = /Y/Z + X/Z + /XYZ


Esercizio 6: semplificazione ulterioreF(X,Y,Z) = /Y/Z + X/Z + /XYZ == /Z (/Y+X) + Z (/XY) = (DeMorgan)= /Z (/Y+X) + Z /(X+/Y)Prima: formula realizzable mediante un circuito che impiega 2 porte a due ingressi e 2 porte a tre ingressiDopo: formula implementabile con 4 porte a due ingressi.

YZ F

X




Esercizio 6: semplificazione ulteriore

YZ F

X

YZ

FX


Esercizio 7Progettare un circuito di controllo per un allarme antincendio. Il sistema riceve in ingresso quattro segnali provenienti da altrettanti sensori di fumo (S1, S2, S3, S4) e genera un segnale di uscita A. Il segnale di allarme A=1 deve essere attivato se almeno due sensori segnalano presenza di fumo (=1).




Esercizio 7: soluzioneF = S1S2 + S1S3 + S1S4 + S2S3 + S2S4 + S3S4

F

S1 S2 S3 S4


Esercizio 8La funzione f(x,y,u,v) è definita come somma dei mintermini (0, 1, 2, 4, 5, 6, 7, 8, 9, 10)Effettuarne la sintesi sia come somma di prodotti sia come prodotto di somme. Con il mintermine n si intende il prodotto logico corrispondente alla combinazione di variabili in ingresso uguale alla codifica binaria di n.Ad es. il mintermine 2 corrisponde all’ingresso 0010, quindi a /x/yu/v




Esercizio 8: Tabella di veritàf(x, y, u, v) somma dei mintermini (0, 1, 2, 4, 5, 6, 7, 8, 9, 10)

# mintermine x y u v f0 0 0 0 0 11 0 0 0 1 12 0 0 1 0 13 0 0 1 1 04 0 1 0 0 15 0 1 0 1 16 0 1 1 0 17 0 1 1 1 18 1 0 0 0 19 1 0 0 1 110 1 0 1 0 111 1 0 1 1 012 1 1 0 0 013 1 1 0 1 014 1 1 1 0 015 1 1 1 1 0


Esercizio 8: Mappe di Karnaugh# mintermine x y u v f

0 0 0 0 0 11 0 0 0 1 12 0 0 1 0 13 0 0 1 1 04 0 1 0 0 15 0 1 0 1 16 0 1 1 0 17 0 1 1 1 18 1 0 0 0 19 1 0 0 1 110 1 0 1 0 111 1 0 1 1 012 1 1 0 0 013 1 1 0 1 014 1 1 1 0 015 1 1 1 1 0

00 01 11 1000

01

xyuv

10

11

1 01 1

1 1 1 1

1 1

0 00 0

0 1

f = (/x+/y) (y + /u + /v)




Esercizio 8: Mappe di Karnaugh# mintermine x y u v f

0 0 0 0 0 11 0 0 0 1 12 0 0 1 0 13 0 0 1 1 04 0 1 0 0 15 0 1 0 1 16 0 1 1 0 17 0 1 1 1 18 1 0 0 0 19 1 0 0 1 110 1 0 1 0 111 1 0 1 1 012 1 1 0 0 013 1 1 0 1 014 1 1 1 0 015 1 1 1 1 0

00 01 11 1000

01

xyuv

10

11

1 01 1

1 1 1 1

1 1

0 00 0

0 1

f = /xy + /y/u + /y/v


Esercizio 8: Sintesi in forma SOP e POS

v

f

yyxuy

y

f

x

vyu




Esercizio 8: verificaVerifichiamo che (/x+/y) (y + /u + /v) sia equivalente a /xy + /y/u + /y/v

(/x+/y) (y + /u + /v) =/xy + /yy + /x/u + /y/u + /x/v + /y/v = [ /yy=0 ]/xy + /x(/u+/v) + /y(/u+/v)

Ponendo z = (/u+/v) la fornula si può riscrivere/xy +/xz + /yz = (essendo /xz = /xzy+/xz/y)/xy + /xzy + /xz/y + /yz = (per assorbimento)/xy + /yz =/xy + /y(/u+/v) =/xy + /y/u + /y/v


Esercizio 9 (1)Si consideri la funzione booleana di 3 variabili F(a,b,c) che vale 1 per le tre combinazioni di ingressi 001, 011, 010, e vale 0 per tutte le altre combinazioni.

Esprimere F in prima forma canonica (somma di prodotti)Disegnare una rete combinatoria che realizza la funzione espressa al punto precedente utilizzando solamente porte AND e OR a due ingressi (oltre alle porte NOT).Calcolare il costo della rete disegnata al punto precedente considerando che ogni porta a due ingressi (AND oppure OR) ha costo pari a quattro, mentre una porta NOT ha costo pari a uno.




Esercizio 9 (2)Calcolare il ritardo della rete considerando i seguenti valori di ritardo:

AND (2 ingressi): ritardo = 10 nsec;OR (2 ingressi): ritardo = 12 nsec;NOT: ritardo = 2 nsec.

Trasformare l’espressione di F determinata in precedenza in modo da minimizzare il costo della sua realizzazione. Se si usa l’algebra di Boole bisogna indicare le singole operazioni svolte e il nome oppure la forma del teorema adottato (ad esempio, “Proprietà Associativa” oppure “(ab)c = a(bc)”)NB: si richiede di minimizzare il costo, anche se questo comporta un maggior ritardo

Calcolare il costo della nuova funzione ottenuta


Esercizio 9 (3)F(a,b,c) = /a/bc + /abc + /ab/cCosto (F) = 1*3+4*8 = 35Ritardo (F) = 2 + 10*2 + 12*2 = 46 ns

a b c a b c

2ns 10ns 10ns 12ns 12ns

Si poteva fare meglio (ad es. Riusando /ac)




Esercizio 9 (4)

Costo (F) = 1 + 4 + 4 = 9Ritardo (F) = max(2,10) + 12 = 22 ns

Espressione trasformata Teorema utilizzatoa b c+ a b c+ a b c X + X = X

ab c+ a b c+ a b c+ a b c XY + XZ = X (Y + Z)a c ( b + b)+ a b ( c + c) X + !X = 1

ac+ ab XY + XZ = X (Y + Z)a(b + c)


Esercizio 9 (5)

F=/ac + /ab = /a(b+c)

00 01 11 1001

abc

11 1




Esercizio 10Progettare un circuito di controllo per un display a sette segmenti. Il circuito ha un solo ingresso (X) e deve far apparire sul display i caratteri “L” e “H” in corrispondenza, rispettivamente, dell’ingresso X=0 e X=1)

X


Esercizio 10: soluzioneX=0 X=1

ab

cd

ef g

ab

cd

ef g

f=e=1 [sempre accesi]a=0 [sempre spento]b=c=g=X [accesi quando X=1, spenti quando X=0]d=/X [acceso quando X=0, spento quando X=1]




Esercizio 11Studiare il circuito.



pq

r

A B C D0 0 0 00 1 1 01 0 1 01 1 0 1

p q1 11 11 00 1

r1011

A B

C D

È il semisommatore!




Esercizio 12Individuare gli errori presenti nel seguente schema circuitale



?




Esercizio 13Compilare la tabella di verità del seguente circuito



X Y0 00 11 01 1

U1 U20 01 11 01 1

U2=YInfatti, U2 = Y(X+Y) = Y+XY =Y





X Y0 00 11 01 1

U1 U20 01 11 01 1

X Y

U1 U2


Esercizio 14Compilare la tabella di verità del seguente circuito




Esercizio 14: soluzioneX Y0 0

0 10 0

U

0 1

1

11

1

Z0

01

11 0

1 11 0

1 1

0

01

1

1

10

1

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

/Z






Esercizio 15: soluzione 1

U = X Y

X Y0 0

0 10 0

p

0 1

0

10

1

Z0

01

11 0

1 11 0

1 1

0

01

1

1

01

0

pq

U0

10

11

01

0

q0

11

01

00

1X Y U



U = Z/q + /Zqq = Z/W + /ZWU = Z/q + /Z (Z/W + /ZW) /q = /(Z/W) /(/ZW) = (/Z+W) (Z+/W) = /ZZ + WZ +/W/Z + W/W = WZ +/W/ZU = Z (WZ +/W/Z) + /Z (Z/W + /ZW) = ZWZ + Z/W/Z + /ZZ/W + /Z/ZW =

= ZW+/ZW = (Z+/Z)W = WU = W !

qW W

0

10

1

Z0

01

1

U0

10

1

q0

11

0





U = WW

WU = W = X Y


Esercizio 16Progettare un circuito che visualizzi il valore di un ingresso N a 3 bit tramite un display a 7 segmenti

L’ingresso rappresenta un numero naturale compreso tra 0 e 7.

RCN 3




Esercizio 16: tabella delle veritàX Y0 0

0 10 0

a

0 1

1

10

1

Z0

01

11 0

1 11 0

1 1

0

01

1

0

01

1

c1

01

11

11

1

b1

11

11

00

1

d1

10

10

11

0

f1

00

01

11

0

e1

10

00

10

0

g0

10

11

11

0

N0

21

34

65

7


Esercizio 16: tabella delle veritàX Y0 0

0 10 0

a

0 1

1

10

1

Z0

01

11 0

1 11 0

1 1

0

01

1

0

01

1

c1

01

11

11

1

b1

11

11

00

1

d1

10

10

11

0

f1

00

01

11

0

e1

10

00

10

0

g0

10

11

11

0

a = /X/Z + /XY + XZb = /X + /Y/Z +YZc = X + /Y +Z = /(/XY/Z)d = /XY+ /X/Z + Y/Z + X/YZe = Y/Z + /X/Zf = /Y/Z + X/Y + X/Zg = /XY + X/Y + X/Z




Esercizio 0Realizzare NOT, AND e OR usando esclusivamente porte NAND.

XY Z

XY Z=/(XY)Q=XY


Realizzazione della funzione NOTObiettivo: realizzare /X

A=?B=? /XQ=AB=?

Affinché l’uscita sia /X occorre che Q sia = X




Realizzazione della funzione NOTObiettivo: realizzare /X

A=?B=? /XQ=AB=X

Quali valori devono avere A e B affinché AB = X?

Se A=X e B=X, allora AB = X

Se A=X e B=1, allora AB = X1 = X

X /X

X /X1


Realizzazione della funzione ANDBasta negare l’uscita della porta NAND. La negazione la sappiamo fare, dunque:

XY /(XY)/(XY)




Realizzazione della funzione ORAbbiamo a disposizione NAND, AND e NOT.Il modo più semplice per realizzare l’OR è usare il teorema di De Morgan:

A+B = /(/A/B)

A

B/(/A/B) = A+B

/A

/B


ConclusioneUsando esclusivamente porte NAND si può realizzare qualunque funzione logica (cioè qualunque circuito combinatorio).




Esercizio 17Si desidera un circuito combinatorio che realizza la funzione definita come segue.

L’ingresso è un numero N codificato in complemento a due su 4 bit.L’uscita è su un solo bit.L’uscita vale 1 per i seguenti valori di N: -8, -7, -6, -5, 0, 3, 4, 6. Per gli altri valori possibili di N, l’uscita vale 0.

Realizzare il circuito, utilizzando esclusivamente porte nand.


Esercizio 17L’uscita vale 1 per i seguenti valori di N: -8, -7, -6, -5, 0, 3, 4, 6. Per gli altri valori possibili di N, l’uscita vale 0.Per comodità chiamiamo a, b, c, d i 4 bit X, essendo a il più significativo.

a b c d Z0 0 0 0 10 0 0 1 00 0 1 0 00 0 1 1 10 1 0 0 10 1 0 1 00 1 1 0 10 1 1 1 01 0 0 0 11 0 0 1 11 0 1 0 11 0 1 1 11 1 0 0 01 1 0 1 01 1 1 0 01 1 1 1 0

N01234567-8-7-6-5-4-3-2-1




Esercizio 17: Mappa di Karnaugh00 01 11 10

00

01

abcd

10

11

1 10 0

1 00 1

1 1

0 000

1 1

f = a/b + /a/c/d +/ab/d + /bcd =/b (a+cd) + /a/d (/c+b)

a b c d Z0 0 0 0 10 0 0 1 00 0 1 0 00 0 1 1 10 1 0 0 10 1 0 1 00 1 1 0 10 1 1 1 01 0 0 0 11 0 0 1 11 0 1 0 11 0 1 1 11 1 0 0 01 1 0 1 01 1 1 0 01 1 1 1 0

N01234567-8-7-6-5-4-3-2-1


Esercizio 17f = a/b + /a/c/d +/ab/d + /bcd == /b (a+cd) + /a/d (/c+b) = = /b /(/a /(cd)) + /a/d /(c/b) = = /(/(/b /(/a /(cd))) /(/a/d /(c/b))) == nand(nand(/b, nand(/a, nand(c,d))),

nand(/nand(/a, /d), nand(c, /b)))




Esercizio 17f = nand(nand(/b, nand(/a, nand(c,d))),

nand(/nand(/a, /d), nand(c, /b))) a b c d

Z

(VHUFL]LRvcg.isti.cnr.it/~tarini/teaching/archi/2016/04E-RetiCombinatorie.pdf · 0dufr 7dulql...

Documents

Transcript of (VHUFL]LRvcg.isti.cnr.it/~tarini/teaching/archi/2016/04E-RetiCombinatorie.pdf · 0dufr 7dulql...