Base 8

La somma può dare un riporto di ; il prodotto può dare un riporto compreso tra e b-2.

Valgono le stesse regole e proprietà formali della aritmetica decimale ma si devono usare tavole diverse da quelle pitagoriche per addizione e moltiplicazione.

Conversione di un numero reale a da base 10 a base b

Parte intera di a: [a]=N

Metodo delle divisioni successive

Si eseguono successive divisioni intere di N (la prima volta) o dei vari quozienti ottenuti (le volte successive) per la base b, fino a ottenere un quoziente

I resti ottenuti, convertiti nei simboli della base b, sono le cifre di N nella nuova base dalla meno significativa alla più significativa.

ESEMPI

resto 0

resto 1

resto 1

resto 0

resto 1

resto 1

resto 1

resto 1 (246)₁₀=(11110110)₂

resto 6

resto 6

resto 3 (246)₁₀=(366)₈

resto 5

resto 15=F (246)₁₀=(F5)₁₆

Parte frazionaria di a: a-[a]= N

Metodo delle moltiplicazioni successive

Si eseguono successive moltiplicazioni di N (la prima volta) o delle parti frazionarie (le volte successive) per la base b fino a ottenere un prodotto nullo o un numero sufficiente di cifre. Le parti intere dei prodotti successivi, convertite nei simboli della base b, sono le cifre di N nella nuova base.

ESEMPI

0.1 x 2 = 0.2              p. intera 0

0.2 x 2 = 0.4              p. intera 0

0.4 x 2 = 0.8              p. intera 0

0.8 x 2 = 1.6              p. intera 1

0.6 x 2 = 1.2              p. intera 1

0.2 x 2 = 0.4.          p. intera 0 (0.1)₁₀=(0.00011.)₂

0.1 x 5 = 0.5              p. intera 0

0.5 x 5 = 2.5              p. intera 2

0.5 x 5 = 2.5.          p. intera 2 (0.1)₁₀=(0.02.)₅

0.5 x 2 = 1.0 p. intera 1 (0.5)₁₀=(0.1)₂

Caso generale:

conversione da base 10 a base 2 di a=-(25.375)₁₀

segno = -

[|a|] (metodo delle divisioni successive)

a-[|a|] (metodo delle moltiplicazioni successive)

a

Divisioni successive

resto 1

resto 0

6:2=3 resto 0

3:2=1 resto 1

1:2=0 resto 1

Moltiplicazioni successive

.375 x 2= .750        p. intera 0

.750 x 2= 1.500 p. intera 1

.5 x 2 = 1.00           p. intera 1

Conversione di un numero reale a da base b a base

Si sfrutta la rappresentazione posizi 727c24h onale, perché permette di usare aritmetica in base

ESEMPIO

Conversione di un numero reale a da base b₁ a base b₂

Si passa attraverso la base

ESEMPIO

Conversione di (1221)₇ in base 2:

conversione da base 7 a base 10

conversione da base 10 a base 2

resto 0

resto 0

resto 0

57:2=28 resto 1

28:2=14 resto 0

resto 0

resto 1

resto 1

resto 1 (456)₁₀=(111001000)₂

Pertanto (1221)₇ = (111001000)₂

CASO PARTICOLARE

Conversione da base b₁ a base b₂ con :

b₂ = b₁^k: si staccano gruppi di k cifre a partire dal punto radice verso destra e verso sinistra, completando con zeri quelli incompleti

ESEMPIO. a = -(1101110.01)₂

In base

5 6 . 2 )₈

In base

- 0110 1110 . 0100

6 E . 4 )₁₆

b₁ = b₂^k: si espande ogni cifra della rappresentazione in base b₁ in k cifre che esprimono la conversione della cifra nella nuova base b₂

ESEMPIO

a = (53.7)₈

in base 2 (k=3)

5 3 . 7

a = -(E4.A)₁₆

in base 2 (k=4)

E 4 . A

- (1110 0100 . 1010)₂

Numeri fixed point: permettono di rappresentare un intervallo di interi.

Regole di rappresentazione: si abbiano a disposizione t+1 bit

Rappresentazione di un intero positivo N=(a_na_n-1.a₀)₂

t+1          t t-1 1

Se n+1 t, la rappresentazione è corretta: fi(N)=N

Se n+1>t, si ha l'OVERFLOW intero (non rilevato dal computer).

La rappresentazione di un intero N con più di t cifre binarie è non corretta: fi(N) N

Il massimo intero positivo rappresentabile correttamente è 2^t-1

ESEMPIO. t+1=3

000 rappresentazione fixed di 0

001 rappresentazione fixed di 1

010 rappresentazione fixed di 2

011 rappresentazione fixed di 3

3 è il massimo intero positivo rappresentabile.

Rappresentazione di un intero negativo N=-(a_na_n-1.a₀)₂

Si considera |N| espresso in base

si esegue 2^t+1-|N|

si rappresenta il numero ottenuto in t+1 bit.

Il risultato è detto rappresentazione di N complemento a in t+1 bit.

ESEMPIO. t+1=3

Per N=-1, si ha

La rappresentazione di complemento a in bit è

Per N=-2, si ha

La rappresentazione di complemento a in bit è

Per N=-3, si ha

La rappresentazione di complemento a in bit è

Per N=-4, si ha

La rappresentazione di complemento a in bit è

Si osservi che la rappresentazione complemento a in t+1 bit si ottiene:

q       sostituendo con e con nella rappresentazione binaria del valore assoluto del numero (complemento a 1)

q       aggiungendo

oppure:

q       ponendo nella posizione della cifra meno significativa non nulla

q       cambiando con e con nelle successive cifre a sinistra

ESEMPIO

si ha:

q      

q       rappresentazione fixed di

oppure

q      

q      

Il minimo intero rappresentabile correttamente è

100000.00000= 2^t+1- |N| =2^t N=-2^t

Nella rappresentazione fixed di un intero, il bit t+1 è

per gli interi positivi e lo zero

per gli interi negativi.

ESEMPIO. t+1=4

Sono rappresentabili esattamente come numeri fixed point solo gli intero nell'intervallo [-2^t , 2^t -1].

Generalmente alla rappresentazione degli interi sono riservati 4 byte, ossia t+1=32 bit. Pertanto è possibile rappresentare correttamente gli interi tra

Operazioni tra numeri fixed point.

Somma t+1=4

Operandi di segno uguale:

(3)₁₀ 0011 (3)₁₀ 0011

(2)₁₀ 0010 (5)₁₀ 0101

(5)₁₀ 0101 (8)₁₀ 1000 overflow!!

1000 è la rappresentazione di -8

1101 (-5)₁₀ 1011

1110 (-4)₁₀ 1100

(-5)₁₀ 1011 (-9)₁₀ 0111 overflow!!

0111 è la rappresentazione di 7

OVERFLOW intero: sommando due numeri dello stesso segno, si può ottenere un numero che è interpretato cal calcolatore come un numero di segno contrario.

Operandi di segno opposto: è il caso della differenza; viene eseguita sommando al primo numero la rappresentazione complemento a 2 del secondo.

(3)₁₀ 0011 (5)₁₀ 0101

(-2)₁₀ 1110 (-7)₁₀ 1001

(1)₁₀ (-2)₁₀ 1110

a,b>0

=(2^t+1+a-b) troncato a t+1 cifre (se a>b)

fi(a-b)=(a+2^t+1-b) =                        

=(2^t+1-(b-a)) (se a<b)

Non si verifica mai overflow: il risultato è già rappresentato nella forma complemento a 2.

Moltiplicazione : costituita da una combinazione di somme e spostamenti.

0011 (3)₁₀

0100 (4)₁₀=

0000 (12)₁₀

0000

0011

0000

0001100

Divisione: costituita da una combinazione di differenze e spostamenti.

10010 |0101 (18)₁₀ 5)₁₀=(3)₁₀

0101 |11

01000 resto 3

0101

0011 resto

Numeri floating point: permettono di approssimare l'insieme dei numeri reali; in realtà rappresentano esattamente solo un insieme finito di numeri razionali.

Regole di rappresentazione:

q       se a=0 la sua rappresentazione è data da tutti 0;

q       un numero reale a viene rappresentato in base usando la seguente forma scientifica:

a=(-1)^s (a₀ . a₁ a₂ a₃ ..)₂ 2^p            a₀

segno: 1 bit per la rappresentazione di s se a>0 se a<0

mantissa: poiché a₀=1 sempre, si rappresentano le successive t-1 cifre binarie più significative, perdendo le cifre successive (troncamento o arrotondamento), in questo modo si rappresentano t cifre pur avendo a disposizione solo t-1 bit (formato IEEE: t=24

esponente: rappresentazione per traslazione; si hanno un numero predefinito l di bit a disposizione; si possono rappresentare dunque 2^l differenti informazioni; allora in genere:

da a 2^l/2 -1 si rappresentano esponenti negativi da -2^l/2 a -1

2^l/2                 rappresenta l'esponente

da 2^l/2+1 a 2^l-1 si rappresentano esponenti positivi da a 2^l/2-1

ESEMPIO. l=3

Rappresentazione binaria          esponente

per traslazione espresso in base 10

3

2

1

100 0

011 -1

010 -2

-3

-4

(esponente + 4)₂ = rappresentazione dell'esponente

4 (e più in generale 2^l/2), ossia la rappresentazione dell'esponente nullo è il bias da aggiungere all'esponente per ottenere la sua rappresentazione.

Nel formato IEEE, l=8 e bias=

Si rappresentano esattamente gli esponenti che stanno nell'intervallo di interi [

rappresentazione dell'esponente in base 2 in 8 bit=

(esponente + 127)₁₀ = (esponente +01111111)₂

ESEMPI

Rappresentazione dell'esponente 0 = (0 + 127)₁₀             = 01111111

Rappresentazione dell'esponente -126 = (- 126 + 127)₁₀= 00000001

Rappresentazione dell'esponente 127 = ( 127 + 127)₁₀ = 11111110

00000000 e 11111111 sono riservati.

Si noti che per gli esponenti positivi il bit più significativo della loro rappresentazione è 1, mentre per quelli non positivi assume valore 0.

ESEMPIO.

Rappresentazione di (4.25)₁₀ come numero floating point in formato IEEE.

(4.25)₁₀ = (100.01)₂= 1.0001 2¹⁰ 10+01111111=10000001 esponente)

s esponente mantissa (23 bit)

10000001 00010000000000000000000 (4 byte=32 bit)

Non sono rappresentabili:

numeri reali con parte esponente superiore a 2¹²⁷ 10³⁸ (OVERFLOW: il calcolatore si arresta);

numeri reali con parte esponente inferiore a 2^-126 10^-38 (UNDERFLOW: il calcolatore considera il numero come zero e prosegue l'elaborazione).

Il più grande numero reale rappresentabile in valore assoluto è:

3.40 10³⁸

Il più piccolo numero reale vicino allo zero in valore assoluto è:

1.000...00 2^-126= 2^-126 1.18 10^-38

Tuttavia anche in tale intervallo sono rappresentabili esattamente solo i numeri reali aventi al più t cifre binarie come mantissa, ossia solo un insieme FINITO e LIMITATO di numeri razionali finiti.

Tali numeri non sono ugualmente spaziati:

tra successive potenze di 2 sono rappresentati esattamente 2²³ (2^t-1) differenti numeri.

Pertanto i numeri floating point sono più fitti in corrispondenza delle potenze basse di 2 e più radi in corrispondenza delle potenze alte di 2.

È opportuno lavorare sempre con dati opportunamente scalati.

Ogni numero floating point rappresenta se stesso e un intero intervallo di reali.

Pertanto ogni altro numero reale a è approssimato con il numero floating point più vicino, con un errore relativo massimo pari a

2^-(t-1) nel caso di troncamento e 2^-t nel caso di arrotondamento; nel formato IEEE, 2^-23 10^-7 , equivalente a 7 cifre di precisione decimale.

Questo errore è caratteristico del calcolatore con cui si lavora (dipende dalla base e dal numero di bit a disposizione per la rappresentazione della mantissa) ed è detto

PRECISIONE DI MACCHINA.

In pratica è il più piccolo numero che sommato a 1 fornisce un risultato maggiore di 1.

Operazioni tra numeri floating point.

Le operazioni tra numeri reali vengono SIMULATE dall'aritmetica floating point.

Poiché non tutti i reali sono rappresentabili, anche se si usano operandi che appartengono all'insieme dei numeri rappresentabili, non è detto che il risultato sia un numero floating point.

Viene preso come risultato di una operazione il numero floating point più vicino al risultato esatto.

Pertanto ogni operazione è potenzialmente affetta da un ERRORE relativo, che è pari al più alla precisione di macchina ed è detto ERRORE DI ARROTONDAMENTO.

In una sequenza di operazioni floating point (algoritmo), si verifica una PROPAGAZIONE DEGLI ERRORI DI ARROTONDAMENTO, che dipende dall'ordine delle operazioni e dal numero di cifre di precisione.

ESEMPIO. Somma di due numeri finiti (si assume base 10 e 5 cifre per la rappresentazione della mantissa).

Normalizzazione delle mantisse all'esponente massimo;

.76755

Esecuzione della somma delle mantisse

Troncamento o arrotondamento del risultato a 5 cifre decimali

Risultato = .76772 10²

Errore relativo = (.7677134-.76772)/(.7677134)

CONSEGUENZA: nell'aritmetica dei numeri floating point non valgono più le proprietà formali delle operazioni tra numeri reali.

ESEMPIO. Si devono sommare i seguenti numeri binari:

1, .1 2^-10, .1 2^-10 , .1 2^-10, .1 2^-10 (si usa base 2 e 3 bit per la mantissa).

Eseguiamo la somma nell'ordine

1 +

0.001

1.001 1

1 +

0.001

1.001 1

1 +

0.001

1.001 1

1 +

0.001

1.001 1

Risultato finale =1

Errore relativo =(0.333..)₁₀

Eseguiamo la somma in ordine inverso

0.001+

0.001

0.010 1.00 2^-10

0.010+

0.001

0.011 1.10 2^-10

0.011+

0.001

0.100 1.00 2^-1

0.100+

1.000

1.100 1.100 2⁰

Risultato finale =1.1 2⁰ = (1.5)₁₀

Errore relativo = 0

Quando si devono sommare numeri di esponente molto diverso si verifica un errore di incolonnamento.

Non vale la proprietà associativa dell'addizione.

Conviene fare la somma dal numero meno significativo al più significativo per minimizzare l'errore di arrotondamento.

ESEMPIO.

Supponiamo di usare base 10 e 5 cifre per la mantissa.

Supponiamo di dover valutare:

162/485- 129/388 il cui valore esatto è .15464 10^-2.

Nel calcolatore:

Dopo la normalizzazione si ha 0.155?? 10^-2. Il calcolatore introduce 00 al posto di ??. Le ultime due cifre però non hanno significato.

ERRORE RELATIVO = 0.2 10^-2

Si noti che l'errore è dello stesso ordine di grandezza del risultato.

Questo si dice ERRORE DI CANCELLAZIONE e si manifesta quando si devono sottrarre due numeri simili tra loro, precedentemente affetti da errore.

OPERATORI LOGICI E ALGEBRA DI BOOLE

L'algebra di Boole è basata su tre operazioni logiche o booleane che si applicano a operandi che possono assumere due soli valori:

vero (rappresentato con 1);

falso (rappresentato con 0).

Un solo bit basta a rappresentare un operando di una espressione booleana.

Il risultato di una operazione booleana è determinato tramite le cosiddette TAVOLE DI VERITA', che forniscono il valore ottenuto in funzione di tutte le possibili combinazioni dei valori assunti dagli operandi.

OPERAZIONI A DUE OPERANDI

Somma booleana

Prodotto booleano

OPERAZIONE A UN OPERANDO

Complementazione logica o negazione

ESEMPIO

Tavola di verità di una espressione booleana a tre ingressi

Come nelle espressioni numeriche si eseguono prima i prodotti (AND), poi le somme (OR), a meno che non siano specificate parentesi.

Questa espressione booleana è detta anche OR ESCLUSIVO.

PORTE LOGICHE

Gli elementi circuitali che corrispondono agli operatori logici di base prendono il nome di PORTE LOGICHE.

Le porte AND e OR hanno due operandi di tipo binario in ingresso e uno in uscita. La porta NOT ha un solo operando in ingresso e 1 in uscita.

AND                               OR NOT

Altre porte diffuse sono NAND (NOT (. AND.)) e NOR (NOT (. OR .)).

Ogni funzione logica può essere generata come combinazione di tali porte logiche; il circuito che realizza la funzione è una RETE LOGICA ed è una combinazione di porte logiche fondamentali.

CODICI

Un codice è un insieme di simboli per rappresentare una informazione di qualsiasi genere (parole, numeri caratteri,...)

Codice binario è un codice che utilizza come simboli le cifre binarie 0 e 1.

Con N cifre binarie è possibile codificare 2^N oggetti distinti.

Per codificare M oggetti distinti, il minimo numeri di cifre binarie necessarie è il primo intero tale che:

N log₂M

CODIFICA DEI CARATTERI

I caratteri di un testo vengono codificati in sequenze di bit, usando un codice di traduzione.

Il codice più usato è il codice ASCII (American Standard Code for Information Interchange); esso utilizza 7 bit e consente di rappresentare 128 caratteri.

Esistono versioni del codice che utilizzano un ottavo bit e consentono di rappresentare altri 128 caratteri.

I caratteri si dividono in tre classi:

caratteri di comando (codici di trasmissione o controllo, per es. ESC, CTRL,.)

caratteri alfanumerici:

maiuscole A B C . Z con codici da 65 a 90

minuscole a b c .z                con codici da 97 a 122

cifre 0 1 2 .9                         con codici da 48 a 57

caratteri speciali ();.,: spazio; lo spazio ha codice 32

Ogni carattere occupa un byte; l'ottavo bit è usato per estendere il codice (con caratteri grafici o lettere greche o lettere accentate.) o nella trasmissione dati come bit di parità per segnalare errori.

Altri codici :

EBCDIC (Extended Binary Coded Decimal Interchange Code) a 8 bit per elaboratori IBM.

BCD (Binary Code Decimal)          a 4 bit: è un codice per la rappresentazione dei numeri. Ciascun numero viene suddiviso nelle cifre decimali che lo compongono e ogni cifra viene codificata separatamente dalle altre; poichè ci sono 10 differenti cifre servono 4 bit.

Esempio. (721)₁₀=(0111 0010 0001)_BCD.