La Rappresentazione

La Rappresentazione

delle Informazioni

Rappresentazione dei caratteri:

la codifica ASCII

codice ASCII della lettera ‘A’

01000001

Q W E R T Y

A S D F G H

tastiera

• La Codifica ASCII serve a codificare i caratteri alfanumerici.

• È un sistema di codifica dei caratteri a 7 bit.

• Estensione ad 8 bit per raddoppiare il numero di caratteri rappresentabili (extended ASCII). In questo caso sono codificati simboli speciali per i diversi alfabeti quali lettere greche, lettere accentate, etc.

La Codifica ASCII: codifica tabellare

Come sequenza di codifiche ASCII la parola “CANE” sarà:

01000011 01000001 01001110 01000101

Per la decodifica si decompone la sequenza di bit in byte e si determina il carattere corrispondente ad ogni byte.

La Codifica Unicode

• E’ un sistema di codifica che assegna un numero (o meglio, una combinazione di bit) a ogni carattere in maniera indipendente dal programma, dalla piattaforma e dalla lingua (e dal suo sistema di scrittura).

• E’ compatibile col codice ASCII.

• Attualmente codifica i simboli di quasi tutti gli alfabeti moderni.

• Nato come codice a 16 bit (corrispondenti a 65536 caratteri diversi), per

permettere la rappresentazione della totalità dei caratteri si basa su tre

tipi di codifiche diverse: UTF-8 a 8 bit (1 byte), UTF-16 a 16 bit (word) e

UTF-32 a 32 bit (double word).

Rappresentazione dei numeri

„ Concetti da chiarire:

‰ Cardinalità di un insieme

„ è il numero totale di elementi da rappresentare :

l’inseme P = {0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15} ha cardinalità |P| = 16

l’insieme Q = ha cardinalità |Q|= 4

‰ Base della rappresentazione

„ Gli esseri umani contano in base 10 (probabilmente deriva dal numero delle dita)

„ I computer in base 2 (bit)

Quanti bit servono per memorizzare informazioni relative ai due insiemi?

n = log2 ( | . | )

n^Q= 2 corrispondenti a n^P= 4 corrispondenti a …??? Abbiamo bisogno di un metodo di codifica più

efficiente di quello tabellare visto con i caratteri

* Per approfondimento è possibile consultare

http://webuser.unicas.it/destefano/slides-fimc/3-rappresentazione-dell%27Informazione.pdf

Rappresentazione dei numeri

„

Tra i primi sistemi di numerazione abbiamo quello romano:

‰ Cifre Æ

‰ Sistema addizionale poco adatto per la rappresentazione di numeri molto grandi

‰ Non era rappresentato lo zero

‰ Operazioni complesse

„

Base di numerazione araba

‰ Cifre: 0 1 2 3 4 5 6 7 8 9

‰ È una rappresentazione posizionale

‰ possibile per la presenza dello zero

‰ Operazioni più semplici Esempio:

3201 =

(3x10³) + (2x10²) + (0x10¹) + (1x10⁰)

In generale

„

Rappresentazione in base B Æ B cifre

‰

0 1 2 … B-1

„

d

= { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 } in base 10

„

d

= { 0, 1 } in base 2

„

d

= { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, A, B, C, D, E, F } in base 16

„

Conversione verso la base decimale:

‰

d

d

... d

d

d

è un numero a 32 cifre

‰

valore = d

x B

+ d

x B

+ ... + d

x B

+ d

x B

+ d

x B

Esempio di conversione in base 10

„

da B=2 :

‰

cifre: 0 1

‰

1011010 Æ

1x2

+ 0x2

+ 1x2

+ 1x2

+ 0x2

+ 1x2 + 0x1 =

64 + 16 + 8 + 2 = 90 7 cifre binarie Æ 2 cifre decimali

„

da B=16 :

‰

cifre: 0 1 2 3 4 5 6 7 8 9 A B C D E F

‰

524 Æ

5x16

+ 2x16 + 4x1 = 1316

3 cifre esadecimali Æ 4 cifre decimali

Conversione esadecimale-binario

Siccome 16=2

, il passaggio tra le rappresentazioni

in base 2 e in base 16 è molto semplice:

10 16 2

00 0 0000

01 1 0001

02 2 0010

03 3 0011

04 4 0100

05 5 0101

06 6 0110

07 7 0111

08 8 1000

09 9 1001

10 A 1010

11 B 1011

12 C 1100

13 D 1101

14 E 1110

15 F 1111

3F9

0011 1111 1001

1111111001

Quale base usare ?

„

Decimale

‰

naturale per gli esseri umani.

„

Esadecimale

‰

utile (agli esseri umani) per esaminare lunghe stringhe di bit

„

Binaria

‰

rappresentazione ottimale per il calcolatore

… perché non usare una codifica

binaria della rappresentazione in

base 10 ?

Conversione base 10 Æ base 2 (interi)

„

Come ottenere la rappresentazione in base 2 di un numero intero T rappresentato in base 10 ?

„

Non si conoscono né le cifre né il numero di cifre.

„

Si divide il numero per la base e si prende il resto in ordine inverso.

Es.:

43/2 = 21 con resto 1

21/2 = 10 con resto 1 43

= 101011

10/2 = 5 con resto 0

5/2 = 2 con resto 1 2/2 = 1 resto 0

1

Aritmetica in base 2

Le operazioni aritmetiche si svolgono in maniera analoga a quanto si fa in base 10.

+ 0 1

0 0 1

1 1 10

* 0 1

0 0 0

1 0 1 “tavola pitagorica”

in base 2

Aritmetica in base 2

1 1

1 1 1 +

1 1 0 =

1 1 0 1

5 x

3

15

1 0 1 x

1 1 =

1 0 1

1 0 1

1 1 1 1

7 +

6

13

1 0 1 x

1 0 =

1 0 1 0

5 x

2

10

di una posizione!

Aritmetica dei registri

„

I registri di memoria sono supporti di lunghezza finita

„

Ciò impone delle restrizioni all’insieme di numeri rappresentabili e di conseguenza, dei vincoli all’aritmetica

„

Registro a N bit Æ 2

valori diversi rappresentabili

‰

Es.: 8 bit Æ 256 valori

possibile rappresentare l’intervallo [0,255]

1 2 3 ... N

Aritmetica dei registri

Non ci sono problemi nel caso in cui l’operazione produce un risultato rappresentabile nel registro

0 1 1 0 1 1 0 1 +

1 0 0 0 1 0 0 1 =

1 1 1 1 0 1 1 0

1 0 9 +

1 3 7 =

2 4 6

Aritmetica dei registri

Se l’operazione fornisce un risultato R non rappresentabile, si produce un riporto uscente dal registro, mentre all’interno rimane solo una parte della rappresentazione del risultato (ossia R mod 2

)

1 1 1 0 1 1 0 1 +

1 0 0 0 1 0 0 1 =

1 0 1 1 1 0 1 1 0

2 3 7 +

1 3 7 =

3 7 4

1 1 8

* Operazione di modulo consiste nel calcolare il resto della divisione tra due numeri:

A mod b = A - parte_intera( A div b) x b.

Es. 15 mod 7 = 15 – 2 x 7 = 1 dove parte_intera(15/7)= parte_intera(2,14) = 2

Rappresentazione dei numeri negativi

„ Dobbiamo tener conto del segno del numero.

„ La soluzione più immediata è quella di utilizzare un bit del registro come segno del numero. I restanti bit costituiscono il numero in valore assoluto.

„ L’intervallo di rappresentazione è [-2^N-1+1, +2^N-1-1].

„ La posizione del bit di segno diventa di notevole importanza.

„ Con questa rappresentazione si ha un’ambiguità nello 0. Lo zero può essere rappresentato sia dalla stringa tutti zero sia dalla stringa uno (come bit di segno) seguito da tutti zero.

„ Le operazioni diventano alquanto complicate. Somma e sottrazione sono operazioni nettamente diverse.

Possibile convenzione:

0 Æ + 1 Æ -

+/-

Rappresentazione in complemento alla base

„ Complementi alla base: i numeri aventi segno negativo sono rappresentati come complemento a 2 del numero rappresentato, ossia:

‰ La rappresentazione di un numero x nell’intervallo [0,2^N] è

x se x>= 0 RappB(x) =

2^N-x se x<0

o anche per le proprietà della rappresentazione su un registro lungo N:

Rapp(x)=(x+2^N) mod 2^N.

„ Il bit più significativo è indicativo del segno (“bit di segno”). In questo caso il valore 1 rappresenta il segno negativo.

„ L’intervallo di numeri rappresentati [-2^N-1,+2^N-1-1], asimmetrico.

Risolve l’ambiguità dello zero che viene rappresentato dalla stringa tutti zero mentre la stringa 1 e tutti zero ora rappresenta il -1.

Calcolo rapido del complemento alla base

„

Per ottenere rapidamente la rappresentazione in complemento alla base di un numero negativo su N bit

‰ si estrae la rappresentazione del valore assoluto del numero su N bit

‰ si complementano le cifre ad una ad una

‰ si aggiunge 1

„

Es.: complemento alla base su 8 bit di -33

33₁₀ =00100001 11011110+1=11011111

Si passa cioè dalla rappresentazione per complementi alla base diminuiti che corrisponde al complementamento ad 1 bit. Più rigorosamente la

rappresentazione per complementi alla base diminuiti è:

x se x>= 0

RappBD(x) =

(2

-1) - x se x<0

Operazioni in complemento alla base

„

Vantaggio dei complementi è che le operazioni di somma e differenza si realizzano eseguendo sempre delle somme:

„

Le addizioni si realizzano direttamente sulle rappresentazioni in quanto Rapp(x+y)= Rapp(x)+Rapp(y)

„

Anche le sottrazioni si valutano tramite addizioni, ponendo x-y come x+(-y); di conseguenza

R(x-y)=R(x)+R(-y)

„

Nel caso in cui l’operazione produce un numero al di fuori

dell’intervallo di rappresentazione si ha un overflow.

Operazioni in complemento alla base

+4 0100 +4 0100

+2 + 0010 -2 +1110

+6 0|0110 +2 1|0010

-4 1100 +5 0101 -6 1010

-2 + 1110 +4 +0100 -3 +1101

-6 1|1010 -7 0|1001 +7 1|0111

overflow

Rappresentazione per eccessi

„ Un altro metodo per la rappresentazione dei numeri interi è la rappresentazione per eccessi. In generale nella

rappresentazione per eccesso k il numero x viene rappresentato come RappE(x) = x+k

„ Per un registro di N bit l’intervallo di valori da rappresentare viene diviso in 2 (

2

2

2

rappresentazione di un numero x nell’intervallo è data da RappE(x) = x+2^N-1

„ Anche in questo caso il bit più significativo è indicativo del segno ma questa volta lo zero rappresenta i numeri

negativi.

„ L’intervallo di numeri rappresentati è [-2^N-1,+2^N-1-1].

Lo 0 è rappresentato dalla stringa 1 e tutti 0.

00000 -16

00001 -15

00010 -14

00011 -13

. .

. .

01110 -2

01111 -1

10000 0

10001 +1

10010 +2

. .

. .

11101 +13

11110 +14

11111 +15

Operazioni in eccessi

„

Le addizioni si realizzano direttamente sulle rappresentazioni in quanto RappE(x+y)=RappE (x)+RappE (y)

„

Anche le sottrazioni si valutano tramite addizioni, ponendo x-y come x+(-y);

RappE(x-y) = RappE(x) + RappE (-y)

ma dato che RappE(x)+RappE(y)=x+y+2

+2

il risultato necessita di una correzione (sottraendo un 2

)

„

Nel caso in cui l’operazione produce un numero al di fuori dell’intervallo di

rappresentazione si ha un overflow

Confronto tra complementi alla base ed eccessi

„

Entrambe permettono di realizzare una sottrazione tramite addizione (macchine aritmetiche più semplici).

„

Le operazioni in eccessi richiedono un aggiustamento finale.

„

La rappresentazione in complementi rende più difficile il confronto.

Rappresentazione dei numeri reali

„

La rappresentazione dei numeri reali in base 2 è completamente analoga a quella in base 10:

‰

Parte intera + parte frazionaria, separate da un punto

„

La parte frazionaria è formata da cifre che pesano le potenze di 2 a esponente negativo.

‰

Esempio: 110.0101

Æ 2

+2

+2

+2

= 6.3125

„

Conversione: si convertono separatamente la parte intera e quella frazionaria.

‰

Esempio: 6.3125

Æ 6

= 110

0.3125 x 2 = 0.6250 con parte intera 0

0.6250 x 2 = 1.2500 con parte intera 1 0101 0.2500 x 2 = 0.5000 con parte intera 0

0.5000 x 2 = 1.0000 con parte intera 1

Rappresentazione in virgola fissa

„ Si assume prefissata la posizione del punto all’interno del registro (fixed point)

p = 4 N = 8

„ Con questa convenzione, il valore x rappresentato nel registro è k*2^-p, dove k è il valore che otterremmo se interpretassimo come un intero il contenuto del registro.

„ Qual è l’insieme dei valori rappresentabili su un registro a N bit ? k: 0,1,2,…,2^N-1 Æ x: 0, 2^-p, 2*2^-p, …, (2^N-1)*2^-p

Esempio: N=8, p=4

x = 0, 0.0625, 0.125, 0.1875,…, 15.9375

I numeri sono rappresentati con una certa approssimazione (ricordiamo la

quantizzazione uniforme: l’errore della rappresentazione equivale a metà intervallo) Esempio:

Tutti i valori compresi tra 0.03125 e 0.09375 sono rappresentati da 0.0625

Tutti i valori compresi tra 0 e 0.03125 sono rappresentati da 0.0000 Æ underflow

p N

Esempio di numero in virgola fissa

Supponiamo di voler rappresentare il numero 22.315 in virgola fissa in un registro ad 8 bit con p=3.

Separiamo parte intera e parte frazionaria:

22

Æ 10110

0.315

Æ 0.010100…

1 0 1 1 0 0 1 0 Posizione del punto

p=3

Virgola fissa con segno

„

La codifica dei numeri relativi in complementi alla base si

applica in maniera immediata ai numeri reali rappresentati in virgola fissa.

„

La rappresentazione di un numero reale con segno (N bit, punto in posizione p) si ottiene tramite la regola:

dove R(x) è la rappresentazione in virgola fissa di x

R(x) se x ≥ 0

b

- R(x) se x < 0

Virgola fissa con segno

Esempio (N=8, p=3):

R(-3.7) = 2

-R(3.7) Æ

1 0 0 0 0 0 0 0 0 - 0 0 0 1 1 1 0 1 1 1 1 0 0 0 1 1

R(-3.7)

Virgola fissa con segno

„

Possiamo comunque applicare il criterio già visto per ottenere velocemente la rappresentazione in complementi alla base:

„

Per ottenere R(-3.7) si considera R(3.7) e si complementa cifra per cifra aggiungendo 1 al bit meno significativo:

R(3.7)

1 1 1 0 0 0 1 0 +

1

1 1 1 0 0 0 1 1

0 0 0 1 1 1 0 1

Precisione della virgola fissa

L’errore massimo assoluto della rappresentazione si commette nel

rappresentare il numero più piccolo diverso da 0, ed equivale al primo semi intervallo:

Err_max= 2^-p/2

per p=4 Err_max= 0.03125

Come fare per diminuire l’errore ?

basta aumentare p…. In queto modo però si riduce il range dei numeri rappresentabili.

Se al contrario si aumenta il range dei valori (N grande p piccolo) si riduce la precisione.

Per migliorare globalmente la

rappresentazione bisogna ridurre l’errore

relativo Æ

numeri enormi non hanno bisogno di una grande precisione, mentre numeri piccoli si.

Raggio della terra = 6378,388 Km (+/- 0.00001 mm)!!??!

Raggio dell’atomo di idrogeno = 53 x 10^-12m

0%

5%

10%

15%

20%

25%

30%

35%

40%

45%

50%

0 32 64 96 128 160 192 224 256

Rappresentazione

Errore relativo

E_rel=Err_max/x

- 2^-p/2 0 2^-p/2

Vantaggi e svantaggi della virgola fissa

„

vantaggi

‰

Semplicità

‰

Piena compatibilità con la rappresentazione degli interi e possibilità di usare circuiti aritmetici comuni.

„

svantaggi:

‰

Errore relativo elevato per x prossimi a zero

‰

Compromesso range/precisione

‰

Entrambi legati al fatto che il fattore di scala è fisso.

Rappresentazione in virgola mobile

„

Si potrebbero mitigare i problemi andando a rappresentare esplicitamente il fattore di scala.

„

In questo modo la virgola non è più “fissa”, ma diventa “mobile”.

„

Fissata la base b, il valore viene considerato nella forma M*b

(notazione scientifica) ed è rappresentato tramite la coppia (M,E) Esempio: 22.315=0.22315*10

Æ (0.22315,2)

10110.010=10.110010*2

Æ (10.110010,11)

„

Nel registro saranno quindi prefissate zone diverse per la mantissa

e per l’esponente.

Rappresentazione in virgola mobile

„

Solitamente M viene rappresentato come numero reale in virgola fissa e in segno e modulo mentre E si rappresenta come numero intero con segno per eccessi.

„

M è rappresentato su m bit con p cifre frazionarie M:

0, 2

, 2*2

, …, (2

-1)*2

mentre E è rappresentato su e bit E: -2

,…-1,0,1, …,+2

-1.

Gli estremi dell’intervallo, quindi, sono:

N

=M

*2

= 2

*2

N

=M

*2

= (2

-1)* 2

*2

Esempio sulla virgola mobile

Rappresentazione in FP di –12.6:

12.6

= 1100.1001

= 0.11001001 * 2

Segno: 1

Mantissa: 0.11001001100110011001100 Esponente: 4+128 = 132

= 10000100

1 1 0 0 0 0 1 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1

Rappresentazione normalizzata

„

Con la virgola mobile non la rappresentazione non è unica:

N = M*2

= (M*2)*2

= (M*4)*2

= (M/2)*2

„

Il numero più piccolo rappresentabile viene modificato in funzione di p, posizione della virgola

N

= 2

*2

*2

„

Quale scegliere?

Quella che ha la prima cifra della mantissa diversa da 0

Æ rappresentazione normalizzata

Rappresentazione normalizzata

„

Esempio: N = 0.0003241892 mantissa a 5 cifre decimali

„

Diverse rappresentazioni possibili:

0.00032*10

0.00324*10

0.03241*10

0.32418*10

Å normalizzata

Poiché in bit la prima cifra dopo la virgola è sempre 1 si

decide di non rappresentarla per evitare la ridondanza ed

avere a disposizione un bit in più.

Rappresentazione normalizzata

„

Valutiamo l’errore di approssimazione:

‰

Errore assoluto massimo è

Err

= (2

/2)*2

‰

Errore relativo:

E

= Err

/x

Questa volta varia in funzione dell’esponente: l’errore commesso su numeri grandi è

proporzionale a 2^E mentre quello commesso nelle vicinanze dello zero è proporzionale a 2^-E

„

Pro

‰ Precisione variabile a seconda del numero rappresentato: alta per numeri piccoli e bassa per numeri alti: 100+--0.5 ; 0.57 + - 0.005 ; 10¹⁷ +-10¹²

„

Contro

‰ Underflow più frequente nella rappresentazione normalizzata

perché abbiamo fissato la rappresentazione del numero più piccolo a 1.0000000000…x 2^-E

Per poter rappresentare con maggiore precisione i valori prossimi allo 0 la rappresentazione viene denormalizzata

Lo standard IEEE754

„

Tre formati:

‰

Singola precisione (32 bit: 23 bit mantissa + 8 bit esp. + 1 bit segno)

‰

Doppia precisione (64 bit: 52 bit mantissa + 11 bit esp. + 1 bit segno)

‰

Quadrupla precisione (128 bit: 112 bit mantissa + 15 bit esp. +

1 bit segno)

Operazioni in floating point

„

Molto più complicate rispetto agli interi e alla virgola fissa

„

Diverse operazioni necessarie:

‰

Denormalizzazione per allineare i valori all’esponente più alto

‰

Sommare le mantisse

‰

Normalizzare il risultato e verificare se si è in under/overflow

‰

Arrotondare se necessario

„

Se i segni sono diversi, bisogna calcolare la differenza tra le mantisse e determinare il segno del risultato

„

Operazioni troppo complesse per poter essere effettuate

con l’unità aritmetica per gli interi.