FONDAMENTI DI INFORMATICA B FONDAMENTI DI INFORMATICA B Esercitazione n.1

1

UNIVERSITA’ DEGLI STUDI DI PARMA Dipartimento di Ingegneria dell’Informazione

Fondamenti di Informatica B Esercitazione 1

1 / 23 Marcello CARLETTI

C

E

FONDAMENTI DI INFORMATICA B FONDAMENTI DI INFORMATICA B Esercitazione n.1

Esercizi di sintesi mediante mappe

UNIVERSITA’ DEGLI STUDI DI PARMA Dipartimento di Ingegneria dell’Informazione

Fondamenti di Informatica B Esercitazione 1

2 / 23 Marcello CARLETTI

C

E

RIEPILOGO TEORICO RIEPILOGO TEORICO - - I I

2 categorie di circuiti logici:

• CIRCUITI COMBINATORI:

– la relazione ingresso/uscita non dipende dal tempo – privi di stato interno

• CIRCUITI SEQUENZIALI:

– l’uscita dipende anche dalla storia passata del circuito – presenza di stato interno (memoria)

⇒ Vedremo reti combinatorie ad 1 uscita:

reti a più uscite possono essere scomposte nel parallelo di più reti ad 1 uscita

UNIVERSITA’ DEGLI STUDI DI PARMA Dipartimento di Ingegneria dell’Informazione

Fondamenti di Informatica B Esercitazione 1

3 / 23 Marcello CARLETTI

C

E

RIEPILOGO TEORICO

RIEPILOGO TEORICO - - II II

• Obiettivi della minimizzazione logica:

– minimizzare il numero di porte

– a pari numero di porte, minimizz. il numero di ingressi

⇒Minori costi

• Non più forme canoniche in senso stretto, minterm e maxterm,

ma SdP e PdS minime, implicanti (implicati) principali ed essenziali

• Si devono trovare tutti gli implicanti (implicati) principali essenziali

+

un insieme minimo di implicanti (implicati) principali

UNIVERSITA’ DEGLI STUDI DI PARMA Dipartimento di Ingegneria dell’Informazione

Fondamenti di Informatica B Esercitazione 1

4 / 23 Marcello CARLETTI

C

E

RIEPILOGO TEORICO

RIEPILOGO TEORICO - - III III

• Per funzioni fino a 4, 5 o 6 variabili esistono tecniche di minimizzazione manuali che si appoggiano alle mappe di Karnaugh:

non sono riempite per avere i numeri in sequenza, ma per sfruttare le adiacenze tra le possibili configurazioni degli ingressi

0 1 1 1 1 0 0 0

0 1 1 1 1 0 a bc d

0 0

0 1 3 2

4 5 7 6

1 2 1 3 1 5 1 4 8 9 1 1 1 0

collocazione dei numeri a 4 bit (da 0 a 15) all’interno di una mappa di K a r n a u g h

UNIVERSITA’ DEGLI STUDI DI PARMA Dipartimento di Ingegneria dell’Informazione

Fondamenti di Informatica B Esercitazione 1

5 / 23 Marcello CARLETTI

COMPUTER ENGINEERING

E S E R C I Z I O n . 1 E S E R C I Z I O n . 1

( a , b , c , d ) ⁼ ∑

( 1 , 3 , 7 , 8 , 9 , 12 , 13 , 15 )

f

0 1 1 1 1 0 0 0

0 1 1 1 1 0 a bc d

0 0

0 1 1 0

0 0 1 0

1 1 1 0

1 1 0 0

• Minimizzare la funzione sia come somme di prodotti che come prodotti di somme

UNIVERSITA’ DEGLI STUDI DI PARMA Dipartimento di Ingegneria dell’Informazione

Fondamenti di Informatica B Esercitazione 1

6 / 23 Marcello CARLETTI

COMPUTER ENGINEERING

S O L U Z I O N E E S E R C I Z I O n . 1 S O L U Z I O N E E S E R C I Z I O n . 1 - - I I

e, tra questi, identificare quelli essenziali:

gli implicanti principali essenziali d e v o n o comparire nella forma minima della funzione

0 1 1 1 1 0 0 0

0 1 1 1 1 0 a bc d

0 0

0 1 1 0

0 0 1 0

1 1 1 0

1 1 0 0

2

UNIVERSITA’ DEGLI STUDI DI PARMA Dipartimento di Ingegneria dell’Informazione

Fondamenti di Informatica B Esercitazione 1

7 / 23 Marcello CARLETTI

COMPUTER ENGINEERING

S O L U Z I O N E E S E R C I Z I O n . 1 S O L U Z I O N E E S E R C I Z I O n . 1 - - II II

implicanti primi tali che:

Questa funzione presenta 2 coperture irridondanti:

0 1 1 1 1 0 0 0

0 1 1 1 1 0 a bc d

0 0

0 1 1 0

0 0 1 0

1 1 1 0

1 1 0 0

{ p p

}

R =

, Κ ,

R K p p p f ma R p p p

f =

+ Κ +

^,

∈ ^, ≠

+ Κ +

^,

∈ ⊂

0 1 1 1 1 0 0 0

0 1 1 1 1 0 a bc d

0 0

0 1 1 0

0 0 1 0

1 1 1 0

1 1 0 0

ottima perché contiene il minor numero di prodotti (quindi, di porte)

UNIVERSITA’ DEGLI STUDI DI PARMA Dipartimento di Ingegneria dell’Informazione

Fondamenti di Informatica B Esercitazione 1

8 / 23 Marcello CARLETTI

COMPUTER ENGINEERING

S O L U Z I O N E E S E R C I Z I O n . 1 S O L U Z I O N E E S E R C I Z I O n . 1 - - III III

4. Rappresentare l’e s p r. minima con una RLC a 2 livelli:

– con AND e OR

d c b d b a c a

f = ⋅ + ⋅ ⋅ + ⋅ ⋅

a c d

f b

UNIVERSITA’ DEGLI STUDI DI PARMA Dipartimento di Ingegneria dell’Informazione

Fondamenti di Informatica B Esercitazione 1

9 / 23 Marcello CARLETTI

COMPUTER ENGINEERING

S O L U Z I O N E E S E R C I Z I O n . 1 S O L U Z I O N E E S E R C I Z I O n . 1 - - I V I V

– oppure, grazie ad una delle leggi di De M o r g a n ,

c o n N A N D a c d

f b

UNIVERSITA’ DEGLI STUDI DI PARMA Dipartimento di Ingegneria dell’Informazione

Fondamenti di Informatica B Esercitazione 1

10 / 23 Marcello CARLETTI

COMPUTER ENGINEERING

S O L U Z I O N E E S E R C I Z I O n . 1 S O L U Z I O N E E S E R C I Z I O n . 1 - - V V

0 1 1 1 1 0 0 0

0 1 1 1 1 0 a bc d

0 0

0 1 1 0

0 0 1 0

1 1 1 0

1 1 0 0

( ^{a d} ) ( ^{c d} ) ( ^{a b c} ) ( ^{a b c} )

f = + ⋅ + ⋅ + + ⋅ + +

UNIVERSITA’ DEGLI STUDI DI PARMA Dipartimento di Ingegneria dell’Informazione

Fondamenti di Informatica B Esercitazione 1

11 / 23 Marcello CARLETTI

COMPUTER ENGINEERING

S O L U Z I O N E E S E R C I Z I O n . 1 S O L U Z I O N E E S E R C I Z I O n . 1 - - V I V I

– c o n O R e A N D a c d

f b

UNIVERSITA’ DEGLI STUDI DI PARMA Dipartimento di Ingegneria dell’Informazione

Fondamenti di Informatica B Esercitazione 1

12 / 23 Marcello CARLETTI

COMPUTER ENGINEERING

S O L U Z I O N E E S E R C I Z I O n . 1 S O L U Z I O N E E S E R C I Z I O n . 1 - - V I I V I I

– oppure, grazie all’altra legge di De M o r g a n ,

c o n N O R a c d

f b

3

UNIVERSITA’ DEGLI STUDI DI PARMA Dipartimento di Ingegneria dell’Informazione

Fondamenti di Informatica B Esercitazione 1

13 / 23 Marcello CARLETTI

COMPUTER ENGINEERING

R I E P I L O G O D E L P R O C E D I M E N T O R I E P I L O G O D E L P R O C E D I M E N T O

(implicati) principali, la cui somma (prodotto) copra la funzione ed il cui costo complessivo sia minimo o meglio

1. Trovare tutti gli implicanti (implicati) principali essenziali

2. Scegliere un insieme irridondante di ulteriori implicanti (implicati) principali, la cui somma (prodotto) copra la funzione ed il cui costo sia minimo 3. Formalizzare l’espressione minima

4. Rappresentare l’e s p r. minima con una RLC a 2 livelli

UNIVERSITA’ DEGLI STUDI DI PARMA Dipartimento di Ingegneria dell’Informazione

Fondamenti di Informatica B Esercitazione 1

14 / 23 Marcello CARLETTI

COMPUTER ENGINEERING

C A S I C R I T I C I C A S I C R I T I C I

0 1 1 1 1 0 0 0

0 1 1 1 1 0 a bc d

0 0

1 0 0 1

1 0 0 1

1 0 0 1

1 0 0 1

0 1 1 1 1 0 0 0

0 1 1 1 1 0 a bc d

0 0

1 0 0 1

0 1 1 0

0 1 1 0

1 0 0 1

UNIVERSITA’ DEGLI STUDI DI PARMA Dipartimento di Ingegneria dell’Informazione

Fondamenti di Informatica B Esercitazione 1

15 / 23 Marcello CARLETTI

COMPUTER ENGINEERING

E S E R C I Z I O n . 2 a E S E R C I Z I O n . 2 a

( x

, x

, x

, x

)

f

• Minimizzare la funzione come somme di prodotti, considerando le condizioni di indifferenza come 0

0 1 1 1 1 0 0 0

0 1 1 1 1 0 x3x

2 0 0

1 - 1 -

0 0 1 1

0 - 0 0

0 1 1 0

x₁x₀

UNIVERSITA’ DEGLI STUDI DI PARMA Dipartimento di Ingegneria dell’Informazione

Fondamenti di Informatica B Esercitazione 1

16 / 23 Marcello CARLETTI

COMPUTER ENGINEERING

S O L U Z I O N E E S E R C I Z I O n . 2 a S O L U Z I O N E E S E R C I Z I O n . 2 a

0 1 1 1 1 0 0 0

0 1 1 1 1 0 x₃x₂ 0 0

1 - 1 -

0 0 1 1

0 - 0 0

0 1 1 0

x₁x₀

0 1 3 0 2 3 1 2 3 0 1 2

3

x x x x x x x x x x x x

x

f = ⋅ ⋅ ⋅ + ⋅ ⋅ + ⋅ ⋅ + ⋅ ⋅

Costo del circuito:

• # porte = 5

• # letterali = 17

UNIVERSITA’ DEGLI STUDI DI PARMA Dipartimento di Ingegneria dell’Informazione

Fondamenti di Informatica B Esercitazione 1

17 / 23 Marcello CARLETTI

COMPUTER ENGINEERING

E S E R C I Z I O n . 2 b E S E R C I Z I O n . 2 b

( x

, x

, x

, x

)

f

• Minimizzare la funzione come somme di prodotti, sfruttando le condizioni di indifferenza in modo adeguato

0 1 1 1 1 0 0 0

0 1 1 1 1 0 x₃x₂ 0 0

1 - 1 -

0 0 1 1

0 - 0 0

0 1 1 0

x₁x₀

UNIVERSITA’ DEGLI STUDI DI PARMA Dipartimento di Ingegneria dell’Informazione

Fondamenti di Informatica B Esercitazione 1

18 / 23 Marcello CARLETTI

COMPUTER ENGINEERING

S O L U Z I O N E E S E R C I Z I O n . 2 b S O L U Z I O N E E S E R C I Z I O n . 2 b

0 2 1 3 2

3

x x x x x

x

f = ⋅ + ⋅ + ⋅

Costo del circuito:

• # porte = 4

• # letterali = 9

0 1 1 1 1 0 0 0

0 1 1 1 1 0 x₃x₂ 0 0

1 - 1 -

0 0 1 1

0 - 0 0

0 1 1 0

x₁x₀ Differenze nel procedimento:

• Attribuire un 1 (0) potenziale a tutte le indifferenze

• Trovare tutti gli implicanti (implicati) principali che non coprano solo indifferenze

• Coprire in modo ottimo la funzione originaria

4

UNIVERSITA’ DEGLI STUDI DI PARMA Dipartimento di Ingegneria dell’Informazione

Fondamenti di Informatica B Esercitazione 1

19 / 23 Marcello CARLETTI

COMPUTER ENGINEERING

E S E R C I Z I O n . 2 c E S E R C I Z I O n . 2 c

( x

, x

, x

, x

, x

)

f

• Minimizzare la funzione di 5 variabili come somme di prodotti, sfruttando le condizioni di indifferenza

0 1 1 1 1 0 0 0

0 1 1 1 1 0 x₃x₂ 0 0

- 1 1 1

0 - 0 -

0 0 1 1

- 1 - 0

x₁x₀

x₄= 1 0 1 1 1 1 0

0 0 0 1 1 1 1 0 x₃x₂ 0 0

1 - 1 -

0 0 1 1

0 - 0 0

0 1 1 0

x₁x₀

x₄= 0

UNIVERSITA’ DEGLI STUDI DI PARMA Dipartimento di Ingegneria dell’Informazione

Fondamenti di Informatica B Esercitazione 1

20 / 23 Marcello CARLETTI

COMPUTER ENGINEERING

S O L U Z I O N E E S E R C I Z I O n . 2 c S O L U Z I O N E E S E R C I Z I O n . 2 c

1 2 3 4 1 3 4 0 2 2

3

x x x x x x x x x x

x

f = ⋅ + ⋅ + ⋅ ⋅ + ⋅ ⋅ ⋅

Costo del circuito:

• # porte = 5

• # letterali = 15 0 1 1 1 1 0 0 0

0 1 1 1 1 0 x₃x₂ 0 0

1 - 1 -

0 0 1 1

0 - 0 0

0 1 1 0

x₁x₀

xx₄₄= 0= 0

0 1 1 1 1 0 0 0

0 1 1 1 1 0 x₃x₂ 0 0

- 1 1 1

0 - 0 -

0 0 1 1

- 1 - 0

x₁x₀

xx₄₄= 1= 1

UNIVERSITA’ DEGLI STUDI DI PARMA Dipartimento di Ingegneria dell’Informazione

Fondamenti di Informatica B Esercitazione 1

21 / 23 Marcello CARLETTI

COMPUTER ENGINEERING

E S E R C I Z I O n . 3 E S E R C I Z I O n . 3

Si abbia un numero binario di 5 bit, A, B, C, D, E, essendo A il più significativo ed E il meno significativo.

Si determini:

1. la funzione booleana che valga 1 solo quando il numero in questione è primo, tenendo presente che lo zero non è un numero primo;

2. l’espressione minima della funzione booleana come somma di prodotti e come prodotto di somme.

UNIVERSITA’ DEGLI STUDI DI PARMA Dipartimento di Ingegneria dell’Informazione

Fondamenti di Informatica B Esercitazione 1

22 / 23 Marcello CARLETTI

COMPUTER ENGINEERING

S O L U Z I O N E E S E R C I Z I O n . 3 S O L U Z I O N E E S E R C I Z I O n . 3 - - I I

Costo del circuito:

• # porte = 7

• # letterali = 28

x x x x x x x x x x

24 23 22 21 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0

x x

31 30 29 28 27 26 25

E C B A E D C A E D C A D C B A E D B E C B

f = ⋅ ⋅ + ⋅ ⋅ + ⋅ ⋅ ⋅ + ⋅ ⋅ ⋅ + ⋅ ⋅ ⋅ + ⋅ ⋅ ⋅

0 1 1 1 1 0 0 0

0 1 1 1 1 0

B C 0 0

0 1 1 0

0 0 1 0

0 1 1 0

0 0 0 0

D E

A = 1 0 1 1 1 1 0

0 0 0 1 1 1 1 0

B C 0 0

0 1 1 1

0 1 1 0

0 1 0 0

0 0 1 0

D E

A = 0

UNIVERSITA’ DEGLI STUDI DI PARMA Dipartimento di Ingegneria dell’Informazione

Fondamenti di Informatica B Esercitazione 1

23 / 23 Marcello CARLETTI

COMPUTER ENGINEERING

S O L U Z I O N E E S E R C I Z I O n . 3 S O L U Z I O N E E S E R C I Z I O n . 3 - - II II

Costo del circuito:

• # porte = 9

• # letterali = 30 0 1 1 1 1 0 0 0

0 1 1 1 1 0

B C 0 0

0 1 1 1

0 1 1 0

0 1 0 0

0 0 1 0

D E

A = 0

0 1 1 1 1 0 0 0

0 1 1 1 1 0

B C 0 0

0 1 1 0

0 0 1 0

0 1 1 0

0 0 0 0

D E

A = 1

( ^{D E} ) ( ) ^{C E} ( ) ( ^{B E B C D} ) ( ^{A B C D} ) ( ) ( ^{A E A B C} ) ( ^{A B C D} )

f = + ⋅ + ⋅ + ⋅ + + ⋅ + + + ⋅ + ⋅ + + ⋅ + + +