Rappresentazione dell’informazione
Paolo Bison
Fondamenti di Informatica 1 A.A. 2004/05
Universit`a di Padova
Rappresentazione dell’informazione, Paolo Bison, A.A. 2004-05, 2004-10-15 – p.1/48
informazione
tipo di informazione
numerica
non-numerica / simbolica
codifica binaria
[paolo@pcbison tmp]# dumpbin boh
0000000000000001111111111111111000000000000000111111111111111111
0000000000000001000000000000000011111111111111111111111111111011
0000000000000011111111111111110000000000000000001111111111111110
1111111111111111000000000000000100000000000001000000000000000001
1111111111111111111111111111111011111111111111010000000000000000
0000000000000000111111111111111100000000000000000000000000000000
0000000000000001000000000000000000000000000000001111111111111111
1111111111111101000000000000001011111111111111100000000000000010
1111111111111110000000000000000011111111111110011111111111111111
Interpretazione dell’informazione
programma eseguibile
[paolo@pcbison tmp]# ./boh
bash: ./boh: cannot execute binary file [paolo@pcbison tmp]#
valori numerici
[paolo@pcbison tmp]# od -t d2 boh
0000000 256 -257 768 -1 256 0 -1 -1025
0000020 768 -769 0 -257 -1 256 1024 256
0000040 -1 -257 -513 0 0 -1 0 0
0000060 256 0 0 -1 -513 512 -257 512
0000100 -257 0 -1537 -1 -2049 256 -1793 768 0000120 -1281 1024 -1537 -257 -1281 0 -769 256
0000140 -1025 -1 -1793 0 -1537 768 -769 0
0000160 -2305 0 -1281 256 -2049 -1 -1025 -1 0000200 -2049 0 -3329 -1 -2049 256 -3073 1792
Rappresentazione dell’informazione, Paolo Bison, A.A. 2004-05, 2004-10-15 – p.3/48
Interpretazione dell’informazione
testo
[paolo@pcbison tmp]# od -t a boh
000 nul soh del ˜ nul etx del del nul soh nul nul del del del { 020 nul etx del | nul nul del ˜ del del nul soh nul eot nul soh 040 del del del ˜ del } nul nul nul nul del del nul nul nul nul 060 nul soh nul nul nul nul del del del } nul stx del ˜ nul stx 100 del ˜ nul nul del y del del del w nul soh del x nul etx
immagine
Interpretazione dell’informazione
cos’è?
Ludwig Van Beethoven
SINFONIA N. 9 in Re Minore, op. 125 I movimento
direttore: Karl Böhm
Francoforte, 29 settembre 1954.
Rappresentazione dell’informazione, Paolo Bison, A.A. 2004-05, 2004-10-15 – p.5/48
Tipo codifica
differenti codifiche per
informazione numerica
informazione simbolica
Sistema posizionale di numerazione
un numero è rappresentato da una sequenza di simboli
a k . . . a 2 a 1 a 0 .a −1 . . . a −lb a (1) dove
la base b ∈ N e b ≥ 2,
le cifre a i 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(a k )b k + . . . + v(a 1 )b 1 + v(a 0 )b 0 + v(a − 1 )b − 1 + . . . + v(a −l )b −l con v : S → D
a il punto di radice separa termini associati a potenze positive da quelli associati a potenze negative
Rappresentazione dell’informazione, Paolo Bison, A.A. 2004-05, 2004-10-15 – p.7/48
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
=
1 · 2 2 + 1 · 2 1 + 0 · 2 0 + 1 · 2 −1 + 1 · 2 −2
=
6.75
Sistemi 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, A, 10 11 B, 12 C, 13 D, 14 E, 15 F}
70C.1 16 = 7 · 16 2 + 0 · 16 1 + 12 · 16 0 + 1 · 16 −1 = 1804.06255 10
Rappresentazione dell’informazione, Paolo Bison, A.A. 2004-05, 2004-10-15 – p.9/48
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 10
base qualunque ⇒ altra base
base qualunque ⇒ decimale ⇒ altra base
Rappresentazione dell’informazione, Paolo Bison, A.A. 2004-05, 2004-10-15 – p.11/48
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 2
001 | 111 | 100 | 101.100 |2 1745.4 8
0011 | 1110 | 0101.1000 |2 3E5.8 16
notazione più compatta
Ottale (Esadecimale) ⇒ Binaria
si scrive il valore delle cifre ottali (esadecimali) in binario utilizzando tre (quattro) bit
315.7 8
011 | 001 | 101.111 |2 5B0.C 16
0101 | 1011 | 0000.1100 |2 ottale ⇔ esadecimale
ottale ⇔ binaria ⇔ esadecimale
Rappresentazione dell’informazione, Paolo Bison, A.A. 2004-05, 2004-10-15 – p.13/48
Decimale ⇒ Base b
dato un numero nella forma M.F 10 si converte separatamente:
parte intera M
parte frazionaria F
Parte intera M
trovare m i tali per cui
M = m k b k + . . . + m 2 b 2 + m 1 b 1 + m 0
eseguendo M/b si ottiene
quoziente m k b k −1 + . . . + m 2 b 1 + m 1 resto m 0
iterando, finché il quoziente non vale 0, si trovano i valori numerici degli m i come resti della divisione per b
Rappresentazione dell’informazione, Paolo Bison, A.A. 2004-05, 2004-10-15 – p.15/48
Parte frazionaria F - I
trovare f i tali per cui
F = f 1 b −1 + f 2 b −2 + . . . + f l b −l + . . .
eseguendo F × b si ottiene il prodotto f 1 + f 2 b −1 + . . . + f l b −(l−1) + . . .
| {z }
parte frazionaria
f 1 è la parte intera del prodotto a
iterando si trovano i valori numerici degli f i come parte intera del prodotto della parte frazionaria del passo precedente per b
a si ricordi che F < 1
Parte frazionaria F - II
condizioni di terminazione
prodotto nullo
numero finito di f i
prodotto già ottenuto in un passo precedente
numero infinito di f i ⇒ numero periodico nella base b
Rappresentazione dell’informazione, Paolo Bison, A.A. 2004-05, 2004-10-15 – p.17/48
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 2
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 2
Rappresentazione dell’informazione, Paolo Bison, A.A. 2004-05, 2004-10-15 – p.19/48
55.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 2
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 2
Rappresentazione dell’informazione, Paolo Bison, A.A. 2004-05, 2004-10-15 – p.21/48
2015.625 10 ⇒ X 16
parte intera 2015
quoziente resto
2015 :16 125 15
125 7 13
7 0 7
2015 10 = 7DF 16
2015.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 16
Rappresentazione dell’informazione, Paolo Bison, A.A. 2004-05, 2004-10-15 – p.23/48
Numeri naturali
rappresentazione in sistema binario con N bit
2 N possibili valori da 0 a 2 N − 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 2 N −1
complemento a 1
complemento a 2
Rappresentazione dell’informazione, Paolo Bison, A.A. 2004-05, 2004-10-15 – p.25/48
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 2 N −1
numero relativo M
rappresentato dalla codifica binaria del numero naturale M + 2 N −1
es. N = 5 ⇒ 2 N −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, A.A. 2004-05, 2004-10-15 – p.27/48
Complemento a 1
interi positivi
rappresentati come i primi 2 N −1 numeri naturali
interi negativi
“complemento a 1” a della rappre- sentazione binaria del corrispon- dente intero positivo
a trasformazione 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 2 N −1 numeri naturali
interi negativi
“complemento a 2” a della rappre- sentazione binaria del corrispon- dente intero positivo
a si 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, A.A. 2004-05, 2004-10-15 – p.29/48
Proprietà complemento a 2
una sola rappresentazione dello 0
operazioni aritmetiche indipendenti dal segno 10 01 010 1
2 00010
12 01100
-2 1 1 1 1 1 110 1 -1 11111 -3 11101
15 1 1 0 1111 1 -4 11100 11 01011
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 bit a
< minimo: riporto sul carry bit, ma non su quello di segno
15 0 1 1 1 111 1 2 00010 17 10001
-2 1 11110
−16 10000
−18 01110
a carry bit: bit successivo a quello di segno
Rappresentazione dell’informazione, Paolo Bison, A.A. 2004-05, 2004-10-15 – p.31/48
Numeri frazionari
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, A.A. 2004-05, 2004-10-15 – p.33/48
Virgola mobile
dato un numero espresso nella forma m × b c
si rappresentano in maniera separata la mantissa m (virgola fissa ampiezza e segno) e la caratteristica c (eccesso 2 N −1 ) mentre la base b (potenza di 2) viene implicitamente definita dal formato:
IEEE
IBM
Digital
posizione del punto di radice definita dal valore
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 2
e “hidden bit”, i.e. il bit a sx del punto di radice non viene rappresentato (è sempre 1)
Rappresentazione dell’informazione, Paolo Bison, A.A. 2004-05, 2004-10-15 – p.35/48
Formato IEEE (cont.)
modulo minimo=1 × 2 −126
modulo massimo = (2 − 2 −23 ) × 2 127
casi particolari
c bit22−0 = 0 6= 0 -127 0 non norm.
128 ∞ NAN a
a Not 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
overflow
valore in modulo superiore al massimo rappresentabile
underflow
valore in modulo inferiore al minimo rappresentabile
Rappresentazione dell’informazione, Paolo Bison, A.A. 2004-05, 2004-10-15 – p.37/48
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 2
Rappresentazione dell’informazione, Paolo Bison, A.A. 2004-05, 2004-10-15 – p.39/48
117.1 10
virgola fissa N = 32, M = 20
00000000000001110101000110011001 2 00075199 16
formato IEEE
1110101.00011001100110011 2 1.11010100011001100110011 2 × 2 6 c = 6 ⇒ 127 + 6 = 133 = 10000101 2 0 | 10000101 | 11010100011001100110011 2
42EA3333 16
Binary Coded Decimal (BCD)
segno e ciascuna cifra di un numero decimale rappresentati separatamente con 4 bit
precisione arbitraria
−1350.1 10
=
11110001001101010000.0001 BCD
0 0000
1 0001
2 0010
...
8 1000
9 1001
+ 1010
- 1111
Rappresentazione dell’informazione, Paolo Bison, A.A. 2004-05, 2004-10-15 – p.41/48
Informazione simbolica
codifica di 2 N simboli mediante N bit
associazione biunivoca tra simboli e sequenze di bit (numeri in base 2)
codici
ASCII (7 bit, 128 simboli)
EBCDIC (8 bit, 256 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, A.A. 2004-05, 2004-10-15 – p.43/48
Unicode
Unicode (cont.)
Rappresentazione dell’informazione, Paolo Bison, A.A. 2004-05, 2004-10-15 – p.45/48
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, A.A. 2004-05, 2004-10-15 – p.47/48