Rappresentazione e
Memorizzazione dei Dati
Giuseppe Nicosia
CdL in Matematica (Laurea Triennale)
Facoltà di Scienze MM.FF.NN.
Università di Catania
Bit e loro Memorizzazione
Definizioni
•
•
•
•
Algoritmo:
Algoritmo una sequenza finita ordinata di passi non
ambigui ed eseguibili che definiscono un'attività di
lunghezza finita.
Programmi:
Programmi la rappresentazione di un algoritmo
compatibile con la macchina.
Software:
Software i programmi, e gli algoritmi che
rappresentano (es. sistemi operativi).
Hardware:
Hardware dispositivi fisici.
Lo sviluppo di algoritmi è quindi un obiettivo
fondamentale dell’informatica.
Individuare un algoritmo per risolvere il
problema equivale a risolvere il problema stesso.
stesso
Operazioni Booleane
George Boole (1815-1864)
•
•
I computer rappresentano le informazioni
come sequenze di bit (binary digit o cifra
binaria o unità binaria).
Operazioni Booleane:
–
–
–
–
•
AND;
OR;
XOR (eXclusive OR, OR esclusivo);
NOT.
Un dispositivo che, dati i valori di ingresso,
produce l’uscita di un’operazione booleana è
chiamato porta logica.
Operazioni Booleane
1. P AND Q => è vera solo quando P e Q sono
vere (dove P e Q rappresentano asserzioni, ad
esempio “Questa è una frase.”);
2. P OR Q => è vera quando almeno una delle due
è vera;
3. P XOR Q => è vera quando uno dei due è vera e
l’altro è falsa (“o P oppure Q ma non
entrambi”);
4. NOT P => assume il valore di verità opposto a P.
Operazioni Booleane (2/2)
Rappresentazioni delle Porte Logiche
AND e OR
Rappresentazioni delle Porte Logiche
XOR e NOT
Un semplice Circuito flip-flop
L ' i m p u l s o
t e m p o r a n e o
sull'ingresso
superiore ha portato
il flip-flop a 1, e
questo valore resterà
tale anche dopo che
l'ingresso superiore
sarà riportato a 0.
Esempio (1/3)
Esempio (2/3)
Esempio (3/3)
–
Analogamente, se si
porta temporaneamente
a 1 l'ingresso inferiore,
si forza l'uscita del flipflop a diventare 0 e a
rimanere tale anche
dopo che il valore
dell'ingresso
inferiore
sarà riportato a 0.
Memorizzazione di bit.
–
Un altro modo di costruire un flip-flop
Rappresentazione delle
Informazioni su di un
calcolatore
Rappresentazione delle Informazioni
• L’informazione viene rappresentata
mediante sequenze di bit.
• Ogni parola, o testo, o dato numerico,
o immagine, o suono viene codificato
come configurazioni di bit.
Rappresentazione dei Valori Numerici (1/2)
• La notazione binaria è un modo di
rappresentare i valori numerici usando solo le
cifre 0 e 1, anziché tutte le cifre del sistema
decimale.
• Attraverso 1 bit è possibile rappresentare due
informazioni (una con 0 ed una con 1).
• Utilizzando una sequenza di 2 bit possiamo
avere quattro codifiche distinte.
• Analogamente, utilizzando 3 bit possiamo
rappresentare otto informazioni differenti.
Rappresentazione dei Valori
Numerici (2/2)
• Riassumendo:
– 1 bit => 2=21 informazioni;
– 2 bit => 4=22 informazioni;
– 3 bit => 8=23 informazioni;
In generale:
– N bit => 2N informazioni.
• Esempio:
Esempio
Per rappresentare 57 informazioni è
necessario utilizzare una sequenza di 6 bit.
Rappresentazione Binaria (1/2)
Nel sistema di numerazione
binario i numeri vengono
codificati usando le due
cifre “1” e “0” ed uno
schema posizionale in cui
si usa la base 2 al posto
della base 10.
10
Utilizzando questa codifica
è possibile rappresentare
qualunque numero intero
positivo.
Decoding the binary
representation 100101
0
Rappresentazione Binaria (2/2)
Considerato il numerale:
cn cn-1 … c1 c0
in cui ogni “ci” è la cifra “0” o “1”,
rappresenterà il numero:
c0*20 + c1*21 + … + cn-1*2n-1 + cn*2n
Decodifica di rappresentazioni Binarie
Esempi:
Il numerale “1011” denota il numero:
1*20 + 1*21 + 0*22 + 1*23 = 1110
il numerale “100101” denota il numero:
1*20 + 0*21 + 1*22 + 0*23 + 0*24 + 1*25 = 3710
il numerale “1010001” denota il numero:
1*20 + 0*21 + 0*22 + 0*23 + 1*24 + 0*25 + 1*26 = 8110
Conversione dalla base 10 alla base 2
Bisogna dividere la base 10 per 2 fino a quando il
quoziente intero della divisione è zero.
Esempio: consideriamo il
numerale
34510
e
cerchiamo
la
rappresentazione
binaria
corrispondente:
Leggendo i resti dal basso
verso l’alto si ha la
rappresentazione binaria
del numero 34510 .
345/2
= 172
resto 1
172/2
= 86
resto 0
86/2
= 43
resto 0
43/2
= 21
resto 1
21/2
= 10
resto 1
10/2
= 5
resto 0
5/2
= 2
resto 1
2/2
= 1
resto 0
1/2
= 0
resto 1
Un Algoritmo per trovare la
rappresentazione binaria di un
intero positivo
Operazioni sui numeri binari
• Lo stesso procedimento che utilizziamo per
i numeri decimale può essere utilizzato per
le operazioni di somma in base due.
• L’unica differenza è che si devono
effettuare i riporti quando la somma supera
il valore “1”.
• Regole di base:
Esempi di Somma Binaria
5+
3=
8
0101 +
0011 =
1000
25 +
21 =
46
011001 +
010101 =
101110
117 +
109 =
226
01110101 +
01101101 =
11100010
Esercizi sul Sistema Binario
• Convertire le seguenti rappresentazioni binarie
nel formato in base 10 equivalente:
a.101010, b. 100001, c. 10111, d. 0110, e. 11111
• Convertire le seguenti rappresentazioni in base
dieci nel formato binario equivalente:
a. 32, b. 64, c. 96, d. 15, e. 27
• Eseguire le seguenti somme in binario:
a.32 + 27, b. 96 +15, c. 64 + 11
Complemento a due
Complemento a due
+3 = 00000011
+2 = 00000010
+1 = 00000001
+0 = 00000000
-1 = 11111111
-2 = 11111110
-3 = 11111101
Notazione in Complemento a Due
•
•
Complemento a due viene utilizzato per rappresentare
ogni intero positivo e negativo.
Regole:
Regole
–
–
Il bit più significativo (più a sinistra) rappresenta il segno del
numero: “0” positivo, “1” negativo;
La rappresentazione di un numero negativo si ottiene in tre
passi:
•
•
•
Si rappresenta in complemento a due il numero positivo con lo stesso
valore assoluto del numero negativo da codificare;
Si invertono tutti i bit in tale rappresentazione, cioè si mette “1” dove
c’e’ “0” e viceversa;
Si somma 1 al LSB del risultato ottenuto al passo precedente.
Esempio di Notazione in Complemento a Due:
da +5 a -5
Supponiamo di voler codificare in forma
binaria il numero “-5”:
1) La rappresentazione in complemento a
due del numero “+5” è 0101;
2) Invertendo tutti i bit si ottiene: 1010;
3) Sommando “1” si ottiene 1011,
rappresentazione in complemento a
due di “-5”.
Notazione in Complemento a Due
• Per effettuare la conversione inversa, si procede
come segue:
– Se il primo bit è “0” il numero è positivo;
– Altrimenti:
• Si ignora il primo bit;
• Si invertono i restanti bit;
• Si somma “1” al numero ottenuto al passo precedente per
ottenere il valore assoluto del numero negativo.
Esempio di Notazione in
Complemento a Due: da -5 a +5
Consideriamo il numero binario
complemento a due 1011= -5.
1. Si esclude il primo bit (011);
2. Invertendo si ottiene: 100;
3. 1002 = 410;
4. 4 + 1 = 5.
Risultato finale “5”.
in
Sistema di Notazione in
Complemento a Due
Caso speciale 1
0=
00000000
Bitwise not
11111111
Add 1 to LSB
+1
Result
1 00000000
Overflow is ignored, so:
-0=0
Caso speciale 2
-128 =
10000000
bitwise not 01111111
Add 1 to LSB
+1
Result
10000000
So:
-(-128) = -128 !
Monitor MSB (sign bit)
It should change during negation
Somma Binaria con Notazione in
Complemento a Due (1/2)
+2
-5 =
-3
0010 +
1011 =
1101
+7
-5 =
+2
0111 +
1011 =
10010
Problema di overflow
Il problema della sottrazione è uguale al problema dell’addizione.
Il problema “7 - 5” equivale al problema “7 + (-5)”.
Somma Binaria con Notazione in
Complemento a Due (2/2)
Esercizi sul Sistema Binario con
Notazione in Complemento a Due
• Convertire le seguenti rappresentazioni in
complemento a due:
a.00011, b.01111, c.11100, d.11010, e.00000, f.10000
• Convertire le seguenti rappresentazioni in base
dieci:
a. 6, b.-6, c.-17, d.13, e.-1
• Eseguire le seguenti somme:
a.0101 + 0010, b. 1110 + 0011, c. 1010 + 1110
Rappresentazione in Notazione
Esadecimale di numeri positivi
Notazione Esadecimale (1/3)
• Le sequenze di lunghe stringhe di bit
(flussi di bit) sono facilmente soggette ad
errori.
• La notazione esadecimale si basa sul fatto
che le configurazioni di bit hanno
lunghezza multipla di quattro.
• La notazione esadecimale impiega un
unico simbolo per esprimere quattro bit.
Notazione Esadecimale (2/3)
Notazione Esadecimale (3/3)
Esempi:
• 10110101
=>
1010010011001000 =>
B5
A4C8
Esercizi:
Utilizzare la notazione esadecimale per rappresentare le
seguenti configurazioni di bit: 0110101011110010 –
111010000101010100010111 – 01001000
Quali configurazioni di bit sono rappresentate dalle
seguenti configurazioni esadecimali: 5FD97 – 610A –
ABCD – 0100
Problema dell’Overflow
• Il problema dell’overflow si presenta
quando il valore da rappresentare è esterno
all’intervallo di valori che possono essere
rappresentati.
• Es. 5 + 4 = 9 utilizzando 4 bit.
• Con la notazione in complemento a due, si
ottiene sommando due valori positivi o due
negativi.
• Oggi si utilizzano configurazioni di 32 bit
(2.147.483.647) per memorizzare i valori.
Rappresentazione del Testo (1/4)
•
•
•
•
In un calcolatore, un testo viene presentato come una lunga
stringa (sequenza) di bit.
Il metodo di codifica più utilizzato è il codice ASCII
(American Standard Code for Information Interchange).
nterchange
L’insieme dei simboli comunemente usati
può essere
codificato usando 7 bit,
bit che permettono la rappresentazione
di 27=128 configurazioni differenti (76 conf. nel codice
originario)
Oggi si usa il formato esteso a 8 bit:
– Vantaggi: un codice che si adatta perfettamente alle celle
di memoria, altre 128 configurazioni da usare per
includere altre informazioni non usate nel codice ASCII
iniziale
– Svantaggi: queste 128 configurazioni vengono interpretate
in modo diverso dai diversi produttori SW/HW, ovvero
problemi di compatibilità.
Rappresentazione del Testo (2/4)
• Sebbene 7 bit siano sufficienti per codificare
l’insieme dei caratteri, oggi il codice ASCII
standard usa 8 bit.
bit
Rappresentazione del Testo (3/4)
Esempio: sia data la seguente sequenza:
011010010110110000000000011100000110111100101110
Il testo che essa codifica può essere ottenuto, dividendo la
sequenza in gruppi di 8 bit e assegnare ad ogni gruppo il
corrispondente carattere nella tabella ASCII.
ASCII
01101001
i
01101100
l
00000000
01110000
p
01101111
o
00101110
.
Rappresentazione del Testo (4/4)
Esempio: siano dati i numeri 2 e 5, la
codifica nella tabella ASCII è:
2 = 00110010, 5 = 00110101
il risultato che si ottiene dalla somma è:
00110010
00110101
01100111
“g”
Rappresentazione del testo:
Unicode e ISO
• Codice Unicode: usa una codifica univoca di
16 bit (65536 configurazioni), quanto basta a
rappresentare i simboli più comuni cinesi e
giapponesi.
• Codice ISO: 32 bit, in potenza miliardi di
simboli.
Rappresentazione delle Immagini (1/3)
•
•
Le tecniche più diffuse per rappresentare le
immagini vengono classificate in due categorie:
tecniche bitmap e tecniche vettoriali.
L’immagine viene considerata come una matrice di
punti. Ogni punto è detto pixel (picture element)
element ed
assume il valore di “0” o “1” per un’immagine
B/W.
Si usa la convenzione che i pixel siano ordinati dal basso
verso l’alto e da sinistra verso destra.
destra
•
Nelle immagini a colori ogni pixel può essere
rappresentato da una combinazione di bit, che
indicano il colore corrispondente.
Rappresentazione delle Immagini (2/3)
•
•
Il colore di ogni pixel viene registrato secondo tre
componenti: rosso,
rosso verde e blue (ogni componente un
byte)
Risoluzione:
Risoluzione indica la precisione con cui viene
effettuata la suddivisione di un’immagine in pixel (es.
una griglia di 640x480 pixel).
Domanda:
Domanda quanti bit servono per rappresentare 256
colori, per ciascun pixel? 8 bit => 28 = 256
La rappresentazione di un’immagine mediante la
codifica dei pixel richiede una quantità notevole di
spazio di memoria (es. 8 bit per pixel con risoluzione
640x480 => 307200 x 8 bit => 2457600).
2457600)
Rappresentazione delle Immagini (3/3)
•
•
Svantaggio tecniche bitmap: difficilmente una immagine può essere
convertita in una dimensione qualsiasi.
Le tecniche vettoriali consentono di risolvere il problema della
scalatura:
l'immagine è rappresentata da un insieme di linee e curve.
Tale rappresentazione mantiene i dettagli relativi al modo in cui
le linee e le curve sono tracciate dal dispositivo.
Font scalabili: i vari font (tipi di caratteri) disponibili sulle
stampanti e sui monitor sono codificati con tecniche vettoriali.
Esempi: True type (Microsoft e Apple) simboli mediante
formule matematiche; Postscript (Adobe Systems) caratteri e
dati grafici più generali; CAD (computer aid design).
Le tecniche vettoriali non sono in grado di produrre immagini di
qualità fotografica, ecco perchè nelle videocamere digitali di oggi
sono utilizzate tecniche bitmap.
–
–
–
–
•
Rappresentazione dei suoni
•
•
Metodo generico: campionare l'ampiezza dell'onda sonora a
intervalli regolari e nel registrare le serie di valori numerici ottenuti.
Frequenza di campionamento di 8000 campioni al secondo.
3
Rappresentazione dei suoni
•
•
•
Gli attuali CD musicali sono realizzati con una frequenza di
campionamento di 44.100 campioni al secondo. Ogni campione è
rappresentato con 16 bit (32 bit per le registrazioni stereo).
Segue, che ogni secondo di musica registrata in stereo richiede più
di un milione di bit.
Sistema di codifica alternativo, più economico, MIDI (Musical
Instrument Digital Interface)
MIDI codifica lo strumento che deve eseguire una determinata
nota per un certo periodo.
Questo implica che una registrazione MIDI possa risultare
molto diversa se eseguita su sintetizzatori differenti.
Codifica meno costosa in termini di bit.
–
–
–
Memorizzazione dei Dati
La Memoria Principale
Organizzazione della Memoria (1/4)
• Un qualunque calcolatore è costituito da un
numero elevato di circuiti flip-flop, in grado
di memorizzare un bit.
• Sono organizzati in unità dette celle, o
parole, con una dimensione tipica di 8 bit.
• 8 bit = 1 byte, ovvero una cella un byte
• Data una sequenza di bit:
bit più
significativo
bit meno
significativo
Organizzazione della Memoria (2/4)
•
•
•
•
La memoria principale è una sequenza di byte,
byte
ciascuna caratterizzata da un indirizzo.
indirizzo
L’indirizzo,
indirizzo o locazione,
locazione di un byte nel
dispositivo è il suo numero d’ordine nella
sequenza, a partire da 0.
Un tale sistema di indirizzo consente
l’identificazione univoca di ciascuna cella.
La memoria è divisa in celle di 1 byte => per
archiviare una stringa di 16 bit si utilizzano 2
celle di memoria consecutive.
consecutive
Organizzazione della Memoria (3/4)
Gli indirizzi sono espressi mediante numeri interi o
in notazione binaria.
binaria
Organizzazione della Memoria (4/4)
•
•
•
Memoria RAM (Random Access Memory): indica che
è possibile accedere individualmente ad ogni cella in
ordine casuale e con accesso diretto.
diretto
Il tempo necessario per accedere ad una cella di
memoria è lo stesso indipendentemente dalla posizione
della cella nella sequenza.
Operazioni sulle celle di memoria: lettura e scrittura.
Il numero totale di celle progettate è una potenza di 2.
N.B.:
1K= kilobyte = 210=1024 ~ 103, 1M = 220=1KK, 1G= 230=1KM
Es. 4 KB = 4x1024 = 4096 byte (4096 celle di memoria)