01-Codifica binaria-Esercizi (1)

FONDAMENTI DI INFORMATICA 1

Università degli Studi di CagliariCorso di Laurea in Ingegneria Biomedica (Industriale), Chimica, Elettrica

Esercitazione

ALGEBRA DI BOOLE

CODIFICA BINARIA DELL’INFORMAZIONE

A.A. 2008/2009

Docente: Gian Luca Marcialis

http://www.diee.unica.it/~marcialis/FI1

Fondamenti di Informatica 1 - A.A. 2008/09 - Ing. Gian Luca Marcialis 2

Un esercizio semplice

� Dimostrare che A * A’ = 0 e A + A’ = 1� Si usino le tabelle di verità

A A’ A * A’ A + A’0 1 0 11 0 0 1


Il teorema di De Morgan

� Si verifichi l’uguaglianza (A + B)’ = A’ * B’ utilizzando � le proprietà dell’algebra booleana

� le tabelle di verità

� Soluzione� Per la proprietà dell’elemento complementare: (A+B)’ * (A+B) = 0

� Quindi anche A’ * B’ * (A+B) = 0

� Sviluppando l’espressione precedente:

� A’ * B’ * A + A’ * B’ * B = A’ * A * B + A’ * B’ * B = 0 + 0 = 0 c.v.d.


Semplificazione di espressioni booleane

� Si semplifichi la seguente espressione applicando le proprietà e i teoremi dell’algebra booleana:

� A*B’ + C*A’ + A*C� Soluzione:

� = C * (A’ + A) + A*B’ = {prop. distributiva}

� = C + A*B’ {prop. El. Complementare + neutro}

� Verificare che il numero di operatori booleani richiesti dopo lasemplificazione sia inferiore a quello iniziale

− Inizialmente: 3 AND, 2 OR, 2 NOT− Semplificando: 1 AND, 1 OR, 1 NOT


Dal compito del 8/7/2008

� Semplificare la seguente espressione con i teoremi dell’algebra booleana:

� A*B’ + B*C + A*C’� Soluzione

� = A * (B’ + C’) + B*C = {commutatività + distributività}

� = A * (B*C)’ + B*C = { De Morgan}

� = (A + B*C) * ((B*C)’ + B*C) = {distributività + el. complementare}

� = A + B*C

� Verificare l’uguaglianza con le tavole di verità


Dal compito del 4/2/2009

� Date tre variabili booleane, che descrivono tre eventi relativi all’esame di Fondamenti di Informatica 1:� Scritto_Soddisfacente == 1 � voto conseguito allo scritto > 20

� Orale_Superato == 1 � orale OK

� Scritto_Insufficiente == 1 � voto conseguito allo scritto < 16

� Esprimere la variabile Esame_Superato in funzione delle precedenti, secondo le regole di Fondamenti di Informatica 1

� Soluzione:� Esame_Superato = Scritto_Soddisfacente + Orale_Superato * Scritto_Insufficiente’

� Infatti Esame_Superato == 1 quando:− Lo scritto ha voto > 20 � Scritto_Soddisfacente == 1− Oppure ,

• Lo scritto ha voto >= 16 � Scritto_Insufficiente’ == 1

• E l’orale è stato superato �Orale_Superato == 1

� Nota bene: la forma ottenuta è del tipo C + A*B’ (vedi slide n. 4)


Esercizi di aritmetica binaria

� Convertire 1011, espresso in cifre binarie, nella rappresentazione decimale

� Soluzione� Si usa l’algoritmo di conversione:

� X = 1*23 + 0*22 + 1*21 + 1*20 = 8 + 0 + 2 + 1 = 1110� Convertire il decimale 11 in binario� Soluzione:

� Algoritmo delle divisioni successive. Il resto corrisponde alle cifre binarie a partire da quella meno significativa

� 11/2={quoz. 5, resto 1}; 5/2 = {2, 1}; 2/2 = {1, 0}; 1/2 = {0, 1}


Aritmetica in virgola fissa

� Esprimere 13.7510 in binario� Soluzione

� Si separano parte intera e parte frazionaria

� Per la parte intera si usa l’algoritmo delle divisioni successive, ottenendo: 13 = 1101

� Per la parte frazionaria si usa l’algoritmo delle moltiplicazioni successive 0.75 = 0.11

− Ottenuto come segue: 0.75 * 2 = 1.5; 0.5 * 2 = 1.0− Poiché la parte frazionaria dopo l’ultima iterazione è zero,

l’algoritmo termina

� Quindi: 13.7510 = 1101.112


Conversione in virgola mobile

� Esprimere il valore dell’esercizio precedente in virgola mobile secondo la convenzione 1.b * 2E

� ‘b’ è la parte della mantissa che precede l’1 piùsignificativo, unico valore in parte intera

� Soluzione� 1101.11 = 1101.11 * 23 * 2-3 = 1.10111 * 23

� Esprimendo per esempio l’esponente in segno e valore con tre bit (quello più significativo, posto a zero, indica segno positivo):

� 1.10111 * 2011

� Si ottiene dunque b 10111, E 011


Alcuni semplici algoritmi in pseudo-

codice: l’algoritmo del prodotto

� Si supponga di implementare l’algoritmo del prodotto di due valori X e N come N volte la somma di X

� In altri termini, la seguente sommatoria:

� Soluzione� Utilizziamo i come indice per contare il numero di volte che sommiamo X con sé stesso

� Ricordando che l’espressione A = A + B significa: “prendo il vecchio valore di A, gli sommo B, ed il risultato lo assegno di nuovo ad A”, posso scrivere l’algoritmo come segue:

− Input: X e N; Output Y = X * N− i=0− Y=0− Ripeti

• Y = Y + X

• i = i + 1

− Finché i < N

NXXXXXYN

i

⋅=+++==∑=

...1


L’algoritmo della potenza

� Con lo stesso criterio precedente, voglio implementare l’algoritmo dell’elevamento a potenza Y = BE

� In questo caso abbiamo una “produttoria”:

� Soluzione� Appoggiamoci sempre ad i come “contatore”

� L’espressione A = A + B può anche essere A = A * B che significa “prendo il vecchio valore di A, gli moltiplico B ed il risultato lo assegno ad A”

� Input: B, E; Output: Y = BE

� i=1;

� Y=1

� Finché i<=E− Y = Y * B− i = i + 1

� Ripeti

� Abbiamo anticipato l’espressione “Finché” così l’algoritmo funziona anche se E = 0.

∏=

=⋅⋅⋅==E

i

EBBBBBY1

...

01-Codifica binaria-Esercizi (1)

Documents

Transcript of 01-Codifica binaria-Esercizi (1)