La codifica binaria della informazione: differenze tra le versioni

Versione delle 14:50, 1 ott 2016

Vitoantonio Bevilacqua La codifica binaria della informazione bevilacqua@poliba.it

Sommario. Il presente paragrafo si riferisce alle prime due lezioni del corso di Fondamenti di Informatica e Laboratorio di Informatica. Parole chiave: Codifica Binaria, Memoria RAM, Complemento a 2, IEEE 754 a singola e doppia precisione.

Introduzione

Il fine principale degli argomenti trattati in queste iniziali lezioni consiste nell'illustrare in quale maniera l'informazione, per adesso soltanto numerica, viene memorizzata nella memoria RAM (Random Access Memory) di un sistema di calcolo rispettando standard condivisi, per poi essere elaborata attraverso un linguaggio di programmazione. In particolare si tratteranno: la codifica binaria, la codifica esadecimale, le conversioni di base, il concetto di errore di una codifica, la codifica di numeri interi con e senza segno in CA2 (complemento a 2), la codifica di numeri reali in singola e doppia precisione secondo lo standard IEEE 754, gli effetti sulla dichiarazione delle variabili signed e unsigned di tipo char ed int, e delle variabili float e double in linguaggio C.

La memoria di lavoro

La memoria RAM (Random Access Memory) è la memoria di lavoro (elaborazione) di un sistema di calcolo; per semplicità essa può essere rappresentata come una tabella organizzata in righe, ciascuna delle quali (per ora chiamata word) viene suddivisa in 4 colonne o blocchi, da ora in poi chiamati byte, costituiti da una sequenza di 8 bit (binary digit) ovvero 8 cifre che possono assumere soltanto valori 0 o 1. In generale, ogni programma di elaborazione si occupa della gestione delle informazioni per unità elementari corrispondenti alla dimensione dei byte, senza necessariamente scendere al livello di dettaglio dei singoli bit, per questo motivo si dice che la unità minima indirizzabile (ovvero dotata di un indirizzo in memoria corrispondente alla posizione in memoria RAM) è il singolo byte. Il modo più diffuso di numerare i byte, iniziando sempre dal numero progressi 0, è da destra verso a sinistra (“little Endian”), laddove il verso dall’alto verso il basso è ovviamente relativo a come più avanti si dirà essere partizionata la intera memoria RAM.

Le regole per le trasformazioni di base

Dato un numero, le basi del sistema di numerazione che si usano per leggere tale numero sono la base 2 (binaria), 8 (ottale), 16 (esadecimale); assegnata una base del sistema di numerazione, le cifre sono date da 0 fino a numero base – 1. Dopo la cifra 9, si aggiungono A, B, C, D, E, F per formare la base di un sistema esadecimale.

Assegnato un numero codificato in base 2, si decodifica facilmente in base 10; esempio della codifica chiamata “in binario puro”:

[math](1010.101)_2 = (1 * 2^3+ 0 * 2^2+1 x 2^1+ 0 * 2^0 + 1 * 2^{-1}+ 0 * 2^{-2} + 1 * 2^{-3})_{10}=(10.625)_{10} [/math]

Codifica binaria di un numero: per l’operazione inversa, si utilizzano due algoritmi rispettivamente per la parte intera e decimale del numero:

Algoritmo di Horner - divisioni successive

Si prende il numero intero, si mette in colonna a sinistra, lo si divide per 2, riportando quoziente sotto il dividendo mentre il resto accanto al dividendo, e così via fino a raggiungere il quoziente 0. La parte intera del numero in binario è la sequenza dei resti, presa dal basso verso l’alto.

Algoritmo di Horner - moltiplicazioni successive

Si prende il numero decimale, si mette in colonna a sinistra, lo si moltiplica per 2, riportando:

1. Se il prodotto è ≥1, accanto al primo fattore 1 e sotto il complemento del prodotto
2. Se il prodotto è <1, accanto al primo fattore lo 0 e sotto il prodotto

Cosi via, fino a raggiungere il prodotto 0. La sequenza da prendere come parte decimale del numero in binario è la sequenza di destra presa dall’alto verso il basso.

File:Passo3:right

Mentre nell’algoritmo delle divisioni lo 0 si raggiunge sempre, nell’algoritmo delle moltiplicazioni non è sempre possibile raggiungerlo e ciò dipende dal concetto di periodo della base; il periodo si ripete dal momento in cui si trova un numero già trovato in precedenza.

Esempio: Codifica in binario e ricodifica in decimale del numero 127.4

[math](127.4)_{10} = (1111111.0110)_2 = (127.375)_{10} [/math]

Nel momento in cui si accetta un periodo, si commette un “errore di codifica”. Si definisce:

• Errore assoluto 𝑒𝑎lo scarto tra il numero iniziale da codificare e il numero ottenuto dopo la ricodifica nella stessa base di partenza. Esempio: [math]= 127.4 – 127.375 = 0.025[/math]
• Errore relativo [math]e_r =\frac{e_a}{num}[/math] dove num è il numero iniziale rispetto al quale si è commesso l’errore di codifica

Esempio: [math]e_r = \frac{0.025}{127.4} [/math]

• Errore relativo percentuale [math] e_{r\%} = e_r * 100 [/math]

Concetto di range (intervallo di rappresentazione di un numero): preso un byte, supponendo che, avendo a disposizione n bit, tutti gli n codificano numeri interi in base binaria, il range di rappresentazione varia tra [math][0, 2^n − 1][/math]

La formula deriva dal numero di combinazioni diverse che si possono ottenere [math]2^n = 256[/math] Tenendo conto che si inizia la numerazione da 0. Essendo 8 i bit: [0, 255]

Codifica esadecimale di un numero

La codifica esadecimale di un numero è necessaria per minimizzare il codice; per eseguirla si possono utilizzare due metodi:

1. Gli algoritmi da usare sono sempre gli algoritmi di Horner, con le opportune modifiche (in colonna si moltiplica e divide per 16). Infatti i due algoritmi sono generici, nel senso che, non dipendono dalla base in cui è rappresentato un numero.
2. Si codifica in binario il numero, quindi, essendo [math]24 = 16[/math] si raccolgono le cifre a 4 a 4, a partire dalla virgola e si decodifica da base binaria a base decimale ciascuno dei blocchi Esempio:

Codifica in esadecimale di [math] 65.25 : (65.25)_10 = (1000001.01)_2[/math]

Dunque [math](65.25)_{10} = (41.4)_{16} [/math]

Rappresentazione con modulo e segno (“signed magnitude” o M&S)

Per rappresentare un numero con segno, si usa, per convenzione:

• Un bit per il segno: 0 per + (più), 1 per – (meno)
• N-1 bit per il modulo

Il bit che codifica il segno è definito MSB (Most Significant Bit, il primo bit, il più significativo). Esempio:[math] n = 8[/math], range [math][-127,+127] [/math] [math](−11)_10 = (0011011)_2 [/math]

In questo caso le combinazioni si riducono a 255 causa la doppia rappresentazione dello 0: [math]10000000 = 00000000 = 0[/math] e il range è: [math][-(2^{n-1}-1),2^{n-1}-1] = [-127,127]. [/math]

L’operazione di complemento a uno. (CA1)

E’ un’operazione molto semplice per un sistema di calcolo ed è alla base dell’operazione di complemento a due grazie alla quale è possibile rappresentare numeri interi negativi e positivi. Per trovare la rappresentazione in complemento a uno si invertono semplicemente tutti i bit della parola.

La codifica in complemento a due per i numeri con segno (CA2)

Il complemento a due è il metodo più diffuso per la rappresentazione dei numeri con segno. Il valore da utilizzare relativamente al MSB risulta essere il suo opposto (questo implica che se vale 0 porta a una decodifica di valore uguale alla rappresentazione in binario puro):

00000000=0

00000001=1

…

01111111=+127

10000000=-1⋅27=-128

10000001=-128+1=-127

…

11111111=-1

Le combinazioni sono 256 per la rappresentazione univoca dello 0: ovvero soltanto [math]00000000 = 0[/math]; in questo caso il range varia tra [math][-(2^{n-1}),2^{n-1}-1] = [-128,127] [/math] .

Per codificare un numero in complemento a due:

1. Si sceglie il range per il quale è possibile codificare il numero e di conseguenza i bit necessari
2. Si rappresenta il valore assoluto del numero in binario
3. Si applica l’operazione di complemento a 1 e si somma 1
4. La sequenza ottenuta è la codifica del numero iniziale in complemento a due Esempio:

Si vuole codifica in complemento a 2 il numero -65

Il range varia tra [-128,127]

[math]2^8[/math] combinazioni 𝑐𝑜𝑚𝑏𝑖𝑛𝑎𝑧𝑖𝑜𝑛𝑖

8 bit necessari

Il valore assoluto è: [math](65)_10 = (01000001)_2 [/math]

Faccio il complemento a 1: [math]10111110 [/math]

Il complemento a 2 è:[math] 10111110 + 1 = 10111111 [/math]

Lo standard IEEE 754

Standard IEEE 754 single precision: Rappresentazione di un numero reale in 32 bit. I 32 bit vengono suddivisi in 3 gruppi:

Il modulo del numero viene codificato in base binaria usando gli algoritmi di divisione e moltiplicazione successive evidenziando, nella parte decimale, un periodo ove ci fosse. La rappresentazione binaria risultante è detta “fixed point” (a virgola fissa). Si passa alla rappresentazione “floating point” (a virgola mobile) per determinare mantissa ed esponente. Si sposta la virgola fino alla sinistra dell’ultima cifra diversa da zero, cambiando anche l’esponente per riequilibrare l’ordine di grandezza. La parte dopo la virgola indica la mantissa matematica. Se si sposta la virgola alla destra dell’ultima cifra diversa da zero, cambiando anche l’esponente:

• La parte del numero dopo la virgola indica la mantissa normalizzata che, se composta da un numero di cifre < 23, ai restanti bit si assegna valore 0
• Per codificare l’esponente, si usa la rappresentazione per eccesso: si somma l’esponente al bias [math](2^{n−1} − 1)[/math] dove n è il numero di bit riservati all'esponente e quindi si codifica il numero

Esempio: Si vuole codificare secondo lo standard IEEE754 a single precision, il numero -118.625

• Codifico la parte intera: [math](118)_{10} = (1110110)_2[/math]
• Codifico la parte decimale: [math](0.625)_{10} = (.101)_2[/math]
• La rappresentazione in fixed point è: 1110110.101
• Sposto la virgola fino alla sinistra dell’ultima cifra diversa da 0 e riequilibrio l’ordine di grandezza: [math]0.1110110101*2^7[/math]
• La mantissa matematica è: 1110110101
• Sposto la virgola fino alla destra dell’ultima cifra diversa da zero e riequilibrio l’ordine di grandezza: [math]1.110110101*2^6[/math]
• La mantissa normalizzata è: 110110101
• Codifico l’esponente: [math]6 + 2^7 − 1 = 6 + 127 = 5 + 128 = 10000101 [/math]
• La rappresentazione secondo lo standard IEEE754 a single precision è:

L’ordine di precisione delo standard IEEE754 è dato dal numero di cifre della mantissa. Per ottenere una rappresentazione più precisa si usa lo standard IEEE754 a double precision (64 bit)

Il metodo di rappresentazione è simile a quello usato per lo standard a single precision, l’unica cosa che varia è il bias: [math]2^{11−1} − 1 = 1023 [/math] I valori assunti dall'esponente e dalla mantissa determinano l'appartenenza del numero ad una di queste categorie:

• Zeri;
• Numeri in forma normale;
• Numeri in forma denormalizzata;
• Infiniti;
• NaN (not a number).