[Architettura Degli Elaboratori] Problemi con Addizione anticipo del riporto e Moltiplicazione numeri senza segno

[giupar93]

Salve ragazzi, sto affrontando un argomento davvero tosto.. Addizione con anticipo del riporto e la Moltiplicazione di numeri senza segno. Ho letto più e più volte la spiegazione del libro, ma non la capisco, ho cercato in rete ma non trovo nulla che coincida con quello del libro o se coincide non si capisce una mazza. Ora mi rivolgo a voi come ultima spiaggia. Qualcuno potrebbe spiegarmi queste due "Tecniche" ? RIngrazio anticipatamente tutti coloro che almeno ci proveranno. Grazie !!

[BoG3]

ma ti interessa la circuiteria? lo schema generale astratto? ... dicci!
Un adder ripple carry (credo sia quello che intendi tu) nasce così:

Si costruisce un sommatore a 1 bit! Come? semplice:
so fare la somma dei bit? si!! la tabella di verita' è:

x+y = s
______
0+0 =0
0+1 =1
1+0 =1
1+1 =0 con riporto 1

Concordi? Ora, chiaramente un sommatore a 1 bit.. non è che abbia molte applicazioni di per se, specialmente in macchine complesse, che lavorano su gruppi di bit (4,8,16,32,64...) Giusto? Se tu volessi sommare 13+11, avresti bisogno al meno di un sommatore a 4 bit (questo perchè con 4 bit puoi rappresentare 16 numeri, da 0 a 15). Attenzione, 13+11 supera l'intervallo di rapresentabilita' con 4 bit ma ora nn preoccupiamocene
Uno dei vantaggi di un sommatore di questo tipo è che è modulare. questo vuol dire che posso prenderlo, come i pezzi di lego ed attaccarne diversi un serie per creare un sommatore a 2,3,4,...89bit.
Per rendere piu' completo il mio sommatore devo prevedere che ci possa essere anche un carry del bit precedente.
Pero' se faccio questo lavoro, il riporto di un sommatore dovra' andare ad influenzare la somma di quell osuccessivo, ad esempio:

01+
01=
----
10

esattamente come accade nelle somme decimali, riporto e sommo "l'eccesso" sulla somma a sinistra rispetto a quella momentaneamente in esame.
Ora se prendi in esame una somma piu' complessa come ad esempio:

1101+
1011

capisci che ai fini di un risultato corretto, è importante sapere cosa è accaduto nella somma antecedente, se questa ha riportato un carry o meno.

Ops! allora, sopra, abbiamo proposto una soluzione non buona. riproviamo a creare una tabella di verita' piu' completa:

x y C | S C 
______|__________
0 0 0 | 0 0
0 0 1 | 1 0
0 1 0 | 1 0
0 1 1 | 0 1
1 0 0 | 1 0
1 0 1 | 0 1
1 1 0 | 0 1
1 1 1 | 1 1

TABELLA 1

dove x,y sono le cifre binarie da sommare, C è il carry (a sinistra è il carry in ingresso, ovvero quello generato da un eventuale operazione precedente, a destra della tabella è il carry in uscita dall'attuale operazione), S è la somma di x e y
Ora siamo in grado di ricavarci le equazioni delle varie uscite $S_i, C_i$ in base agli ingressi.
Quindi hai che $S =\bar(x)*\bar(y)*C + \bar(x)*y*\bar(C)+ x*\bar(y)*\bar(C)+x*y*C$ ti invito a ricavare la formula del Carry in uscita e a semplificare un po' il tutto. (caso mai facci sapere se non riesci).
Ora guarda questa foto:


Capisci che il 2° adder deve aspettare che il primo generi il risultate e l'eventuale carry, il terzo deve aspettare il 2°, il quarto il 3° e così via ... questo si rileva inefficace. I progettisti pero' hanno visto che in realta' il carry ..puo' essere predetto ancor prima dell'operazione di somma e quindi hanno pensato bene di evitare il ritardo di un ripple carry implementando questa nuova idea. Ora, dalla tabella 1 possiamo ricavarci la seguente relazione: $C_(i+1)=x_i*y_i+C_i*(x_i+y_i)$ questo vuol dire che l curry al passo successivo esiste sol ose le 2 cifre precedentemente sommate sono 1 e 1 oppure se gia da prima esisteva un carry e che è stato sommato ad un altro 1 (che sia x=1 o y=1 non importa).

Ora hanno isolato $x_i*y_i$ e l'hanno chiamato G (generatore, perchè se $x_i*y_i=1$ avro' sicuramente un riporto) e $C_i*(x_i+y_i)$ l'hanno chiamato P (propagate, perchè il carry ricevuto in ingresso, va a sommarsi ad un 1 di uno dei 2 operandi e viene "propagato sulla somma successiva"). otteniamo una cella di questo tipo:


Ora con dei calcoli matematici semplici (sostituzioni) puoi ottenere:
$c_1 = G_0+P_0c_0$ ossia: il carry genreato in uscita dal primo sommatore a 1 bit dipende da $G_0+P_0C_0$, vedi sopra le loro definizioni.
Ok ma... posso anche dire subito a cosa corrisponde il carry del secondo sommatore a 1 bit:
$c_2 = G_1+P_1c_1$ ma.. posso sostituire $c_1$ con la formula ricavata sopra: $c_1 = G_0+P_0c_0$ e ottengo:
$c_2 = G_1+P_1(G_0+P_0c_0)$, così anche per il terzo sommatore:

$c_3 = G_2+P_2c_2= G_2 + P_2(G_1+P_1(G_0+P_0c_0))$ etc etc... piu' chiaro? spero di aver scritto tt giusto :\