Comprimere i dati ed errori di comunicazione

Nella lezione 02 hai fatto due conti. Lo schermo di un portatile Full HD ha 1920 × 1080 pixel, e in RGB ogni pixel occupa 3 byte. Quindi una foto grande come lo schermo occupa 1920 × 1080 × 3 = 6 220 800 byte, circa 6 MB. Un'ora di musica come quella dei CD occupa 635 040 000 byte, circa 635 MB.

Sono numeri enormi. Uno smartphone contiene migliaia di foto, e una pagina web ne mostra decine in pochi secondi. Se ogni foto pesasse 6 MB, la memoria finirebbe subito e le pagine si caricherebbero lentissime.

L'immagine guida: dettare al telefono

Per tutta la lezione tieni in mente questa scena. Detti un messaggio a un amico, al telefono. Vuoi metterci poco tempo, e la linea a volte gracchia.

Per fare prima, usi dei trucchi senza pensarci:

• invece di «zero, zero, zero, zero, zero, zero, zero, zero» dici «otto zeri»;
• le parole che usi di continuo le abbrevi;
• se due frasi sono quasi uguali, dici «come prima, ma con…»;
• se avete lo stesso libro, dici «pagina 12, parola 5» invece di dettare la parola.

Sono proprio le quattro tecniche del libro. Scrivere gli stessi dati con meno bit si chiama compressione (data compression). Le prossime quattro sezioni le vedono una per volta.

Senza perdita e con perdita

Prova a comprimere due cose diverse.

• Un testo. Se cambi una sola lettera, «pesca» diventa «pasta». Dopo la compressione il testo deve tornare identico, lettera per lettera.
• Una foto. Se un pixel tra due milioni diventa un pochino più scuro, nessuno se ne accorge. Si può accettare di perdere qualche dettaglio, se in cambio la foto occupa dieci volte meno.

Il libro chiama i due casi così.

Come si legge. Senza perdita: comprimi, decomprimi, e hai di nuovo gli stessi identici bit. Con perdita: decomprimi e hai qualcosa di molto simile, ma non uguale. Per testi, programmi e numeri serve la compressione senza perdita. Per foto, musica e video va bene anche quella con perdita.

Torna al telefono. Se il messaggio è 0000000011110000, non detti sedici cifre. Dici «otto zeri, quattro uni, quattro zeri». Hai detto la stessa cosa con molte meno parole.

Un gruppo di simboli uguali uno dopo l'altro si chiama ripetizione (run). Al posto di ogni ripetizione si scrivono due cose: quale simbolo si ripete e quante volte. Questo modo di comprimere si chiama codifica run-length (run-length encoding), cioè «codifica della lunghezza delle ripetizioni».

Dove funziona bene? Dove ci sono lunghe ripetizioni. Pensa alla F della lezione 02, disegnata con i pixel: in un disegno in bianco e nero ci sono lunghe file di pixel bianchi e lunghe file di pixel neri. Anche i fax e le schermate con grandi zone di un colore solo si comprimono bene così.

Dove funziona male? Prendi la fila 01010101. Le ripetizioni sono otto, tutte lunghe 1: «uno zero, un uno, uno zero…». Scritta così diventa più lunga di prima. Quando i dati cambiano di continuo, come nelle foto, la codifica run-length non serve.

La codifica run-length è senza perdita: dal numero di ripetizioni si riscrive la fila identica.

Il telegrafo usava il codice Morse: ogni lettera è una fila di punti e linee. Guarda quanto sono lunghe:

Chi l'ha inventato ha dato i codici più corti alle lettere più usate. Così i messaggi si trasmettono prima. È la seconda tecnica del libro: la codifica in base alla frequenza (frequency-dependent encoding). La frequenza di un simbolo è quante volte compare.

In ASCII, invece, ogni lettera occupa un byte: la «e» come la «q». Si spreca spazio.

Un problema: dove finisce una lettera?

Nel Morse la E è «·» e la A è «· –». Se ricevi «· –», è una A oppure una E seguita da una T? Il telegrafista lo capisce perché tra una lettera e l'altra c'è una pausa.

Con i bit non ci sono pause: c'è solo una fila di 0 e di 1. Per leggerla senza dubbi serve una regola.

Un codice con questa regola si chiama codice prefisso: nessun codice è il «prefisso», cioè la parte iniziale, di un altro.

Un esempio piccolo: BANANA

La parola BANANA ha tre lettere diverse: A tre volte, N due volte, B una volta.

Con un codice in cui tutte le lettere hanno la stessa lunghezza, un bit non basta: dà solo due possibilità, 0 e 1. Servono 2 bit per lettera, per esempio A = 00, B = 01, N = 10. Le lettere sono 6, quindi 6 × 2 = 12 bit.

Ora prova un codice di lunghezza variabile: A = 0, B = 10, N = 11.

• È un codice prefisso? A è 0, e nessun altro codice comincia con 0. B e N cominciano con 1, ma sono diversi al secondo bit. Sì.
• BANANA diventa 10 0 11 0 11 0, cioè 100110110: 9 bit invece di 12.

Per leggerlo, parti da sinistra:

1. 1 da solo non è un codice; 10 è B.
2. 0 è A.
3. 1 da solo no; 11 è N.
4. Poi 0 è A, 11 è N, 0 è A.

Viene di nuovo BANANA, senza nessuna pausa.

Come si costruisce: l'albero di Huffman

Come si sceglie il codice migliore? C'è un metodo, inventato da David Huffman nel 1952. I codici che produce si chiamano codici di Huffman.

L'idea: si mettono insieme, un passo alla volta, le due lettere più rare. Così le lettere rare finiscono in fondo e hanno codici lunghi, quelle frequenti restano in alto e hanno codici corti.

Ecco l'albero. In cima c'è il gruppo finale, con peso 10. Ogni unione è una biforcazione, con 0 a sinistra e 1 a destra.

Per trovare il codice di una lettera, scendi dalla cima e scrivi i numeri dei rami. Per arrivare alla G: a sinistra (0), poi a destra (1), poi a sinistra (0). Quindi G = 010.

In tutto 6 + 6 + 4 + 3 + 3 = 22 bit. Con un codice a lunghezza fissa servono 3 bit per lettera, perché le lettere diverse sono 5 e con 2 bit le possibilità sono solo 4: in tutto 10 × 3 = 30 bit. In ASCII, un byte per lettera, sarebbero 80 bit.

Il codice è prefisso da solo: ogni lettera sta in fondo a un ramo, e nessuna sta sulla strada per un'altra.

Il libro descrive la tecnica così.

Come si legge. Le lettere frequenti hanno codici corti, quelle rare codici lunghi, come nel Morse. In media il messaggio occupa meno bit. È senza perdita: dal codice si riottiene il messaggio identico.

Ancora al telefono. Detti le temperature di una settimana: 20, 21, 21, 22, 20, 19, 19. Dopo la prima, puoi dire solo quanto cambia: «20, poi più 1, poi uguale, poi più 1, poi meno 2, poi meno 1, poi uguale».

I numeri da dettare diventano 20, +1, 0, +1, −2, −1, 0. Sono quasi tutti piccoli, e i numeri piccoli si scrivono con pochi bit.

Questa è la terza tecnica: la codifica relativa (relative encoding), detta anche differenziale (differential encoding). Si scrive il primo dato per intero; per ogni dato dopo, solo la differenza con quello prima.

Funziona bene quando ogni dato somiglia a quello prima. Il libro fa l'esempio dei video. Un video è una fila di immagini, i fotogrammi, 25 o 30 al secondo. Due fotogrammi vicini sono quasi uguali: la persona si è mossa appena, lo sfondo è identico. Invece di conservare ogni fotogramma per intero, si conserva solo che cosa è cambiato.

Anche i campioni di un suono, quelli della lezione 02, cambiano poco da uno all'altro. Per questo la codifica relativa si usa anche per l'audio.

Se le differenze si scrivono esatte, la codifica relativa è senza perdita. Se si arrotondano per risparmiare ancora, diventa con perdita.

L'ultimo trucco del telefono: tu e il tuo amico avete lo stesso vocabolario. Invece di dettare una parola lettera per lettera, dici «pagina 512, parola 7». Lui la cerca e la trova.

Questa è la quarta tecnica, la codifica a dizionario (dictionary encoding). Il dizionario è un elenco numerato di parole, uguale per chi scrive e per chi legge. Al posto di ogni parola si scrive il suo numero nell'elenco.

Il libro fa l'esempio del correttore ortografico di un programma di videoscrittura, che ha già un dizionario. Con 25 000 parole, quanti bit servono per il numero di una parola?

• Con 14 bit i numeri possibili sono $2^{14}=16384$. Si legge «due alla quattordici» e vuol dire 2 moltiplicato per sé stesso 14 volte, come nella lezione 02. Non bastano.
• Con 15 bit sono $2^{15}=32768$: bastano.

Quindi ogni parola costa 15 bit. La parola «computer» in ASCII ne occupa 8 × 8 = 64.

Il dizionario si costruisce mentre leggi

C'è un problema: un dizionario fisso va bene per le parole di una lingua, ma non per una foto o per un file qualunque. L'idea furba è costruire il dizionario mentre si comprime. Chi legge lo ricostruisce identico, negli stessi momenti, quindi non bisogna nemmeno spedirlo.

Questa si chiama codifica a dizionario adattiva (adaptive dictionary encoding). Il metodo più famoso è LZW, dalle iniziali dei suoi inventori: Lempel, Ziv e Welch.

Il libro la spiega con messaggi fatti di tre simboli: la x, la y e lo spazio. Le regole, nella versione del libro:

La prima volta la parola xyx costa tre numeri. Da lì in poi ne costa uno solo. Più un messaggio ripete le stesse parole, più si guadagna.

Chi legge ricostruisce il dizionario

Il tuo amico riceve 121343434 e conosce solo il dizionario iniziale: x = 1, y = 2, spazio = 3. Legge un numero alla volta.

1. 1, 2, 1: scrive x, y, x.
2. 3: è uno spazio. La parola xyx è finita, ed è nuova: la aggiunge al dizionario come 4, proprio come aveva fatto chi ha compresso.
3. 4: ora sa che è xyx, e la scrive.
4. Poi 3, 4, 3, 4: spazio, xyx, spazio, xyx.

Ha riottenuto «xyx xyx xyx xyx», identico. LZW è senza perdita.

Nella lezione 02 un pixel in RGB occupa 3 byte: quanto rosso, quanto verde e quanto blu, ognuno da 0 a 255. I colori possibili sono più di sedici milioni. Le quattro tecniche di prima aiutano, ma per le immagini si fa di più.

GIF: dipingere con i numeri

Conosci i disegni da colorare con i numeri? Ogni zona ha un numero, e in fondo alla pagina c'è la legenda: 1 = rosso, 2 = giallo, 3 = blu.

GIF (Graphic Interchange Format) fa così. Sceglie al massimo 256 colori e li mette in una tabella, la tavolozza (palette). Ogni colore della tavolozza è scritto con i suoi 3 byte RGB. Poi ogni pixel non dice più il suo colore: dice solo il numero del colore nella tavolozza.

Un numero da 0 a 255 sta in un byte. Quindi ogni pixel occupa 1 byte invece di 3: l'immagine pesa circa un terzo.

Poi GIF comprime ancora i numeri dei pixel con LZW, il dizionario che cresce. Un colore della tavolozza può anche essere «trasparente»: lì si vede lo sfondo che c'è dietro.

GIF è con perdita, se l'immagine di partenza ha più di 256 colori: i colori che non stanno nella tavolozza vengono sostituiti dal più vicino. Per una foto, che ha migliaia di sfumature, la differenza si vede. Per un disegno o un fumetto, che hanno pochi colori e zone di colore pieno con bordi netti, non si perde quasi niente. È la domanda 3 del §1.9.

JPEG: l'occhio vede meglio la luce del colore

Guarda una foto in bianco e nero: capisci tutto, anche senza i colori. I dettagli, i bordi, le facce stanno soprattutto nella luminosità, cioè quanto è chiaro o scuro ogni punto. Il colore conta, ma l'occhio ne nota i piccoli cambiamenti molto meno.

JPEG (dal nome del gruppo che l'ha creato, Joint Photographic Experts Group) è il formato delle fotografie, e sfrutta proprio questo. Ha una versione senza perdita, poco usata perché comprime poco. Quella di tutti i giorni è lo standard di base (baseline standard), che è con perdita. Funziona così:

1. Ogni pixel si scrive con tre numeri diversi da RGB: uno per la luminosità (luminance) e due per il colore (chrominance). Ne parlava già una nota della lezione 02.
2. L'immagine si divide in quadratini di 2 × 2 pixel. Per ogni quadratino si tiene la luminosità di tutti e quattro i pixel, ma per il colore solo la media dei quattro.
3. L'immagine si divide in blocchi di 8 × 8 pixel. Ogni blocco si trasforma con un procedimento matematico, e i dettagli più fini, quelli che l'occhio vede meno, si approssimano.
4. Alla fine si usano le tecniche senza perdita di prima: run-length, codifica relativa, codici a lunghezza variabile.

Il passo 2, contato su un quadratino:

Solo questo passo dimezza i numeri, e l'occhio non vede la differenza. Con tutti i passi, di solito una foto in JPEG occupa almeno dieci volte meno che in RGB.

Sei a un concerto. Esplode un petardo, e per un attimo non senti nient'altro: nemmeno la voce del cantante, che pure c'è. Poi accanto a una cassa che suona un basso fortissimo qualcuno ti parla a voce bassa, con una voce grave: non lo senti.

Sono due limiti veri dell'orecchio, e MP3, il formato più famoso per la musica, li sfrutta. Il libro li chiama così:

• mascheramento temporale (temporal masking): subito dopo un suono forte, per un breve momento, l'orecchio non sente i suoni deboli;
• mascheramento in frequenza (frequency masking): un suono forte copre i suoni deboli con una nota vicina alla sua. La frequenza di un suono è quello che lo fa più grave o più acuto.

MP3 toglie dalla registrazione i suoni che tanto non sentiresti. È una compressione con perdita, ma la perdita è scelta in modo da non sentirsi. È la domanda 6 del §1.9.

Quanto si guadagna? Un CD, come nella lezione 02, conserva ogni secondo 44 100 campioni da 16 bit, per due canali: 44 100 × 16 × 2 = 1 411 200 bit al secondo. Un MP3 di buona qualità ne usa spesso 128 000. Il conto 1 411 200 : 128 000 fa circa 11: lo stesso brano occupa circa undici volte meno.

I video: MPEG

Per i video c'è MPEG (Motion Picture Experts Group). Usa la codifica relativa che hai già visto:

• solo alcuni fotogrammi si conservano per intero, compressi come immagini, in modo simile a JPEG;
• per i fotogrammi in mezzo si conservano solo le differenze rispetto a quelli vicini.

In una scena in cui una persona parla davanti a un muro, il muro si conserva una volta sola. Di ogni fotogramma dopo cambiano solo la bocca e gli occhi.

Torna al telefono. La linea gracchia, e il tuo amico capisce «cinque» invece di «nove». Con i bit succede lo stesso: un graffio su un disco, un disturbo nell'aria o sul cavo, e uno 0 arriva come 1, o un 1 come 0. Il libro chiama questi problemi errori di comunicazione (communication errors).

Chi riceve non vede il messaggio giusto: vede solo i bit che arrivano. Come fa ad accorgersi che uno è sbagliato?

L'accordo: gli 1 sono sempre dispari

Tu e il tuo amico vi mettete d'accordo così: ogni gruppo di bit che spedisci deve avere un numero dispari di 1. Se un byte ha già un numero dispari di 1, aggiungi uno 0. Se ne ha un numero pari, aggiungi un 1, così diventano dispari.

Il bit in più si chiama bit di parità (parity bit). Il libro lo mette a sinistra, davanti al byte: ogni byte diventa una fila di 9 bit.

All'arrivo il tuo amico conta gli 1 dei 9 bit. Se sono dispari, va tutto bene. Se sono pari, c'è stato un errore, e chiede di rispedire.

Perché funziona? Ogni bit che cambia aggiunge un 1 o ne toglie uno. In tutti e due i casi, un numero dispari diventa pari.

Come si legge. Prima di spedire conti gli 1 e aggiungi il bit che rende il totale dispari. Chi riceve riconta tutti i bit, compreso quello di parità: un totale pari vuol dire che qualcosa si è rotto per strada. Con la parità pari si fa lo stesso, al contrario.

Un vantaggio della parità dispari: una fila di soli 0 non è mai giusta, perché zero 1 sono un numero pari. Se una linea si guasta e manda solo zeri, chi riceve se ne accorge.

Alcune memorie dei computer usano proprio questo: per ogni byte conservano 9 bit, gli 8 del byte più il bit di parità.

Nello strumento clicca sui bit del byte e scegli la parità: il bit di parità si calcola da solo. Poi prova «Un errore» e «Due errori»: guarda quando l'errore si vede.

Due errori non si vedono

Se cambiano due bit, il primo rende pari il totale e il secondo lo rende di nuovo dispari. Il conto torna, e chi riceve non si accorge di niente.

Il bit di parità vede un errore, tre errori, cinque errori: un numero dispari. Non vede due, quattro, sei errori. E anche quando vede un errore, non dice quale bit è sbagliato. È la domanda 2 del §1.10.

Un bit di parità per ogni byte costa un bit ogni otto: il messaggio cresce di un ottavo. Per messaggi lunghi si usa anche un'altra strada. Si spediscono i byte così come sono, e alla fine si aggiunge un byte in più, che li controlla tutti.

È come quando detti una lista di numeri e alla fine aggiungi: «il totale fa 312». Se il tuo amico somma e non gli torna 312, ha capito male qualcosa.

Il byte di controllo

Metti i byte uno sotto l'altro. Ogni colonna è una fila di bit, e per ogni colonna calcoli un bit di parità. Gli otto bit di parità, uno per colonna, formano un byte: il byte di controllo (checkbyte). Qui uso la parità dispari, come per il bit di parità del libro.

Chi riceve rifà lo stesso conto colonna per colonna. Se un bit della colonna 5 cambia, la colonna 5 non torna.

Somme di controllo e CRC

Il libro cita altre due varianti della stessa idea, solo come nome:

• la somma di controllo (checksum): si sommano i byte del messaggio e si spedisce anche la somma, come il «totale 312» del telefono;
• il controllo a ridondanza ciclica (cyclic redundancy check, CRC): un conto più complicato, che si accorge di quasi tutti gli errori, anche di tanti bit vicini. Lo usano le reti e i file ZIP.

All'esame basta sapere che esistono e che servono ad accorgersi degli errori.

Il bit di parità ti dice «c'è un errore», ma non dove. Si può fare di meglio: correggerlo senza chiedere di rispedire.

Al telefono si fa così: «nove, ripeto, nove, ripeto, nove». Se senti «nove, cinque, nove», capisci che era nove: due volte su tre.

Con i bit: invece di 0 spedisci 000, invece di 1 spedisci 111. Se arriva 010, la maggioranza dice 0: c'era 000, ed è cambiato un bit solo. Funziona, ma il messaggio è diventato tre volte più lungo. Il libro mostra un modo più furbo, con meno bit in più. Per capirlo serve un modo di misurare quanto due file di bit sono diverse.

Quanto sono diverse due file di bit

Metti 1011 e 1001 una sotto l'altra e confrontale posto per posto: sono diverse solo nel terzo bit. Il numero di posti in cui sono diverse si chiama distanza di Hamming, dal nome di Richard Hamming, che studiò questi codici negli anni Quaranta.

Come si legge. Si scrivono le due file una sotto l'altra e si contano le colonne con due bit diversi. Distanza 0 vuol dire file identiche. Distanza 1 vuol dire che basta cambiare un bit per passare da una all'altra. Le due file devono avere lo stesso numero di bit.

Il codice del libro: lettere lontane tra loro

Per otto lettere, da A a H, bastano 3 bit, perché $2^3=2\cdot 2\cdot 2=8$. Il libro ne usa 6, e sceglie le file in modo che ogni coppia sia lontana. Le file scelte per le lettere si chiamano parole del codice. Il codice è nella figura 1.27 del libro.

Prendi due lettere qualsiasi e calcola la distanza: viene sempre 3 o 4, mai meno. Per esempio A e C sono diverse in 3 posti, A e B in 4. Su tutte le 28 coppie, 16 sono a distanza 3 e 12 a distanza 4.

La distanza più piccola tra due parole del codice si chiama distanza minima del codice. Qui è 3.

Come si decodifica

Arriva 010100. Non è nella tabella, quindi c'è stato un errore. Calcola la distanza da ogni lettera:

La più vicina è D, cioè 011100, a distanza 1: è cambiato solo il terzo bit. Si decodifica D.

Nello strumento clicca sui bit della fila arrivata: vedi la distanza da ogni lettera, i bit diversi evidenziati e la lettera più vicina.

Perché un errore si corregge e due si vedono

Immagina ogni parola del codice come una casa. Intorno a ogni casa c'è un giardino: le file a distanza 1 da lei, cioè quelle che ottieni cambiando un bit solo.

• Le case distano almeno 3 l'una dall'altra. Quindi due giardini non si toccano mai: una fila a distanza 1 da A non può essere a distanza 1 anche da C, altrimenti A e C disterebbero al massimo 2.
• Un errore: la fila esce dalla casa e finisce nel suo giardino. Il giardino è di una casa sola, quindi sai da dove viene. L'errore si corregge.
• Due errori: la fila si allontana di 2. Non arriva mai su un'altra casa, che dista almeno 3: quindi non è una parola del codice, e ti accorgi dell'errore. Però può finire nel giardino di un'altra casa, e allora la correzione sbaglia.

Riassumendo: con distanza minima 3 il codice corregge un errore e ne rivela due. Rivelare vuol dire accorgersene.

Ora si capisce anche il bit di parità. Prendi due gruppi di 9 bit giusti, tutti e due con un numero dispari di 1. Se fossero diversi in un bit solo, uno dei due avrebbe un 1 in più dell'altro, e i loro numeri di 1 non sarebbero dispari tutti e due. Quindi sono diversi in almeno 2 bit: la distanza minima è 2. Rivela un errore, ma non ne corregge nessuno.

Le regole dell'esame, uguali per i tre canali, sono nella lezione 01 e nella scheda del corso: 9 quiz in 45 minuti, con Safe Exam Browser.

Che cosa serve di questa lezione

1. La distanza di Hamming. È il quiz 1 della simulazione d'esame 1 del 2023/24: quattro coppie di file da 8 bit, e per ognuna la distanza. Si fa in pochi secondi, se conti con calma colonna per colonna.
2. Parità e codice del libro. Le domande del §1.10: dove c'è sicuramente un errore, aggiungere il bit di parità dispari, decodificare con il codice da A a H.
3. La compressione. Nei quiz delle simulazioni del 2023/24 non compare, ma il §1.9 è nella mappa comune del libro. Le domande più probabili sono quelle del libro: le quattro tecniche, un messaggio da comprimere con LZW, con perdita o senza, che cosa sfruttano JPEG e MP3.

Nelle simulazioni del 2023/24 tornano anche complemento a 2, virgola mobile e notazione in eccesso: sono le sezioni 1.6 e 1.7, nella lezione 03.

Errori da evitare

• Usare la parità pari quando il libro usa la dispari: leggi bene il testo della domanda.
• Contare gli 1 senza il bit di parità, quando controlli una fila ricevuta: si contano tutti i 9 bit.
• Credere che il bit di parità corregga: si accorge soltanto, e solo di un numero dispari di errori.
• Calcolare la distanza di Hamming tra file di lunghezza diversa: non ha senso.
• Confondere «corregge» e «rivela»: con distanza minima 3 corregge 1 errore e ne rivela 2.
• Dire che GIF è senza perdita per le foto: con più di 256 colori li approssima.
• In LZW, aggiungere al dizionario una parola che c'è già, o dimenticare di scrivere lo spazio.

Compressione

Scrivere gli stessi dati con meno bit (data compression).

Senza perdita

Una compressione da cui si riottengono esattamente i dati originali (lossless).

Con perdita

Una compressione da cui si ottengono dati solo simili agli originali (lossy), come JPEG e MP3.

Codifica run-length

Al posto di una ripetizione si scrivono il simbolo e quante volte si ripete (run-length encoding).

Codifica in base alla frequenza

Codici corti per i simboli frequenti e lunghi per quelli rari (frequency-dependent encoding).

Codice di Huffman

Un codice in base alla frequenza costruito unendo ogni volta i due pesi più piccoli.

Codice prefisso

Un codice in cui nessun codice è l'inizio di un altro: si legge senza pause.

Codifica relativa

Il primo dato per intero, poi solo le differenze con il dato prima (relative o differential encoding).

Codifica a dizionario

Al posto di una parola si scrive il suo numero in un elenco comune (dictionary encoding).

LZW

Codifica a dizionario adattiva: il dizionario cresce mentre si comprime (Lempel, Ziv, Welch).

GIF

Formato per immagini con una tavolozza di al massimo 256 colori, un byte per pixel, più LZW.

Tavolozza

La tabella dei colori di un'immagine GIF (palette): ogni pixel dice il numero del suo colore.

JPEG

Formato per foto, con perdita: luminosità per ogni pixel, colore come media, blocchi di 8 × 8 pixel.

MPEG

Famiglia di formati per i video: alcuni fotogrammi interi, degli altri solo le differenze.

MP3

Formato per la musica, con perdita: toglie i suoni nascosti dal mascheramento temporale e in frequenza.

Bit di parità

Il bit aggiunto perché il numero totale di 1 sia dispari (parità dispari) o pari (parità pari).

Byte di controllo

Un byte di bit di parità, uno per colonna, spedito dopo un gruppo di byte (checkbyte).

Distanza di Hamming

Il numero di posizioni in cui due file di bit della stessa lunghezza sono diverse.

Distanza minima

La distanza di Hamming più piccola tra due parole di un codice: nel codice del libro è 3.

Codice correttore

Un codice le cui parole sono lontane tra loro, così un errore si corregge scegliendo la parola più vicina (error-correcting code).

Spunta quando sai fare la cosa senza guardare gli appunti. Le spunte restano salvate in questo browser.

• So dire la differenza tra compressione senza perdita e con perdita, con un esempio per tipo.
• So comprimere una fila di bit con la codifica run-length e un elenco di numeri con la codifica relativa.
• So costruire un codice di Huffman con l'albero e contare i bit di una parola.
• So comprimere e decomprimere un messaggio con LZW come nel libro, con la tabella del dizionario.
• So spiegare come comprimono GIF, JPEG, MPEG e MP3, e quali sono con perdita.
• So aggiungere il bit di parità dispari a un byte e dire se un gruppo ricevuto ha sicuramente un errore.
• So calcolare la distanza di Hamming e decodificare con il codice del libro, da A a H.
• So spiegare perché un codice con distanza minima 3 corregge un errore e ne rivela due.