Sistemi di Numerazione
e
Algebra Booleana
Laura Farinetti
Claudio Fornaro
Antonio Lioy
Massimo Poncino
Dipartimento di Automatica e Informatica
Politecnico di Torino
Sistemi di numerazione
Il sistema di numerazione usuale e
posizionale (unita, decine, centinaia, : : :)
decimale (cifre = 0,1,2,3,4,5,6,7,8,9)
In altre parole:
208 = 2 10 + 0 10 + 8 10
2
1
0
Altri sistemi di numerazione di interesse sono anch'essi posizionali, ma con base diversa da 10.
sistema
binario
ottale
esadecimale
base
cifre
2
01
8
01234567
16 0 : : : 9 A B C D E F
c 1992 - 96 - L.Farinetti, C.Fornaro, A.Lioy, M.Poncino (POLITO - DAI)
SN-AB.1
Conversione decimale ! base N
Si eettuano divisioni successive del numero dato per
la base N; i resti delle singole divisioni, presi alla
rovescia, rappresentano le cifre del numero nella base
N.
Esempio: convertire 107 in base 2, 5 e 16.
10
107 53 26 13 6 3 1 0
1 1 0 1 0 1 1
107 21 4 0
2 1 4
; quozienti
; resti
; quozienti
; resti
107 6 0 ; quozienti
11 6
; resti
I resti sono in base 10, quindi devono essere convertiti in base N: (11) = (B) .
2
16
Quindi 107 = (1101011)
= (412)
= (6B )
10
2
5
16
c 1992 - 96 - L.Farinetti, C.Fornaro, A.Lioy, M.Poncino (POLITO - DAI)
SN-AB.2
Esercizi - conversione decimale ! base N
Convertire i seguenti numeri decimali nelle basi specicate:
345 in base 2
345 in base 8
345 in base 16
989 in base 5
417 in base 7
615 in base 9
426 in base 2
1042 in base 11
c 1992 - 96 - L.Farinetti, C.Fornaro, A.Lioy, M.Poncino (POLITO - DAI)
[R. 101011001]
[R. 531]
[R. 159]
[R. 12424]
[R. 1134]
[R. 753]
[R. 110101010]
[R. 868]
SN-AB.3
Esercizi - conversione decimale ! base N
Convertire i seguenti numeri decimali nelle basi specicate:
6666 in base 16
4596 in base 4
687 in base 16
595 in base 5
111 in base 2
656 in base 5
811 in base 16
1101 in base 8
c 1992 - 96 - L.Farinetti, C.Fornaro, A.Lioy, M.Poncino (POLITO - DAI)
[R. 1A0A]
[R. 1013310]
[R. 2AF]
[R. 4340]
[R. 1101111]
[R. 10111]
[R. 32B]
[R. 2115]
SN-AB.4
Conversione base N ! decimale
Partendo dalla cifra piu signicativa, si moltiplica
la cifra per il valore della base, elevata alla potenza
corrispondente alla posizione.
Esempio: convertire (302) in base 10.
La cifra meno signicativa indica il coeciente di 7 ,
quella piu signicativa il coeciente di 7 , per cui
7
0
2
(302) = 3 7 + 0 7 + 2 7
= 3 49 + 0 7 + 2 1
= 147 + 0 + 2
= 149
7
2
1
0
c 1992 - 96 - L.Farinetti, C.Fornaro, A.Lioy, M.Poncino (POLITO - DAI)
SN-AB.5
Esercizi - conversione base N ! decimale
Convertire in base 10 i seguenti numeri espressi nelle
basi indicati:
(1000101)
(477)
2
8
[R. 69]
[R. 319]
(40F )
16
[R. 1039]
(3074)
5
(5778)
[R. Impossibile]
9
[R. 4283]
(126)
9
(781)
16
(3B8)
13
c 1992 - 96 - L.Farinetti, C.Fornaro, A.Lioy, M.Poncino (POLITO - DAI)
[R. 105]
[R. 1921]
[R. 658]
SN-AB.6
Esercizi - conversione base N ! decimale
Convertire in base 10 i seguenti numeri espressi nelle
basi indicati:
(10010)
8
[R. 4104]
16
[R. 746]
(2EA)
(369F 1)
(5669)
11
(94598)
(889)
15
10
12
[R. Impossibile]
[R. 7456]
[R. 94598]
[R. 1257]
(1110)
3
(1357)
[R. 1065]
8
[R. 751]
c 1992 - 96 - L.Farinetti, C.Fornaro, A.Lioy, M.Poncino (POLITO - DAI)
SN-AB.7
Conversione base N ! base M
In generale conviene fare la conversione da base N a
base 10, seguita dalla conversione da base 10 a base
M.
Nel caso particolare in cui si debba passare dalla base
2 alle basi 8 o 16 (o viceversa), il calcolo e semplicato perche:
ogni cifra ottale (0, : : : , 7) e esprimibile nella
corrispondente codica binaria (000, : : : , 111) su
3 cifre binarie
ogni cifra esadecimale (0, : : : , F) e esprimibile
nella corrispondente codica binaria (0000, : : : ,
1111) su 4 cifre binarie
c 1992 - 96 - L.Farinetti, C.Fornaro, A.Lioy, M.Poncino (POLITO - DAI)
SN-AB.8
Esempi - conversione base N ! base M
Convertire (01001010100010110) in ottale
Partendo dalla cifra meno signicativa si considerano
la cifre binarie rispettivamente a gruppi di 3:
2
01 001 010 100 010 110
# #
#
1 1
#
2
#
4
#
2
6
Quindi: (01001010100010110) = (112426)
2
8
Convertire (A3D) in binario
Scriviamo le singole cifre esadecimali come numeri
binari di 4 cifre:
16
(A)
#
(D)
(3)
16
#
16
#
16
(1010) (0011) (1101)
2
2
Quindi: (A3D) = (101000111101)
16
2
2
c 1992 - 96 - L.Farinetti, C.Fornaro, A.Lioy, M.Poncino (POLITO - DAI)
SN-AB.9
Esercizi - conversione base N ! base M
Convertire i seguenti numeri nelle basi indicate:
(10010101001010) in base 8
[R. 22512]
(11110101101000) in base 16
[R. 3D68]
(13277) in base 2
[R. 1011010111111]
(B0E 9) in base 2
[R. 1011000011101001]
(214) in base 2
[R. 111011]
(354) in base 6
[R. 510]
(821) in base 12
[R. 477]
(821) in base 8
[R. 1233]
(821) in base 16
[R. 29B]
2
2
8
16
5
7
9
9
9
c 1992 - 96 - L.Farinetti, C.Fornaro, A.Lioy, M.Poncino (POLITO - DAI)
SN-AB.10
Esercizi - conversione base N ! base M
Convertire i seguenti numeri nelle basi indicate:
(AC 29B) in base 8
16
(34772) in base 16
8
(1011) in base 13
9
(312) in base 4
16
(1492) in base 15
11
(C 14) in base 16
15
(C 14) in base 8
15
(558) in base 12
9
c 1992 - 96 - L.Farinetti, C.Fornaro, A.Lioy, M.Poncino (POLITO - DAI)
[R. 2541233]
[R. 39FA]
[R. 44B]
[R. 30102]
[R. 87B]
[R. A9F]
[R. 5237]
[R. 322]
SN-AB.11
Addizioni e sottrazioni in binario
Si eettuano secondo le regole del sistema decimale,
ossia sommando (sottraendo) le cifre di pari peso
Si suppone di non avere limitazione sul numero di
cifre binarie (bit) disponibili.
Esempio: eettuare la somma binaria 11110+10100
1
1
1
1 1 1 1 0 +
1 0 1 0 0
1 1 0 0 1 0
Esempio: eettuare la dierenza binaria 1011 ; 0110
1
1 0 1 1 0 1 1 0
0 1 0 1
c 1992 - 96 - L.Farinetti, C.Fornaro, A.Lioy, M.Poncino (POLITO - DAI)
SN-AB.12
Carry e Borrow
Come nelle usuali operazioni su numeri decimali, si
puo avere un riporto sul bit di peso immediatamente
superiore, o un prestito dal bit di peso immediatamente superiore.
Nella numerazione binaria questi sono detti rispettivamente carry e borrow.
Le somme (dierenze) bit a bit possono essere denite come segue:
0+0=0
1+0=1
0+1=1
1 + 1 = 0 (carry=1)
0;0=0
1;0=1
1;1=0
0 ; 1 = 1 (borrow=1)
c 1992 - 96 - L.Farinetti, C.Fornaro, A.Lioy, M.Poncino (POLITO - DAI)
SN-AB.13
Esercizi - somme e sottrazioni in binario
Eettuare le seguenti operazioni in binario puro:
(34) + (77)
[R. 1101111]
(225) + (63)
[R. 100100000]
(229) + (111)
[R. 101010100]
(10) ; (6)
[R. 100]
(39) ; (14)
[R. 11001]
(32) ; (7)
[R. 11001]
(84) ; (37)
[R. 101111]
(18) ; (7)
[R. 1011]
(25) ; (15)
[R. 1010]
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
c 1992 - 96 - L.Farinetti, C.Fornaro, A.Lioy, M.Poncino (POLITO - DAI)
SN-AB.14
Overow
Nel caso in cui si abbia un numero limitato di bit a
disposizione (come avviene nella realta), si possono
avere due casi particolari:
carry sul bit piu signicativo (MSB)
borrow dal bit piu signicativo (MSB)
In entrambi i casi il numero di bit ssato non e sufciente per rappresentare il risultato.
Questa condizione si dice condizione di overow.
c 1992 - 96 - L.Farinetti, C.Fornaro, A.Lioy, M.Poncino (POLITO - DAI)
SN-AB.15
Esempi - overow
Considerando numeri binari di 4 bit, eettuare la
somma 9 + 7
(9) = (1001)
(7) = (0111)
10
2
10
2
1 0 0 1 +
0 1 1 1
1 0 0 0 0
Il risultato non e rappresentabile su 4 bit: overow.
Considerando numeri binari di 4 bit, eettuare la
dierenza 4 ; 7
(4) = (0100)
(7) = (0111)
10
2
10
2
(1) 0 1 0 0 0 1 1 1
1 1 0 1
Il risultato non e rappresentabile su 4 bit: overow.
c 1992 - 96 - L.Farinetti, C.Fornaro, A.Lioy, M.Poncino (POLITO - DAI)
SN-AB.16
Rappresentazione in modulo e segno
E' uno dei modi per rappresentare numeri interi relativi su un numero ssato di bit.
Dati N bit, il bit piu signicativo indica il segno, ed i
restanti N-1 il valore assoluto del numero, in binario
puro.
S
modulo
0: segno +
1: segno ;
In questa notazione esistono due rappresentazioni
del numero 0:
0
1
0:::0
0:::0
;! +0
;! ;0
c 1992 - 96 - L.Farinetti, C.Fornaro, A.Lioy, M.Poncino (POLITO - DAI)
SN-AB.17
Esercizi - modulo e segno
Rappresentare in modulo e segno su 4 bit il massimo
e minimo valore, le due rappresentazioni dello 0, i
numeri +5 e ;1.
Soluzione:
minimo numero = 1111 = ;7
massimo numero = 0111 = +7
;0 = 1000
+0 = 0000
+5 = 0101
;1 = 1001
c 1992 - 96 - L.Farinetti, C.Fornaro, A.Lioy, M.Poncino (POLITO - DAI)
SN-AB.18
Rappresentazione in complemento a due
Conversione da decimale a complemento a due:
se il numero e positivo, la corrispondente rappresentazione in C.A. 2 e costituita dal modulo del
numero in binario a cui viene aggiunto il bit di
segno con valore zero (MSB)
0
modulo
se il numero e negativo:
{ si scrive il corrispondente numero positivo in
rappresentazione C.A. 2
{ si complementano tutti i bit
{ si somma 1
Le ultime due operazioni rappresentano l'operazione
di \complemento a due" di un numero binario
Osservazioni:
i numeri negativi hanno sempre bit di segno = 1
esiste una sola rappresentazione dello 0: (0 : : : 0)
c 1992 - 96 - L.Farinetti, C.Fornaro, A.Lioy, M.Poncino (POLITO - DAI)
SN-AB.19
Rappresentazione in complemento a due
Un modo alternativo per calcolare il \complemento
a due" di un numero binario negativo e il seguente:
Considerando il numero da destra a sinistra eseguo
le seguenti operazioni:
copio tutti gli zeri no a trovare il primo uno
copio l'uno
complemento i restanti bit
Esempio:
01 : : : 01 : : : 01
10 : : : 10 : : : 10
1
0:::0
1
1
0:::0
0:::0
0:::0
c 1992 - 96 - L.Farinetti, C.Fornaro, A.Lioy, M.Poncino (POLITO - DAI)
SN-AB.20
Esempi - complemento a due
Rappresentare in complemento a due su 5 bit il numero (+8)
10
codico il modulo in binario (+8) = (1000)
il numero e positivo, quindi il bit di segno e 0
10
2
(+8) = (01000)CA
10
2
Rappresentare in complemento a due su 5 bit il numero (;11)
10
codico il modulo in binario (+11) = (01011)
complementando i bit si ha (10100)
sommando +1 (cioe 00001), si ha:
(;11) = (10101)CA
10
2
2
10
c 1992 - 96 - L.Farinetti, C.Fornaro, A.Lioy, M.Poncino (POLITO - DAI)
2
SN-AB.21
Conversione da complemento a due a
decimale
se il numero e positivo (MSB=0), si converte come un numero binario puro
se il numero e negativo (MSB=1):
{ si sottrae 1
{ si complementano tutti i bit
{ si converte il numero cos ottenuto considerandolo come un numero binario puro
I primi due punti possono essere attuati anche
applicando l'operazione di complemento a 2 al
numero, infatti ((numero)CA )CA =numero
2
c 1992 - 96 - L.Farinetti, C.Fornaro, A.Lioy, M.Poncino (POLITO - DAI)
2
SN-AB.22
Conversione da complemento a due a
decimale - esempio
Scrivere il numero decimale corrispondente al numero 100101 in complemento a due su 6 cifre
Il numero (100101)CA e negativo, percio
2
prima sottraggo 1, ottenendo (100100)
complementando i bit ottengo (011011)
converto considerando il numero in binario puro:
(011011) = 1 2 + 1 2 + 1 2 + 1 2 = (27)
2
2
2
4
3
1
0
10
Quindi il numero decimale corripsondente e ;27.
c 1992 - 96 - L.Farinetti, C.Fornaro, A.Lioy, M.Poncino (POLITO - DAI)
SN-AB.23
Limiti delle rappresentazioni
Fissato il numero N di bit disponibili, e possibile
rappresentare i seguenti numeri:
binario puro
modulo e segno
complemento a due
N
0 : : : (2
;(2N ;1 ; 1)
:::
;(2N ;1)
; 1)
;0+0
:::0:::
:::
+ (2
+ (2
N ;1 ; 1)
N ;1 ; 1)
Ad esempio, su 5 bit e possibile rappresentare i seguenti numeri:
in binario puro : da 0 a 31
in modulo e segno : da ;15 a +15
in complemento a due: da ;16 a +15
c 1992 - 96 - L.Farinetti, C.Fornaro, A.Lioy, M.Poncino (POLITO - DAI)
SN-AB.24
Rappresentazione di oggetti
Per rappresentare N oggetti con numeri binari occorrono almeno K bit:
K = dlog (N )e
dove per dX e si intende il numero intero immediatamente superiore od uguale ad X (funzione ceiling).
Ad esempio, per rappresentare 77 oggetti, sono necessari almeno 7 bit (2 = 128), dato che con 6 bit
posso arrivare solo no a 2 = 64.
2
7
6
c 1992 - 96 - L.Farinetti, C.Fornaro, A.Lioy, M.Poncino (POLITO - DAI)
SN-AB.25
Esercizi sulle rappresentazioni
Rappresentare in MS e in CA2 su 8 bit i seguenti
numeri decimali:
+12
;35
+40
;1
;128
+271
+127
c 1992 - 96 - L.Farinetti, C.Fornaro, A.Lioy, M.Poncino (POLITO - DAI)
[R. 0 0001100]
[R. 1 0100011]
[R. 1 1011101]
[R. 0 0101000]
[R. 1 0000001]
[R. 1 1111111]
[R. Impossibile]
[R. 1 0000000]
[R. Impossibile]
[R. 0 1111111]
SN-AB.26
Somma in complemento a due
Dati due numeri X e Y in complemento a due su N
bit, la somma X + Y si calcola sommando aritmeticamente tutti i bit degli addendi, compreso quello di
segno.
L'eventuale carry oltre il bit di segno viene tralasciato.
Esempio: calcolare (;7) + (10) in complemento
a due su 5 bit
(;7) = 11001
(10) = 01010
10
10
10
10
1 1 0 0 1 +
0 1 0 1 0
1 0 0 0 1 1
Il carry nella posizione oltre il bit di segno non viene
considerato ed il risultato e 00011, ossia (3)
10
c 1992 - 96 - L.Farinetti, C.Fornaro, A.Lioy, M.Poncino (POLITO - DAI)
SN-AB.27
Dierenza in complemento a due
Ci si riconduce al caso della somma trasformando la
dierenza nella somma del primo numero con l'inverso del secondo.
Esempio: calcolare (;7) ; (4) in complemento a
due su 5 bit.
Si opera come se l'operazione fosse (;7) + (;4) :
(;7) = 11001
(;4) = 11100
10
10
10
10
10
10
1 1 0 0 1 +
1 1 1 0 0
1 1 0 1 0 1
Tralasciando il carry oltre il bit di segno il risultato
e 10101, ossia (;11)
10
c 1992 - 96 - L.Farinetti, C.Fornaro, A.Lioy, M.Poncino (POLITO - DAI)
SN-AB.28
Overow in complemento a due
Si puo vericare se contemporaneamente:
i due addendi hanno segno concorde
il segno del risultato e diverso dal segno dei due
addendi
s1
s1
s2
overow
se e solo se s2 6= s1
c 1992 - 96 - L.Farinetti, C.Fornaro, A.Lioy, M.Poncino (POLITO - DAI)
SN-AB.29
Esempio - overow
Calcolare (;12) + (;6) in complemento a due su
5 bit:
10
10
(;12) = 10100
(;6) = 11010
10
10
1 0 1 0 0 +
1 1 0 1 0
1 0 1 1 1 0
Si ha carry oltre il bit di segno, che viene ignorato. Il
bit di segno e diverso da quello degli addendi, cioe il
risultato della somma di due numeri negativi sarebbe
positivo, il che e impossibile (overow).
Verica: il risultato sarebbe (;18) , non rappresentabile in complemento a due su 5 bit.
10
c 1992 - 96 - L.Farinetti, C.Fornaro, A.Lioy, M.Poncino (POLITO - DAI)
SN-AB.30
Esercizi - somma e sottrazione in
complemento a due
Eseguire le seguenti operazioni in complemento a due
su 9 bit:
(131) ; (193)
10
10
[R. (;62) = 111000010]
10
(255) ; (256)
10
10
[R. (;1) = 111111111]
10
(;127) + (;130)
10
10
[R. (;257) overow]
10
(255) + (2) + (;127)
10
10
10
[R. (130) = 010000010]
10
(;256) + (2)
10
10
[R. (;254) = 100000010]
10
c 1992 - 96 - L.Farinetti, C.Fornaro, A.Lioy, M.Poncino (POLITO - DAI)
SN-AB.31
Numeri frazionari
Conversione da decimale a binario:
si convertono separatamente parte intera e parte
frazionaria
per la parte intera si segue la procedura di conversione gia vista
per la parte frazionaria si eettuano moltiplicazioni successive per 2 separando la parte intera
(0 o 1) da quella frazionaria cos ottenuta, nche:
{ il risultato della moltiplicazione e 1:000 : : :
{ oppure si raggiunge la precisione richiesta
Esempio: convertire in binario (6:25)
(6) = (110)
10
0.25 0.5 0.0
0 1
10
2
parte frazionaria
parte intera
6:25 = 110:01
.
10
2
c 1992 - 96 - L.Farinetti, C.Fornaro, A.Lioy, M.Poncino (POLITO - DAI)
SN-AB.32
Approssimazione dei numeri frazionari
Si noti che in generale ad un numero frazionario decimale con un numero limitato di cifre puo corrispondere un numero frazionario binario con un numero
innito di cifre. In tal caso ci si ferma quando si
raggiunge la precisione desiderata.
Esempio: convertire in binario (0:3) con la precisione di almeno
10
1
100
0.3 0.6 0.2 0.4 0.8 0.6 0.2
0 1 0 0 1 1 0
" " " " " " "
1
21
1
22
1
23
1
24
1
25
1
26
1
27
(0:3) = 0:0100110 : : :
10
L'errore e minore di
1
100
perche 7 =
1
2
c 1992 - 96 - L.Farinetti, C.Fornaro, A.Lioy, M.Poncino (POLITO - DAI)
1
128
< .
1
100
SN-AB.33
Esercizi - numeri frazionari
Convertire in binario i seguenti numeri
(0:625)
10
(0:03125)
[R. 0:101 ]
2
10
(0:828125)
[R. 0:00001 ]
2
10
[R. 0:110101 ]
2
Calcolare a quale numero decimale corrispondono i
seguenti numeri binari frazionari:
0:1101001
2
1011:0101
[R. (0:8203125) ]
2
11:10011
10
[R. (11:3125) ]
10
2
[R. (3:59375) ]
10
c 1992 - 96 - L.Farinetti, C.Fornaro, A.Lioy, M.Poncino (POLITO - DAI)
SN-AB.34
Rappresentazione in oating-point
Utilizzata per rappresentare numeri frazionari nella
notazione esponenziale:
numero = (mantissa) 2esponente
Il formato piu utilizzato e quello IEEE P754, rappresentato su 32 bit nel seguente modo:
S
8 bit
esponente
23 bit
mantissa (modulo)
L'esponente e rappresentato come numero senza segno su 8 bit in eccesso 127, cioe i valori da -126 a
+127 sono messi in corrispondenza con i valori da 0
a 255, per non dovere gestire anche il segno dell'esponente.
c 1992 - 96 - L.Farinetti, C.Fornaro, A.Lioy, M.Poncino (POLITO - DAI)
SN-AB.35
Floating-point: mantissa
La mantissa e codicata in modulo e segno su 24
bit,
la mantissa e sempre normalizzata nella forma
1:XXXXX
si rappresenta solo la parte frazionaria nei 23 bit
meno signicativi
il peso del MSB del modulo e 2;
il segno e dato dal MSB dei 32 bit
1
La rappresentazione di un numero e quindi nella forma
numero = 1:XXXXX 2 Y Y Y Y 2
(
c 1992 - 96 - L.Farinetti, C.Fornaro, A.Lioy, M.Poncino (POLITO - DAI)
)
SN-AB.36
Conversione decimale ! IEEE P754
Per trasformare un numero decimale N nella sua rappresentazione in oating-point, si deve
trasformarlo in binario
trasformarlo nella forma normalizzata
1:XXXXX 2 Y Y Y Y 2
il segno e 0 per i numeri positivi, 1 per i negativi
l'esponente e pari a 127+ n, dove n e il numero di
(
)
posizioni di cui e stato spostato il punto decimale
dalla forma binaria a quella normalizzata
la parte frazionaria della mantissa normalizzata
(XXXXX ) si memorizza nei 23 bit meno signicativi
c 1992 - 96 - L.Farinetti, C.Fornaro, A.Lioy, M.Poncino (POLITO - DAI)
SN-AB.37
Esempio - oating-point
Convertire in formato oating-point IEEE P754 il
numero 13:25
10
il numero e positivo, per cui il segno e 0
il numero convertito in binario puro e :
1101:01
spostando il punto decimale di 3 posizioni, il numero si normalizza in
1:10101 2
l'esponente in eccesso 127 vale:
127 + 3 = 130 = 10000010
2
2
3
2
La rappresentazione richiesta e:
0 10000010 10101000000000000000000
c 1992 - 96 - L.Farinetti, C.Fornaro, A.Lioy, M.Poncino (POLITO - DAI)
SN-AB.38
Conversione IEEE P754 ! decimale
L'interpretazione di un numero e piuttosto complicata: chiamando s il segno, e l'esponente, ed m la
mantissa, si possono avere i seguenti casi:
e=0, m=0: il valore e (;1)s (0), cioe +0 o -0
e=0, m6=0: il numero e nella forma non norma-
lizata
0 < e < 255: il numero e nella forma
(;1)s 2 e; (1:m)
e=255, m=0: il valore e (;1)s 1, cioe un numero
innitamente grande o piccolo (+1 o ;1)
e=255, m6=0: non e un numero valido (detto
NAN, Not A Number); puo essere usato per codicare informazioni di errore
(
127)
c 1992 - 96 - L.Farinetti, C.Fornaro, A.Lioy, M.Poncino (POLITO - DAI)
SN-AB.39
Esercizi - codica IEEE P754
Rappresentare in formato IEEE P754 i seguenti numeri
5:0
10
;9:25
[R. 0 10000001 0100 : : : 0]
10
12:8125
[R. 1 10000010 0010100 : : : 0]
10
[R. 0 10000010 100110100 : : : 0]
Dati i seguenti numeri in formato IEEE P754, dire
a quale numero decimale corrispondono:
0 10000001 010010 : : : 0
1 10001101 01110 : : : 0
0 01111101 01010 : : : 0
c 1992 - 96 - L.Farinetti, C.Fornaro, A.Lioy, M.Poncino (POLITO - DAI)
[R. 5.125]
[R. 23552.0]
[R. 0.328125]
SN-AB.40
Codici BCD
E' una codica per rappresentare numeri decimali in
binario (Binary Coded Decimal).
Il numero decimale viene suddiviso nelle cifre decimali che lo compongono, e ciascuna di queste convertita in binario puro secondo la corripondenza:
cifra
0
1
2
3
4
5
6
7
8
9
codice
0000
0001
0010
0011
0100
0101
0110
0111
1000
1001
c 1992 - 96 - L.Farinetti, C.Fornaro, A.Lioy, M.Poncino (POLITO - DAI)
SN-AB.41
Esempi - codici BCD
Esempio: convertire il numero 1592 in codice BCD.
1
5
#
9
#
2
#
#
0001 0101 1001 0010
Quindi 1592 = 0001010110010010BCD .
10
Esempio: ricavare il numero decimale corrispondente
al numero 01011000000001000111BCD
0101 1000 0000 0100 0111
#
5
#
8
#
0
#
4
#
7
Quindi 01011000000001000111BCD = 58047 .
10
c 1992 - 96 - L.Farinetti, C.Fornaro, A.Lioy, M.Poncino (POLITO - DAI)
SN-AB.42
Esercizi - conversione binaro $ BCD
Convertire i seguenti numeri binari in BCD:
1000 1001 0011 0111
[R. 8937]
100 1000 0010 1001
[R. 4829]
1 0010 0011 0010 1001 0001
[R. 123291]
10 1001 0101 0110 0101
[R. 29565]
Convertire i seguenti numeri BCD in binario:
4171
6153
4261
10478
[R. 100 0001 0111 0001]
[R. 110 0001 0101 0011]
[R. 100 0010 0110 0001]
[R. 1 0000 0100 0111 1000]
c 1992 - 96 - L.Farinetti, C.Fornaro, A.Lioy, M.Poncino (POLITO - DAI)
SN-AB.43
Codica dell'informazione non numerica
I calcolatori possono intrinsecamente trattare solo
informazioni binarie. Per trattare numeri relativi
e frazionari abbiamo adottato particolari codiche
(modulo e segno, complemento a due, oating-point).
Piu in generale con i numeri binari posso rappresentare insiemi enumerabili di oggetti, stabilendo una
corrispondenza biunivoca tra oggetti e numeri (codica).
c 1992 - 96 - L.Farinetti, C.Fornaro, A.Lioy, M.Poncino (POLITO - DAI)
SN-AB.44
Codica dell'informazione non numerica
Per rappresentare i caratteri alfabetici esistono alcune codiche standard: ad esempio il codice ASCII (il
piu diuso) codica su 7 cifre binarie tutti i caratteri
alfabetici piu alcuni speciali.
000
010
020
030
040
050
060
070
100
110
120
130
140
150
160
170
nul
bs
dle
can
sp
(
0
8
@
H
P
X
`
h
p
x
001
011
021
031
041
051
061
071
101
111
121
131
141
151
161
171
soh
ht
dc1
em
!
)
1
9
A
I
Q
Y
a
i
q
y
002
012
022
032
042
052
062
072
102
112
122
132
142
152
162
172
stx
nl
dc2
sub
"
*
2
:
B
J
R
Z
b
j
r
z
Codice ASCII (ottale)
003 etx 004 eot
013 vt 014 np
023 dc3 024 dc4
033 esc 034 fs
043 # 044 $
053 + 054 ,
063 3 064 4
073 ; 074 <
103 C 104 D
113 K 114 L
123 S 124 T
133 [ 134 \
143 c 144 d
153 k 154 l
163 s 164 t
173 f 174 &
005
015
025
035
045
055
065
075
105
115
125
135
145
155
165
175
c 1992 - 96 - L.Farinetti, C.Fornaro, A.Lioy, M.Poncino (POLITO - DAI)
enq
cr
nak
gs
%
5
=
E
M
U
]
e
m
u
g
006
016
026
036
046
056
066
076
106
116
126
136
146
156
166
176
ack
so
syn
rs
&
.
6
>
F
N
V
^
f
n
v
~
007
017
027
037
047
057
067
077
107
117
127
137
147
157
167
177
bel
si
etb
us
'
/
7
?
G
O
W
g
o
w
del
SN-AB.45
Codiche
Un codice deve permettere di risalire dalla codica
al simbolo rappresentato: per questo motivo, una
stringa binaria su un certo numero di bit ha piu interpretazioni, a seconda della codica che si considera.
Ad esempio, la stringa binaria 1101010 rappresenta:
il numero 106 in binario puro
il numero -42 in modulo e segno
il numero -22 in complemento a due
il carattere 'j' nella codica ASCII
c 1992 - 96 - L.Farinetti, C.Fornaro, A.Lioy, M.Poncino (POLITO - DAI)
SN-AB.46
Algebra Booleana
Opera su variabili che possono assumere soltanto i
due valori 0 e 1 (variabili Booleane).
Operazioni base:
A
0
0
1
1
AND
B AB
0 0
1 0
0 0
1 1
A
0
0
1
1
OR
B A+B
0 0
1 1
0 1
1 1
NOT
A A
0 1
1 0
c 1992 - 96 - L.Farinetti, C.Fornaro, A.Lioy, M.Poncino (POLITO - DAI)
SN-AB.47
Algebra Booleana
Operazioni estese:
A
0
0
1
1
A
0
0
1
1
NAND
B AB
0 1
1 1
0 1
1 0
EXOR
B AB
0 0
1 1
0 1
1 0
A
0
0
1
1
A
0
0
1
1
NOR
B A+B
0 1
1 0
0 0
1 0
EXNOR
B AB
0 1
1 0
0 0
1 1
N.B. E possibile rappresentare qualunque espressione utilizzando esclusivamente l'operazione NAND oppure l'operazione NOR.
c 1992 - 96 - L.Farinetti, C.Fornaro, A.Lioy, M.Poncino (POLITO - DAI)
SN-AB.48
Funzioni booleane
Funzioni di variabili booleane che assumono soltanto
i valori 0 e 1.
Denite tramite tabelle di verita, nelle quali si indica il valore assunto dalla funzione per ogni possibile
combinazione delle variabili.
Esempio: F (x ; x ) denita da
1
2
x
0
0
1
1
1
x
0
1
0
1
F
0
1
0
1
2
Normalmente rappresentate nella forma di espressioni booleane, in cui le variabili booleane sono combinate tramite i quattro operatori fondamentali
Esempio:
F (x ; x ) = x x + x
1
2
1
2
c 1992 - 96 - L.Farinetti, C.Fornaro, A.Lioy, M.Poncino (POLITO - DAI)
1
SN-AB.49
Costruzione di tabelle di verita
Per costruire la tabella della verita di un'espressione
booleana:
semplicare l'espressione mediante teoremi del-
l'algebra booleana, se possibile
calcolare i termini parziali della funzione riducendoli alle operazioni fondamentali
Esempio: calcolare la tabella di verita della funzione
F (a; b; c) = a b + c
a
0
0
0
0
1
1
1
1
b
0
0
1
1
0
0
1
1
c
0
1
0
1
0
1
0
1
ab ab+c
0
0
0
1
0
0
0
1
0
0
0
1
1
1
1
1
c 1992 - 96 - L.Farinetti, C.Fornaro, A.Lioy, M.Poncino (POLITO - DAI)
SN-AB.50
Circuiti logici
Una funzione booleana puo anche essere rappresentata da un circuito logico, cioe da un insieme di porte
logiche connesse fra loro.
Le porte logiche elementari corrispondono alle operazioni base dell'algebra booleana:
BUF
A
A
B
A
B
A
B
INV
A
QQ
AND
AB
OR
A+B
EXOR
AB
A
A
B
A
B
A
B
QQ
e
e
e
A
NAND
NOR
e
AB
A+B
EXNOR
c 1992 - 96 - L.Farinetti, C.Fornaro, A.Lioy, M.Poncino (POLITO - DAI)
AB
SN-AB.51
Circuiti logici - esempio
Disegnare il circuito logico che rappresenta le funzioni:
F (a; b; c) = a b + c
a
b
c
F =ab+c
F (a; b; c) = a b + b c
a
b
c
e
e r
e
J
J
F =ab+bc
c 1992 - 96 - L.Farinetti, C.Fornaro, A.Lioy, M.Poncino (POLITO - DAI)
SN-AB.52
Teoremi dell'algebra booleana
X
X
X
X
X
X
X
0=0
1=
=
X
=0
Y
=
Y
+X
X
X
+
X
X
Y
:::
+
Y
X
+0 =
X
+
X
=
X
+
X
=1
X
+
Y
=
:::Z
X
+
Y
+::: +
Z)
(X +
X
Y
X
+1 = 1
X
X
X
X
=
Z
Z
=
Y
=
X
Y
=
X
+X
Y
X
X
+Y +
(
Y
+
X
+
=
Y
X
X
Y
(
X
(
X
(X +
Y
)
X
X
Y
+
(
X
X
Z
+
Z)
+
Y
)=
X
+
Y
)=
X
)
(
c 1992 - 96 - L.Farinetti, C.Fornaro, A.Lioy, M.Poncino (POLITO - DAI)
X
=
X
=
X
Y
+
:::Z
Y
Y
+Y) =
X
SN-AB.53
Z
Semplicazione di espressioni booleane
Esempi: semplicare le seguenti espressioni:
f (x; y; z ) = xyz + xyz + yz
= xy(z + z ) + yz
= xy + yz
= y (x + z )
f (x; y; z ) =
=
=
=
x + y + xy + (x + y)xy
x + y + y + (x + y)xy
x + 1 + (x + y)xy
1
f (x; y; z ) =
=
=
=
(x + y )xy + z
xxy + yxy + z
0y+0x+z
z)
c 1992 - 96 - L.Farinetti, C.Fornaro, A.Lioy, M.Poncino (POLITO - DAI)
SN-AB.54
Esercizi - tabelle di verita
Determinare le tabelle di verita delle seguenti funzioni:
f = a(a + b)
[R. f (a; b) a]
1
1
f = (ab + b)c
2
[R. a
0
0
0
0
1
1
1
1
b
0
0
1
1
0
0
1
1
c
0
1
0
1
0
1
0
1
ab
0
0
0
0
0
0
1
1
b ab + b
1 1
1 1
0 0
0 0
1 1
1 1
0 1
0 1
c 1992 - 96 - L.Farinetti, C.Fornaro, A.Lioy, M.Poncino (POLITO - DAI)
c
1
0
1
0
1
0
1
0
f ]
1
0
0
0
1
0
1
0
2
SN-AB.55
Esercizi - tabelle di verita
Determinare le tabelle di verita delle seguenti
zioni:
f (a; b; c) = abc + bc + ac
[R. a b c abc bc ac
0 0 0 1 0 0
0 0 1 0 0 0
0 1 0 0 0 0
0 1 1 0 1 0
1 0 0 0 0 0
1 0 1 0 0 1
1 1 0 0 0 0
1 1 1 0 1 1
fun-
3
c 1992 - 96 - L.Farinetti, C.Fornaro, A.Lioy, M.Poncino (POLITO - DAI)
f ]
1
0
0
1
0
1
0
1
3
SN-AB.56
Esercizi - semplicazione di espressioni
Semplicare le seguenti espressioni:
acd + bcd + acd + ab + bd
[R. ab + d]
(a + c)abc
abc + bcd + bc + bce + bcf
[R. 0]
[R. ab + bc + cd + bce]
(a + c)(a + b + d)(b + c + d)
[R. ab + ac + bc + cd]
abc + cdf + de + ef + bd
[R. b + c + d + e + f ]
c 1992 - 96 - L.Farinetti, C.Fornaro, A.Lioy, M.Poncino (POLITO - DAI)
SN-AB.57
Esercizi - verica dell'equivalenza di
espressioni booleane
E noto che in aritmetica vale la proprieta distributiva
a(b + c) = ab + ac
ma non
a + (bc) = (a + b)(a + c)
Stabilire se le precedenti proprieta sono o non sono
valide nell'algebra di Boole.
c 1992 - 96 - L.Farinetti, C.Fornaro, A.Lioy, M.Poncino (POLITO - DAI)
SN-AB.58
Esercizi - funzioni booleane
Per essere ammessi all'orale di un esame universitario si devono aver superato almeno due scritti di
esonero su tre.
Indicando simbolicamente con le variabili Booleane
A, B e C il superamento del primo, secondo e terzo
scritto
costruire la tavola di verita della funzione
f (A; B; C ) che rappresenta l'ammissione all'orale
scrivere ed eventualmente semplicare f
[R. BC + AC + AB ]
c 1992 - 96 - L.Farinetti, C.Fornaro, A.Lioy, M.Poncino (POLITO - DAI)
SN-AB.59
Esercizi - funzioni booleane
Un impianto chimico e dotato di un sistema di allarme automatico che segnala le situazioni anormali. L'allarme suona quando risulta soddisfatta la seguente condizione:
la temperatura della caldaia e maggiore di 170C
e la pressione e superiore a 2 atmosfere, oppure non auisce combustibile e la temperatura
della caldaia e inferiore a 170C.
Costruire una tabella di verita che indichi quando
l'allarme e in funzione e ricavare la funzione corrispondente.
[R. xy + zx]
c 1992 - 96 - L.Farinetti, C.Fornaro, A.Lioy, M.Poncino (POLITO - DAI)
SN-AB.60
Esercizi - funzioni booleane
Una cassaforte ha quattro lucchetti, a, b, c, d, che
devono essere tutti contemporaneamente aperti afnche la cassaforte possa essere aperta.
Le chiavi sono distribuite fra tre persone, X , Y e Z ,
come segue:
X possiede le chiavi a e d;
Y possiede le chiavi b e d;
Z possiede le chiavi a e c.
Le variabili X , Y e Z siano uguali a 1 se la persona corrispondente e presente con le proprie chiavi,
altrimenti siano uguali a 0.
Costruire la tavola di verita della funzione f (X; Y; Z )
che e uguale a 1 se e solo se la cassaforte e aperta, e
in seguito scrivere f .
[R. Y Z ]
c 1992 - 96 - L.Farinetti, C.Fornaro, A.Lioy, M.Poncino (POLITO - DAI)
SN-AB.61
Esercizi - circuiti logici
Disegnare i circuiti logici che rappresentano le seguenti funzioni:
f (a; b; c) = (a b + b) c
1
f (a; b; c) = a b c + b c + a c
2
f (a; b; c) = (a b) c
3
f (a; b; c; d) = (a b + c) (d + a)
4
f (a; b; c) = (a b) (b c)
5
f (a; b; c; d) = ((a + b) cd) (ac + b)
6
c 1992 - 96 - L.Farinetti, C.Fornaro, A.Lioy, M.Poncino (POLITO - DAI)
SN-AB.62
Esercizi riassuntivi
1. Trovare le basi per la quale sono valide le seguenti
operazioni:
210 = 12 p171 = 13
12
[R. 4, 8]
2. Si eseguano le seguenti operazioni rappresentando gli operandi in complemento a due su 12 bit:
(a) (181) ; (1455)
(b) (747) + (1300)
Si esprimano poi i risultati delle operazioni precedenti nel sistema esadecimale.
[R.(a) 101100000110 = (;1274) = B 06
(b) 011111111111 = (2047) = 7FF ]
3. Qual e il numero minimo di cifre binarie necessarie a rappresentare in complemento a due il numero ;87:46875?
[R. 13]
10
10
10
10
10
10
c 1992 - 96 - L.Farinetti, C.Fornaro, A.Lioy, M.Poncino (POLITO - DAI)
16
16
SN-AB.63
4. Si eseguano le seguenti operazioni rappresentando gli operandi in complemento a due su 11 bit:
(a) (9:0625) ; (12:375)
(b) (14:750) + (17:375)
[R.(a) 1111100:1011 = ;3:3125
(b) 0010000:001 = +32:125]
5. Eseguendo il DUMP nel formato esadecimale di
un le contenente numeri nella rappresentazione
oating-point standard, si leggono i seguenti numeri:
41440000 3E 800000
Di quali numeri si tratta?
[R. +12.25 +0.25]
6. Si consideri un codice Gray a 16 eventi: determinare le corrispondenze tra le congurazioni Gray
e le congurazioni in binario puro esprimendole
nel sistema ottale.
Esempio: (17)Gray = (12)binario.
10
10
10
10
c 1992 - 96 - L.Farinetti, C.Fornaro, A.Lioy, M.Poncino (POLITO - DAI)
SN-AB.64
7. Rappresentare in complemento a due il numero ;64:3925 con una precisione di ; indicare
qual e il numero minimo di cifre binarie occorrenti e scrivere il numero decimale corrispondente a
quello binario approssimato.
[R. 1 0111111.1001101111
18 cifre ( 10 = )
-63.3916]
8. Applicando i teoremi dell'algebra booleana, minimizzare l'espressione seguente:
x(w + y) + y(z + y)
[R. x + y + z ]
9. Data la funzione booleana f (x; y; z; k) avente espressione
kx z (x + xk + x + xy)
scrivere l'espressione di f (x; y; z; k) e semplicarla poi tramite i teoremi fondamentali.
[R. f = k x z ]
1
1000
1
2
c 1992 - 96 - L.Farinetti, C.Fornaro, A.Lioy, M.Poncino (POLITO - DAI)
1
1024
SN-AB.65
10. Data la funzione booleana f (x; y; z; k) avente espressione
xy + x + y + z + xzk + xyz + x + z + k + xyz
ricavare la tabella di verita
semplicare l'espressione utilizzando i teoremi
fondamentali e ricavare le tabelle di verita di
quest'ultima.
[R. xz + y]
11. Disegnare il circuito corrispondente alla funzione
booleana f (x; y; z; w) avente espressione
(x y + y z y z w ) w
c 1992 - 96 - L.Farinetti, C.Fornaro, A.Lioy, M.Poncino (POLITO - DAI)
SN-AB.66