Cos'è ElectroYou | Login Iscriviti

ElectroYou - la comunità dei professionisti del mondo elettrico

7
voti

LogicBignami (XII)

Indice

I sistemi di numerazione (parte quarta)

Riprendiamo il discorso interrotto in LogicBignami XI sull'esecuzione delle operazioni matematiche principali nel sistema numerico binario, analizzando anche il concetto di overflow.

Overflow

L'overflow (o traboccamento) si presenta quando, in una macchina di calcolo, a seguito di un'operazione, si supera il massimo numero manipolabile della macchina stessa.

Supponiamo di avere un dispositivo che manipoli numeri binari naturali a 4 \; bit, e supponiamo di voler eseguire la somma tra i numeri 1111_{(2)} = 15_{(10)} \; e 1_{(2)} = 1_{(10)} \;:

Il risultato, considerando anche l'ultimo riporto (indicato in blu), è giustamente pari a 10000_{(2)} = 16_{(10)} \; c'è però un problema: abbiamo detto che il nostro circuito può manipolare solo 4 \; bit, quindi potrà "vedere" soltanto i primi 4 \; bit del risultato (0000_{(2)}) \; e, per tanto, otterremo un risultato errato.

Il bit risultante da un'operazione, che ha "peso" 2^n \;, dove n \; sono i bit che compongono il numero binario manipolabile dal circuito, viene chiamato overflow (o traboccamento).

Questo, in genere, rappresenta un segnale di errore in quanto ci avvisa che il risultato dell'operazione eseguita ha superato, in valore assoluto, il massimo numero rappresentabile con i bit a nostra disposizione: infatti nella somma precedente, con 4 \; bit a disposizione potevamo rappresentare solo un valore massimo pari a 2^4 - 1 = 15_{(10)} = 1111_{(2)} \;(vedi LogicBignami IX).

Lo stesso ragionamento si applica ai numeri binari positivi, qualunque sia il sistema utilizzato per rappresentare i numeri binari con segno: infatti ricordiamo che la parte che rappresenta il valore assoluto del numero binario, ossia il numero binario ottenuto escludendo il bit rappresentante il segno positivo, equivale alla rappresentazione effettuata tramite un numero binario naturale (vedi LogicBignami XI).

Quindi, un overflow sulla somma dei MSB di due numeri binari positivi, indica sempre un errore nel risultato.

Da notare, poi, che l'overflow sul MSB determina anche il cambiamento del bit segno (*) nel risultato della somma, ulteriore indicazione di errore nell'avvenuta operazione:

ad esempio, se sommiamo 0101_{(2)} = 5_{(10)} \; a 0111_{(2)} = 7_{(10)} \; otteniamo

In pratica dalla somma di due numeri binari positivi abbiamo ottenuto un numero binario negativo (1100_{(2)}) \; indicativo, oltre alla presenza dell'overflow, dell'errore generatosi nell'operazione eseguita.

(*) Nota: per i numeri binari espressi in modulo e segno il bit di segno non rientra nell'operazione di somma, per cui si considera solamente la presenza dell'overflow sulla somma dei MSB, come verrà ribadito anche più avanti.

Quando, invece, si tratta di sommare dei numeri binari di segno opposto o entrambi negativi, possono presentarsi due tipologie di overflow:

- quello appena enunciato che si presenta nella somma dei rispettivi MSB
- oppure quello che si può generare dalla somma dei bit di segno

come si può vedere rappresentato nella figura seguente.

Inoltre gli overflow che si possono generare nella somma di numeri binari di segno opposto o entrambi negativi, non sempre rappresentano un indicatore di risultato errato in quanto possono essere funzionali della tipologia di rappresentazione utilizzata per i numeri binari negativi: basta ricordare, ad esempio, la tecnica dell' end-around -carry che abbiamo visto applicata nelle operazioni di somma effettuate con numeri binari negativi rappresentati in complemento a 1 (LogicBignami XI).

Nota:
Quando eseguiamo la somma algebrica di due numeri di segno opposto, il risultato sarà sempre compreso tra questi due numeri quindi, segnatamente al sistema numerico binario, non sarà mai possibile superare il limite di valore esprimibile con i bit utilizzati.

Vediamo allora di analizzare, per le diverse rappresentazioni dei numeri binari negativi, quando un overflow è da considerare un errore e quando parte dell'operazione stessa.

1) Numeri binari in modulo e segno

Come abbiamo detto nell'articolo precedente, questa rappresentazione dei numeri binari con segno non permette di eseguire una somma algebrica eseguendo semplicemente una somma bit per bit dei due numeri, segno compreso, ma si deve procedere ad analizzare i segni dei due numeri, per decidere se eseguire una somma (segni concordi) o una differenza (segni discordi).

Quindi, in caso di somma, l'eventuale comparsa di overflow sarà dovuto alla somma dei due MSB dei relativi moduli e rappresenterà un errore per superamento del valore limite rappresentabile dal numero di bit utilizzati.

Esempio, se vogliamo sommare i numeri binari 1101_{(2)} = -5_{(10)} \; e 1011_{(2)} = -3_{(10)} \; procediamo:

- separiamo i bit di segno, sono entrambi settati a 1 \;, quindi sono concordi (entrambi negativi) pertanto possiamo procedere con la somma dei moduli

Come ci aspettavamo, abbiamo ottenuto un overflow dalla somma dei MSB dei moduli, infatti il risultato è errato in quanto la somma [-5 + (-3) = -8]_{(10)} \; supera il massimo valore rappresentabile dai 3 \; bit del modulo.

Da notare che i bit di segno non rientrano nella somma in quanto devono essere elaborati a parte da un apposito circuito.

2) Numeri binari in complemento a 1

Abbiamo visto che nella somma algebrica con numeri binari negativi rappresentati in complemento a 1, in presenza di un overflow sul bit di segno, lo si somma ulteriormente al risultato ottenuto per ottenere il valore finale dell'operazione, nella tecnica denominata end-around carry), ma si devono fare dei distinguo.

Se eseguiamo anche qui la somma algebrica tra 1100_{(2)} = -3_{(10)} \; e 1010_{(2)} = -5_{(10)} \;, il cui risultato sappiamo già ricadere al di fuori del massimo rappresentabile con un numero binario in complemento a 1 di 4 \; bit (1000_{(2)} = -7_{(10)}) \;, otteniamo:

Come si vede abbiamo si, un overflow sul bit di segno, ma anche se attuiamo la tecnica dell' end-around carry otteniamo un risultato finale di 0111_{(2)} = 7_{(10)} \;: errato sia per valore che per segno.

Se invece eseguiamo la somma algebrica tra 1011_{(2)} = -4_{(10)} \; e 1100_{(2)} = -3_{(10)} \; otteniamo

Anche in questo caso abbiamo un overflow sul bit di segno, ma la tecnica dell' end-around carry, questa volta, ci porta al risultato corretto 1000_{(2)} = -7_{(10)} \;.

Per discriminare quando l'overflow sul bit di segno segnala un errore, cioè il superamento del valore limite rappresentabile dal numero binario composto dai bit manipolabili dal nostro circuito, si deve analizzare se, nell'operazione eseguita, è stato generato anche un overflow sulla somma dei due MSB.

Come si può notare, la prima operazione la somma algebrica non aveva portato a nessun overflow sulla somma dei due MSB, nell'applicazione, però, della tecnica dell' end-around carry viene generato un riporto sul MSB, cioè un overflow.

Da notare che il riporto sul MSB si può presentare anche prima dell'applicazione della tecnica dell' end-around carry, infatti se sommiamo algebricamente i numeri 1101_{(2)} = -2_{(10)} \; e 1100_{(2)} = -3_{(10)} \; otteniamo

Come si vede abbiamo sia l'overflow bit di segno che sul MSB, generato, questa volta, direttamente dalla somma algebrica dei due numeri di partenza, e il risultato è, ovviamente, corretto: 1010_{(2)} = -5_{(10)} \;.

Da notare, invece, che l'eventuale generazione di overflow nella somma algebrica tra un numero binario positivo e uno negativo non è mai indice di errore in quanto il risultato non può mai ricadere al di fuori dei valori limite imposto dal numero di bit utilizzati.

In definitiva, l'unico controllo per determinare se la generazione di un overflow sul bit di segno sia da considerare un errore o meno, è da eseguire solo nella somma algebrica tra numeri binari negativi:

- se l'operazione genera solo un overflow sul bit di segno, allora il risultato è errato per superamento del valore rappresentabile con il numero di bit utilizzati.
- se l'operazione genera un overflow sul bit di segno e un overflow sulla somma dei singoli MSB, o sull'MSB nell'applicazione della tecnica di end-around carry, allora il risultato dell'operazione è corretto.

3) Numeri binari in complemento a 2

Anche con questa rappresentazione dei numeri negativi si può fare un discorso analogo a quello fatto in precedenza: l'overflow che, eventualmente, si genera sul bit di segno non sempre è indicativo di un errore nel risultato ottenuto nella somma algebrica di due numeri binari.
Infatti, nella somma algebrica tra numeri binari rappresentati in complemento a 2

- la presenza solo di un overflow sul bit di segno, indica che il risultato è errato per superamento del valore rappresentabile con il numero di bit utilizzati.
- la presenza di un overflow sul bit di segno e un overflow sulla somma dei singoli MSB, indica che il risultato dell'operazione è corretto.

Da notare che con questo metodo di rappresentazione dei numeri binari negativi, l'oveflow sul bit di segno non fa parte del risultato, ma va considerato esclusivamente come eventuale segnalazione di errore.

Facciamo alcuni esempi:

Nel primo, somma di numeri binari di segno opposto, come già detto non è possibile superare il limite di valori esprimibile con il numero di bit manipolabili ed infatti, come segnalazione di risultato coerente, sono presenti sia l'overflow sul bit di segno che l'overflow sulla somma dei MSB.

Nel secondo abbiamo una somma di numeri binari negativi con risultato entro i limiti di valori consentiti: anche in questo caso la correttezza dell'operazione è rappresentata dalla presenza di entrambi gli overflow.

Nell'ultimo caso abbiamo ancora la somma di numeri binari negativi ma, questa volta, il risultato cade al di fuori dei limiti di valore consentiti con 3 \; bit [-3 + (-6) = -9]_{(10)} \;: come possiamo vedere l'errore è segnalato dalla presenza del solo overflow sul bit di segno (oltre al fatto di aver ottenuto un risultato positivo).

4) Numeri Eccesso-N

Come già spiegato nell'articolo precedente, i numeri binari rappresentati in Eccesso-N nelle operazioni di somma possono essere trattati in due modi:

- se utilizzati direttamente, si ricade nelle stesse regole citate per i numeri binari rappresentati in modulo e segno.
- se, invece, viene invertito lo "stato" del bit di segno, questi, in pratica, diventano dei numeri binari in complemento a 2 e così possono essere utilizzati.

In entrambi i casi si rimanda agli specifici paragrafi per il trattamento degli eventuali overflow.

Moltiplicazione nel sistema numerico binario

L'operazione di moltiplicazione nel sistema numerico binario può essere eseguita in diversi modi, comunque, qualunque sia il metodo scelto, il prodotto tra due bit, b_A \; e b_B \;, appartenenti a due numeri binari A_{(2)} \; e B_{(2)} \;, viene determinato seguendo la sotto riportata tabella della verità:

bA
bB
b_A \cdot b_B
0
0
0
0
1
0
1
0
0
1
1
1



Moltiplicazione tra numeri binari naturali

Questo è il caso più semplice e il suo procedimento rispecchia quello classico che tutti conosciamo, utilizzato nel sistema numerico decimale quando si esegue la moltiplicazione tra due numeri composti da più cifre.

Supponendo di voler moltiplicare tra loro due numeri binari A_{(2)} \; e B_{(2)} \; entrambi a 3 \; bit, otterremmo la seguente "forma" classica:


In pratica, come infatti avviene nel sistema numerico decimale, otterremo una matrice di prodotti parziali i quali poi verranno sommati per colonne al fine di ottenere il risultato finale dell'operazione di moltiplicazione.

Ogni prodotto parziale è composto da un numero binario con tanti bit quanti sono quelli del moltiplicando: si ottiene moltiplicando ciascun bit del moltiplicatore, a partire dal LSB, per ogni bit del moltiplicando.

Quindi, nell'esempio sopra riportato, noi avremo:

Prodotti parziali:

PP0_{(2)} = b_{PP02}\;b_{PP01}\;b_{PP00} = [b_{B0} \cdot b_{A2}][b_{B0} \cdot b_{A1}][b_{B0} \cdot b_{A0}]
PP1_{(2)} = b_{PP12}\;b_{PP11}\;b_{PP10} = [b_{B1} \cdot b_{A2}][b_{B1} \cdot b_{A1}][b_{B1} \cdot b_{A0}]
PP2_{(2)} = b_{PP22}\;b_{PP21}\;b_{PP20} = [b_{B2} \cdot b_{A2}][b_{B2} \cdot b_{A1}][b_{B2} \cdot b_{A0}]

Da notare che il prodotto parziale PP1_{(2)} \; va incolonnato sotto al prodotto parziale PP0_{(2)} \;, spostato a sinistra di una posizione pari ad un bit, e così anche per il prodotto parziale PP2_{(2)} \; rispetto a PP1_{(2)} \;.

Il valore finale del prodotto, sarà pari a

P_{(2)} = b_{P5}\;b_{P4}\;b_{P3}\;b_{P2}\;b_{P1}\;b_{P0}

dove ogni bit b_{(Pn)} \; equivale alla somma della colonna di bit corrispondenti nella matrice dei prodotti parziali, così

b_{P0} = b_{PP00} \;
b_{P1} = b_{PP01} + b_{PP10} \;
b_{P2} = b_{PP02} + b_{PP12} + b_{PP20} \;
\cdots \;

e così via.

Il bit b_{P5} \;, evidenziato in grigio, potrebbe non esistere (ossia essere pari a 0 \; che, in un numero binario naturale può essere omesso) in quanto, di fatto, si tratta dell'eventuale overflow derivante dalla somma tra il bit b_{PP22} \; e un possibile riporto della somma generatrice di b_{P3} \; .

Escludendo quando il moltiplicatore è pari a 1_{(2)} = 1_{(10)} \;, in cui il risultato della moltiplicazione ha lo stesso numero di bit del moltiplicando, la moltiplicazione tra due numeri binari A_{(2)} \; e B_{(2)} \; rispettivamente di lunghezza pari a n \; e m \; bit, genera un risultato con un numero di bit che, al massimo, sarà pari a n + m \;.

Facciamo adesso un esempio pratico:

Moltiplichiamo i numeri binari naturali 101_{(2)} = 5_{(10)} \; e 111_{(2)} = 7_{(10)} \;.

Per quanto detto in precedenza, essendo entrambi i numeri binari, da 3 \; bit, il risultato potrà essere, al massimo, di 6 \; bit.

Ovviamente ci aspettiamo di ottenre, come risultato, 35_{(10)} = 100011_{(2)} \;.

Come possiamo notare il risultato è, come logico, quello che avevamo previsto.


Moltiplicazione tra numeri binari con segno

Se, invece, volgiamo eseguire il prodotto tra due numeri binari con segno, dobbiamo procedere in una maniera leggermante differente.

Innanzi tutto si utilizza la codifica dei numeri binari negativi, in complemento a 2 (vedi LogicBignami XI), poi, nella costruzione della matrice dei prodotti parziali si devono porre in evidenza quei bit, nei singoli prodotti, che derivano dal prodotto con il bit di segno negativo: questi vengono, convenzionalmente, indicati come bit negativi.

Da notare che se moltiplicando e moltiplicatore sono entrambi negativi, il prodotto tra i due bit di segno negativi, genera un bit positivo.

Ad esempio, se moltiplichiamo i due numeri binari negativi 1001_{(2)} = -7_{(10)} \; e 1110_{(2)} = -2_{(10)} \; otteniamo la seguente matrice dei prodotti parziali in cui abbiamo evidenziato con la scrittura ^-1 \; i, cosiddetti, bit negativi.


A questo punto la matrice dei prodotti parziali così ottenuta si deve suddividere in due sottomatrici:

- una contenete solo prodotti parziali con bit non marcati come negativi: la posizione occupata dai bit negativi verrà settata a 0 \;

- l'altra contenete solo prodotti parziali bit marcati come negativi: in questo caso la posizione occupata dai bit non negativi verrà settata a 0 \;)

In tutte e due le suddette sottomatrici, i bit settati a 0 \; nella matrice dei prodotti parziali rimangono invariati.

Si eseguono, poi, le somme separate delle colonne di bit delle due sottomatrici.

Quindi, proseguendo con l'esempio precedente, avremo le seguenti sottomatrici con le relative somme:

Si fa notare che:

1) nella sottomatrice dei prodotti parziali relativa ai bit positivi, in grassetto, sono evidenziati i settaggi a 0 \; dei bit indicati come ^-1 \;
3) viceversa, nella sottomatrice dei prodotti parziali relativa ai bit negativi, in grassetto, sono evidenziati i settaggi a 0 \; dei bit settati, semplicemente, a 1 \;.

Dalle due sottomatrici risultano le seguenti somme:

- somma sottomatrice prodotti parziali bit positivi 1000110_{(2)} \;
- somma sottomatrice prodotti parziali bit negativi 0111000_{(2)} \;

A questi due numeri binari va aggiunto, a sinistra del MSB, un ulteriore bit settato a 0 \; in quanto si devono considerare numeri binari positivi, quindi:

- somma sottomatrice prodotti parziali bit positivi 01000110_{(2)} = 70_{(10)} \;
- somma sottomatrice prodotti parziali bit negativi 00111000_{(2)} = 56_{(10)} \;

Il risultato finale della moltiplicazione si ottiene eseguendo la differenza tra il numero binario generato dalla somma della sottomatrice dei prodotti parziali dei bit positivi e quella dei bit negativi, ovvero facendo la somma algebrica tra la somma della sottomatrice dei prodotti parziali dei bit positivi e il complemento a 2 di quella dei bit negativi.

Quindi, procedendo nella complementazione della somma della sottomatrice dei prodotti parziali dei bit negativi ed eseguendo la summenzionata somma algebrica, otteniamo il risultato finale del nostro esempio:


Come si vede il risultato dell'operazione genera un overflow sul MSB, e uno sul bit di segno, quindi quest'ultimo, per quanto spiegato nel paragrafo precedente, non rappresenta un indicativo di errore.

Di fatti il risultato ottenuto 00001110(2) = 14(10) è corretto: da notare, come avevamo detto in precedenza, che il risultato è un numero binario di 8 \; bit in quanto i numeri binari moltiplicati erano, ognuno, di 4 \; bit.

Vediamo adesso un esempio di moltiplicazione tra un numero binario negativo e uno positivo (non starò a ripetere la spiegazione di tutti i passaggi):

moltiplichiamo tra loro i numeri binari con segno 1101_{(2)} = -3_{(10)} \; e 0111_{(2)} = 7_{(10)} \;

Come si può notare il procedimento è identico e, alla fine, otteniamo il risultato 11101011(2) = − 21(10) come ci aspettavamo.

La moltiplicazione di due numeri binari positivi si esegue come si è visto nella moltiplicazione tra numeri binari naturali


Moltiplicazione per somme successive

Si basa sulla definizione stessa di moltiplicazione come somma di numeri uguali:

infatti, dati due numeri positivi, A \; e B \;

abbiamo che

A \cdot B = \sum _{k=1}^B{A} \;

In pratica questo sistema può essere utilizzato anche con numeri negativi solo che, in tale caso va considerato, nella sommatoria, il valore assoluto del moltiplicando, e il segno da attribuire al risultato finale viene ricavato secondo le classiche regole del segno rammentate di seguito:

(+) \cdot (+) = (+)
(+) \cdot (-) = (-)
(-) \cdot (+) = (-)
(-) \cdot (-) = (+)

Quindi, in definitiva, trattando la moltiplicazione tra numeri binari con segno, il bit di segno da associare al risultato dipenderà dalla seguente tabella della verità:

b_{s_A}
b_{s_B}
b_{s_{risultato}}
0
0
0
0
1
1
1
0
1
1
1
0

Inoltre, se il moltiplicando è un numero binario negativo, si dovrà utilizzare, nell'esecuzione delle somme successive, il suo valore assoluto, ossia il suo complemento a 2 e lo stesso discorso vale per il moltiplicatore che, rappresentando l'indice della sommatoria, quindi il numero di addendi della nostra somma, va sempre considerato in valore assoluto (oltre che al suo corrispondente valore in decimale).

In pratica il procedimento per la moltiplicazione per somme successive, nel sistema numerico binario, si può riassumere dal seguente schema:


dove

A_{(2)} \; è il numero binario che rappresenta il moltiplicando

B_{(2)} \; è il numero binario che rappresenta il moltiplicatore

|B_{(10)}| \; è il corrispondente valore assoluto in decimale del numero binario B_{(2)} \; e rappresenta il numero di addendi della nostra sommatoria.

Vediamo allora un esempio di applicazione eseguendo la moltiplicazione tra i numeri binari con segno 1011_{(2)} = -5_{(10)} \; e 0011_{(2)} = 3_{(10)} \;, considerando moltiplicando il primo.

Iniziamo analizzando i bit di segno: uno è settato a 1 \; (numero binario negativo) e l'altro a 0 \; (numero binario positivo) quindi il bit del risultato dovrà essere settato a 1 \; in quanto dovrà essere un numero binario negativo, pertanto il risultato della sommatoria dovrà essere complementato a 2.

Essendo il moltiplicando un numero binario negativo, lo dovremo rendere positivo prima dell'esecuzione della sommatoria, eseguendone la complementazione a 2:

1011_{(2)} \rightarrow complemento\;a\;2\; \rightarrow 0101_{(2)}

Dal moltiplicatore ricaviamo il valore assoluto in decimale per conoscere il numero di addendi della nostra sommatoria:

| 0011(2) | = 3(10)

Formiamo quindi una somma di tanti 3 \; addendi, composti dal numero binario 0101_{(2)} \;, ed eseguiamo l'operazione:

Nota: Abbiamo già detto che il risultato di una moltiplicazione tra numeri binari può richiedere un numero di bit pari alla somma dei bit di moltiplicando e moltiplicatore, per questo motivo, prima di eseguire la sommatoria, conviene espandere i singoli addendi a tale numero di bit, aggiungendo, a destra del bit di segno, tanti bit settati a 0 \; fino al raggiungimento del summenzionato numero.

Nel nostro esempio, essendo i due numeri binari da 4 \; bit, il risultato potrebbe richiedere 8 \; bit, per questo sono stati aggiunti 4 \; bit settati a 0 \; a destra del bit di segno (evidenziati in amaranto).

Quindi il risultato delle somme successive è pari a 00001111_{(2)} \;, che può essere ridotto a 01111_{(2)} \; dal momento che l'eliminazione di una sequenza di bit settati a 0 \; a destra del bit di segno, fino al primo bit settato a 1 \;, non comporta nessuna variazione del valore assunto.

All'inizio abbiamo pero detto che, essendosi evidenziato che il bit di segno deve essere settato a 1 \; (il risultato deve essere un numero binario negativo), il risultato della sommatoria deve essere complementato a 2, quindi eseguiamo tale operazione per ottenere il risultato finale:

01111_{(2)} = 15_{(10)} \rightarrow complemento\;a\;2\; \rightarrow 10001_{(2)} = -15_{(10)}

come ci aspettavamo.

Moltiplicazione tra numeri binari frazionari (in virgola fissa)

Fino ad ora abbiamo visto la moltiplicazione tra numeri binari interi, per quelli frazionari (a virgola fissa), è possibile utilizzare solo i primi due metodi visti, in quanto il metodo delle somme successive permette di avere solo il moltiplicando frazionario, il moltiplicatore, come indice del numero di addendi di cui deve essere composta la somma, deve essere un numero intero.

Come avviene nella moltiplicazione di numeri frazionari nel sistema numerico decimale, anche in quello binario, nel risultato si contano, come parte frazionaria, tanti bit, quanto la somma dei bit frazionari di moltiplicando e moltiplicatore.

Esempio, moltiplichiamo tra loro i numeri binari 010,11_{(2)} = 2,75_{(10)} \; e 111,11(2) = − 0,25(10)

Il risultato, come si vede, è, come ci si aspettava, pari a 11111,0101_{(2)} = -0,6875_{(10)} \;.

A differenza dei numeri binari positivi, in quelli negativi espressi in complemento a 2, una sequenza di bit settati a 1 \; a destra del bit di segno può essere eliminata fino al penultimo bit settato a 1 \;, così il risultato 11111,0101_{(2)} \; può essere ridotto a 11,0101_{(2)} \;.

Da notare che, come è stato detto, nel risultato il numero dei bit della parte frazionaria corrisponde alla somma del numero dei bit della parte frazionaria di moltiplicando e moltiplicatore.

Moltiplicazioni con moltiplicatore pari a 2n

Nel caso in cui il moltiplicatore equivalga a 2n, quindi 10_{(2)} = 2^1_{(10)} \;, 100_{(2)} = 2^2_{(10)} \;, 1000_{(2)} = 2^3_{(10)} \;, ecc..., il riusltato della moltiplicazione equivale al moltiplicando a cui vengono semplicemente aggiunti n \; bit settati a 0 \; a destra del LSB, semplificando di molto il processo di moltiplicazione.

In questo frangente si dice che il risultato equivale al numero di partenza spostato (shiftato) a sinistra di n \; posizioni: questo concetto verrà ripreso in seguito quando verranno trattati i registri a scorrimento o shift register.

Infatti se eseguiamo la moltiplicazione tra 0101_{(2)} = 5_{(10)} \; e 0100_{(2)} = 2^2_{(10)} \;, otteniamo:

Come si vede il risultato equivale al numero binario di partenza a cui sono stati aggiunti 2 \; bit settati a 0 \; (evidenziati in amaranto): in pratica è come se il numero 0101_{(10)} \; si sia spostato (shiftato) a sinistra di 2 \; posizioni.

Divisione nel sistema numerico binario

Per quanto riguarda la divisione nel sistema numerico binario, questa si esegue considerando i numeri in valore assoluto, recuperando il valore da attribuire al bit di segno del risultato dall'analisi dei valori assunti dai bit di segno di dividendo e divisore nel rispetto dell regole viste nel paragrafo precedente, dove cambia solo il tipo di operazione eseguita, quindi:

(+) \div (+) = (+)
(+) \div (-) = (-)
(-) \div (+) = (-)
(-) \div (-) = (+)

Da cui si ricava la seguente tabella della verità:

b_{s_A}
b_{s_B}
b_{s_{risultato}}
0
0
0
0
1
1
1
0
1
1
1
0

dove

b_{(s_A)} \; equivale al bit di segno del numero binario A_{(2)} \;

b_{(s_B)} \; equivale al bit di segno del numero binario B_{(2)} \;

b_{s_{risultato}} \; equivale al bit di segno del quoziente tra A_{(2)} \; e B_{(2)} \;

In definitiva, se nell'operazione da eseguire, dividendo e/o divisore sono numeri binari negativi, questi dovranno essere trasformati in numeri binari positivi prima di effettuare la divisione.

Nota

Per quanto concerne l'operazione di divisione, si intenderà sempre soddisfatta la relazione

divisore \ne 0

Fatta questa premessa, analizziamo i principali metodi per eseguire l'operazione di divisone nel sistema numerico binario.

Metodo c.d. "in colonna"

Questo è il classico metodo, usato nel sistema numerico decimale soprattutto quando si tratta di eseguire operazioni di divisione in qui il divisore è composto da più cifre.

Dando per scontato che questo sistema sia conosciuto da tutti, inserisco semplicemente una figura che ne rappresenti il procedimento.

La grossa differenza nel sistema numerico binario sta nel fatto che i valori che possono assumere i singoli bit del quoto sono, ovviamente, solo 1 \; e 0 \;, quindi il valore che potrà assumere il sottraendo nelle sequenze di sottrazioni potrà essere o nullo o il divisore stesso.

Quindi il settaggio di un bit del quoto dipenderà dal rapporto di grandezza tra minuendo e divisore in ogni singola sottrazione:

- se minuendo < \; divisore, ovvero se minuendo - \; divisore < 0 \;, allora il corrispondente bit del quoto sarà settato a 0 \;
-

- viceversa, se minuendo \ge \; divisore, ovvero se minuendo - \; divisore \ge 0 \;, allora il corrispondente bit del quoto sarà settato a 1 \;

Vediamo quindi di spiegarne il procedimento servendoci di un esempio:

Supponiamo di voler dividere i numeri binari naturali 110010101_{(2)} = 405_{(10)} \; e 111_{(2)} = 7_{(10)} \;.

Nell'esempio sopra riportato ho indicato come:

- M[n] \; il numero binario che rappresenta il minuendo delle varie sottrazioni

- D[m] \; il numero binario che rappresenta il risultato differenza delle varie sottrazioni
- Di \; il numero binario che rappresenta il divisore

- Dv \; il numero binario che rappresenta il dividendo

Il procedimento è il seguente:

1- All'inizio si confronta Di \; con un numero binario, formato dallo stesso numero di bit di Di \;, composto a partire dal MSB di Dv \; scorrendo verso destra.
Nel nostro esempio questo numero binario, indicato come m1 \; all'interno del rettangolo grigio chiaro in Dv \;, corrisponde a 110_{(2)} = 6_{(10)} \;: confrontandolo con Di \; risulta
m1 < di \;
per tanto non è possibile eseguire una sottrazione m1 - Di \ge 0\;.


Nota

Ogni volta che non è possibile eseguire una sottrazione con risultato nullo o positivo, ossia ogni volta che M[n] < Di \; si aggiunge, da destra verso sinistra, a partire dall'ultimo inserito, un bit settato a 0 nel quoto.

Nel caso dell'impossibilità di eseguire la prima sottrazione a pari numero di bit, come poco sopra indicato, il primo bit settato a 0 \; del quoto può essere omesso (in grigio chiaro nell'esempio).


2- Se, con un numero binario di pari bit, non è possibile eseguire la sottrazione con Di \;, ci si sposta a destra, in Dv \;, di un ulteriore bit , in modo da formare un numero binario M1 \; composto da un bit in più rispetto a Di \;.
Nell'esempio
M1 = 1100_{(2)} = 12_{(2)} \;, quindi abbiamo
M1 > Di \; per cui possiamo eseguire la differenza tra i due
M1 - Di = (1100 - 111)_{(2)} = 101_{(2)} = 5_{(10)} \;, il cui risultato verrà denominato D1 \;.
(in figura sono stati evidenziati in blu i bit in prestito e in verde il valore assunto dal corrispondente bit in seguito al prestito effettuato)
Inoltre, essendo M1 > Di \;, verrà settato a 1 \; il MSB(*) del quoto
(*) Un eventuale bit settato a 0 \; all'estrema sinistra di un numero binario naturale sappiamo che può essere eliminato in quanto non significativo.


3- Ottenuto D1 \; si aggiunge, a destra del suo LSB, il primo bit, proseguendo sempre a destra, in Dv \;, non utilizzato per formare il numero binario M1 \;:
essendo M1 \; composto dai primi 4 \; bit, MSB compreso, di Dv \;, il bit che aggiungeremo sarà 5^{\underline \circ} \; partendo dal MSB (che nell'esempio corrisponde al bit di peso 4 \;).
4- Formato il nuovo numero binario M2 \; questo andrà nuovamente confrontato con Di \; per stabilire se sia possibile eseguire l'operazione di sottrazione tra i due:
Come si vede, nell'esempio
M2 = 1011_{(2)} = 11_{(10)} \;, per cui
M2 > Di \; e, di conseguenza ricaviamo,
D2 = M2 - Di = (1011 - 111)_{(2)} = 1_{(2)} = 1_{(10)} \;
Anche in questo caso, essendo M2 > Di \;, verrà settato a 1\; il bit del quoto immediatamente alla destra dell'ultimo immesso.


5- I due ultimi passaggi (3 e 4) si ripeteranno fino a quando si sarà aggregato l'ultimo bit di Dv (che corrisponderà al suo LSB) al LSB dell'ultima differenza eseguita.


6- Quando la summenzionata operazione di aggregazione non genera un numero M[n] \ge Di \;, rendendo impossibile l'esecuzione dell'operazione di sottrazione, come già detto si dovrà settare il corrispondente bit del quoto a 0\;, inoltre, si continuerà ad aggregare ulteriori bit di Dv \; fino a raggiungere le condizioni necessarie al prosieguo delle sottrazioni tra M[n] \; e Di \;.
Nota: Ad ogni aggiunta di bit si ripete il controllo per verificare se M[n] \ge Di \; e se fallisce si aggiungeranno ulteriori bit settati a 0 \; al quoto.
Nell'esempio questo accade al risultato D3 \; dove è necessario aggregare fino a 3 \; bit di Dv \; per ottenere M6 > Di \;.


7- L'operazione si conclude, per una divisione tra numeri binari naturali interi, quando il LSB di Dv \; è stato aggregato all'ultima differenza eseguita.
A questo punto, detto MU \; l'ultimo numero binario ottenuto dalla summenzionata aggregazione, si possono verificare 2 casi:
a) MU < Di in questo caso Mu rappresenta il resto della divisione e l'ultimo bit del quoto è settato a 0 \;
b) MU > Di in questo caso è possibile eseguire l'ultima differenza, che chiameremo DU \;, e setteremo l'ultimo bit del quoto a 1 \;
DU = MU - Di\; dove
DU \; rappresenterà il nostro resto e sarà 0 \le DU < Di \;.

Quindi, come si vede dalle operazioni svolte

(110010101 \div 111 = 111001 \; resto \; 110)_{(2)} \; che equivale a

(405 \div 7 = 57 \; resto \; 6)_{(10)} \;.

Ovviamente è anche possibile continuare la divisione ed avere un risultato frazionario: in questo caso, raggiunto il LSB del dividendo si porrà una virgola (anche dopo il LSB del quoto), e si aggiungeranno, alla sua destra, tanti bit settati a 0 \; in base al numero di bit, dopo la virgola, che so vuole ottenere nel quoto.

Supponiamo, allora di voler continuare la precedente divisione per avere almeno quattro cifre frazionarie nel risultato: aggiungiamo allora una virgola e 4 \; bit settati a 0 \; alla destra del LSB del numero bianrio 110010101_{(2)} \; e, procedendo come abbiamo visto, otteniamo:

In definitiva, quindi, continuando fino alla quarta cifra decimale si ottiene

(110010101 \div 111 = 111001,1101 \; resto \; 0,0110)_{(2)} \; che equivale a

(405 \div 7 = 57,8125 \; resto \; 0,3125)_{(10)} \;.

Si può notare che, nella suddetta divisione, M7 = M10 \;, quindi la sequenza si ripete, perciò il risultato di tale divisione è un numero periodico di periodo 110_{(2)} \;:

(110010101 \div 111 = 111001,\overline {110})_{(2)} \;.

Di fatti anche nel sistema numerico decimale si otterrebbe un numero periodico:

(405 \div 7 = 57,\overline {857142})_{(10)} \;


Metodo della "sottrazione e scorrimento"

In questo metodo ci si basa sul principio dello spostamento (o scorrimento/shift) di un numero binario, similmente a quanto abbiamo analizzato in precedenza nel paragrafo relativo alla moltiplicazione per 2^n \;.

In pratica il procedimento segue questo schema:

detti

A_{(2)} \; dividendo
B_{(2)} \; divisore
Q_{(2)} \; quoto

Divisione tra numeri binari frazionari (virgola fissa)

Nel caso in cui fosse necessario eseguire divisioni con dividendo e/o divisore frazionari (in virgola fissa), è conveniente eseguire la divisione trattando i numeri binari come interi, applicando le seguenti regole al risultato ottenuto:

detti

n_{(Dv)} \; il numero di bit frazionari che compongono il dividendo

m_{(Di)} \; il numero di bit frazionari che compongono il divisore

si possono presentare 3 \; casi:

1) n(Dv) = m(Di)
In questo caso il risultato della divisione tra i due numeri binari considerati come interi coincide con il risultato della divisione tra i due numeri binari frazionari.
Esempio
(11,011 \div 1,111 = 11011 \div 1111 = 1,110011\dots)_{(2)}
2) n(Dv) > m(Di)
In questo frangente, una volta ottenuto il risultato della divisione tra i due numeri binari considerati come interi, si dovrà spostare la virgola di (n(Dv)m(Di)) posizioni verso sinistra: ogni eventuale posizione oltre il MSB del quoto va settata a 0 \;.
Esempio
Eseguire la divisione tra 1,1011_{(2)} \; e 11,11(2)
Passando ai numeri interi otteniamo (11011 \div 1111 = 1,110011\dots)_{(2)} \;
Il dividendo ha 4 \; bit dopo la virgola e il divisore 2 \;, quindi dobbiamo spostare a sinistra la virgola del risultato di 2 \; posizioni ma, superando il suo MSB saremo costretti ad aggiungere 2 \; bit settati a 0 \; quindi:
(1,1011 \div 11,11 = 0,0110011\dots)_{(2)}
3) n(Dv) < m(Di)
Questo caso è l'opposto del precedente, per cui, una volta ottenuto il risultato della divisione tra i due numeri binari considerati come interi, si dovrà spostare la virgola di (m(Dv)n(Di)) posizioni verso destra.
Esempio
Eseguire la divisione tra 11,11_{(2)} \; e 1,1001(2)
Passando ai numeri interi otteniamo (1111 \div 11001 = 0,100110011\dots)_{(2)} \;
Il dividendo ha 2 \; bit dopo la virgola e il divisore 4 \;, quindi dobbiamo spostare a destra la virgola del risultato di 2 \; posizioni ottenendo:
(11,11 \div 1,1001 = 10,0110011\dots)_{(2)}


Divisioni con divisore pari a 2^n \;

Nel caso in cui il divisore equivalga a 2n, quindi 10_{(2)} = 2^1_{(10)} \;, 100_{(2)} = 2^2_{(10)} \;, 1000_{(2)} = 2^3_{(10)} \;, ecc..., il riusltato della divisione equivale a spostare a sinistra di n \; bit il limite della parte frazionaria del dividendo.

In questo frangente si dice che il risultato equivale al numero di partenza spostato (shiftato) a destra di n \; posizioni: questo concetto verrà ripreso in seguito quando verranno trattati i registri a scorrimento o shift register.

Infatti se eseguiamo la divisione tra 1100_{(2)} = 12_{(10)} \; e 100_{(2)} = 2^2_{(10)} \;, otteniamo:

Come possiamo vedere il quoto equivale al dividendo a cui sono stati "tolti" i 2 \; bit di sinistra, cioè, in altre parole, è come aver spostato (shiftato) a sinistra di 2 \; posizioni il LSB della parte intera.

La cosa risulta più evidente se eseguiamo la divisione tra 1100_{(2)} = 12_{(10)} \; e 1000_{(2)} = 2^2_{(10)} \;: in questo caso il risultato è 1,1_{(2)} = 1,5_{(10)} \; e si nota più chiaramente che il LSB della parte intera è stato spostato a sinistra di 3 \; posizioni.

Con questo abbiamo concluso la disamina delle quattro operazioni fondamentali nel sistema numerico binario, relativamente ai numeri interi e frazionari (a virgola fissa).

Prossimamente analizzeremo come vengono rappresentati i numeri frazionari a virgola mobile, poi, nel proseguio di questa trattazione, inizieremo ad analizzare come si realizzano alcune funzioni digitali combinatorie d'uso più comune.

LogicBignami - Indice articoli correlati

3

Commenti e note

Inserisci un commento

di ,

Chiedo scusa per l'enorme ritardo accumulato nella pubblicazione di questo capitolo: purtroppo gli eventi non sono stati dei migliori e la stesura è passata in secondo/terzo piano rispetto ad altre priorità.
Spero, in futuro, di poter essere più veloce nella stesura e pubblicazione.

Resta sempre inteso che ogni errore/miglioria vogliate segnalare è ben accetta.

Rispondi

Inserisci un commento

Per inserire commenti è necessario iscriversi ad ElectroYou. Se sei già iscritto, effettua il login.