Lezione 2 Informatica PDF

Cos’è l’elettronica digitale? In elettronica, un circuito analogico è un circuito in cui le informazioni sono rappresentate utilizzando tutti i liv...

Cos’è l’elettronica digitale? In elettronica, un circuito analogico è un circuito in cui le informazioni sono rappresentate utilizzando tutti i livelli di tensione o di corrente appartenenti ad un determinato intervallo ○ infiniti livelli di tensione (o di corrente) sono validi ai fini della rappresentazione Al contrario, un circuito digitale è un circuito in cui le informazioni sono rappresentate attraverso un numero finito di livelli di tensione o di corrente ○ non tutti i livelli di tensione (o di corrente) sono riconosciuti come validi ma solo quelli Elettronica e logica digitale appartenenti ad un insieme discreto Tutti i segnali elettrici (in tensione o corrente) sono soggetti al rumore che può alterarne i valori, ma il principale vantaggio dei circuiti digitali rispetto agli analogici è l'alta capacità di reiezione (eliminazione) del rumore Un segnale elettrico digitale affetto da rumore è ancora facilmente interpretabile! Applicazioni dell’elettronica digitale Logica digitale Il primo computer digitale venne costruito nel 1944 alla Harvard Il termine digitale deriva dalla parola inglese digit, che significa University, ma era ancora di tipo elettromeccanico, non elettronico cifra o numero e che a sua volta deriva dal latino digitus che significa dito L'elettronica digitale ebbe inizio nel 1946 con un calcolatore ○ con le dita contiamo i numeri da 1 a 10! elettronico digitale chiamato ENIAC, realizzato con circuiti a valvole La logica digitale quindi è associata alla matematica del discreto che lavora con un insieme finito di numeri Anche se per molti anni il digitale rimase nel settore dei computer, oggi le tecniche digitali trovano impiego in moltissime aree: dalla telefonia, ai sistemi militari, dagli strumenti di uso medico fino a prodotti di ampio mercato (televisione, radio, automobili, etc.) Logica binaria bit, Byte, … La logica binaria è un particolare tipo di logica digitale che lavora Nell’ambito dell’informatica il bit è l’unità di misura con la quale si esprime la con due soli possibili valori: quantità di informazione elaborata, memorizzata o comunicata Come ogni unità di misura anche il bit ha i suoi multipli: 1 Nibble = 22 (4) bit 1 Byte = 23 (8) bit 0 1 1 KiloByte (KB) = 210 (1024) Byte FALSO VERO 1 MegaByte (MB) = 220 Byte = 1024 KB (circa un milione di Byte) Nella logica binaria la singola cifra è detta bit 1 GigaByte (GB) = 230 Byte = 1024 MB (circa un miliardo di Byte) ○ la parola bit è la contrazione delle parole inglesi binary e digit e 1 TeraByte (TB) = 240 Byte = 1024 GB (circa mille miliardi di Byte) significa quindi letteralmente cifra binaria L’informatica spesso usa termini divertenti per indicare le cose: “one byte” significa “un morso”, “one nibble” significa “un bocconcino”. Rappresentazione dell’informazione Il calcolatore e l’elettronica digitale All’interno del calcolatore, CPU, memoria centrale e dispositivi di Dati ed istruzioni vengono rappresentati tramite sequenze di bit: I/O sono realizzati con tecnologia elettronica digitale ○ Ad esempio: 01000110101...1 Dati ed istruzioni vengono rappresentati a partire da due valori distinti di grandezze elettriche: Una sequenza di bit può rappresentare qualunque tipo di informazione e chi la legge non può capire di che informazione si tratti senza una ○ tensione alta (VH, ad es. 5V) conoscenza a priori ○ tensione bassa (VL, ad es. 0V) Ad esempio, la sequenza 01000001 potrebbe rappresentare: A tali valori vengono convenzionalmente associate le due cifre ○ l’intero 65 binarie 0 e 1: ○ il carattere ‘A’ ○ l’ampiezza di una nota musicale ○ logica positiva: 1 ↔ VH / 0 ↔ VL ○ il colore di un puntino sullo schermo ○ logica negativa: 0 ↔ VH / 1 ↔ VL ○... Bisogna introdurre il concetto di codifica Codifica “Nella teoria dell'informazione, e conseguentemente nelle telecomunicazioni, nell'elettronica e nell'informatica, un codice è un sistema di segnali, segni o simboli convenzionalmente designati per rappresentare un'informazione” (Wikipedia, 2017) “Il procedimento di codifica riguarda la modalità seguita per Sistemi di numerazione assegnare univocamente ad ogni elemento dell'insieme di informazioni da rappresentare una stringa che lo rappresenti.” (Wikipedia, 2017) Noi vedremo esempi di codifiche per: numeri caratteri immagini suoni Il concetto di numero Sistemi di numerazione “In matematica, un numero è un ente astratto in grado di esprimere Un sistema di numerazione è un modo di esprimere e una quantità, oppure la posizione in un elenco di elementi, oppure rappresentare i numeri attraverso un insieme di simboli (detti ancora il rapporto tra grandezze dello stesso tipo.” (Treccani, 2017) cifre) I numeri sono concetti ed esistono in quanto tali Un sistema di numerazione si dice posizionale se i simboli usati per La loro rappresentazione può invece variare a seconda delle scrivere i numeri assumono valori diversi a seconda della posizione convenzioni adottate che occupano nella notazione Non bisogna confondere un numero con una sua rappresentazione! Un sistema di numerazione si dice non posizionale in caso Ad esempio il numero tre può essere rappresentato come: contrario 3 (arabo) III (romano) df (babilonese) df (ebraico) Sistemi posizionali e non posizionali Sistemi posizionali e non posizionali Nel sistema di numerazione arabo la prima cifra da destra esprime il numero I sistemi di numerazione posizionali necessitano della cifra zero per delle unità, la seconda quello delle decine, la terza quello delle centinaia, la segnare i posti "vuoti" quarta quello delle migliaia, e così via Ad esempio il numero cinquecentocinque (5 centinaia, 0 decine, 5 unità) Per esempio il numero 555 si legge: 5 centinaia, 5 decine, 5 unità (ovvero va scritto 505, con uno zero nella posizione delle decine cinquecentocinquantacinque) ○ se non si mettesse lo zero, scrivendo 55, sarebbe il numero ○ la stessa cifra, 5, quando si trova nella prima posizione ha valore cinque, cinquantacinque invece di cinquecentocinque nella seconda posizione ha valore cinquanta, nella terza posizione ha valore cinquecento Nei sistemi non posizionali invece non si usa lo zero perché l'uso di simboli diversi per unità, decine, centinaia, etc. lo rende non necessario In un sistema di numerazione non posizionale invece per esprimere questi tre ○ in numeri romani cinquecentocinque si scrive DV e non si può valori si usano tre simboli diversi: ad esempio in numeri romani confondere con cinquantacinque che si scrive LV cinquecentocinquantacinque si scrive DLV Sistemi posizionali e non posizionali Formalizzazione Un sistema di numerazione posizionale è caratterizzato da una L'utilizzo della posizione per codificare delle informazioni permette di base di rappresentazione B usare un numero minore di simboli ○ siamo in grado di scrivere tutti i numeri con sole 10 cifre Ogni numero è rappresentato come sequenza di simboli (cifre) appartenenti a un alfabeto di B simboli distinti Nei sistemi non posizionali risulta difficile l’utilizzo di regole generali Ogni simbolo è associato ad un valore compreso fra 0 e B-1 e ad un per il calcolo peso che dipende dalla sua posizione L'adozione della notazione posizionale ha permesso di definire ed Il simbolo in posizione i è associato ad un peso pari a Bi applicare algoritmi relativamente semplici ed indipendenti dalla dimensione dei numeri per effettuare le operazioni elementari come Per ottenere il valore del numero rappresentato in forma esplicita si moltiplica il valore di ogni simbolo per il peso associato e si l'addizione, la moltiplicazione o l'elevamento a potenza, consentendo sommano i risultati ottenuti. lo sviluppo del calcolo matematico astratto e quindi della scienza moderna Esempio: base B Esempio: base 10 (B = 10) Consideriamo un numero rappresentato in base B con N cifre: La base 10 è quella a noi più familiare ma non è l’unica! Essa utilizza una rappresentazione basata su 10 possibili cifre dN-1 … d2 d1 d0 (da 0 a 9) ognuna delle quali ha un peso associato dipendente dalla sua posizione che è dato dalle potenze del Il simbolo d0 è in 10 posizione 0 e pesa B0 Il numero 234 può essere rappresentato in forma esplicita Il simbolo dN-1 è Il simbolo d2 è in in posizione N-1 e posizione 2 e pesa come: pesa BN-1 B2 2 * 102 + 3 * 101 + 4 * 100 Internamente, un calcolatore elettronico adotta una rappresentazione binaria (B=2) Esempio: base 2 (B = 2) Conversioni di base Per noi esseri umani è più familiare la rappresentazione La base 2 è quella utilizzata dal calcolatore elettronico! decimale (B=10) Essa utilizza una rappresentazione basata su 2 possibili cifre Quindi, le quantità numeriche che forniamo come dati di (0 e 1) ognuna delle quali ha un peso associato dipendente input al calcolatore, ad esempio tramite tastiera, o quelle che dalla sua posizione che è dato dalle potenze del 2 otteniamo come dati di output dal calcolatore, ad esempio tramite monitor, sono in base 10 Il numero 1001 può essere rappresentato in forma esplicita come: Il passaggio dall'una all'altra forma richiede un processo di conversione 1 * 23 + 0 * 22 + 0 * 21 + 1 * 20  Ogni numero può essere espresso, in modo univoco, come sequenza di Il metodo delle divisioni successive è applicabile a qualunque base cifre in una qualunque base Altre basi Nell’ambito dell’informatica, oltre alla base 2 e alla base 10, si Divisione successive con altre basi Vediamo qualche esempio: utilizzano comunemente altre due basi ○ Base “ottale” (B=8) →simboli {0, …, 7} ○ Base “esadecimale” (B=16) →simboli {0, …, 9, A, …, F} Consideriamo ad esempio il numero ventisette Numero Base Calcolo Rappresentazione quattordici quattro 14/4=3 con resto 2 3/4=0 con resto 3 32 undici due 11/2=5 con resto 1 5/2=2 con resto 1 2/2=1 con resto 0 Numero Base Simboli Rappresentazione 1/2=0 con resto 1 1011 ventisette due {0,1} 11011 sessantatre dieci 63/10=6 con resto 3 6/10=0 con resto 6 63 ventisette otto {0,1,...,7} 33 ventisette dieci {0,1,...,9} 27 sessantatre sedici 63/16=3 con resto 15 3/16=0 con resto 3 3F ventisette sedici {0,1,...,9, A,...,F} 1B Rappresentazione dei numeri naturali In un calcolatore che opera con parole di N bit, con ogni parola è possibile rappresentare 2N numeri naturali Solitamente, si rappresentano i numeri da 0 a 2N - 1 Codifica dei numeri naturali e Ad esempio: aritmetica binaria ○ 8 bit → 256 numeri → [0, …, 255] ○ 16 bit → 65.536 numeri → [0, …, 65.535] ○ 32 bit → 4.294.967.296 numeri →[0, …, 4.294.967.295] ○ … Ad un determinato numero di bit, quindi, si associa un intervallo rappresentabile (intervallo limitato e chiuso) che ci indica quali numeri naturali possono essere codificati con quel numero di bit. Esercizio (soluzione) Overflow Calcoliamo A/B con A=cinquantanove e B=cinque espressi in rappresentazione Per capire il concetto di overflow, consideriamo in un primo binaria: momento il sistema di numerazione decimale ○ utilizzando solo tre cifre decimali è possibile Soluzione: rappresentare solo i numeri compresi tra 0 e 103-1 ovvero 101 999 111011 101 ○ il numero successivo (1000) e tutti quelli che lo seguono 1011 -100 richiedono una quarta cifra che non abbiamo 000 Da ciò si deduce che: 1001 Quoziente ○ avendo un numero finito di cifre possiamo rappresentare 101 un intervallo discreto di numeri naturali -1001 101 - 100 Quindi A/B = 1011 con resto di 100! Resto Overflow Overflow Immaginiamo adesso di effettuare un’operazione di somma tra L’overflow porta a risultati errati in quanto vengono due numeri rappresentati in base decimale con 3 cifre considerate solo le cifre meno significative ovvero quelle più a destra 325 + 158 = 483 Quindi, ad esempio, si verifica che: Il risultato può essere ancora 6 + 98 = 104 rappresentato con 3 cifre ○ 678 + 421 = 99 12 + 45 = 57 ○ 560 + 923 = 483 ○ 999 + 1 = 0 678 + 421 = 1099 Il risultato non può essere rappresentato con 3 cifre: 560 + 923 = 1483 Overflow! 999 + 1 = 1000 Quindi un overflow si verifica quando il risultato di un’operazione ha bisogno, per essere rappresentato, di più bit di quanti non ne abbiamo a disposizione. Overflow Overflow L’overflow si verifica con tutti i sistemi di numerazione nel Quindi, ad esempio, se si hanno solo tre bit si verifica che: momento in cui si limita il numero di cifre che si possono ○ i numeri rappresentabili sono quelli da 0 a 23-1=7 utilizzare ○ si verifica overflow ogni qual volta il risultato di un'operazione è maggiore o uguale a 8 Questo è proprio il caso del calcolatore che ha ovviamente Ad esempio: una memoria limitata per immagazzinare le informazioni ○ 510 + 410 = 910 non da overflow nell’ambito del sistema di rappresentazione decimale In particolare il calcolatore ha un numero massimo di bit per ○ ma 1012 + 1002 = 10012 da overflow! rappresentare un numero Naturale ○ ovvero per un calcolatore che usa solo 3 bit: 510 + 410 = 110! Le operazioni che possono portare a overflow nell’ambito dei numeri naturali sono ovviamente addizione e moltiplicazione Numeri interi Finora abbiamo visto come possono essere codificati i numeri naturali in base 2 e le operazioni aritmetiche che possono essere svolte su di essi I numeri naturali sono solo un sottoinsieme dei numeri interi Codifica di numeri interi Ci serve un metodo per codificare numeri con segno Vedremo le più comuni codifiche: ○ modulo e segno ○ complemento a uno ○ complemento a due Vedremo quindi come l’operazione di somma algebrica di numeri interi con segno possa essere implementata  Rappresentazione di un numero Rappresentazione modulo e segno negativo Se si hanno a disposizione N bit: Se si vuole calcolare la rappresentazione di un numero negativo in ○ N-1 bit vengono utilizzati per la rappresentazione del modulo modulo e segno con N bit si deve: ○ 1 bit viene utilizzato per la rappresentazione del segno ○ settare il bit in posizione N-1 (ovvero il bit di segno) a 1 ○ Ad esempio: ○ calcolare la rappresentazione binaria del modulo ad esempio 0 →segno + con il metodo delle divisioni successive 1 →segno - ○ utilizzare tutti gli N-1 bit per immagazzinare il modulo (ciò N-1 N-2 N-3 2 1 0 significa che se la rappresentazione del modulo occupa meno di N-1 bit vanno aggiunti degli 0 a sinistra per riempire). Segno Modulo Ad esempio, volendo rappresentare il numero decimale –2710 in Quindi, con una parola di N bit si possono rappresentare i numeri rappresentazione modulo e segno ad 8 bit avremo: interi appartenenti all’intervallo: –2710 = 100110112 [– (2N-1 – 1), 2N-1 –1] Segno Rappresentazione binaria del in quanto è come se avessimo due intervalli (uno positivo e uno modulo Bit 0 di riempimento negativo) rappresentati entrambi con N-1 bit Esempio: numeri a 4 bit (modulo e Somma algebrica (modulo e segno) segno) -7 1111 La somma algebrica tra due numeri interi in rappresentazione -6 1110 modulo e segno può essere un’operazione complessa! -5 1101 -4 1100 Non basta infatti eseguire una addizione dei due numeri. -3 1011 Consideriamo numeri a 4 bit: -2 1010 –110 = 10012 -1 1001 +210 = 00102 -0 1000 +0 0000 effettuando l’addizione otteniamo: 10112 che non è -110 ma -310! +1 0001 +2 0010 Dobbiamo applicare un algoritmo più complesso. Tutto dipende +3 0011 dai segni dei due numeri interi: +4 0100 ○ entrambi positivi → addizione tra i moduli e segno positivo +5 0101 ○ entrambi negativi → addizione tra i moduli e segno negativo +6 0110 ○ uno negativo e uno positivo → ??? +7 0111 Somma algebrica (modulo e segno) Somma algebrica (modulo e segno) Svolgiamo ad esempio la somma algebrica tra i numeri: Ma cosa sarebbe successo se avessimo dovuto effettuare la somma algebrica tra i ○ +5910 = 001110112 numeri: ○ –2710 = 100110112 ○ +2710 = 000110112 ○ –5910 = 101110112 In decimale, eseguiamo semplicemente una sottrazione: ○ +5910 –2710 = +3210 In questo caso, 59 > 27 quindi, in decimale, eseguiamo una sottrazione: ○ 59 – 27 = 32 e assegnamo al risultato un segno negativo Anche in binario dobbiamo eseguire una sottrazione ma solo sui bit del modulo: ○ +2710 –5910 = –3210 0 1 1 1 0 1 1 - Anche in binario dobbiamo eseguire una sottrazione ma anche in questo caso solo sui bit di modulo: 0 0 1 1 0 1 1 = 0 1 1 1 0 1 1 - 0 1 0 0 0 0 0 0 0 1 1 0 1 1 = Quindi eseguiamo l’operazione su 7 bit e settiamo l’ultimo bit a 0 (numero 0 1 0 0 0 0 0 positivo): ○ (001110112) + (100110112) = 001000002 Quindi eseguiamo l’operazione su 7 bit e settiamo l’ultimo bit a 1 (numero negativo): Somma algebrica (modulo e segno) Doppio 0 Quindi ricapitolando l’algoritmo per implementare la somma algebrica tra due La rappresentazione in modulo e segno ha anche un altro numeri in rappresentazione binaria in modulo e segno è: problema ○ Se i due numeri hanno segni concordi: addiziona i moduli e mantieni il segno ○ Se i due numeri hanno segni discordi, Abbiamo una doppia rappresentazione per lo zero individua il modulo maggiore, esegui la sottrazione tra il modulo maggiore e quello minore Ad esempio, nel caso di rappresentazione a 8 bit i numeri: poni al risultato il segno del numero con modulo maggiore ○ 000000002 = (+) 010 ○ 100000002 = (-) 010 E’ un algoritmo troppo complesso da implementare per svolgere un’operazione così banale! E’ uno spreco perché potremmo utilizzare uno dei due codici per Dobbiamo trovare un modo per ottimizzarlo! rappresentare un altro numero!  Rappresentazione di un numero Complemento a 1 negativo E’ una tecnica alternativa per rappresentare i numeri Ad esempio, volendo rappresentare il numero decimale -4310 in rappresentazione complemento a 1 a 8 bit dovremo: negativi ○ partire dalla rappresentazione di 4310 in binario 1010112 Dati N bit è possibile rappresentare numeri nell’intervallo: ○ aggiungere due bit 0 a sinistra per arrivare a 8 bit ottenendo [–(2N-1 – 1), 2 N-1 –1] 001010112 Data la rappresentazione binaria di un numero positivo ○ operare una bitwise not ottenendo appartenente all’intervallo −4310 = 110101002 [0, 2N-1–1] Nota che -4310 è rappresentabile in complemento a 1 su 8 bit perchè 4310 è il suo corrispondente negativo in complemento a 1 si ottiene: rappresentabile in binario su 7 bit. aggiungendo tanti 0 a sinistra fino ad arrivare ad un totale di N bit Se il modulo del numero non è rappresentabile con un bit in meno rispetto al numero di bit che vogliamo usare allora quel numero non è invertendo tutti i bit (l’operazione è anche detta bitwise rappresentabile in complemento a 1. Questo comunque è vero anche per NOT) la rappresentazione modulo e segno. Esempio: numeri a 4 bit (complemento Somma algebrica (complemento a 1) a 1) -7 1000 Con il complemento a 1 la somma algebrica diventa un’operazione -6 1001 molto naturale. -5 1010 -4 1011 Si implementa, infatti, come una normale addizione ma con la -3 1100 complicazione che un eventuale riporto al bit in posizione N (che non -2 1101 è immagazzinabile) deve essere nuovamente addizionato al risultato -1 1110 (operazione detta end-around carry) -0 1111 +0 0000 Ad esempio, effettuiamo la somma tra i numeri –110 e +210 a 8 bit +1 0001 +2 0010 Il numero +210 è rappresentato in complemento a 1 a 8 bit come +3 0011 000000102 +4 0100 +5 0101 La rappresentazione del numero –110 in complemento a 1 a 8 bit può +6 0110 essere ottenuta considerando quella di +110 su 8 bit ovvero +7 0111 000000012 e invertendo tutti i bit: –1 = 11111110 Somma algebrica (complemento a 1) Complemento a 1: problemi Il risultato della semplice addizione tra –110 e +210 sarebbe: Utilizzare il complemento a 1 per rappresentare i numeri negativi riduce solo in parte i due problemi visti con la 1 1 1 1 1 1 1 0 + rappresentazione modulo e segno: ○ E’ vero che la somma algebrica si implementa sempre con 0 0 0 0 0 0 1 0 = una addizione ma c’è il problema del end-around carry 1 0 0 0 0 0 0 0 0 che complica l’implementazione a livello elettronico ovvero, senza tenere conto del riporto, 010. ○ Sono comunque presenti due rappresentazioni per lo zero ovvero: Trasportando il riporto (bit in posizione 8) indietro fino alla 010 = 000000002 = 111111112 prima cifra (posizione 0) e sommandolo, invece, si ottiene il risultato corretto ovvero: 000000012 = +110 Esempio: numeri a 4 bit (complemento Complemento a 2 a 2) La tecnica utilizzata nei moderni calcolatori per rappresentare -8 1000 numeri interi negativi è il complemento a 2 -7 1001 -6 1010 Dati N bit è possibile rappresentare numeri nell’intervallo: -5 1011 [–2N-1, 2N-1 –1] -4 1100 -3 1101 Data la rappresentazione a N bit di un numero positivo nell’intervallo -2 1110 [0, 2N-1–1] -1 1111 il suo corrispondente negativo si può ottenere in due modi: +0 0000 semplicemente invertendo tutti i bit e addizionando uno +1 0001 oppure andando dal bit meno significativo verso sinistra, +2 0010 trovando il primo 1 e invertendo tutti i bit successivi +3 0011 +4 0100 Ad esempio, dato il numero 4310 ovvero (con 8 bit) 001010112 +5 0101 allora il numero −4310 diventa 110101012 +6 0110 +7 0111 Somma algebrica (complemento a 2) Somma algebrica (complemento a 2) Con il complemento a 2 la somma algebrica si trasforma in Il risultato della semplice addizione tra –110 e +210 sarebbe: un’addizione senza alcuna ulteriore complicazione. Ad esempio, effettuiamo la somma tra i numeri –110 e +210 a 8 bit 1 1 1 1 1 1 1 1 + 0 0 0 0 0 0 1 0 = Il numero +210 è rappresentato in complemento a 2 a 8 bit come 1 0 0 0 0 0 0 0 1 000000102 ovvero, senza tenere conto del riporto: La rappresentazione del numero –110 in complemento a 2 a 8 bit può essere ottenuta considerando quella di +110 su 8 bit ovvero 000000012 = +110 000000012, invertendo tutti i bit e sommando 1: –110 = 111111112 Complemento a 2 Il complemento a 2 risolve tutti i problemi visti finora: ○ la somma algebrica è implementabile con una semplice addizione ○ non è necessario effettuare alcun end around carry ○ c’è una sola rappresentazione per lo 010 ovvero, ad esempio ad 8 bit, 000000002 (nota che di questo numero Codifica di numeri Reali non è calcolabile il complemento a 2 su 8 bit) Nota: ○ il numero 100000002 che nella rappresentazione modulo e segno equivarrebbe a –010 può essere utilizzato per rappresentare un numero negativo aggiuntivo ovvero (nel caso di 8 bit) il numero –12810 Numeri reali Virgola fissa e mobile Un numero reale è composto da: Ci sono due metodi principali di rappresentazione dei reali ○ parte intera (prima della virgola o punto) nel calcolatore: ○ parte decimale o frazionaria (dopo la virgola o punto) ○ Rappresentazione in virgola fissa In un numero reale, le cifre della parte frazionaria possono essere ○ Rappresentazione in virgola mobile: infinite (numero irrazionale o numero razionale periodico) Nel calcolatore, non è possibile rappresentare esattamente un La rappresentazione in virgola mobile è quella utilizzata nei numero reale irrazionale o razionale periodico (ovvero con infinite calcolatori moderni ed esiste uno standard (IEEE 754) che la cifre nella parte frazionaria) definisce Dobbiamo approssimare con un numero razionale non periodico vicino ovvero con un numero reale in cui le cifre della parte frazionaria sono in numero finito (troncamento) Rappresentazione in virgola fissa Esempio Viene utilizzato un bit di segno, I bit per la parte intera e D Vogliamo convertire il seguente numero in rappresentazione bit per la parte frazionaria binaria a virgola fissa (con I=4 e D=4) in rappresentazione decimale: 10011.01102 +/- I-1 I-2 … 0 -1 -2 … -D Segno Parte intera Parte frazionaria Si ha: ○ Segno: 1 ○ Parte intera: 1*20+1*21+0*22+0*23 = 1 + 2 = 3 Quindi un numero N in base due è scritto come: ○ Parte decimale: 0*2-1+1*2-2+1*2-3 = 0.25 + 0.125 = 0.375 N2 = s aI-1 aI-2 … a0 b-1 b-2 … b-D Quindi il numero in rappresentazione decimale è: Se vogliamo convertirlo in base decimale: -3.37510 N10 = (-1)s * (aI-1*2I-1 + … + a1*21 + a0*20 + + b-1*2-1 + b-2*2-2 + … + b-D*2-D ) Esempio Underflow Vogliamo convertire il seguente numero in rappresentazione Il termine arithmetic underflow (anche floating point underflow, o semplicemente underflow) è una condizione in cui il risultato di un calcolo è binaria a virgola mobile IEEE 754 a precisione singola in un numero con un valore assoluto più preciso di quanto il calcolatore possa rappresentazione decimale: effettivamente rappresentare. ○ 010000000100100100001111110110112 L'underflow aritmetico può verificarsi quando il vero risultato di un'operazione in virgola mobile è più piccolo in grandezza (cioè, più vicino a Soluzione: zero) rispetto al valore minimo rappresentabile come numero in virgola mobile. ○ 3.141592710 L'underflow può in parte essere considerato come un overflow negativo dell'esponente del valore in virgola mobile. Ad esempio, se la parte esponente può rappresentare valori da −128 a 127, un risultato con un valore inferiore a −128 può causare un underflow. Per gli interi, il termine integer underflow si riferisce tipicamente a un tipo speciale di overflow degli interi, in cui il risultato di una sottrazione porterebbe a un valore inferiore al minimo consentito per un determinato tipo di intero, ossia il risultato ideale sarebbe più vicino a meno infinito rispetto al valore rappresentabile più vicino a meno infinito per il tipo di output. George Boole George Boole (Lincoln, 2 novembre 1815 – Ballintemple, 8 dicembre 1864) è stato un matematico e logico britannico, ed è considerato il fondatore della logica matematica. La sua Operatori logici e algebra di Boole opera influenzò anche settori della filosofia e diede vita alla scuola degli algebristi della logica. Primo estimatore e continuatore della sua opera fu Augustus de Morgan. L'opera maggiore di Boole è stata la base (grazie a Claude Shannon, che ha riconosciuto la coincidenza tra il funzionamento dei circuiti commutatori e la logica proposizionale), degli studi sui circuiti elettronici e sulla commutazione, e ha costituito un passo importante verso la concezione dei moderni computer. Algebra booleana Funzioni booleane In matematica e logica matematica l'algebra di Boole, anche detta algebra In matematica e in informatica, una funzione booleana a n variabili è booleana, è il ramo dell'algebra in cui le variabili possono assumere una funzione tale che: solamente i valori vero e falso (valori di verità), generalmente denotati come ○ le n variabili sono booleane ovvero possono assumere 1 e 0 rispettivamente. (Wikipedia, 2017) esclusivamente i valori 0 e 1 ○ gli operatori coinvolti sono esclusivamente quelli booleani Esistono 3 principali operatori nell’ambito dell’algebra booleana: ovvero NOT, AND e OR o loro derivati ○ NOT (negazione logica) ○ AND (prodotto logico) Ovviamente anche la funzione può assumere esclusivamente i valori 0 ○ OR (somma logica) e1 Con tale formalismo si possono descrivere le relazioni logiche in modo simile a quanto fa l'algebra ordinaria con le relazioni numeriche: la Più formalmente una funzione booleana f a n variabili è definita come: combinazione di AND, OR e NOT permette di sviluppare qualsiasi funzione booleana e i tre operatori logici formano pertanto un insieme f(x0, x1, …, xn-1) : Bn →B con B = {0,1} funzionalmente completo. Tabella di verità Esempio Strumento utile alla rappresentazione di funzioni booleane Consideriamo una ipotetica funzione booleana Y a tre variabili A, B e C La tabella di verità elenca tutte le possibili combinazioni di valori che possono assumere le variabili booleane coinvolte nella funziona ed il La sua tabella di verità avrà 8 righe risultato della funzione stessa A B C Y Se le variabili coinvolte nella funzione sono n, la tabella di verità sarà 0 0 0 0 caratterizzata da 2n righe riportando il risultato della funzione per 0 0 1 1 quella particolare combinazione 0 1 0 0 0 1 1 0 1 0 0 1 1 0 1 1 1 1 0 1 1 1 1 0 Operatori booleani: NOT (negazione) Operatori booleani: AND (congiunzione) L'operatore NOT restituisce il valore inverso a quello in entrata. Una L'operazione AND restituisce come valore 1 se tutti gli operandi hanno concatenazione di NOT è semplificabile con un solo NOT in caso di valore 1, mentre restituisce 0 in tutti gli altri casi. Tale operazione è anche dispari ripetizioni o con nessuno nel caso di pari. detta prodotto logico. Nella teoria degli insiemi corrisponde all'intersezione. Possibili notazioni: ○ NOT A Possibili notazioni: ○ !A ○ A AND B ○ -A ○ A&B ○ ¬A ○ A*B ○ Ā ○ A∧B A B Y= A AND B Tabella di verità: Tabella di verità: 0 0 0 A Y = NOT A 0 1 0 0 1 1 0 0 1 0 1 1 1 Operatori booleani: OR (disgiunzione) Altri operatori booleani L'operazione logica OR restituisce 1 se almeno uno degli elementi è 1, mentre Gli operatori booleani AND, OR e NOT possono essere combinati tra loro per restituisce 0 in tutti gli altri casi. Tale operazione è anche detta somma logica. ottenere altri operatori più complessi ma utilizzati altrettanto spesso Nella teoria degli insiemi corrisponde all'unione. In logica booleana due funzioni si dicono equivalenti se hanno la medesima Possibili notazioni: tabella di verità ○ A OR B ○ A|B Operatori aggiuntivi: ○ A+B ○ A XOR B (equivalente a A * !B + !A * B) ○ A∨B ○ A NAND B (equivalente a !(A AND B)) ○ A NOR B (equivalente a !(A OR B)) Tabella di verità: A B Y= A OR B ○ A XNOR B (equivalente a !(A XOR B)) 0 0 0 0 1 1 1 0 1 1 1 1 Operatori booleani: XOR Esempio di funzione booleana L'operatore XOR, detto anche OR esclusivo, restituisce 1 se e solo se il Consideriamo la funzione numero degli operandi uguali a 1 è dispari, 0 in caso contrario. In generale, ci Y = A * B + !A * C si riferisce a questo operatore come operatore di disparità. e scriviamone la tabella di verità Possibili notazioni: ○ A XOR B A B C A*B !A !A*C Y ○ A⊕B 0 0 0 0 1 0 0 Tabella di verità: A B Y= A XOR B 0 0 1 0 1 1 1 0 1 0 0 1 0 0 0 0 0 0 1 1 0 1 1 1 0 1 1 1 0 0 0 0 0 0 1 0 1 1 0 1 0 0 0 0 1 1 0 Esercizio utile: verificare che A XOR B = A * ! B + !A * B tramite tabelle di verità. 1 1 0 1 0 0 1 1 1 1 1 0 0 1 Esercizio Esercizio Consideriamo la funzione Consideriamo la funzione Y = (A + C)*(A + !B) Y = (A + C)*(A + !B) e scriviamone la tabella di verità e scriviamone la tabella di verità A B C Y 0 0 0 0 0 0 1 1 0 1 0 0 0 1 1 0 1 0 0 1 1 0 1 1 1 1 0 1 1 1 1 1  Charset Una codifica di caratteri, o charset, consiste in un codice che associa un insieme di caratteri (tipicamente rappresentazioni di grafemi così come appaiono in un alfabeto utilizzato per comunicare in una lingua naturale) ad un insieme di altri oggetti, come numeri (specialmente nell'informatica) o pulsazioni elettriche, con lo scopo di facilitare la memorizzazione di un testo in un computer o la sua trasmissione attraverso una rete di telecomunicazioni. (Wikipedia, 2017) Codifica dei caratteri Esempi di codici per i caratteri nel corso della storia sono: 1840: Codice Morse 1857: Codice Internazionale Nautico (tramite bandiere) 1930: Codice Baudot (telescriventi) 1963: Codice ASCII 1981: estensioni del Codice ASCII 1991: Unicode 1.0 1996: Unicode 2.0 1999: Unicode 3.0 2001: Unicode 4.0 (include le lingue antiche) Tabella ASCII base Tabella ASCII base La prima codifica che associa a caratteri dell’alfabeto inglese delle stringhe di bit è la tabella ASCII, inventata nel 1961 da un ingegnere dell’IBM, Robert Bemer ma pubblicata solo nel 1963 ASCII sta per American Standard Code for Information Interchange La tabella ASCII di base utilizzava solo 7 bit e associava ai 128 interi rappresentabili una serie di caratteri 128 caratteri bastavano per le lettere dell’alfabeto inglese, che non ha accentate o caratteri speciali, con l’aggiunta di qualche decina di caratteri invisibili come gli “a capo”, le “tabulazioni”, etc. Esempio di codifica di un testo Tabella ASCII estesa Negli anni è diventato evidente che la tabella ASCII di base non era sufficiente per lingue diverse dall’inglese Come primo tentativo si è provato ad espanderla con una tabella ASCII estesa, che, sfruttando l’ottavo bit prima utilizzato per altri scopi, consentiva di definire altri 128 caratteri, fra cui le vocali accentate Questi 256 caratteri non erano sufficienti nemmeno considerando solo gli alfabeti europei! Tabella ASCII estesa ISO 8859 Una prima soluzione è stata di mantenere stabile la tabella ASCII di base (i primi 128 caratteri, corrispondenti all’alfabeto inglese) e di prevedere diverse tabelle ASCII estese per i diversi alfabeti L’ISO, ente di standardizzazione internazionale, ha così definito le tabelle di codifica cosiddette ISO 8859 con 14 varianti, ognuna con una diversa tabella estesa La tabella ISO 8859-1, detta Latin-1, è quella che siamo più spesso abituati ad usare, perché contiene le vocali accentate più comuni, quelle in uso in Italia, Francia, Spagna Altre ISO 8859 sono usate nella Repubblica Ceca, in Russia, etc. La soluzione “multi-tabella estesa” può andar bene solo se in un documento inseriamo solo caratteri provenienti da solo uno degli alfabeti considerati! Unicode e ISO 10646 Unicode e ISO 10646 Una soluzione migliore è venuta da Unicode, un ente che si è posto il problema di In Unicode sono possibili diverse codifiche di carattere descrivere in un’unica tabella, o meglio, in uno spazio concettuale, tutti i caratteri esistenti in tutti gli alfabeti noti Esse si riferiscono sempre al medesimo repertorio di caratteri ma Con Unicode entra in gioco in maniera chiara la distinzione fra repertorio dei usando un numero di byte differente caratteri (tutti i caratteri descritti nel sistema Unicode) e codifica del carattere Una codifica Unicode universale, che utilizza 4 byte per tutti i Le due cose coincidevano in pratica con il sistema ASCII o ISO 8859 caratteri, è la UCS-4 ma è usata raramente nei documenti perché Unicode definisce in maniera univoca la corrispondenza fra un preciso carattere e un testo latino occuperebbe 4 volte lo spazio della codifica ASCII un numero che rappresenta le coordinate di quel carattere nello “spazio unicode”, cioè nel repertorio di caratteri Codifiche più usate sono la codifica UTF-8 e la UTF-16. Il modo in cui i numeri sono rappresentati da byte in un determinato documento La UTF-16 utilizza 2 byte per memorizzare i primi 65536 caratteri e però dipende dalla codifica di carattere scelta 4 byte per tutti gli altri L’intero repertorio dei caratteri definiti in Unicode è stato recepito dalla ISO 10646 Unicode e ISO 10646 UTF-8 sfrutta invece una importante caratteristica di Unicode, quella di essere parzialmente compatibile con la tabella ASCII UTF-8 può infatti usare un solo byte per i primi 128 caratteri, quelli dell’ASCII base, usare 2 byte per memorizzare altri 1920 caratteri, corrispondenti al latino esteso, al cirillico, greco, romanico, etc., e 3 byte per i successivi 63488 caratteri (inclusi molti ideogrammi orientali) Un’altra caratteristica interessante della codifica UTF-8 è che quando usa più di un byte per codificare un carattere, nessuno dei due byte, preso singolarmente, può venir scambiato per un byte ASCII Questo evita fraintendimenti fastidiosi per i sistemi operativi e i programmi che non comprendono UTF-8 Si tratta dunque di un’ottima codifica per noi occidentali, equivalente (e compatibile) all’ASCII per le lingue latine e in grado tuttavia di rappresentare in un medesimo documento qualunque carattere disponibile nel repertorio Unicode  La realtà è analogica Tutti i fenomeni fisici appaiono ai nostri occhi come analogici! Ad esempio, l’intensità del suono (ovvero il livello di pressione sonora), misurata solitamente in Decibel (dB), è una quantità continua nell’intervallo [0, 300] dB Digitalizzazione di suoni e immagini 0 dB è la soglia dell’udibile e 300 dB è l’intensità sonora del rumore prodotto da un vulcano in eruzione Altro esempio è lo spettro dei colori: nonostante comunemente si pensi che esistano 7 colori primari (quelli dell’arcobaleno!), lo spettro del visibile è continuo nell’intervallo [400, 789] THz 400 THz è la frequenza del rosso mentre 789 THz corrisponde al violetto Digitalizzazione Digitalizzazione La digitalizzazione è il processo di conversione che, applicato alla misurazione di un La digitalizzazione, o conversione analogico-digitale, è un processo complesso che fenomeno fisico, ne determina il passaggio dal campo dei valori continui a quello dei richiede svariate fasi valori discreti. Tale processo viene oggi comunemente sintetizzato nei termini di passaggio dall'analogico al digitale. (Wikipedia, 2017) L'idea che sta alla base della digitalizzazione è la seguente: ○ qualsiasi grandezza fisica di interesse (tensione, corrente, pressione, Nel campo dell'informatica e dell'elettronica, con digitalizzazione si intende il velocità...) viene misurata e il valore della sua misura codificato come numero processo di trasformazione di un'immagine, di un suono, di un documento in un binario formato digitale, interpretabile da un computer, dove per formato digitale si intende ○ se la grandezza assume diversi valori nel tempo, essa sarà misurata a intervalli un codice binario in cui tutto è rappresentato da combinazioni di zero o uno, quindi regolari, dando luogo ad una sequenza di numeri binari da stati del tipo acceso/spento. (Wikipedia 2017) Un disco in vinile su cui è registrata una canzone rappresenta un esempio di riproduzione analogica del suono La stessa canzone riprodotta nel formato MP3 tramite un computer rappresenta un esempio di riproduzione digitale  Consiste nel prelevare dei campioni dal segnale analogico sorgente Conversione analogico-digitale Campionamento Generalmente il campionamento è uniforme (fatto ad intervalli di tempo regolari) Possiamo individuare tre fasi principali: L’intervallo di tempo (che determina gli istanti in cui si ○ Campionamento preleva il campione) è detto periodo di campionamento ○ Quantizzazione ○ Codifica Ognuna di esse è realizzata da un opportuno circuito integrato Quantizzazione Codifica Consiste nell’associare a ciascun campione un valore Consiste nell’associare a ciascun valore quantizzato una appartenente ad un intervallo limitato e discreto (ovvero con parola codice numero finito di punti) Il segnale analogico viene quindi convertito in una sequenza L’intervallo dei valori viene spesso suddiviso in parti uguali di bit (quantizzazione uniforme) Digitalizzazione del suono Parametri e compressione Lo schema generale del ciclo di vita del suono digitale è il Tre sono i parametri che caratterizzano il campionamento del suono influenzando sia lo spazio di memoria occupato che la qualità del suono: seguente: ○ numero di canali: può essere mono (un solo canale), stereo (due canali), surround (5 o più canali) ○ risoluzione: solitamente si utilizzano 8 o 16 bit per campione - nel primo caso la qualità del suono è inferiore a quella di un nastro mentre nel secondo la qualità è ottimale ○ frequenza di campionamento: può variare da 11 kHz adatta alla registrazione della voce, a 22 kHz adatta alla registrazione di un nastro fino a 44 kHz per una registrazione a qualità CD Nel caso specifico del suono è spesso necessario applicare tecniche di compressione per ridurre l’occupazione di memoria: ○ MP3 ○ Advanced Audio Coding ○ Ogg Vorbis ○ FLAC Digitalizzazione delle immagini Risoluzione Nel caso delle immagini il campionamento, la quantizzazione Una immagine digitale è costituita da una matrice di punti detti picture elements (pixel), simili ai punti della retinatura nelle immagini a stampa e la codifica avvengono sia nello spazio che nello spettro dei colori Tanto più fitta è la griglia (più numerosi sono i pixel) tanto migliore è la risoluzione dell’immagine  La profondità di colore è data dal numero di bit utilizzati per rappresentare il colore di ciascun pixel Dots per inch Profondità di colore Profondità di colore utilizzate spesso sono: La risoluzione (e dunque la qualità del dettaglio) di un’immagine è tanto maggiore ○ 1 bit: immagine in bianco e nero quanto più grande è il numero di pixel in una data area Essa si esprime come numero di pixel per unità di lunghezza verticale e ○ 8 bit: immagine con 256 livelli di colore o toni di grigio orizzontale misurata in dots per inch (DPI) ○ 16 bit: immagine a circa 65 mila colori ○ 75 x 75 DPI ○ 24 bit: immagine a circa 16 milioni di colori ○ 300 x 300 DPI ○ 600 x 600 DPI Esistono svariati formati che applicano compressioni più o meno potenti sulle immagini per ridurre lo spazio occupato: Formati più comuni ○ BMP (nessuna compressione) ○ JPG/JPEG (compressione lossy ovvero con perdita di qualità) ○ GIF (adatto per immagini a pochi colori anche in movimento) ○ PNG (alternativa open source a GIF) Esercizi