Che materia stai cercando?

Anteprima

ESTRATTO DOCUMENTO

Esercizi risolti e proposti di Reti Logi http://www.appunti.net/

Es.4. Convertire il numero 10810 in binario.

Metodo delle divisioni successive: si divide progressivamente per 2 e si

prende il resto.

/2 %2

108

54 0 LSB

27 0

13 1

6 1

3 0

1 1

0 1 MSB

10810 = 11011002

Metodo empirico.

26=64 27=128

< 108 <

25=32 26=64

< 108-64=44 <

23=8 24=16

< 44-32=12 <

22=12-8 26 25 23 22

10810 = + + + = 11011002

1.2 Somme e sottrazioni tra numeri binari

Es.5. Eseguire la somma tra i numeri binari 10011 e 101.

(carry) 0 1 1 1

(1910) 1 0 0 1 1 +

( 510) 0 0 1 0 1 =

---------

(2410) 1 1 0 0 0

N.B. carry = riporto

Es.6. Eseguire la somma tra i numeri binari 10111110 e 10001101.

(carry) 1 0 1 1 1 1 0 0

(23810) 1 0 1 1 1 1 1 0 +

(14110) 1 0 0 0 1 1 0 1 =

-----------------

(37910) 1 0 1 0 0 1 0 1 1 Pag. 2

© 2000 G. Cabodi AP00035

Esercizi risolti e proposti di Reti Logi http://www.appunti.net/

Es.7. Rappresentare in base 2 i numeri decimali 3 e 6, codificandoli su 4 bit. Effettuarne la somma e

rappresentare il risultato su 4 bit.

(carry) 1 1 0

(310) 0 0 1 1 +

(610) 0 1 1 0 =

--------

(910) 1 0 0 1

Es.8. Rappresentare in base 2 i numeri decimali 5 e 12, codificandoli su 4 bit. Effettuarne la somma

e rappresentare il risultato su 4 bit.

(carry) 1 1 0 0

( 510) 0 1 0 1 +

(1210) 1 1 0 0 =

--------

(1710) ? 0 0 0 1

Risultato non rappresentabile su 4 bit: OVERFLOW = carry out dal MSB (Most

Significant Bit)

Es.9. Eseguire la differenza tra i numeri binari 10100110 e 11101.

(borrow) 0 0 1 1 0 0 1

(16610) 1 0 1 0 0 1 1 0 -

( 2910) 0 0 0 1 1 1 0 1 =

----------------

(13710) 1 0 0 0 1 0 0 1

N.B. borrow = prestito

Es.10. Rappresentare in base 2 i numeri esadecimali 15 e A2, codificandoli su 8 bit. Effettuarne la

differenza e rappresentare il risultato su 8 bit.

(borrow) 1 1 1 0 0 0 1 0

(1516) 0 0 0 1 0 1 0 1 -

(A216) 1 0 1 0 0 0 1 0 =

----------------

(-8D10) ? 0 1 1 1 0 0 1 1

Risultato negativo non rappresentabile come numero binario senza segno:

OVERFLOW = borrow dal MSB (Most Significant Bit) = minuendo > sottraendo. Pag. 3

© 2000 G. Cabodi AP00035

Esercizi risolti e proposti di Reti Logi http://www.appunti.net/

1.3 Rappresentazioni per numeri interi con segno

1.3.1 Codifica binaria modulo e segno.

Un bit per il segno (0: numero positivo, 1: numero negativo), i rimanenti per il modulo.

Es.11. Rappresentare in modulo e segno su 8 bit i numeri +3710, -1008, -3B16.

+3710 -> 00100101

-1008 -> 11000000

-3B16 -> 10111011

bit di segno

Es.12. Convertire in decimale i seguenti numeri in codice modulo e segno su 4 bit.

0011 -> +3

1010 -> -2

1111 -> -7

Es.13. Effettuare le seguenti somme algebriche tra numeri in codice modulo e segno.

0010 + 1011 + 1101 + 1101 +

0100 = 1110 = 0010 = 0111 =

---- ---- ---- ----

Regola: la somma algebrica tra due numeri codificati in modulo e segno si effettua come segue

• se gli addendi sono concordi la somma è concorde con essi ed ha come modulo la somma dei

loro moduli. Si ha overflow nel caso di carry-in sul bit di segno (carry-out dal penultimo bit).

• se gli addendi sono discordi la somma è concorde con l'addendo di modulo maggiore ed ha

come modulo la differenza tra il modulo maggiore ed il minore. In pratica si sottrae all'addendo

di modulo maggiore l'opposto dell'addendo con modulo minore. Non è possibile avere overflow.

000 110

0010 + 1011 +

0100 = 1110 =

---- ----

0110 1001

Overflow

1101 + 1 101 -

0010 = 1 010 =

---- - ---

1 011

1101 + 0 111 -

0111 = 0 101 =

---- - ---

0 010 Pag. 4

© 2000 G. Cabodi AP00035

Esercizi risolti e proposti di Reti Logi http://www.appunti.net/

1.3.2 Codifica in complemento a 2

I numeri positivi hanno rappresentazione coincidente con quella in modulo e segno (MSB a 0, nei

restanti bit il modulo). I numeri negativi sono rappresentati mediante l'operazione di

complementazione alla base del loro modulo (se n sono i bit a disposizione, il numero -x ha la

2n-x

stessa rappresentazione di in binario puro).

Si noti che i numeri positivi hanno il MSB a 0, i negativi a 1.

L'operazione di complementazione a 2, che permette di passare, nella notazione c-a-2, da un numero

al suo opposto, si può effettuare in uno dei seguenti modi.

• Dato un numero in codice c-a-2, complementarlo a 1 (convertire gli 0 in 1 e gli 1 in 0) e

sommare 1.

• Dato un numero in codice c-a-2, lasciare invariati i bit da destra (LSB) verso sinistra sino al

primo 1 (compreso). Complementare a 1 tutti i restanti bit.

Es.14. Rappresentare in c-a-2 su 8 bit i seguenti numeri decimali: 20, -6, -81

20 -> 00010100

-6 -> (+6 -> 00000110) -> 11111010

-81 -> (+81 -> 01010001) -> 10101111

Es.15. Effettuare le seguenti somme algebriche tra numeri nella codifica c-a-2 su 4 bit.

Regola: la somma tra numeri nella notazione c-a-2 si effettua come la somma tra numeri binari puri

(compresi i MSB che indicano il segno). Si può avere overflow (risultato scorretto) se, sommando

due addendi concordi, si ottiene una somma discorde con essi: tale situazione si presenta nel caso di

carry-in e carri-out diversi tra loro sul MSB.

(carry) 0000

(+3) 0011 +

(+4) 0100 =

----

(+7) 0111 risultato corretto

(carry) 1100

(+6) 0110 +

(-3) 1101 =

----

(+3) 0011 risultato corretto

(carry) 1110

(-2) 1110 +

(-6) 1010 =

----

(-8) 1000 risultato corretto

(carry) 1000

(-3) 1101 +

(-6) 1010 =

----

(-9 ?) 0011 risultato scorretto: overflow Pag. 5

© 2000 G. Cabodi AP00035

Esercizi risolti e proposti di Reti Logi http://www.appunti.net/

1.4 La codifica BCD (Binary Coded Decimal)

Operazioni nella base decimale, codifica binaria per le singole cifre (0..9).

Es.16. Rappresentare in codice BCD i numeri decimali 45 e 37.

45 -> 0100 0101

37 -> 0011 0111

Somma tra due numeri in BCD. Le cifre decimali corrispondenti vengono sommate come numeri

binari. Nel caso di risultati > 9 occorre sottrarre 10 e propagare un riporto di 1. In pratica, questo si

ottiene sommando 6 (0110).

Es.17. Effettuare le seguenti somme tra numeri BCD. 1

(45) 0100 0101 + (56) 0101 0110 + (29) 0010 1001 +

(22) 0010 0010 = (37) 0011 0111 = (18) 0001 1000 =

--------- --------- ----------

(67) 0110 0111 1101(>9) + 10001(>9) +

0110 = 0110 =

--------- ----------

(93) 1001 0011 (47) 0100 0111 Pag. 6

© 2000 G. Cabodi AP00035

Esercizi risolti e proposti di Reti Logi http://www.appunti.net/

1.5 Moltiplicazione e divisione tra numeri binari K

Il prodotto tra un numero binario senza segno e una potenza di due si effettua mediante una

X Y=2

operazione di shift a sinistra di posizioni:

K K

X*2 = X<<K

La divisione si può considerare come prodotto per una potenza di esponente negativo, cioè uno shift

a destra: K -K

X/2 = X*2 = X<<(-K) = X>>K

Il prodotto tra due numeri binari (di bit) e (di bit) ha come risultato un numero P (di non più

X n Y m

di bit significativi). La moltiplicazione può essere effettuato in vari modi, alcuni dei quali

n+m

saranno illustrati nel seguito. I metodi proposti possono essere adottati per prodotto tra numeri senza

segno o numeri in modulo e segno (ricordando che in tal caso si effettua il prodotto dei moduli, ed il

segno del risultato è positivo nel caso di fattori concordi, negativo nel caso di fattori discordi). Il

prodotto tra numeri in C-a-2 può essere ricondotto al prodotto tra numeri in modulo e segno,

convertendo i fattori a tale notazione.

1.5.1 Moltiplicazione mediante somme ripetute

Il prodotto si può effettuare sommando a se stesso volte.

X*Y X Y

Es. (X=13) 1101 * 1101 +

(Y=3) 11 = -> 1101 +

---- 1101 =

------

(X*Y=39) 100111

1.5.2 Moltiplicazione mediante shift e somma

Il prodotto si può effettuare in modo simile al prodotto effettuato tra numeri in base 10: il

X*Y

moltiplicando viene moltiplicato per un bit del moltiplicatore alla volta, ed i prodotti parziali

X Y

vengono successivamente sommati.

Es. (X=11) 1011 *

(Y=13) 1101 =

-------

1011

0000

1011

1011

-------

(X*Y=143) 1000111

Nell’esempio si sono calcolati dapprima tutti i prodotti parziali, poi si è effettuata la somma. Una

ulteriore realizzazione del prodotto prevede di alternare prodotti e somme parziali. Ad ogni passo si

calcola un prodotto parziale, lo si addiziona alla somma dei prodotti parziali (P, inizializzata al

valore 0) e si effettua uno shift a destra di quest’ultima. Pag. 7

© 2000 G. Cabodi AP00035

Esercizi risolti e proposti di Reti Logi http://www.appunti.net/

Es. (X=11) 1011 *

(Y=13) 1101 =

---------

(P=0) 0000 +

(X Y) 1011

0 ---------

01011 (shift)

---------

01011 +

(X Y) 0000

1 ---------

001011 (shift)

---------

001011 +

(X Y) 1011

2 ---------

0110111 (shift)

---------

0110111 +

(X Y) 1011

3 ----------

10001111 (shift)

----------

(X*Y=143) 10001111

1.6 Rappresentazioni per numeri reali

Un numero reale può essere rappresentato mediante n cifre binarie (bit) in notazione a virgola fissa

(fixed point) oppure a virgola mobile (floating point).

Nel caso di rappresentazione fixed point si riservano i bit alla parte intera e gli f rimanenti bit (i+f =

n) alla parte frazionaria, secondo lo schema seguente:

. Xn-1*2i-1+...+Xn-i*20+ Xf-1*2-1+...+X0*2-f

Xf-1 ...X0 =

Xn-1 ...Xn-i

Negli esempi seguenti si rappresentano numeri reali senza segno su 8 bit (4 per la parte intera e 4

per la frazionaria) 23+20+2-2+2-3+2-4

1001.0111 = = 9.4375

21+20+2-3

0011.0010 = = 3.125

2-1

0000.1000 = = 0.5

Per i numeri con segno si può riservare 1 bit al segno, adottando notazioni in modulo e segno

oppure in complemento a 2 nelle quali, in pratica, il numero di bit riservati alla parte frazionaria (f)

2-f

introduce un coefficiente moltiplicativo rispetto alla rappresentazione degli interi. La

rappresentazione fixed point è tuttavia assai poco utilizzata. Infatti, la maggior parte dei sistemi

numerici utilizzano, per la rappresentazione dei numeri reali, la notazione floating point, che

permette un errore relativo di rappresentazione notevolmente migliore ed uniforme per tutti i numeri

rappresentabili. Pag. 8

© 2000 G. Cabodi AP00035

Esercizi risolti e proposti di Reti Logi http://www.appunti.net/

Tra i vari formati adottati per le rappresentazioni floating point, esaminiamo lo standard IEEE 754,

utilizzata, tra l’altro, per i reali in semplice precisione sui processori della famiglia INTEL 80x86.

Un reale con segno viene rappresentato su 32 bit, di cui

• 1 bit per il segno

• 8 bit per l’esponente (in base 2) eccesso 127

• 23 bit per la mantissa.

La rappresentazione è conforme allo schema seguente:

(-1)s 2E-127,

S E7 ...E0 m22 ...m0 × ×

= M M = 1.m22...m0

Esempi ⋅ 127-127

0 01111111 00000000000000000000000 = +(1.0) 2 = +1.0

2 ⋅ 128-127

2 = -2.0

1 10000000 00000000000000000000000 = -(1.0) 2 ⋅ 126-127

0 01111110 10000000000000000000000 = +(1.1) 2 = +0.75

2 ⋅ 130-127

2 = -10.0

1 10000010 01000000000000000000000 = -(1.01) 2

Si noti che lo zero (0) viene rappresentato con esponente e mantissa 0:

0 00000000 00000000000000000000000 = +0

1 00000000 00000000000000000000000 = -0

1.6.1 Somma tra numeri in floating-point

La somma tra numeri in floating point si effettua come somma tra numeri in modulo e segno, dopo

aver normalizzato (o allineato) i numeri allo stesso esponente (quello più grande tra i due). Il

risultato va eventualmente normalizzato per ottenere la notazione standard. Il metodo può essere

facilmente rappresentato ricorrendo alla notazione scientifica per i numeri in base 10.

⋅ ⋅

9 6

Esempio: 9.9985 10 + 2.3128 10

⋅ ⋅ 9

9

9.9985 10 + 9.9985000 10 +

⋅ ⋅ 9

6 =

2.3128 10 = 0.0023128 10

----------- ---------------

⋅ ⋅

9 10

10.0008128 10 = 1.00008128 10

In sintesi, tornando alla base 2 e supponendo di voler sommare due numeri in floting point e ,

N N

1 2

e , si effettuano i seguenti passi:

rappresentati in modo simbolico come =S E M N2=S M E

N 1 1 1 1 2 2 2

1. Si confrontano gli esponenti: se sono uguali si procede dal passo 3; se sono diversi se ne calcola

la differenza D=|E -E |.

1 2 ) attribuendogli l’esponente maggiore (es.

2. Si normalizza il numero di esponente minore (es. N 2

D D

dividendone la mantissa per (es. quest’ultima operazione può

E ’=E )e 2 M ’=M /2 ):

2 1 2 2

essere realizzata mediante shift a destra di posizioni (es.

D M ’=M >>D).

2 2

3. Si sommano (somma modulo e segno) le mantisse (con relativo segno):

es. = + =

S M S M S ’M ’, E E = E ’

3 3 1 1 2 2 3 1 2

4. Se il risultato non è normalizzato, lo si normalizza incrementando di 1 l’esponente e dividendo

per 2 la mantissa (shift a destra di una posizione).

Es. 1: -10.0 + 0.75 = -9.25

N = 1 10000010 01000000000000000000000 - (-10.0)

1

N = 0 01111110 10000000000000000000000 = (+0.75)

2 Pag. 9

© 2000 G. Cabodi AP00035

Esercizi risolti e proposti di Reti Logi http://www.appunti.net/

---------------------------------------

S = 1, E = 10000010, M = 1.010000...0

1 1 1

S = 0, E = 01111110, M = 1.100000...0

2 2 2

D = E - E = 4

1 2

E ’ = E

2 1

M ’ = M >>4 = 0.000110...0

2 2

S = 1, M = 1.010000...0 -

1 1

S = 0, M ’ = 0.000110...0 =

2 2 ------------

S = 0, M = 1.001010...0 =

3 3

N = 1 10000010 00101000000000000000000 (-9.25)

3

Es. 2: -10.0 + 0.75 = -9.25

N = 0 01111111 10000000000000000000000 - (+1.5)

1

N = 0 10000001 11100000000000000000000 = (+7.5)

2

---------------------------------------

S = 0, E = 01111111, M = 1.100000...0

1 1 1

S = 0, E = 10000001, M = 1.111000...0

2 2 2

D = E - E = 2

2 1

E ’ = E

1 2

M ’ = M >>2 = 0.011000...0

1 1

S = 0, M ’ = 0.011000...0 +

1 1

S = 0, M = 1.111000...0 =

2 2 -------------

S = 0, M = 10.010000...0

3 3

normalizzazione finale:

E = E +1 = 10000010

3 1

M ’ = M >>1 = 1.001000...0

3 3

N = 0 10000010 00100000000000000000000 (+9.0)

3

1.6.2 Prodotto tra numeri in floating-point

Il prodotto tra due numeri in floating-point può essere effettuato sommandone gli esponenti ed

effettuando il prodotto tra i moduli. Il risultato va poi eventualmente normalizzato. Pag. 10

© 2000 G. Cabodi AP00035

Esercizi risolti e proposti di Reti Logi http://www.appunti.net/

1.7 Il Codice ASCII

E' la codifica più diffusa tra quelle utilizzate per rappresentare l'insieme dei caratteri. Utilizza 8 bit e

non tutte le codifiche sono valide. Si noti, in particolare che le codifiche dei caratteri alfabetici sono

contigue ed ordinate, come pure quelle delle cifre 0..9. Inoltre, le lettere maiuscole e minuscole

differiscono per 1 bit (il terzo da sinistra).

Es. 'A' ha codice 01000001 (= 6510 = 4116)

'a' ha codice 01100001 (= 9710 = 6116) Pag. 11

© 2000 G. Cabodi AP00035

Esercizi risolti e proposti di Reti Logi http://www.appunti.net/

1.8 Esercizi proposti

1. Effettuare le seguenti conversioni di base:

11010112 = ?16

101101112 = ?16

10100100112 = ?16

110110012 = ?8

10111100112 = ?8

1740038 = ?2

67248 = ?2

F3A516 = ?2

AB3D16 = ?2

2. Effettuare le seguenti somme tra numeri ottali:

1372 + 47135 + 175214 + 110321 +

4631 = 5125 = 152405 = 56573 =

---- ----- ------ ------

3. Scrivere per i seguenti numeri le rappresentazioni, su 8 bit, in modulo e segno, complemento a 1

e complemento a 2: +18, +115, +79, -49, -3, -100.

4. Indicare se le seguenti somme tra numeri in c-a-2 su 8 bit generano overflow:

11010100 + 10111001 + 01011101 + 00100110 +

10101011 = 11010110 = 00100001 = 01011010 =

-------- -------- -------- --------

5. Si determinino le regole per sottrarre numeri in codice BCD, enunciando, in particolare, le regole

per la determinazione del riporto e l'applicazione di operazioni di correzione. Pag. 12

© 2000 G. Cabodi AP00035

Esercizi risolti e proposti di Reti Logi http://www.appunti.net/

2. Funzioni logiche

Sia dato lo spazio (insieme dei valori logici o booleani). Si dice funzione logica o

B={0,1}

booleana di variabili logiche , formalmente

f n x1,...,xn →

Bn

f(x1,...,xn ): B

una funzione che ad ogni possibile assegnazione di valori logici alle variabili fa

x1,...,xn

corrispondere un valore logico (0 o 1).

Vari sono i formalismi possibili per rappresentare funzioni logiche. Un formalismo di

rappresentazione si dice canonico se, date due funzioni arbitrarie queste sono uguali se e solo

f,g,

se è uguale la loro rappresentazione.

2.1 Rappresentazione di funzioni logiche

Introduciamo i formalismi in grado di rappresentare funzioni logiche mediante un esempio.

Siano dati tre punti A, B, C e siano definite tre variabili logiche x, y, z,

associate rispettivamente alle coppie di punti AC, BC, AB. Ognuna di queste

variabili assumerà valore 0 per indicare che non esiste connessione diretta

tra i punti associati, 1 per indicare che esiste connessione diretta. Si

rappresenti una funzione logica delle variabili x, y, z, la quale indichi

con 0 l'assenza di connessione (diretta o indiretta) tra i punti A, C, con 1

la presenza di una connessione.

 ¬∃

0 connessione diretta AC

=

x ∃

1 connessione diretta AC

 ¬∃

0 connessione diretta BC

=

y ∃

1 connessione diretta BC

 ¬∃

0 connessione diretta AB

=

z ∃

1 connessione diretta AB

 ¬∃

0 connessione diretta o indiretta AC

3 

→ =

f x y z B B f

( , , ) : , ∃

1 connessione diretta o indiretta AC Pag. 13

© 2000 G. Cabodi AP00035

Esercizi risolti e proposti di Reti Logi http://www.appunti.net/

Tabella di verità (truth table)

Si enumerano su righe diverse le possibili assegnazioni di valori alle variabili indipendenti ed i

corrispondenti valori della funzione. Dato un ordine per le variabili indipendenti e per le righe della

tabella, questa rappresentazione è canonica.

x y z f

0

0 0 0 0

0 0 1 0

0 1 0 1

0 1 1 1

1 0 0 1

1 0 1 1

1 1 0 1

1 1 1

Notazione algebrica

Si definisce letterale una variabile o il complemento della stessa.

Es. .

x, y, x', y'

Si definisce termine prodotto un singolo letterale o il prodotto logico di più letterali.

Es. .

z',xy,x'yz'

Si definisce somma di prodotti (abbreviato SP) la somma logica di più termini prodotto.

.

Es. z'+xy+x'yz'

Si definisce termine somma un singolo letterale o il prodotto logico di più letterali.

Es. .

z',x+y,x'+y+z'

Si definisce prodotto di somme (abbreviato PS) il prodotto logico di più termini somma.

Es. .

z'(x+y)(x'+y+z')

Si dice termine normale un termine (prodotto o somma) in cui nessuna variabile compare più di una

volta (sia in forma affermata che negata).

Es. di termini non normali: .

wxx, vv'wx', w+x+y+y'

Si definisce minterm di variabili un prodotto normale di letterali. I possibili minterm a

n n n

2n

variabili sono (tutte le possibili combinazioni delle variabili in forma affermata o negata).

n

.

Es. di minterm a variabili:

4 v'w'x'y', vw'x'y

Si definisce maxterm di variabili una somma normale di letterali. I possibili maxterm a

n n n

2n

variabili sono (tutte le possibili combinazioni delle variabili in forma affermata o negata).

n

Es. di maxterm a variabili: .

4 v'+w'+x'+y', v+w'+x'+y

Si definisce somma canonica una somma di minterm. Una somma di minterm è infatti una

rappresentazione canonica per una funzione logica. In modo analogo si dice prodotto canonico un

prodotto di maxterm. Pag. 14

© 2000 G. Cabodi AP00035

Esercizi risolti e proposti di Reti Logi http://www.appunti.net/

La funzione precedentemente proposta può essere quindi rappresentata come:

(somma canonica)

f(x,y,z) = x'yz+xy'z'+xy'z+xyz'+xyz (prodotto canonico)

= (x+y+z)(x+y+z')(x+y'+z)

per ricavare la rappresentazione a prodotto canonico si può partire dalla

funzione negata rappresentata come prodotto canonico, procedendo come segue:

f'(x,y,z) = x'y'z'+x'y'z+x'yz'

= ((x'y'z')'⋅(x'y'z)'⋅(x'yz')')' (De Morgan)

= ((x+y+z)(x+y+z')(x+y'+z))' (De Morgan)

da cui

f(x,y,z) = (f'(x,y,z))' = (x+y+z)(x+y+z')(x+y'+z)

Utilizzando i teoremi dell'algebra booleana, una rappresentazione canonica può essere semplificata,

riducendone il numero di termini e di letterali. La forma risultante, tuttavia, non è canonica.

f(x,y,z) = x'yz+xy'z'+xy'z+xyz'+xyz (ab+ac = a(b+c))

= x'yz+xy'(z'+z)+xy(z'+z) (a+a' = 1)

= x'yz+xy'+xy

= x'yz+x (a+a'b = a+b)

= x+yz

f(x,y,z) = (x+y+z)(x+y+z')(x+y'+z) (a = aa)

= (x+y+z)(x+y+z')(x+y+z)(x+y'+z) ((a+b)(a+c) = a+bc)

= (x+y+zz')(x+z+yy') (aa' = 0)

= (x+y)(x+z)

Si noti in particolare la dualità algebrica tra somme e prodotti.

Notazione cubica

La notazione cubica utilizza i valori per rappresentare i letterali. Un letterale viene

0,1

rappresentato in corrispondenza diretta secondo la corrispondenza

0: variabile negata,

1: variabile affermata,

in corrispondenza inversa secondo la corrispondenza

1: variabile negata,

0: variabile affermata.

Un generico termine somma o prodotto viene detto cubo.

Assegnato un ordine alle variabili, un minterm viene rappresentato secondo la corrispondenza

diretta, un maxterm secondo la corrispondenza inversa.

Es. →

vwx'y 1101

v'+w+x+y' 1001

Una somma canonica viene rappresentata come sommatoria di cubi, un prodotto canonico come

prodottoria di cubi. per rappresentare minterm e maxterm si può utilizzare una notazione numerica

(intero corrispondente interpretando il cubo come numero binario). Pag. 15

© 2000 G. Cabodi AP00035

Esercizi risolti e proposti di Reti Logi http://www.appunti.net/

Es. ∑ ∑

f(x,y,z) = x,y,z(011,100,101,110,111) = x,y,z(3,4,5,6,7)

∏ ∏

= x,y,z(000,001,010) = x,y,z(0,1,2)

Un generico termine prodotto o somma viene rappresentato in notazione cubica con tutte le

variabili, utilizzando per quelle mancanti il simbolo '-' (don't care).

Es. ∑

f(x,y,z) = z'+xy+x'yz' = x,y,z(--0,11-,010)

g(x,y,z) = z'(x+y)(x'+y+z') = x,y,z(--1,00-,101) Pag. 16

© 2000 G. Cabodi AP00035

Esercizi risolti e proposti di Reti Logi http://www.appunti.net/

Mappe di Karnaugh

Una mappa di Karnaugh è una rappresentazione di funzioni logiche nella quale le possibili

combinazioni di valori alle variabili indipendenti sono messe in corrispondenza con le caselle di una

mappa rettangolare. Caratteristica importante delle mappe di Karnaugh è il mantenere adiacenti (per

quanto possibile) caselle (assegnazioni di valori alle variabili) che differiscano per una sola

variabile.

Una funzione logica viene rappresentata mediante mappa di Karnaugh inserendo in ogni casella il

valore logico (0,1) corrispondente per la funzione. In pratica compaiono degli nelle caselle

1

associate ai minterm della somma canonica e degli nelle caselle associate ai maxterm del prodotto

0

canonico.

In figura sono riportati schemi di mappe di karnaugh per funzioni di 3, 4 e 5 variabili. Si noti che

tali schemi non sono gli unici possibili. Le singole caselle sono state contrassegnate con un intero

che rappresenta in forma compatta la configurazione delle variabili indipendenti, assumendo per

esse un l'ordine tale intero corrisponde inoltre alla rappresentazione numerica

v,w,x,y,z:

decimale dell'eventuale minterm o maxterm associato alla casella stessa. Dato uno schema con

relativa assegnazione di valori alle variabili indipendenti, una mappa di Karnaugh è una

rappresentazione canonica di funzioni logiche.

vw vw

xy

x 00 01 11 10 00 01 11 10

0 2 6 4 0 4 12 8

1

0 1

0 1

0 1

0 0

1 0

1 0

1 0

1

0 00

1 3 7 5 1 5 13 9

1

0 1

0 1

0 1

0 1 1 1 1

0 0 0 0

1 01 3 7 15 11

0 0 0 0

1 1 1 1

11 2 6 14 10

0 0 0 0

1 1 1 1

10

v 0 1

wx

yz 00 01 11 10 00 01 11 10

0 4 12 8 16 20 28 24

0

1 0

1 0

1 0

1 0

1 0

1 0

1 0

1

00 1 5 13 9 17 21 29 25

1 1 1 1 1 1 1 1

0 0 0 0 0 0 0 0

01 3 7 15 11 19 23 31 27

0 0 0 0 0 0 0 0

1 1 1 1 1 1 1 1

11 2 6 14 10 18 22 30 26

0 0 0 0 0 0 0 0

1 1 1 1 1 1 1 1

10 Pag. 17

© 2000 G. Cabodi AP00035

Esercizi risolti e proposti di Reti Logi http://www.appunti.net/

La funzione proposta

f(x,y,z) = x'yz+xy'z'+xy'z+xyz'+xyz

= (x+y+z)(x+y+z')(x+y'+z)

= x+yz

= (x+y)(x+z)

∑ ∑

= x,y,z(011,100,101,110,111) = x,y,z(3,4,5,6,7)

∏ ∏

= x,y,z(000,001,010) = x,y,z(0,1,2)

= x,y,z(1--,-11)

= x,y,z(00-,0-0)

può quindi essere rappresentata dalla seguente mappa di karnaugh:

xy

z 00 01 11 10

0 2 6 4

1

0 1

0 1

0 1

0

0 1 3 7 5

1

0 1

0 1

0 1

0

1 f

PLA (Programmable Logic Array)

La PLA è una forma di rappresentazione di funzioni logiche basata su notazione cubica. Il termine

Programmable Logic Array, in realtà, fa riferimento al tipo di realizzazione circuitale che se ne

effettua. Una PLA è una matrice in grado di rappresentare funzioni logiche delle stesse

m n

variabili, rappresentate come somme di prodotti (non si tratta di minterm, quindi la rappresentazione

non è canonica). La matrice è formata da righe, ognuna associata ad un diverso termine prodotto,

p

e da colonne.

(n+m)

• Le prime colonne costituiscono il cosiddetto piano nel quale ogni riga rappresenta un

n AND,

termine prodotto in notazione cubica (si ricorda che variabile negata, variabile affermata,

0: 1: -

: variabile non presente).

• Le successive colonne sono associate ognuna ad una diversa funzione logica e contengono 1

m

sulle righe corrispondenti ai termini prodotto presenti, 0 sulle righe corrispondenti ai termini

prodotto assenti dalla funzione stessa.

Es. ∑

f(x,y,z) = x+yz = x,y,z(1--,-11)

g(x,y,z) = x'z+yz = x,y,z(0-1,-11)

piano AND piano OR

x 1 - - 1 0

yz - 1 1 1 1

x'z 0 - 1 0 1

x y z f g Pag. 18

© 2000 G. Cabodi AP00035

Esercizi risolti e proposti di Reti Logi http://www.appunti.net/

2.2 Funzioni non completamente specificate

Una funzione logica si dice non completamente specificata se il suo valore non è definito per una o

più assegnazioni delle variabili di ingresso. In tali configurazioni il valore dell'uscita può in effetti

risultare arbitrario, oppure le configurazioni stesse sono prive di interesse in quanto impossibili (il

dominio della funzione è ristretto alle sole configurazioni valide).

Per indicare l'indifferenza della funzione in corrispondenza ad una assegnazione degli ingressi si

introduce il valore logico don't-care (rappresentato dal simbolo -).

• Si dice on-set di una funzione l'insieme delle configurazioni degli ingressi per le quali

f f=1.

• Si dice off-set di una funzione l'insieme delle configurazioni degli ingressi per le quali

f f=0.

• Si dice don't-care-set di una funzione l'insieme delle configurazioni di indifferenza degli

f

ingressi, per le quali f=-.

Una funzione non completamente specificata viene solitamente rappresentata in uno dei seguenti

f

modi:

• definendo on-set (oppure off-set) e don't-care-set.

• definendo l'insieme di funzioni completamente specificate che coincidono con su on-set e

f

off-set, ed assumono tutte le possibili configurazioni sul don't-care set. tale insieme è dato

dall'intervallo essendo ed due funzioni completamente specificate tali che

(g,h), g h

on-set(g)=on-set(f), off-set(h)=off-set(f).

In pratica si definiscono on-set (tramite e off-set (tramite

g) h).

Presentiamo ora tramite un esempio le possibili rappresentazioni di una funzione non

completamente specificata. Si vuole rappresentare una funzione logica non completamente

specificata definita come segue 

0 se x 3x x1x è la codifica di un numero BCD non primo

2 0

4 

f(x , x , x1 , x ) : B B, f = 1 se x 3x x1x è la codifica di un numero BCD primo

3 2 0 2 0

- se x x x x non è una cifra BCD

3 2 1 0

• si elencano solo le righe segnificative, cioè on-set ed off-

Truth table:

set. x x x x f

3 2 1 0 0

0 0 0 0 1

0 0 0 1 1

0 0 1 0 1

0 0 1 1 0

0 1 0 0 1

0 1 0 1 0

0 1 1 0 1

0 1 1 1 0

1 0 0 0 0

1 0 0 1 Pag. 19

© 2000 G. Cabodi AP00035

Esercizi risolti e proposti di Reti Logi http://www.appunti.net/

• Notazione cubica

∑(1,2,3,5,7)

f(x3x2x1x0) = + d(10,11,12,13,14,15)

∏(0,4,6,8,9)

= × d(10,11,12,13,14,15)

• Mappa di Karnaugh x x

3 2

x x 00 01 11 10

1 0 0 4 12 8

1 1 1 1

0 0 0 0

-

00 1 5 13 9

1 1 1 1

0 0 0 0

-

01 3 7 15 11

0 0 0

1 1 1 1

- -

11 2 6 14 10

0 0 0 0

- -

1 1 1 1

10 f Pag. 20

© 2000 G. Cabodi AP00035

Esercizi risolti e proposti di Reti Logi http://www.appunti.net/

2.3 Minimizzazione di funzioni logiche mediante mappe di Karnaugh

Definizioni 2k

Data una mappa di Karnaugh ad variabili, si dice un insieme di caselle le

n k-cubo (0<k£n) 2k

cui assegnazioni di valori alle variabili assumono, su un sottoinsieme di variabili, tutte le

k

possibili configurazioni, e sulle restanti variabili la stessa configurazione.

(n-k)

Un implicante di ordine di una mappa di Karnaugh è un contenente 1 in ogni casella

k k-cubo

(oppure 0 in ogni casella).

Un implicante copre una casella della mappa se questa appartiene all'implicante.

Un implicante copre un altro implicante se ne copre ogni casella.

Un implicante è detto primo se non è coperto da alcun altro implicante. Un implicante non è primo

se è coperto da almeno un implicante (di ordine superiore). Una funzione logica può essere scritta

come somma degli implicanti primi che coprono i minterm (caselle ad oppure come prodotto

1)

degli implicanti primi che coprono i maxterm (caselle ad Tali rappresentazioni sono canoniche.

0).

Un implicante primo è essenziale se copre almeno una casella non coperta da alcun altro implicante.

Ricerca degli implicanti primi

Es.1. Data la funzione la si scriva sotto forma di somma e di

f(w,x,y)=∑(3,4,5,6,7),

prodotto di implicanti primi.

a) somma di implicanti primi: copertura degli 1.

xy

z 1-- = x

00 01 11 10

0 2 6 4

1

0 1

0 1

0 1

0

0 1 3 7 5

1

0 1

0 1

0 1

0

1 f -11 = yz

∑(1--,-11)

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

b) prodotto di implicanti primi: copertura degli 0.

0-0 = x+z

xy

z 00 01 11 10

0 2 6 4

1

0 1

0 1

0 1

0

0 1 3 7 5

1

0 1

0 1

0 1

0

1

00- = x+y f

∏(00-,0-0)

f(x,y,z) = = (x+y)(x+z) Pag. 21

© 2000 G. Cabodi AP00035

Esercizi risolti e proposti di Reti Logi http://www.appunti.net/

Es.2. Data la funzione la si scriva sotto forma di

f(w,x,y,z)=∑(1,2,3,5,7,11,13),

somma e di prodotto di implicanti primi.

a) somma di implicanti primi: copertura degli 1.

wx

yz 00 01 11 10

0 4 12 8

1 1 1 1

0 0 0 0

00 1 5 13 9

1 1 1 1

0 0 0 0

01 3 7 15 11

0 0 0 0

1 1 1 1

11 2 6 14 10

0 0 0 0

1 1 1 1

10 f

∑(0--1,-101,001-,-011)

f(w,x,y,z) = = w'z+xy'z+w'x'y+x'yz

b) prodotto di implicanti primi: copertura degli 0.

wx

yz 00 01 11 10

0 4 12 8

1 1 1 1

0 0 0 0

00 1 5 13 9

1 1 1 1

0 0 0 0

01 3 7 15 11

0 0 0 0

1 1 1 1

11 2 6 14 10

0 0 0 0

1 1 1 1

10 f

∏(--00,-1-0,1--0,111-,100-)

f(w,x,y,z) =

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

Es.3. Data la seguente mappa di Karnaugh di una funzione funzione si scriva

f(w,x,y,z), f

sotto forma di somma di implicanti primi.

wx wx

yz yz

00 01 11 10 00 01 11 10

0 4 12 8 0 4 12 8

1 1 1 1 1 1 1 1

0 0 0 0 0 0 0 0

00 00

1 5 13 9 1 5 13 9

1 1 1 1 1 1

1 1

0 0 0 0 0 0 0 0

01 01

3 7 15 11 3 7 15 11

0 0 0 01 0 0 0 0

1 1 1 1 1 1 1

11 11

2 6 14 10 2 6 14 10

0 0 0 0 0 0 0 0

1 1 1 1 1 1 1 1

10 10

f f

∑(-10-,--01,-0-1,11--,1--1)

f(w,x,y,z) = = xy'+y'z+x'z+wx+wz Pag. 22

© 2000 G. Cabodi AP00035

Esercizi risolti e proposti di Reti Logi http://www.appunti.net/

Es.4. Data la funzione f(v,w,x,y,z)=∑(5,7,8,10,13,15,16,18,20,24,25,27,29,31),

la si scriva sotto forma di somma e di prodotto di implicanti primi.

a) mappa di Karnaugh v 0 1

wx

yz 00 01 11 10

00 01 11 10

0 4 12 8 16 20 28 24

1 1 1 1 1 1 1 1

0 0 0 0 0 0 0 0

00 1 5 13 9 17 21 29 25

1 1 1 1 1 1 1 1

0 0 0 0 0 0 0 0

01 3 7 15 11 19 23 31 27

0 0 0 0 0 0 0 0

1 1 1 1 1 1 1 1

11 2 6 14 10 18 22 30 26

0 0 0 0 0 0 0 0

1 1 1 1 1 1 1 1

10 f

b) somma di implicanti primi: copertura degli 1.

v 0 1

wx

yz 00 01 11 10

00 01 11 10

1 1 1 1 1 1 1

0 0 0 0 0 0 0 0

1

00 1 1 1 1 1 1 1

0 0 0 0 0 0 0

01 0 0 0 0 0 0 0 0

1 1 1 1 1 1 1 1

11 0 0 0 0 0 0 0 0

1 1 1 1 1 1 1 1

10 f

f(v,w,x,y,z) = v'xz+vwz+wxz+

v'wx'z'+vw'x'z'+vwx'y'+vx'y'z'+vw'y'z'+wx'y'z'

b) prodotto di implicanti primi: copertura degli 0.

v 0 1

wx

yz 00 01 11 10

00 01 11 10

1 1 1 1 1 1 1 1

0 0 0 0 0 0 0 0

00 1 1 1 1 1 1 1 1

0 0 0 0 0 0 0 0

01 0 0 0 0 0 0 0 0

1 1 1 1 1 1 1 1

11 0 0 0 0 0 0 0 0

1 1 1 1 1 1 1 1

10 f

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

(x’+y’+z)(w’+x’+z)(v’+w’+y’+z)(v’+w+x’+y’) Pag. 23

© 2000 G. Cabodi AP00035

Esercizi risolti e proposti di Reti Logi http://www.appunti.net/

Es.5. Data la funzione non

f(x3,x2,x1,x0)=∑(1,2,3,5,7) + d(10,11,12,13,14,15)

completamente specificata, la si scriva sotto forma di somma e di prodotto di implicanti primi. Si

noti che tale rappresentazione consiste in una funzione completamente specificata.

a) somma di implicanti primi: copertura degli 1, utilizzando i - (don't-

care) necessari per ottenere implicanti di ordine il più elevato possibile.

x x

3 2

x x 00 01 11 10

1 0 0 4 12 8

1 1 1 1

0 0 0 0

-

00 1 5 13 9

1 1 1 1

0 0 0 0

-

01 3 7 15 11

0 0 0

1 1 1 1

- -

11 2 6 14 10

0 0 0 0

- -

1 1 1 1

10 f

f(x3,x2,x1,x0) = x3'x0+x2x0+x2'x1+x1x0

a) prodotto di implicanti primi: copertura degli 0, utilizzando i - (don't-

care) necessari per ottenere implicanti di ordine il più elevato possibile.

x x

3 2

x x 00 01 11 10

1 0 0 4 12 8

1 1 1 1

0 0 0 0

-

00 1 5 13 9

1 1 1 1

0 0 0 0

-

01 3 7 15 11

0 0 0

1 1 1 1

- -

11 2 6 14 10

0 0 0 0

- -

1 1 1 1

10 f

f(x3,x2,x1,x0) = x3'(x1+x0)(x2'+x0) Pag. 24

© 2000 G. Cabodi AP00035

Esercizi risolti e proposti di Reti Logi http://www.appunti.net/

Implicanti essenziali ed espressioni minimizzate

Data una mappa di Karnaugh ed una copertura degli 1 (o degli 0) si dice implicante essenziale un

implicante primo che copre almeno un 1 (o uno 0) non coperto da alcun altro implicante primo. Un

implicante si dice invece ridondante se copre unicamente caselle già coperte da implicanti

essenziali: in particolare, l'implicante in oggetto non è essenziale.

Una copertura minima SP (PS) di una mappa di Karnaugh è un insieme di implicanti primi tale da

coprire tutti gli 1 (ogli 0) della mappa, composto da:

• tutti gli implicanti essenziali;

• un insieme minimo di implicanti principali non essenziali e non ridondanti. Un possibile

criterio di minimo è il seguente: gli implicanti primi vanno scelti in modo da minimizzarne il

numero e a parità di numero di implicanti, il numero totale di letterali.

Una copertura minima priva di alee statiche di ordine 1 è una copertura minima alla quale va

eventualmente aggiunto un insieme minimo di implicanti primi, tale da evitare il caso di caselle ad

1 (o 0) adiacenti non incluse in uno stesso implicante.

Es.6. Data la funzione la si minimizzi in forma SP e PS (vedi

f(w,x,y)=∑(3,4,5,6,7),

Es.1). Si richiedono inoltre le forme minime prive di alee statiche di ordine 1.

Tutti gli implicanti primi sono essenziali; le coperture SP e PS ottenute in

Es.1 sono minime e prive di alee statiche.

Es.7. Data la funzione la si minimizzi in forma SP e

f(w,x,y,z)=∑(1,2,3,5,7,11,13),

PS (vedi Es.2). Si richiedono inoltre le forme minime prive di alee statiche di ordine 1.

Tutti gli implicanti primi sono essenziali; le coperture SP e PS ottenute in

Es.2 sono minime e prive di alee statiche.

Es.8. Data la seguente mappa di Karnaugh di una funzione funzione la si

f(w,x,y,z),

minimizzi in forma SP (vedi Es.2). Si richiede inoltre una forma minima priva di alee statiche di

ordine 1. wx

wx wx yz

yz yz 00 01 11 10

00 01 11 10 00 01 11 10 0 4 12 8

0 4 12 8 0 4 12 8 1 1 1 1

0 0 0 0

1 1 1 1 1 1 1 1

0 0 0 0 0 0 0 0 00

00 00 1 5 13 9

1 5 13 9 1 5 13 9 1 1

1 1

0 0 0 0

1 1

1 1 1 1 1 1

0 0 0 0 0 0 0 0 01

01 01 3 7 15 11

3 7 15 11 3 7 15 11 0 0 0 0

1 1 1 1

0 0 0 01 0 0 0 0

1 1 1 1 1 1 1 11

11 11 2 6 14 10

2 6 14 10 2 6 14 10 0 0 0 0

1 1 1 1

0 0 0 0 0 0 0 0

1 1 1 1 1 1 1 1 10

10 10 f

f f no alee

copertura minima

f(w,x,y,z) = xy'+x'z+wx (copertura minima)

f(w,x,y,z) = xy'+x'z+wx+y'z+wz (copertura priva di alee) Pag. 25

© 2000 G. Cabodi AP00035

Esercizi risolti e proposti di Reti Logi http://www.appunti.net/

Es.9. Data la funzione f(v,w,x,y,z)=∑(5,7,8,10,13,15,16,18,20,24,25,27,29,31),

la si minimizzi in forma SP e PS (vedi Es.4). Si richiedono inoltre le forme minime prive di alee

statiche di ordine 1.

a) minimizzazione SP

v 0 1

wx

yz 00 01 11 10 00 01 11 10 implicanti essenziali

1 1 1 1 1 1 1

0 0 0 0 0 0 0 0

1

00 implicanti primi non essenziali

1 1 1 1 1 1 1

0 0 0 0 0 0 0

01 implicante primo ridondante

0 0 0 0 0 0 0 0

1 1 1 1 1 1

1 1

11 0 0 0 0 0 0 0 0

1 1 1 1 1 1 1 1

10 f

f(v,w,x,y,z) = v'xz+vwz+v'wx'z'+vw'x'z'+vw'y'z'+vwx'y'

= “ +wx'y'z'

= “ +vx'y'z' (coperture minime)

f(w,x,y,z) = xy'+x'z+wx+y'z+wz

f(v,w,x,y,z) = v'xz+vwz+v'wx'z'+vw'x'z'+vw'y'z'+

vwx'y'+vx'y'z'+wx'y'z'+wxz (copertura priva di alee)

b) minimizzazione PS.

v 0 1

wx

yz 00 01 11 10 00 01 11 10 implicanti essenziali

1 1 0

1 1 1 1 0

1 1

0 0 0 0 0 0

00 implicanti primi non essenziali

1 1 1 1 1 1 1 1

0 0 0 0 0 0 0 0

01 implicante primo ridondante

0 0 0 0 0 0

0 0

1 1 1 1 1 1 1 1

11 0 0

0 0 0 0 0 0

1 1 1 1 1 1 1 1

10 f

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

(x’+y’+z)(v+w+z) (copertura minima)

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

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

(copertura priva di alee)

Pag. 26

© 2000 G. Cabodi AP00035

Esercizi risolti e proposti di Reti Logi http://www.appunti.net/

Es.10. Data la funzione non

f(x3,x2,x1,x0)=∑(1,2,3,5,7) + d(10,11,12,13,14,15)

completamente specificata, la si minimizzi in forma SP e PS (vedi Es.4). Si richiedono inoltre le

forme minime prive di alee statiche di ordine 1.

a) minimizzazione SP

x x

3 2

x x 00 01 11 10

1 0 implicanti essenziali

1 1 1 1

0 0 0 0

-

00 implicanti primi ridondanti

1 1 1 1

0 0 0 0

-

01 0 0 0

- -

1 1 1 1

11 0 0 0 0

- -

1 1 1 1

10 f

f(x3,x2,x1,x0) = x3'x0+x2'x1 (copertura minima priva di alee statiche)

b) minimizzazione PS

x x

3 2

x x 00 01 11 10

1 0 0 4 12 8 implicanti essenziali

1 1 1 1

0 0 0 0

-

00 1 5 13 9

1 1 1 1

0 0 0 0

-

01 3 7 15 11

0 0 0

1 1 1 1

- -

11 2 6 14 10

0 0 0 0

- -

1 1 1 1

10 f

f(x3,x2,x1,x0) = x3'(x1+x0)(x2'+x0)

(copertura minima priva di alee statiche) Pag. 27

© 2000 G. Cabodi AP00035

Esercizi risolti e proposti di Reti Logi http://www.appunti.net/

2.4 Esercizi proposti

1. Sia data la seguente mappa di Karnaugh. La si minimizzi in forma NAND-NAND

mediante una copertura priva di alee statiche.

vw

00 01 11 10

xy 00 - 0 0 1

01 1 1 0 0

11 1 - 0 -

10 - 0 0 1

vw

00 01 11 10

0 4 12 8

xy 00 1 5 13 9

01 3 7 15 11

11 2 6 14 10

10 Pag. 28

© 2000 G. Cabodi AP00035

Esercizi risolti e proposti di Reti Logi http://www.appunti.net/

2. Sia dato il seguente schema di mappa di Karnaugh.

vwx

000 001 011 010 100 101 111 110

yz 00

01

11

10

Lo si utilizzi per minimizzare come somma di prodotti e prodotto di somme le seguenti

funzioni. Si rappresentino in forma algebrica il risultati.

Σ(4,6,7,9,11,12,13,14,15,20,22,25,27,28,30)

F(vwxyz) = + d(1,5,29,31).

vwx

000 001 011 010 100 101 111 110

1 5 12 9 16 20 28 24

yz 00 2 6 13 10 17 21 29 25

01 4 8 15 12 19 23 31 27

11 3 7 14 11 18 22 30 26

10

F(vwxyz) = ...............................................................................................................

vwx

000 001 011 010 100 101 111 110

1 5 12 9 16 20 28 24

yz 00 2 6 13 10 17 21 29 25

01 4 8 15 12 19 23 31 27

11 3 7 14 11 18 22 30 26

10

F(vwxyz) = ............................................................................................................... Pag. 29

© 2000 G. Cabodi AP00035

Esercizi risolti e proposti di Reti Logi http://www.appunti.net/

Σ(4,5,10,12,13,16,17,21,25,26,27,29).

F(vwxyz) = vwx

000 001 011 010 100 101 111 110

1 5 12 9 16 20 28 24

yz 00 2 6 13 10 17 21 29 25

01 4 8 15 12 19 23 31 27

11 3 7 14 11 18 22 30 26

10

F(vwxyz) = ...............................................................................................................

vwx

000 001 011 010 100 101 111 110

1 5 12 9 16 20 28 24

yz 00 2 6 13 10 17 21 29 25

01 4 8 15 12 19 23 31 27

11 3 7 14 11 18 22 30 26

10

F(vwxyz) = ...............................................................................................................

Σ(5,6,13,14,17,18,19,21,22,23,24,25,27,31).

F(vwxyz) = vwx

000 001 011 010 100 101 111 110

1 5 12 9 16 20 28 24

yz 00 2 6 13 10 17 21 29 25

01 4 8 15 12 19 23 31 27

11 3 7 14 11 18 22 30 26

10

F(vwxyz) = ...............................................................................................................

vwx

000 001 011 010 100 101 111 110

1 5 12 9 16 20 28 24

yz 00 2 6 13 10 17 21 29 25

01 4 8 15 12 19 23 31 27

11 3 7 14 11 18 22 30 26

10

F(vwxyz) = ............................................................................................................... Pag. 30

© 2000 G. Cabodi AP00035

Esercizi risolti e proposti di Reti Logi http://www.appunti.net/

3. Circuiti Combinatori

(realizzati con porte logiche)

3.1 Analisi funzionale

Problema. Dato lo schema di un circuito combinatorio, descritto mediante porte logiche, se ne

ricavi la funzione logica realizzata.

I O

Rete 

Combinatoria ∈ n

n I B

m 

= ∈

 m

( )

O F I O B

 → =

n m

: , ( , ,..., )

F B B F f f f

 − −

1 2 0

m n

Es.1. Ricavare la funzione logica realizzata dal circuito in figura e rappresentarla mediante tabella di

verità, notazione cubica e algebrica, mappa di Karnaugh, PLA.

N1

A

S O

B N2

• Tabella di verità (truth table) S A B N1 N2 O

0 0 0 0 0 0

0 0 1 0 0 0

0 1 0 1 0 1

0 1 1 1 0 1

1 0 0 0 0 0

1 0 1 0 1 1

1 1 0 0 0 0

1 1 1 0 1 1

• Notazione cubica. Σ Π

O = f(S,A,B) = (2,3,5,7) = (0,1,4,6)

• Notazione algebrica.

O = f(S,A,B) = S’A+SB Pag. 31

© 2000 G. Cabodi AP00035

• Mappa di Karnaugh.

Esercizi risolti e proposti di Reti Logi http://www.appunti.net/

SA

00 01 11 10

B 0 0 1 0 0

1 0 1 1 1

• PLA.

- 1 1 1

1 - 0 1

A B S O

Es.2. Ricavare la funzione logica realizzata dal circuito in figura e rappresentarla mediante tabella di

verità, notazione cubica e algebrica, mappa di Karnaugh, PLA.

A

B S

C R

• Tabella di verità (truth table) A B C R S

0 0 0 0 0

0 0 1 0 1

0 1 0 0 1

0 1 1 1 0

1 0 0 0 1

1 0 1 1 0

1 1 0 1 0

1 1 1 1 1

• Notazione cubica. Σ Π

R = f (A,B,C) = (3,5,6,7) = (0,1,2,4)

1 Σ Π

S = f (A,B,C) = (1,2,4,7) = (0,3,5,6)

0

• Notazione algebrica.

R = f (A,B,C) = AB+AC+BC

1 ⊕ ⊕

S = f (A,B,C) = A B C

0 Pag. 32

© 2000 G. Cabodi AP00035

• Mappa di Karnaugh.

Esercizi risolti e proposti di Reti Logi http://www.appunti.net/

AB AB

00 01 11 10 00 01 11 10

C 0 0 0 1 0 C 0 0 1 0 1

1 0 1 1 1 1 1 0 1 0

R S

AB

00 01 11 10

C 0 00 01 10 01

1 01 10 11 10

R S

• PLA.

0 0 1 01

0 1 0 01

1 0 0 01

1 1 1 01

1 1 - 10

1 - 1 10

- 1 1 10

A B C RS

Es.3. Si rappresentino le funzioni logiche realizzata dal circuito in figura.Si dica poi se il circuito è

equivalente a quello dell’esercizio precedente.

A N1

B S

C R

• Tabella di verità (truth table) Pag. 33

© 2000 G. Cabodi AP00035

A B C N1 R S

Esercizi risolti e proposti di Reti Logi http://www.appunti.net/

0 0 0 0 0 0

0 0 1 0 0 1

0 1 0 1 0 1

0 1 1 1 1 0

1 0 0 1 0 1

1 0 1 1 1 0

1 1 0 0 1 0

1 1 1 0 1 1

La rappresentazione è canonica. La tabella è uguale a quella dell’es. 2 => I circuiti sono equivalenti.

• Notazione cubica e mappe di Karnaugh: coincidono con quelle dell’es. 2.

• Notazione algebrica.

N1 = AB’+A’B

R = g (A,B,C) = N1(A,B)C + AB =

1 = (AB’+A’B)C + AB = AB’C + A’BC + AB

S = g (A,B,C) = N1(A,B)C’ + N1’(A,B)C =

2 = (AB’+A’B)C’ + (AB’+A’B)’C =

= AB’C’ + A’BC’ + (A’+B)(A+B’)C =

= AB’C’ + A’BC’ + A’B’C + ABC

= g e f = g (f e f da es. 2) mediante i teoremi dell’algebra Booleana

Si può dimostrare che f

1 1 2 2 1 2

oppure portando f , g , f e g in forma canonica (g è già in forma canonica).

1 1 2 2 2

• PLA.

0 0 1 01

0 1 0 01

1 0 0 01

1 1 1 01

0 1 1 10

1 0 1 10

1 1 - 10

A B C RS Pag. 34

© 2000 G. Cabodi AP00035

3.2 Analisi ingresso-uscita

Esercizi risolti e proposti di Reti Logi http://www.appunti.net/

Data la descrizione del circuito, determinare i valori di uscita corrispondenti a valori noti per gli

ingressi (o viceversa).

Data la funzione logica realizzata da un circuito, Calcolare i valori di corrispondenti

O = F(I), O

a valori dati par è relativamente semplice: è sufficiente sostituire alle variabili di ingresso i valori

I

relativi e valutare in particolare, ad ogni configurazione di ingresso completamente specificata

F;

corrisponde una sola configurazione di valori in uscita. Dati i valori di uscita (O), calcolare le

configurazioni di valori di ingresso che producono tali valori di uscita è operazione più complessa,

perchè generalmente una data configurazione di uscita può essere prodotta da più configurazioni in

ingresso.

Es. 4. Dato il circuito di Es.2, trovare l’insieme delle configurazioni di ingresso che producono in

uscita RS = 10.

• Calcolo mediante tabella di verità. Si selezionano le righe corrispondenti a RS = 10.

A B C R S

0 0 0 0 0

0 0 1 0 1

0 1 0 0 1

0 1 1 1 0

1 0 0 0 1

1 0 1 1 0

1 1 0 1 0

1 1 1 1 1

Le configurazioni di ingresso possono essere rappresentate dalla seguente tabella

A B C

0 1 1

1 0 1

1 1 0 α

Definito l’insieme tale insieme può essere caratterizzato da una

= {011, 101, 110}, α

funzione logica delle variabili che vale per le configurazioni di valori appartenenti ad

A,B,C, 1 α,

e per quelle non appartenenti. Tale funzione si dice funzione caratteristica dell’insieme

0

formalmente definita come  α

0

: se ABC

χ = 

( A , B , C )

α α

 ∈

 1

: se ABC

α(A,B,C).

più semplicemente, la si può scrivere Nel caso proposto

α(A,B,C) = R(A,B,C) S’(A,B,C)

• Notazione cubica

α(A,B,C) Σ(3,5,6,7)(Σ(1,2,4,7))’

= Σ(3,5,6,7)Σ(0,3,5,6) Σ(3,5,6)

= =

Π(0,1,2,4)(Π(0,3,5,6))’

= Π(0,1,2,4)Π(1,2,4,7) Π(0,1,2,4,7)

= =

• Notazione algebrica Pag. 35

© 2000 G. Cabodi AP00035


ACQUISTATO

4 volte

PAGINE

76

PESO

326.46 KB

AUTORE

Menzo

PUBBLICATO

+1 anno fa


DETTAGLI
Esame: Reti logiche
Corso di laurea: Corso di laurea in ingegneria informatica
SSD:
A.A.: 2013-2014

I contenuti di questa pagina costituiscono rielaborazioni personali del Publisher Menzo di informazioni apprese con la frequenza delle lezioni di Reti logiche e studio autonomo di eventuali libri di riferimento in preparazione dell'esame finale o della tesi. Non devono intendersi come materiale ufficiale dell'università Napoli Federico II - Unina o del prof Canonico Roberto.

Acquista con carta o conto PayPal

Scarica il file tutte le volte che vuoi

Paga con un conto PayPal per usufruire della garanzia Soddisfatto o rimborsato

Recensioni
Ti è piaciuto questo appunto? Valutalo!

Altri appunti di Reti logiche

Reti Logiche – Slides
Dispensa
Reti Logiche – Boole
Dispensa
Reti Logiche - prova d'esame 2004
Esercitazione
Reti Logiche - riconoscitore di codice 8-4-2-1
Esercitazione