8.5 Komprimering og sampling

Det er mulig fordi virkelige data er fulle av mønstre og gjentakelser: himmelen i et fotografi er tusenvis av nesten like blå piksler, et dokument har de samme ordene om igjen, en lydfil har stillhet.

To familier, og skillet mellom dem er selve eksamensspørsmålet:

Komprimering der originalen kan gjenskapes nøyaktig, bit for bit.

Metoden er å beskrive mønstre kortere — for eksempel «her kommer 40 like tegn» i stedet for å skrive dem ut.

Tapsløs komprimering er påkrevd der en eneste endret bit ødelegger alt:

- Programfiler. Ett feil bit, og programmet krasjer.
- Tekstdokumenter og regneark. Et tall kan ikke være «omtrent riktig».
- Arkivfiler som ZIP.
- Bildeformatene PNG og GIF.

Prisen er at gevinsten er moderat. Du kan ikke kaste noe, bare skrive det smartere.

Komprimering der noe informasjon kastes for godt. Originalen kan aldri gjenskapes.

Det som kastes, velges ut fra hva sansene våre likevel ikke merker: fargenyanser øyet ikke skiller, lyder som overdøves av andre lyder, detaljer i et bilde som er for små til å ses.

Formatene du må kunne:

- JPEG for stillbilder.
- MP3 for lyd.
- MPEG for video.

Gevinsten er stor — ofte 10 til 20 ganger mindre fil — og det er derfor strømming og digitale bilder i det hele tatt lar seg gjøre.

Fellen, som er belagt gang på gang: at JPEG og MP3 er tapsløse fordi «de ser og høres jo helt like ut». At du ikke merker forskjellen, er nettopp poenget med metoden — men dataene er borte.

Den enkleste tapsløse metoden: erstatt en rekke like tegn med antallet og tegnet.

Tegnrekka AAAABBBCCD har 10 tegn. Kodet blir den:

Et analogt signal varierer kontinuerlig: det har en verdi i hvert eneste øyeblikk, og verdien kan være hvilken som helst — ikke bare bestemte trinn.

Eksempler: lufttrykket i en lydbølge, spenningen fra en mikrofon, viseren på et gammelt speedometer, en kvikksølvsøyle i et termometer.

Naturen er analog. Alle sanseinntrykk starter som analoge signaler.

Et digitalt signal består av enkeltverdier med bestemte trinn, målt på bestemte tidspunkt.

Digitale signaler har to store fordeler over analoge:

- De tåler støy. Et litt forvrengt signal kan leses tilbake til nøyaktig $0$ eller $1$; en litt forvrengt analog verdi er bare forvrengt.
- De kan kopieres uten tap. En kopi av en kopi av en kopi er identisk med originalen — noe alle som har kopiert en lydkassett vet at ikke gjelder analogt.

Prisen er at det digitale signalet bare er en tilnærming til det analoge. Hvor god tilnærmingen er, avgjøres av to ting: hvor ofte man måler, og hvor nøyaktig hver måling lagres.

Dette er hele digitaliseringen: fra en sammenhengende kurve til en rekke tall.

Figur i ord: tegn en bølgekurve. Sett loddrette streker med jevn avstand langs tidsaksen, og marker et punkt der hver strek krysser kurven. De markerte punktene er samplene — det er alt maskinen tar vare på. Kurven mellom punktene finnes ikke i fila; den gjettes fram igjen ved avspilling.

To valg avgjør kvaliteten:

- Samplingsfrekvensen: hvor ofte du måler.
- Bitdybden: hvor mange bit hver måling lagres med, altså hvor fine trinn verdiene har.

Kjente verdier:

Etter at et tidspunkt er valgt, må også verdien rundes av til et av de mulige trinnene. Det heter kvantisering.

Antall trinn følger $2^{n}$-regelen fra kap. 8.2:

- 8 bit gir $2^{8} = 256$ trinn.
- 16 bit gir $2^{16} = 65\,536$ trinn — CD-standarden.

Avrundingen til nærmeste trinn er en liten feil, og summen av alle disse feilene høres som en svak susing. Med 16 bit er den så langt under musikken at ingen merker den.

Hold de to fra hverandre: samplingsfrekvensen gjelder tid (hvor ofte), bitdybden gjelder verdi (hvor nøyaktig). Begge må være store nok, og de er uavhengige valg.

Merk hva slags feil dette er. Det er ikke tap av detaljer eller dårligere kvalitet — det er en falsk frekvens som dukker opp av ingenting.

Det klassiske bildet er vognhjulene i gamle filmer som ser ut til å gå bakover. Kameraet tar 24 bilder i sekundet, hjulet snurrer fortere enn det, og øyet får presentert en bevegelse som aldri fant sted.

Motmiddelet er å fjerne de for høye frekvensene med et filter før samplingen. Er de først samplet feil, kan de ikke skilles ut igjen etterpå — den falske og den ekte lave frekvensen er da helt like tall i fila.

Grunnen til at det trengs: en lydbølge kommer ikke langt gjennom lufta av seg selv, men en radiobølge gjør det. Løsningen er å la lyden endre radiobølgen på en måte mottakeren kan reversere.

To måter å endre bærebølgen på:

Ett ekstra bit som legges til slik at det samlede antallet enere blir et bestemt partall eller oddetall. Mottakeren teller enerne og ser om det stemmer.

Du møtte paritetsbitet i kap. 8.3 som den enkleste formen for kanalkoding. Det gjentas her fordi det hører til samme problem som resten av kapitlet: et signal som blir forvrengt på veien.

De to begrensningene, som er det som spørres om:

- Paritet oppdager feil, men retter dem ikke.
- Den oppdager bare et oddetall av feil. To bit som slår om samtidig, gir samme paritet som før, og feilen slipper gjennom.

$$\text{kompresjonsforhold} = \frac{\text{størrelse før}}{\text{størrelse etter}}$$

Går en fil fra 10 byte til 8 byte, er forholdet $10 : 8 = 1{,}25$. Går den fra 36 MB til 3 MB, er forholdet $12$ — fila er tolv ganger mindre.

Forholdet skrives ofte som «$12:1$» eller «12 ganger». Et forhold under $1$ betyr at fila ble større, noe som faktisk kan skje med RLE på data uten gjentakelser.

Merk at forholdet ikke sier noe om kvalitet. Et høyt forhold er imponerende for tapsløs komprimering og helt vanlig for komprimering med tap — de to kan ikke sammenlignes direkte.

Det vanligste formatet for fotografier, og det bruker komprimering med tap.

JPEG utnytter at øyet er langt mer følsomt for lysstyrke enn for fargenyanser, og at fine detaljer i et travelt motiv ikke merkes. Den kaster derfor det øyet minst savner.

To ting som er verdt å kunne:

- Kompresjonsgraden kan velges. Høy kvalitet gir stor fil og lite synlig tap; lav kvalitet gir liten fil og synlige firkantmønstre.
- Tapet er kumulativt. Åpner du en JPEG, endrer den og lagrer på nytt, komprimeres den med tap én gang til. Gjentar du det mange ganger, forfaller bildet.

JPEG passer dårlig til strektegninger, tekst og skjermbilder — der gir de skarpe kantene stygge artefakter, og PNG er riktig valg.

Det mest kjente formatet for lyd, med komprimering med tap.

MP3 bygger på hvordan øret faktisk hører: en svak tone rett ved siden av en sterk tone er umulig å høre, og da er det ingen grunn til å lagre den. Slike lyder kastes.

Resultatet er ofte 10 ganger mindre fil enn et ukomprimert opptak, med en forskjell de fleste ikke hører på vanlig avspilling.

Fellen: at MP3 er tapsløs fordi den «høres helt lik ut». Det er hele hensikten med metoden — men de kastede lydene kommer aldri tilbake.

Familien av formater for video, med komprimering med tap.

Videokomprimering utnytter en ting stillbilder ikke har: at påfølgende bilder ligner hverandre. I stedet for å lagre hvert bilde for seg, lagres et helt bilde av og til, og deretter bare endringene fra det forrige.

Det er derfor en video av en person som sitter stille i et rom, blir liten, mens en video med raske klipp og mye bevegelse blir stor.

Uten videokomprimering ville strømming vært umulig: ukomprimert video i vanlig oppløsning krever langt mer båndbredde enn en vanlig internettforbindelse har.

- 1 Hz er én svingning per sekund.
- 1 kHz er tusen svingninger per sekund.

I lyd svarer frekvensen til tonehøyde: lav frekvens gir dyp tone, høy frekvens gir lys tone. Et menneske hører omtrent fra 20 Hz til 20 kHz, og den øvre grensen synker med alderen.

Merk at frekvens brukes om to ulike ting i dette kapitlet, og de må holdes fra hverandre:

- Signalets frekvens — hvor fort selve lyden svinger.
- Samplingsfrekvensen — hvor ofte maskinen måler.

Nyquist-regelen er nettopp en påstand om forholdet mellom de to.

En bærebølge er en jevn, høyfrekvent svingning som brukes til å frakte et annet signal over en avstand.

Bærebølgen inneholder ingen informasjon i seg selv. Den er transportmiddelet: informasjonen legges inn ved å endre bølgen, enten i høyde (AM) eller i takt (FM).

Frekvensen til bærebølgen er det du stiller inn på radioen. «P1 på 92,4» betyr at bærebølgen svinger 92,4 millioner ganger i sekundet, og at mottakeren skal lytte etter endringer i akkurat den.

Det er også derfor to sendere ikke kan bruke samme bærebølgefrekvens i samme område — da ville endringene blandet seg.