Biomedical Engineering - Informatica Medica

Fondamenti di Informatica - Rappresentazione Binaria

Divided by topic

Fondamenti di informatica – Prof. Roveri Rappresentazione binaria Numeri e caratteri Algoritmi = istruzioni + dati. Per scrivere un programma che descriva un algoritmo è necessario rappresentare istruzioni e dati utilizzando un formato che il calcolatore sia in grado di: 1) memorizzare, 2) elaborare, 3) trasmettere. Codice (semantica) = insieme di regole che ad ogni configurazione ammissibile associa un’entità d’informazione. Lo stesso alfabeto può essere utilizzato con codici diversi . Il calcolatore utili zza un alfabeto binario: usiamo dispositivi elettronici digitali in grado di assumere due soli stati: acceso/spento, on /off, 1/0, vero/falso. Un alfabeto binario non limita le funzionalità di un calcolatore. Il simbolo o cifra binaria si indica con bit (Bi nary digIT): è la quantità d’informazione che si ottiene selezionando una configurazione da un insieme che ne contiene due. La risposta “sì” oppure “no” a una domanda porta 1 bit d’informazione. Il calcolatore tratta diversi tipi di dati (numeri, caratteri , ecc.) tutti rappresentati con la codifica binaria. Problema: assegnare un codice univoco a tutti gli oggetti compresi in un insieme predefinito. Quanti oggetti diversi posso codificare con parole binarie composte di k bit? 2k stati -> 2k oggetti. Quanti bit mi servono per codificare N oggetti ? N ≤ 2k→ k≥ log 2N → k= ⌈log 2N⌉. Ipotesi implicita: le parole di un codice hanno tutte la stessa lunghezza. 1 Byte = 8 bit -> 256 stati Ecc.. Quanti sono gli oggetti da rappresentare? 26 lettere maiuscole, 26 lettere minusco le, 10 cifre, circa 30 simboli d’interpunzione, circa 30 caratteri di controllo. In totale circa 120 oggetti -> k=7. Per la codifica dei caratteri e delle stringhe (sequenze di caratteri come parole e frasi) si sfruttano delle convenzioni che associano un valore numerico ad ogni carattere. Le più diffuse sono:  Codice ASCII (American Standard Code for Information Interchange) utilizza 7 bit, può rappresentare 126 caratteri detti caratteri ASCII standard.  Codice ASCII esteso utilizza 8 bit (1 Byte), può rappr esentare 256 caratteri detti caratteri ASCII estesi (comprende i caratteri ASCII standard con alcuni caratteri semigrafici).  Convenzione UNICODE: sfrutta 16 bit per rappresentare fino a 65'536 caratteri, utile nel caso di alfabeti particolarmente compless i quale quello cinese. ASCII estesa: Codifica dei numeri naturali: Notazione posizionale : permette di rappresentare un qualsiasi numero naturale (intero non negativo) nel modo seguente: sequenza di cifre ci: cn cn−1… c1 rappresenta un base B ≥2 il valore cn× Bn−1+ cn−1× Bn−2+ ⋯ + c1× B0. La notazione decimale tradizionale è di tipo posizione con B=10. Base generica: B. A = {…} con |A|=B, insieme di n simboli (cifre) con cui rappresentiamo Bn numeri. Esempio: “ventinove” in varie basi: B = otto, A={0 ,1,2,3,4,5,6,7} 29 10 = 35 8 B = cinque, A={0,1,2,3,4} 29 10 = 104 5 B = tre, A={0,1,2} 29 10 = 1002 3 B = sedici, A ={0,1,…,9,A,B,C,D,E,F} 29 10 = 1D 16 Codifica binaria : usata dal calcolatore per tutte le informazioni. B=2, A={0,1}. La sequenza di bit bi bn bn−1… b1 rappresenta in base 2 il valore: bn× 2n−1+ bn−1× 2n−2+ ⋯ + b1× 20. Conversione binario -> decimale , esempi: - N= 1101 2=1× 23+ 1× 22+ 0× 21+ 1× 20= 8+ 4+ 1= 13 10 - N= 100101 2=1× 25+ 0× 24+ 0× 23+ 1× 22+ 0× 21+ 1× 20= 32 + 4+ 1= 37 10 Conversione decimale -> binario : si calcolano i resti della divisione per due finché il risultato di una divisione diventa 0 , esempio: N= 23 10: - 23:2=11, R0=b0=1 - 11:2=5, R1=b1=1 - 5:2=2, R2=b2=1 - 2:2=1, R3=b3=0 - 1:2=0, R4=b4=1  23 10 = 10111 2 Esempio: N= 18 10: - 18:2=9, R0=b0=0 - 9:2=4, R1=b1=1 - 4:2=2, R2=b2=0 - 2:2=1, R3=b3=0 - 1:2=0, R4=b4=1  18 10 = 10010 2 Non esiste il concetto di infinito nel calcola tore: l’insieme di numeri rappresentabili è finito e dipende dal numero di bit disponibili. Codifica binaria su n bit: con una sequenza di n bit si possono rappresentare 2n numeri interi assoluti da 0 a 2n− 1. La lunghezza delle sequenze di bit adottate stabilisce il massimo numero che può essere rappresentato. Con 1 Byte (cioè una sequenza di 8 bit): 00000000 bin = 0dec 00001000 bin = 8dec 00101011 bin = 43 dec 11111111 bin = 255 dec Aumento dei bit: premettendo in modo progressivo un bit 0 a sinistra, il valore del numero non cambia. Riduzione dei bit: cancellando in modo progressivo un bit 0 a sinistra, il valore del numero non muta, ma bisogna arrestarsi quando si trova un bit 1. Qu esto è importante nella codifica di numeri interi. Nella codifica Modulo e Segno il primo bit a sinistra rappresenta il segno del numero (bit di segno) e i bit rimanenti rappresentano il valore. Il bit di segno è applicato al numero rappresentato ma non f a propriamente parte del numero. Esempio con n=9 (8 bit + 1 bit per il segno): 000000000 m&s = +0dec 000001000 m&s = +8dec 100001000 m&s = −8dec Con 8 bit posso codificare i numeri da 0 a 255; con la codifica m&s, con 9 bit codifico da -255 a +255. Non si usa molt o perché ci sono due rappresentazioni per lo 0: 000000000 m&s e 100000000 m&s . Non c’è quindi rappresentazione biunivoca e ciò causa una serie di inefficienze. Per questo si usa la codifica Complemento a 2 . Il primo bit a sinistra non è un bit di segno ma ha un peso negativo mentre tutti gli altri hanno peso positivo . La sequenza di bit ������������ ������������ ������������−1… ������1 rappresent a in C2 il valore: bn× (−2n−1)+ bn−1× 2n−2+ ⋯ + b1× 20. Il bit più a sinistra è ancora chiamato bit di segno. Non c’è differenza tra un numero natur ale e un numero in complemento a 2 se il numero è positivo, la codifica è la stessa. Numero a 3 bit in C2: 000 C2 = −0× 22+ 0× 21+ 0× 20= 0dec 001 C2 = −0× 22+ 0× 21+ 1× 20= 1dec 010 C2 = −0× 22+ 1× 21+ 0× 20= 2dec 011 C2 = −0× 22+ 1× 21+ 1× 20= 3dec 100 C2 = −1× 22+ 0× 21+ 0× 20= −4dec 101 C2 = −1× 22+ 0× 21+ 1× 20= −3dec 110 C2 = −1× 22+ 1× 21+ 0× 20= −2dec 111 C2 = −1× 22+ 1× 21+ 1× 20= −1dec NB: in base al bit di segno, lo zero è considerato positivo! Il primo vantaggio è che non ci sono due configurazioni per lo zero . Il secondo è che a parità di bit, si ha a disposizione una codifica in più (nel caso di 3 bit, è -4). L’inverso additivo (o opposto) di un numero di C2 si ottiene invertendo (negando) ogni bit del numero e sommando +1 alla posizione meno significativa : 01011 C2 = 1× 23+ 1× 21+ 1× 20= 8+ 2+ 1= 11 dec 10100 + 1= 10101 C2 = −1× 24+ 1× 22+ 1× 20= −16 + 4+ 1= −11 dec Importante: 1) con due applicazioni dell’algoritmo si riottiene il numero iniziale [ -(-A)=A], 2) lo zero in C2 è (correttamente) opposto di sé stesso. Se il numero che voglio codificare è positivo, non cambia nulla, per ché la codifica è la stessa (a meno di uno 0 all’inizio). Se il numero è negativo non cambia nulla lo stesso: codifico la versione positiva, aggiungo uno 0 all’inizio e la inverto. Il segno è incorporato nel numero rappresentato in C2, non è semplicemente applicato come in m&s. Il bit più significativo rivela il segno: 0 per numero positivo, 1 per numero negativo (il numero 0 è considerato positivo). NB: se il numero è negativo, NON si può distaccare il bit più significativo e dire che i bit rimanenti rappresentano il valore assoluto del numero . Intervalli di rappresentazione: o Binario naturale a n ≥1 bit: [0, 2n) o Modulo e segno a n ≥2 bit: ( −2n−1, 2n−1): il numero 0 ha due rappresentazioni equivalenti, (00…0, 10…0). o C2 a n ≥2 bit: [ −2n−1, 2n−1): l’intervallo è asimmetrico. Numeri frazionari in virgola fissa : La sequenza di bit rappresentante un numero frazionario consta di due parti di lunghezza prefissata ; il numero di bit a sinistra e a destra della virgola è stabilito a priori, anche se alcuni bit restassero nulli. È un sistema di rappresentazione semplice ma poco flessibile e può condurre a sprechi di bit . Per rappresentare il virgola fissa numero molto grandi (oppure molto precisi) occorrono molti bit. Esempio: 19 ,6875 dec = 1× 24+ 1× 21+ 1× 20+ 1× 2−1+ 1× 2−3+ 1× 2−4= 16 + 2+ 1 2+ 1 8+ 1 16 = 10011 ,1011 virgola fissa Numeri frazionari in virgola mobile : La rappresentazione in virgola mobile (o floating point) è usata spesso in base 10 (notazione scientifica). Il vantaggio è che è molto compatta. Esempio: 0,137 × 10 8not .scientifica = 13 .700 .000 dec La rappresentazione binaria si basa sulla relazione: Segnali audio Le onde sonore sono segnali continui. Devono essere discretizzate: - Discretizzazione del tempo , campionamento : scelta di istanti in cui considerare il valore del segnale. - Discretizzazione delle ampiezze , quantizzazione: codifica dei campioni con un numero predefinito di bit. Campionamento . Si misura l’ampiezza del segnale analogico a intervalli regolari, ogni T secondi . T è detto periodo di campionamen to (in secondi). F=1/T è detta frequenza di campionamento (in Hz). La frequenza di campionamento dipende dalla dinamica del segnale: se il segnale cambia rapidamente necessito di una F elevata. Un campionamento più fitto (ovvero con una frequenza di campio namento maggiore) consente di rappresentare i segnali analogici con maggiore fedeltà. Per segnali audio di tipo vocale, la frequenza di campionamento è tipicamente 8kHz. Per segnali audio musicali, la frequenza di campionamento è tipicamente 44.1kHz. Tanto più la frequenza è alta, tanto più avrò bisogno di memoria . Inoltre, raggiunta una certa soglia di frequenza si misura il segnale in modo ottimale, è inutile aggiungere informazione in eccesso. Quantizzazione . I campioni estratti con la quantizzazione rappresentano le ampiezze con precisione arbitraria . Per poter essere rappresentato da un calcolator e, il valore dell’ampiezza deve essere espresso tramite un numero finito di bit. La quantizzazione suddivide l’intervallo dei valori ammissibili in 2k bit , d ove k è il numero di bit per campione. La figura mostra una quantizzazione a 3 bit/campione. Errore di quantizzazione : differenza tra valore originale e l’ampiezza associata. Più è elevato k, più l’intervallo delle ampiezze diminuisce, quindi l’errore di quantizzazione diventa più piccolo. Tuttavia, k elevato implica un elevato utilizzo di memoria . Esempio: brano musicale su CD. F = 44100 Hz, 16 bit/campione. 2 canali (destro e sinistra9: 2x16x44100 = 1411200 bit/s -> 176 Kbyte/s. 1 canzone, circa 5 minuti -> 176 Kbyte/s x 60s/min x 5min -> circa 52 M byte. 60 minuti di musica -> 176x60x60 -> circa 630 M byte. Un file mp3 di una canzone da 5 minuti sono circa 5 M byte -> fattore d i compressione di circa 10:1. L’accuratezza della ricostruzione dipende: - da quanto sono piccoli gli intervalli di campionamento; - da quanti bit uso per descrivere il suono in ogni campione; - ricorda: maggiore accuratezza significa maggior quantità di memori a occupata! Anche per i suoni si possono utilizzare tecniche (lossless o lossy) di compressione per migliorare l’occupazione di memoria della sequenza di campioni. Le tecniche più efficaci sfruttano le “debolezze” dell’orecchio umano. Esempio: MPEG -1/2 Layer 3, detto anche MP3. Rappresentazione di immagini Il calcolatore non può direttamente rappresentare in memoria informazione continua. Le immagini devono essere prima “ discretizzate ” ovvero trasformate in un insieme di parti distinte, che possono poi essere codificate separatamente sotto forma di numeri. Tipologie: - immagini scalari o raster, es. foto; - immagini vettoriali, es. un disegno geometrico. Immagini raster . Chiamiamo risoluzione dell’immagine la dimensione della griglia utilizzata per discret izzare l’immagine (es. 640x480). Il pixel è l’unità di informazione più piccola che ho all’interno di un’immagine . Aumentando la risoluzione (ovvero il numero di pixel) e quindi diminuendo la dimensione del singolo pixel, la rappresentazione approssima meg lio l’immagine originaria. Dopo aver discretizzato l’immagine, occorre rappresentare ogni pixel con un numero . Tale numero dovrà rappresentare il colore associato al pixel, utilizzando un certo range: si parla di quantizzazione. Per immagini in bianco e nero senza sfumature sono sufficienti un solo bit per ogni pixel: 0 per rappresentare i pixel più bianchi, 1 per rappresentare i pixel più neri. Per immagini in bianco e nero con sfumature, si usa la rappresentazione in “toni di grigio”: un byte per pixel , con 256 gradazioni di grigio per ogni pixel, o più byte per pixel, per avere più gradazioni possibili. Per immagini a colori, si usa la rappresentazione del colore secondo il modello RGB (red, green, blue): sintesi additiva dei tre colori primari ognuno con la propria codifica ; i primi 8 bit codificano il rosso, i secondi 8 il verde, gli ultimi 8 il blu. Profondità cromatica = numero di bit per ogni pixel (di norma 24, ovvero un byte per ogni colore). La risoluzione e la profondità cromatica determinano la dimensione di memoria necessaria a memorizzare l’immagine . Esempio: 1024x768 pixel toni di grigio/pixel = 1024x768 pixel x 8 bit/pixel = 768 K byte. Se l’immagine è a colori, per esempio 1024x768 pixel x 3 componenti /pixel x256 toni/component e = 1024x768 pixel x 3 componenti/pixel x 8 bit/pixel = 2304 Kbyte . In fase di codifica esiste la necessità di adottare tecniche di compressione per ottimizzare l’occupazione di spazio di memoria e la velocità di trasmissione attraverso la rete.  Le tecnic he di compressione lossless (senza perdita di informazione) sono reversibili, ad hoc per immagini (es. PNG) o applicabili a qualsiasi tipo di dato, ad es. codifiche basate sulla frequenza statistica dei dati: i dati più frequenti vengono codificati con seq uenze di bit più brevi (ZIP).  Gli algoritmi lossy (con perdita di informazione) sono generalmente specifici di un certo campo e sfruttano le caratteristiche degli oggetti da rappresentare per “buttare via” informazioni poco importanti. Nel caso di immagini , gli algoritmi usati nei formati JPEG sfruttano la caratteristica dell’occhio umano di essere poco sensibile a lievi cambiamenti di colore in punti contigui, e quindi eliminano questi lievi cambiamenti “appiattendo” il colore dell’immagine. Generalmente è possibile specificare quanto siamo disposti a perdere attraverso alcuni parametri. Principali formati di compressione per immagini raster: - TIFF (Tagged Image File Format): uso di tag (etichette) descrittivi, 24 bit/pixel, compressione senza perdita; - GIF (Graphics Interchange Format, Compuserve): più immagini nello stesso file, compressione senza perdita; - PNG (Portable Network Graphics): compressione lossless, studiato per sostituire GIF (coperto da brevetti); supporta solo grayscale e RGB; studiato per t rasmissione di immagini su web; - BMP (BitMaP, Mycrosoft e IBM): 1, 4, 8, 24 bit/pixel, compressione senza perdita (RLE); - JFIF ( Jpeg File Interchange Format, meglio noto come formato JPEG) : compressione JPEG. Fattore di compressione = dimensione originale/d imensione file compresso. Esempio: fotocamera a 8Mpixel -> circa 8000000 di pixel. Occupazione immagine non compressa a colori = 8000000 pixel x 3 componenti/pixel x 1 byte/componente = 24000000 byte -> circa 24M byte. Salvo l’immagine in formato JPEG e ott engo un file .jpg di dimensione 2.4M byte. Fattore di compressione: 24 M byte / 2.4 M byte = 10:1. Un’immagine può essere di scarsa qualità per tanti motivi: la risoluzione non è adeguata, o non ho una quantizzazione adeguata, o non ho un rapporto di compressione adeguato (o combinazioni di queste) . Immagini vettoriali . Definiscono gli oggetti che compongono l’immagine mediante equazioni matematiche. Sono basate su una rappresentazione geometrica delle immagini : usano relazioni matematiche tra punti e linee per descrivere un’immagine. Non c’è perdita di dettaglio ingrandendo o rimpicciolen do l’immagine . Le immagini vettoriali sono composte da oggetti. Tutti gli oggetti sono costruiti a partire da una serie di primitive: punti, linee, rettangoli, ellis si… La grafica vettoriale è l’uso di primitive geometriche che sono tutte basate su equazioni matematiche, per rappresentare le immagini nel computer. Vantaggi:  è fatta di oggetti geometrici che formano gli oggetti: line (x1,y1,x2,y2), circle (x,y,radius);  può essere scalata a qualsiasi dimensione senza perdere qualità;  indipendente dalla risoluzione (non esiste il concetto di pixel) ;  occupano pochissimo spazio di memoria (dell’ordine dei Kbytes). Svantaggi:  le immagini vettoriali sono per loro natura gene rate all’interno della macchina;  non è il miglior formato per immagini di tipo fotografico con toni continui, luci, ombre, miscele di colore. Esempio: è possibile rappresentare in maniera schematica un oggetto come un albero e quindi renderne l’idea, ma è impossibile dettagliarne ogni particolare come ad esempio le foglie, le striature sul tronco, ecc. Rasterizzazione = conversione di un’immagine vettoriale in un’immagine raster. Non è possibile l’operazione inversa, ma la rasterizzazione è sempre possibile. Video Video = successione di immagini fisse (frame) trasmesse con velocità sufficientemente elevata . Il movimento è rappresentato già in modo discreto nei media: con un numero abbastanza alto di fotogrammi fissi (15 -30 al secondo) l’occhio um ano percepisce il movimento come continuo. Tradizionalmente, il segnale video di tipo televisivo utilizza un formato interlacciato . Prima vengono generate le righe pari, poi quelle dispari. Vengono generati 50 “semiquadri” al secondo. Era necessario perché la larghezza della banda non era sufficiente. Nel formato progressivo , ogni frame è costituito sia dalle righe pari che da quelle dispari. Interlacciato: 720 punti/linea, 576 linee (288 pari, 288 dispari), 50 semiquadri al secondo (25 frame/s) , 3 byte/pixel (RGB), 720x288x50x3 = 31104000 byte/sec = circa 31Mbyte/sec = circa 250 Mbps. 2 ore di film occupano, se non compressi, 2x60x60x31 = 223200 Mbyte = circa 223 Gbyte. Un DVD ha una capacità di circa 4.5 Gb, avrei bisogno di un fattor e di compressione pari a 223/4.5=50. Progressivo: 320x240 pixel, 15 frame/secondo, 3 byte/pixel (RGB), 320x240x15x3 = 3456000 byte/s = circa 3.5 Mbyte/s = 28 Mbyte/s. 1 minuto di video registrato occupa, se non compresso, 60x3.5 = 219 Mbyte. Potrei codifi care separatamente ogni fotogramma come immagine fissa. È la tecnica usata da molte fotocamere compatte, che salvano i filmati ripresi in formato Motion -JPEG (ogni frame è compresso con JPEG). Si è in grado di ottenere rapporti di compressione dell’ordine 10 -20 senza eccessiva perdita di qualità. Per ottenere rapport i di compressione più alti è necessario sfruttare la ridondanza temporale : f rame consecutivi in una sequenza di immagini sono simili l’uno all’altro , quindi posso codific are solo le differenze tra i frame successivi. È possibile ottenere rapporti di compressione 50:1 fio ad anche 100:1 senza un degrado eccessivo della qualità.