Operazioni tra numeri in Virgola Mobile

Operazioni tra numeri in Virgola Mobile •  Operazioni di mol.plicazione e divisione: –  Le man4sse vengono mol4plicate o divise –  Gli esponen4 vengo somma4 o so:ra; –  Se necessario, la man4ssa viene rinormalizzata e l’esponente corre:o •  Operazioni di somma o so3razione: –  L’esponente più piccolo viene reso uguale al più grande spostando la man4ssa verso destra del numero di cifre pari alla differenza tra gli esponen4 (shiD per o:enere un corre:o incolonnamento) –  Le man4sse vengono sommate o so:ra:e –  Se necessario, la man4ssa viene rinormalizzata e l’esponente corre:o Esempio: somma 100.01101 Bit di segno= 0 5 bit esponente= 00011 10 bit man4ssa= 1000110100 10.101101 Bit di segno= 0 5 bit esponente= 00010 10 bit man4ssa= 1010110100 Esempio: somma 0 00011 1000110100 + 0 00010 1010110100 Allineo man4ssa 0 00011 1000110100+ 0 00011 0101011010= -­‐-­‐-­‐-­‐-­‐-­‐-­‐-­‐-­‐-­‐-­‐-­‐-­‐-­‐-­‐-­‐-­‐-­‐-­‐-­‐-­‐-­‐-­‐-­‐-­‐-­‐-­‐-­‐-­‐-­‐-­‐ 0 00011 1110001110 Esempio: prodo:o 1.011 à 0 00001 1011* 11.01 à 0 00010 1101 = -­‐-­‐-­‐-­‐-­‐-­‐-­‐-­‐-­‐-­‐-­‐-­‐-­‐-­‐-­‐-­‐-­‐-­‐-­‐-­‐-­‐-­‐-­‐ 0 00011 1000111100 Overflow •  Per numeri rappresenta4 con un numero finito di bit, la somma può portare ad un numero in valore assoluto troppo grande per poter essere memorizzato nella memoria stessa (OVERFLOW) •  7010+6610 su un byte •  010001102+010000102 = 100010002= -­‐2810 su un byte, con rappresentazione in complemento a 2. So:razione in complemento a 2 •  Grazie alla rappresentazione in complemento a 2 la so:razione si riconduce ad una somma, rappresentando in complemento il so:raendo. •  2010-­‐3010 •  111101102= complemento a 2 su 8 bit = -­‐1010 Standard IEEE (Ins4tute of Electrical and Electronics Engineers) per la rappresentazione in virgola mobile •  Diversi forma4 per la rappresentazione dei numeri reali che differiscono per il numero totale di bit u4lizza4. I più diffusi: –  a precisione singola, con 32 bit –  a doppia precisione, con 64 bit Rappresentazione IEEE in singola precisione. •  L’interpretazione è abbastanza par4colare: –  lo standard deve perme:ere di rappresentare non solo un insieme di numeri reali quanto più ampio possibile, con la massima precisione possibile, –  ma anche valori speciali quali •  NaN – “Not a Number” : risultato di operazioni non ammesse quali la divisione per zero, •  +∞ e -­‐∞ •  Interpretazione della cara:eris4ca n –  valore compreso tra 0 e 255 (8 bit) –  i valori estremi (0 e 255) sono interpreta4 in una maniera speciale, –  i valori compresi tra 1 e 254 (inclusi) sono interpreta4 come esponente del numero razionale so:raendo 127 al valore effe;vamente rappresentato: •  se n=131 allora l’esponente del numero rappresentato vale 4, mentre se n=125 l’esponente vale -­‐2. In questo modo è possibile rappresentare tanto esponen4 posi4vi quanto nega4vi, interpretando il numero effe;vamente rappresentato come un intero senza segno (cosa che facilita i confron4). •  Interpretazione della man4ssa –  rappresentata in forma normalizzata su 23 bit ignorando il primo bit: –  il primo bit deve valere 1 (come vedremo il valore 0 ha una sua rappresentazione specifica). –  Trascurando quindi il primo bit e rappresentando solo la parte frazionaria della man4ssa, si o;ene di fa:o l’equivalente di 24 bit. •  Casi speciali: –  Il valore 0 viene rappresentato ponendo a 0 tanto la cara:eris4ca quanto la man4ssa (a seconda del valore del bit del segno è possibile rappresentare i valori -­‐0 e +0). –  Il valore 255 per la cara:eris4ca viene u4lizzato per rappresentare il valore “infinito” (posi4vo o nega4vo a seconda del valore del segno) se la man4ssa vale 0, o il valore speciale NaN se la man4ssa è diversa da 0. –  Se la cara:eris4ca vale 0 e la man4ssa è diversa da 0, quest’ul4ma viene interpretata come se si tra:asse di una parte puramente frazionaria (primo bit uguale a 0, quindi non normalizzato) e l’esponente viene posto per convenzione a -­‐126. •  Riassumendo: –  de:o s il bit del segno, n la cara:eris4ca, ed m la man4ssa, valgono le seguen4 regole per il calcolo del valore v rappresentato: –  se n=255 e m≠0 allora v=NaN –  se n=255 e m=0 e s=0 allora v=+∞ –  se n=255 e m=0 e s=1 allora v=-­‐∞ –  se 0<n<255 allora v=(-­‐1)s×2(n-­‐127) ×1.m –  se n=0 e m≠0 allora v=(-­‐1)s×2-­‐126 ×0.m –  se n=0 e m=0 e s=0 allora v=+0 –  se n=0 e m=0 e s=1 allora v=-­‐0 •  1.m denota il numero binario razionale composto da un 1, seguito dal punto decimale, seguito dai bit presen4 nella parte riservata alla man4ssa •  0.m denota il numero composto da uno 0, seguito dal punto decimale, seguito dai bit che compongono la man4ssa. •  La rappresentazione in doppia precisione è del tu:o analoga ma usa 11 bit per la cara:eris4ca e 52 bit per la man4ssa. Esempio •  −118.625 •  Segno=1 •  Numero binario=1110110.101=1.110110101·∙26 •  Esponente=6+127=133 à 10000101 •  Man4ssa=11011010100000000000000 •  1 10000101 11011010100000000000000 Esempi IEEE 754 SISTEMI DI CODIFICA Codifica di da4 non numerici: definizioni •  I calcolatori lavorano soltanto con i numeri, ma devono poter tra:are anche altre en4tà, per questa ragione sono sta4 inventa4 i codici. •  Alfabeto: insieme finito di simboli (caraEeri) disFnF •  Parola o Stringa: sequenza finita di simboli Alfabeto usato dai calcolatori •  I calcolatori lavorano u4lizzando due simboli: –  INTERRUTTORE: aperto/chiuso –  TRANSISTOR: conduce/non conduce –  LIVELLO DI TENSIONE: alto/basso –  RIFLETTIVITÀ DI UN’AREOLA: alta/bassa –  DOMINIO DI MAGNETIZZAZIONE: magne4zzato/non magne4zzato •  I calcolatori u4lizzano quindi una logica e un’aritme4ca binaria •  Ai due sta4 stabili di un disposi4vo, ai due valori di una grandezza, vengono associa4 convenzionalmente i simboli 0 e 1 Alfabe4 usa4 dall’uomo •  È necessario stabilire delle regole di corrispondenza, de:e CODIFICHE •  La codifica me:erà in corrispondenza biunivoca ogni SIMBOLO appartenente all’alfabeto più ricco con una STRINGA di simboli appartenenF all’alfabeto più rido:o Codifica: definizione •  Dato un insieme I di elemen4 qualsiasi, si dice codifica di I mediante parole (o stringhe) di un alfabeto A un procedimento che perme:e di stabilire una corrispondenza biunivoca tra gli elemen4 di I e le parole di un so:oinsieme Q dell’insieme delle parole di A. •  Esempio: codifica di le:ere tramite cifre decimali Codici binari: definizione •  Un codice binario è la codifica dei simboli di un alfabeto S mediante stringhe di bit. •  Se C è la cardinalità (n. di elemen4) di S, il numero n di bit da u4lizzare per codificare tu; i simboli di S deve essere tale che: •  Ossia: •  M è il minimo numero di bit necessario per codificare S –  Se n = M il codice è non ridondante (usa il minimo numero di bit per codificare tu; i simboli di S) –  Se n > M il codice è ridondante (usa più bit del necessario per codificare tu; i simboli di S) Esempi Distanza di Hamming •  Date due parole della stessa lunghezza, si definisce distanza di Hamming (H) il numero di bit differen4 che compaiono nelle due parole in posizioni corrisponden4. •  Esempio: S1 = 00000 00000 S2 = 00000 11111 H = 5 Se due parole di codice hanno una distanza di Hamming uguale a H, ci vogliono esa:amente H errori su singoli bit per trasformare l'una nell'altra. •  Es: la distanza di Hamming tra s1=1000 1001 e s2=1011 0001 è H =3 ossia per trasformare s1 in s2 devono cambiare tre bit. Distanza di Hamming •  Si definisce distanza di Hamming (H) di un codice: –  il minimo numero di bit di cui differiscono due parole qualsiasi del codice •  Se n=M (codice NON ridondante) H=1 •  Se c’è ridondanza (n>M, codice ridondante) H≥ 1 Esempi •  Non sempre se n>M allora H>1. •  Esempio: •  Alfabeto = {A, B, C} Quanto vale M? Codici a rivelazione/correzione degli errori •  In un sistema di comunicazione reale il segnale trasmesso può essere affe:o da errori. •  Ci sono due approcci al tra:amento degli errori –  Includere abbastanza informazione aggiunFva in modo da poter ricostruire il messaggio originario (correzione dell'errore) –  Includere meno informazione aggiunFva, in modo da accorgersi che c'è stato un errore, senza per questo essere in grado di correggerlo (rilevazione dell'errore). •  Normalmente, il segnale consiste di : n = m + r bit, dove: –  m bit cosFtuiscono il messaggio vero e proprio; –  r bit sono ridondan4, e sono de; redundant bit (o check bit). Codici a rivelazione/correzione degli errori •  Le capacità di rilevare o correggere gli errori dipendono stre:amente dalla distanza di Hamming del codice scelto. •  Per rilevare R errori serve un codice con distanza di Hamming pari a H=(R+1), quindi H>1 –  Infa;, in questo caso qualunque combinazione di R errori non riesce a trasformare una parola valida in un’altra parola valida, per cui si ha per forza una parola non valida, che quindi rivela il fa:o che ci sono sta4 degli errori. •  Per correggere C errori serve un codice con distanza di Hamming pari a H=(2C+1), quindi H>2 –  Infa; in questo caso una parola contenente fino a C errori è più vicina a quella originaria che a qualunque altra parola valida. Capacità rivela4va di un codice •  Se si è verificato un numero di errori minore di Hmin, la parola ricevuta non è una parola prevista dal codice e quindi è possibile rivelare gli errori. •  Se si è verificato un numero di errori maggiore o uguale a Hmin, la parola ricevuta potrebbe corrispondere ad una parola di codice. In tal caso non sarebbe possibile rivelare gli errori. •  La regola da u4lizzare per valutare la capacità rivela4va di un codice è la seguente: •  Capacità rivela4va pari a l errori per parola Hmin ≥ l +1 Capacità corre;va di un codice •  Se si è verificato un numero di errori minore di Hmin/2, possiamo correggere la parola ricevuta trasformandola nella parola di codice più vicina. •  Se si è verificato un numero di errori maggiore o uguale a Hmin/2, non possiamo correggere la parola ricevuta (la parola di codice ad essa più vicina potrebbe non essere la parola che era stata trasmessa). •  La regola da u4lizzare per valutare la capacità corre;va di un codice è la seguente: •  Capacità corre;va pari a t errori per parola Hmin≥ 2t +1 Esempio • 
• 
• 
• 
• 
Date le due parole di codice: X1=(000), X2=(111); Distanze di Hamming: H(X1,X2)=3; Distanza minima del codice: Hmin=3; •  Un codice di questo 4po può rivelare sino a 2 errori (2 4pologie di errori, 1 bit o 2 bit) e correggere sino a 1 errore (1 4pologia di errore, 1 bit sbagliato) Esempio Dato il codice composto dalle seguen4 parole: X1=(000), X2=(011), X3=(101), X4=(110); Distanze di Hamming: H(X1,X2)=2, H(X1,X3)=2, H(X1,X4)=2, H(X2,X3)=2,H
(X2,X4)=2, H(X3,X4)=2; •  Distanza minima del codice: Hmin=2; • 
• 
• 
• 
•  Questo codice può rivelare 1 errore, mentre non può essere u4lizzato per la correzione di errori Codici Ridondan4 a Rivelazione: parità •  È un codice con H = 2 •  Si o;ene dal codice non ridondante aggiungendo 1 bit in modo che il numero complessivo di bit uguali a “1” sia pari (parità pari) o dispari (parità dispari) •  Avendo H=2 può solo rilevare gli errori, e solo se ques4 accadono singolarmente o in un numero dispari nella stessa parola di codice Codici di Hamming •  Codici ridondan4 con H>2 e perciò con capacità di auto correzione. •  Il più noto e semplice(H=3) prevede di inserire in un codice non ridondante di m bit r bit di controllo in par4colari posizioni . •  Perché possa essere corre:o un errore (singolo) deve valere: m ≤ 2r –r –1 –  Corregge un bit in posizione arbitraria –  Rivela la presenza di un solo errore –  Funziona bene se gli errori sono distribui4 casualmente •  Esempio: parola di 7 bit (m = 7) •  Per creare un codice di Hamming con H=3 (C = 1) bisogna rispe:are la relazione precedente e quindi usare 4 bit di controllo aggiun4vi (r = 4). Esempio: parità •  Devo trasme:ere la seguente parola (con parità dispari): 0100