Rappresentazione dell’informazione

(1)

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 1111111111110111000000000000000111111111111110000000000000000011 ...

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

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

(2)

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.

Tipo codifica

differenti codifiche per

informazione numerica

informazione simbolica

Sistema posizionale di numerazione

un numero è rappresentato da una sequenza di simboli

a k . . . a ₂ a ₁ a ₀ .a ₋₁ . . . a _−lb ^a (1) dove

la base b ∈ N e b ≥ 2,

le cifre a ⁱ 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 ¹ + v(a 0 )b ⁰ + v(a ₋ 1 )b ⁻ ¹ + . . . + 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

Sistemi di numerazione

decimale b = 10

a ⁱ ∈ {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}

103.24 ₁₀

=

1 · 10 ² + 0 · 10 ¹ + 3 · 10 ⁰ + 2 · 10 ⁻¹ + 4 · 10 ⁻²

binario b = 2 a i ∈ {0, 1}

110.11 2

=

1 · 2 ² + 1 · 2 ¹ + 0 · 2 ⁰ + 1 · 2 ⁻¹ + 1 · 2 ⁻²

=

6.75 ₁₀

(3)

Sistemi di numerazione (cont.)

ottale b = 8

a ⁱ ∈ {0, 1, 2, 3, 4, 5, 6, 7}

103.2 ₈ = 1 · 8 ² + 0 · 8 ¹ + 3 · 8 ⁰ + 2 · 8 ⁻¹ = 88.5 ₁₀

esadecimale b = 16

a ⁱ ∈ {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, ¹⁰ A, ¹¹ B, ¹² C, D, ¹³ ¹⁴ E, ¹⁵ F}

70C.1 ₁₆ = 7 · 16 ² + 0 · 16 ¹ + 12 · 16 ⁰ + 1 · 16 ⁻¹ = 1804.06255 10

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 ₃

=

1 · 3 ² + 2 · 3 ¹ + 2 · 3 ⁰ + 1 · 3 ⁻¹

= 17.¯3 10

base qualunque ⇒ altra base

base qualunque ⇒ decimale ⇒ altra base

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 ₂

001 _| 111 _| 100 _| 101.100 _|2 1745.4 8

0011 _| 1110 _| 0101.1000 _|2 3E5.8 ₁₆

notazione più compatta

(4)

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 ₁₆

0101 _| 1011 _| 0000.1100 _|2 ottale ⇔ esadecimale

ottale ⇔ binaria ⇔ esadecimale

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 ⁱ tali per cui

M = m k b ^k + . . . + m ₂ b ² + m ₁ b ¹ + m ₀

eseguendo M/b si ottiene

quoziente m ^k b ^k ⁻¹ + . . . + m ₂ b ¹ + m ₁ resto m 0

iterando, finché il quoziente non vale 0, si trovano i valori numerici degli m ⁱ come resti della divisione per b

Parte frazionaria F - I

trovare f ⁱ tali per cui

F = f ₁ b ⁻¹ + f ₂ b ⁻² + . . . + f l b ^−l + . . .

eseguendo F × b si ottiene il prodotto f 1 + f 2 b ⁻¹ + . . . + f ^l b ^−(l−1) + . . .

| {z }

parte frazionaria

f 1 è la parte intera del prodotto ^a

iterando si trovano i valori numerici degli f ⁱ come parte intera del prodotto della parte frazionaria del passo precedente per b

a

si ricordi che F < 1

(5)

Parte frazionaria F - II

condizioni di terminazione

prodotto nullo numero finito di f ⁱ

prodotto già ottenuto in un passo precedente

numero infinito di f ⁱ ⇒ numero periodico nella base b

62.25 ₁₀ ⇒ X ₂

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 ₁₀ = 111110 ₂

62.25 ₁₀ ⇒ X ₂

parte frazionaria 0.25

prodotto intera

0.25 ×2 0.5 0

0.5 1.0 1

0.25 ₁₀ = 0.01 ₂

62.25 ₁₀ = 111110.01 ₂

55.3 ₁₀ ⇒ X ₂

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 ₁₀ = 110111 ₂

(6)

55.3 ₁₀ ⇒ X ₂

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 ₁₀ = 0.01001 ₂

55.3 10 = 110111.01001 2

2015.625 ₁₀ ⇒ X ₁₆

parte intera 2015

quoziente resto

2015 :16 125 15

125 7 13

7 0 7

2015 10 = 7DF 16

2015.625 ₁₀ ⇒ X ₁₆

parte frazionaria 0.625

prodotto intera

0.625 ×16 10.0 10

0.625 ₁₀ = 0.A ₁₆

2015.625 ₁₀ = 7DF.A ₁₆

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

(7)

Numeri interi

rappresentazione del segno e valore con N bit

metodi

ampiezza e segno

eccesso 2 ^N ⁻¹

complemento a 1

complemento a 2

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 ⁻¹

numero relativo M

rappresentato dalla codifica binaria del numero naturale M + 2 ^N ⁻¹

es. N = 5 ⇒ 2 ^N ⁻¹ = 16 ⇒ M + 16

N = 5

15 11111 14 11110

.. .

2 10010

1 10001

0 10000

-1 01111 -2 01110

.. . -15 00001 -16 00000

Complemento a 1

interi positivi

rappresentati come i primi 2 ^N ⁻¹ 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

(8)

Complemento a 2

interi positivi

rappresentati come i primi 2 ^N ⁻¹ 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

Proprietà complemento a 2

una sola rappresentazione dello 0

operazioni aritmetiche indipendenti dal segno 10 01 010 ¹

2 00010

12 01100

-2 ^{1 1} 1 1 ¹ 110 ¹ -1 11111 -3 11101

15 ^{1 1} 0 1111 ¹ -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 ¹ 111 ¹ 2 00010 17 10001

-2 ¹ 11110

−16 10000

−18 01110

a

carry bit: bit successivo a quello di segno

Numeri frazionari

notazione a virgola fissa (fixed point)

notazione a virgola mobile (floating point)

(9)

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

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 ⁻¹ ) mentre la base b (potenza di 2) viene implicitamente definita dal formato:

IEEE

IBM

Digital

posizione del punto di radice definita dal valore dell’esponente 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 ₂ ≤ m ≤ 1.11111111111111111111111 ₂ e “hidden bit”, i.e. il bit a sx del punto di radice non viene rappresentato (è sempre 1)

Formato IEEE (cont.)

modulo minimo=1 × 2 ⁻¹²⁶

modulo massimo = (2 − 2 ⁻²³ ) × 2 ¹²⁷

casi particolari

c bit22−0 = 0 6= 0 -127 0 non norm.

128 ∞ NAN ^a

a

Not A Number

(10)

Note floating-point

distanza tra due numeri

determinato dal valore del bit meno significativo della mantissa il quale dipende dalla caratteristica:

0.000000000000000000000001 ₂ × 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

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 ₁₀

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 ₁₀ = 1110101.00011 ₂

117.1 ₁₀

virgola fissa N = 32, M = 20

00000000000001110101000110011001 ₂ 00075199 ₁₆

formato IEEE

1110101.00011001100110011 2

1.11010100011001100110011 ₂ × 2 ⁶ c = 6 ⇒ 127 + 6 = 133 = 10000101 ₂ 0 _| 10000101 _| 11010100011001100110011 ₂

42EA3333 ₁₆

(11)

Binary Coded Decimal (BCD)

segno e ciascuna cifra di un numero decimale rappresentati separatamente con 4 bit

precisione arbitraria

−1350.1 ₁₀

=

11110001001101010000.0001 BCD

0 0000

1 0001

2 0010

...

8 1000

9 1001

+ 1010

- 1111

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

a₀

a₁

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 }

Unicode

(12)

Unicode (cont.)

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 Do it yourself

Si converta il seguente numero, dato in complemento a due, come numero relativo in base 9

1111000110

Si rappresentino in complemento a due a 10 bit e poi si sommino i numeri

−13 4 e 108 9

Si rappresenti il numero

93.625 10

nel formato floating-point IEEE

Considerato il numero

−748 10

lo si rappresenti in complemento a 2 con il minimo numero di bit

possibili.

Rappresentazione dell’informazione

Rappresentazione dell’informazione

Paolo Bison

Fondamenti di Informatica 1 A.A. 2004/05 Universit`a di Padova

informazione

tipo di informazione

 numerica

 non-numerica / simbolica

codifica binaria

[paolo@pcbison tmp]# dumpbin boh

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

Interpretazione dell’informazione

testo

[paolo@pcbison tmp]# od -t a boh

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.

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

il punto di radice separa termini associati a potenze positive da quelli associati a potenze negative

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 10

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, 10 A, 11 B, 12 C, D, 13 14 E, 15 F}

70C.1 16 = 7 · 16 2 + 0 · 16 1 + 12 · 16 0 + 1 · 16 −1 = 1804.06255 10

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

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

numerica

non-numerica / simbolica

informazione numerica

informazione simbolica

a k . . . a ₂ a ₁ a ₀ .a ₋₁ . . . a _−lb ^a (1) dove

la base b ∈ N e b ≥ 2,

le cifre a ⁱ sono simboli presi da un insieme S di b elementi in corrispondenza biunivoca con

v(a k )b ^k + . . . + v(a 1 )b ¹ + v(a 0 )b ⁰ + v(a ₋ 1 )b ⁻ ¹ + . . . + v(a _−l )b ^−l con v : S → D

a ⁱ ∈ {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}

103.24 ₁₀

1 · 10 ² + 0 · 10 ¹ + 3 · 10 ⁰ + 2 · 10 ⁻¹ + 4 · 10 ⁻²

1 · 2 ² + 1 · 2 ¹ + 0 · 2 ⁰ + 1 · 2 ⁻¹ + 1 · 2 ⁻²

6.75 ₁₀

a ⁱ ∈ {0, 1, 2, 3, 4, 5, 6, 7}

103.2 ₈ = 1 · 8 ² + 0 · 8 ¹ + 3 · 8 ⁰ + 2 · 8 ⁻¹ = 88.5 ₁₀

a ⁱ ∈ {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, ¹⁰ A, ¹¹ B, ¹² C, D, ¹³ ¹⁴ E, ¹⁵ F}

70C.1 ₁₆ = 7 · 16 ² + 0 · 16 ¹ + 12 · 16 ⁰ + 1 · 16 ⁻¹ = 1804.06255 10

si applica la definizione di sistema di numerazione 122.1 ₃

1 · 3 ² + 2 · 3 ¹ + 2 · 3 ⁰ + 1 · 3 ⁻¹

(esadecimale) corrispondente al loro valore 1111100101.10 ₂

001 _| 111 _| 100 _| 101.100 _|2 1745.4 8

0011 _| 1110 _| 0101.1000 _|2 3E5.8 ₁₆

011 _| 001 _| 101.111 _|2 5B0.C ₁₆

0101 _| 1011 _| 0000.1100 _|2 ottale ⇔ esadecimale

parte intera M

parte frazionaria F

trovare m ⁱ tali per cui

M = m k b ^k + . . . + m ₂ b ² + m ₁ b ¹ + m ₀

quoziente m ^k b ^k ⁻¹ + . . . + m ₂ b ¹ + m ₁ resto m 0

iterando, finché il quoziente non vale 0, si trovano i valori numerici degli m ⁱ come resti della divisione per b

trovare f ⁱ tali per cui

F = f ₁ b ⁻¹ + f ₂ b ⁻² + . . . + f l b ^−l + . . .

eseguendo F × b si ottiene il prodotto f 1 + f 2 b ⁻¹ + . . . + f ^l b ^−(l−1) + . . .

f 1 è la parte intera del prodotto ^a

iterando si trovano i valori numerici degli f ⁱ come parte intera del prodotto della parte frazionaria del passo precedente per b

prodotto nullo numero finito di f ⁱ

prodotto già ottenuto in un passo precedente

numero infinito di f ⁱ ⇒ numero periodico nella base b

62.25 ₁₀ ⇒ X ₂

62 ₁₀ = 111110 ₂

62.25 ₁₀ ⇒ X ₂

0.25 ₁₀ = 0.01 ₂

62.25 ₁₀ = 111110.01 ₂

55.3 ₁₀ ⇒ X ₂

55 ₁₀ = 110111 ₂

55.3 ₁₀ ⇒ X ₂