Specialarbete datakomprimering

• INLEDNING
  • Historik
  • Grundbegrepp
• ODESTRUKTIV KOMPRIMERING
  • Shannon-Fano-kodning
  • Huffman-kodning
  • Adaptiv Huffman-kodning
  • Aritmetisk kodning
  • Modeller av högre ordning
  • Ordbaserad komprimering
  • Komprimering med ett glidande fönster
  • En förbättring av LZ77-komprimeringen
  • LZ78-komprimering
  • En förbättring av LZ78
• DESTRUKTIV KOMPRIMERING
  • Inledning till destruktiv komprimering
  • Ljudkomprimering
  • Destruktiv grafikkomprimering
  • Komprimering av rörliga bilder
• LITTERATURFÖRTECKNING

• Contents

INLEDNING

Historik

Ända sedan den första datorns tid har lagringsutrymme varit ett problem. Att få plats, både i datorns minne och på ett yttre lagringsmedia, med de program och de data som ska behandlas. Även då priserna på både minne och lagringsmedia stadigt är på nedgång, är behovet alltid större än tillgången.

För att kunna få plats med så mycket som möjligt kom man tidigt på principerna med datakomprimering. Redan på 1940-talet introducerade Claude Shannon från Bell Labs i USA sin informationsteori, i vilken datakomprimering är en av grundvalarna.

Denna grundläggande datakomprimering stöder sig på överflöd, informationsöverflöd. Ordet entropi har hämtats in från termodynamiken, och betyder den mängd information ett givet meddelande innehåller. Ju oftare en viss kod förekommer i ett meddelande, desto mindre är informationsinnehållet för varje tillfälle då just denna kod förekommer. För de koder som förekommer sällan är förhållandet omvänt, de innehåller mer information.

Informationsinnehållet för en given kod i en given text kan enligt Shannon räknas fram på formeln

Antal_bitar = log₂ sannolikhet

Meddelandets totala entropi är helt enkelt summan av de enskilda kodernas entropi.

Grundbegrepp

Innan vi går in mer på olika typer av datakomprimering är det bra att ha vissa grundbegrepp klara för sig.

Man kan lätt få för sig att datakomprimering bara är att läsa in t.ex. en text och samtidigt mata ut en kompaktare version av denna, men så enkelt är det inte. Datakomprimering är en process som består av två steg, skapandet av en modell och kodning av meddelandet med hjälp av denna modell.

Detta kan enkelt liknas vid att läsa en bok på ett främmande språk, innan du kan läsa boken måste du lära dig språket, sätta upp en modell av hur språket fungerar. Först när du har denna modell kan du läsa boken och göra dig en uppfattning om vad den handlar om, och, exempelvis, sammanfatta boken.

Det är detta skapande av en modell som är det avgörande steget i datakomprimering. Det spelar ingen roll hur bra kodningsdelen av komprimeringsprogrammet är, utan en bra modell kan den inte åstadkomma någonting alls.

Inom komprimeringen talar man om två olika typer, på engelska kallas de "lossy" och "loss-less", vilket enklast kan översättas med destruktiv och odestruktiv komprimering. När du utför en odestruktiv komprimering vet du att det du får tillbaka när du packar upp är precis samma sak som du hade när du startade komprimeringscykeln. Detta är nödvändigt för komprimering av program och databaser, för om programmen kom tillbaka på ett annat sätt när de packades upp kan det få förödande konsekvenser. Däremot är det inte nödvändigt med odestruktiv komprimering av ljud och bilder, då en liten skillnad i exaktheten i bilden normalt inte kan uppfattas av våra mänskliga sinnen.

Det är den destruktiva komprimeringen som vunnit mark på sistone, till exempel med de relativt nya standardiserade metoderna för komprimering av stillbilder, kallat JIFF (JPEG Interchangable File Format), vilken utvecklats av JPEG (Joint Photographic Experts Group) samt för rörliga bilder, utvecklat av MPEG (Moving Pictures Experts Group). JIFF-standarden är väl utarbetad, men ändock tämligen ny. Äldre program stöder inte denna standard, men allteftersom dessa program uppdateras kommer fler och fler program som stöder dem. MPEG-standarden är ännu i prototypstadiet, men redan idag används MPEG för överföring av rörliga bilder via satellit över Atlanten.

Inom kort kommer även vissa satellit-TV-kanaler att provsända i det nya MPEG-formatet. Den nyaste Eutelsat-serien av satelliter är förberedd för detta och kan sända en analog kanal samtidigt med en digital i samma transponder, och i framtiden samtidigt sända flera digitala kanaler på samma bandbredd. Även på den nyuppskjutna (januari 1995) SES Astra 1D förekommer testsändningar i digitalt format, nästa satellit i serien, Astra 1E är endast avsedd för digitala sändningar.

Jag kommer i detta specialarbete huvudsakligen inrikta mig på den odestruktiva komprimeringen, men jag kommer även kort att beskriva den destruktiva komprimeringen.

ODESTRUKTIV KOMPRIMERING

Shannon-Fano-kodning

Shannon-Fano-kodning är den första välkända metoden för kodning och komprimering av data. Den utvecklades av Claude Shannon vid Bell Labs och R. M. Fano vid M. I. T. Shannon-Fano-kodning bygger på att varje tecken, symbol, har en i förväg känd sannolikhet. Utifrån denna sannolikhetstabell formas ett bitträd, där de mest sannolika symbolerna har kortare representation, och de minst sannolika längre.

För att skapa ett Shannon-Fano-träd används följande, ganska enkla, algoritm:

1. Den relativa sannolikheten för varje förekommande symbol i det som ska kodas beräknas.
2. Dessa sannolikheter sorteras i ordning av ökande frekvens, med de mest förekommande frekvenserna överst.
3. Listan delas i två delar, så att den totala relativa frekvensen på den övre halvan ansluter så väl som möjligt till den totala relativa frekvensen av den nedre halvan.
4. Den övre halvan av tabellen tilldelas binärkoden 0, och den undre halvan binärkoden 1.
5. Steg 3-4 utförs sedan rekursivt för varje del av tabellen tills dess att varje post i den har ett unikt bitmönster.

        Symbol  Förekomster
        A       15
        B       7
        C       6
        D       6
        E       5
        fig. 1. En enkel frekvenstabell.

        Symbol  Förekomster        Kod
        A       15                 0 0
        B       7                  0 1
        C       6                  1 0
        D       6                  1 1 0
        E       5                  1 1 1
        fig. 2. Shannon-Fano-koder

        Symbol  Förekomster  Antal bitar  Totalt  SF bitar  SF totalt
        A       15           1,38         20,68   2         30
        B       7            2,48         17,35   2         14
        C       6            2,70         16,20   2         12
        D       6            2,70         16,20   3         18
        E       5            2,96         14,82   3         15
                                          85,25             89
        fig. 3. Efter Shannon-Fano-komprimering

Huffman-kodning

Huffman är en komprimeringsmetod som i en eller annan form än idag används väldigt ofta, även om den används tillsammans med andra metoder. Huffman-kodning liknar Shannon-Fano-kodning till den del att man även här använder ett träd, men i stället för att börja från toppen (kallas visserligen för roten) börjar man "bakifrån". Algoritmen publicerades för första gången av D. A. Huffman år 1952, i en text rubricerad "A Method for the Construction of Minimum Redundancy Codes".

1. En lista över samtliga förekommande tecken (noder) i den information som ska kodas skapas.
2. De två noder med lägst frekvens kopplas samman, och en "föräldranod" skapas. Dess frekvens sätts till summan av de två sammankopplade noderna.
3. Denna nya "föräldranod" läggs till i nodlistan, samtidigt som de två "barnnoderna" tas bort.
4. Den ena av de båda noderna sätts att representera en nolla hos sin föräldranod, den andra en etta.
5. Steg 2-4 genomförs tills dess det endast finns en fri nod i trädet, denna kallas för roten.

Om vi går genom ovanstående algoritm för den frekvenstabell som fanns i föregående stycke, kommer vi att få denna tabell (kan skilja något, beroende på om vi tar C och E eller D och E i första delningen).

        Symbol  Förek. Kod     Antal bitar     Totalt  SF Totalt
        A       15      0       1       15      30
        B       7       1 0 0   3       21      14
        C       6       1 0 1   3       18      12
        D       6       1 1 0   3       18      18
        E       5       1 1 1   3       15      15
                                        87      89
        fig. 4. Efter Huffman-komprimering 

Huffman är en av de mest grundläggande metoderna för komprimering, och används i allt från kommersiella komprimeringsprogram till faxmaskiner.

En nackdel som finns med Huffman-kodning, och för den delen även Shannon-Fano-kodning, är att avkodaren måste börja med en exakt kopia av den modell som användes vid kodningen, och för att så ska vara fallet måste i detta fall frekvenstabellen skickas med filen. Detta gör att man får upp till 257 bytes extra data (maximalt 256 olika tecken, och en speciell "stopp"-kod) i varje fil. Man har dock kommit på motmedel även mot detta, vilket ska behandlas i nästa avsnitt.

Adaptiv Huffman-kodning

För att genomföra en sådan kodning använder man följande algoritm. Observera att uppdateringsrutinen måste vara exakt likadan i såväl kodaren som avkodaren, annars kommer inte det som matas ut av avkodaren att stämma med det som fanns från början.

        Kodare                        Avkodare

        1. Initialisera modell        1. Initialisera modell
        2. Hämta rådata               2. Hämta kodad data
        3. Koda                       3. Koda av
        4. Skriv den kodade datan     4. Skriv den avkodade datan
        5. Uppdatera modellen         5. Uppdatera modellen
        6. Uppdatera 2-4 till filslut 6. Uppdatera 2-4 till filslut
        fig. 5. Algoritmer för adaptiv Huffman-kodning

Ett Huffmanträd är, enkelt beskrivet, ett binärt träd där varje nod, oavsett om det är en intern nod (nod med pekare till andra noder), eller ett "löv" (ett tecken), har en specifik "vikt". Varje nod, förutom rotnoden, har ett "syskon" som delar samma "förälder". Trädet uppvisar syskonegenskap om alla noder kan listas i ordning av ökande vikt, och om varje nod kommer bredvid sitt syskon i listan. Trädets noder listas i ordning från nedre hörnet, där den lägsta vikten finns, genom hela den nivån, och börjar om från samma håll igen i nästa nivå.

fig. 6. Ett Huffmanträd med syskonegenskaper

För att beskriva hur en uppdatering kan gå till kan jag ge ett exempel: Vi har hittills kodad ovanstående träd, och nästa symbol i strömmen är ett A, först kodas A:et, eller avkodas om vi går åt det hållet, och sedan uppdateras vikten för A:et, i detta fall blir den nu 2. Samtidigt uppdateras pekarna för A:s föräldranoder ända tills dess vi har kommit till roten på trädet. Vi ser då att trädet fortfarande har syskonegenskapen (detta kan enkelt kontrolleras genom att trädet söks igenom sekventiellt och att man hela tiden kontrollerar att påföljande tal är mindre än eller lika med det aktuella).

En annan situation kommer dock att uppträda om även nästa symbol i trädet är ett A, då kommer A:ets vikt att vara 3, vilket är mer än både B, C och D, men lika mycket som den nuvarande föräldranoden till A och B. A:et byter då plats med D:et i trädet (kom ihåg att B, C och D har samma vikt, så deras inbördes ordning har inget inflytande), och trädet räknas om. Vikten på föräldranoden för D och B, vilken tidigare var föräldranoden för A och B, är då oförändrad på 4, och förädranoden för C och D får den nya vikten fem. På samma sätt uppdateras resten av vikterna, och vi ser att trädet då igen uppvisar syskonegenskaper.

På detta sätt kommer trädet kontinuerligt att uppdateras, utan att det tar allt för lång tid för varje uppdatering.

Problemet med adaptiv kodning är att man i början inte vet något om dataströmmen, och därför har man inget inledande träd att bygga vidare på. Den enklaste lösningen är att skapa ett träd med 256 tomma noder med en vikt av ett vardera, men det är opraktiskt, det är bättre att börja med ett tomt träd. Men då uppkommer ett problem, hur ska vi koda symboler vi ännu inte sett? Lösningen kallas för utbrytarkod (escape code), och fungerar så att en speciell symbol läggs till i trädet med koden 257 (256 använder vi som filslutsmarkering). Denna kods vikt ändras aldrig, utan kommer hela tiden att generera längsta möjliga sekvens, vilket i början är en bit. När vi har kodad utbrytarkoden lägger vi helt enkelt in den kod som inte förekommit tidigare okodad i filen, och lägger till den i trädet, med vikten ett. Nästa gång vi hittar samma kod har vi den redan i trädet, och kan direkt använda dess kod. Vid avkodningen gör vi på motsvarande sätt; hittar utbrytarkoden och hämtar sedan in ett helt tecken som läggs till i trädet.

Med adaptiv Huffmankodning uppstår dock ett annat problem, nämligen möjligheten till spill. Varje nod i Huffmanträdet har en räknare kopplad till den, där symbolens, eller nodens underliggande symbolers, vikt finns lagrad. För denna räknare måste vi använda någon gängse variabeltyp. Låt oss säga att vi använder ett 16-bitars tal, vad händer då när ett tecken har förekommit 65.536 gånger, då 65.535 är det största tal som kan lagras i ett 16-bitars tal.

Det finns även ett annat problem som kan uppkomma, och som kan uppkomma väldigt tidigt, och det är när den längsta Huffmankoden överstiger den variabel med vilken den sänds över till filen via kodaren. Avkodaren arbetar oftast bit för bit från roten och uppåt, och bryr sig inte hur lång koden är, medan kodaren arbetar åt andra hållet och ackumulerar värdet i en variabel. Om då längden på koden överstiger storleken på denna variabel är vi illa ute. Detta kan illustreras med Fibonaccis talföljd, där varje tal är summan av sina två föregångare: 1, 1, 2, 3, 5, 8, 13 osv. Om vi bygger ett Huffmanträd som har Fibbonaccis talföljd som vikterna kommer vi att märka att koderna blir mycket långa för de symboler som har de minsta vikterna.

Om maximalvärdet som kan kodas är 16 bitar långt betyder det att ett rotvärde på 4181 (18:e talet i Fibonaccis talföljd) kan orsaka spill i trädet. Det problemet, och problemet med att spara vikterna i en variabel hanteras oftast genom att med jämna mellanrum skalera om Huffmanträdet, oftast med en skalfaktor på 2. Problemet (och faktiskt fördelen) är att detta kan omdisponera trädet, eftersom det är heltal vi arbetar med. Trädet kan komma att få en helt annan struktur efter skaleringen, vilket avhjälper problemet med Fibonaccis talföljd.

Nackdelen är att vi tappar "skärpa" vid skaleringen, eftersom frekvenserna inte stämmer helt inbördes. Men, detta är inte alltid en nackdel, dels kommer nya data snabbt att omintetgöra oskärpan, och dels gör vi så att gamla data vägs mindre viktiga än nya data, vilket är bra om en fil byter karaktär, exempelvis i en programfil, från binärdata till textsträngar.

Ett exempel på omskalering:

fig. 7. Ett Huffmanträd före omskalering

fig. 8. Huffmanträdet från figur 7 efter omskaleringen

fig. 9. Huffmanträdet från figur 7 efter omskalering och ombyggnad

Aritmetisk kodning

Aritmetisk kodning jobbar på ett helt annat sätt än Huffmankodning, i stället för att ersätta varje symbol med ett tecken så kodas ett helt meddelande till ett flyttal. Detta går till så att det för varje symbol som finns i meddelandet som ska komprimeras beräknas en sannolikhet, och sedan tilldelas för varje symbol en del av talområdet mellan 0,0 och 1,0 där delarna är i proportion till sannolikheten.

Dessa tal används sedan för att koda meddelandet på ett sådant sätt att man hela tiden beräknar en undre och en övre gräns som är möjlig för att representera symbolen. Om vi säger att vi har meddelandet "BILL GATES" så skulle vi få följande sannolikhetstabell och områden:

        Tecken     Sannolikhet  Område
        mellanslag 1/10         0,00 <= x < 0,10
        A          1/10         0,10 <= x < 0,20
        B          1/10         0,20 <= x < 0,30
        E          1/10         0,30 <= x < 0,40
        G          1/10         0,40 <= x < 0,50
        I          1/10         0,50 <= x < 0,60
        L          2/10         0,60 <= x < 0,80
        S          1/10         0,80 <= x < 0,90
        T          1/10         0,90 <= x < 1,00
        fig. 10. Tabell för aritmetisk kodning av ett meddelande 

När vi kodar av går vi motsatt väg, först ser vi att talet ligger mellan 0,20 och 0,30, vilket ger oss att det börjar med "B". Vi drar ifrån 0,2 och dividerar med denna symbols bredd (0,10) vilket ger ett tal mellan 0,50 och 0,60 vilket betyder "I". Så håller vi på till vi upptäcker koden för "slut på data" (vilken inte inkluderades i detta exempel).

Trots att aritmetisk kodning enklast kan förklaras med hjälp av flyttal i området 0-1, så är det betydligt enklare att på en dator jobba med heltalsmatematik, och dessutom går det betydligt snabbare eftersom flyttalsmatematik på datorer är ganska långsamt. Om vi jobbar med 16-bitars heltalsmatematik skulle vi få gränserna 0 och FFFFh (0-65.535 decimalt). Det ställer dock till lite problem, vi skulle hellre vilja ha talet 10000h som övre gräns. Men det är enkelt att tänka sig med bara 16 bitar, om vi hela tiden tänker oss att vi kan "fylla på" med Fh från höger på den övre gränsen och med 0 på den lägre så får vi i praktiken gränserna 0 och 10000h. Detta eftersom talet 0.11111... binärt (0.FF.... hexadecimalt) är samma sak som 1. För att visa detta tar jag en liten ekvation, där jag använder den decimala motsvarigheten:

        x = 0,99999....
        10x = 9,99999.... (vi har ju oändligt många nior)
        10x - x = 9,99999... - 0,99999...
        9x = 9
        x = 1
        0,99999... = 1

"Men varför är det då så mycket bättre med aritmetisk kodning än Huffmankodning?" kan man fråga sig. Svaret är enkelt: vi kommer betydligt närmare det informationsinnehåll vilket jag förklarade i början. Aritmetisk kodning kommer alltid att koda lika bra eller bättre än Huffmankodning. Vi kan ta som exempel texten "AAAAAAA". Om vi sätter sannolikheterna så att "A" ges området mellan 0,00 och 0,90 och filslutssymbolen områden 0,90 och 1,00, och kan då tillverka det kodade meddelandet:

        Nytt tecken  Undre gräns  Övre gräns
                     0            1
        A            0            0,9
        A            0            0,81
        A            0            0,729
        A            0            0,6561
        A            0            0,59049
        A            0            0,531441
        A            0            0,4782969
        filslut      0,43046721   0,4782969
        fig. 11. Aritmetisk kodning av ett meddelande

Modeller av högre ordning

Om vi tänker oss en källkod skriven i Pascal, så kanske tecknet för ny rad har en sannolikhet av 1/40 att inträffa, om man använder tidigare modellering. Men efter ett semikolon (";") så har den kanske sannolikheten 39/40, och det borde ju kunna tas till vara bättre, kan man tycka. En metod för detta är att använda en modell av högre ordning ("higher order model"). Det jag hittills berört är modeller av ordning 0 (order-0), dvs. ingen hänsyn tas till framförvarande tecken. Om vi i stället hela tiden tittar på tecknet före har vi en modell av ordning 1, och om vi tittar på fler tecken kan vi komma upp i högre ordningar.

Det låter ju bra, men det finns nackdelar. Om vi ska skicka med en sannolikhetstabell med den komprimerade filen kommer detta att ta upp mycket stor plats. I det första exemplet med Huffman-kodning tog vår tabell upp 256 tecken. Med en modell av ordning 1 kommer vi ha 256 sådana tabeller! Detta skulle ge en tabell på upp till 65.536 tecken, vilket kräver en ganska stor fil för att ö.h.t. vara lönsamt.

Hur går vi då förbi detta? På samma sätt som tidigare, med adaptiv kodning. Problemet är här att om vi börjar med att initiera 256 tabeller där alla tecken i dem har en grundläggande sannolikhet på 1/256 vardera, så skulle alla tecken koda åtta bitar vid första uppkomsten. Om vi exempelvis tar kombinationen "qu" i engelskan, så är "u" en inte så vanlig bokstav, men efter "q" är den betydligt vanligare ("question", "query", "quarter" o.s.v.). Om vi då skulle koda med en modell av ordning 0 skulle u få en lång bitsträng, men med ordning 1 borde den få en kortare, i de fall den följer på ett q. Om vi då börjar med en inledande sannolikhet av 1/256 skulle u först kodas som 8 bitar, vilket inte motsvarar dess informationsinnehåll.

Vi får då ta användning av den metod som redan beskrivits ovan, en utbrytarkod. Denna utbrytarkod kommer att återge kontrollen till "huvudtabellen", den tabell som inte tar hänsyn till framförvarande tecken. Finns tecknet med där kodas det, och läggs till i tabellen för den kod som föregick den. Om den inte fanns i huvudtabellen skickas tecknet med okomprimerat, och det läggs in i båda tabellerna. Nästa gång samma teckenkombination förekommer har vi redan en sannolikhet för den, och kan koda den utan problem.

Man kan tycka att kodning av högre modell alltid genererar bättre komprimering. Om vi har en modell av ordning 3 skulle vi få 16.777.216 olika tabeller, och det skulle krävas en mycket lång dataström för att få denna modell att komprimera, och en stor del av detta utrymme skulle aldrig användas, vilket gör att vi slösar datorminne i onödan. Det är då vi har nytta av denna "fall-tillbaka" ("fallback") metod och generera utbrytarkoder.

Vi tar ett exempel, låt os säga att vi har kontexten "BEH" (ordning 3) och ska koda ett "Ö" för första gången. Vi hittar inte Ö i tabellen för BEH, så vi skickar en utbrytarkod, och tittar i tabellen för "EH" (ordning 2). Ej heller där hittar vi Ö, och faller tillbaka på "H"-tabellen (ordning 1). Så håller vi på till vi kommer till tabellen av ordning 0 (eller tills dess vi hittar koden, naturligtvis). Om vi inte hittar den ens i denna tabell faller vi tillbaka på en speciell ordning (-1), där vi har samtliga förekommande tecken med en vikt av ett, och ur denna tabell genererar vi tecknet. Sedan uppdaterar vi naturligtvis tabellerna för "", "H", "EH" och "BEH" med avseende på bokstaven Ö.

Ordbaserad komprimering

För att med ett konkret exempel visa hur ordbaserad komprimering fungerar, med ett exempel som använder Svenska Akademins ordlista i 1986 års upplaga. Inledningen av föregående mening skulle då kunna kodas såhär:

165/13 45/33 344/13 130/4 284/23 131/22

Texten presenteras som en enkel tabell med siffror som kan slås upp. Det första talet motsvarar sidnummer och det andra talet vilket ord på sidan det är fråga om. Svenska akademins ordlista har 674 sidor, vilket kan kodas i 10 bitar. Varje sida har garanterat färre än 256 ord, vilket betyder att varje ord kan kodas med 18 bitar, och de första sex orden som visats ovan skulle därför endast ta upp 108 bitar, vilket kan jämföras med de 248 bitar som det tar upp som i vanlig text (8 bitar per bokstav). En komprimering på 56%!

Precis som med de komprimeringsmetoder som tidigare behandlas kan ordbaserad komprimering göras med en statisk eller adaptiv modell, och i detta fall är det inte alltid helt självklart vilken metod som är att föredra.

Som exempel kan vi ta en databas innehållande Sveriges bilregister. Vi skulle i förväg kunna bygga upp en ordlista med ord såsom "Volvo", "Saab", "1994" o.s.v., och när denna ordlista har kompilerats görs den tillgänglig för både kodaren och avkodaren. Eftersom en databas av det här slaget av sin natur kan bli rejält stor så är det ingen större försämring av komprimeringen att hela tiden skicka med ordlistan.

Detta bilregister skulle vara ett exempel på en statisk ordlista, eftersom den byggts upp innan komprimeringen genomförs. Vi kan även för att förbättra komprimeringen räkna på en exempeldatabas, med ett mindre antal bilar, och göra ett Huffmanträd med de olika biltyperna som symboler, och därigenom uppnå ännu bättre komprimering.

Användning av ordbaserad komprimering med hjälp av en statisk ordlista är beroende av implementationen, och kan inte användas som en universell komprimerare. Vi kan exempelvis inte använda bilregistrets ordlista för att komprimera ett medlemsregister för den lokala syföreningen. De flesta algoritmerna för ordbaserad komprimering är adaptiva, de bygger upp sin ordlista allt eftersom texten läses in, och de startar antingen med en tom ordlista, eller en fördefinierad standardordlista.

Algoritmen för en enkel adaptiv ordbaserad komprimerad kunde vara:

        1.      Läs ett ord från infilen.
        2.      Finns ordet redan i ordlistan?
        3.      om ja:  Mata ut en pekare till ordet i ordlistan till utfilen.
                om nej: 3a. Lägg till ordet i ordlistan.
                        3b. Mata ut ordet till utfilen.
        4.      Fortsätt läsa till filslut.
        fig. 12. Algoritm för adaptiv ordbaserad komprimering

Ordbaserad komprimering uppfanns i slutet av 1970-talet av två israeliska forskare, Jacob Ziv och Abraham Lempel. Dessa två publicerade 1977 och 1978 två artiklar om denna typ av komprimering[1], vilka populärt kallas för LZ77 och LZ78. Forskning inom datakomprimering hade tills dess mestadels handlat om olika sätt att optimera Huffman-kodning, och det var därför ett stort genombrott.

Trots detta dröjde det fram till 1984 innan denna typ av komprimering fick sitt stora genombrott, när Terry Welch publicerade "A Technique for High-Performance Data Compression". Denna artikel beskrev hans implementation av LZ78, kallad LZW, vilken idag används i så olika sammanhang som modemkommunikation (v.42bis) och grafiska bilder (CompuServes GIF - Graphical Interchange Format). Nackdelen med denna komprimeringsmetod är att den är patenterad, vilket ställer till problem om man vill använda den.

Det är lätt att tro att LZ77 och LZ78 är närbesläktade, eftersom det i dagligt tal talas om "Lempel Ziv-komprimering", precis som om de vore samma sak. Så är dock inte fallet, och jag ska nu förklara skillnaden mellan de två.

Komprimering med ett glidande fönster

Komprimering med LZ77-algoritmen sker genom att text jämförs med text som ligger i en buffert, vilken består av den senast inlästa delen av dataströmmen. LZ77 använder en datastruktur som består av ett textfönster vilket är delat i två delar. Den första delen är ett stort block av redan kodad eller avkodad text, och den andra, vanligen betydligt mindre, är en förhandsbuffert ("look-ahead buffer"). Förhandsbufferten består av text som ännu ej kodats. Vanligen är textfönstret flera tusen bytes stor, medan förhandsbufferten är betydligt mindre, exempelvis tio eller hundra bytes. Algoritmen försöker matcha innehållet i förhandsbufferten med strängarna i "ordlistan".

fig. 13. En LZ77-buffert under arbete

I figur 13 visas en del av en C-källkod under kodning. Textfönstret är i detta fall 59 bytes, med en 12 bytes förhandsbuffert.

LZ77-komprimering går ut på att det hela tiden matas ut en serie koder, vilka är uppdelade i tre delar. Dessa tre delar är först ett offsetvärde till en fras i textfönstret, sedan längden på denna fras och som tredje del, den första symbolen i förhandsbufferten som kommer efter den kodade frasen. Om ingen matchande fras kan hittas skickas ett offsetvärde och fraslängd på noll ut, och sedan en symbol.

I exemplet i figur 13 ovan ser vi att frasen "<MAX ; j++)" kommer upp i förhandsbufferten, och genom att leta i textbufferten hittar vi "<MAX" som är den längsta matchande frasen. Den finns på position 14 i bufferten (vi börjar räkna på noll), och är tre bytes lång. Efter frasen följer ett mellanslag, så nästa kod i den komprimerade filen blir (14, 4, " "). När denna fras har kodats skiftar bufferten åt vänster med fem steg för att komma förbi den nyss kodade frasen, och vi får en buffert som den i figur 14.

fig. 14. Bufferten i fig. 13 efter en kodning

Vi kodar på samma sätt i detta fall, och kommer då att koda (35, 3, "+"). Så håller vi på tills dess att filen är slut, och att implementera detta i ett program är tämligen enkelt. Det svåra är bara att alltid hitta den längsta koden, men det går. Däremot är det betydligt enklare att skriva avkodarprogrammet, eftersom det inte behöver leta efter matchningar. Avkodarrutinen behöver bara hålla reda på textfönstret, och när vi läser in och avkodar en kod, letar vi på frasen i fönstret, matar ut frasen och påföljande tecken och skiftar bufferten åt vänster.

Det finns dock vissa problem med LZ77-kodning. Ett är att tiden för komprimering blir mycket större om vi använder en större buffert, eftersom mer data måste jämföras för att hitta en träff. Däremot spelar storleken på fönstret ingen övervägande roll vid avkodningen, och eftersom man oftast har tid att lägga ned lite extra arbete på kodningsfasen är detta inget större problem.

Ett annat problem är rent programmeringstekniskt, själva sättet att koda fönstret. Antagligen tänker man sig att fönstret ska "flyta" fram över data, och att dess innehåll hela tiden ska skiftas runt. Problemet är att när vi hanterar stora fönster, exempelvis upp emot fyra kilobyte stora, så tar det lite för lång tid att mellan varje kodning skjuta hela fönstret ett par bytes. Lösningen på det problemet är att i stället ha ett fixerat fönster, och sätta en pekare till var fönstret börjar och slutar. Då kan vi i stället för att skifta hela fönstret exempelvis fem bytes, flytta pekaren fem bytes framåt och samtidigt läsa in fem bytes från filen på dessa positioner. Förvisso gör detta det lite svårare med själva sökningen av matchningar, eftersom den matchande strängen naturligtvis kan befinna sig över "kanten". Det får man dock ta, eftersom det är betydligt bättre med ett fixerat fönster. Tidsförlusten med strängsökningar över kanten uppväger problemet med skiftningen av fönstret.

Det finns dock ett stort problem som inte går att gå runt med den grundläggande LZ77-kodningen, och det är när det inte finns några matchande fraser i bufferten. När matchande fraser hittas blir komprimeringen oftast mycket stor, men om vi exempelvis måste koda ett "c" som inte hittades i bufferten så måste vi koda (0, 0, "c"). Och om vi då skulle använda ett fönster på 4 kilobyte och en sexton bitars förhandsbuffert så skulle det ta tolv bitar att koda fönsterpositionen och fyra bitar att koda fraslängden. Detta skulle ge oss tjugofyra bitar för att koda en åtta bitars symbol, en expandering på tre gånger!

En förbättring av LZ77-komprimeringen

Det är huvudsakligen två förändringar i hur denna algoritm arbetar i förhållande till LZ77. Det första är sättet på vilket textfönstret hanteras. I den ursprungliga LZ77-algoritmen sparas fönstret undan som en lång dataström, utan någon organisation. I LZSS sparar fortfarande texten i ett datafönster, men ovanpå detta skapas en ytterligare datastruktur, ett binärt sökträd. När en text lämnar förhandsbufferten och kommer in i textfönstret sorteras den även in i ett sökträd på ett sådant sätt att sökning underlättas avsevärt. Detta medför att söktiden ej längre kommer att vara proportionell mot produkten av fönsterstorleken (som med LZ77), utan proportionell mot tvålogaritmen av fönsterstorleken, multiplicerad med fraslängden. Detta gör inte bara kodningsdelen snabbare, utan underlättar även användning av större fönsterstorlek. En dubblering av fönsterstorleken kommer ju inte längre nödvändigtvis att resultera i en dubblering av söktiden, utan kanske bara i en obetydlig ökning.

Den andra stora förändringen är sättet på vilken data som kodats sparas i utfilen. LZ77 matade hela tiden ut ett offsetvärde, en fraslängd och bokstaven som följde på frasen, vilket betyder att LZ77 alltid alternerar pekare med tecken, oberoende på hur indataströmmen ser ut. LZSS, däremot, tillåter pekare och data att mixas fritt. I början är det svårt för komprimeringsrutinen att hitta fraser, och då skickas tecken ut ett och ett. Under LZ77 gav detta enorm dataexpandering, men inte under LZSS. När sedan det blir lättare att hitta fraser är LZSS även där smartare, LZ77 var alltid tvunget att mata ut ett tecken efter varje fras, men så icke LZSS. Algoritmen görs så att varje symbol inleds med en bit som bestämmer hur kommande data ser ut. Hur genomför vi då detta rent praktiskt? Jo, vi skickar ut en bit före varje tecken, vilken får bestämma hur kommande data ser ut. Om vi skickar en nolla så skickar vi en hel byte, och om vi skickar en etta är det ett offset/längd-par.

Både LZ77 och LZSS kallas för "giriga" algoritmer, eftersom de analyserar vilken kodningsmöjlighet som ger bästa möjliga komprimering. Som exempel kan vi ta en ordbaserad komprimering, i vilken det tar tjugofem bitar att koda ett par med offset/längd och nio bitar att koda ett okänt tecken. Detta skulle ge att den punkt från vilken vi tjänar på att koda med pekare är tre bytes, en träff på två bytes skulle kodas som två vanliga tecken.

Låt oss ta ett exempel. Vi håller på och kodar en lärobok i programmering, och efter ett tag hittar vi frasen "Go To Statement Considered Harmful", och i textfönstret har vi bland annat dessa fragment: "Go T", "o S", "tat" samt " Stat." En "girig" komprimeringsrutin skulle naturligtvis koda på detta sätt:

        Offset/längd för "Go T"      25 bitar
        Offset/längd för "o S"       25 bitar
        Offset/längd för "tat"       25 bitar
                                     = 75 bitar

        Offset/längd för "Go T"      25 bitar
        Tecken "T"                   9 bitar
        Tecken "o"                   9 bitar
        Offset/längd för " Stat"     25 bitar
                                     = 68 bitar

LZ78-komprimering

Visserligen kan detta förbättras genom att vi använder en större buffert, men oavsett hur stor den kommer att vara kommer vi förr eller senare att tappa fraser, och dessutom tar det längre tid att söka ju större buffert vi har. Visserligen blir inte förlusten så fruktansvärt stor om vi använder LZSS-metoden, men den kommer i alla fall att märkas. Dessutom kommer längden på pekaren att öka, och gränsen för om det lönar sig att koda en pekare kommer att öka, vilket gör att korta fraser inte kommer att kodas som fraser, utan som individuella tecken, och detta kommer att minska komprimeringens effektivitet avsevärt.

En annan flaskhals är storleken på förhandsbufferten, om vi skulle ha en fras som är större än förhandsbufferten, men som finns i hela sin längd i textbufferten kommer vi vara tvungna att dela upp den. Även här kan man tycka att man borde öka storleken på bufferten, men här är problemet att komprimeringstiden tar extremt längre tid, proportionellt mot storleksändringen. Om vi ändrar storleken från 16 bytes till 1 kilobyte kommer tiden det tar för att jämföra varje fras att ta sextiofyra gånger längre tid. Och det är inte bra.

Det är därför man skapade LZ78. I stället för att använda en buffert i vilken träffar kan sökas i, så sparas i stället alla hittills kodade fraser undan. Kodningsförfarandet i LZ78 liknar till stor del det i LZ77, LZ77 matar ut en serie koder, vilka består av en pekare, fraslängd och påföljande tecken. LZ78 skickar också ut en serie koder, dessa består av frasnummer och påföljande tecken. Någon fraslängd behöver inte skickas med, eftersom den redan är definierad för varje fras. Till skillnad mot LZ77 börjar LZ78 med en nästan tom ordlista, den består bara av en enda kod, nämligen en null-sträng, dvs. en sträng med längden noll.

Vid kodningen läses tecken för tecken in, dessa sammanställs i en sträng. Kodaren fortsätter att göra så tills dess det inte längre finns någon likadan fras i ordlistan. När detta uppstår skickas koden för den fras som var likadan ut, samt koden för det påföljande tecknet. Samtidigt läggs denna sträng till i ordlistan, så att nästa gång samma fras uppkommer kan vi lätt hitta den.

Per definition kommer en tom sträng alltid att matcha fras noll i ordlistan, vilket medför att vi, när vi träffar på ett nytt tecken, kan koda denna nollfras tillsammans med tecknet, och lägga till detta i ordlistan. Första gången vi träffar på bokstaven "D" kommer vi att koda (0, "D"). I exemplet nedan kodar vi en del av en engelsk ordlista.

        Text in: "DAD DADA DADDY DADO..."
        Frasnr  Tecken Kodad sträng
        0       "D"    "D" (blir nummer 1 ordlistan)
        0       "A"    "A" (2)
        1       " "    "D " (3)
        1       "A"    "DA" (4)
        4       " "    "DA " (5)
        4       "D"    "DAD" (6)
        1       "Y"    "DY" (7)
        0       " "    " " (8)
        6       "O"    "DADO" (9)
        fig. 15. LZ78 i arbete

Ordlistan fylls på tämligen fort med nya fraser, allteftersom vi läser in och kodar. I det enkla exemplet ovan fick efter ett relativt litet antal tecken nio olika fraser.

Precis som i LZ77 bestämmer storleken på frasminnet i LZ78 hur bra kodningen sker. Egentligen borde ett större ordlista resultera i en bättre komprimering, men så enkelt är det inte. Precis som i LZ77 måste ju en pekare kodas, och storleken på denna pekare ökar ju i takt med att mängden fraser ökas. Om vi har 4.096 fraser måste vi koda en 12 bitars pekare för varje tecken, vilket gör att alla fraser kortare än tre tecken kommer att leda till dataexpansion i stället för datakomprimering. Förhållandet större ordlista - bättre komprimering gäller bara om storleken de indata som ska komprimeras går mot oändligheten.

Huvudproblemet med LZ78 är egentligen hur vi ska koda ordlistan. Att bara sätta upp en lista med alla fraser i är svårt, eftersom fraslängderna kan variera i längd allt från en byte upp till antal fraser i ordlistan genom två bytes (om vi har en serie likadana fraser, exempelvis "AABABCABCDABCDEABCDEF..."). En lösning på detta är att koda ordlistan som ett binärt träd, där vi börjar med en rot som består av nollsträngen. Från denna rot kommer det att gå ut en gren för varje tecken som hittas, och från dessa grenar kommer ytterligare grenar att gå ut. Att det går att genomföra på detta sätt beror på att fraserna hela tiden bygger på varandra, och blir längre och längre. Vi kan ju inte ha en fras på tio tecken, om vi inte innan det har en fras på nio tecken som innehåller de inledande tecknen.

Ett problem med LZ78 som inte finns i LZ77 är att avkodaren måste upprätthålla samma träd som kodaren har. I LZ77 skickade vi ju bara en pekare och en fraslängd, medan vi i LZ78 skickar endast ett frasnummer.

Ytterligare ett problem som inte nämnts ännu, är vad man ska göra om ordlistan blir full. Oavsett hur stor ordlista vi har, så kommer den förr eller senare att fyllas. Vi har då två saker att välja på, om vi ska fortsätta med komprimeringen, och helt enkelt sluta lägga till nya fraser i ordlistan, eller om vi ska rensa hela ordlistan och börja om från början igen. Om vi behåller ordlistan, och filen byter karaktär (t.ex. i ett program från binärdata till text), så kommer detta att leda till betydligt sämre komprimering, och om vi rensar ordlistan kommer vi ju till en början att få dålig komprimering igen. COMPRESS-programmet för Unix löser detta på ett elegant sätt. När ordlistan är full börjar programmet kontrollera hur hög komprimeringsfaktor som uppnås. Så länge den håller sig på ungefär samma nivå behålls ordlistan, men om den sjunker rensas ordlistan, och programmet börjar om från början med en tom ordlista.

En förbättring av LZ78

LZSS-algoritmen som diskuterades tidigare förbättrade LZ77 genom att ta bort kravet på att ett tecken skulle följa varje frasreferens. Det är till och med så att det inte förekommer några enskilda tecken alls i LZW, utan endast fraser. Detta möjliggörs genom att komprimerings- och dekomprimeringsrutinerna förladdas med en ordlista som innehåller hela den uppsättning symboler som förekommer i filen som ska komprimeras. Varje gång en kod matas ut, läggs den resulterande strängen till i fraslistan, och vi kommer därför snabbt att fylla på frasminnet.

Det finns dock ett problem med LZW-kodning, och det är möjligheten att avkodaren får upp en kod som ännu inte definierats. Detta kan dock endast hända vid speciella förutsättningar, och det är när sekvensen tecken,sträng,tecken,sträng förekommer, till exempel "VIKTIGT!VIKTIGT!...VIKTIGT!VIKTIGT!X", vid kodningen av den sista strängen kommer en kod att matas ut som ännu ej definierats. Eftersom detta är det enda tillfälle som det kan ske vid, kan man skriva en rutin som tar föregående kod, och lägger till samma tecken som med vilket frasen började, och så har hela problemet lösts.

DESTRUKTIV KOMPRIMERING

Inledning till destruktiv komprimering

Ljudkomprimering

Vid digitalisering, sampling, av ljud använder man sig en viss samplingsfrekvens, vilken alltså talar om hur ofta man samplar. Den högsta frekvens en normal människa kan uppfatta är omkring 20 kHz, och för att sampla den skulle vi behöva en samplingsfrekvens på 40 kHz, eftersom det i de 20 kHz ingår en hel vågform. Vanligt är att man använder en samplingsfrekvens på 44 kHz, till exempel används detta för CD-skivor. Detta kommer att ge oss mer än vi behöver. En annan sak som inverkar på ljudskärpan är hur stor spannbredd vi använder vid samplingen. Vanligen används 8 eller 16 bitar, vilket motsvarar 128 eller 32.768 nivåer (eftersom ljuden går från både negativt till positivt måste vi använde en bit för att indikera riktningen). Inom telefonin används vanligen 8 kHz samplingsfrekvens, vilket skär av många högfrekventa toner, men eftersom tal vanligen består av mest lågfrekventa toner, går det utmärkt utan.

Hur ska vi då komprimera ljuddata? Odestruktiv komprimering kan ge mycket skilda resultat, från ingen komprimering alls till en resulterande storlek nära 10% av originalstorleken. Ett sätt att komprimera kan vara att göra om de delar av ljudet som är nära nog tystnad till verklig tystnad, detta ger dock också mycket skilda resultat. Vissa ljudsamplingar har mycket tystnad, och vissa har ingen alls.

Ett annat sätt är att minska ner antalet bitar som används för att representera. Om vi tar en vanlig röst, exempelvis, så måste vi sätta maximivärdet ganska högt för vilka ljudstyrkor (spänningstal) som kan registreras, för att även fånga in om någon skriker. Problemet är att vi tappar skärpa för de låga ljudstyrkorna, om någon exempelvis viskar. Vad vi då kan använda oss av är en logaritmisk skala, som ger större skärpa åt de låga nivåerna, och lägre skärpa åt de höga. Eftersom de höga nivåerna är de som varierar mest, är detta ett utmärkt sätt att komprimera på. Vi kan då komprimera ett ganska stort spann av ljudnivåer till ett relativt litet antal bitar, och ändå behålla skärpan där den behövs mest. Och dessutom gör detta att komprimeringsgraden hela tiden kommer att vara konstant, vilket är en förutsättning för telefonsamtal, där varje samtal har en viss bandbredd, varken mer eller mindre.

Destruktiv grafikkomprimering

Huffman- och aritmetisk kodning, som arbetar med sannolikheter, har svårt att komprimera grafik, eftersom bilder oftast har en jämn frekvens av olika symboler, och dessa komprimeringsmetoder kräver varianser i komprimeringen för att fungera någorlunda vettigt.

Ej heller ordbaserad komprimering kan komma till sin fulla rätt på bilder. Som ett exempel kan vi ta en bild av ett spjälstaket, där ser varje spjäla för det mänskliga ögat helt lika ut, men om man tittar riktigt noga så skiljer de sig lite grann mellan varje, och eftersom denna skillnad finns kan man inte komprimera bilden på ett vettigt sätt med denna metod heller.

Det är på grund av dessa problem som andra komprimeringsmetoder har utvecklats, det finns ett par olika, som exempelvis differentiell modulation, vilket innebär att man i stället för att för varje punkt definiera en specifik färg, definierar hur stor skillnaden är gentemot föregående punkt. Eftersom övergångar i bilder sällan sker direkt från en punkt till en annan, så kan detta göras utan att förlora allt för mycket skärpa i bilden.

Det finns även olika adaptiva metoder, vilka liknar differential modulation, men i stället för att bara ta hänsyn till föregående pixel, så tar man skillnaden mot medelvärdet av de omkringliggande punkter, eller åtminstone de punkter man redan visat av dessa (det vill säga oftast punkterna ovanför och till vänster om den aktuella).

Tyvärr ger ingen av ovan nämnda metoder mer än liten komprimering, och dessutom finns de i många olika format. Därför tillsatte Internationella standardiseringsorganisationen, ISO, och den Internationella telekommunikationskommisionens (ITU) tekniska kommitté, CCITT, till en grupp som skulle utveckla en standard för destruktiv grafikkomprimering. Denna grupp heter JPEG, och de har nyligen lagt fram det slutgiltiga förslaget till en standard, vilken används flitigt i moderna programvaror. Komprimering med denna metod kan vara så bra att resultat blir endast en tiondel av originalstorleken.

Komprimering med JPEG sker i tre steg, vilka visas i figur 16 nedan.

fig. 16. De tre stegen vid JPEG-komprimering

Det första steget, den diskreta kosinustransformen, är det som är hemligheten bakom varför det kan bli så bra komprimering. DCT är ett sätt att omvandla ett sätt att presentera data till ett annat, och liknar FFT, snabb Fourier-transform, som bl.a. används vid analysering av ljud, men även till mycket annat.

För att första DCT är det en fördel om man förstår FFT. FFT är en uppsättning matematiska formler tar en given, av flera funktioner sammansatta signal, och omvandlar den till en serie kosinuskoeffecienter vilka väl approximerar den ursprungliga funktionen. Om man tar en funktion som är sammansatt av tre kosinuskurvor, kommer vi ur FFT att få tre värden, vilka kan läggas samman för att återfå samma funktion som vi hade från början.

Det är detta som DCT gör, men på bilder. Insignalen är bilden, eller en liten del av den, och ur denna fås en serie frekvenser, vilka sedan kan sättas samman till ungefär samma bildsegment igen. Skälet till att bara ta en del av bilden vid varje tillfälle är att det dels tar alldeles för lång tid att räkna på en stor del av bilden, eller för den delen hela bilden, och att det är enklare att approximera funktionsvärden ur ett mindre utsnitt, eftersom "funktionen" inte kommer att vara periodisk. Dessutom kommer funktionen inte att vara någon funktion i den vanliga meningen, eftersom insignalen på ett sätt är tredimensionell, x- och y-axlarna representerar bildpositionen, och z-axeln den färg som den aktuella bildpunkten har.

När man utfört denna matematiska formel kommer man att få en matris, som är lika stor som det bildsegment man från början hade. Man kan då ställa sig frågan vad det är för mening med DCT, om man får tillbaka lika mycket data som man hade från början. Skillnaden är vad siffrorna representerar. Från början representerade siffrorna färgen för varje enskild punkt i bildsegmentet, men efter DCT representerar varje siffra en specifik frekvens, och magnituden av dessa frekvenser. Eftersom det mänskliga ögat är mest känsligt för låga frekvenser, och inte alls så bra ser de höga (som exempelvis breda, glest placerade svarta balkar, gentemot tunna tätt placerade sådana balkar), så räcker det att behålla en bra skärpa på de låga frekvenserna, och approximera de höga frekvenserna mer och mer.

När bilden sedan sätts samman igen kommer bilden att ha tappat mycket av de höga frekvenserna, de tunna balkarna i exemplet ovan kanske har ersatts med en gråskala, men eftersom det är på det sätt vi uppfattade dem från början, så kommer vi inte att se någon drastisk skillnad. I fallet med de breda balkarna, så hade de en såpass låg frekvens att de inte tappat något alls, eller endast mycket litet, av dess ursprungliga skärpa.

Dessutom kan skalningen, kvantificeringen, av utdatat från DCT göras olika övergripande, och man kan därigenom få olika kvalitetsfaktorer, från knappt märkbar, till mycket märkbar. Men även när man använder den faktor som gör kvalitetförsämringen synlig, så kommer vi hela tiden att kunna se vad det var för bild från början, det övergripande utseendet på bilden förändras aldrig, bara skärpan på de individuella partierna.

Komprimering av rörliga bilder

Hur ska man då komprimera rörliga bilder? Det första förslaget borde vara att helt enkelt sätta ihop en bunt JPEG-komprimerade bilder och visa dem en och en efter varande. Problemet är bara att det är väldigt ineffektivt. Varje bild måste beräknas för sig, och likheter i olika bilder, vilket förekommer till stor grad, eftersom det oftast bara är en liten del av bilden som rör sig, utnyttjas inte, och detta leder till att komprimeringen blir ineffektiv.

MPEG bygger just på detta, att likheterna mellan de olika bilderna är mycket stor, men varje bild skapas inte på ett sådant sätt att den bygger på den föregående. Det finns tre typer av bilder, "frames", nämligen "I", "P" och "B". En I-bild ("intra frame") är en vanlig stillbild, som till stor del liknar en JPEG-komprimerad bild, och den innehåller alltså hela bilden. En P-bild ("predicted frame") innehåller skillnaden mellan den aktuella bilden, och den föregående, och en B-bild ("bidirectional frame") innehåller skillnaden mellan föregående och nästa bild, så även nästa bild måste kännas till för att kunna visa bilden. Detta är mycket effektivt för att komprimera bilder, men är mycket svårt att implementera.

En serie bilder ser vanligen ut så här: IBBPBBPBBPBBIBBPBBPB...

Var tolfte bild är en I-bild, vilket bygger på beräkningar att det behövs en ny bild var 0,4:e sekund (detta gäller för USA och Japan, det är andra siffror för europeiska bilder, eftersom vi använder ett annat TV-system). Kvoten mellan antalet B- och P-bilder grundar sig på experiment.

För att kunna visa detta måste sändaren skicka bilderna i ordningen 0, x, x, 3, 1, 2, 6, 4, 5 (där x kan vara ingenting om det är den verkliga startpunkten, eller tidigare bilder), eftersom de första I- och P-bilderna måste vara kända för att kunna koda av B-bilderna...

Med i standarden följer en komprimeringsmetod för ljud, vilket gör det en komplett standard för att sända kompletta TV-program och allting. Detta sker redan experimentellt, och när den slutgiltiga standarden från MPEG är klar, kommer det att utföras i stor kommersiell skala. Åtminstone har flertalet stora TV-bolag uttalat sin förhoppning om att göra så. Den europeiska musik-TV-kanalen MTV planerar att experimentellt sända digitalt komprimerat med start 95-07-01.

Komprimering är det som gäller för framtiden, verkar det som.

LITTERATURFöRTECKNING

"The MPEG-FAQ version 2.0 11 maj 1993"
Phade Software (phade@cs.tu-berlin.de)

"Tillämpad signalanalys"
Anders Svärdström
Studentlitteratur
ISBN 91-44-25391-5

reportage ur "TELE-satellit TV"
TELE-satellit, TELE-audiovision Medien GmbH

reportage ur "TV 13 degrees East"
Eutelsat

samt

diverse hjälpsamma personer inom svenska Fidonet

© Copyright 1995 Peter Karlsson
Alla rättigheter reserverade

[2]Artikeln heter "A Technique for High-Performance Data Compression"