Altri sistemi numerici ed ultime note sulla conversione

Consideriamo una combinazione (o parola) generica di m posizioni i cui caratteri sono presi dall’alfabeto associato alla base b.
Cm-1 ... C0
Ci chiediamo quante sono le parole distinte che possiamo creare. 
Ebbene, data una base generica b ed un numero di cifre m, il numero massimo di combinazioni distinte costituite da m caratteri dell’alfabeto associato alla base b scelta, è pari a bm.

Ci possiamo convincere rapidamente di tale risultato; poiché l’alfabeto della base b è costituito da ‘b’ elementi (0,1,...,b-1), dovendo fissare un carattere per la prima posizione della combinazione (C0), possiamo scegliere tra i ‘b’ simboli disponibili. Quindi se m fosse uguale ad uno, cioè fossimo interessati solo a parole costituite da un unico carattere, il numero di tali parole sarebbe pari a ‘b’. Se invece fossimo interessati a parole lunghe due caratteri (m=2), opereremmo nel modo seguente. Prenderemmo in considerazione, ad una ad una, tutte le parole lunghe un carattere (costruite al passo precedente) ed “attaccheremmo” a ciascuna di esse un secondo carattere (posizione C1), scegliendolo tra tutti quelli dell’alfabeto disponibile (che sono ancora in numero di ‘b’). In tal modo ogni parola lunga un carattere genererà ‘b’ parole lunghe due caratteri. Ma allora se le parole lunghe un carattere erano in numero di ‘b’, le parole lunghe due caratteri saranno in numero di (b·b)=b2. E’ facile iterare il procedimento per ottenere parole via via più lunghe. 
Per chiarire le idee vediamo come si sviluppa la costruzione di parole con alfabeto binario (b=2).

Il massimo numero naturale che possiamo esprimere con una codifica posizionale in base b, utilizzando parole lunghe m cifre, è pari a bm-1. Infatti le parole di codifica saranno bm ma i numeri da codificare inizieranno da zero.
 
Nell’ambito degli elaboratori elettronici, oltre alla codifica binaria, sono spesso utilizzate la codifica ottale (base=8) e quella esadecimale (base = 16). Il loro impiego deriva essenzialmente dal fatto che tali notazioni sono più coincise di quella in base 2 (a parità di numero da rappresentare impiegano meno cifre).

Codifica ottale:
La base è b=8 e l’alfabeto delle cifre è C = {0,1,2,3,4,5,6,7}
ES.	7(8) + 3(8) = 12(8)
Verifichiamolo eseguendo la conversione in decimale:
7(8) = 7(10)	e	3(8) = 3(10)	e	12(8) = 1·81 + 2·80 = 10(10)

Codifica esadecimale:
La base è b=16 e l’alfabeto delle cifre è C= {0,1,2,3,4,5,6,7,8,9,A,B,C,D,E,F}
ES. 	D(16) + 9(16) = 16(16)
Verifichiamolo eseguendo la conversione in decimale:
D(16) = 13·160 = 13(10)		9(16) = 9·160 = 9(10)		16(16) = 1·161+ 6·160 = 22(10)

Poiché tali basi sono esprimibili come potenze del due:

81 = 23		161 = 24
da tali equivalenze si ha che:
•	una cifra ottale può rappresentare sino ad un numero naturale massimo che è pari a quello esprimibile in binario utilizzando però tre cifre.
•	una cifra esadecimale può rappresentare sino ad un numero naturale massimo che è pari a quello esprimibile in binario utilizzando però quattro cifre.

 Questa osservazione ci indica la strada per poter effettuare molto facilmente le conversioni binario – ottale (e viceversa) e binario – esadecimale (e viceversa).

Binario  Ottale e viceversa
Se, come abbiamo osservato, una cifra ottale è in grado di esprimere quello che esprimono ben tre cifre binarie, allora possiamo operare la conversione in questa maniera:

cioè sostituiamo ogni tre cifre binarie con la cifra ottale numericamente equivalente.
Viceversa sostituiamo ogni cifra ottale con l’equivalente numerico in binario (tre cifre).

Binario  Esadecimale e viceversa
Se, come abbiamo osservato, una cifra esadecimale è in grado di esprimere quello che esprimono ben quattro cifre binarie, allora possiamo operare la conversione in questa maniera:

cioè sostituiamo ogni quattro cifre binarie con la cifra esadecimale numericamente equivalente.
Viceversa sostituiamo ogni cifra esadecimale con l’equivalente numerico in binario (quattro cifre).

In generale questo tipo di facili conversioni possono avvenire ogni qual volta, dette b1 e b2 le due basi rispetto alle quali eseguire la conversione, si abbia : 

b1= b2k   con b1, b2, k appartenenti ai naturali

Possiamo dare uno sguardo un po’ più rigoroso a questo tipo di conversioni. Supponiamo di avere la codifica di un numero in base b2 e di voler ottenere quella in base b1 sapendo che tra loro esiste l’equivalenza b1= b2k (con k numero naturale).

bn(b2)n + ... + b2k-1(b2)2k-1 + ... + bk(b2)k + bk-1(b2)k-1 + ... + b2(b2)2 + b1(b2)1 + b0(b2)0
										A
Ora, poiché b2k indica, come visto in precedenza, il massimo numero naturale esprimibile con k cifre nella notazione in base b2, l’equivalenza b1= b2k ci dice che una singola cifra della notazione in base b1 ha la stessa capacità espressiva. Quindi il termine A è sostituibile con l’equivalente cifra in base b1. Consideriamo poi i successivi k termini (da k a 2k-1).

b2k-1(b2)2k-1 + ... + bk(b2)k

Mettendo in evidenza la potenza k-esima di b2 otteniamo:

[ b2k-1(b2)k-1 + ... + bk(b2)0 ]· (b2)k
						    B

Il termine B è analogo al termine A visto in precedenza e può essere rappresentato con un’unica cifra in base b1. Iterando il procedimento possiamo porre l’attenzione sui successive k cifre (da 2k a 3k-1) e mettere in evidenza la potenza (b2)2k.
A questo punto risulta evidente il tipo di espressione che otteniamo:

... + C·(b2)2k + B·(b2)k + A·(b2)0

dove le cifre A,B,C,... appartengono all’alfabeto della base b1.
Poiché b1= b2k allora b12= b22k , b13= b23k ... e sostituendo abbiamo:

... + C·(b1)2 + B·(b1)1 + A·(b1)0

cioè ...CBA rappresentano proprio la codifica in base b1 del numero rappresentato in base b2 dalla sequenza di cifre bn bn-1 ... b1 b0.

Come ultimo esempio di conversione tra codifiche, vediamo quello relativo a due basi generiche g1 e g2. Supponiamo di avere la codifica del numero N in base g1 e di voler ottenere quella in base g2. Una volta espressa la base g2 in base g1 eseguiremo:
•	il metodo divisivo (con l’aritmetica della base g1) tra la parte intera del numero N e g2
•	il metodo moltiplicativo (con l’aritmetica della base g1) tra la parte frazionaria del numero N e g2

ES.
Vogliamo ottenere la codifica in base 5 del seguente numero espresso in base 2:

100011.1011(2)   ? (5)
Prima convertiamo la base 5 in binario:
5(10) = 101(2)

Parte intera : (metodo divisivo)
Nota: i numeri che seguono sono tutti espressi in binario
100011 / 101 	= 111	resto 0	a0
111/101	= 1	resto 10
1/101	= 0	resto 1	a3
Convertiamo i resti da binario a base 5 per ottenere le cifre della codifica che ci interessa.
0(2) 	= 0(5)
10(2) 	= 2(5)			100011(2) = 120(5)
1(2) 	= 1(5)

Parte decimale : (metodo moltiplicativo)
Nota: i numeri che seguono sono tutti espressi in binario
0,1011·101	= 11	+ 0,0111	a-1
0,0111·101	= 10	+ 0,0011
0,0011·101	= 0	+ 0,1111
0,1111·101	= 100	+ 0,1011	a-4
Considerando le parti intere e convertendole in base 5 otteniamo:
11(2) = 3(5)
10(2) = 2(5)	  0,1011(2) = 0,3204(5) +  
100(2) = 4(5)			 = errore che si commette arrestando il procedimento alla quarta cifra decimale.

Aritmetica sui binari

Vediamo ora le quattro operazioni eseguite sui numeri in codifica binaria.

Somma : Per sommare due numeri consideriamo singolarmente la somma delle cifre che occupano posizioni omologhe dal punto di vista del peso. Quando la somma di due cifre alla posizione generica k va oltre la possibilità di rappresentazione con la singola cifra, si considera il riporto di uno per la somma delle cifre in posizione k+1.
Le regole per la somma di due cifre binarie sono:

0+0=0
0+1=1
1+0=1
1+1=0 con il riporto di 1
ES.
1001101(2)+ 1010(2)			       R
	corretto allineamento	1001101 +
      1010
					1010111

Differenza : Vale un discorso analogo a quello fatto per la somma. In questo caso però, quando la cifra del sottraendo è superiore a quella del minuendo, si deve considerare un riporto negativo per le cifre alla posizione immediatamente superiore.

0-0=0
1-0=1
1-1=0
0-1=1 con il riporto negativo di 1
ES.
1001101(2) - 1010(2)			         R
1001101 -
      1010
					1000011

Moltiplicazione : La moltiplicazione binaria, intesa come addizione ripetuta, segue le stesse regole della moltiplicazione decimale. Essa soddisfa la seguente tabella:

0·0=0
1·0=0
0·1=0
1·1=1
ES.
1111(2) · 10(2)		
1111 ·
10
0000
	1111/
	11110

Divisione : La divisione nel sistema binario segue lo schema della divisione nel sistema decimale e può essere eseguita contando quante volte un numero può essere sottratto ad un altro. Il risultato è detto quoziente. In realtà questa operazione viene eseguita nei calcolatori elettronici per sottrazioni ripetute.

ES.
1111(2) · 100(2)		
1111	100
100	11,11
 \111
	    100
	\ 110
	  100
   \100
  100
  000

Rappresentazione dei numeri negativi

Estendiamo ora il nostro sistema di codifica numerica per poter rapresentare oltre ai numeri naturali N (0,1,2…), anche gli interi Z (…,-2,-1,0,1,2,…) cioè l’insieme costituito dai naturali con segno (+,-). 
In questa sezione vedremo i tre metodi più utilizzati, in particolar modo per quanto riguarda la codifica binaria. 

•	Rappresentazione con il bit del segno
•	Complemento a 1
•	Complemento a 2

Nota: è bene puntualizzare, anche se lapalissiano, che il tipo di rappresentazione adottato per trattare i numeri negativi deve essere noto a tutti i sistemi che intendono comunicare tra loro. Infatti non vi è alcun modo, guardando per esempio un numero in codifica binaria, di capire con quale rappresentazione è espresso e tantomeno se trattasi di un numero positivo o negativo. 

Bit del segno:
In questo tipo di codifica la cifra più significativa indica il segno.
Supponendo quindi che cn … c3 c2 c1 c0 sia la codifica di un numero, con la cifra cn indichiamo se il numero è positivo o negativo.
Si usa normalmente indicare con la cifra ‘0’ i numeri positivi e con ‘1’ quelli negativi.
Le cifre restanti (modulo) indicano il numero al quale va applicato il segno.
Così, immaginando di trattare codifiche numeriche a sette cifre, il numero 1011110(2) rappresenta –30(10) e 0011110(2) rappresenta 30(10).
Detto n il numero di cifre e b la base adottati per la rappresentazione, l’intervallo numerico massimo con questo tipo di codifica è:

da   -b(n-1)   a b(n-1)

Le operazioni aritmetiche si effettuano sui soli moduli con le regole viste in precedenza. E’ necessario però analizzare il segno degli operandi per comprendere il tipo di operazione da effettuare (infatti, in questo contesto, una somma può tradursi in una differenza 4+ [-7]  4-7 ) e per valutare il segno del risultato.

Complemento a 1:
Stabiliamo innanzi tutto di indicare con m il numero di cifre utilizzato per la rappresentazione. Questo significa che potremo ‘disporre’ di 2m combinazioni binarie (parole di codifica) per rappresentare gli elementi di un intervallo numerico (-n, n).
Il complemento a 1 di un numero c (ck…..c1c0) espresso in binario si ottiene sostituendo ciascuna cifra ci secondo l’espressione:

ci’ = 1- ci

Molto semplicemente possiamo affermare che l’operazione del complemento a 1 consiste nello scambiare le cifre a 0 con 1 e viceversa.
Il complemento a 1 di un numero espresso in binario rappresenta il suo opposto.
Con parole binarie di lunghezza m si possono rappresentare i numeri nell’intervallo:

[-(2m/2)+1, (2m/2)-1]

E’ stato scritto (2m/2), piuttosto che l’espressione equivalente 2m-1 , perché rende più chiaro il senso delle assegnazioni delle parole codice ai relativi numeri.
Vediamo graficamente il senso di questa ultima affermazione.
Supponiamo di avere a disposizione tre cifre per la rappresentazione (m=3). Tutte le possibili combinazioni sono riportate qui di seguito.

Configurazioni dello zero

000
001
010

Configurazioni 

Mezzeria delle configurazioni

011
100
101
110
111

Come si vede, la divisione per 2 del numero delle configurazioni (2m) sta ad indicare il fatto che esattamente metà di esse sono dedicate alla rappresentazione dei numeri positivi e l’altra metà a quelli negativi. La codifica dello zero è data dalla sequenza di zero e necessariamente anche dalla sequenza di tutti uno (il complemento a 1 di 0000…(2) è 1111…(2) ma non si può certo distinguere tra +0 e –0). 

m =3

Decimale	Codifica in complemento a uno	
0	000	
1	001	
2	010	
3	011	
- 3	100	
- 2	101	
- 1	110	
0	111	

Con l’impiego di questa codifica le differenze si tramutano in somme.
Vediamo un esempio di operazione.
Supponiamo di avere a disposizione tre cifre per la rappresentazione e di voler eseguire la ‘somma’:

2(10) + (-3)(10) = -1(10)

Ora 2 ha per codifica la sequenza 010 e –3 ha la sequenza 100.
Eseguendo la somma binaria tra i due otteniamo:

010 +
100
	110

dove 110(2) è esattamente la codifica di –1(10). 
Quando si esegue un’operazione il cui risultato è superiore alle capacità di rappresentazione si ha una condizione detta di overflow. In particolare questa si può presentare solo dalla somma di operandi con lo stesso segno (due negativi o due positivi) e si riconosce immediatamente dal fatto che il risultato ha segno diverso da quello degli operandi stessi (somma di due positivi… risultato negativo! e viceversa).

Complemento a 2:
Nel complemento a 2, una volta fissata la dimensione delle parole di codifica (m) l’opposto di un numero è dato da:
00…0(2) – (cm-1… c0)(2)
senza considerare gli eventuali riporti oltre l’m-esima cifra.

Con parole binarie di lunghezza m si possono rappresentare i numeri nell’intervallo:

[-(2m/2), (2m/2)-1]

In questo tipo di codifica esiste un’unica rappresentazione dello zero (0…0) e, in modo analogo a quanto visto per il complemento a 1, occorre prestare attenzione alle condizioni di overflow. 
Il complemento a due di un numero si può ottenere anche eseguendone prima il complemento a uno e poi sommando 1 al risultato. Vediamo un esempio di complemento a due eseguito in entrambi i modi.

Supponiamo di avere tre cifre a disposizione per la codifica e di voler ottenere il complemento a due del numero 011(2). 

000(2) – 011(2) = 101(2)
che si può ottenere anche eseguendo prima il complemento a uno:

011(2)	100(2)
e sommando poi 1 al risultato:

100(2) + 1(2) = 101(2)

Nota: è bene ricordare, ancora una volta, che gli eventuali riporti oltre l’m-esima cifra (spazio di rappresentazione) non vanno considerati!

Vediamo un esempio di operazione con questo tipo di codifica.
Supponiamo m=4 e consideriamo l’operazione 7(10) + (-3(10)) = 4(10).
Ora 7(10) ha per codifica 0111(2) e (-3(10)) ha per codifica:

Complemento a due 

Codifica binaria a 4 bit

3(10)  0011(2)  1101(2) 

Allora 7(10) + (-3(10)) si calcola come:

I riporti oltre l’m-esima cifra non si devono considerare.

0111+
1101
101004(10)

Come fatto per il complemento a uno, vediamo le associazioni tra numeri e relative codifiche con la tabella seguente:
m = 3
Decimale	Codifica in complemento a due	
0	000	
1	001	
2	010	
3	011	
- 4	100	
- 3	101	
- 2	110	
- 1	111	

Rappresentazione numerica in virgola mobile

I numeri vengono immagazzinati all’interno di un elaboratore, com’è ovvio aspettarsi, in spazi finiti (registro, locazione di memoria). Supponendo di avere a disposizione n elementi di memorizzazione, ciascuno in grado di trattenere l’informazione relativa ad una cifra binaria (0,1), potremmo dedicare una quota i delle n per la rappresentazione della parte intera del numero e le restanti (n – i) per la parte frazionaria. Questo tipo di rappresentazione si dice “in virgola fissa”.
Ipotizzate però ora di avere un processo i cui risultati oscillano tra valori infinitesimamente piccoli ed infinitamente grandi. Se dedicaste molte delle n posizioni a disposizione alla parte frazionaria, per ottenere una buona rappresentazione dei valori numerici molto piccoli, vi ritrovereste poi in difficoltà nel dover rappresentare i risultati con valore numerico molto elevato e viceversa.
Per ovviare a tale inconveniente si è definito uno standard di rappresentazione detto ”in virgola mobile”. Un numero N è identificato da una coppia di valori interi detti mantissa ed esponente (indicati rispettivamente con m ed e nel seguito), tali che, detta b la base nella quale si opera (normalmente b=2) si ha:

N = m·be

Vediamo un esempio di rappresentazione in virgola mobile considerando la base dieci (b = 10) per una maggiore immediatezza della comprensione.
N = 357,44(10)	  in virgola mobile  < 35744 ; -2 > = 35744 · 10-2 = 357,44(10)

Si è deciso poi, per quanto riguarda la mantissa, di esprimerla in una forma standard detta normalizzata. Affinché una mantissa sia in forma normalizzata occorre che:

1.	La parte intera di m sia uguale a zero
2.	La prima cifra a destra della virgola sia diversa da zero

Quindi la mantissa nella sua forma normalizzata è interna all’intervallo:

1/b    m  1

Poiché è nota a priori l’applicazione della normalizzazione, si rappresenta solo la parte decimale della mantissa (cifre a destra della virgola). Volendo quindi esprimere il numero N =357,44(10) con la notazione in virgola mobile normalizzata avremo:

0,35744 · 103    < 35744 ; 3 >

Mantissa in forma normalizzata

Normalmente per rappresentare anche i numeri negativi si utilizza la codifica con il bit del segno per la mantissa ed il complemento a due per l’esponente. Con quest’ultima notazione la rappresentazione in virgola mobile normalizzata è espressa dalla terna:

< S ; m’ ; e >   con m’ mantissa normalizzata

nella quale S indica il segno, 1  segno negativo , 0  segno positivo.
Vediamo un esempio completo di rappresentazione in virgola mobile normalizzata in base due. Supponiamo di avere 8 bit a disposizione dei quali 4 per la mantissa, 3 per l’esponente e 1 per il segno.

N= - 0,09375(10)
La conversione in binario di N è 0,00011(2). 
La sua normalizzazione è 0,11 · 2-3.
L’esponente –3 espresso in complemento a due è 101(2).
S =1 perché N è negativo.
Quindi la rappresentazione in virgola mobile sarà < 1 ; 1100 ; 101 >

Possiamo ora renderci conto della forza espressiva di questa notazione analizzando gli intervalli (range) di rappresentazione(‘E’ esprime il numero di bit dedicati all’esponente).

Numeri positivi: 

Numeri negativi:

Le operazioni con la notazione in virgola mobile

Dati due numeri N1<S1; m1 ; e1> e N2<S2; m2 ; e2> si ha, indicando con il pedice ‘r’ gli elementi del risultato:

Prodotto :N1·N2
Sr = 0 se S1=S2 ; 1 se S1S2   
er = e1 + e2
mr = m1·m2

Quoziente : N1/N2
Sr = 0 se S1=S2 ; 1 se S1S2   
er = e1 - e2
mr = m1/m2

Somma e sottrazione : 
Queste due operazioni meritano una discussione specifica.
Consideriamo, per fissare le idee, di dover eseguire l’operazione di somma. Tutto ciò che sarà detto vale in modo analogo per l’operazione di differenza.

Affinché sia possibile sommare due mantisse occorre ‘allineare’ le cifre dei due operandi in modo tale che si esegua correttamente la somma tra cifre con lo stesso peso (notazione posizionale).
Il problema quindi sorge solo quando e1  e2.
Vediamo di analizzare il problema utilizzando la base dieci e ovviamente la rappresentazione in virgola mobile normalizzata.

N1  <0 ; 249 ; 5 >  N2  <0 ; 364 ; 3 >

Ora N1= 0,249·105 = 24900 e N2= 0,364·103 = 364.
E’ chiaro che per eseguire la somma non è possibile sommare le due mantisse direttamente (0,249+0,364 !!!!?) ma occorre allineare le cifre con lo stesso peso. Per esempio la cifra 9 di N1 ha, guardando solo la mantissa, peso 10-3 che moltiplicato per 105, indicata dall’esponente, diventa 102. La cifra 4 di N2 ha peso 10-3 tenendo conto della sola mantissa, che diviene poi 100 considerando l’esponente. E’ quindi chiaro che per eseguire correttamente la somma (la differenza) tra due numeri espressi in virgola mobile, occorre, prima di tutto, portare gli esponenti allo stesso valore, così che le cifre delle mantisse assumano le corrette posizioni.

Supponiamo che si abbia e1 < e2.
Per allineare correttamente le cifre delle mantisse, è necessario moltiplicare N1 (quello con esponente minore) per una potenza della base in uso pari a . Questa operazione porterà l’esponente di N1 al valore di quello di N2. Ma per non alterare il valore del numero occorre anche dividere per la stessa potenza.
Vediamo l’esempio N1  <0 ; 249 ; 5 >  N2  <0 ; 364 ; 3 > per chiarire le idee.
Dobbiamo portare l’esponente e2 dal valore 3 al valore 5. Questo significa moltiplicare per una potenza della base dieci pari a 10(5-3):

0,364·103·102 = 0,364·105

Ora però, per non alterare il valore di N2 dobbiamo necessariamente anche dividere per la potenza di 102 (o equivalentemente moltiplicare per 10-2). Lasciando inalterato l’esponente facciamo in modo che tale operazione incida solo sulla mantissa:

0,364·105·10-2 = 0,00364·105

A questo punto è corretto eseguire la somma Nr tra N1 e N2 che ha per mantissa la somma delle mantisse e come esponente quello maggiore tra e1 ed e2.

Negli elaboratori elettronici, dove la rappresentazione dei numeri avviene necessariamente in spazi di dimensione finita, quando si moltiplica per una potenza della base di rappresentazione si dice anche che si esegue un’operazione di shift, verso destra se la potenza è negativa e verso sinistra se è positiva. Ipotizzando infatti di moltiplicare per la potenza bk (k positivo) si ottiene uno spostamento delle cifre del numero verso sinistra di k posizioni. Analogo il discorso se k è negativo nel qual caso si ottiene uno spostamento delle cifre del numero verso destra di k posizioni. 
Considerando uno shift verso destra (sinistra) le posizioni vuote che si vengono a creare a sinistra (destra) vengono ‘riempite’ con la cifra zero.
ES. Supponiamo che un’area dell’elaboratore possa contenere otto cifre binarie (per esempio un registro):

1	1	0	0	1	0	1	0	

Eseguendo una moltiplicazione per 23, cioè un’operazione di shift verso sinistra di tre posizioni otterremo come risultato :

1  1  0

 shift a sinistra
0	1	0	1	0	0	0	0	

			cifre perse		cifre 0 entrate a rimpiazzare le posizioni vuote

Ovviamente quest’operazione, a meno che non sia voluta, è altamente deleteria se le cifre perse sono differenti da zero in quanto queste ultime occupano le posizioni a maggior peso nella rappresentazione posizionale (MSD more significant digit). 
Relativamente allo shift a destra invece possiamo dire che, le cifre non nulle che si perdono, sono quelle con peso piccolo (LSD least significant digit). 
Nella rappresentazione in virgola mobile, nel momento in cui si esegue una somma, l’operazione di shift verso destra della mantissa del numero con esponente minore e la relativa modifica dell’esponente ad essa associata, equivalgono ad una sorta di troncamento e quindi ad una perdita di precisione, peraltro necessaria.