A hie adeg

3 - Rappresentazione dell'Informazione

Ugo DalLago

DipartimentodiS ienzedell'Informazione

UniversitàdegliStudidiBologna

Anno A ademi o2007/2008

◮

I al olatorigestis ono informazionidivaria natura: testi,

immagini, suoni, lmati,et .

◮

I al olatori,però,lavoranouni amente onsequenze dibit.

◮

Risultaquindi ne essaria di un'opportuna odi a.

◮

Esamineremole odi hedei datipiùsempli i: numeri e

aratteri.

◮

Glis hemidi odi adevono essere:

◮

ompatti,ovveronondevonoutilizzarerappresentazioni

troppopiùlunghedellostrettone essario.

◮

prati i,ovverodevonofa ilitarela omputazione.

◮

fedeli,ovverodevonoevitarediperdereinformazione.

◮

Partiamo daun insiemedidati rappresentabili D.

◮

Abbiamo adisposizioneun alfabetonito A.

◮

Consideriamoparolenell'alfabetoA, ovverosequenze di

simbolinell'alfabeto. Indi hiamo onA

∗

l'insieme ditutte le

parolenite nell'alfabetoA.

◮

Una funzione di odi aD

→

^A

^∗

^{è una mappainiettiva}

dallo spaziodei dati nell'insiemedelleparoledell'alfabeto.

◮

Se A ontiene k simboli, onparoledilunghezza n si possono

rappresentare k n

oggetti diversi.

◮

Esempi:

◮

D

N

èl'insiemedeinumerinaturali,A

10

= {

⁰

,

¹

,

²

, . . . ,

⁹

}

^è

l'alfabetoelafunzionedi odi aasso iaadogninumero

naturalelasuarappresentazionein base10.

◮

D

N

èl'insiemedeinumerinaturali,A

2

= {

⁰

,

¹

}

^{èl'alfabetoe}

lafunzionedi odi aasso iaadogninumeronaturalelasua

rappresentazione inbase2.

◮

D

P

èl'insiemedelleparoleinusonellalinguaitaliana,

A

P

= {

^a

,

^b

,

, . . . ,

^u

,

^v

,

^z

,

^à

,

^è

,

^é

,

^ì

,

^ò

,

^ù

}

^{elafunzionedi odi a}

◮

Neisistemidi al olo,l'alfabeto diriferimentoè A 2

= {

⁰

,

¹

}

^.

◮

Inoltre, ssatounsistema di al olo,laquantità di memoria a

disposizionesarà sempre nita,esarà quindipossibileavere a

disposizionesolole sequenzein A

∗

2

lunghe alpiùk.

◮

Ciòsigni a,in parti olare, hein untipi osistema di al olo

nonè possibiletener tra iadi tuttiinumeri naturali!

◮

Di onseguenza, o orre onsideraresottoinsieminiti

dell'insiemeD

N

dei numerinaturali: D k

N

sarà l'insiemedei

numeri naturali rappresentabili onk ifre.

◮

D 3

N

ontiene156,932,...

◮

D 8

N

ontienetuttiinumerinaturaliinferiorialmiliardo.

◮

D k

N

nonè mai hiusorispettoalle operazioni aritmeti he

+ , −

oltre he a

×, /

^.

◮

Possiamoottenerenumeritroppograndi(overow ),oppure

troppopi oli(underow ).

◮

Da quiin poi,studieremoi sistemidi numerazioneposizionale.

◮

La odi apiù omune perinumeri interiè la odi a

de imaleposizionale,in uil'alfabetoutilizzato è

A

10

= {

⁰

,

¹

,

²

, . . . ,

⁹

}

^.

◮

Lageneri a sequenza d

k

. . .

^{d2d1d0 odi a ilnumero intero:}

X

k

i

=

⁰

d

i

×

¹⁰ⁱ

◮

Ininformati a,altre odi heposizionalisonopiùimportanti:

◮

La odi abinaria,in uil'alfabetoutilizzatoèA

2

= {

⁰

,

¹

}

^.

◮

La odi aottale,in uil'alfabetoutilizzatoè

A

8

= {

⁰

,

¹

,

²

,

³

,

⁴

,

⁵

,

⁶

,

⁷

}

◮

La odi aesade imale,in uil'alfabetoutilizzatoè

A

16

= {

⁰

,

¹

,

²

,

³

,

⁴

,

⁵

,

⁶

,

⁷

,

⁸

,

⁹

,

^A

,

^B

,

^C

,

^D

,

^E

,

^F

}

^{. Isimboli}

A

,

^B

,

^C

,

^D

,

^E

,

^F orrispondonoa10

,

¹¹

,

¹²

,

¹³

,

¹⁴

,

^15,

.

Binary

Octal

Decimal

Hexadecimal

1 1 1 1 1 0 1 0 0 0 1

7 D 1

1 × 2 ¹⁰ + 1 × 2 ⁹ + 1 × 2 ⁸ + 1 × 2 ⁷ + 1 × 2 ⁶ + 0 × 2 ⁵ + 1 × 2 ⁴ + 0 × 2 ³ + 0 × 2 ² + 0 × 2 ¹ + 1 × 2 ⁰

3 7 2 1

3 × 8 ³ + 7 × 8 ² + 2 × 8 ¹ + 1 × 8 ⁰

2 0 0 1

2 × 10 ³ + 0 × 10 ² + 0 × 10 ¹ + 1 × 10 ⁰

+ + +

7 × 16 ² + 13 × 16 ¹ + 1 × 16 ⁰ 1792 + 208 + 1

1

0 16 0 0 0

1 16

64 128 256 512

+ + + +

+ + +

+ + + + + +

1024

448 1536

2000 0 0 1

◮

Due parole (inalfabetidiversi)sono equivalentise odi ano

lo stessonumero naturale.

◮

Convertireuna sequenza signi a trovareuna parola (inun

alfabetodiverso) equivalentealla prima.

◮

Convertireunnumero in notazioneottaleo esade imalein

notazionebinaria (o vi eversa)è moltosempli e.

◮

Se siparteda unnumero innotazionede imalee losi vuole

onvertire in notazionebinariasi puòpro edereper divisioni

su essive.

◮

Vi eversa,un numeroin notazionebinaria puòessere

onvertitoin notazionede imale pro edendoper

moltipli azionisu essive.

◮

Comunque, è semprepossibileutilizzareladenizionevista in

pre edenza: una sequenza s

k

. . .

^{s2s1s0 in baseb odi ail}

numero naturale

X

k

i

=

⁰

s

i

×

^bi

Example 1

Hexadecimal Binary Octal

Hexadecimal Binary

Octal Example 2

1

1

9 4

4

4

8 B

B 6

1

4

4 5

5

0

0 7

7 7

A

B C

5 5

5 6

4

3

3

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

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

. . .

.

.

.

Quotients Remainders

1 4 9 2 7 4 6 3 7 3 1 8 6 9 3 4 6 2 3 1 1 5 2 1 0

1 0 0

0 1

1 1 1

1 0

0

1 0 1 1 1 0 1 0 1 0 0 = 1492 ₁₀

1 + 2 × 1499 = 2999 0

1 1 1 1 0 1 1 0 1 1 1

Result 1 + 2 × 749 = 1499

1 + 2 × 374 = 749 0 + 2 × 187 = 374 1 + 2 × 93 = 187 1 + 2 × 46 = 93 0 + 2 × 23 = 46 1 + 2 × 11 = 23 1 + 2 × 5 = 11 1 + 2 × 2 = 5 0 + 2 × 1 = 2

1 + 2 × 0 = 1 Start here

◮

Esistonoun erto numero dis hemidi odi aperla

rappresentazionedei numeribinari onsegno.

◮

Nellos hemadetto modulo e segno,si utilizzailbitpiù

signi ativo(quellopiù asinistra) ome bit disegno (0 peril

+

^{e 1 per il}

−

^).

◮

An he nelsistema detto omplementoa uno siusa ilbit di

segno. Neinumerinegativi, però, o orre invertiretutti gli

altribit.

◮

Nelsistema detto omplemento aduesi usa sempreilbit di

segno. Perinumeri negativi,o orre invertireglialtri bit,e

poi siaggiunge1 alrisultato.

◮

Esiste poiilsistema ine esso di 2 k

−

¹

per numeridi k bit.

Ogni numero (positivoonegativo) viene rappresentato dal

numero binarioottenutoaggiungendo 2 k

−

¹

alnumero di

partenza.

◮

Adesempio,se sivuole rappresentare

−

^{6 on8bit in}

omplemento adue, siparteda 6in binario:

00000110

,

si passaa

−

⁶ⁱⁿ omplementoauno:

11111001

,

e siarrivaa

−

^{6 in} omplemento adue:

11111010

.

◮

Data una stringain omplementoadue, di iamo

s

k s

k

−

¹

. . .

^s1 s

0

,ilnumero daessarappresentato èottenuto

mediantelaformula:

−

^sk

×

^2k

+

k

−

¹

X

i

=

⁰

s

i

×

²ⁱ

◮

L'intervallo di numerirappresentabili dipende dalsistema

utilizzatoe dalnumero di bita disposizione. Supponiamonel

seguito diutilizzarek bit.

◮

Ladimensionedell'intervallorappresentabile res e

esponenzialmente onk.

◮

Se iinteressano soloi numerinaturali, possiamo

rappresentare l'intervallo ompreso tra 0e 2 k

−

^1.

◮

Sek

=

⁸l'intervallosaràquellotra0e255.

◮

Se siutilizzala odi a moduloe segno o la odi a

omplementoa uno si potranno rappresentarei numeritra

−

^2k

⁻

¹

+

^{1 e2k}

⁻

¹

−

^{1. In}parti olare, i saranno duestringhe binarieentrambe orrispondenti a0.

◮

Sek

=

⁸l'intervallosaràquellotra

−

^127e

+

^127.

◮

Se siutilizzala odi a omplemento adueo la odi aad

e esso sipotranno rappresentarei numeritra

−

^2k

⁻

^{1 e}

2

k

−

¹

−

^{1,visto heuna solastringabinaria} orrispondea0.

◮

Sek

=

⁸l'intervallosaràquellotra

−

^128e

+

^127.

Addendo 0+ 0+ 1+ 1+

Addendo 0= 1= 0= 1=

Somma 0 1 1 0

Riporto 0 0 0 1

◮

Lasomma aritmeti atra duenumeri in notazionebinaria si

eettuaseguendo unpro edimento inusonell'aritmeti a

de imale.

◮

Nell'aritmeti a in omplemento auno,ilriportogenerato dai

due bitpiùsigni ativi vienesommatoalbit meno

signi ativo.

◮

Nell'aritmeti a in omplementoadue, ilriportogenerato

dallasomma deibit piùsigni ativiviene sempli emente

s artato.

◮

Perquanto riguardal'overow :

◮

Segliaddendi hannosegnooppostononsièveri ato

overow.

◮

Segliaddendi hannolostessosegnoeilrisultatohasegno

opposto,si èveri atooverow.

◮

Segliaddendi eilrisultato hannotuttilostessosegno, siha

overowse esolose ilrisultatoin orrispondenzadelbitdi

Decimal 1's complement 2's complement

10 + ( − 3) +7

00001010 11111100 1 00000110

carry 1 00000111

00001010

11111101

1 00000111

discarded

◮

Generalizzare isistemi heabbiamo introdottoanumeri on

virgolanonè di ile.

◮

Laposizionedellavirgolaèssataapriori,altrimentirisulta

impossibileeseguireoperazioniaritmeti heinpre isionenita.

◮

Spessol'intervallo dei numeriutilizzatiè moltogrande.

◮

Intal aso,l'impiegodinumeri onvirgolassadiventa

problemati o. Avremmobisognoditantissimibit,an hesele

ifre signi ativenonsono osìtante.

◮

Abbiamo bisognodi sistemadi rappresentazione dei numerinel quale l'intervallodei numerirappresentabilinon dipenda dal

numero di ifresigni ative

◮

Abbiamobisognodei numeri onvirgolamobile!

◮

Un modoperrappresentare ilnumer n disa oppiando

l'intervallodallapre isione onsistenell'esprimere ilnumero n

ome segue:

n

=

f

×

^10e

dove f è hiamatofrazioneo mantissae e è hiamato

esponente o aratteristi a.

◮

Esempi:

3

,

¹⁴

=

⁰

,

³¹⁴

×

¹⁰¹

=

³

,

¹⁴

×

¹⁰⁰

0

,

⁰⁰⁰⁰⁰¹

=

0

,

¹

×

¹⁰

⁻

⁵

=

1

,

⁰

×

¹⁰

⁻

⁶

1941

=

⁰

,

¹⁹⁴¹

×

¹⁰⁴

=

¹

,

⁹⁴¹

×

¹⁰³

◮

Supponiamodi rappresentare:

◮

Lafrazionef on0oppure onun valore onsegnoatre ifre

tale he0

,

¹

≤ |

^f

| <

^1.

◮

L'esponenteèunvalore onsegno adue ifre.

◮

Queste rappresentazionivariano,in modulo,da 0

,

¹

×

¹⁰

⁻

^{99 a}

0

,

⁹⁹⁹

×

^{1099,mari hiedonosolamente inque ifrede imali!}

1 Negative overflow

2 Expressible negative numbers

3 Negative underflow

4 Zero

5 Positive underflow

6 Expressible positive numbers

7 Positive overflow

—10 ¹⁰⁰ —10 ^—100 0 10 ^—100 10 ¹⁰⁰

◮

Un'operazione he oinvolgadue numeriin virgolamobile può

produrre:

◮

Unerrore di overow, seilrisultatoètroppograndeper

essereespressoinvirgolamobile.

◮

Unerrore di underow,seilrisultato ètroppopi oloper

essereespressoinvirgolamobile.

◮

Sappiamo poi he:

◮

Inumerirealisonodensi: datiduerealix ey tali hex

<

^y

esisteunaltronumerorealez onx

<

^z

<

^y.

◮

Inumeriinvirgolamobilesonoun sistemadis reto, hepuò

esprimereunaquantitànitadinumerireali. Peresempio

dividendo0

,

¹⁰⁰

×

^{103per3otteniamoun reale henonè}

esprimibilenelsistemaequindivaarrotondato.

◮

Le onsiderazioniappena fattevalgonoan he quandoil

numero di ifreriservatealla mantissae ilnumero di ifre

riservateall'esponente ambiano.

◮

In on reto, mantissa ed esponentesono rappresentati da ifre

binarie. In tal asoparliamodi mantissanormalizzataquando

2 ^–1 2 ^–2

Unnormalized:

Sign +

Excess 64 exponent is 84 – 64 = 20

Fraction is 1 × 2 ^–12 + 1 × 2 ^–13 +1 × 2 ^–15 + 1 × 2 ^–16

Normalized:

Example 1: Exponentiation to the base 2

= 2 ²⁰ (1 × 2 ^–12 + 1 × 2 ^–13 + 1 × 2 ^–15 + 1 × 2 ^–16 ) = 432

= 2 ⁹ (1 × 2 ^–1 + 1 × 2 ^–2 + 1 × 2 ^–4 + 1 × 2 ^–5 ) = 432

= 16 ⁵ (1 × 16 ^–3 + B × 16 ^–4 ) = 432 To normalize, shift the fraction left 11 bits and subtract 11 from the exponent.

Sign +

Excess 64 exponent is 73 – 64 = 9

Fraction is 1 × 2 ^–1 + 1 × 2 ^–2 +1 × 2 ^–4 + 1 × 2 ^–5

Sign +

Excess 64 exponent is 69 – 64 = 5

Fraction is 1 × 16 ^–3 + B × 16 ^–4 2 ^–3

2 ^–4 2 ^–5

2 ^–6 2 ^–7

2 ^–8 2 ^–9

2 ^–10 2 ^–11

2 ^–12 2 ^–13

2 ^–14 2 ^–15

2 ^–16

0

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

1

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

Normalized: = 16 ³ (1 × 16 ^–1 + B × 16 ^–2 ) = 432

To normalize, shift the fraction left 2 hexadecimal digits, and subtract 2 from the exponent.

Sign +

Excess 64 exponent is 67 – 64 = 3

Fraction is 1 × 16 ^–1 + B × 16 ^–2 0

0 1 0 0 0 0 1 1 0 0 1 1 0 1 1 0 0 0 0 0 0 0 0 Example 2: Exponentiation to the base 16

Unnormalized: 0 1 0 0 0 1 0 1 0 0 0 0 16 ^–1

0 0 0 0 16 ^–2

0 0 0 1 16 ^–3

1 0 1 1 16 ^–4

.

.

.

.

◮

Quando l'insiemedei datida rappresentareè l'insiemedelle

parolein un ertolinguaggio naturale,o orre primadi tutto

apire omesi odi ano i singoli aratteri,le singolelettere.

◮

Il primotentativo fuil odi eASCII(Ameri anStandardCode

forInformationInter hange).

◮

Ogni arattereè odi atodauninteroa7bit.

◮

Intotale,quindi,abbiamo128 aratteri distinti.

◮

Diversi linguagginaturali, però, utilizzano insiemidi aratteri

diversi. Perquesto motivo siintrodusseil on etto di ode

page,

◮

Uninsiemedi256 aratterispe i odiunalinguaodi un

gruppodilingue.

◮

Il odi edestinatoadiventare lostandardè hiamato UNICODE.

◮

Adogni arattereèasso iataunasequenzadi16bit hiamata

odepoint.

◮

A ias unalfabetoèasso iatouninsiemedi odepointtraloro