Lezione  IX                      FRAMES  NOFRAMES

Rappresentazione dell informazione

 

I dati (numeri interi, numeri reali, caratteri,) su cui gli elaboratori operano vengono codificati in quanto possono appartenere ad un qualsiasi insieme. Iniziamo considerando i sistemi di numerazione per rappresentare interi, reali e caratteri.

 

Sistemi di numerazione ed algoritmi di conversione

 

Un sistema di numerazione un metodo che associa ad ogni numero (ente matematico che pu essere rappresentato mediante una stringa di caratteri, detti  cifre ,di un alfabeto fissato) un unico  numerale  ( sequenza di cifre ). Ad esempio 1621 , MDCXXI sono due numerali per il medesimo numero, appartenenti a due sistemi di numerazione diversi, rispettivamente la numerazione araba e la numerazione romana.

MDCXXI scritto usando un tipo di sistema additivo, cio basato su un principio puramente additivo di numerazione, che usa le cifre  I V X L C M;  infatti il numerale in questione rappresenta il valore : mille+cinquecento+cento+dieci+dieci+uno = milleseicentoventuno. E un sistema non posizionale; quindi di difficile rappresentazione.

1621 un numerale nel sistema decimale arabo che un sistema di tipo posizionale; cio ogni cifra ha un peso diverso in base alla sua posizione nella stringa. Infatti noi possiamo scrivere :

1621 = 1x10^3 + 6x10^2 + 2x10^1 + 1x10^0

8,42 = 8x10^0 + 4x10^-1 +2x10^-2

Il peso calcolato usando una base che in questo caso 10 e le cifre sono 0,1,2,,9.

Apriamo una piccola parentesi per sottolineare che 1621 un numero intero senza segno, ossia formato dai numeri naturali ((1,2,3,.) + lo zero), 8,42 un numero reale e che MDCXXI appartiene ai sistemi non posizionali, che hanno regole proprie e per questo rendono molto complessa l esecuzione dei calcoli.

Sistemi posizionali

 

In generale consentono di rappresentare i numeri in modo compatto e per questo i calcoli possono essere effettuati in modo molto semplice; essi sono distinti dalla base b .

Un numerale in generale lo si indica con  Cn-1 Cn-2 C1 C0 dove le cifre  Ck { 0,1,,b-1 } con k= 0,,n-1

Il peso della cifra Ck = b^k con k = 0,1,,n-1

Numero = Cn-1* b^n-1 + Cn-2*b^n-2 + ...+ C1*b^1 + C0

Il numero ottenuto con il polinomio in b rappresentato dal numerale : (Cn-1 Cn-2 C1 C0 ) in base b.

Es.

( 1621 ) in base 10 coincide con 1x10^3 + 6x10^2 + 2x10^1 + 1

Il valore di un numero num espresso nella notazione posizionale e dato dalla seguente formula :

n-1

num = Ck x b^k

k=0

dove b la base

e Ck ( con k= 0,1,...,n-1 ) sono le cifre (comprese fra 0 e b-1)

Una sequenza di cifre non interpretabile se non viene precisata la base in cui espressa.

Esempi in tabella di numeri interi:

 

stringa

base

alfabeto

Calcolo del valore

valore

15

2

{0,1}

1*2^3 + 1*2^2 + 1*2^1+1

1111

15

8

{0,1,2,.,7}

1*8^1 + 7*8^0

17

15

10

{0,1,2..,9}

1*10^1 + 5*10^0

15

15

16

{0,1,2,9,A,,F}

0*16^1 +F*16^0

0F

 

Sistema binario

Il sistema binario posizionale in base b=2; le cifre o simboli dellalfabeto sono {0,1}

Il numero 12 coincide con (1100) in base 2 che uguale a 12 in base 10.

1100 = 1x2^3 + 1x2 ^2 + 0x2^1 + 0x2^0

certamente noto che qualsiasi numero elevato a zero fa 1. 

I calcoli sono stati eseguiti in base 10.

 

link a programma di conversione in binario

 

Cambiando base si ottengono altri sistemi significativi in informatica.

Se b=8  ottengo il  sistema ottale  costituito dalle cifre                { 0,1,2,3,4,5,6,7}.

Il numero 12  in base 10 corrisponde al numero 14 in base 8: infatti   1x8^1 + 4X8^0

Se b=16 ottengo il sistema esadecimale costituito dalle cifre :

{ 0,1,2,3,4,5,6,7,8,9,A,B,C,D,E,F } dove A rappresenta il valore numerico 10, B l 11, C il 12, D il 13, E il 14 ed F il 15.

Il  12 in base 16 equivale alla C .

B1F : 11x16^2 + 1x16^1 + 15x16^0  ossia 2847 in base 10

 

(20) 16 (32) 10 (100000) 2 = ( 40) 8

 

OSSERVAZIONE

In qualunque sistema posizionale, con cifre 0 per zero e 1 per uno, la base b si rappresenta con ( 10 ) in base b ; ( 10 ) in base 2 = due; (10) in base 8 = otto ; ( 10 ) in base 16 =sedici           

Con 1 cifra nei numeri binari si rappresentano due distinti valori 0 ed 1;

con 2 cifre si rappresentano 4 distinti valori { 00 01 10 11 }

con 3 cifre si rappresentano 8 distinti valori { 000 001 010 011 100 101 110 111 }

con n cifre si rappresentano 2^ n valori diversi.

 

Nei numeri in base b con n cifre si rappresentano b^n valori diversi

 

Operazioni aritmetiche

Tutte le notazioni posizionali utilizzano per le operazioni le medesime regole, a prescindere dalla base di rappresentazione adottata. Per cui le regole che conosciamo per i numeri decimali restano valide.

Nelle operazioni con i numeri decimali se eseguiamo la somma fra il numero 26 ed il numero 39 facciamo

26 +

39 =

5 e riporto 1

65

( il riporto in informatica si chiama carry ( pronuncia cherri))

 

con i numeri binari 1+1 = 0 e riporto 1 per cui 1+1= 10 (che in decimale significa 2)

 

Tabella della somma in binario

N1

0

0

1

1

N2

0

1

0

1

Somma

0

1

1

0

Riporto

0

0

0

1

 

Esempi di somme:

001  +

110 =

111

001 +

101  =

110

 

011 +

 110 =

1001

questa ultima somma 3 in base 10, + 6 in base dieci fornisce 9 in base 10 , ma per rappresentare il nove in base due viene richiesta una cifra in pi; non bastano 3 bit ma ne necessitano 4; in questo caso si dice che si verificato un trabocco.

Rappresentazione di un numero con parte frazionaria

( 25.56 ) 10 = 2 * 10^1 + 5 * 10^0 + 5 * 10^(-1) + 6 * 10^(-2)

In generale, se il numero ha parte frazionaria, dopo C0 ci sono altre cifre di peso rispettivamente b^(-1) , b^(-2) , ,b^(-m)

( Cn-1 Cn-2 C1 C0 C-1 C-2 C-3 C-4 C-5.C-m ) b

Il numero sarebbe:

( Cn-1 * b^(n-1) + Cn-2 * b^( n-2) ++ C1 * b + C0 +

C-1 * b^(-1) + C-2 * b^(-2) + C-3 * b^(-3) ++ C-m * b^ (-m) )

Esempio

( 11001.1001) in base 2 = ( ? ) in base 10

1 * 2^4 + 1 * 2^3  +  0 * 2^2 + 0 * 2^1 + 1 * 2^0  + 1 * 2^(-1)  +  

0 * 2^(-2)  +  0 * 2^(-3)  + 1 * 2^(-4)

= 16 + 8 + 1 + 0.5 + 0.0625 = ( 25.5625 ) in base 10

una rappresentazione approssimata in generale.

Conversioni di base

Esaminiamo le tecniche (algoritmi ) per ottenere un numerale in base b2 che rappresenta un numerale in base b1;

(..)b1 (........)b2  dove fra parentesi rappresentato il medesimo numero.

1)   Algoritmo delle divisioni successive

In una notazione posizionale:

num = C0 + b^1 * C1 + b^2 * C2 +..+Cn-1 * b^(n-1)

che si pu riscrivere come :

num= C0 + b * ( C1 +  b * ( C2 + b * ( C3 +...)))

Di conseguenza  C0  pu essere ricavato come resto della divisione intera fra num/b                                                              

per cui il quoziente di tale divisione  

q = C1 + b*(C2 + b* (C3 +))

Quindi le altre cifre si ottengono iterando il procedimento, ottenendole nell ordine dalla meno significativa (LSB) alla pi significativa (MSB).

LSB (least significant bit) MSB (most significant bit).

Cerchiamo di chiarire ci: se abbiamo un numero espresso nella base b1 che vogliamo convertire in un numero della base b2 eseguendo le operazioni tutte in base b1; procediamo nel seguente modo, che esporremo con un

esempio:

(25) in base 10  

deve essere convertito in un numero ( x ) in base 2.

25 : 2 =12 resto 1 C0 1

12 : 2 = 6 resto 0 C1 0

6 : 2 = 3 resto 0 C2 0

3 : 2 = 1 resto 1 C3 1

1 : 2 = 0 resto 1 C4 1

per cui il numero x in base 2 corrispondente al 25 in base 10 : 11001

Il procedimento che si segue quindi: 

si divide il numero in base b1 per la base b2 ed il resto della divisione intera = C0, poi con il quoziente ottenuto al passo precedente eseguiamo una ulteriore divisione per la base b2 ed il resto = C1, con il quoziente attuale si esegue ancora una divisione per la base b2 ed il resto = C2.. ed il procedimento continua fino ad ottenere un quoziente pari a 0. 

Ad ogni divisione fatta secondo l aritmetica della base b1 otteniamo una cifra della rappresentazione della base b2 ossia si ottiene complessivamente C0, C1, C2,..,C n-1 .

Quindi per essere pi chiari , per convertire un numero num in base b1=10 in una stringa di cifre in base b2 :

a)    si divide num per b2

b)    il resto della divisione costituisce la cifra meno significativa C0;

c)     il quoziente serve ad iterare il procedimento;

d)    Se tale quoziente zero l algoritmo termina, se non zero tale quoziente lo si assume come nuovo valore num;

e)    Si itera il procedimento con il nuovo valore num .

Esempi con numeri interi con b1=10

Numero base b1

Base b2

Calcolo valore

Stringa

11

2

11/2 =5 resto 1

5/ 2 =2 resto 1

2/2 =1 resto 0

1/2 =0 resto 1

1011

C3C2C1C0

37

8

37/8 = 4 resto 5

5/8 = 0 resto 5

55

C1C0

128

10

128/10 = 12 resto 8

12/10 = 1 resto 2

1/10 = 0 resto 1

128

C2C1C0

63

16

63/16 = 3 resto 15

3/16 = 0 resto 3

3F

C1C0

2)    L espressione che fornisce il numerale Cn-1*b^n-1++ C0 + C-1*b^-1+ fornisce anche un metodo per convertire il numerale da base b1 a base b2. Infatti per ottenere la rappresentazione nella base b2 serve esprimere la base b1 ed i coefficienti Ci del numerale su scritto, nella base b2 e poi eseguire sempre nella base b2, le operazioni indicate: cio rappresentare

Ci ( ...) b2

b1 ( ) b2

e poi calcolare il polinomio, facendo i conti in base b2.

Esempio.

( 1100 )2 ( ? )10

( 1100 )2 = (1)2 * (10)^3 2 + (1)2 * (10)^2 2 + (0)2 *(10)^12 +   ( 0 ) 2  * ( 10 )^0 2

= (1)10 * (2)^3 10  + 1 * 2^2 + 0 * 2 + 0

= 1 * 8 + 1 * 4 =  ( 12 )10

esempio

( 11001 ) 2  =  ( 25 ) 10

1 * 10^4 + 1 * 10^3 + 0 * 10 ^2 + 0 * 10^1 + 1*10^0              nella   base 2     

= 1* 2 ^4 + 1* 2^3 + 0 + 0 + 1     nella   base 10

= 16 + 8 +1 = 25

esempio

( 1100 ) 2 = ( ? ) 8

1 * 10^3 + 1 * 10^2 + 0 * 10^1 + 0 * 10 ^0 base 2

= 1* 2 ^3 + 1* 2^2 base8

otto         quattro

= 1* ( 10 )^1 8 +  4 * (10 )^0 8 = ( 14 ) 8

esercizio

( 31.44 ) 8 = ( 25.5625 ) 10

( 19.9 ) 16 = ( 25.5625 ) 10

Il primo si risolve cos :

3* 8 +1 + 4 * 1/8 + 4 * 1/64

il secondo si risolve cos:

1 * 16 + 9 + 9 * 1/16

esercizio conversione da base 10 a base due

( 25 ) 10  =  ( ? ) 2

= 2 * 10 ^ 1 + 5 * 10 ^0 =

= 10 * 1010 + 101 * 1 = tutto espresso in binario

= 10100 +101 =

=11001

infatti :

1010 *

10 =

_

0000

1010

_

10100

e

10100+

101=

_

11001

Caso di numeri con parte frazionaria ( reali )

In questo caso bisogna trattare diversamente la parte frazionaria da quella intera

( Cn-1 Cn-2 C1 C0.C-1 C-2 C-m )

Prima del punto decimale,per la parte intera, eseguiamo n divisioni di () in base b1 per ( b2) in base b1; mentre dopo il punto decimale, per la parte frazionaria, eseguiamo m moltiplicazioni di () in base b1 per ( b2 ) in base b1.

Infatti

[ C-1*b2^ -1 + C-2 * b2^ -2 +.+ C-m *b2^ -m ] *b2 =

C-1 + C-2 * b2^ -1 +.+ C-m * b2^ (-m+1)

La cifra cercata la parte intera e dopo m moltiplicazioni abbiamo trovato

C-1 C-2 C-3 . C-m

( si continua fino a quando il risultato ha parte frazionaria =0 o finch si raggiunge una precisione soddisfacente).

Riassumiamo quanto detto in questultima parte: per i numeri interi si opera per divisioni successive, perch gli esponenti sono >= 0 mentre nella parte frazionaria abbiamo esponenti negativi e quindi per isolare le cifre bisogna procedere per moltiplicazioni successive.

La conversione di un numero reale in una stringa avviene in due fasi: 

conversione della parte intera ( divisioni successive ) conversione della parte frazionaria ( moltiplicazioni successive ).

L algoritmo delle moltiplicazioni successive opera solo su numeri puramente frazionari (ossia | N |< 1) ; ad ogni passo viene prodotta una nuova cifra della stringa come lalgoritmo delle divisioni successive, ma in questo caso le cifre sono prodotte nellordine da sinistra a destra ( allontanandosi dal punto decimale ); la cifra che si produce disponibile come parte intera del risultato della moltiplicazione.

Esempio

( 25.5625 )10  =  ( . ) 2

Separiamo parte intera e parte frazionaria:

( 25 )10  = ( 11001 )2  ottenuto con le divisioni successive

mentre per

(.5625)10  = ( ? ) procediamo usando l algoritmo delle moltiplicazioni successive.

.5625 x 2 = 1.125 C- 1 =  1

.125 x 2 = 0.250 C- 2  =  0

.250 x 2 = 0.500 C- 3 =  0

.500 x 2 = 1.000 C- 4 =  1

la parte frazionaria uguale a zero e quindi ci fermiamo.

Per cui la stringa  ( ? ) 2 cercata uguale a 1001

Il numero completo allora 11001.1001

Primo caso particolare

( Cn-1 Cn-2 C1 C0 ) in base b^k ( Dm-1 Dm-2 D1 D0 ) in base b

Si traduce ogni cifra Ci in base b

( [Cn-1 in base b] [Cn-2 in base b] [C0  in base b] ) in base b

Esempio

( 653 ) in base 8 ( ? ) 2

in questo caso k = 3

= ([6 in base 2 ] [ 5 in base 2] [ 3 in base 2]) 2

= ( [110] [101] [011] )

= ( 110101011) 2

spiegazione analitica

( ) in base b^k = Cn-1 * (b^k)^ (n-1) + 

Cn-2 * (b^k)^(n-2) ++C1*b^k + Co

dove Ci {0, 1, 2, , (b^k ) -1}

Si rappresenta di nuovo tutto in base b

( Ci ) in base b^k = ( D k-1 ^ i + D k-2 ^ i + + D1 ^ i + D0 ^ i ) in base b

con Dj ^ i  { 0, 1, 2, , b-1}

visto dal punto di vista in base b   Ci    un numero compreso tra 0 e (b ^ k) -1

ricordandoci che con n cifre binarie si rappresentano 2 ^ n diversi numeri compresi fra 0 e 2^n - 1, avremo che con n cifre in base b si rappresentano b^n numeri compresi nell intervallo [ 0 , b^n -1] ; quindi per rappresentare un Ci [0 , b^k -1 ] ci vogliono k cifre.

Allora ogni cifra  Ci {0,1, ,b^k -1}    rappresentabile come:

Ci = Dk-1 ^ i + Dk-2 ^ i + + D1 ^ i + D0 ^ i

Sostituendo nel polinolimio di () in base b^k otteniamo k * n addendi:

[ Dk-1 ^ (n-1) * b^(k-1) + ..... + D1^ (n-1)*b +D0 ^ (n-1) ] b^(k*(n-1)) +

+ [ Dk-1 ^(n-2) * b^(k-1) + .... + D0 ^ (n-2) ] * b^(k*(n-2)) +

+ ........

+ [ Dk-1 ^ 1 * b^ (k-1) + .... + D0 ^1 ] * b^k +

+ [ Dk-1 ^ 0 * b^ (k-1) + .... + D0 ^0] =

= Dk-1 ^ (n-1) * b ^ (k-1+k*n -k) + ... + D1 ^ (n-1) * (b ^ (k * n - k+1))+ D0 ^ (n-1) * b^( k*n - k) + Dk-1 ^ ( n-2) * b^(k-1+k*n-2k) + ... + D0 ^ (n-2) * b^ (k*n-2k) +

+ ... + Dk-1^(1) * b^(k-1+k) + ... + D0 ^(1) * b^k +

+ Dk-1 ^ (0)* b^ (k-1) + ...+ D0 ^ 0

CIOE

( Cn-1 Cn-2 C1 C0 ) = ( Dk-1 ^ n-1 Dk-2 ^ n-1 ... D1 ^ n-1 D0 ^ n-1 Dk-1 ^ n-2 ... D0 ^ n-2 ......... Dk-1 ^ 0 ... D0 ^ 0 )

Nel termine a primo membro abbiamo n cifre b^k mentre al secondo membro abbiamo

(Cn-1 ) in base b (Cn-2) in base b .. ( C0) in base b.

Esempio

(1 5 A ) in base 16 = ( ? ) in base 2

k=4 per cui ha:

0001 0101 1010 4 cifre binarie per ogni cifra esadecimale

ossia il numero in base 2 corrispondente al numero in base 16        ( 1 5 A ) :

( 000101011010 )

Esempio con numero frazionario

( 25.5 ) in base 10 = ( 11001.1 ) in base 2

000101011010

se volessimo rappresentare 25.5 in base 8 e 16 dobbiamo considerare il rispettivo numero binario e

nel caso di base 8 raggruppare a gruppi di k=3 

( in quanto 8 2^3 ) i bit iniziando dal punto decimale verso sinistra per la parte intera e dal punto decimale verso destra per la parte frazionaria; laddove si formano gruppi con un numero di cifre inferiore a 3 si aggiungono degli zeri.

Nel nostro caso per la conversione in base 8 avremo 011001.100 = ( 31.4 ) in base 8.

Nel caso della conversione in base 16 avremo che i gruppi di bit sono k=4 (16 2^4) , per cui si ha : 00011001.1000 = ( 19.9 ) in base 16.

Secondo caso particolare

Se b1 = b e b2=b^k come si rappresenta un numero () in base b in () in base b^k ? 

Vale lo stesso ragionamento di prima ma in questo caso invece di espandere, contraiamo la rappresentazione di partenza, raggruppando cifre della rappresentazione in base b k a k e raggruppando ciascun gruppo in b^k.

Ossia in questo caso non necessario applicare l algoritmo di conversione ma si pu agire direttamente.

Esempio

( 110 101 011 ) in base 2 quanto vale in base 8 ?

b1=b=2 e b2=b^k= 2^3

lo abbiamo gia considerato nell esempio precedente per cui si raggruppano i bit a k a k, 3 a 3 iniziando da sinistra verso destra per cui il numero cercato ( 653 ) in base 8.

Esempio

( 110101011001 ) in base 2 = ( 6531 ) in base 8

( 110101011001 ) in base 2 = ( D59 ) in base 16

calcolarli come esercizio.

NOTA BENE

Se le cifre sono poche per formare i gruppi di bit ne possiamo aggiungere a sinistra, se il numero rappresentato intero , ma devono essere zeri:

avendo 11 001 in base 2 per trasformarlo in base otto aggiungo uno zero all estrema sinistra della stringa ottenendo due gruppi di k=3 bit ed il risultato

( 31 ) in base 8.

Se lo convertiamo in base 16 occorre aggiungere 3 zeri allestrema sinistra ottenendo ( 19 ) in base 16.

Richiamo

In qualunque sistema di numerazione si possono rappresentare numeri con parte frazionaria

Esempio

11001.1001 ?

= 1 * 2^4 + 1 * 2^3 + 1 * 2 ^0 + 1 * 2^ (-1) + 1 * 2^ (-4)

= ( 25.5625 ) in base 10

Concludendo abbiamo visto come il metodo delle divisioni successive permette di ricavare da un numero intero la rappresentazione in base 2 es. ( 25 ) in base 10 uguale a ( 11001 ) in base 2; simili considerazioni permettono di ricavare (25.5625) in base 10 come ( 11001.1001 ) in base 2.

Vi un trattamento separato della parte intera e della frazionaria.

Per la parte intera si divide per (b2) in base b1 e si ottengono      CO C1 ... Cn-1.

Per la parte frazionaria moltiplicando per (b2) in base b1 si ottengono :

C-1 C-2 . C-m .

 

Test 9