Rappresentazione dell’informazione Paolo Bison

(1)

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

₂

a

₁

a

₀

.a

₋₁

. . . 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(ak)b^k+ . . . + v(a1)b¹+ v(a0)b⁰+ v(a−1)b⁻¹+ . . . + 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

Sistemi di numerazione

decimale b = 10

a

_i

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

103.24

10

=

1 · 10

²

+ 0 · 10

¹

+ 3 · 10

⁰

+ 2 · 10

⁻¹

+ 4 · 10

⁻²

binario b = 2 a

_i

∈ {0, 1}

110.11

₂

=

1 · 2

²

+ 1 · 2

¹

+ 0 · 2

⁰

+ 1 · 2

⁻¹

+ 1 · 2

⁻²

=

6.75

₁₀

(2)

Sistemi di numerazione (cont.)

ottale b = 8

a

_i

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

103.2

₈

= 1 · 8

²

+ 0 · 8

¹

+ 3 · 8

⁰

+ 2 · 8

⁻¹

= 88.5

₁₀

esadecimale b = 16

a

_i

∈ {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

2

001

_|

111

_|

100

_|

101.100

_|2

1745.4

₈

0011

_|

1110

_|

0101.1000

_|2

3E5.8

₁₆

notazione più compatta

(3)

Ottale (Esadecimale) ⇒ Binaria

si scrive il valore delle cifre ottali (esadecimali) in binario utilizzando tre (quattro) bit

315.7

₈

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

₁₀

si converte separatamente:

parte intera M

parte frazionaria F

Parte intera M

trovare m

_i

tali per cui

M = m

_k

b

^k

+ . . . + m

₂

b

²

+ m

₁

b

¹

+ m

₀

eseguendo M/b si ottiene

quoziente m

_k

b

^k−1

+ . . . + m

₂

b

¹

+ m

₁

resto m

₀

iterando, finché il quoziente non vale 0, si trovano i valori numerici degli m

_i

come resti della divisione per 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

₂

(4)

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

2

2015.625

₁₀

⇒ X

₁₆

parte intera 2015

quoziente resto

2015 :16 125 15

125 7 13

7 0 7

2015

₁₀

= 7DF

₁₆

Parte frazionaria F - I

trovare f

_i

tali per cui

F = f

₁

b

⁻¹

+ f

₂

b

⁻²

+ . . . + f

_l

b

^−l

+ . . .

eseguendo F × b si ottiene il prodotto f

₁

+ f

₂

b

⁻¹

+ . . . + f

_l

b

^−(l−1)

+ . . .

| {z }

parte frazionaria

f

₁

è 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

asi 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

(5)

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

₁₀

= 110111.01001

₂

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

(6)

Numeri interi

rappresentazione del segno e valore con N bit

metodi

ampiezza e segno

eccesso 2

^N−1

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−1

numero relativo M rappresentato dalla codifica binaria del numero naturale M + 2

^N⁻¹

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

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

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

(7)

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

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

Proprietà complemento a 2

una sola rappresentazione dello 0

operazioni aritmetiche indipendenti dal segno 10 01

1

010

2 00010

12 01100

- 2

^{1 1}

1 1

¹

110

¹

-1 11111

-3 11101

15

^{1 1}

0 1111

¹

-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 bit

^a

< minimo: riporto sul carry bit, ma non su quello di segno

15

1

0 1

¹

111

¹

2 00010 17 10001

- 2

¹

11110

−16 10000

−18 01110

acarry bit: bit successivo a quello di segno

Numeri frazionari

sottoinsieme dei numeri reali

codifiche

notazione a virgola fissa (fixed point)

notazione a virgola mobile (floating point)

(8)

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

basato sulla notazione scientifica

−1.5 × 10

⁵

−15.0 × 10

⁴

0.3 × 10

⁻²

3.0 × 10

⁻³

formato IEEE

si esprime il numero frazionario nella forma m × 2

^c

si rappresentano in maniera separata la mantissa m in virgola fissa e la caratteristica c

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

cbit22−0

= 0 6= 0 -127

^a

0 non norm.

128

^b

∞ ^NAN

^c

a00000000

b11111111

cNot A Number

(9)

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

aritmetica

se a >> b , a + b = a

overflow

valore in modulo superiore al massimo rappresentabile

underflow

valore in modulo inferiore al minimo rappresentabile

117.1

₁₀

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

₁₆

(10)

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

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)

UNICODE (32 bit, 96447 simboli) www.unicode.org

ASCII

a0a1 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

Unicode

(11)