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:

 

 

Sistema binario

Il sistema binario è posizionale in base b=2; le cifre o simboli dell’alfabeto 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 +

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 quest’ultima 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 l’algoritmo delle divisioni successive, ma in questo caso le cifre sono prodotte nell’ordine 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  = ( ? )2  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 all’estrema 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 .