Differences

This shows you the differences between two versions of the page.

--- conv_bin_bcd [2018/03/07 16:50] – admin
+++ conv_bin_bcd [2018/03/07 18:48] (current) – admin
@@ Line 59: / Line 59: @@
 Partiamo dal caso più semplice di N=2 con la cifra più significativa uguale a 0. Nel caso in cui la cifra meno significativa sia minore di 5 ricadiamo nel caso particolare già osservato in precedenza. Elenchiamo comunque esplicitamente tutti i casi:
+  * ''2x{'0000' '0000'}10''=''{'0000' '0000'}10''  (ovvero: 2x0=0)
+  * ''2x{'0000' '0001'}10''=''{'0000' '0010'}10''  (ovvero: 2x1=2)
+  * ''2x{'0000' '0010'}10''=''{'0000' '0000'}10''  (ovvero: 2x2=4)
+  * ''2x{'0000' '0011'}10''=''{'0000' '0000'}10''  (ovvero: 2x3=6)
+  * ''2x{'0000' '0100'}10''=''{'0000' '0000'}10''  (ovvero: 2x4=8)
   * ''2x{'0000' '0101'}10''=''{'0001' '0000'}10''  (ovvero: 2x5=10)
-  * 2x{'0000' '0110'}10={'0001' '0010'}10  (ovvero: 2x6=12)
+  * ''2x{'0000' '0110'}10''=''{'0001' '0010'}10''  (ovvero: 2x6=12)
-  * 2x{'0000' '0111'}10={'0001' '0100'}10  (ovvero: 2x7=14)
+  * ''2x{'0000' '0111'}10''=''{'0001' '0100'}10''  (ovvero: 2x7=14)
-  * 2x{'0000' '1000'}10={'0001' '0110'}10  (ovvero: 2x7=16)
+  * ''2x{'0000' '1000'}10''=''{'0001' '0110'}10''  (ovvero: 2x7=16)
-  * 2x{'0000' '1001'}10={'0001' '1000'}10  (ovvero: 2x7=14)
+  * ''2x{'0000' '1001'}10''=''{'0001' '1000'}10''  (ovvero: 2x7=14)
+Se per un momento dimentichiamo l'interpretazione delle stringe in BCD e le guardiamo le rappresentazioni come strimghe in binario naturale, vediamo che nel caso il cui il numero di partenza è maggiore di 4 la corrispodenza (di nuovo: interpretrando le stringhe di 8 bit complessivi in binario naturale) la funzione che dobbiamo implementare per avere poi i bit giusti in notazione BCD è la seguente
+  * da ''{0000_0101}2''a ''{0001_0000}2'' ovvero da 5 a 16
+  * da ''{0000_0110}2''a ''{0001_0010}2'' ovvero da 6 a 18
+  * da ''{0000_0111}2''a ''{0001_0100}2'' ovvero da 7 a 20
+  * da ''{0000_1000}2''a ''{0001_0110}2'' ovvero da 8 a 22
+  * da ''{0000_1001}2''a ''{0001_1000}2'' ovvero da 9 a 24
+ Si noti che la relazione ottenuta è la funzione
+  * y=2xc+6=2x(c+3)
+dove y è il risultato da ottenere e c è il valore della cifra meno significativa del numero BCD di partenza.
+Come è allora evidente, per ottenere la rappresentazione giusta del doppio in BCD nel caso esaminato (numero su due cifre in BCD con la prima cifra 0 e la seconda di valore c) basta operare come segue:
+  * si interpretano i 4 bit dell'ultima cifra in binario naturale.
+  * se il numero risultante è minore di 5, si esegue uno shift a sinistra del gruppo di 4 bit
+  * se il numero risultante è maggiore o uguale a 5 si esegue in binario naturale l'operazione 2x(c+3); i 4 bit meno significativi del risultato sono usati come cifra BCD meno significativa, alla cifra più significativa della rappresentazione BCD si assegna la stringa "0001". A questo risultato si giunge anche se si somma 3 (in binario naturale) alla cifra a si fa uno schift a sinistra dell'intera stringa di bit mettendo a 0 il bit più a destra.
+Resta da vedere se è possibile generalizzare l'operazione a numeri rappresentati in BCD con un numero qualunque di cifre (sempre nell'ipotesi che il doppio del numero dato sia rappresentabile sullo stesso numero di cifre).
+Per fare questo immaginiamo che quanto fatto fino ad ora fosse in realtà riferito a un numero rappresentato in BCD su tre cifre con la prima cifra pari a zero, la seconda cifra che svolge il ruolo della seconda cifra nel caso precedente e la terza cifra con valore qualunque.
+Ora pensiamo al fatto che moltiplicare per 2 un numero significa sommarlo a se stesso e pensiamo all'algoritmo per la somma imparato alle elementari. Perché partiamo dalla colonna più a destra dopo aver incolonnato i numeri? perché per calcolare la cifra immediatamente a destra ci serve sapere se c'è riporto dalla colonna che stiamo esaminando. Se sapessimo che, nel caso di un numero a tre cifre (con la prima cifra 0), la somma sulla colonna più a destra non genera riporto, potremmo calcolare le 2 cifre più a sinistra senza bisogno di effettuare la somma sulla colonna più a destra. In questo caso ricadremmo nel caso dell'esempio fatto in precedenza del numero a due sole cifre. Quando questo succede, il bit meno significativo della codifica BCD della seconda cifra da destra della somma è sicuramente '0'. Inoltre, qualunque sia la il valore della seconda cifra da destra degli addendi, visto che stiamo facendo la somma di due cifre uguali (in assenza di riporto), il valore della cifra della somma nella colonna corrispondente è certamente pari e quindi inferiore o al più uguale a 8.
+Cosa succede, però, se c'e' riporto dalla prima colonna a destra? Si tratta di sommare 1 alla cifra della somma immediatamente a destra. Questa somma avrà effetto solo sulla cifra immediatamente a destra che, ricordiamo, prima della somma del riporto era certamente inferiore a 9. Si noti anche che, applicando l'algoritmo più sopra descritto (se la cifra è maggiore o uguale a 5 si somma tre e si fa uno shift a sinistra della stringa risultante, il bit più significativo della cifra a sinistra (che è certamente 1 in questo caso) diventa il bit meno significativo della cifra immediatamente a sinistra, cosa che corrisponde effettivamente a sommare uno alla stessa, ovvero a tenere conto del riporto.
+In definitiva, per ottenere la rappresentazione del doppio di un numero con il numero di partenza e di arrivo rappresentati in BCD si procede come segue:
+  * si guardano i gruppi di 4 bit di ciascuna cifra come numeri in codifica in binario naturale.
+  * per ciascun numero (ciascuna cifra), se il valore è maggiore o uguale a 5 si somma 3 (algoritmo di somma in binario naturale) e si sostituiscono i 4 bit risultanti (non ci può essere riporto) a quelli precedenti.
+  * dopo aver eseguito il punto precedente per tutte le singole cifre, si esegue uno shift a sinistra dell'intera stringa di bit, mettendo a 0 il bit meno significativo.
+  * i gruppi di bit allineati a 4 a 4 partendo da sinsitra sono le cifre BCD del numero pari al doppio del numero di partenza.
+Queste considerazioni sono alla base dell'algoritmo di conversione da codifica in binario naturale a BCD che va sotto il nome di "double dabble algorithm" [[https://en.wikipedia.org/wiki/Double_dabble|vedi]].
-Numeriamo le colonne dell'algoritmo della somma delle elementari da destra a sinistra partendo da 0 (la colonna più a detrsa è individuata dal numero (N-1). Concentriamo la nostra attenzione sulla colonna generica L (supponiamo per ora N-1>L>0). Siano C(L-1), C(L) e C(L+1) rispettivamente i valori delle cifre nella colonna L-1, L e L-1 del numero di partenza (quello di cui vogliamo ottenere il doppio. Si tratta di capire come si trova il valore della cifra S(L) della colonna L della somma.
-Distinguiamo intanto i casi possibili nei due casi seguenti: C(L-1)<5 e C(L-1)>=5.
-: a sinistra della cifra L, della cifra L,  (cifre da detrsa verso sinistra