Algebre booleane e progetto logico dei calcolatori digitali/Sistemi di numerazione, aritmetica binaria
Struttura della memoria dal punto di vista operativo
[modifica | modifica sorgente]In un calcolatore digitale la memoria è l'organo capace di conservare dei dati e delle istruzioni codificati in un certo modo. Si pone così il problema di cercare qual è il supporto migliore per memorizzare un'informazione. Dato un dispositivo che può assumere b stati diversi, è possibile codificare un numero in una certa base associando a ogni stato una cifra del numero in questione.
Per esempio, si pensi di avere un dispositivo capace di assumere 10 stati diversi (S0, S1, S2... S9) e di associare a ognuno di essi una delle dieci cifre base del sistema decimale nel seguente modo:
Ora se si vuole codificare il numero 3541 abbiamo bisogno di quattro dispositivi (perché quattro sono le cifre del numero da codificare) che chiameremo D1,D2, D3 e D4, dove
- D4 assumerà lo stato corrispondente al numero delle unità
- D3 a quello delle decine
- D2 a quello delle centinaia
- D1 a quello delle migliaia.
Stato | S0 | S1 | S2 | S3 | S4 | S5 | S6 | S7 | S8 | S9 |
---|---|---|---|---|---|---|---|---|---|---|
D1 | 3 | |||||||||
D2 | 5 | |||||||||
D3 | 4 | |||||||||
D4 | 1 |
In definitiva per codificare un numero di n cifre in base b occorrono n dispositivi capaci di assumere b stati diversi, ed una volta costruito un tale sistema vi si possono codificare (beninteso non contemporaneamente) bn numeri.
Vediamo ora come si può arrivare a dire che la base 2 è la più conveniente nel senso che a parità di numero di informazioni da memorizzare è necessario il minor numero di stati.
Si è visto che per memorizzare un numero di n cifre in base b occorre un dispositivo che contiene b×n stati diversi e capace di memorizzare N=bn informazioni diverse; il problema si pone quindi:
Immaginando ora di far variare b e n con continuità si hanno le condizioni estremali:
dalle quali segue che lg b=1 cioè b=e che si può verificare è effettivamente un punto di minimo per la funzione b×n con la condizione di bn=cost.
Poiché 2<e<3 si potrebbe scegliere tanto il 2 quanto il 3 come base ma per motivi tecnici (ad esempio quelli riguardanti il vantaggio dei dispositivi bistabili) si è scelta la base 2.
Vediamo ciò con un esempio pratico: il numero 99910=1111011112 (il numero in basso sta a indicare la base, il passaggio dalla base 10 alla base 2 verrà trattato in seguito). Allora volendo costruire i dispositivi atti a rappresentarli avremo:
Disp. | S0 | S1 | S2 | S3 | S4 | S5 | S6 | S7 | S8 | S9 |
---|---|---|---|---|---|---|---|---|---|---|
D1 | 9 | |||||||||
D2 | 9 | |||||||||
D3 | 9 |
..... | D1 | D2 | D3 | D4 | D5 | D6 | D7 | D8 | D9 | D10 |
---|---|---|---|---|---|---|---|---|---|---|
S0 | 0 | |||||||||
S1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
È facile vedere che nel primo caso occorrono 30 stati diversi, mentre nel secondo solo 20, e inoltre nel primo si possono memorizzare 103=1000 informazioni mentre nel secondo 210=1024 informazioni.
Visto che la base 2 è migliore, vediamo come sono organizzati i dispositivi atti a memorizzare un numero in tale base.
Logicamente essi saranno in grado di assumere due stati diversi a cui diamo i valori: 1 o 0; + o -; vero o falso.
I dispositivi vengono raggruppati (fisicamente) in insiemi, l'insieme delle informazioni binarie in essi contenute viene chiamato voce.
A ogni insieme viene associato un numero (indirizzo) che ci permette di accedere alla voce. Per esempio se si ha bisogno di conservare da qualche parte una informazione si dà al computer l'istruzione di memorizzarla nella voce, per esempio, 001.
Sistemi di numerazione
[modifica | modifica sorgente]Per approfondire su Wikipedia, vedi la voce Sistemi di numerazione. |
La nozione di numero è una delle nozioni fondamentali dell'aritmetica e della matematica. Non tracceremo qui né la storia di questa nozione né descriveremo l'evoluzione che ha portato alle definizioni assiomatiche dei numeri. Constateremo solamente che in pratica i numeri ci risultano accessibili grazie a una rappresentazione che in generale è decimale, ma può anche essere di tipo differente (sessagesimale, romana...). Un metodo di rappresentazione costituisce quello che si chiama un sistema di numerazione. Il sistema più usato nella vita corrente è quello decimale.
Consideriamo il numero:
Questa notazione significa in pratica che N può considerarsi risultante dalla somma:
In altri termini, la scrittura ordinaria dei numeri è un modo di esprimerli in funzione delle cifre da 0 a 9 e delle potenze di 10.
Questa notazione ha le seguenti proprietà:
- la posizione di una cifra indica la potenza di cui essa è coefficiente nel calcolo della somma
- in assenza di una potenza nella somma si mette uno 0 nella posizione corrispondente
non è necessario scrivere gli eventuali zeri a sinistra dell'ultima cifra non nulla.
A causa di queste proprietà si ha l'abitudine di dire che la numerazione decimale è una numerazione di posizione.
Il numero 10, in funzione delle cui potenze si esprime il numero N, viene detto la base del sistema e sono necessari 10 simboli distinti 0, 1, 2, 3....9 per scrivere un numero.
L'utilizzazione della base 10 non è legata ad alcuna necessità logica o matematica ma probabilmente a considerazioni di tipo pratico; comunque si è fatto uso anche di altri sistemi di numerazione (base 12, 20, 60 in particolare). Si può allora generalizzare questa nozione di numerazione di posizione al modo seguente: dato un numero intero b>1, detto base del sistema del sistema di numerazione considerato, è b simboli distinti x0, x1.....x{b-1}, si fa la convenzione di scrivere un numero intero sotto la forma:
e questo per convenzione significa che il numero X può essere calcolato mediante la formula
Ogni simbolo xn...xk....x0 è uno fra i b simboli utilizzati per rappresentare i numeri da 0 a b-1.
Data la rappresentazione xnx{n-1}.....x0 la sommatoria fornisce X univocamente, e inversamente si può dimostrare che la rappresentazione xnx{n-1}....x0 di un intero è unica.
Nota 1:
- Per b=2 si ha un sistema di numerazione binario
- " b=8 ottale
- " b=10 decimale
- " b=12 dodecasimale
- " b=16 esadedcimale
- " b=60 sessagesimale
Nota 2: se si effettua la somma in un altro sistema di numerazione, il risultato sarà un numero X. Ad esempiosi può utilizzare un sisterma di posizione ma con una base b' diversa.
Sarà allora
Esempio: consideriamo il numero rappresentato in ottale da: X8= 3017.
Questo numero può essere rappresentato in decimale al modo seguente:
e quindi il numero che si scrive X8=3017 in ottale diventa X10=1551 in decimale.
Nota 3: l'indice k ha nome peso o rango: il peso più debole è 0, quello più forte è n.
Nota 4: è da notare la distinzione tra un numero e la sua rappresentazione; tale distinzione è importante e interviene nei problemi di conversione di un numero da un sistema di numerazione a un altro.
Le definizioni precedenti si riferiscono a numeri interi. In generale si avranno espressioni comprendenti una parte intera e una frazionaria che scriveremo:
espressione del numero
Come nel sistema decimale la virgola separa la parte intera da quella frazionaria.
Sistema di numerazione binario
[modifica | modifica sorgente]Numerazione binaria
[modifica | modifica sorgente]In questo sistema un numero è rappresentato, conformemente alla definizione generale da una successione di 1 e di 0:
cioè
in cui i simboli xi assumono i valori o 0 o 1 per ogni valore di i sono detti cifre binarie o digits.
Esempio:
Nota: con n cifre decimali è possibile rappresentare 10n numeri. Per rappresentare questi numeri nel sistema binario è necessario un numero di cifre binarie m tali che
cioè
- .
Addizione e sottrazione in binario. Complementazione
[modifica | modifica sorgente]Addizione: consideriamo due numeri
Si cerca S=X+Y. A tale scopo si procede come nel sistema decimale, partendo dal rango 0 e determinando rango per rango la somma S. Ad ogni rango i si determina:
- la somma modulo 2 di xi, yi e del riporto ri ottenuto dal rango precedente, ottenendo il digit si della somma S.
- il riporto r{i+1} da riportare sul rango i+1.
Queste due operazioni sono riassunte nella tabella 2.3.
Xi | Yi | ri | Xi+Yi+ri | Si | ri |
---|---|---|---|---|---|
0 | 0 | 0 | 0 | 0 | 0 |
0 | 0 | 1 | 1 | 1 | 0 |
0 | 1 | 0 | 1 | 1 | 0 |
0 | 1 | 1 | 10 | 0 | 1 |
1 | 0 | 0 | 1 | 1 | 0 |
1 | 0 | 1 | 10 | 0 | 1 |
1 | 1 | 0 | 10 | 0 | 1 |
1 | 1 | 1 | 11 | 1 | 1 |
Esempio:
Sottrazione. In modo analogo si ha la tabella 2.4, che fornisce per ogni rango, la sottrazione Si e il riporto r{i+1} per la sottrazione S=X-Y.
Xi | Yi | ri | Xi-(Yi+ri) | Si | ri |
---|---|---|---|---|---|
0 | 0 | 0 | 0 | 0 | 0 |
0 | 0 | 1 | -1=-2+1 | 1 | 1 |
0 | 1 | 0 | -1=-2+1 | 1 | 1 |
0 | 1 | 1 | -2 | 0 | 1 |
1 | 0 | 0 | 1 | 1 | 0 |
1 | 0 | 1 | 0 | 0 | 0 |
1 | 1 | 0 | 0 | 0 | 0 |
1 | 1 | 1 | -1=-2+1 | 1 | 1 |
Esempio:
In pratica però si utilizza il metodo dei complementi che riconduce il calcolo della sottrazione a quello di addizione.
Complementazione. Si definisce complemento vero di un numero intero binario 0<x<2n la quantità:
Esempio: sia il numero X=11001 di cinque cifre. Il suo complemento vero (detto anche complemento a due) sarà:
Si definisce invece complemento a 1 di un numero intero binario 0<X<2'n la quantità:
Esempio: sia X=11001. Il suo complemento a 1 sarà:
Nel sistema binario il complemento a 1 di un numero può essere ottenuto direttamente scambiando nella rappresentazione del numero stesso gli 1 con gli 0. Conoscendo il complemento a 1 di un numero binario si può ottenere il complemento vero sommando un 1:
Si può ora utilizzare la definizione di complemento e quella di classi residuo modulo m per costruire un algoritmo in grado di calcolare una sottrazione mediante un'operazione di somma.
Siano A e B due numeri tali che:
allora:
Si possono presentare due casi:
a) per A-B≥0 si ha:
b) per A-B ≤0 si ha:
Per distinguere tra i due casi è sufficiente esaminare la posizione n nella operazione A+C2n(B): infatti se A+C2n(B)≥2n nella n-esima posizione del risultato comparirà un 1 (caso a) e quindi il residuo modulo 2n fornisce la differenza stessa; se invece compare lo 0 l'operazione fornisce il valore complementato del valore assoluto del risultato (caso b).
Esempio:
Moltiplicazione e divisione in binario
[modifica | modifica sorgente]Moltiplicazione. Il metodo di base è quello che si usa anche in decimale: a seconda che la cifra del moltiplicatore valga 1 o 0 si aggiunge o no il moltiplicando alla somma parziale, scalando a ogni passo quest'ultima di un rango verso sinistra:
Divisione. Il metodo di base consiste nel sottrarre, come nel sistema decimale, il divisore moltiplicato per il solo fattore possibile e cioè 1.
I metodi esposti per le quattro operazioni costituiscono solo dei procedimenti a partire dai quali sono stati trovati molti accorgimenti per accrescerne la velocità di esecuzione da parte del calcolatore.
Sistemi con base 2p (p≥1)
[modifica | modifica sorgente]Per p=1 si ha il binario puro. Per p>1 si hanno dei sistemi (p=3 ottale, p=4 esadecimale) che vengono spesso utilizzati come notazioni abbreviate per il binario puro, sia per facilitare la lettura agli operatori, sia per certi calcoli. Le conversioni dalla base2 alla base 2p e viceversa si riconducono a dei semplici raggruppamenti di termini. Consideriamo dei numeri interri: pur di aggiungere il necessario numero di zeri a sinistra di un numero binario, si può sempre scrivere:
con
cioè raggruppando le cifre binarie a gruppi di p a partire da destra.
Segue che:
I gruppi Xi sono quindi in binario puro le rappresentazioni delle cifre di N nel sistema a base 2p.
Inversamente, dato un numero N in un sistema di base 2p, sarà sufficiente rappresentare ogni cifra in binario per avere il numero N in binario puro.
Esempio: codice ottale
Il codice ottale è quindi spesso utilizzato come notazione compatta del binario puro. Esso infatti, a causa della semplicità della procedura di conversione, permette di economizzare allora del tempo-macchina o di semplificare i dispositivi di conversione (caso di visualizzazione numerica a cifre luminose).
Conversioni da un sistema di numerazione a un altro
[modifica | modifica sorgente]Primo metodo
[modifica | modifica sorgente]Numeri interi. Consideriamo un numero N; lo si può scrivere mediante due basi b1 e b2 ottenendo per N due espressioni che chiameremo Nb1 e Nb2. Si avrà allora:
con le relazioni:
Il problema della conversione è il seguente: data l'espressione Nb1 nel sistema di base b1 trovare l'espressione Nb2 dello stesso numero N nel sistema di base b2, o viceversa. A tale fine osserviamo che y0 è il resto della divisione di N per la base b2.
Infatti:
quindi:
cioè
Possiamo fare le stesse considerazioni nel numero N1 e quindi y1 sarà il resto della divisione di N1 per b2 e così via.
Si vede quindi che si ottengono le cifre successive di N2 considerando i resti successivi così ottenuti:
in cui y0, y1...ym rappresentano i resti delle divisioni successive.
Esempio: convertire N10=3412 in base 8.
Si cercano allora i resti successivi delle divisioni per 8. Si ottiene:
e quindi
Notiamo che il metodo di conversione tra due basi b1 e b2 sopra esposto è in teoria applicabile nei due sensi (b1→b2 e b2→b1). In pratica volendo passare dalla base b1 alla base b2, è necessario eseguire le operazioni di divisione nella base b1. Quindi quando i calcoli sono fatti a mano non si ricorrerà a questo metodo che per convertire un numero decimale in un'altra base, come nell'esempio visto. Lo stesso discorso non vale nel caso in cui l'operazione di conversione sia meccanizzata mediante un sistema automatico.
Numeri frazionari inferiori all'unità. Consideriamo, analogamente al caso precedente, in numero N in una rappresentazione Nb1 in un sistema di base b1; e cerchiamo la rappresentazione Nb2 in un sistema di base b2. Notiamo che l'espressione:
significa:
- .
Moltiplicando N per b2 si ha:
Cioè la cifra che in (N×b2) appare a sinistra della virgola è la prima cifra cercata: y-1. Possiamo ora considerare il numero ottenuto conservando solo le cifre a destra della virgola ed applicare lo stesso procedimento: cioè lo si moltiplica per b2 e la cifra che risulta a sinistra della virgola sarà y-2, ecc.
Il procedimento considerato può anche non avere termine, e quindi la rappresentazione di un numero frazionario può avere termine in un sistema di numerazione e non averlo in un altro.
Come per la conversione di numeri interi, si può notare che il metodo qui visto per i numeri frazionari comporta delle moltiplicazioni nel sistema di partenza a base b1. Quindi, per i calcoli a mano, questo metodo si utilizza solamente per le conversioni a partire dal sistema decimale verso una generica base b.
Esempio: Convertire N10=0,71875 in base 2.
e quindi N2=0,101110 ha termine dopo la 5a cifra.
Numeri con parte intera e parte frazionaria. Si procede in due tempi: si applica il metodo (a) alla parte intera e il metodo (b) alla parte frazionaria. Il numero cercato si ottiene mediante unione dei due risultati.
Secondo metodo
[modifica | modifica sorgente]Dato un numero avente la rappresentazione:
si esprimono le cifre xn, x{n-1},...,x0, x{-1} nel sistemadi numerazione b2 e così anche per le potenze di b1: b1n b1(n-1)... b1,b1(-1) e si effettua la somma seguente nel sistema di base b2:
- .
In questo caso notiamo che il passaggio dalla base b1 alla base b2 implica che la somma (c) sia effettuata nel sistema di base b2, e quindi questo metodo è quello usato quando è necessario convertire un numero da una base generica a quella decimale nei calcoli fatti a mano.
Esempio: convertire N2=11011,101 in base 10.
I metodi di conversione esposti si prestano a numerose varianti: i parametri da prendere in considerazione dal punto di vista tecnico consistono essenzialmente nella rapidità di conversione e nella complessità dei dispositivi, in contrasto fra loro.