Informatica

CODIFICA BINARIA
DELL’INFORMAZIONE
ARITMETICA DEL CALCOLATORE
ALGEBRA DI BOOLE E CENNI DI
LOGICA

1
Elaborazione
dell’informazione
CHE COS’È L’INFORMAZIONE?
CHE COSA VUOL DIRE ELABORARLA?
L’informazione
Messaggio che apporta conoscenza:
 C’è una situazione iniziale, di ignoranza o incertezza
 C’è un evento fisico di qualche tipo
 C’è una situazione finale, in cui la conoscenza è superiore
a quella iniziale
Es: la lettura di questa slide
 All’inizio non sapevate che cosa fosse l’informazione
 Alcuni (molti) fotoni hanno colpito la vostra retina in un
certo modo
 Ora sapete che cosa è l’informazione!
L’informazione
Esempi di informazione:
 Un suono può apportare informazione:
 Può portare una notizia
 Può apportare conoscenza sull’ambiente circostante (il suono del
clacson di una macchina che sta arrivando)
 L’informazione può anche semplicemente essere il fatto che si è
mossa dell’aria

Lo stesso messaggio può portare quantità di

informazione diverse a seconda dello stato di chi lo
riceve (ognuno lo interpreta, lo elabora)
Elaborazione
Che cosa si può fare, con questa informazione?

 La notizia: trascriverla, ri-trasmetterla -- eventualmente

dopo averla modificata, tradotta, sintetizzata

 Il segnale: registrarlo, usarlo per reagire (fare un salto

all’indietro), misurarne l’intensità

 Il suono: modificarlo, registrarlo, utilizzarlo per creare

messaggi visivi, per controllare dei proiettori luminosi, …
Elaborazione automatica
I calcolatori elettronici sono in grado di compiere
molto bene alcune di queste elaborazioni di
informazione…
Purché:
 L’informazione sia rappresentata con una codifica
opportuna (digitale, cioè codificata numericamente)
• In modo molto informale noi considereremo informazione ciò che
viene trasmesso da un messaggio rappresentabile con un numero
(intero)

 Le elaborazioni da compiere siano descritte in modo

algoritmico
 Esempi
Un diario contiene di certo
dell’informazione.
Si tratta di informazione che può
essere manipolata da un
calcolatore?
Sì:
a) possiamo assegnare un numero di due cifre ad ogni lettera dell’alfabeto
(‘a’=11,’b’=12, etc), compresi gli spazi
b) chiamiamo la coppia di cifre corrispondente ad una certa lettera codice
della lettera (per esempio: 11 è il codice per la ‘a’)
c) possiamo trascrivere il diario utilizzando i nostri codici, uno dietro l’altro

 Otteniamo un numero intero, molto grande, che codifica il diario

 L’informazione contenuta nella codifica è sufficiente a ricostruire “quello

che c’è scritto” nel diario
Cosa ce ne facciamo,
dell’informazione?
Che cosa può fare un calcolatore con il numero che
rappresenta il diario?

 può memorizzarlo
 può eventualmente trasmetterlo
 può misurare la frequenza d’uso di alcune parole
 può controllare che le parole siano scritte in italiano
corretto

 può cercare di capire la psicologia dello scrivente?

Tutta l’informazione?
Qualcuno potrebbe obiettare che nel diario c’è molto
di più di quello che c’è scritto…
Per esempio: la grafia (il modo con cui chi ha scritto
quello che ha scritto) potrebbe contenere
dell’informazione
Possiamo tradurre l’informazione sulla grafia in un
numero?
Codificare un’immagine
 Ad ogni punto facciamo corrispondere
un numero che ne codifica il livello di
grigio
 Mettendo di seguito tutte le cifre di tali
numeri in un ordine prestabilito,
l’immagine è codificata da un solo
grande numero
11
 E il suono?
Anche tutta l’informazione contenuta in un brano musicale la
posso trasformare in un numero?
Ma che cos’è, in questo caso, l’ “informazione” ?
◦ la conoscenza che serve per “riprodurre” acusticamente il brano (cioè per
riprodurne il suono)

• La percezione del suono è fisicamente causata dalla variazione, nel tempo, della
pressione dell’aria in prossimità del timpano.
• La pressione si può misurare (cioè convertire in un numero) a intervalli di tempo
piccoli (campionamento), i valori sono numeri..
• …anche un brano musicale si può rappresentare con un numero intero
Insomma…
…molta dell’informazione con cui abbiamo a che fare
e che può interessarci elaborare…
...può essere rappresentata con un numero intero
Cosa non può esserlo?
◦ Per Pitagora, niente (tutto è numero)
◦ Per il pancomputazionalismo, nemmeno (tutta la realtà
fisica sarebbe rappresentabile digitalmente)
In questo corso…
Non tratteremo il problema di acquisire l’informazione che
vogliamo elaborare
 Immagineremo di averla già disponibile, in forma numerica

Non tratteremo il problema di comunicare i risultati

dell’elaborazione in modo efficacemente fruibile
 Ci accontenteremo di «visualizzarli da qualche parte»

Impareremo, invece, come far compiere al calcolatore le

elaborazioni che desideriamo sulla nostra informazione
codificata, per trasformarla:
 Impareremo, cioè, a programmare il calcolatore
Calcolo e ambiente

input output

172312 Calcolatore 514232

Rappresentare l'informazione:
associare significati e simboli
Significati Simboli
Codifica

sun
Interpretazione
soleil
güneş

Codifiche
diverse

16
Rappresentare l'informazione:
associare significati e simboli

penna
biro

penna
Codifica
ridondante
Codifica
(l’interpretazione
è univoca) ambigua
(l’interpretazione
non è univoca)

17
Codifica dell’informazione
Rappresentare (codificare) le informazioni
con un insieme limitato di simboli (detto alfabeto A)
in modo non ambiguo
Esempio: numeri interi
Codifica decimale (dec, in base dieci)
 A = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 }, |A| = dieci
 “sette” : 7dec
 “ventitre” : 23dec
 “centotrentotto” : 138dec
Notazione posizionale
 dalla cifra più significativa (a sinistra) a quella meno significativa (a destra)
 ogni cifra corrisponde a una diversa potenza di dieci

18
Numeri naturali
Notazione posizionale: permette di rappresentare un qualsiasi
numero naturale (intero non negativo) nel modo seguente:
la sequenza di cifre: cn-1 cn-2 … c1 c0
rappresenta in base B ≥ 2 il valore:
cn-1×Bn−1 + cn−2×Bn−2 + … + c1×B1 + c0×B0

dove: ci ∈ {0, 1, 2, …, B−1} per ogni 0 ≤ i ≤ n-1

La notazione decimale tradizionale è di tipo posizionale(con B=dieci)
(non ambigua, e non ridondante -- se si fissa a priori il num. di cifre)
Esistono notazioni non posizionali
 Ad esempio i numeri romani: II, IV, VI, X, XV, XX, VV (non ambigua, ridondante)

19
Numeri naturali in varie basi
Base generica: B
A= { ... }, con |A| = B, sequenze di n simboli (cifre)
 cn-1 ... c1 c0 = cn-1 x Bn-1 + … + c1 x B1 + c0 x B0
 Con n cifre rappresentiamo Bn numeri: da 0 a Bn-1
“ventinove” in varie basi
 B = otto A = {0,1,2,3,4,5,6,7} 29dec = 358
 B = cinque A = {0,1,2,3,4} 29dec = 1045
 B = tre A = {0,1,2} 29dec = 10023
 B = sedici A = {0,1,...,8,9,A,B,C,D,E,F} 29dec = 1D16
Codifiche notevoli
 Esadecimale (sedici), ottale (otto), binaria (due)

20
Codifica binaria
Usata dal calcolatore per tutte le informazioni
 B = due, A = { 0, 1 }
 BIT (crasi di “BInary digIT”):
 unità elementare di informazione
• Dispositivi che assumono due stati
• Ad esempio due valori di tensione elettrica VA e VB

Numeri binari naturali:

la sequenza di bit bi (cifre binarie):
bn-1 bn−2 … b0 con bi ∈ {0, 1}

rappresenta in base 2 il valore:

bn-1×2n −1 + bn−2×2n−2 + … + b0×20

21
Numeri binari naturali (bin)
Con n bit codifichiamo 2n numeri interi positivi: da 0 a 2n-1
Con 1 Byte (cioè una sequenza di 8 bit):
 00000000bin = 0dec
 00001000bin = 1 × 23 = 8dec
 00101011bin = 1 × 25 + 1 × 23 + 1 × 21 + 1 × 20 = 43dec
 11111111bin = Σn = 0,1,2,3,4,5,6,7 1 × 2n = 255dec
Conversione bin → dec e dec → bin
 bin→dec: 11101 = Σ b 2i = 24+23+22+20 = 29
bin i i dec
 dec→bin: metodo dei resti

22
Conversione dec → bin
Metodo dei resti: si calcolano i resti delle divisioni per due

In pratica basta: 19 : 2 = 9 → 1
1. Decidere se il numero è pari (resto 0) 9:2=4→1
oppure dispari (resto 1), e annotare il resto 4:2=2→0
2. Dimezzare il numero (trascurando il resto) 2:2=1→0
3. Ripartire dal punto 1. fino a quando si 1:2=0→1
ottiene 0 come risultato della divisione

Ecco un esempio,
per quanto modesto,
di algoritmo
si ottiene 0: fine
19dec=10011bin

23
Metodo dei resti
19 : 2 = 9 (1) 76 : 2 = 38 (0)
9 : 2 = 4 (1) 38 : 2 = 19 (0)
4 : 2 = 2 (0) 19 : 2 = 9 (1)
9 : 2 = 4 (1)
2 : 2 = 1 (0)
4 : 2 = 2 (0)
1 : 2 = 0 (1) 2 : 2 = 1 (0)
19dec = 10011bin 1 : 2 = 0 (1)
76dec = 1001100bin
Del resto 76 = 19x4 = 1001100
Per raddoppiare, in base due, si N.B. Il metodo funziona
aggiunge uno zero in coda, così come
con tutte le basi!
si fa in base dieci per decuplicare
2910=456=329=2711=2114=1029

24
Conversioni rapide bin → dec
In binario si definisce una notazione abbreviata, sulla falsariga
del sistema metrico-decimale:
ki = 210 = 1.024 ≈ 103 (kilo)
Mi = 220 = 1.048.576 ≈ 106 (Mega)
Gi = 230 = [Link] ≈ 109 (Giga)
Ti = 240 = [Link].776 ≈ 1012 (Tera)
È curioso (benché non sia casuale) come ki, Mi, Gi e Ti in base 2
abbiano valori molto prossimi ai corrispondenti simboli (k=103,
M=106, G=109, T=1012) del sistema metrico decimale, tipico
delle scienze fisiche e dell’ingegneria
L’errore risulta < 10 % (infatti la 2a cifra è sempre 0)

25
Ma allora…
È facile (e rapido) calcolare il valore decimale approssimato
delle potenze di 2, anche con esponente grande
Infatti basta:
 Tenere a mente l’elenco dei valori esatti delle prime dieci
potenze di 2 [20=1, 21=2, 22=4, 23=8, 24=16, 25=32, 26=64, 27=128,
28=256, 29=512]
 Scomporre in modo additivo l’esponente in contributi di
valore 10, 20, 30 o 40, “leggendoli” come successioni di
simboli K, M, G oppure T
Quanto vale (circa) 217 ?
Risposta: “128 mila” ( infatti 217 = 27+10 = 27 × 210 = 128 k )
in realtà, 217 vale un po’ di più (ma poco)
valore reale = 131.072 errore = 1−128.000/131.072 ≈ 2,3 %

26
Altri esempi
224 = 24+20 = 16 Mi, leggi “16 milioni”
235 = 25+30 = 32 Gi, leggi “32 miliardi”
248 = 28+40 = 256 Ti, leggi “256 trilioni”, o anche
= 28+10+30 = 256 Ki Gi, leggi “256 mila miliardi”
252 = 4 Ki Ti, leggi “4 mila trilioni”, o anche
= 4 Mi Gi, leggi “4 milioni di miliardi”
N.B.: l’approssimazione è sempre per difetto
 ma “regge” (err<10%) anche su valori molto grandi

27
Al contrario… (dec → bin)
Si osservi come 103 = 1000 ≈ 1024 = 210,
con errore = 1 − 1000/1024 = 2,3 %
Pertanto, preso un intero n, si ha:
10n = (103)n / 3 ≈ (210)n / 3 = 210 × n / 3

Quanto vale (circa) in base 2:

109 ? risposta: circa 210 × 9 / 3 = 230
con errore: 1 − 230/109 ≈ −7,3 % (approx. eccesso)

1010 ? risposta: circa 210 × 10 / 3 ≈ 233

con errore: 1 − 233/1010 ≈ 14,1 % (approx. difetto)

L’approssimazione è per eccesso o per difetto

28
Operazioni sui numeri binari
Dove sono memorizzati i numeri, in un calcolatore?
 Ad esempio in "registri" di memoria, cioè schiere di circuiti
(hardware) che contengono sequenze di bit
 Essendo hardware, contengono necessariamente un numero predefinito di
bit (ovviamente non di più, ma neanche di meno)
 Se il numero di bit è "cablato", un registro può contenere
numeri fino a un massimo prefissato
 Non possono esserci bit "vuoti" (la tensione è VA o VB)
Come si elaborano i numeri?
 Ad esempio le addizioni e le sottrazioni?

29
Aumento e riduzione dei bit in bin
Aumento dei bit
 Aggiungendo come prefisso in modo progressivo un bit 0 a
sinistra, il valore del numero non muta
4dec = 100bin = 0100bin = 00100bin = … 000000000100bin
5dec = 101bin = 0101bin = 00101bin = … 000000000101bin

Riduzione dei bit

 cancellando in modo progressivo un bit 0 a sinistra, il valore del
numero non muta, ma bisogna arrestarsi quando si trova un bit 1!
7dec = 00111bin = 0111bin = 111bin STOP !
2dec = 00010bin = 0010bin = 010bin = 10bin STOP !

30
Operazioni – Numeri binari naturali
Algoritmo di “addizione a propagazione dei riporti”
È l’algoritmo decimale elementare, adattato alla base 2

Pesi 7 6 5 4 3 2 1 0
Riporto 1 1 1
Addendo 1 0 1 0 0 1 1 0 1 + 77dec
Addendo 2 1 0 0 1 1 1 0 0 = 156dec

Somma 1 1 1 0 1 0 0 1 233dec

31

addizione naturale (a 8 bit)

 Operazioni – Numeri binari naturali
addizione tra numeri espressi con un numero
fissato a priori di cifre ( nell’esempio: 8 bit)

Pesi 1 7 6 5 4 3 2 1 0
Riporto 1 1 1 1 1
Riporto Addendo 1 0 1 1 1 1 1 0 1 + 125dec
“perduto”
Addendo 2 1 0 0 1 1 1 0 0 = 156dec
Somma 0 0 0 1 1 0 0 1 25dec !

overflow risultato errato!

overflow (o trabocco) significa che il valore del risultato non può

essere rappresentato con il numero di cifre a disposizione
32
Riporto e overflow (addizione naturale)
Si ha overflow quando il risultato corretto
dell’addizione eccede il potere di rappresentazione
dei bit a disposizione
 8 bit nell’esempio precedente
Nell’addizione tra numeri binari naturali si ha
overflow ogni volta che si genera un riporto
addizionando i bit della colonna più significativa
(riporto “perduto”)

33
Numeri interi in modulo e segno
Numeri interi (positivi e negativi) in modulo e segno (m&s)

 il primo bit a sinistra rappresenta il segno del numero (bit di

segno), i bit rimanenti rappresentano il valore
 0 per il segno positivo
 1 per il segno negativo

Esempi con n = 9 (un bit per il segno + 8 bit per il valore)

 000000000m&s = + 0dec
 000001000m&s = + 1 × 23 = 8dec
 100001000m&s = − 1 × 23 = −8dec
 … e così via …

34
Osservazioni sul m&s
Il bit di segno è applicato al numero rappresentato, ma
non fa propriamente parte del numero in quanto tale
 il bit di segno non ha significato numerico
Distaccando il bit di segno, i bit rimanenti
rappresentano il valore assoluto del numero
 che è intrinsecamente positivo

È una buona idea ma… possiamo fare meglio!

35
Il complemento a 2 (C2)
Numeri interi in complemento a 2:
il C2 è un sistema binario, in cui alla codifica del valore
assoluto dell’intero in binario naturale si aggiunge un bit
nella posizione più a sinistra (quella “più significativa”) e si
intende il peso del bit più significativo come negativo,
mentre i restanti bit della codifica in binario naturale
continuano ad avere peso positivo
La sequenza di n bit:
bn−1 bn−2 … b0
interpretata in C2 codifica il valore decimale ottenuto come:
−bn-1×2n−1 + bn−2×2n−2 + … + b0×20
Il bit più a sinistra è ancora chiamato bit di segno

36
Numeri a tre bit in C2
000C2 = –0×22 + 0×21 + 0×20 = 0dec
001C2 = –0×22 + 0×21 + 1×20 = 1dec
010C2 = –0×22 + 1×21 + 0×20 = 2dec
011C2 = –0×22 + 1×21 + 1×20 = 2+1 = 3dec
100C2 = –1×22 + 0×21 + 0×20 = −4dec
101C2 = –1×22 + 0×21 + 1×20 = −4+1 = −3dec
110C2 = –1×22 + 1×21 + 0×20 = −4+2 = −2dec
111C2 = –1×22 + 1×21 + 1×20 = −4+2+1 = −1dec

N.B.: in base al bit di segno lo zero è considerato positivo

37
Invertire un numero in C2
L’inverso additivo (o opposto) di un numero N codificato in C2 si
ottiene:
 Invertendo (negando) ogni bit del numero
 Sommando 1 alla posizione meno significativa

Esempio:
 01011C2 = 1×23+1×21+1×20 = 8+2+1 = 11dec
 10100 + 1 = 10101C2 = −1×24+1×22 +1×20 = −16+4+1 = −11dec

Si provi a invertire 11011C2 = −5dec

Si verifichi che con due applicazioni dell’algoritmo si riottiene il
numero iniziale [ –(–N) = N ] e che lo zero in C2 è (correttamente)
opposto di se stesso [ –0 = 0 ]

38
Conversione dec → C2
Se Ddec ≥ 0:
 Converti Ddec in binario naturale.
 Premetti il bit 0 alla sequenza di bit ottenuta.
 Esempio: 154dec ⇒ 10011010bin ⇒ 010011010C2
Se Ddec < 0:
 Trascura il segno e converti Ddec in binario naturale
 Premetti il bit 0 alla sequenza di bit ottenuta
 Calcola l’opposto del numero così ottenuto, secondo la
procedura di inversione in C2
 Esempio: −154dec ⇒ 154dec ⇒ 10011010bin ⇒
⇒ 010011010c2 questo è +154dec ⇒ calcoliamo l’opposto
ottenendo: 101100101 + 1 ⇒ 101100110C2
Occorrono 9 bit sia per 154dec sia per −154dec

39
Aumento e riduzione dei bit in C2
Estensione del segno:
 replicando in modo progressivo il bit di segno a sinistra, il
valore del numero non muta
4 = 0100 = 00100 = 00000100 = … (indefinitamente)
−5 = 1011 = 11011 = 11111011 = …(indefinitamente)
Contrazione del segno:
 cancellando in modo progressivo il bit di segno a sinistra, il
valore del numero non muta
 purché il bit di segno non abbia a invertirsi !
7 = 000111 = 00111 = 0111 STOP! (111 è < 0)
−3 = 111101 = 11101 = 1101 = 101 STOP! (01 è > 0)

40
Osservazioni sul C2
Il segno è incorporato nel numero rappresentato in C2, non è
semplicemente applicato (come in m&s)
Il bit più significativo rivela il segno:
 0 per numero positivo,
 1 per numero negativo (il numero zero è considerato positivo), ma…
NON si può distaccare il bit più significativo e dire che i bit
rimanenti rappresentano il valore assoluto del numero
 questo è ancora vero, però, se il numero è positivo !!!

41
Interi relativi in m&s e in C2
Se usiamo 1 Byte: da –128 a 127

dec. 127 m&s 01111111 C2 01111111

126 01111110 01111110
… … …
2 00000010 00000010
1 00000001 00000001
+0 00000000 00000000
-0 10000000 -
-1 10000001 11111111
-2 10000010 11111110
… … …
-126 11111110 10000010
-127 11111111 10000001
-128 - 10000000

42
Intervalli di rappresentazione
Binario naturale a n ≥ 1 bit: [0, 2n)
Modulo e segno a n ≥ 2 bit: (−2n−1, 2n−1)
C2 a n ≥ 2 bit: [−2n−1, 2n−1)
In modulo e segno, il numero zero ha due
rappresentazioni equivalenti (00..0, 10..0)
L’intervallo del C2 è asimmetrico (−2n−1 è
compreso, 2n−1 è escluso); poco male …

43
Lunghezza della rappresentazione
Ґlog2 valore˥ = Numero di bit per rappresentare il valore
(in binario naturale)
 ARROTONDAMENTO ALL’INTERO SUPERIORE

Esempio: Ґlog2 74˥ =Ґ6,....˥ = 7 bit, cifre in base B=2

In generale: ҐlogB valore˥ = Numero di cifre per
rappresentare il valore in
base B
E per il C2?
... 1+ Ґlog2 |valore|˥ in tutti i casi
TRANNE QUANDO il valore è una potenza di 2 positiva (…il «1+…» diventa «2+…»)
per esempio: num. min. di bit per rappresentare 16 in c2: 2+log2(16)=6, infatti: 010000

44
Operazioni – Numeri in C2
addizione algebrica (a 8 bit)
L’algoritmo è identico a quello naturale
(come se il primo bit non avesse peso negativo)

Pesi 7 6 5 4 3 2 1 0
Riporto 1 1 1
Addendo 1 0 1 0 0 1 1 0 1 + 77dec
Addendo 2 1 0 0 1 1 1 0 0 = −100dec 45

Somma 1 1 1 0 1 0 0 1 −23dec
 Operazioni – Numeri in C2
addizione algebrica con overflow
Pesi 7 6 5 4 3 2 1 0
Riporto 1 1 1 1
nessun
riporto Addendo 1 0 1 0 0 1 1 0 1 + 77dec
“perduto”
Addendo 2 0 1 0 1 1 1 0 0 = 92dec

Somma 1 0 1 0 1 0 0 1 −87dec !

risultato errato!
Overflow:
risultato negativo!

ancora overflow
46
Riporto e overflow in C2
(addizione algebrica)
Si ha overflow quando il risultato corretto eccede il potere
di rappresentazione dei bit a disposizione
 La definizione di overflow non cambia!
Si può avere overflow senza “riporto perduto”
 Capita quando da due addendi positivi otteniamo un risultato
negativo, come nell’esempio precedente
Si può avere un “riporto perduto” senza overflow
 Può essere un innocuo effetto collaterale
 Capita quando due addendi discordi generano un risultato
positivo (si provi a sommare +12 e -7)

47
Rilevare l’overflow in C2
Se gli addendi sono tra loro discordi (di segno diverso)
non si verifica mai
Se gli addendi sono tra loro concordi, si verifica
se e solo se il risultato è discorde
 addendi positivi ma risultato negativo
 addendi negativi ma risultato positivo
Criterio di controllo facile da applicare!
 La giustificazione è immediata pensando all’intervallo di rappresentazione
dei numeri in C2...

48
Confrontiamo bin, m&s, C2
255 bin 11111111
254 11111111
… …
130 10000010
129 10000001
128 10000000
01111111 dec. 127 m&s 01111111 C2 01111111
01111110 126 01111110 01111110
… … … …
00000010 2 00000010 00000010
00000001 1 00000001 00000001
00000000 +0 00000000 00000000
- -0 10000000 -
- -1 10000001 11111111
- -2 10000010 11111110
- … … …
- -126 11111110 10000010
- -127 11111111 10000001
- -128 - 10000000

49
Rappresentazione ottale ed esadecimale
Ottale o in base otto (oct):
 Si usano solo le cifre 0-7
534oct = 5oct×(8dec)2 + 3oct×(8dec)1 + 4oct×(8dec)0 = 348dec

Esadecimale o in base sedici (hex):

 Si usano le cifre 0-9 e le lettere A-F per i valori 10-15
B7Fhex = Bhex×(16dec)2 + 7hex×(16dec)1 + Fhex×(16dec)0 =
= 11dec×(16dec)2 + 7dec×(16dec)1 + 15dec×(16dec)0 = 2943dec

Entrambe queste basi sono facili da convertire in

binario, e viceversa...

50
Conversioni bin → hex e hex → bin
Converti: 010011110101011011bin =
0001bin 0011bin 1101bin 0101bin 1011bin =
= uno tre tredici cinque undici =
= 1hex 3hex Dhex 5hex Bhex = 13D5Bhex
Converti: A7B40Chex
Ahex 7hex Bhex 4hex 0hex Chex =
= dieci sette undici quattro zero dodici =
= 1010bin 0111bin 1011bin 0100bin 0000bin 1100bin =
= 101001111011010000001100bin
Si provi a convertire anche
• bin  oct, oct  bin, dec  hex, dec  oct

51
Numeri frazionari in virgola fissa
0,1011bin (in binario)
0,1011bin = 1×2−1 + 0×2−2 + 1×2−3 + 1×2−4 = 1/2 + 1/8 + 1/16 =
= 0,5 + 0,125 + 0,0625 = 0,6875dec

Si può rappresentare un numero frazionario in virgola fissa (o fixed

point) nel modo seguente:
19,6875dec = 10011,1011 virgola fissa

poiché si ha: 19dec = 10011bin e 0,6875dec = 0,1011bin

proporzione fissa:
5 bit per la parte intera, 4 bit per quella frazionaria
◦ Avremo 29 diversi valori codificati, e avremo 24 valori tra 0 e 1, 24 valori tra 1 e 2, … e
così via, con tutti i valori distribuiti su un asse a distanze regolari

-1 0 +1 +2

52
Numeri frazionari in virgola fissa
La sequenza di bit rappresentante un numero frazionario consta di
due parti di lunghezza prefissata
 Il numero di bit a sinistra e a destra della virgola è stabilito a priori, anche se
alcuni bit restassero nulli

È un sistema di rappresentazione semplice, ma poco flessibile, e

può condurre a sprechi di bit
 Per rappresentare in virgola fissa numeri aventi valore assoluto molto
grande oppure molto piccolo occorrono tanti bit sia per la parte intera
che per la parte frazionaria
 La precisione nell'intorno dell'origine e lontano dall'origine è la stessa

53
 Virgola fissa
Conversione dec → bin di parti frazionarie
Il metodo per convertire in binario parti frazionarie di numeri decimali è
duale di quello dei resti

Conversione dec -> bin Conversione dec -> bin

Parte intera (metodo dei resti) Parte frazionaria (metodo dei prodotti)
• Divido per 2 il numero decimale • Moltiplico per 2 la parte frazionaria
intero del numero decimale
• Riporto il resto • Riporto la parte intera
• Mi fermo quando ottengo 0 come • Mi fermo quando (se!) ottengo 1
risultato della divisione per risultato della moltiplicazione
• Per ottenere il numero binario che • Per ottenere il numero binario che
codifica il numero decimale intero, codifica il numero decimale intero,
leggo i resti in ordine inverso leggo le parti intere nello stesso
rispetto a come li ho ottenuti ordine in cui le ho ottenute

54
Virgola fissa
Conversione dec → bin di parti frazionarie

Esempio: 0,625dec

0,625 x 2 → 1,25
0,25 x 2 → 0,5
0,5 x 2 → 1
0

0,625dec = 0,101bin = 1x2-1+0x2-2+1x2-3 = 0,5+0,125 = 0,625

55
Virgola fissa
Conversione dec → bin di parti frazionarie
Esempio: 0,675dec 0,675 x 2 → 1,35
0,35 x 2 → 0,7
0,7 x 2 → 1,4
si ottiene ancora 0,4: 0,4 x 2 → 0,8
numero periodico 0,8 x 2 → 1,6
0,6 x 2 → 1,2
0,2 x 2 → 0,4
In binario non si può 0,4 …
rappresentare in modo
finito il valore 0,675dec
0,675dec = 0,101(0110)bin

56
Numeri frazionari in virgola mobile
La rappresentazione in virgola mobile (o floating point) è usata
spesso in base 10 (detta notazione scientifica):
0,137 × 108 notazione scientifica per intendere 13.700.000dec

La rappresentazione si basa sulla relazione

Rvirgola mobile = M × BE [attenzione: non (MxB)E ]

In binario, si utilizzano m ≥ 1 bit per la mantissa M e

n ≥ 1 bit per l’esponente E

 mantissa: un numero frazionario (tra -1 e +1)

 la base B non è rappresentata (è implicita)
 in totale si usano m + n bit

57
Numeri frazionari in virgola mobile
Supponiamo B=2, m=3 bit, n=3 bit, M ed E in binario naturale
M = 0112 ed E = 0102
Rvirgola mobile = 0,011 × 2010 = (1/4 + 1/8) × 22 = 3/8 × 4 = 3/2 = 1,5dec

M ed E possono anche essere negativi

◦ Normalmente, infatti, si usa il modulo e segno per M, mentre
si usa la rappresentazione cosiddetta in eccesso per E (qui non spiegata)

Vantaggi della virgola mobile

• si possono rappresentare con pochi bit numeri molto grandi oppure valori
frazionari molto piccoli (cioè con molti decimali)
• Sull’asse dei valori i numeri rappresentabili si affollano nell’intorno dello zero,
e sono sempre più sparsi al crescere del valore assoluto

-M 0 +M

58
ATTENZIONE! (i "pericoli" della virgola mobile)
Approssimazione
 0,375 x 107 + 0,241 x 103 = 0,3750241 x 107 ≈ 0,375 x 107
Ma, in virgola mobile, se disponiamo di poche cifre per la mantissa:
 0,375 x 107 + 0,241 x 103 = 0,375 x 107
 del resto sarebbe sbagliato approssimare a 0,374 x 107 o 0,376 x 107
Definiamo un ciclo che ripete la somma un milione di volte...
 Inizia con X = 0,375 x 107
 Ripeti 1.000.000 di volte X = X + 0,241 x 103 (incremento non intero)

TUTTO OK?
 Alla fine dovrebbe essere X = 0,375 x 107 + (0,241 x 103 x 106) ≈ 0,245 x 109

59
ATTENZIONE! (i "pericoli" della virgola mobile)
...
 Alla fine dovrebbe essere X = 0,375 x 107 + (0,241 x 103 x 106) ≈ 0,245 x 109

Ma, in virgola mobile...

 Il contributo delle singole somme (una alla volta) si perde del
tutto!
 Il risultato resta 0,375 x 107, sbagliato di due ordini di grandezza

 Scrivendo programmi che trattano valori rappresentati in virgola

mobile è necessario essere consapevoli dei limiti di
rappresentazione

 Lo stesso è vero con gli interi (rischio di overflow)

60
Aritmetica standard
Quasi tutti i calcolatori oggi adottano lo standard aritmetico
IEEE 754, che definisce:
 I formati di rappresentazione binario naturale, C2 e virgola mobile
 Gli algoritmi di somma, sottrazione, prodotto, ecc, per tutti i
formati previsti
 I metodi di arrotondamento per numeri frazionari
 Come trattare gli errori (overflow, divisione per 0, radice quadrata
di numeri negativi, ...)
Grazie a IEEE 754, i programmi sono trasportabili tra
calcolatori diversi senza che cambino né i risultati né la
precisione dei calcoli svolti dal programma stesso

61
Non solo numeri! codifica dei caratteri
Nei calcolatori i caratteri sono codificati mediante sequenze
di n ≥ 1 bit, ognuna rappresentante un carattere distinto
 Corrispondenza biunivoca tra numeri e caratteri
Codice ASCII (American Standard Computer Interchange
Interface): utilizza n=7 bit per 128 caratteri
Il codice ASCII a 7 bit è pensato per la lingua inglese.
Il codice ASCII Esteso a 8 bit, può rappresentare il doppio dei
caratteri
 Si aggiungono così, ad esempio, le lettere con i vari gradi di accento
(come À, Á, Â, Ã, Ä, Å, ecc), necessarie in molte lingue europee, e
altri simboli speciali ancora

62
Alcuni simboli del codice ASCII
Num. (in base 10) Codifica (7 bit) Carattere (o simbolo)
0 0000000 <terminator>
9 0001001 <tabulation>
10 0001010 <carriage return>
12 0001100 <sound bell>
13 0001101 <end of file>
32 0100000 blank space
33 0100001 !
49 0110001 1
50 0110010 2
64 1000000 @
65 1000001 A
66 1000010 B 63
97 1100000 a
98 1100001 b
126 1111110 ~
Altre codifiche alfanumeriche
Codifica ASCII esteso a 8 bit (256 parole di codice). È la
più usata
Codifica FIELDATA (6 bit, 64 parole codificate) Semplice
ma compatta, ... storica
Codifica EBDC (8 bit, 256 parole codifiate) Usata per
esempio nei nastri magnetici
Codifiche ISO-X (rappresentano i sistemi di scrittura
internazionali). P. es.: ISO-LATIN

64
Codifica di testi, immagini, suoni, ...
Caratteri: sequenze di bit
 Codice ASCII: utilizza 7(8) bit: 128(256) caratteri
Testi: sequenze di caratteri (cioè di bit)
Immagini: sequenze di bit
 bitmap: sequenze di pixel (n bit, 2n colori)
 jpeg, gif, pcx, tiff, …
Suoni (musica): sequenze di bit
 wav, mid, mp3, ra, …
Filmati: immagini + suoni
 sequenze di …? … "rivoluzione" digitale

65
Dentro al calcolatore...
Informazione e memoria

Una parola di memoria è in grado di contenere una

sequenza di n ≥ 1 bit
Di solito si ha: n = 8, 16, 32 o 64 bit
Una parola di memoria può dunque contenere gli elementi
d’informazione seguenti:
 Un carattere (o anche più di uno)
 Un numero intero in binario naturale o in C2
 Un numero frazionario in virgola mobile
 Alcuni bit della parola possono essere non usati
Lo stesso può dirsi dei registri della CPU

66
Per esempio...
indirizzi parole di memoria da 32 bit
un carattere ASCII, 0 la cella resta
probabilmente è un dato Z bit non usati parzialmente
inutilizzata
quattro caratteri ASCII
1 @
“impacchettati” nella A b 1 potrebbe essere un dato
stessa cella
oppure l’indirizzo di un’altra
2
Numeri la cui 1234 (in bin. nat.) cella (gli indirizzi sono
intrinsecamente positivi)
codifica richiede
3
molti bit possono - 4321 (in C2) probabilmente
estendersi su più è un dato
celle consecutive 4
19,758 (in virgola mob.)
probabilmente
un’istruzione? 5 è un dato
(perché no?) ...

67
Algebra di Boole
e
Elementi di Logica

68
Cenni all’algebra di Boole

L’algebra di Boole (inventata da George Boole,

britannico, seconda metà ’800), o algebra della
logica, si basa su operazioni logiche
Le operazioni logiche sono applicabili a operandi
logici, cioè a operandi in grado di assumere solo i
valori vero e falso
Si può rappresentare
vero con il bit 1 e
falso con il bit 0 (convenzione di logica positiva)

69
Operazioni logiche fondamentali

Operatori logici binari (con 2 operandi logici)

 Operatore OR, o somma logica
 Operatore AND, o prodotto logico
Operatore logico unario (con 1 operando)
 Operatore NOT, o negazione, o inversione

Poiché gli operandi logici ammettono due soli valori, si può

definire compiutamente ogni operatore logico tramite una
tabella di associazione operandi-risultato

70
Operatori logici di base
e loro tabelle di verità

A B A and B A B A or B A not A
0 0 0 0 0 0 0 1
0 1 0 0 1 1 1 0
1 0 0 1 0 1
1 1 1 1 1 1
(prodotto logico) (somma logico) (negazione)

Le tabelle elencano tutte le possibili combinazioni in

ingresso e il risultato associato a ciascuna combinazione

71
Espressioni logiche (o Booleane)
Come le espressioni algebriche, costruite con:
 Variabili logiche (chiamate: letterali): p. es. A, B, C = 0 oppure 1
 Operatori logici: and, or, not
Esempi:
A or (B and C)
(A and (not B)) or (B and C)
Precedenza: l’operatore “not” precede l’operatore “and”, che a
sua volta precede l’operatore “or”
A and not B or B and C = (A and (not B)) or (B and C)

Per ricordarlo, si pensi OR come “+” (più), AND come “×” (per) e
NOT come “−” (cambia segno)

72
Tabella di verità di
un’espressione logica
A B NOT ( ( A OR B) AND ( NOT A ) )
0 0 1
0 1 0
1 0 1
1 1 1

Specificano i valori di verità

per tutti i possibili valori
delle variabili

73
Tabella di verità di
un’espressione logica
A and B or not C
ABC X = A and B Y = not C X or Y
000 0 and 0 = 0 not 0 = 1 0 or 1 =1
001 0 and 0 = 0 not 1 = 0 0 or 0 =0
010 0 and 1 = 0 not 0 = 1 0 or 1 =1
011 0 and 1 = 0 not 1 = 0 0 or 0 =0
100 1 and 0 = 0 not 0 = 1 0 or 1 =1
101 1 and 0 = 0 not 1 = 0 0 or 0 =0
110 1 and 1 = 1 not 0 = 1 1 or 1 =1
111 1 and 1 = 1 not 1 = 0 1 or 0 =1

74
Due esercizi
A B NOT ( ( A OR B) AND ( NOT A ) )
0 0 1 0 0 0 0 1 0
0 1 0 0 1 1 1 1 0
1 0 1 1 1 0 0 0 1
1 1 1 1 1 1 0 0 1

A B C ( B OR NOT C ) AND ( A OR NOT C )

0 0 0 0 1 1 0 1 0 1 1 0
0 0 1 0 0 0 1 0 0 0 0 1
0 1 0 1 1 1 0 1 0 1 1 0
0 1 1 1 1 0 1 0 0 0 0 1
1 0 0 0 1 1 0 1 1 1 1 0
1 0 1 0 0 0 1 0 1 1 0 1
1 1 0 1 1 1 0 1 1 1 1 0
1 1 1 1 1 0 1 1 1 1 0 1

75
A che cosa servono le espressioni logiche?

A modellare alcune (non tutte) forme di ragionamento

 A = «è vero che 1 è maggiore di 2 ?» (sì o no, qui è no) = 0
 B = «è vero che 2 più 2 fa 4 ?» (sì o no, qui è sì) = 1
 A and B = «è vero che 1 sia maggiore di 2 e che 2 più 2 faccia 4 ?»
Si ha che A and B = 0 and 1 = 0, dunque no
 A or B = «è vero che 1 sia maggiore di 2 o che 2 più 2 faccia 4 ?»
Si ha che A or B = 0 or 1 = 1, dunque sì

OR, AND e NOT vengono anche chiamati connettivi logici, perché

funzionano come le congiunzioni coordinanti “o” (inclusivo) ed
“e”, e come la negazione “non”, del linguaggio naturale
Si modellano ragionamenti (o deduzioni) basati solo sull’uso di “o”,
“e” e “non” (non è molto, ma è utile)

76
Che cosa non si può modellare
tramite espressioni logiche?
Le espressioni logiche (booleane) non modellano:
 Domande esistenziali: “c’è almeno un numero reale x tale che il suo quadrato
valga −1 ?” (si sa bene che non c’è...)
∃x | x2 = −1 è falso
 Domande universali: “ogni numero naturale è la somma di quattro quadrati di
numeri naturali ?” (si è dimostrato di sì)
∀x | x = a2+b2+c2+d2 è vero (“teorema dei 4 quadrati”)
Più esattamente andrebbe scritto: ∀x ∃a,b,c,d | x = a2+b2+c2+d2

∃ e ∀ sono detti “operatori di quantificazione”, o quantificatori

La logica che usa solo or, and, not è il calcolo proposizionale
Aggiungendo gli operatori di quantificazione si ha il calcolo dei
predicati (che è una logica molto più complessa)

77
Tautologie e Contraddizioni

Tautologia
 Una espressione logica che è sempre vera, per qualunque
combinazione di valori delle variabili
 Esempio: principio del “terzo escluso”: A or not A (tertium non datur, non si
dà un terzo caso tra l’evento A e la sua negazione)

Contraddizione
 Una espressione logica che è sempre falsa, per qualunque
combinazione di valori delle variabili
 Esempio: principio di “non contraddizione”: A and not A (l’evento A e la sua
negazione non possono essere entrambi veri)

78
Equivalenza tra espressioni
Due espressioni logiche si dicono equivalenti (e si indica con
⇔) se hanno la medesima tabella di verità.
La verifica è algoritmica. Per esempio:

AB not A and not B ⇔ not (A or B)

00 1 and 1 = 1 not 0 = 1
01 1 and 0 = 0 not 1 = 0
10 0 and 1 = 0 not 1 = 0
11 0 and 0 = 0 not 1 = 0

• Espressioni logiche equivalenti modellano gli stessi

stati di verità a fronte delle medesime variabili

79
Proprietà dell’algebra di Boole
L’algebra di Boole gode di svariateproprietà, formulabili
sotto specie di identità
 (cioè formulabili come equivalenze tra espressioni logiche, valide
per qualunque combinazione di valori delle variabili)

Esempio celebre (e utile): le “Leggi di De Morgan”

not (A and B) = not A or not B (1a legge)

not (A or B) = not A and not B (2a legge)

80
Ancora sulle proprietà
Alcune proprietà somigliano a quelle dell’algebra numerica
tradizionale:
 Proprietà associativa: A or (B or C) = (A or B) or C (idem per AND)
 Proprietà commutativa: A or B = B or A (idem per AND)
 Proprietà distributiva di AND rispetto a OR:
A and (B or C) = A and B or A and C … e altre ancora

Molte altre sono alquanto “insolite”…

 Proprietà distributiva di OR rispetto a AND:
A or B and C = (A or B) and (A or C)
 Proprietà di assorbimento (A assorbe B):
A or A and B = A
 Legge dell’elemento 1: not A or A = 1 … e altre ancora

81
Uso delle proprietà
Trasformare un’espressione logica in un’altra, differente per
aspetto ma equivalente:
not A and B or A = (assorbimento)
= not A and B or (A or A and B) = (togli le parentesi)
= not A and B or A or A and B = (commutativa)
= not A and B or A and B or A = (distributiva)
= (not A or A) and B or A = (legge dell’elemento 1)
= true and B or A = (vero and B  B)
= B or A è più semplice dell’espressione originale

Occorre conoscere un’ampia lista di proprietà e si deve riuscire a

“vederle” nell’espressione (talvolta è difficile)

Si può verificare l’equivalenza anche con le tabelle di verità!

82