DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
Codifica binaria
dell’informazione
Marco D. Santambrogio – [email protected]
Ver. aggiornata al 29 O0obre 2013 Info di servizio
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
•  Doodle su demo 1mo compitino
http://tinyurl.com/infob1314-demo1mo
•  Correzione demo
http://tinyurl.com/infob1314-cdemo1mo
2
Un obiettivo per domarli tutti…
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
3
Uno dei problemi…
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
4
Obiettivi
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
•  Rappresentazione dell’informazione
•  Da decimale a binario
§  Contiamo con i numeri binari
•  Limiti della rappresentazione
•  Complemento a due
5
Codifica binaria
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
Chi ha “inventato” il bit?
Claude Shannon nel 1948 nel paper:
“A Mathematical Theory of Communication”
6
Codifica binaria
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
•  Alfabeto binario: usiamo dispositivi con solo due stati
•  Problema: assegnare un codice univoco a tutti gli oggetti
compresi in un insieme predefinito (e.g. studenti)
•  Quanti oggetti posso codificare con k bit:
§ 
§ 
§ 
§ 
§ 
1 bit ⇒ 2 stati (0, 1) ⇒ 2 oggetti (e.g. Vero/Falso)
2 bit ⇒ 4 stati (00, 01, 10, 11) ⇒ 4 oggetti
3 bit ⇒ 8 stati (000, 001, …, 111) ⇒ 8 oggetti
…
k bit ⇒ 2k stati ⇒ 2k oggetti
•  Quanti bit mi servono per codificare N oggetti:
§  N ≤ 2k ⇒ k ≥ log2N ⇒ k = ⎡log2N⎤ (intero superiore)
•  Attenzione:
ipotesi implicita che i codici abbiano tutti la stessa
lunghezza
7
Esempio di codifica binaria
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
•  Problema: assegnare un codice binario
univoco a tutti i giorni della settimana
•  Giorni della settimana: §  N = 7 ⇒ k ≥ log27 ⇒ k = 3
•  Con 3 bit possiamo ottenere 8 diverse
configurazioni:
§  Ne servono 7, quali utilizziamo?
§  Quale configurazione associamo a quale
giorno?
•  Attenzione: ipotesi che i codici abbiano
tutti la stessa lunghezza
8
I giorni della settimana in binario (1)
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
Lunedì
Martedì
Sabato Domenica
Mercoledì Venerdì
Giovedì
Giovedì Lunedì
Martedì Mercoledì
Domenica Venerdì Sabato
Lunedì
Martedì
Mercoledì Giovedì
Sabato
Venerdì
Mercoledì
Giovedì
Venerdì
Sabato
Domenica
Domenica
1 bit 2 “gruppi” Lunedì
Martedì
2 bit 4 “gruppi” 3 bit 8 “gruppi” 9
I giorni della settimana in binario (2)
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
Lunedì
Giovedì
Martedì
Sabato Domenica
Mercoledì Venerdì
Giovedì
Sabato Giovedì
Giovedì
Domenica
Sabato
Martedì
Martedì
Sabato
Venerdì Lunedì Mercoledì
1 bit 2 “gruppi” Martedì
Domenica
Domenica
Mercoledì
Mercoledì
Venerdì
Venerdì
Lunedì
2 bit 4 “gruppi” Lunedì
3 bit 8 “gruppi” 10
Stampa dei caratteri
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
11
Quale è il codice ASCII di ‘a’?
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
Ma quindi, quanto vale ‘a’?
97, 353, 609
Siamo sicuri?
97, 353=97+256, 609=353+256=97+256+256
97 = 97 + 256*0
353 = 97+256*1 609 = 97+256*2
12
97+256*i… quindi…
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
•  Quanti caratteri ci sono?
§  256
•  Con quanti bit rappresento 256
numeri? §  log2256 = log228 = 8
13
Codifica binaria dei caratteri
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
•  Quanti sono gli oggetti compresi
nell’insieme?
§ 
§ 
§ 
§ 
26 lettere maiuscole + 26 minuscole ⇒ 52
10 cifre
Circa 30 segni d’interpunzione
Circa 30 caratteri di controllo (EOF, CR, LF, …)
circa 120 oggetti complessivi ⇒ k = ⎡log2120⎤ = 7
•  Codice ASCII: utilizza 7 bit e quindi può
rappresentare al massimo 27=128 caratteri
§  Con 8 bit (= byte) rappresento 256 caratteri (ASCII esteso)
§  Si stanno diffondendo codici più estesi (e.g. UNICODE) per
rappresentare anche i caratteri delle lingue orientali
14
ASCII su 7 bit
0001
0010
0011
0100
0101
0110
0111
1000
1001
1010
1011
1100
1101
1110
1111
010
011
100
101
110
111
0000
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
sp
0
@
P
`
p
!
1
A
Q
a
q
"
2
B
R
b
r
#
3
C
S
c
s
$
4
D
T
d
t
%
5
E
U
e
u
&
6
F
V
f
v
'
7
G
W
g
w
(
8
H
X
h
x
)
9
I
Y
I
Y
*
:
J
Z
j
z
+
;
K
[
k
{
,
<
L
\
l
|
-­‐
=
M
]
m
}
.
>
N
^
n
~
/
?
O
_
o
canc
15
bit, Byte, KiloByte, MegaByte, …
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
bit = solo due sta9, “0” oppure “1”. Byte = 8 bit, quindi 28 = 256 sta9 KiloByte [KB] = 210 Byte = 1024 Byte ~ 103 Byte MegaByte [MB]
= 220 Byte = 1'048'576 Byte ~ 106 Byte GigaByte [GB]
= 230 Byte ~ 109 Byte TeraByte [TB]
= 240 Byte ~ 1012 Byte PetaByte [PB]
= 250 Byte ~ 1015 Byte ExaByte [EB] = 260 Byte ~ 1018 Byte 16
Da Hobbit a Hobbyte
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
17
Da base 10 a base 2
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
•  Dato un numero K rappresentato in base
dieci, la sua rappresentazione in base
due sarà del tipo bn bn-1bn-2 … b1b0 §  bi: cifra binaria
•  Per convertire un numero in base dieci
nel corrispondente in base due si devono
trovare i resti delle divisioni successive
del numero K per due
18
Da base 10 a base 2
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
•  Esempio: il numero 610:
6/2 = 3 resto 0
3/2 = 1 resto 1
1/2 = 0 resto 1
•  Leggendo i resti dal basso verso l’alto, si
ha che la rappresentazione binaria del
numero 610 è 1102
•  Per una corretta verifica basta riconvertire
il risultato alla base 10
§  Cioè, calcolare 1 x 22 + 1 x 21 + 0 x 20
19
Da base 10 a base 2
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
•  Perché 1102 = 610 ?
6/2 = 3 resto 0
3/2 = 1 resto 1
1/2 = 0 resto 1
0 x 20 +
1 x 21 +
1 x 22
= 6
1 x 22 + 1 x 21 + 0 x 20 = 1 x 21 + 1 x 20 con resto 0
2
1 x 21 + 1 x 2 0
= 1 x 20 con resto 1
2
1 x 20
= 0 con resto 1
2
20
Da base 10 a base 2
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
•  Esempio: il numero 34510:
345/2 = 172 resto 1
172/2 = 86 resto 0
86/2 = 43 resto 0
43/2 = 21 resto 1
21/2 = 10 resto 1
10/2 = 5 resto 0
5/2 = 2 resto 1
2/2 = 1 resto 0
1/2 = 0 resto 1
•  Leggendo i resti dal basso verso l’alto
§  Larappresentazione binaria del numero 34510 è
1010110012
21
Altre basi: ottale, esadecimale
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
•  Sistema ottale
§  Utilizza una notazione posizionale basata su
otto cifre (0,1,…,7) e sulle potenze di 8
§  Esempio: 1038 = 1 x 82 + 0 x 81 + 3 x 80 = 67
•  Sistema esadecimale
§  Utilizza una notazione posizionale basata su
sedici cifre (0,1,…,9,A,B,C,D,E,F) e sulle potenze
di 16
§  Esempio: 10316 = 1 x 162 + 0 x 161 + 3 x 160 = 259
§  Esempio: AC416 = 10 x 162 + 12 x 161 + 4 x 160 = 2756
22
Operazioni su numeri binari
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
•  Vediamo solo il caso della addizione nella
codifica binaria:
§  Si mettono in colonna i numeri da sommare
§  Si calcola il riporto ogni volta che la somma
parziale supera il valore 1
•  Addizione:
0
0
1
1
+
+
+
+
0
1
0
1
=
=
=
=
0
1
1
0
con
con
con
con
riporto
riporto
riporto
riporto
0
0
0
1
23
Operazioni su numeri binari
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
•  Addizione:
0
0
1
1
+
+
+
+
0
1
0
1
=
=
=
=
0
1
1
0
con
con
con
con
riporto
riporto
riporto
riporto
0
0
0
1
•  Esempi:
1 0 1 +
1 +
1 1 =
1 =
1 0 0 0
1 0
1 0 1 1 0 1 0 1 +
1 1 1 +
1 0 0 0 1 1 0 =
1 1 =
1 1 1 1 1 0 1 1
1 0 1 0
24
Codici a lunghezza fissa
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
•  Se si usa un numero prestabilito di cifre
si ha un codice a lunghezza fissa
•  In questo modo si pone anche un limite
al numero massimo rappresentabile
•  Esempio: qual è il numero più grande
rappresentabile con 4 cifre?
§ 
§ 
§ 
§ 
In
In
In
In
base
base
base
base
10:
2:
16:
8:
9999
1111 FFFF 7777 (=1510)
(=6553510)
(=409510)
25
Il fattoriale
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
•  Dato n, intero positivo, si definisce n
fattoriale e si indica con n! il prodotto
dei primi n numeri interi positivi
minori o uguali di quel numero. In
formule
•  Nota:
§  0! = 1
§  1! = 1
§  2! = 2, 3! = 6,…
26
Il fattoriale: codice
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
27
Proviamo ad eseguirlo…
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
WAT
28
Codici a lunghezza fissa
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
•  Numeri maggiori di quello massimo
rappresentabile causano problemi di
overflow
§  Ovvero per essere rappresentati richiedono più
cifre di quelle a disposizione
•  Esempio: 4 cifre
§ 
§ 
§ 
§ 
In
In
In
In
base
base
base
base
10:
2:
16:
8:
9999 + 1
1111 + 1
FFFF + 1
7777 + 1
=
=
=
=
1000010
100002 (=1610)
1000016 (=6553610)
100008 (=409610)
29
Codici a lunghezza fissa
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
•  In generale, con N cifre a disposizione e
base b il più grande numero (intero
positivo) rappresentabile si può
esprimere come
bN – 1
•  Esempio: N=4
§ 
§ 
§ 
§ 
In
In
In
In
base
base
base
base
10:
2:
16:
8:
9999 =
1111 =
FFFF =
7777 =
104 - 1
24 - 1
164 - 1
84 - 1
30
Codici a lunghezza fissa
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
• 
Esempio di overflow nel sistema binario
dovuto a operazioni aritmetiche:
§  5 + 4 = 9
(in sistema decimale)
§  abbiamo usato solo una cifra decimale per il
risultato
• 
Ricordiamo: 510 = 1012, 410 = 1002
1 0 1 +
1 0 0 =
1 0 0 1
(in sistema binario)
Errore: overflow (non può essere codificato 910 = 10012 con tre bit)
31
Rappresentazione dei numeri
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
•  Possiamo rappresentare i numeri usando un
numero variabile di cifre (che dipende dal valore
che si vuole rappresentare) §  Come? Introduciamo un simbolo speciale che indica
dove termina la rappresentazione di un numero e inizia
quella del numero successivo
§  Esempio: 1001#11#1 (codice a lunghezza variabile, #
separatore)
•  Esistono anche “codici di espansione”, che
permettono di definire dei codici a lunghezza
variabile senza far uso del carattere di
separazione
32
Rappresentazione dei numeri
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
•  In realtà, una semplice codifica binaria
come quella discussa fino ad ora non è
sufficiente, per due motivi:
§  Numeri negativi
§  Numeri con la virgola
•  Per questi numeri vengono utilizzate
delle rappresentazioni differenti
§  Per esempio “complemento a due” per
rappresentare i numeri negativi
33
Numeri negativi
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
•  Si può pensare di usare un bit per il
segno
§  “0” identifica “+”
§  “1” identifica “-”
•  Gli altri bit vengono usati per codificare il
valore assoluto (modulo) del numero
[-22+1, 22-1]
[0, 23-1]
-3
-2 -1
0
1
2
3
4
5
6
7
34
Numeri negativi - problemi
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
•  Con 3 bit avremo:
" Problemi:
000
+0
001
+1
010
+2
011
+3
100
-0
101
-1
110
-2
111
-3
n 
n 
Il numero 0 ha due
rappresentazioni
Per l’operazione di
somma si deve tener
conto dei segni degli
addendi
0010+
1011=
1101
(+2)
(-3)
(-5 ERRATO)
35
Il fattoriale: codice
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
36
Proviamo ad eseguirlo…
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
int sono interi con segno
37
Il fattoriale: unsigned int
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
38
Proviamo ad eseguirlo…
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
39
Numeri negativi: Complemento a due
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
•  Il bit più significativo rappresenta il segno del
numero: 0 per i numeri positivi e 1 per i numeri
negativi
•  La rappresentazione di un numero positivo si ottiene
codificando il valore assoluto del numero con i bit
restanti
•  La rappresentazione di un numero negativo si
ottiene in tre passi:
§  Si rappresenta in complemento a due il numeri positivo
con lo stesso valore assoluto del numero negativo da
codificare
§  Si invertono tutti i bit in tale rappresentazione
(0→1,1→0)
§  Si somma uno al risultato ottenuto al passo precedente
40
Complemento a due
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
•  Esempio (con 4 bit a disposizione):
§  La codifica di +5 è 0101
§  La codifica del numero –5 avviene in tre passi:
•  La rappresentazione in complemento a due di +5 è
0101
•  Invertendo tutti i bit si ottiene 1010
•  Sommando 1 si ottiene 1011, la rappresentazione
in complemento a due di -5
41
Complemento a due
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
•  Per ottenere un numero con segno data
la sua rappresentazione in complemento
a due:
§  Se il primo bit è 0 il numero è positivo: per
calcolarne il valore assoluto si esegue la
conversione da binario a decimale
§  Se il primo bit è 1 il numero è negativo:
• 
• 
• 
• 
Si ignora il primo bit
Si invertono i restanti bit
Si converte il numero da binario a decimale
Si somma uno al numero ottenuto per ottenere il
valore assoluto del numero negativo
42
Complemento a due
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
•  Esempio: 1011
§ 
§ 
§ 
§ 
Si esclude il primo bit
Invertendo 011 si ottiene 100 che è codifica di 4
Va aggiunto 1 per ottenere il valore assoluto 5
Il risultato è quindi -5
43
Complemento a due
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
•  Con 3 bit avremo:
" Esempi di addizione:
000
+0
001
+1
010
+2
011
+3
100
-4
101
-3
110
-2
111
-1
0010+
1011=
1101
(+2)
(-5)
(-3)
0111+
1011=
0010
(+7)
(-5)
(+2)
Nel secondo esempio,
l’overflow è ignorato
44
Exe 1: Codifica dell’informazione
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
•  Quanti bit si devono utilizzare per
rappresentare 300 informazioni distinte?
•  Quanti byte occupa la parola “psicologia”
se la si codifica utilizzando il codice
ASCII?
•  Dati 12 bit per la codifica, quante
informazioni distinte si possono
rappresentare?
45
Exe 2: Codifica dei suoni
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
•  Quanto spazio occupa un suono della
durata di 30 secondi campionato a 100
Hz (100 campioni al secondo), in cui ogni
campione occupa 4 byte?
46
Exe 3: Codifica dei numeri
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
•  Codificare il numero 17510 nella
corrispondente rappresentazione binaria
•  Ordinare in modo crescente i seguente
numeri: 10510 , 128 , 1001100002 ,
1001110 •  Codificare il numero negativo –1510 nella
rappresentazione in complemento a due 47
Exe 4: Codifica delle immagini
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
•  Quanti bit occupa un’immagine di 100 x
100 pixel in bianco e nero?
•  Quanti byte occupa un’immagine di 100
x 100 pixel a 256 colori?
•  Se un’immagine a 16777216 di colori
occupa 2400 byte, da quanti pixel sarà
composta? 48
Fonti per lo studio + Credits
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
•  Fonti per lo studio
§  Informatica arte e mestiere, S. Ceri, D. Mandrioli, L.
Sbattella, McGrawHill
•  Capitolo 11
§  Introduzione ai sistemi informatici, D. Sciuto, G.
Buonanno, L. Mari, 4a Ed, McGrawHill
•  Capitolo 2
§  The Art & Craft of Computing, S. Ceri, D. Mandrioli, L.
Sbattella, Addison-Wesley
•  Capitolo 13
•  Credits
§  P. Spoletini
§  J. Sproston
49