Sistemi numerazione IV - lepillole.it · Esempio:*somma 100.01101 Bitdi* segno=0 5*bit...
33
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
Transcript of Sistemi numerazione IV - lepillole.it · Esempio:*somma 100.01101 Bitdi* segno=0 5*bit...
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
