Rappresentazione dell’informazione Paolo Bison
Fondamenti di Informatica Ingegneria Meccanica
Università di Padova A.A. 2008/09
Rappresentazione dell’informazione, Paolo Bison, FI08, 2008-09-29 – p.1
Codifica dell’informazione
rappresentazione dell’informazione con una sequenza finita di bit
differenti codifiche per
informazione numerica
informazione simbolica
informazione non simbolica
Sistema posizionale di numerazione
un numero è rappresentato da una sequenza di simboli
a
k. . . a
2a
1a
0.a
−1. . . a
−lba(1)
dove
la base b ∈ N e b ≥ 2 ,
le cifre ai sono simboli presi da un insieme S di b
elementi in corrispondenza biunivoca con l’insieme
D = {i ∈ N : 0 ≤ i < b}
interpretazione di (1)
v(ak)bk + . . . + v(a1)b1+ v(a0)b0+ v(a−1)b−1+ . . . + v(a−l)b−l
con
v : S → D
ail punto di radice separa termini associati a potenze positive da quelli associati a potenze negative
Rappresentazione dell’informazione, Paolo Bison, FI08, 2008-09-29 – p.3
Sistemi di numerazione
decimale
b = 10
a
i∈ {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}
103.24
10=
1 · 10
2+ 0 · 10
1+ 3 · 10
0+ 2 · 10
−1+ 4 · 10
−2
binario
b = 2
a
i∈ {0, 1}
110.11
2=
· 2
2+ 1 · 2
1+ 0 · 2
0+ 1 · 2
−1+ 1 · 2
−2Sistemi di numerazione (cont.)
ottale
b = 8
a
i∈ {0, 1, 2, 3, 4, 5, 6, 7}
103.2
8= 1 · 8
2+ 0 · 8
1+ 3 · 8
0+ 2 · 8
−1= 88.5
10
esadecimale
b = 16
a
i∈ {0, 1, 2, 3, 4, 5, 6, 7, 8, 9,
10A,
11B,
12C,
13D,
14E,
15F } 70C.1
16= 7 · 16
2+ 0 · 16
1+ 12 · 16
0+ 1 · 16
−1= 1804.06255
10Rappresentazione dell’informazione, Paolo Bison, FI08, 2008-09-29 – p.5
Conversione di base
trasformare la rappresentazione di un numero in una data base nella corrispondente rappresentazione in un’altra base
possibili conversioni
base qualunque ⇒ decimale
base qualunque ⇒ altra base
binaria ⇒ ottale (esadecimale) ottale (esadecimale) ⇒ binaria
ottale ⇔ esadecimale
decimale ⇒ altra base
Base qualunque ⇒ Decimale
si applica la definizione di sistema di numerazione
122.1
3=
1 · 3
2+ 2 · 3
1+ 2 · 3
0+ 1 · 3
−1= 17.¯3
10base qualunque ⇒ altra base
base qualunque ⇒ decimale ⇒ altra base
Rappresentazione dell’informazione, Paolo Bison, FI08, 2008-09-29 – p.7
Binaria ⇒ Ottale (Esadecimale)
partendo dal punto di radice si raggruppano in bit in terne (quaterne) e si scrive la cifra ottale (esadecimale)
corrispondente al loro valore
1111100101.10
2001
|111
|100
|101.100
|21745.4
80011
|1110
|0101 .1000
|23E5.8
16
notazione più compatta
Ottale (Esadecimale) ⇒ Binaria
si scrive il valore delle cifre ottali (esadecimali) in binario utilizzando tre (quattro) bit
315.7
8011
|001
|101.111
|25B0.C
160101
|1011
|0000.1100
|2ottale ⇔ esadecimale
ottale ⇔ binaria ⇔ esadecimale
Rappresentazione dell’informazione, Paolo Bison, FI08, 2008-09-29 – p.9
Decimale ⇒ Base b
dato un numero nella forma M.F10 si converte separatamente:
parte intera M
parte frazionaria F
Parte intera M
trovare mi tali per cui
M = m
kb
k+ . . . + m
2b
2+ m
1b
1+ m
0
eseguendo M/b si ottiene
quoziente m
kb
k−1+ . . . + m
2b
1+ m
1resto m
0iterando, finché il quoziente non vale 0, si trovano i valori numerici degli mi come resti della divisione per b
Rappresentazione dell’informazione, Paolo Bison, FI08, 2008-09-29 – p.11
62.25
10⇒ X
2
parte intera 62
quoziente resto
62 :2 31 0
31 15 1
15 7 1
7 3 1
3 2 1
2 0 1
62
10= 111110
255.3
10⇒ X
2
parte intera 55
quoziente resto
55 :2 27 1
27 13 1
13 6 1
6 3 0
3 1 1
1 0 1
55
10= 110111
2Rappresentazione dell’informazione, Paolo Bison, FI08, 2008-09-29 – p.13
2015.625
10⇒ X
16
parte intera 2015
quoziente resto
2015 :16 125 15
125 7 13
7 0 7
2015
10= 7DF
16Parte frazionaria F - I
trovare fi tali per cui
F = f
1b
−1+ f
2b
−2+ . . . + f
lb
−l+ . . .
eseguendo F × b si ottiene il prodotto
f
1+ f
2b
−1+ . . . + f
lb
−(l−1)+ . . .
| {z }
parte frazionaria
f
1è la parte intera del prodotto
aiterando si trovano i valori numerici degli fi come parte intera del prodotto della parte frazionaria del passo precedente per b
asi ricordi che F < 1
Rappresentazione dell’informazione, Paolo Bison, FI08, 2008-09-29 – p.15
Parte frazionaria F - II
condizioni di terminazione
prodotto nullo numero finito di fi
prodotto già ottenuto in un passo precedente
numero infinito di fi ⇒ numero periodico nella base b
62.25
10⇒ X
2
parte frazionaria 0.25
prodotto intera
0.25 × 2 0.5 0
0.5 1.0 1
0.25
10= 0.01
2
62.25
10= 111110.01
2Rappresentazione dell’informazione, Paolo Bison, FI08, 2008-09-29 – p.17
55.3
10⇒ X
2
parte frazionaria 0.3
prodotto intera
0.3 × 2 0.6 0
0.6 1.2 1
0.2 0.4 0
0.4 0.8 0
0.8 1.6 1
0.6 1.2 1
0.3
10= 0.01001
2
55.3
10= 110111.01001
22015.625
10⇒ X
16
parte frazionaria 0.625
prodotto intera
0.625 × 16 10.0 10
0.625
10= 0.A
16
2015.625
10= 7DF.A
16Rappresentazione dell’informazione, Paolo Bison, FI08, 2008-09-29 – p.19
Numeri naturali
rappresentazione in sistema binario con N bit
2
Npossibili valori da 0 a 2N − 1
N = 5
0 00000
1 00001
2 00010
.. .
17 10001
.. .
29 11101
30 11110
31 11111
Numeri interi
rappresentazione del segno e valore con N bit
metodi
ampiezza e segno
eccesso 2N−1
complemento a 1
complemento a 2
Rappresentazione dell’informazione, Paolo Bison, FI08, 2008-09-29 – p.21
Ampiezza e segno
1 bit (il più significativo) per il segno (0=+, 1=-)
N − 1 bit per il valore
N = 5
15 01111
14 01110
.. .
2 00010
1 00001
0 00000
-0 10000
-1 10001
-2 10010
.. .
-14 11110
-15 11111
Eccesso 2N−1
numero relativo M rappresentato dalla codifica binaria del numero naturale M + 2N−1
es. N = 5 ⇒ 2N−1 = 16 ⇒ M + 16
N = 5
15 11111
14 11110
.. .
2 10010
1 10001
0 10000
-1 01111
-2 01110
.. .
-15 00001
-16 00000
Rappresentazione dell’informazione, Paolo Bison, FI08, 2008-09-29 – p.23
Complemento a 1
interi positivi
rappresentati come i primi 2N−1
numeri naturali
interi negativi
“complemento a 1”
adella rappre- sentazione binaria del corrispon- dente intero positivo
atrasformazione di ogni 0 in 1 e ciascun 1 in 0
N = 5
15 01111
14 01110
.. .
2 00010
1 00001
0 00000
-0 11111
-1 11110
-2 11101
.. .
-14 10001
-15 10000
Complemento a 2
interi positivi
rappresentati come i primi 2N−1
numeri naturali
interi negativi
“complemento a 2”
adella rappre- sentazione binaria del corrispon- dente intero positivo
asi somma 1 al complemento ad 1
N = 5
15 01111
14 01110
.. .
2 00010
1 00001
0 00000
-1 11111
-2 11110
.. .
-15 10001
-16 10000
Rappresentazione dell’informazione, Paolo Bison, FI08, 2008-09-29 – p.25
Proprietà complemento a 2
una sola rappresentazione dello 0
operazioni aritmetiche indipendenti dal segno
10 01 010
12 00010
12 01100
- 2 1 11 1
1110
1
-1 11111
-3 11101
15
1 10 1111
1-4 11100
11 01011
facile aumento di precisione a P bit ( P > N ) estendere bit di segno per P − N bit
N=5, P=10
01111 ⇒ 0000001111
10010 ⇒ 1111110010
Complemento a 2: overflow
superamento del massimo/minimo valore rappresentabile
> massimo: riporto sul bit di segno, ma non sul carry bita
< minimo: riporto sul carry bit, ma non su quello di segno
15 0
11
1111
12 00010 17 10001
- 2 111110
−16 10000
−18 01110
acarry bit: bit successivo a quello di segno
Rappresentazione dell’informazione, Paolo Bison, FI08, 2008-09-29 – p.27
Numeri frazionari
sottoinsieme dei numeri reali
codifiche
notazione a virgola fissa (fixed point)
notazione a virgola mobile (floating point)
Virgola fissa
dati N bit,
M usati per la parte intera,
N − M per la parte frazionaria
N = 10 , M = 7
0010110
|010 ⇒ 22.25
Rappresentazione dell’informazione, Paolo Bison, FI08, 2008-09-29 – p.29
Virgola mobile
basato sulla notazione scientifica
−1.5 × 10
5−15.0 × 10
40.3 × 10
−23.0 × 10
−3
formato IEEE
si esprime il numero frazionario nella forma
m × 2
csi rappresentano in maniera separata la mantissa m in
virgola fissa e la caratteristica c
Formato IEEE
32 bit con base b = 2
31 30 29 · · · 24 23 22 21 · · · 2 1 0
bit più significativo (31) segno della mantissa (0=+, 1=-)
8 bit (30-23) caratteristica in eccesso 127
23 bit (22-0) mantissa in virgola fissa con N = 24 , M = 1
(punto a dx del bit + significativo) e normalizzata, i.e. prima cifra binaria 6= 0 :
1.0
2≤ m ≤ 1.11111111111111111111111
2e “hidden bit”, i.e. il bit a sx del punto di radice non viene rappresentato (è sempre 1)
Rappresentazione dell’informazione, Paolo Bison, FI08, 2008-09-29 – p.31
Formato IEEE (cont.)
modulo minimo= 1 × 2−126
modulo massimo = (2 − 2−23) × 2
127
casi particolari
c bit22−0
= 0 6= 0
-127
a0 non norm.
128
b∞ NANc
a00000000
b11111111
cNot A Number
Note floating-point
distanza tra due numeri
determinato dal valore del bit meno significativo della mantissa il quale dipende dalla caratteristica:
0.000000000000000000000001
2× b
c
mantissa normalizzata
massimizza la risoluzione utilizzando per ogni numero la caratteristica minima
aritmetica
se a >> b , a + b = a
overflow
valore in modulo superiore al massimo rappresentabile
underflow
valore in modulo inferiore al minimo rappresentabile
Rappresentazione dell’informazione, Paolo Bison, FI08, 2008-09-29 – p.33
117.1
10
parte intera 117
quoziente resto
117 :2 58 1
58 29 0
29 14 1
14 7 0
7 3 1
3 1 1
1 0 1
117.1
10
parte frazionaria 0.1
prodotto intera
0.1 × 2 0.2 0
0.2 0.4 0
0.4 0.8 0
0.8 1.6 1
0.6 1.2 1
0.2 0.4 0
117.1
10= 1110101.00011
2Rappresentazione dell’informazione, Paolo Bison, FI08, 2008-09-29 – p.35
117.1
10
virgola fissa N = 32 , M = 20
00000000000001110101000110011001
200075199
16
formato IEEE
1110101.00011001100110011
21.11010100011001100110011
2× 2
6c = 6 ⇒ 127 + 6 = 133 = 10000101
20
|10000101
|11010100011001100110011
242EA3333
16Binary Coded Decimal (BCD)
segno e ciascuna cifra di un numero decimale rappresentati separatamente con 4 bit
precisione arbitraria
−1350.1
10=
11110001001101010000.0001
BCD0 0000
1 0001
2 0010
.. .
8 1000
9 1001
+ 1010
- 1111
Rappresentazione dell’informazione, Paolo Bison, FI08, 2008-09-29 – p.37
Informazione simbolica
codifica di 2N simboli mediante N bit
associazione biunivoca tra simboli e sequenze di bit (numeri in base 2)
codici
ASCII (7 bit, 128 simboli)
UNICODE (32 bit, 96447 simboli)
www.unicode.org
ASCII
a0 a1 0 1 2 3 4 5 6 7
0 nul dle sp 0 @ P ‘ p
1 soh dc1 ! 1 A Q a q
2 stx dc2 " 2 B R b r
3 etx dc3 # 3 C S c s
4 eot dc4 $ 4 D T d t
5 enq nak % 5 E U e u
6 ack syn & 6 F V f v
7 bel etb ’ 7 G W g w
8 bs can ( 8 H X h x
9 ht em ) 9 I Y i y
A nl sub * : J Z j z
B vt esc + ; K [ k {
C ff fs , < L \ l |
D cr gs - = M ] m }
E so rs . > N ˆ n ˜
F si us / ? O _ o del
Rappresentazione dell’informazione, Paolo Bison, FI08, 2008-09-29 – p.39
Unicode
Unicode (cont.)
Rappresentazione dell’informazione, Paolo Bison, FI08, 2008-09-29 – p.41
Codifiche Unicode
UTF-32
codifica fissa a 32 bit
UTF-16
codifica a 16 bit: maggior parte dei caratteri usano una sola word, altri due
UTF-8
codifica a lunghezza variabile di bytes: caratteri C0 e C1
codificati con un byte
Esempio codifica Unicode
Rappresentazione dell’informazione, Paolo Bison, FI08, 2008-09-29 – p.43
Informazione non simbolica
grandezze fisiche continue suono, immagine
conversione continua ⇒ discreta
campionamento