Lezione XI FRAMES NOFRAMES

Rappresentazione delle informazioni

parte III

Rappresentazione in complemento alla base

Continuiamo il discorso sulla rappresentazione in complemento alla base della lezione X , formalizzandola.

Definiamo Residuo Modulo b^n di X

e lo indichiamo con : | X |

b^n

| X | = X - ë X /b^n û * b^n

b^n

dove b e’ una base generica , X e’ il numero intero relativo, n e’ il numero di cifre ed il simbolo

ë û

indica, la funzione che calcola la parte intera inferiore dell’argomento in esso contenuto.

Indichiamo per comodita’ il residuo modulo b^n su scritto con

Res[X](b^n) e la parte intera inferiore, con P.i.i.( ) .

Proprieta’

Se X Î [-b^(n /2) , b^(n /2) ] ossia | X | <= b^(n/2)

Per ogni x Î [0, b^n ) esiste un unico X tale che

x = Res[X](b^n); cioe’ esiste una corrispondenza biunivoca tra i numeri X ed i numerali x e questo implica che e’ possibile determinare dei numeri X mediante i numerali Res[X](b^n).

Se facciamo l’ ipotesi che | X | <= b^n/2 si puo’ semplificare la definizione di residuo modulo nel modo seguente:

Res[X](b^n) = X se 0<= X < b^(n/2)

Res[X](b^n) = b^n - | X | se -b^(n/2) <= X < 0

La rappresentazione degli interi relativi X, nell’ intervallo

[ -b^n /2 , b^n /2 ) tramite il residuo modulo e’ detta rappresentazione in complemento alla base b.

Esempio

Calcolare il residuo modulo del numero X = +25 nella base b=10 ed n =2:

Res[25] (10^2)= 25 -0 = 25

Res[-25](10^2)= -25 - P.i.i.(-25/100)*10^2 = -25 +100 =75

Tabella di rappresentazione degli interi relativi ottenuta con il residuo modulo dei numeri interi in base b=10 con n =2.

0	1	2	…	49	-50	-49	…	…	- 25	…	…	-3	-2	-1
0	1	2	..	49	50	51	…		75	…	…	97	98	99

La rappresentazione degli interi relativi X compresi nell’ intervallo [-b^n /2 , b^n /2), tramite il residuo modulo b viene detta rappresentazione in complemento alla base b.

Come si vede nella tabella i numerali da 0 a b^(n/2)-1 rappresentano i numeri interi compresi fra 0 e b^(n/2)-1 mentre i numerali da b^(n/2) a b^n -1 rappresentano i numeri interi da -b^(n/2) a -1.

Nel caso in cui la base b=2 avremo che i numerali da 0 a 2^(n/2)-1 rappresentano gli interi compresi fra 0 e 2^(n/2)-1 mentre i numerali da 2^(n/2) a 2^n -1 rappresentano i numeri interi negativi da -2^(n/2) a -1 : per ottenere questa rappresentazione si decide di rappresentare, come gia detto, i numeri da [ -2^(n/2) , 2^(n/2) ) con il rispettivo residuo modulo 2^n dove n = numero di bit usati.

Nella tabella sopra il numero -25 e’ effettivamente rappresentato dal numerale 75, mentre il numero -2 e’ rappresentato dal numerale 98; ossia i numeri da 0 a 49 sono rappresentati dai rispettivi numerali da 0 a 49 mentre i numeri da -50 a -1 sono rappresentati dai numerali da 50 a 99.

Calcolo del numerale di -2 in complemento alla base b=10 con n=2 cifre:

Res[-2](10^2) = -2 - P.i.i.( -2/100 )*100 = -2 - (-1 ) *100 = -2 +100 =98.

Esempio

Se vogliamo calcolare la rappresentazione (da quale numerale e’ rappresentato) del numero X=-20 in complemento alla base 2 con n=6 bit ?

Calcoliamo il Res[-20](2^6) = 64-20 =44 il cui numerale binario e’ 101100.

Schema di calcolo della rappresentazione in complemento a 2 di -X conoscendo la rappresentazione di X.

X = Cn-1 Cn-2 …. C1 C0

a) Si calcola C’n-1 C’n-2 …C’1 C’0 dove C’i = (b-1)-Ci

b) Si aggiunge 1 al risultato cosi ottenuto

Per cui il Res[-X](b^n) = C’n-1 C’n-2…C’1+C’0 +1

Esempio

Calcolare il complemento alla base 10 del numero con, n = 3 cifre, del numero -324. Si determina il numero rappresentato dalla sequenza di cifre :

a) C’2 = (10 - 1) - 3 = 6 ; C’ 1 = (10-1) - 2 = 7 ;

C’ 0 = (10 - 1) - 4 = 5 ottenendo 675;

b)Si aggiunge 1 a 675 ottenendo che Res[-324](10^3) = 676.

Calcolare il complemento alla base 2 del numero con, n = 4 cifre, del numero -0100. Si determina il numero rappresentato dalla sequenza di cifre :

a) C’3 = (2 - 1) - 0 = 1 ; C’2 = (2-1) - 1 = 0 ; C’1 = (2 - 1) -0 = 1; C’0 = (2 - 1) -0 = 1; ottenendo 1011;

b) Si aggiunge 1 a 1011 ottenendo che Res[-0100](2^4) = 1100.

Se la base b=2 avremo quindi che:

a) si scambia 1 con 0 e 0 con 1 in X (complementazione)

b) si aggiunge 1 al risultato ottenuto.

Esempio

( 20 ) in base 2 = 010100 con n= 6 bit

a) 101011

b) + 1

risultato 101100 numerale

101100= 44 = Res[-20](2^6)

Come detto in una lezione precedente, se vogliamo trovare il complemento a due del numero intero -20 , equivale a trovare la rappresentazione binaria del numero +20 e complementare tutti i suoi bit partendo dal meno significativo al piu’ significativo

( da sinistra a destra ) ad iniziare dalla posizione successiva al primo 1 incontrato nella stringa.

Esempio

Determinazione della rappresentazione del numero -15 (su n=8 bit )

+15 = 00001111 si trasforma in 11110001.

Il procedimento funziona anche al contrario ossia data la rappresentazione di -X= -15, complementando ( invertendo ) tutti i suoi bit dal meno significativo al piu’ significativo ad esclusione dei bit incontrati fino al primo 1 (esso stesso incluso ), si ottiene la rappresentazione di X=15 ; infatti 11110001 si trasforma in 00001111.

Osservazione sulla notazione in complemento a 2

a) La notazione in complemento a 2 e’ non ( completamente ) posizionale

b) Il bit piu’ significativo di una stringa di n bit ha peso - 2^(n-1) e non 2^(n-1)

c) Esempio con n = 8 bit, il bit numero 7 ha peso -128 e non +128 per cui la stringa 11110001 denota il valore -128 + 64 +32 +16 +1 = -15 usando la formula vista nella lezione precedente.

Osservazione

E’ importante il numero di cifre n.

Se n=4

( 12 ) in base 2 =1100 e -12 sarebbe 0011 +1 = 0100 = ( 4 ) in base 2

in questo caso sono pochi i bit ! Infatti con n= 4 bit si rappresentano 2^4 numerali e questo implica che

X Î [-16/2 , 16/2) = [-8 , 8) = [-8 , 7] ed il 12 Ï [-8 ,8)

Se usiamo n = 5 bit avremo che il 12 Î [ 16,16 ) e quindi si puo’;

( 12 ) in base 2 = 01100

Res[-12](2^5) = 2^5 - |-12 | = 32-12 = 20 = ( 10100 ) in base 2

Con n= 6 bit pure si puo’, infatti il Res[-12 ](2^6) = 2^6 -| -12 | =64 -12 = 52 = 110100.

Esempi di numerali in complemento a 2 con n =8 bit.

11110001 rappresenta il valore -128 + 64+32+16+1 = -15

01110100 “ 64+32+16+4 = 116

00000000 “ 0, = 0

10000000 “ - 128+64+32+16+8+4+2+1 = -1

01111111 “ 64+32+16+8+4+2+1 = 127

10000111 “ -128+0+0+0+0+4+2+1 = -121

MSB = 0 implica numero positivo

MSB = 1 implica numero negativo

Se prendiamo l’ultima stringa 10000111 e troviamo il suo complemento a 2 otterremo la stringa 01111001 ossia il valore decimale 121 dal quale potremmo dedurre che il complemento a due del numero -X = X (e’ sbagliato ! questo e’ un caso fortuito )

In generale valori opposti come X e -X hanno rappresentazioni completamente diverse.

Indicando con C2[X]n la funzione complemento a 2 del numero X su n bit avremo che:

C2[15]8 = 00001111 mentre il C2[-15]8 = 11110001 cioe’ rappresentazioni completamente diverse.

Operazioni aritmetiche in complemento a due

ADDIZIONI +

Supponiamo di avere n bit per rappresentare un intero e consideriamo due numeri positivi X e Y ed indichiamo con x e y le loro rappresentazioni in complemento ossia il residuo modulo :

x = Res[X](2^n) ; y = Res[Y](2^n)

Consideriamo tutti i possibili casi di addizione e sottrazione tra loro :

+X+Y; +X-Y; -X+Y; -X-Y;

Primo caso +X +Y

Il risultato e’ rappresentato in complemento da x + y = X +Y che risulta essere corretto se non si e’ verificato trabocco ( overflow ) ossia se | X +Y | <= b^n /2.

Esempio con 5 bit: dobbiamo ottenere che | X+Y |<=16; se X=9 e Y=3 avremo: X +Y = 12.

01001 +

00011 =

¾¾¾¾

01100

che e’ 12 in complemento (ossia Res[ X + Y ](2^5) )

Se X vale 9 e Y vale 8 sempre con n= 5 bit avremo: X+Y=17.

01001 +

01000 =

¾¾¾¾

10001

che non e’ la rappresentazione in complemento di 17, per cui il risultato e’ errato, in quanto si e’ verificato un overflow.

Non bastano 5 bit per rappresentare in complemento a 2 il numero 17. Se n=6 avremo:

001001 +

001000 =

¾¾¾¾¾

010001 che rappresenta 17 in complemento a 2.

Secondo caso + X - Y

In questo caso si esegue la somma tra le notazioni in complemento di X e di -Y:

x + y = X +2^n -Y = 2^n + X - Y ; si hanno due sottocasi ,

uno se X - Y>0 e l’altro se X-Y<0 .

a) X > Y : si calcola x+y e si sottrae 2^n. Notare che sottrarre 2^n equivale a trascurare il bit piu’ significativo ( bit MSB all’estrema sinistra della stringa ).

b) X < Y : in questo caso il risultato che si ottiene calcolando x+y

coincide con la rappresentazione in complemento di X -Y.

Esempio con n = 5 bit

x 01001 + ( 9 )

y 11100 = ( - 4 )

¾¾¾¾¾¾¾¾¾¾

x+y , 100101 ( 5 )

trascurando, nella stringa risultato 100101, l’MSB otteniamo 00101 che equivale appunto a 5 in base 10.

x 00100 + ( 4 )

y 10111 = (-9 ) 23 = 32 -9

¾¾¾¾¾¾¾¾¾¾

x+y 11011 (-5)

il risultato 11011 rappresenta il numerale 27 , che rappresenta il numero -5, e che e’ dato da 32 - 5 : b^n - | X | e quindi rappresenta - 5 in complemento a due.

Se volessimo trovare il complemento a due del numero X = 11011 otterremmo 00101 il valore 5 come era logico attendersi, per cui 11011 vale -5. Quindi quando si trova un numerale in complemento a due che ha 1 come MSB intuiamo che si tratta di un numero negativo (abbiamo ricavato il segno ) e volendo trovare il valore del numerale eseguiamo il complemento a due e traduciamo la stringa ottenuta in decimale.

Terzo caso - X + Y

Uguale al secondo caso se si scambia X con Y e Y con X.

Sviluppate questo caso da soli come esercizio.

Facciamo un esempio numerico con -X = -5 e Y = 3 con n =8 bit

-5 + 3 = -2

Ricaviamo la rappresentazione di -5 considerando l’unico contributo negativo possibile e’ il -128 dell’MSB ; e per ottenere -5 occorre determinare gli altri bit in modo da rappresentare il valore +123 :

-5 = -128 +123 ® 1 1111011

-5 + 11111011 +

+3 = 00000011 =

¾¾¾ ¾¾¾¾¾¾

-2 1 11111110

infatti 11111110 = -128 +126 =-2

Comunque -5 in complemento a 2 si puo’ sempre ricavare usando il solito metodo di considerare +5 in binario puro ed invertendo tutti i suoi bit e sommandovi 1.

+5= 00000101

-5 = 11111011

Quarto caso - X - Y

Si fa la somma tra le notazioni in complemento x + y .

Entrambi in numeri da sommare sono negativi per cui avremo che:

Res[-X](b^n ) = b^n - | -X |

Cioe’ x = 2^n - X e y = 2^n - | Y | quindi

x + y = 2^n -X + 2^n -Y = 2^n + ( 2^n -X -Y ) che differisce di 2^n del risultato corretto che e’ essendo - X - Y negativo :

2^n - | - X -Y | = 2^n -X -Y = Res [ -X - Y ](2^n).

Percio’ x+y e’ la rappresentazione del risultato - X - Y a meno del 2^n che va sottratto eliminando il bit piu’ significativo.

Esempio con n=5 bit

-1 + 11111

-5 = 11011

¾¾¾¾¾¾¾

-6 111010

Scartando il bit piu’ significativo in rosso otteniamo 10101 che rappresenta il complemento a due di -6 .

Infatti 11010 vale 24 in decimale e

24= Res[-6](2^5) = 32 - | -6 | = 32 -6 = 24.

Apriamo una parentesi

In alternativa si puo’ spezzare la stringa 10101 in 1 1010 e fare la somma tra il bit piu’ significativo cambiato di segno che ha peso

n -1= 4 ed il valore della restante stringa ® -16 + 10 = -6

In generale questo metodo alternativo va bene a patto di ignorare il riporto oltre nel caso delle addizioni ed il prestito oltre l’ MSB nel caso delle sottrazioni e tutto funziona, come abbiamo visto nell’esempio del terzo caso.

Esempio di due sottrazioni

3 - (+5 ) e 3 - (-5)

+3 - (1) 00000011 -

+5 = 00000101 =

¾¾ ¾¾¾¾¾¾

-2 11111110

+3 - (1) 00000011 -

-5 = 11111011 =

¾¾ ¾¾¾¾¾¾

+8 00001000

Il risultato va bene a patto di ignorare il prestito.

Moltiplicazioni e divisioni con questo metodo alternativo non funzionano.

Fine parentesi.

Ritornando a prima della parentesi notiamo che il risultato e’ corretto soltanto se non si e’ verificato trabocco nella somma. Come si vede che non vi e’ stato trabocco ?

1) Da - X -Y ci aspettiamo un risultato negativo del tipo 1….

Infatti 11010 ha il bit piu’ significativo pari a 1.

Nel caso della somma fra -14 -15 avremo

10010 +

10001 =

¾¾¾¾¾

100011

trascurando il bit piu’ significativo il risultato della somma e’ 00011 che ci indica essere in presenza di un numero positivo per cui si e’ verificato trabocco.

Infatti - 29 Ï [ -2^5 /2 , 2^5 /2) !

Notate se al posto della somma algebrica si esegue la somma tra le rappresentazioni complementate, a parte i casi in cui si verifica il trabocco, la somma effettiva coincide con il risultato oppure viene ricavato da questo trascurando l’ultimo bit ( riporto ).

MOLTIPLICAZIONI *

Dati due numeri X ed Y di n bit ciascuno, per rappresentare il prodotto X*Y servono 2*n bit.

Eseguendo il prodotto di 3 * 4 avremo

011 *

100

¾¾¾¾

000

000 -

011 - -

¾¾¾¾¾¾

01100

che e’ uguale a 12 con 5 bit invece dei 6 bit previsti! Il problema e’ che non bisogna estendere gli addendi sempre con degli 0 ma con 0 per i numeri positivi e 1 per i numeri negativi, quando si opera con rappresentazioni complementate.

In generale

110100 = -12 con b=2 ed n=6

1110100 = -12 con b=2 ed n=7

001100 = +12 con b=2 ed n=6

0001100 = +12 con b=2 ed n=7

Nelle moltiplicazioni il modo di operare e’ diverso a seconda che X>0 e Y<0; X < 0 e Y > 0 ; X< 0 e Y<0.

Primo caso X>0 e Y>0

X * Y = x* * y ( x* e’ x complementato )

Secondo caso X < 0 e Y > 0

Assumiamo b = 2 n = 6

Siano X = XnXn-1…..X1X0 ed Y= Yn-1Yn-2…..Y1Y0 il moltiplicando ed il moltiplicatore rispettivamente.

X * Y puo’ calcolarsi nel modo seguente:

X * (1000…0) + X* (0Yn-1…0) + … + X * (0000…Y0)

(1000…0) e’ negativo va complementato ed esteso a sinistra fino a 2n va fatta con 1. gli altri termini sono tutti positivi tranne uno.

Esempio con n=3 : prodotto 3* (-2)

011

110

¾¾¾¾¾

000000

00011 -

0011- -

1101- - ( ottenuto complementando 0011 )

¾¾¾¾¾¾

111010 58 = 64 -6

1110010 rappresenta -6 in complemento a 2.

Tutti gli addendi vanno estesi a sinistra fino a 2*n bit tutti con 0 tranne il prodotto Yn * X.

Terzo caso : X < 0 e Y < 0

In questo caso tutti i prodotti intermedi vanno lasciati inalterati e vanno estesi con cifre uguali a 1.

101 -3

010 2

¾¾¾¾¾

000000

11101 -

0000 - -

¾¾¾¾¾

111010 -6

Quarto caso X < 0 e Y < 0

x * y = (2^n -X ) ( 2^n -Y ) = 2^(2*n) -2^n * X - 2^n * Y + X*Y =

= 2^(2*n) -2^n * ( X + Y ) + X*Y

si addiziona 2^n X con la complementazione

si addiziona 2^n Y con l ’ estensione della rappresentazione.

Esempio :

101 -3

110 -2

¾¾¾¾¾¾

000000

11101-

101- - da complementare

0011- -

¾¾¾¾¾¾¾

1000110

estensione positiva, complementazione del primo numero -3 ; ma il risultato differisce di 2^n da quello giusto per cui bisogna anche trascurare il bit piu’ significativo in rosso ed il risultato diventa 000110 che e’ appunto pari a 6.

L’ aritmetica in virgola mobile

Supponiamo di operare con un elaboratore le cui celle di memoria sono di lunghezza di 32 bit. Operando in base 2 e riservando 24 bit per la mantissa, 7 bit per l’ esponente ed 1 bit per il segno avremo che essendo ½ <= | m | < 1

la mantissa m piu’ piccola m_min e’ pari ad ½ ossia :

.100000000000000000000000

la mantissa m massima m_max e’ circa 1 ossia :

.111111111111111111111111

che e’ uguale a 2^-1 + 2^-2 +2^-3 + …+ 2^-24 = 1- 2^(-24)

0					1
1/2	1/4	1/8	1/16

2^-1+2^-2 = 1- 2^-2

2^-1 +2^-2 + 2^-3 = 1-2^-3

2^-1+2^-2 + …+ 2^-n = 1- 2^-n

All’ aumentare di n la sommatoria tende sempre piu’ al valore 1.

La caratteristica exp e’ un intero relativo ; su 7 bit in complemento a due si possono rappresentare gli interi compresi in [ -64 , 63] , per cui :

exp massimo = 0111111 = + 63

exp minimo = 1000000 = - 64

Il numero Xmax rappresentabile in virgola mobile si ha in corrispondenza di m massima e di exp massimo, per cui su 32 bit: m_max = 1-2^(-24) ed exp_max = 63 per cui si avra’

Xmax = (1- 2^(-24) ) * 2^ (63) = 2^63 - 2^39 che e’ circa 2^63.

Il numero Xmin rappresentabile in virgola mobile si ha in corrispondenza di m_min e di exp_min :

essendo m_min= 2^-1 =1/2 ed exp_min = -64 avremo

Xmin = 2^-1 * 2^-64 = 2^(-65)

Proprieta’ dell’insieme F

Indichiamo con F l’insieme dei numeri a virgola mobile

( rappresentabili in floating point ),

esso gode delle seguenti proprieta ’ :

a) F e’ contenuto in R ( e’ un sottoinsieme dei numeri reali ).

b) F e’ un insieme finito,

c) F e’ simmetrico rispetto allo 0 ( si hanno due rappresentazioni dello 0 oppure nessuna)

d) Gli elementi di F non sono distribuiti in modo uniforme sull’asse reale.

e) Dato un XÎR se X Ï F si sceglie il numero

X’ = fl(X) Î F, ( fl() funzione di arrotondamento ), piu’ vicino in F che lo rappresenta in modo approssimato.

f) F non gode delle proprieta’ commutativa, associativa, distributiva dei numeri reali.

Quanti numeri diversi si possono avere in F ?

Essendo le mantisse possibili 2^24 le caratteristiche possibili 2^7 ed i segni per ogni combinazione pari a 2 avremo 2^32 numeri diversi.

Calcolo della distanza di alcuni numeri in F

Vediamo che la distanza | Xmin - X*min | e molto inferiore alla distanza | Xmax - X*max | dove X* sono i numeri positivi in F piu’ prossimi agli X.

Avevamo per Xmin m_min = ½ = .100000000000000000000000

exp_min = -64

X*min avra’ m_min = 2^-1 +2^-24 = .100000000000000000000001

exp_min = -64 per cui

X*min = (2^-1 +2^-24 ) * 2^(-64) = 2^-(65) + 2^(-88)

quindi | Xmin - X*min | = 2^(-88)

Xmax aveva m_max = 1- 2^(-24) = .111111111111111111111111

ed exp_max = 63

X* max avra’ m_max = 1- 2^(-23) = .111111111111111111111110

exp_max= 63 per cui X*max = (1-2^(-23)) * 2^63 = 2^63 -2^40

quindi | Xmax - X*max | = | 2^63 -2^39 -2^63 +2^40 | = 2^39

½¾½¾½¾¾¾¾¾….¾¾¾¾¾¾¾¾¾½¾¾¾¾½

0 Xmin X*min X*max Xmax

a sinistra i numeri floating point rappresentati nell ’ elaboratore sono piu’ fitti mentre a destra sono piu’ radi

a sinistra | Xmin - X*min | = 2^(- 88) ( numero positivo ma piccolissimo )

a destra | Xmax - X*max | = 2^39

PRECISIONE DELLA RAPPRESENTAZIONE

Dato un numero X appartenente ad R e’ molto facile che X Ï F. Sia X’ = fl( X ) Î F

La seguente espressione | X -X’ | = e costituisce l’ errore di arrotondamento che si compie usando X’ nei calcoli al posto del valore vero X.

Notiamo che e non e’ costante poiche’ l’insieme F non e’ uniforme.

Nei numeri grandi e puo’ essere molto grande.

Esempio

Il valore Xmax -2^38 cade al centro dell’ intervallo [ X*max , Xmax ] .

Se dobbiamo calcolare la differenza : Xmax -2^19 commetteremo un errore nel rappresentare il risultato. Tale errore essendo

fl( Xmax -2^19 ) = Xmax sara’ pari a 2^19, cioe’ e = 2^19. Notare che un errore di 2^19 su un Xmax = 2^63 non e’ molto drammatico.

Sui numeri piccoli e puo’ essere piccolo.

Eseguendo operazioni aritmetiche si ha una propagazione dell’errore, poiche’ per F non valgono le proprieta’ commutativa, associativa e distributiva.

(X + Y) * Z si calcola facendo:

(fl (X) +fl(Y) = p ; fl(p) * fl (Z) =q

quindi si ha che p e’ sbagliato perche’ somma di due contributi di errore, q sbagliato perche’ prodotto di due contributi di errore, errori che si propagano. L’ errore totale e’ dato da eq:

ex + ey = ep ; ep * ez = eq

Osservazione

Se i numeri sono piccoli sono poco sbagliati rispetto ai grandi ; nei calcoli conviene fare prima tutte le operazioni possibili con numeri piccoli e poi le altre.

Esempio

å 1/(2^i) =

i=1

= 1/(2) +1/(2^2) + 1/(2^3) + ….….. + 1/(2^n)

grande piccolo

= 1/(2^n) + 1/(2^(n-1)) + …… +1/(2^2) + 1/(2)

piccolo grande

queste due espressioni sono diverse per n sufficientemente grande;

nella seconda espressione avremo una precisione maggiore, poiche’

gli errori che si propagano di piu’, sono quelli piu’ piccoli.

-------------------------------------------------------------------------------------------------

Test 11