Note per gli studenti (C. Ciofi)

Molto spesso, quando si affrontano per la prima volta apetti relativi alla rappresentazione dei numeri si fa fatica a distinguere il numero in quanto entità che esiste e mantiene le sue proprietà (cioè il suo “valore”) independentemente dalla sua rappresentazione e la sua rappresentazione. Il punto è che per esprimere il valore di un numero non possiamo fare a meno di usare una rappresentazione. Se restringiamo l'attenzione ai numeri naturali, chiunque abbia una formazione tecnico-scientifica elementare conosce almeno tre rappresentazioni dello stesso numero: la rappresentazione decimale, la rappresentazione mediante “numeri romani”, la rappresentazione in binario naturale. Le seguenti rappresentazioni si riferiscono tutte allo stesso numero:

• decimale (usando 3 cifre): 079

• binario (usando 8 cifre): 01001111

• numemri romani: LXXIX

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 che, inevitabilmente, siamo portati a confondere il numero con la sua rappresentazione decimale.

In queste note, che vogliono essere una presentazione non rigirosamente formale di un particolare metodo di conversione dalla rappresentazione in binario naturale alla rappresentazione in BCD di interi naturali, non ci resta che sfruttare l'indentificazione fra numeri e loro rappresentazione decimale per semplificare, per quanto possibile, la discussione. Useremo comunque le seguenti convensioni:

• Il numero viene identificato dalla sua notazione decimale (per esempio parleremo “del numero 79”)
• Quando vorremo fare esplicito riferimento alla rappresentazione, useremo una stringa ordinata di simboli fra parentesi graffa, seguita dall'indicazione della base espressa in decimale. Per esempio diremo che la rappresentazione in decimale su 4 cifre del numero 79 è {“0079”}10; la rapresentazione in binario di 79 su otto cifre è {“01001111”}2, la rappresentazione in ottale (base 8) di 79 su 4 cifre è {“0117”}8, la rappresentazione di 79 in esadecimale su 3 cifre è {“04F”}26 e così via.
• 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

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: 2×0=0)
• 2x{'0000' '0001'}10={'0000' '0010'}10 (ovvero: 2×1=2)
• 2x{'0000' '0010'}10={'0000' '0000'}10 (ovvero: 2×2=4)
• 2x{'0000' '0011'}10={'0000' '0000'}10 (ovvero: 2×3=6)
• 2x{'0000' '0100'}10={'0000' '0000'}10 (ovvero: 2×4=8)

• 2x{'0000' '0101'}10={'0001' '0000'}10 (ovvero: 2×5=10)
• 2x{'0000' '0110'}10={'0001' '0010'}10 (ovvero: 2×6=12)
• 2x{'0000' '0111'}10={'0001' '0100'}10 (ovvero: 2×7=14)
• 2x{'0000' '1000'}10={'0001' '0110'}10 (ovvero: 2×7=16)
• 2x{'0000' '1001'}10={'0001' '1000'}10 (ovvero: 2×7=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}2a {0001_0000}2 ovvero da 5 a 16
• da {0000_0110}2a {0001_0010}2 ovvero da 6 a 18
• da {0000_0111}2a {0001_0100}2 ovvero da 7 a 20
• da {0000_1000}2a {0001_0110}2 ovvero da 8 a 22
• da {0000_1001}2a {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”.

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).

Facciamo riferimento al seguente schema di calcolo che mette in evidenza il fatto che la moltiplicazion per 2 non è altro che il risultato della somma di un numero per se setesso:

col: N-1 N-2 ….. L+1 L L-1 ….. 1 0

'0000' '0101' ….. '0110' '1001' '1000' ….. '0011' '0101' + '0000' '0101' ….. '0110' '1001' '1000' ….. '0011' '0101' = ——————————————————————