Appunti Fondamenti di Informatica teoria - sistemi di numerazione

SISTEMI DI NUMERAZIONE: OTTALE

SISTEMI DI NUMERAZIONE: ESADECIMALE

SISTEMI DI NUMERAZIONE: ESEMPIO

CONVERSIONE DALLA BASE A ALLA BASE B

- Per la parte intera:

Dato un numero in una base A (es 10), si vuole rappresentarlo in base B (es 2), cioè:

NA = NB + B^2 + B^3 + ...

NA = x0 + B(x1 x2 x3 + ...)

Se dividiamo per la nuova base B, otteniamo un quoziente ed un resto R.

NA = Q1B + R

Uguagliando: NA = R + BQ1 = x0 + B(x1 + B(x2 + ...))

Da cui: x0 = R (resto della divisione)

(x1 + B(x2 + ...)) = Q1 (quoziente)

Iterando il procedimento con Q1 al posto di NA, si ottengono tutti i coefficienti del polinomio nelle potenze di B, cioè la codifica di NA nella nuova base, e quindi NB.

CONVERSIONE DI BASE: NUMERI FRAZIONARI

CONVERSIONE DI BASE

- Per la parte frazionaria:

Dato

un numero in una base A (es. 10), si vuole rappresentarlo in base B(es. 2), cioèè̀: B^-1x^-1 B^-2x^-2 B^-3x^-3 B^-4x^-4+...FA = FB = + + +B^-1(x^-1 B^-1(x^-2 B^-1(...B^-1x^-r)...))= + +Se moltiplichiamo FA per la nuova base B, otteniamo una parte intera I ed una parte frazionaria F1 . Uguagliando:-1 -1 -1• B = x^-1 + B (x^-2 + B (...B x^-r)...) = I + F1FAda cui: x^-1 = IB^-1(x^-2 B^-1(...B^-1x^-r)...)+ = F1Iterando il procedimento con F1 al posto di FA , si ottengono i coefficienti del polinomio nelle potenze di B, cioè la codifica di FA nella nuova base, e quindi FB . Il procedimento termina quando- F1 = 0, oppure- B^-rquando si è raggiunta la precisione desiderata (errore < se ci si ferma al termine x^-r)DA DECIMALE A BINARIO: NUMERI FRAZIONARI- Si moltiplica ripetutamente il numero frazionario decimale per 2, fino ad ottenere una parte decimale nulla o, dato che la condizione potrebbe non verificarsi mai, per un numero prefissato di volte; le cifre del numero binario sono

parti intere dei prodotti successivi; la cifra più significativa è la parte intera del risultato della prima moltiplicazione.

CONVERSIONE DI BASE: NUMERI FRAZIONARI

CONVERSIONE DI BASE: RIASSUNTO

• Parte intera: divisioni per la nuova base, ogni resto rappresenta una cifra a partire dalla meno significativa;
• Parte frazionaria: moltiplicazioni per la base, la parte intera di ogni prodotto rappresenta una cifra a partire dalla più significativa;

CONVERSIONE DI BASE: NUMERI FRAZIONARI

DA DECIMALE A BINARIO: NUMERI INTERI

• Si divide ripetutamente il numero intero decimale per 2 fino ad ottenere un quoziente nullo; le cifre del numero binario sono i resti delle divisioni; la cifra più significativa è l'ultimo resto.

CONVERTIRE IL NUMERO IN BINARIO 58,07₁₀

CONVERTIRE IL NUMERO IN ESADECIMALE 4287,312₁₀

CONVERSIONI TRA BASI CHE SIANO POTENZE DI 2

Se una base è potenza dell'altra, con esponente K, la conversione si ottiene sostituendo ogni gruppo di K

cifre del numero in una base (β1 ) con la cifra corrispondente nell’altra base (β2 ) o viceversa.

Es: da base β1=2 a base β2=8 (K=3) da base β1=2 a base β2=16 (K=4)

N.B. se il numero di bit non è multiplo di K aggiungere gli 0 necessari a renderlo tale in posizioni che non modifichino il significato del numero.

DA BINARIO A ESADECIMALE

- Una cifra esadecimale corrisponde a 4 bit

- Si possono rappresentare numeri binari lunghi con poche cifre (1/4)

- La conversione da binario ad esadecimale è immediata, raggruppando le cifre binarie in gruppi di 4 (da destra) e sostituendole con le cifre esadecimali secondo la tabella precedente.

DA ESADECIMALE A BINARIO

- La conversione da esadecimale a binario si ottiene espandendo ciascuna cifra con i 4 bit corrispondenti.

CONVERSIONI FRA BASI DIVERSE: ESEMPI

CONVERSIONE DA BASE 8 A BASE 16

CONVERSIONE DA BASE A 16 A BASE 8

OPERAZIONI BINARIE

OSSERVAZIONI

- In qualsiasi base, il sistema di numerazione posizionale

Impone che combinazioni diverse di cifre uguali rappresentano numeri diversi. Ad esempio: - Numeri che hanno identica rappresentazione, in basi diverse, hanno valori diversi: Nota: più piccola è la base, minore è il valore del numero rappresentato dalla stessa sequenza di cifre.

LA RAPPRESENTAZIONE DEI DATI E L'ARITMETICA DEGLI ELABORATORI

• I numeratori interi positivi sono rappresentati all'interno dell'elaboratore utilizzando un multiplo del byte (generalmente 4 byte);
• Se l'intero si rappresenta con un numero di cifre minore, vengono aggiunti zeri nelle cifre più significative. Ex. 12 viene rappresentato in un byte come...00001100

NUMERI CON SEGNO

• Per rappresentare numeri con segno, occorre utilizzare un bit in più per definire il segno del numero;
• Si possono usare tre tecniche di codifica.

RAPPRESENTAZIONE DEI NUMERI NEI CALCOLATORI 8

Si consideri un byte (8 bit). Un byte permette di rappresentare stati 2 differenti; può essere utilizzato per rappresentare numeri interi senza segno da 0 a 255 o numeri interi con segno da -128 a 127.

Pertanto, memorizzare 256 diverse configurazioni corrispondenti ai primi 256 numeri naturali (0-255);

Nella rappresentazione in valore assoluto:

N=b₇ b₆ b₅ b₄ b₃ b₂ b₁ b₀•2⁷ + b₆•2⁶ + b₅•2⁵ + b₄•2⁴ + b₃•2³ + b₂•2² + b₁•2¹ + b₀

b₇ b₆ b₅ b₄ b₃ b₂ b₁ b₀

0010010 17 6 5 4 3 2 1 0 N=37

RAPPRESENTAZIONE DEI NUMERI POSITIVI E NEGATIVI

Esiste un problema: come rappresentare i numeri negativi?

Prima soluzione: rappresentazione in Modulo e Segno (anche detta Binario Naturale)

Si utilizza un bit per rappresentare il segno del numero considerato

0 > + (numero positivo)

1 > - (numero negativo)

Se consideriamo un byte, rimangono ora 7 bit per il modulo del numero: i 7 numeri rappresentabili sono perciò ±[0-127] ±[0-2⁷ - 1]

b₇ b₆ b₅ b₄ b₃ b₂ b₁ b₀

b₇ b₆ b₅ b₄ b₃ b₂ b₁ b₀

+/- 6 5 4 3 2 1 0

RAPPRESENTAZIONE DEI NUMERI POSITIVI E NEGATIVI

RAPPRESENTAZIONE DEI NUMERI IN MODULO E SEGNO n-1

Esistono due rappresentazioni diverse dello 0 distanti 2 fra di loro, se n sono i

bit usati per la rappresentazione (8 con 4 bit);

Un incremento binario nella rappresentazione corrisponde ad un incremento per numeri positivi, ma un decremento per numeri negativi;

n-1 Numero minimo: -2 +1

n-1 Numero massimo: 2 -1

RAPPRESENTAZIONE IN MODULO E SEGNO: PROBLEMI

Addizione e sottrazione sono le operazioni di cui si deve disporre per poter realizzare qualsiasi operazione aritmetica più complessa;

Si supponga che il calcolatore abbia una "Unità Aritmetica" che realizzi indipendente le due operazioni;

Di fronte ad una somma algebrica, il calcolatore dovrebbe:

1. Confrontare i due segni,
2. Se uguali, attivare il circuito di addizione,
3. Se diversi, identificare il maggiore (in valore assoluto) ed attivare il circuito di sottrazione,
4. Completare il risultato con il segno corretto.

I passi indicati non sono eseguibili contemporaneamente perché ognuno dipende dai precedenti.

In pratica, invece, per effettuare somma e sottrazione si ricorre ad

COMPLEMENTO ALLA BASE b DI UN NUMERO

Il complemento alla base b di un numero x con n cifre è rappresentato:

• Se esso è positivo, dal numero in binario puro (notazione posizionale);
• Se è negativo, dalla sequenza binaria che rappresenta il valore b -|X|;

Nella rappresentazione in complemento alla base con n cifre le combinazioni rappresentano numeri positivi e negativi.

In particolare:

• Le combinazioni da 0 a (b /2 – 1) rappresentano i numeri positivi, rispettando la usuale rappresentazione posizionale;
• Le combinazioni da b /2 fino a (b – 1) rappresentano i numeri negativi.

ESEMPIO

COMPLEMENTO A 10

Esempio 102b=10, n=2; configurazioni: i numeri da 0 a 49 rappresentano i positivi, con il consueto significato; da 50 a 99 i negativi come previsto dal complemento (-1à99, -2à98, ..., -49à51, -50à50). 2X=-36; -X in

BASE

Nelle rappresentazioni in complemento alla base le rappresentazioni dei numeri negativi sono definite solo quando si è stabilito il numero di cifre.

Esempi:

Il complemento alla base 10 per X= -36, n=2 è 64

Il complemento alla base 10 per X= -36, n=3 è 964

N.B: Entrambi i numeri ottenuti rappresentano -36 !!!

Il complemento alla base 2 per X= -36, n=7 è 1011100

Il complemento alla base 2 per X= -36, n=8 è 11011100à.

con n=7: 36₁₀ = 0100100₂. -36 in complemento a 2 = 1011100₂-36

con n=8: 36₁₀ = 00100100₂. in complemento a 2 = 11011100₂

RAPPRESENTAZIONE IN COMPLEMENTO: RIEPILOGO

- Rappresentazione in complemento a 2:

i numeri positivi sono rappresentati dal loro modulo e hanno il bit più significativo (segno) posto a 0.

I numeri negativi sono rappresentati dalla quantità che manca al valore assoluto del numero (numero positivo) per arrivare alla base elevata al numero di cifre utilizzate (segno compreso).

Pertanto, i numeri negativi hanno il bit del segno sempre a 1.

Metà delle configurazioni sono perciò riservate ai numeri positivi e metà ai numeri negativi.

Discorsi analoghi possono essere fatti per basi diverse da 2: in base 10 un numero è negativo se la prima cifra è 5, in base 8 se 4.