FONDAMENTI DI INFORMATICA I - Considerazione sulla codifica dell'informazione

Numeri decimali e operazioni aritmetiche: siamo abituati ad usare tutte le cifre necessarie senza particolari limiti.

Esempio 2

Informazioni da rappresentare: parole della lingua italiana

alfabeto: 21 lettere

lunghezza delle parole non limitata (si può ipotizzare un limite ragionevole Hp: L_max=26)

alcune sequenze di lettere non hanno significato

Vocabolario italiano

numero di parole esistenti è << 21²⁶

non sono esaurite tutte le sequenze possibili (configurazioni) di lettere

l'introduzione di nuove parole non richiede di aumentare la lunghezza e/o di aumentare il numero di simboli

Codifica dell'informazione

Le informazioni che consideriamo devono essere rappresentate e elaborate da una macchina (calcolatore elettronico).

Aspetto fondamentale:

il numero di elementi "fisici" (elementi di memoria, collegamenti ....) disponibile per contenere la rappresentazione di ogni informazione è finito.

Poiché ogni elemento fisico "contiene" il valore di una cifra binaria, in ogni componente di un calcolatore il numero di cifre binarie disponibili per rappresentare l'informazione è finito. Quindi il numero di informazioni distinte rappresentabili è finito.

Nasce quindi il concetto di non rappresentabilità di informazioni che richiedono un numero di cifre maggiore di quelle disponibili.

Sistema elettronico digitale

Calcolatore:

sistema elettronico costituito da circuiti digitali

In un sistema digitale le informazioni vengono rappresentate, elaborate e trasmesse mediante grandezze fisiche (segnali) che si considerano assumere solo valori discreti. Ogni valore è associato a una cifra (digit) della rappresentazione.

Al contrario, in un sistema analogico le informazioni vengono rappresentate (elaborate e trasmesse) mediante grandezze che possono assumere con continuità tutti gli infiniti valori in un dato intervallo.

Grandezze fisiche utilizzate in un sistema digitale per la rappresentazione dell'informazione:

segnali elettrici (tensione, corrente)

grandezze di tipo magnetico (stato di magnetizzazione)

segnali ottici

Il comportamento fisico dei sistemi di elaborazione riproduce le operazioni di elaborazione e trasmissione delle informazioni rappresentate con le grandezze fisiche (segnali). Si ha quindi una corrispondenza biunivoca tra le operazioni sulle informazioni e le trasformazioni fisiche (operate dai circuiti) sui segnali che le rappresentano.

Rappresentazione delle informazioni con segnali digitali binari

La grandezza fisica che si utilizza (segnale elettrico di tensione) assume solo due valori discreti (binaria)

L'elemento tecnologico base per la realizzazione di circuiti digitali è il transistore il cui funzionamento può essere modellato (in modo molto semplice) come il funzionamento di un interruttore (aperto o chiuso), quindi con due stati fisici, cui corrispondono 2 opportune tensioni (in genere 0V e 5V)..

BIT (binary digit) = cifra binaria. (unità di informazione elementare)

Un bit può assumere due valori che possono essere associati ai simboli:

Terminologia e "unità di misura"

Rappresentazione binaria

Nella rappresentazione binaria l'alfabeto (l'insieme dei simboli utilizzabili) è costituito dalle cifre 0 e 1.

Un'informazione è rappresentabile da una sequenza di cifre.

Quante sono le informazioni distinte rappresentabili?

se sono disponibili N cifre binarie si possono avere 2^N configurazioni diverse e quindi rappresentare al più 2^N informazioni distinte

se si devono rappresentare M informazioni distinte sono necessarie N = log₂M cifre binarie

Quindi a seconda della cardinalità (M) dell'insieme di valori dell'inform 252j94c azione da rappresentare con una certa variabile, quest'ultima dovrà essere basata su un opportuno numero (N) di bit come indicato dalla relazione precedente.

Rappresentazione di valori numerici

Le classi di valori numerici che si possono rappresentare sono le seguenti:

Numeri naturali

Numeri interi (relativi)

Numeri razionali

Rappresentazione di numeri naturali:

codifica pesata (binario naturale)

La codifica si basa sulla notazione posizionale o "pesata" che adottiamo usualmente per i numeri codificati in decimale.

Terminologia:

Base:   B (B=2, B=10, B=3, B=16)

Valori delle cifre: 0 .. B-1

Notazione posizionale: B^k (2^k, 10^k)

Nella notazione posizionale, in qualunque base, il valore numerico rappresentato da una cifra dipende

dal valore della cifra

dalla posizione della cifra nel numero

Esempio in base 10

P₁₀= 121₁₀ = 1

Data una base B e un numero di cifre disponibili N

i numeri naturali (interi 0) rappresentabili sono

P B^N-1

Codifica pesata dei numeri naturali

in base 2

P₂= b_N-1 2^N-1+ b_N-2 2^N-2+......+ b₂ 2²+ b₁ 2¹+ b₀ 2⁰

bit più significativo:   b_N-1

bit meno significativo:    b₀

Ad esempio:

numero di bit disponibili N=3

i valori numerici rappresentabili sono

P cioè 0 P

Codifica pesata dei numeri naturali in base 2

numero di bit disponibili N=5 i valori numerici P rappresentabili sono 0 P cioè 0 P

gli zeri davanti "non contano" ma ci devono essere.

Siamo abituati a non scrivere gli zeri non significativi, lasciandoli impliciti.

Invece i segnali fisici possono solo indicare i valori 0 o 1 per tutti i bit usati per rappresentare un valore numerico, e non possono "sparire".

Per una certa informazione si adotta un numero fisso di bit, che deve essere stabilito a priori, e non una quantità che dipende dal valore di volta in volta rappresentato.

N=6 0 - 63

N=7 0 - 127

N=8 0 - 255

N=10  0 - 1023 (1 K)

N=16  0 - 2⁶ 0 - 64.000 (64 K)

N=32  0 - 2² 0 - 4.000.000.000 (4 G)

Conversione della rappresentazione pesata

Conversione =

passaggio dalla rappresentazione pesata di un numero naturale da una base b ad una base B.

Le regole di conversione si basano:

sull'uguaglianza dei valori numerici, cioè indipendentemente dalla base di rappresentazione il valore del numero è lo stesso

sul concetto di notazione pesata

Consideriamo i casi di conversione da binario a decimale e da decimale a binario di numeri naturali

Conversione binario decimale (numeri naturali): è molto semplice

P₂=11110₂  =

= 16 + 8 + 4 + 2 + 0 = 30₁₀

Conversione decimale binario

di numeri naturali

Algoritmo di conversione:

si considera l'uguaglianza P = Q b + R, dove

P è il numero decimale da convertire

Q è il risultato della divisione intera per la base
b (=2)

R è il resto della divisione intera per la base b
(0 R b-1)

si eseguono ripetute divisioni per la base b = 2 operando in base B = 10.
Le divisioni considerano come valore da dividere, di volta in volta, il Q ottenuto al passo precedente. Il procedimento termina quando il valore da dividere è pari a 0.

Il numero di iterazioni necessarie per arrivare al termine del procedimento determina il numero minimo di bit necessari per rappresentare quel particolare numero in binario.

Conversione decimale binario

di numeri naturali

Esempio: 37 in base 2.

Valgono le seguenti uguaglianze:

P=Q₀b+R₀ = (Q₁b+R₁)b+R₀ = Q₁b²+R₁b¹+R₀b⁰=.....

Quindi R₀ R₁.... sono le cifre della rappresentazione binaria a partire dal bit meno significativo.

Nell'esempio, il numero minimo di bit è 6.

R₅ rappresenta il bit più significativo.

Continuando il procedimento si otterrebbero degli 0 in posizione più significativa.

Conversione decimale binario

della parte frazionaria

Rappresentazione della parte frazionaria:

P = 0.p_-1p_-2p_-3

Nella notazione posizionale per la parte frazionaria il valore del numero rappresentato è dato da:

P₁₀  =0 + d_-1 10^-1+d_-2 10^-2+......(d_-1 ... cifre decimali)

P₂ =0 + b_-1 2^-1+b_-2 2^-2 +b_-3 2^-3 + ...(b_-1 ... cifre binarie)

La conversione da binario a decimale è come quella vista per i numeri naturali, ma con le potenze della base negative.

Per la conversione da decimale a binario l'algoritmo di conversione è "duale" rispetto a quello per la parte intera. In questo caso si opera per moltiplicazioni successive (per la base 2) della sola parte frazionaria.

Le cifre (bit) ottenute sono quelle dei riporti sulle unità intere.

Conversione della parte frazionaria

Esempi e osservazioni sulla conversione:

Esempio 1

il valore è esattamente rappresentabile in base 2 con un qualsiasi numero ( 1) di bit per la parte frazionaria.

Esempio 2

il valore è esattamente rappresentabile in base 2 con un qualsiasi numero ( 2) di bit per la parte frazionaria.

Conversione della parte frazionaria

Esempi e osservazioni sulla conversione:

è rappresentabile esattamente con 4 (o più) bit per la parte frazionaria.

Se si hanno a disposizione solo 3 bit, la conversione genera il valore approssimato 0.101₂ (=0.625₁₀).

non è rappresentabile esattamente ed è periodico (numero illimitato di cifre).

E' molto importante notare che il valore frazionario decimale 0.1 molto frequente nella normale numerazione decimale, non è rappresentabile esattamente in forma binaria. Ciò comporta talvolta risultati approssimati in calcoli eseguiti in base 2, che invece darebbero un risultato esatto in base 10.

Operazioni aritmetiche tra naturali

in notazione posizionale

Le operazioni aritmetiche in base 2 seguono le stesse "regole" di quelle in base 10.

E' fondamentale ricordarsi del problema della rappresentabilità dell'informazione con un numero di bit predefinito.

Ad esempio, nel caso di addizione di due interi rappresentati su N bit, il risultato della somma può richiedere N+1 bit (overflow = traboccamento, o superamento).

I circuiti per eseguire le operazioni aritmetiche in notazione posizionale sono molto semplici.
Notevole vantaggio della codifica posizionale.

Esempio tabella della somma su un bit (come nel decimale esiste il riporto verso la cifra più significativa)

Operazioni aritmetiche: esempi

Somma: N = 4 bit valori rappresentabili da 0 a 15

Sottrazione: N = 4 bit valori rappresentabili da 0 a 15

Codifica ottale

E' la codifica pesata dei numeri naturali in base B=8, sono quindi disponibili 8 valori delle cifre.

Il generico valore in ottale si ottiene dalla relazione (dove N rappresenta il numero di cifre ottali):

P₈=b_N-1 8^N-1+b_N-2 8^N-2+......+b₂ 8²+b₁ 8¹+b₀ 8⁰

Codifica esadecimale (HEX)

E' la codifica pesata dei numeri naturali in base B=16, sono quindi disponibili 16 valori delle cifre.

Il generico valore in esadecimale si ottiene dalla relazione (dove N rappresenta il numero di cifre esadecimali):

P₁₆=b_N-1 16^N-1+b_N-2 16^N-2+......+b₂ 16²+b₁ 16¹+b₀ 16⁰

Nella documentazione tecnica di calcolatori ed in generale di circuiti logici occorre spesso citare delle configurazioni binarie (codifiche, indirizzi, ecc.).

Sequenze di 16 o 32 bit rappresentati con "1" e "0" sono, per l'uomo, scomode da gestire e difficili da ricordare.

Si ricorre quindi generalmente alla rappresentazione esadecimale (HEX). In particolare la forma HEX è usata nel linguaggio Assembler.

Rappresentazione dei numeri interi (relativi): Codifica in modulo e segno

Il primo bit (più significativo, cioè il più a sinistra) viene utilizzato come bit di segno:

numero positivo

numero negativo

Possono essere rappresentati solo gli interi compresi tra -(2^N-1-1) e (2^N-1-1). Infatti solo N-1 bit sono disponibili per il modulo.

Nota: 000 +0

100 -0

Rappresentazione dei numeri interi (relativi): Codifica in complemento a 2

All'interno del calcolatore si utilizza una diversa rappresentazione in complemento a 2 dei numeri interi relativi che consente di trattare somme e sottrazioni algebriche in modo indifferenziato e quindi è realizzabile con circuiti aritmetici più semplici.

Rappresentazione in complemento a 2

Date N cifre binarie, sono disponibili 2^N configurazioni distinte: di queste

2^N-1 vengono utilizzate per rappresentare valori e

2^N-1 vengono utilizzate per rappresentare valori < 0.

Ad esempio, se N = 4 sono disponibili 16 configurazioni distinte, con queste posso rappresentare

valori da 0 a 2^N-1-1 cioè da 0 a 7

valori < 0: da -1 a - 2^N-1 cioè da -1 a -8

N=6 da -32 a +31

N=7 da -64 a +63

N=8 da -128 a +127

N=10    da -512 a + 511

N=16    da 32.768 a +32.767

N=32    da - 2.000.000.000 a

Rappresentazione in complemento a 2

Codifica su 4 bit

			+1

Rappresentazione in complemento a 2

Regola di conversione

Si scrive il valore assoluto del numero da rappresentare in notazione posizionale su N cifre

se il numero da rappresentare è 0, questa è la rappresentazione in complemento a 2

se il numero da rappresentare è < 0, si complementano tutti i bit e si somma 1

In alternativa, partendo dal bit meno significativo, si lasciano inalterati i valori dei bit fino al primo 1 incluso e si complementano i rimanenti bit

Esempio su 4 bit.

P = - 6   6₁₀ = 0110₂

complemento i bit 1001

sommo 1 1010

- 6₁₀ = 1010_cpl2

Esempi di operazioni aritmetiche tra relativi in complemento a 2

^

| Bit di CARRY

Puo' esserci oppure no, come puo' esserci

o no il bit di overflow.

Codifica di numeri razionali:

Rappresentazione in virgola mobile

(floating point)

Il valore di un numero razionale R è esprimibile con la seguente forma generale per qualunque base b

R = M . b ^E

R - valore razionale

M - mantissa frazionaria con segno

b - base

E - esponente intero con segno

Quindi, data una base b, un numero rappresentato in virgola mobile può avere la forma

Dove M è la rappresentazione della mantissa nella base b e con un certo numero di cifre, ed E è la rappresentazione, anche questa nella base b, dell'esponente da dare alla base.

Il campo di valori rappresentabili dipende da E

la risoluzione (precisione) dipende da M

La rappresentazione si dice normalizzata se la mantissa ha un valore compreso tra l'inverso della base e l'unità, cioè

b^-1 M < b⁰

Codifica di numeri razionali:

Rappresentazione in virgola mobile

(floating point)

Base 10

Es. 1250.3 = 0.12503 . 10 ⁴ normalizzato

= 0.0012503 . 10 ⁶ non normalizzato

Per sfruttare al meglio le cifre di mantissa si normalizza

Base b = 2

Es. 1011010.011 = 0.101101001100 . b

In questo esempio, puramente indicativo, la mantissa è di 12 bit e l'esponente di 4 bit.

Codifica di numeri razionali:

rappresentazione in virgola mobile

Standard IEEE floating point su 32 bit

bit di segno della mantissa

bit di esponente E

23 bit di mantissa M (pari a 7 cifre decimali)

Campo di valori rappresentabili
~ -10 ³⁸ . . ~-10 ^-38 0 ~10 ^-38 . . ~10 ³⁸

Risoluzione uno su 8 milioni

NB. I circa 4 miliardi di configurazioni dei 32 bit usati consentono di coprire un campo di valori molto ampio grazie alla distribuzione non uniforme.

Infatti per numeri molto piccoli i valori sono "fitti", ma si vanno "diradando" per i numeri via via più grandi.

Approssimativamente gli intervalli tra valori contigui sono:

per valori di 10000 l'intervallo è di un millesimo

per valori di 10 milioni l'intervallo è di un'unità

per valori di 10 miliardi l'intervallo è di mille

ecc.

Ci sono anche standard IEEE su 64 e su 80 bit che estendono il campo di valori rappresentabili e la precisione.

Informazioni enumerative: caratteri alfanumerici

I caratteri alfanumerici consentono all'uomo di rappresentare tutte le informazioni "scrivibili" (con qualche difficoltà, anche immagini, suoni, sensazioni, ecc.). Si tratta quindi di una codifica molto importante ed utilizzata.

Si devono rappresentare:

lettere maiuscole/minuscole    A a .. Z z

spazio

cifre     0 .... 9

segni di interpunzione , : ; .

simboli   ! " # % @ ) < =

caratteri di controllo per gestire la visualizzazione, la stampa, la trasmissione dei caratteri (inizio riga, salto di riga, salto pagina

La rappresentazione dei caratteri alfanumerici fa uso di una codifica standard universalmente accettata: codifica ASCII (American Standard Code for Information Interchange)

Codifica ASCII: caratteristiche

7 bit per rappresentare ogni carattere

128 caratteri alfanumerici distinti: le possibili configurazioni vanno da 0000000 a 1111111

la codifica è stata scelta in modo da rispettare alcune "proprietà" dei caratteri:

ordinamento delle cifre

ordinamento delle lettere

introduce le seguenti ulteriori proprietà:

le lettere maiuscole precedono tutte le lettere minuscole

la "distanza" tra una lettera maiuscola e la sua corrispondente minuscola è la stessa per tutte le lettere

ASCII esteso (8 bit) 256 configurazioni:

le prime 128 (da 00000000 a 01111111) sono associate ai caratteri dell'ASCII Standard, le rimanenti 128 (da 10000000 a 11111111) sono associate a lettere accentate..., a caratteri semigrafici ...

Tabella ASCII

bit meno

significativi

bit più significativi

N.B.

I valori numerici in piccolo sono il valore decimale corrispondente al codice ASCII

La codifica ASCII di un carattere nella tabella è ottenuta prendendo i 3 bit corrispondenti alla colonna, seguiti dai 4 bit corrispondenti alla riga (questi gruppi di bit sono anche facilmente associabili a cifre esadecimali - v.seguito).

Il registro di stato PSR

e i codici di condizione

Il registro di stato contiene alcune informazioni sull'effetto dell'esecuzione di un'istruzione che possono venire analizzate con successive istruzioni.

Una parte del contenuto del registro e' costituita da 4 bit, detti codici di condizione, e indicati con le lettere:

Z (zero), N (negativo), C (carry, riporto) e V (overflow)

PSR

Dopo l'esecuzione di un istruzione i bit del registro contengono un valore che dipende dal risultato dell'istruzione stessa.

Ad es dopo una addizione:

Z vale 1 solo se il risultato dell'addizione e' 0

N vale 1 solo se il risultato dell'addizione e' negativo

C vale 1 solo se l'addizione ha provocato un riporto

V vale 1 solo se l'addizione ha dato luogo ad

overflow, cioe' la somma di due positivi risulta un

numero negativo, oppure la somma di due negativi

risulta un numero positivo