Rappresentazione dei numeri in virgola fissa
•
Il numero complessivo di cifre significative dei numeri che possono
essere rappresentate in un calcolatore è limitato dalla capacità di una
cella di memoria (con k bit, in modulo e segno, si rappresentano i numeri
compresi fra –2k-1+1 e 2k-1-1)
•
Quando si utilizzano numeri in cui sia presente sia una parte intera, sia
una decimale si può ricorrere alla rappresentazione detta in Virgola
Fissa in cui si fissa la posizione che la virgola deve avere all’interno del
numero da rappresentare
•
Ciò equivale a stabilire a priori il numero di cifre da utilizzare sia per la
parte intera, sia per quella decimale
•
Per i numeri negativi si può utilizzare ancora la tecnica del complemento
Università di Pavia - corso di Fondamenti di Informatica
113
Rappresentazione dei numeri in virgola fissa
Esempio: memorizzare 72.6 con 12 bit, di cui 4 riservati alle cifre decimali
72
36
18
9
4
2
1
0
0
0
0
1
0
0
1
0
b0
b1
b2
b3
b4
b5
b6
b7
0.6
1.2
0.4
0.8
1.6
1
0
0
1
b-1
b-2
b-3
b-4
72.610 = 0100 1000 10012
Rappresentare -72.6: -72.610 = 1011 0111 01112
In pratica il numero è stato moltiplicato per 24, avendo stabilito di avere 4 cifre
decimali
Problema: ridotto intervallo di rappresentazione dei numeri e ridotta
precisione di rappresentazione
Università di Pavia - corso di Fondamenti di Informatica
114
Rappresentazione normalizzata dei numeri reali
Qualsiasi numero reale a  0 può essere rappresentato in modo univoco in base
•
b>1 nella forma:
a  sign a   b


 d b
i 1
i
i
 1 a  0
con   Z , d i  0, sign a   
 1 a  0
•
Questa rappresentazione equivale a:
– d-1 d-2 … d0, d-1 d-2 …
per >0
– 0, d-1 d-2 …
per =0
– 0, 0 … 0 d--1 d--2 …
per <0
•
Se a=0, la rappresentazione è semplicemente 0
•
In pratica si deve fissare una variabilità finita per l’indice i
Università di Pavia - corso di Fondamenti di Informatica
115
Rappresentazione normalizzata dei numeri reali
1758.37
=
0.175837  104
-0.001
=
-0.1  10-2
1
=
0.1  101
5000
=
0.5  104
In generale qualunque numero A può essere rappresentato da:
1.
Il segno di A (S= segno, con la convenzione: 0 = +, 1 = -);
2.
Le cifre significative di A (M= mantissa) rappresentate in una forma normalizzata;
se n sono le cifre utilizzate e B è la base del sistema di numerazione, l’intervallo
di variabilità della mantissa è: B-n  M < 1;
3.
L’esponente (E) a cui bisogna elevare la base B per ottenere il fattore per cui
moltiplicare la mantissa per ottenere A
A = S 0.M x B E
Università di Pavia - corso di Fondamenti di Informatica
116
Rappresentazione in virgola mobile
Per una rappresentazione effettiva si conviene di:
•
eliminare i simboli ridondanti
•
fissare la lunghezza della mantissa
•
fissare la lunghezza dell’esponente
•
utilizzare per l’esponente una convenzione che permetta di rappresentare numeri
positivi e negativi senza l’indicazione esplicita del segno (complemento alla base o
tecnica dell’eccesso, sommando una opportuna costante)
•
disporre gli elementi rimasti (segno, esponente, mantissa) in un ordine
convenzionale
Quindi A viene rappresentato dalla sequenza:
S
E
M
Università di Pavia - corso di Fondamenti di Informatica
117
Rappresentazione in virgola mobile
Esempi:
•
in base 10: 1 cifra per il segno (0 = +, 1 = -), 2 cifre per l’esponente,
rappresentato in complemento, e 8 cifre per la mantissa
S
E
E
M
M
M
M
M
M
M
1758.37
0.175837  104
0 04 17583700
-0.001
-0.1  10-2
1 98 10000000
1
0.1  101
0 01 10000000
5000
0.5  104
0 04 50000000
-63517.8
-0.635178  105
1 05 63517800
-0.0000635178
-0.635178  10-4
1 96 63517800
M
Università di Pavia - corso di Fondamenti di Informatica
118
Rappresentazione in virgola mobile
Esempi:
•
in base 2: 1 bit per il segno (0 = +, 1 = -), 8 bit per l’esponente,
rappresentato in complemento e 23 bit per la mantissa
1001100011111000.0111011
0. 10011000111110000111011  216
0 00010000 10011000111110000111011
-0.0000000000101100110011111
-0. 101100110011111  2-10
1 11110110 10110011001111100000000
Cosa corrisponde al numero seguente rappresentato in virgola mobile?
11101101111110001111100000000000
-0. 111100011111  2-37
0.0000000000000000000000000000000000000111100011111
Università di Pavia - corso di Fondamenti di Informatica
119
Formato dei dati numerici in virgola mobile
•
Numeri reali in singola precisione: 32 bit (1 per il segno, 8 per
l’esponente, 23 per la mantissa); in doppia precisione: 64 (1, 11, 52)
•
In singola precisione l’esponente varia quindi tra -128 e +127
•
Si parla di dinamica per descrivere l’intervallo dei numeri
rappresentabili –2127 < N < 2127 (circa -1038< N < 1038)
•
La mantissa di 23 bit permette di rappresentare numeri con circa 7
cifre decimali significative
•
Per valori superiori a 1038 o inferiori a -1038 si parla di overflow
•
Per valori inferiori al minimo numero positivo rappresentabile ( 0) o
superiori al massimo numero negativo rappresentabile si parla di
underflow
Università di Pavia - corso di Fondamenti di Informatica
120
Formato dei dati numerici in virgola mobile
Passi per ottenere la rappresentazione binaria
•
trasformazione in binario
•
normalizzazione
•
memorizzazione
Esempio: 75.125
75
37
18
9
4
2
1
0
1
1
0
1
0
0
1
0.125
0.250
0.500
1.000
0
0
1
75.12510 = 1001011.0012
1001011.001  0.1001011001  27
Quindi in singola precisione:
0 00000111 10010110010000000000000
Università di Pavia - corso di Fondamenti di Informatica
121
Formato dei dati numerici in virgola mobile
Esempio: 0.0375
0.0375
0.0750
0.1500
0.3000
0.6000
1.2000
0.4000
0.8000
1.6000
0
0
0
0
0
1
0
0
1
0.037510  0.000010012
0.00001001  0.1001 2
4
Quindi in singola precisione:
0 11111100 10011001100110011001100
Università di Pavia - corso di Fondamenti di Informatica
122
Operazioni tra numeri in Virgola Mobile

Operazioni di moltiplicazione e divisione:
1)
2)
3)

Le mantisse vengono moltiplicate o divise
Gli esponenti vengo sommati o sottratti
Se necessario, la mantissa viene rinormalizzata e l’esponente corretto
Operazioni di somma o sottrazione:
1)
2)
3)
L’esponente più piccolo viene reso uguale al più grande spostando la
mantissa verso destra del numero di cifre pari alla differenza tra gli
esponenti (shift per ottenere un corretto incolonnamento)
Le mantisse vengono sommate o sottratte
Se necessario, la mantissa viene rinormalizzata e l’esponente corretto
A: 0,6502
x102 =
Shift: 0,006502 x104 +
B: 0,2347
x104 =
A+B: 0,241202 x104
NB Nello shift si potranno perdere alcune
cifre meno significative, ma sono quelle
di peso minore del numero più piccolo.
Nell’esempio le cifre in rosso verrebbero
perse se si utilizzassero solo 4 cifre
decimali per la mantissa
Università di Pavia - corso di Fondamenti di Informatica
123
Standard IEEE 754
•
Un numero reale  0 viene scritto in binario come 1.b1b2b3…  2e
•
La mantissa a è perciò variabile nell’intervallo 1  a < 2
•
Il numero viene memorizzato su 32 bit
– 1 bit di segno
– 8 bit di esponente
– 23 bit per la mantissa
•
Poiché la prima cifra è sempre 1, questa cifra non viene memorizzata. Di fatto
la mantissa ha 24 cifre binarie, di cui la prima sottintesa
•
L’esponente viene memorizzato sommando il valore costante 127 (notazione
eccesso 127)
Esempio: rappresentare 1.0
0 01111111 0000000 00000000 00000000
Università di Pavia - corso di Fondamenti di Informatica
124
Esempi IEEE 754
•
-1
1 01111111 0000000 00000000 00000000
•
2 = 1  21
0 10000000 0000000 00000000 00000000
•
-3 = -1.1  21
1 10000000 1000000 00000000 00000000
•
0.5 = 1  2-1
0 01111110 0000000 00000000 00000000
•
0.666666
0 01111110 0101010 10101010 10101010
•
3.141593
0 10000000 1001001 00001111 11011100
Università di Pavia - corso di Fondamenti di Informatica
125
Codifica di dati non numerici: definizioni
•
I calcolatori lavorano soltanto con i numeri, ma devono poter trattare anche
altre entità: per questa ragione sono stati inventati i codici.
•
Alfabeto è un insieme finito di simboli (caratteri) distinti
•
Parola o Stringa è una sequenza finita di simboli
Esempi:
•
B={A,
…,
U={1} alfabeto unario;
A={0, 1} alfabeto binario;
alfabeto inglese;
C={A, B, …, Z, 0, 1, …, 9} alfabeto alfanumerico
B,
C,
Z}
Parola è una successione finita di caratteri di un alfabeto
1011001101 è una parola di A o di C
SFSJKGH è una parola di B o di C
SF120C è una parola di C
Università di Pavia - corso di Fondamenti di Informatica
126
Alfabeto usato dai calcolatori
I calcolatori lavorano utilizzando due simboli:
– INTERRUTTORE: aperto/chiuso
– TRANSISTOR: conduce/non conduce
– LIVELLO DI TENSIONE: alto/basso
– RIFLETTIVITÀ DI UN’AREOLA: alta/bassa
– DOMINIO DI MAGNETIZZAZIONE:
I calcolatori utilizzano quindi una logica e un’aritmetica binaria
Ai due stati stabili di un dispositivo, ai due valori di una grandezza,
vengono associati convenzionalmente i simboli 0 e 1
Università di Pavia - corso di Fondamenti di Informatica
127
Alfabeti usati dall’uomo
•
{ A, B, C, D, … ,Z }
•
{ 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 }
•
{ ; , . ! ? : ( ) ‘ “… }
•
{ Caratteri giapponesi }
•
{ Caratteri arabi }
•
È necessario stabilire delle regole di corrispondenza, dette
CODIFICHE
•
La codifica metterà in corrispondenza biunivoca ogni SIMBOLO
appartenente all’alfabeto più ricco con una STRINGA di simboli
appartenenti all’alfabeto più ridotto
Università di Pavia - corso di Fondamenti di Informatica
128
Codifica
•
Dato un insieme I di elementi qualsiasi, si dice codifica di I mediante
parole di un alfabeto A un procedimento che permette di stabilire
una corrispondenza biunivoca tra gli elementi di I e le parole di un
sottoinsieme Q dell’insieme delle parole di A.
Esempio: codifica di lettere tramite cifre decimali
A  01, B  02, C  03, D  04, . . . , Z  26
•
Un codice binario è quindi la codifica dei simboli di un alfabeto
mediante stringhe di bit; se
C
è la cardinalità di
per il numero n di bit da utilizzare deve valere:
S
S
(n. di elementi)
C  2n . Ossia:
n  log ( C )  = M
2
Università di Pavia - corso di Fondamenti di Informatica
129
Codici non ridondati e ridondanti




Se n = M il codice è non ridondante (usa il minimo numero di bit
per codificare tutti i simboli di S)
Se n > M il codice è ridondante (usa più bit del necessario per
codificare tutti i simboli di S)
Si definisce distanza di Hamming (H) di un codice:
Il minimo numero di bit di cui differiscono due parole qualsiasi
del codice
•
Se n=M → H=1
•
Se c’è ridondanza H ≥ 1
Aggiungendo opportunamente la ridondanza alle parole si
possono ottenere codici a rilevazione e/o a correzione di errore
•
Si può dimostrare che per i codici a sola rilevazione:
•
N° di bit errati rilevati: R = H-1
•
e che per i codici a correzione:
•
N° di bit errati corretti: C ≤ (H-1)/2
•
N° di bit errati rilevati: R = H-C-1
Università di Pavia - corso di Fondamenti di Informatica
130
Codici Ridondanti a Rivelazione/Correzione
Sono codici con distanza di Hamming H > 1 e possono
avere la caratteristica di rivelare o correggere uno o
più bit errati

Parità:
•
•
•
È un codice con H = 2.
Si ottiene dal codice non ridondante aggiungendo 1
bit in modo che il numero complessivo di bit uguali a
“1” sia pari (parità pari) o dispari (parità dispari)
Avendo H=2 può solo rilevare gli errori, e solo se
questi accadono singolarmente o in un numero
dispari nella stessa parola di codice
Università di Pavia - corso di Fondamenti di Informatica
131
Codici di Hamming
• Sono codici ridondanti con H>2 e perciò con capacità di auto
correzione.
• Il più noto e semplice ha H=3: dato un codice non ridondante di n bit,
vengono inseriti in particolari posizioni k bit di controllo.
• Perché possa essere corretto un errore (singolo) deve valere:
n ≤ 2k –k –1
• Corregge un bit in posizione arbitraria
• Rivela la presenza di un solo errore
• Funziona bene se gli errori sono distribuiti casualmente
Esempio: parola di 7 bit (n = 7)
Per creare un codice di Hamming con H=3 bisogna rispettare la
relazione precedente e quindi usare 4 bit di controllo aggiuntivi (k = 4).
Università di Pavia - corso di Fondamenti di Informatica
132
Codici Ciclici
Usati nella trasmissione a distanza su linee rumorose,
soprattutto se sono possibili errori a raffica.
Sono codici rivelatori di errore, ma non autocorrettori.
In casi di errore rivelato il messaggio deve essere ritrasmesso.
Un messaggio M di k bit da trasmettere viene trattato come un
polinomio di grado k-1, i cui coefficienti sono i bit del
messaggio.
Preso un altro polinomio G di grado r si arriva attraverso
operazioni modulo 2 su M e G, ad un terzo polinomio T di grado
t (con k<t≤k+r), divisibile per G.
I coefficienti di T costituiscono la stringa di bit da trasmettere.
In ricezione un algoritmo analogo divide T per G. Se il resto
della divisione è ≠ 0 il messaggio deve essere ritrasmesso.
Università di Pavia - corso di Fondamenti di Informatica
133
Codifica delle cifre decimali
Vi sono diverse codifiche delle cifre decimali
•
Codice BCD (Binary Coded Decimal): ogni cifra decimale viene
codificata con 4 bit. È un codice pesato perché il valore di ogni cifra
viene ottenuto eseguendo una somma pesata delle quattro cifre
binarie che lo compongono
•
Codice ad eccesso tre: è basato sul codice BCD. Ogni codifica si
ottiene sommando 3 alla codifica BCD. Non è un codice pesato. Per
passare da una cifra alla cifra corrispondente al complemento a 9
basta complementare le cifre binarie della sua codifica
•
Codice 2421: i numeri indicano ordinatamente i pesi delle 4 cifre
binarie. Come per l’eccesso tre, le codifiche di una cifra e della cifra
corrispondente al complemento a 9 sono fra loro complementari
Università di Pavia - corso di Fondamenti di Informatica
134
Codifica delle cifre decimali
•
BCD
Eccesso 3
2421
0
0000
0011
0000
1
0001
0100
0001
2
0010
0101
0010
3
0011
0110
0011
4
0100
0111
0100
5
0101
1000
1011
6
0110
1001
1100
7
0111
1010
1101
8
1000
1011
1110
9
1001
1100
1111
Sono tutti codici che lasciano 6 configurazioni inutilizzate delle 16 a
disposizione con 4 bit
Università di Pavia - corso di Fondamenti di Informatica
135
Codice Gray
•
Per il modo in cui viene creato si dice che è un codice riflesso. Serve a
codificare un numero in modo che le stringhe di bit che rappresentano
numeri consecutivi differiscano per un solo bit. Il codice Gray elimina il
problema di transizioni spurie passando da una codifica alla successiva
•
Dato un numero, si può passare dalla sua codifica binaria b=bm bm-1 … b1 b0
alla codifica Gray g=gm gm-1 … g1 g0 nel modo seguente:
b2
b1
b0
g2
g1
g0
0
0
0
0
0
0
0
0
1
0
0
1
0
1
0
0
1
1
0
1
1
0
1
0
1
0
0
1
1
0
1
0
1
1
1
1
1
1
0
1
0
1
1
1
1
1
0
0
 g m  bm

 gi  bi  bi 1
0im
mentre il passaggio inverso è
bm  g m

bi  gi  bi 1
0im
 è il simbolo di somma modulo 2 (EXOR - or esclusivo)
Università di Pavia - corso di Fondamenti di Informatica
136
Codifica di informazioni alfanumeriche
•
Per convenzione, si definisce alfabeto esterno di un calcolatore l’insieme dei
caratteri che è in grado di leggere e stampare mediante i dispositivi di I/O.
Questo alfabeto comprende almeno 64 caratteri (esempio codice Field data):
– le 26 lettere dell’alfabeto inglese maiuscole
– le 10 cifre decimali
– 28 caratteri vari (spazio, segni di punteggiatura, etc.)
In genere si utilizzano codici a 7 o 8 bit
•
EBCDIC (Extended Binary Coded Decimal Interchange Code): 8 bit.
Rappresenta caratteri alfanumerici e speciali. Personalizzato per le varie
nazionalità (necessita di conversioni e ormai obsoleto)
•
UNICODE: rappresenta con 16 bit tutti i caratteri della lingua parlata
dall’uomo (usato da Java e adottato da HP, IBM, Microsoft, Oracle, …)
Università di Pavia - corso di Fondamenti di Informatica
137
Codice ASCII
 American Standard Code for Information Interchange
 Ne esistono due versioni:
• 7 bit → 128 simboli; in questo caso l’ottavo bit è usato a volte
come ridondanza (H=2) per la rilevazione di un errore (bit di
parità)
• 8 bit → 256 simboli (ASCII esteso); codifica anche lettere
accentate e caratteri grafici; l’estensione non è standardizzata
e quindi fra i 128 simboli aggiunti può succedere che alla
stessa codifica corrispondano simboli diversi
 È il codice più usato per la codifica dei caratteri alfanumerici
(lettere e cifre) oltre che per simboli di interpunzione e vari. Ad
esempio: . ; : , ( ) [ ] { } / \ < > = ? ! ~ | # $ % & * ^ - @ ecc.
Università di Pavia - corso di Fondamenti di Informatica
138
Codice ASCII
Università di Pavia - corso di Fondamenti di Informatica
139
Codifica delle immagini
•
In un calcolatore tutto è discreto
•
L’immagine è un insieme continuo di informazioni (luce, colore) in due
dimensioni
•
Quando si memorizzano immagini pittoriche o fotografiche si scompone
artificiosamente l'immagine in una sequenza di elementi di informazione
codificati con sequenze binarie
Università di Pavia - corso di Fondamenti di Informatica
140
Codifica bitmap di Immagini
•
L'immagine viene suddivisa in un reticolo di punti detti pixel (picture
element)
•
Ogni pixel viene codificato con una sequenza di bit
000000000000000000000000
000000000000000000100000
000000000000000010100000
000000000000001000100000
000000000000100000100000
000000000010000000100000
000000001000000000100000
000000100000000000100000
La qualità dell'immagine dipende dal numero di pixel per unità di
lunghezza e dal numero di bit utilizzati per codificare ogni pixel.
Università di Pavia - corso di Fondamenti di Informatica
141
Codifica bitmap di Immagini
Problema: Non è possibile ingrandire a
piacimento un'immagine perché non si aumenta
il dettaglio, ma si distinguono i singoli pixel.
La soluzione di aumentare il
numero di pixel non è possibile
perché questo aumenterebbe lo
spazio necessario per
memorizzare una immagine (si
richiederebbe una
compressione)
Università di Pavia - corso di Fondamenti di Informatica
142
Codifica dei pixel
 Immagini in bianco e nero: raramente si usa un solo bit. Ogni pixel
di solito si codifica con 8 bit per rappresentare diversi livelli di
grigio (28 = 256 livelli)
 Immagini a colori: i colori vengono ottenuti tramite la combinazioni
di almeno 3 colori base, detti primari. La composizione può avvenire
tramite la tecnica di sintesi sottrattiva o additiva in funzione del tipo
di dispositivo utilizzato (stampante, monitor o televisore)
•
Per codificare un pixel si devono codificare i tre colori primari (es.
RGB), la cui combinazione consente di ottenere il colore del pixel
stesso
•
Per ciascun colore primario spesso si usano 8 bit e quindi in totale
per codificare ciascun pixel servono 24 bit
•
Ciò consente di codificare 224 ~ 16 milioni di colori diversi
•
Con profondità di colore si intende il numero di bit utilizzati per
codificare i pixel
Università di Pavia - corso di Fondamenti di Informatica
143
Occupazione di memoria di un’immagine
L’occupazione di memoria di un’immagine dipende da:
 definizione o risoluzione dell’immagine (intesa come il numero
di pixel per unità di lunghezza: dot per inch = DPI)
 Numero dei colori (dipende a sua volta dal numero di bit usati
per codificarli: 8, 16, 24 bit)
Tipo immagine
Definizione
Colori
Occupazione
Televisiva
720 x 625
256 (8 bit)
~ 440 kByte
Monitor di PC
1024 x 768
65.536 (16 bit)
1,5 MByte
Fotografica
15.000 x 10.000
16.000.000
(24 bit)
~ 430 MByte
Università di Pavia - corso di Fondamenti di Informatica
144
Formati di file bitmap
 TIFF (Tagged Image File Format): Profondità fino a 24 bit e
vari metodi di compressione
 GIF (Graphics Interchange Format): consente di memorizzare
più immagini in uno stesso file
 JFIF (Jpeg File Interchange Format) e SPIFF implementano il
metodo di codifica JPEG (Joint Photographers Expert Group),
formato standard che usa due tipi di compressione molto
utilizzato su Internet. Prevede la tecnica di visualizzazione
interallacciata (l’immagine viene composta per righe alterne
per cui viene caricata velocemente, ma diventa più nitida man
mano che viene completata)
 BMP (BitMaP) usata con Windows supporta immagini con
profondità 1, 4, 8 e 24 bit
Università di Pavia - corso di Fondamenti di Informatica
145
Immagini vettoriali
Questo formato si usa in applicazioni di progettazione meccanica,
architettonica, elettronica, e in tutte quelle applicazioni in cui
l’immagine viene costruita con elementi di alto livello quali linee,
cerchi, poligoni, archi, colori, ecc.
Al contrario delle immagini bitmap in cui l’elemento di informazione è il
pixel, in quelle vettoriali gli elementi dell’immagine sono gli oggetti
grafici che la compongono
circle 98 66 50
polyline 0 48 88 152 88 48
Ogni oggetto è codificato attraverso un identificatore (es. polyline, circle,
etc.) e alcuni parametri quali le coordinate del centro e la lunghezza del
raggio (per la circonferenza) o le coordinate dei vertici (per il poligono)
Università di Pavia - corso di Fondamenti di Informatica
146
Formato vettoriale per le immagini
Vantaggi:
 Indipendenza dal dispositivo di visualizzazione e dalla sua
risoluzione
 Gli elementi grafici sono indipendenti l’uno dall’altro e si
possono elaborare distintamente
 minore occupazione di memoria rispetto alla grafica bitmap
Svantaggi:
 applicabilità limitata: un’immagine fotografica non si può
scomporre in elementi primitivi
 limiti nell’utilizzo in quanto si possono manipolare immagini
vettoriali solo con il software utilizzato per crearle o
compatibile
Università di Pavia - corso di Fondamenti di Informatica
147
Formati di file vettoriali
 PostScript: incorporato in molte stampanti, si è evoluto nel
tempo e consente di rappresentare immagini vettoriali e
bitmap anche a colori con diverse tecniche di compressione.
Formati derivati del PostScript sono EPS e PDF
 DXF (Drawing Interchange Format) usato da molti programmi
di disegno memorizza i vettori in formato testo. La versione
binaria DXB è più compatta ma meno diffusa
Università di Pavia - corso di Fondamenti di Informatica
148
Rappresentazione di immagini in movimento
Immagini in movimento vengono rappresentate attraverso
sequenze di immagini fisse (frame) visualizzate ad una
frequenza sufficientemente alta da consentire all’occhio umano
di ricostruire il movimento (24, 25 o 30 immagini al secondo)
Lo standard multimediale per le immagini in movimento, MPEG,
codifica ciascun frame separatamente secondo lo standard
JPEG
Si utilizzano tecniche di compressione in quanto un minuto di
filmato a 25 fotogrammi al secondo richiederebbe uno spazio di
memorizzazione di 644 MByte (un CD contiene 680 MByte)
Università di Pavia - corso di Fondamenti di Informatica
149
Algebra Booleana (George Boole (1815-1864))
•
Il simbolo “::=“ significa “è definito / composto da”
•
Il simbolo “|” significa “oppure”
•
L’algebra di Boole è definita su due elementi (vero | falso, 0 | 1)
•
Costante booleana ::= 1 | 0
•
Operatore booleano ::= NOT | AND | OR
•
Una variabile booleana può assumere solo uno dei due valori 0 o 1
Università di Pavia - corso di Fondamenti di Informatica
150
Operatori Booleani
•
NOT (simbolo
1 0
):
0 1
simbolo grafico
x
x
0
1
1
0
Università di Pavia - corso di Fondamenti di Informatica
151
Operatori Booleani
•
AND (prodotto logico); simbolo * oppure •
1*1=1
1*0=0*1=0*0=0
simbolo grafico
x
y
x*y
0
0
0
0
1
0
1
0
0
1
1
1
Università di Pavia - corso di Fondamenti di Informatica
152
Operatori Booleani
•
OR (somma logica); simbolo +
0+0=0
1+0=0+1=1+1=1
simbolo grafico
x
y
x+y
0
0
0
0
1
1
1
0
1
1
1
1
Università di Pavia - corso di Fondamenti di Informatica
153
Funzioni booleane o logiche
•
Sulle variabili booleane può essere definita una funzione booleana o
logica F(x1, x2, …, xn) che per ogni n-pla xi assume valori 0 e 1
•
Una particolare funzione logica F è definita quando ad essa è
assegnata una “tavola di verità”, una tabella in cui è specificato il
valore che assume F in corrispondenza di ogni combinazione delle
variabili x1, x2, …, xn
•
Il numero di combinazioni di n variabili è 2n, cioè la tavola della
verità è costituita da 2n righe
•
Nell’algebra di Boole vale il teorema di dualità che dice:
Ogni identità e ogni proprietà resta valida se si scambiano tra loro
gli elementi 0 e 1 e gli operatori AND e OR
•
Una espressione è duale di un’altra se ottenuta scambiando AND
con OR e 0 con 1. Se un teorema è vero, anche il suo duale è vero
Università di Pavia - corso di Fondamenti di Informatica
154
Proprietà dell’algebra booleana
Duale
Idempotenza
Complementazione
Prop. commutativa
Prop. associativa
Prop. Distributiva
Prop.assorbimento
De Morgan
x0  0
x 1  x
xx  x
x 1  1
x0 x
xx  x
xx  0
x y  yx
x  x 1
x y  yx
x  y   z  x   y  z 
x  y  z  x  y  x  z
{
x  x y  x
x  y   z  x   y  z 
x   y  z   x  y   x  z 
x  x  y   x
x  ( x  y)  x  y
x  ( x  y)  x  y
x y  x  y
x  y  x y
xx
Università di Pavia - corso di Fondamenti di Informatica
155
Operatori Universali
NAND e NOR sono detti universali perché possono da soli realizzare i tre
operatori fondamentali NOT, AND e OR
NAND (/) = negazione dell’AND
NOR ( ) = negazione dell’OR
1/1=0
0 0=1
1/0=0/1=0/0=1
1 0=0 1=1 1=0
simbolo grafico
simbolo grafico
x
y
x/y
x
y
x y
0
0
1
0
0
1
0
1
1
0
1
0
1
0
1
1
0
0
1
1
0
1
1
0
Università di Pavia - corso di Fondamenti di Informatica
156
Operatori Universali
Proprietà:
x 1 0
x /0 1
x0 x
x  ( y  z)  ( x  y)  z
x /1  x
x /( y / z )  ( x / y ) / z
xx x
x/ x  x
x  y  x y
x/ y  x y
x y  x y
x/ y  x y
Solo NOR
Solo NAND
Not x  0  x  x  x
Or
x y0 x y x y  x y
And x  y  x  y 
 x  y  x  y
Not
x 1  x  x  x
And x  y 1  x  y  x  y  x  y
Or
x  y  x y 
 x  y  x  y
Università di Pavia - corso di Fondamenti di Informatica
157
Operatori Universali
•
Realizzazione tramite
NAND
x
x
x
NOT
x
NOR
x
x y
OR
y
x y
x
y
x
y
x y
y
x
AND
x
x y
x
x y
x y
y
y
Università di Pavia - corso di Fondamenti di Informatica
158
Operatore OR-esclusivo (EXOR)
•
L’operatore EXclusive-OR o EXOR è anche detto sommatore modulo 2.
Il simbolo grafico è 
•
x
y
xy
0
0
0
0
1
1
1
0
1
1
1
0
Può essere ricavato tramite i 3 operatori elementari:
f x, y   x  y  x  y  x  y
Università di Pavia - corso di Fondamenti di Informatica
159
Operatore OR-esclusivo (EXOR)
•
L’exor è anche detto funzione DISPARITÀ, perché è vero solo quando un
numero dispari dei suoi argomenti è vero
•
Proprietà:
x0  x
x 1  x
xx  0
x  x 1
x  y  y  x commutativ a
x  y   z  x   y  z 
associativ a
Università di Pavia - corso di Fondamenti di Informatica
160