Differences

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

--- conv_bin_bcd [2018/03/07 14:35] – admin
+++ conv_bin_bcd [2018/03/07 18:48] (current) – admin
@@ Line 13: / Line 13: @@
 Allo domanda "di che numero si tratta?" siamo tutti portati a dire che si tratta del numero "settantanove" in ogni caso. A pesarci bene, però, questa non è la risposta alla domanda. Semmai, dire che il numero che in rappresentazione con numeri romani "LXXIX" è il numero "settantanove" esprime il fatto che il numero "rappresentato" da "LXXIX" è lo stesso "rappresentato" da "079" nei  due rispettivi contesti.
-Siamo così abituati alla rappresentazione in notazione decimale dei numeri interi che, inevitabilmente, siamo
+Siamo così abituati alla rappresentazione in notazione decimale dei numeri che, inevitabilmente, siamo
 portati a confondere il numero con la sua rappresentazione decimale.
@@ Line 22: / Line 22: @@
   * Se si usa la virgola per rappresentare numeri decimali adottiamo le seguenti ovvie convenzioni:
   *   * {"0023,412"}10 rappresenta il numero 23412/10^3; {"010011,11"}2 rappreseta il numero 79/(2^2) e così via.
 Si noti inoltre che, nella ipotesi di ragionare in un contesto in cui gli algoritmi che illustreremo dovranno essere rigorNon ci resta quindi che prendere atto di questo fatto e contesti di  tutti coloro i quai hanno avuto una esperienza anche solo superficiale con
+===Rappresentazione Binary Coded Decimal (BCD)===
+La rappresentazione in BCD è sostanzialmente coincidente con la notazione decimale con la differenza che al posto dei simboli da "0" a "9" si usano stringhe ordinate di 4 cifre (che possono essere solo "0" o "1") per rappresentare ciascuno di esse. La rappresentazione scelta è tale che la stringa di 4 bit, interpretata secondo una codifica in binario naturale, è il numero corrispondente al valore della cifra.
+La corrispondenza fra simboli è la seguente:
+  * invece del simbolo "0" si usa "0000" corrispondente al numero {0000}2=0
+  * invece del simbolo "1" si usa "0001" corrispondente al numero {0001}2=1
+  * ...............
+  * invece del simbolo "9" si usa "1001" corrispondente al numero {1001}2=9
+Pertanto, con queste posizioni, il numero 79 in notazione decimale su 4 cifre si può scrivere sia {0079}10, sia {'0000' '0000' '0111' '1001'}10.
+Nota bene che la dizione notazione decimale indica, inq uesto contesto, il modo in cui si passa dal valore delle singole cifre al valore del numero, non ai simboli che vengono effettivamente usati per indicare le cifre da 0 a 9.
+I simboli BCD sono utili in quando si possono usare stringe di bit (due soli simboli possibili) per codificare 10 cifre distinte.
+Tuttavia, la notazione decimale con cifre BCD gode di alcune proprietà estremamente interessanti ai fini dell'algoritmo che vogliamo sviluppare.
+Sappiamo per esperienza diretta che se un numero in notazione decimale è rappresentato da cifre tutte inferiori a 5, la rappresentazione del doppio si ottiene semplicemente sostituendo a ogni cifra una nuova cifra che corrisponde al valore doppio della cifra precedente. Per esemio il doppio di 123 è 246 che si può ottenere sostituendo a "1" il "2", a "2" il "4" e a "3" il "6". In notazione decimale su 4 cifre con simboli BCD si ha:
+  * 2x{'0000' '0001' '0010' '0011'}10={'0000' '0010' '0100' '0110'}10
+Se si mettono a confronto le due stringe di simboli "0" e "1" dimenticando per un momento il ragguppamente a quattro a quattro della rappresentazione BCD, si ottiene che si è passati dalla stringa di partenza ("0000_0001_0010_0011") alla stringa di arrivo ("0000_0010_0100_0110") nello stesso modo in cu si sarebbe ottenuta la rappresentazione del doppio di un numrero rappresentato in binario naturale (shift a sinistra di una posizione con inserimento di uno 0 a destra). Questa proprietà è certamente interessante, ma come è facile verificare funziona solo nel caso in cui le cifre decimali (o BCD, che è a stessa cosa) di partenza sono strettamente inferiori a 5. Vediamo allora se e come si può estendere l'algoritmo anche ai casi in cui le cifre sono maggiori di 5. Moltiplicare un numero per 2 equivale a farne la somma con se stesso. Facciamo riferimento all'algoritmo della somma imparato alle elemntari con l'unica differenza che invece di usre come simboli le cifre da "0" a "9" usiamo i sorrispondenti simboli in BCD. Supponiamo inoltre di usare lo stesso numero di cifre (N) per la rappresentazione del numero e del suo doppio e che il doppio sia rappresentabile du N cifre.
+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' '0111'}10''=''{'0001' '0100'}10''  (ovvero: 2x7=14)
+  * ''2x{'0000' '1000'}10''=''{'0001' '0110'}10''  (ovvero: 2x7=16)
+  * ''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]].