La codifica binaria della informazione
<html>
<head> <meta http-equiv=Content-Type content="text/html; charset=windows-1252"> <meta name=Generator content="Microsoft Word 14 (filtered)"> <title>Microsoft Word - La codifica binaria dell'informazione_revisione2012.doc</title> <style> </style>
</head>
<body lang=IT>
La codifica binaria della informazione
Vitoantonio Bevilacqua
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.
Indice
1 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.
2 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.
3 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”:
(1010.101)2 = (1 x 23+ 0 x 22+1 x 21+ 0 x 20 + 1 x·2-1+ 0 x 2-2 + 1 x·2-3)10=(10.625)10
Codifica binaria di un numero: per l’operazione inversa, si utilizzano due algoritmi rispettivamente per la parte intera e decimale del numero:
3.1 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.
3.2 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.
<img width=104 height=394 src="1%20Prima%20Dispensa%20-La%20codifica%20binaria%20dell%20informazione_revisione2015_file/image001.gif" align=left hspace=12>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
(127.4)10 = (1111111.0110)2 = (127.375)10
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: 𝑒𝑎= 127.4 – 127.375 = 0.025
• Errore relativo<img width=50 height=20 id="Picture 10409" src="1%20Prima%20Dispensa%20-La%20codifica%20binaria%20dell%20informazione_revisione2015_file/image002.gif">dove num è il numero iniziale rispetto al quale si è commesso l’errore di codifica
Esempio: <img width=53 height=21 id="Picture 10410" src="1%20Prima%20Dispensa%20-La%20codifica%20binaria%20dell%20informazione_revisione2015_file/image003.gif">
• Errore relativo percentuale 𝑒𝑟% = 𝑒𝑟 ∗ 100
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
[0, 2𝑛 − 1].
La formula deriva dal numero di combinazioni diverse che si possono ottenere
2𝑛 = 256 Tenendo conto che si inizia la numerazione da 0.
Essendo 8 i bit: [0, 255]
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 24 = 16 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 65.25: (65.25)10 = (1000001.01)2;
0100 0001 .0100
4 1 .4
Dunque (65.25)10 = (41.4)16
3.3 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: n = 8, range [-127,+127]
(−11)10 = (0011011)2
<img width=189 height=35 id="Picture 721" src="1%20Prima%20Dispensa%20-La%20codifica%20binaria%20dell%20informazione_revisione2015_file/image004.jpg">
In questo caso le combinazioni si riducono a 255 causa la doppia rappresentazione dello 0: 10000000 = 00000000 = 0 e il range è: [-(2n-1-1),2n-1-1] = [-127,127].
3.4 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.
3.5 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 00000000 = 0; in questo caso il range varia tra [-(2n-1),2n-1-1] = [-128,127].
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]
28 𝑐𝑜𝑚𝑏𝑖𝑛𝑎𝑧𝑖𝑜𝑛𝑖
8 bit necessari
Il valore assoluto è: (65)10 = (01000001)2 Faccio il complemento a 1: 10111110
Il complemento a 2 è: 10111110 + 1 = 10111111
4 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:
± esponente mantissa
1 8 23
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 (2𝑛−1 −
1, 𝑑𝑜𝑣𝑒 𝑛 è 𝑖𝑙 𝑛𝑢𝑚𝑒𝑟𝑜 𝑑𝑖 𝑏𝑖𝑡 𝑟𝑖𝑠𝑒𝑟𝑣𝑎𝑡𝑖 𝑎𝑙𝑙′𝑒𝑠𝑝𝑜𝑛𝑒𝑛𝑡𝑒) 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: (118)10 = (1110110)2 Codifico la parte decimale: (0.625)10 = (.101)2
• 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:
0.1110110101*27
• La mantissa matematica è: 1110110101
• Sposto la virgola fino alla destra dell’ultima cifra diversa da zero e riequilibrio l’ordine di grandezza:
1.110110101*26
• La mantissa normalizzata è: 110110101
• Codifico l’esponente: 6 + 27 − 1 = 6 + 127 = 5 + 128 = 10000101
• La rappresentazione secondo lo standard IEEE754 a single precision è:
1 1000101 11011010100000000000000
± esponente mantissa
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)
± esponente mantissa
1 11 52
Il metodo di rappresentazione è simile a quello usato per lo standard a single precision, l’unica cosa che varia è il bias:
211−1 − 1 = 1023
I valori assunti dall'esponente e dalla<a href="https://it.wikipedia.org/wiki/Mantissa"> </a><a href="https://it.wikipedia.org/wiki/Mantissa">mantissa</a><a href="https://it.wikipedia.org/wiki/Mantissa"> </a>determinano l'appartenenza del numero ad una di queste categorie:
• Zeri;
• Numeri in forma normale;
• Numeri in forma<a href="https://it.wikipedia.org/wiki/Numeri_denormalizzati"> </a><a href="https://it.wikipedia.org/wiki/Numeri_denormalizzati">denormalizzata</a><a href="https://it.wikipedia.org/wiki/Numeri_denormalizzati">;</a>
• Infiniti;
• NaN (not a number).
|
Categoria |
Esp. |
Mantissa |
|
Zeri |
0 |
0 |
|
Numeri denormalizzati |
0 |
non zero |
|
Numeri normalizzati |
1-254 |
qualunque |
|
Infiniti |
255 |
0 |
|
Nan (not a number) |
255 |
non zero |
5 Verso il linguaggio C
Per specificare il tipo di variabile (tipo di rappresentazione usata per la codifica della variabile) esistono istruzioni dette
“specificatori di tipo”:
• “char a”: carattere = variabile a memorizzata in 1 byte, codificata secondo C.A.2
• “int b”: intero = variabile b memorizzata in 2 o 4 byte (4 in VisualC++ 6.0), codificata secondo C.A.2 “float c”: single = variabile c memorizzata in 4 byte, codificata secondo IEEE754 single p.
• “double d”: double = variabile d memorizzata in 8 byte, codificata secondo IEEE754 double p.
Non indicando niente davanti agli specificatori di tipo, si sottintende “signed”. Per specificare che la variabile è senza segno, si scrive “unsigned” davanti agli specificatori di tipo e la codifica avverrà senza segno.
Per dimensionare una variabile, esistono gli specificatori “short” e “long” da scrivere davanti agli specificatori di tipo per, rispettivamente, dimezzare o raddoppiare il numero di byte necessari alla rappresentazione.
Per assegnare ad una variabile a il valore n si utilizza l’assegnazione “ a = n ; ” e, a seconda del tipo specificato di variabile, il calcolatore memorizzerà il valore n nel primo pacchetto libero di byte in modo che il primo byte sia multiplo di 4.
L’indirizzo di una variabile “a” è indicato con “&a” ed è quindi multiplo di 4. N.B. la riga di codice a=a+1; non è un’uguaglianza, ma un’assegnazione!
Il calcolatore all’indirizzo &a sovrascriverà al valore della variabile a, che quindi sarà perso, il valore incrementato di 1.
Ringraziamenti. Il presente capitolo è stato scritto anche grazie al prezioso contributo dello studente Donato Mancuso con la successiva revisione del suo collega Pasquale Bonasia.
Riferimenti
1. Bevilacqua, V.: Dispense Teoria 1 e IEEE 754 In: http://www.vitoantoniobevilacqua.it
2. http://it.wikipedia.org/wiki/IEEE_754
3. http://it.wikipedia.org/wiki/Ordine_dei_byte
Appendice: Codice in linguaggio C (per ora solo di test)
#include <stdio.h>
#include <conio.h> /* non ANSI C */
/*#include <math.h> per usare la funzione pow*/ int main() { unsigned char byte[4]; unsigned char *c; char bit[9]; int i,j; float a; float *p=NULL;
a=0;
printf("Le dimensioni in byte di variabili \n"); printf("char, int, double e float valgono \n");
printf("%d %d %d %d\n",sizeof(char),sizeof(int),sizeof(float),sizeof(double));
do {
printf("inserisci a = "); scanf("%f",&a);
/*a=(float)pow(2, -2);utile per trovare il range di rappresentazione*/ p=&a;
c=(unsigned char *)p;
printf("%d %d %d %d\n",*(c+3),*(c+2),*(c+1),*c); printf("\n"); for(i=0;i<4;i++)
{
byte[i]=*(c+3-i); j=0;
while (byte[i]>0)
{
bit[j]=byte[i]%2; byte[i]= byte[i]/2; j=j+1; }
for(;j<8;bit[j++]=0); for(j=7;j>=0;j--) printf("%d",bit[j]); printf(" ");
} printf("\n \n"); printf("altro numero?\n");
}
while(getch()!='n');
return 0;
}
</body>
</html>
