Biosignaalien tiivistäminen.

Timo Tossavainen

Tampereenyliopisto

Tietojenkasittelyopin laitos

Progradu -tutkielma

1.10.1999

Pro gradu -tutkielma,93sivua

Lokakuu 1999

Tiivistelma

Tutkimuksessa arvioitiin useiden eri tiivistysmenetelmien soveltuvuutta Helsin-

gin yliopistollisen keskussairaalan otoneurologisessa laboratoriossa mitattuihin sil-

manliikesignaaleihin.Laaketieteellisetmittauksethalutaansailyttaajatkotutkimus-

ta varten ja biosignaalit vievat muihin mittauksiin verrattuna paljontilaa. Tallen-

nusresurssien tarvetta voidaan vahentaa tiivistamalla tietoa. Tiedon tiivistaminen

voidaan tehda haviottomasti, jolloin alkuperainen tieto sailyy sellaisenaan, tai ha-

viollisesti, jolloin alkuperaisesta tiedosta sailytetaan jokin approksimaatio. Alueen

aiempitutkimusonkeskittynyt sydansahkokayrien tiivistamiseen;tietaakseni tama

tutkimuson ensimmainen,jokaontehty silmanliikesignaalientiivistamisesta.

Haviottomista menetelmista tutkittiin universaalikoodausta, sanakirjamenetel-

mia LZ77 ja LZW, Human-koodausta ja aritmeettista koodausta. Parhaat tulok-

set saavutettiin aritmeettisella koodauksella ja tutkimuksen aikana kehitetylla uu-

dellaparametroituihinuniversaalikoodeihinperustuvallamenetelmalla.Haviollisista

menetelmista tutkittiin skalaarikvantisointia, dierentiaalista pulssikoodimodulaa-

tiota ja muunnoskoodausta; muunnoskoodauksessa tiivistamiseen kaytettiin kyn-

nystamistaja tutkimuksen aikanakehitettya uuttakvantisointimenetelmaa.Haviol-

lisista menetelmista parhaat tulokset saavutettiin muunnoskoodauksella. Uudella

kvantisointimenetelmallasaavutettiinselvastiparempiatuloksiakuinkynnystamisel-

la. Tutkimuksessa saavutetut tulokset seka haviollistenetta haviottomienmenetel-

mien tapauksessa ovat samaa luokkaa ja osittain parempia kuin aiemmissa biosig-

naalien tiivistamistakoskevissa tutkimuksissa ilmoitetuttulokset.

2 Tutkimusongelma . . . 2

3 Tiedontiivistaminen . . . 9

3.1 Aakkostot, merkit ja merkkijonot . . . 10

3.2 Informaatioteoriaa . . . 11

3.3 Universaalikoodaus . . . 17

3.4 Juoksunpituuden koodaus . . . 22

3.5 Shannon-Fano-koodaus . . . 22

3.6 Human-koodaus . . . 23

3.7 LZSS-koodaus . . . 25

3.8 Ziv-Lempel-koodaus . . . 27

3.9 Aritmeettinen koodaus . . . 30

4 Signaalien tiivistaminen . . . 36

4.1 Signaalinkasittelynteoriaa . . . 36

4.2 Signaalien tiivistamisesta. . . 41

4.3 HaviotonDPCM . . . 43

4.4 Kvantisointi . . . 52

4.5 Haviollinen DPCM . . . 55

4.6 Muunnoskoodaus . . . 56

5 Tuloksia . . . 70

5.1 Testien toteutuksesta . . . 70

5.2 Haviottomatmenetelmat . . . 70

5.3 Haviottomienmenetelmien yhteenveto . . . 73

5.4 Haviolliset menetelmat . . . 74

5.5 Haviollisten menetelmienyhteenveto . . . 84

6 Yhteenveto . . . 89

Viitteet . . . 90

KiitoksetJennyjaAnttiWihurinrahastolle,opettajillenijatyontarkastajille.

la.Mittauksetpyritaansailyttamaanjatkotutkimuksiavarten.Biosignaalitovatmit-

tauksia, joissa potilaasta mitataan jotain ajan myota muuttuvaa suuretta. Tunne-

tuimpia niista ovat sydansahkokayra, EKG, ja aivosahkokayra, EEG. Tyypillises-

ti biosignaalit sisaltavat muihin mittauksiin verrattuna enemman informaatiota ja

vievat tasta syysta enemman tiedonsiirto- ja tallennuskapasiteettia. Tiivistamisen

avullavoidaan informaatioesittaa pienemmassatilassa japienentaatiedonsiirto- ja

tallennusresurssien tarvetta.

Tassa tutkimuksessa tutkittiinseka haviollistenetta haviottomien tiivistamisen

menetelmien soveltuvuutta Helsingin yliopistollisen keskussairaalan otoneurologi-

sessalaboratoriossamitattuihinsilmanliikesignaaleihin.Silmanliikesignaalienavulla

tutkitaanmm.sisakorvaanliittyviatasapainosairauksia;diagnoosiatehtaessaniiden

mittaaminenpotilailtaonvakiotoimenpide.

Tiedontiivistamisenmenetelmatvoidaanjakaatiivistetystadatastarekonstruoi-

dundatanlaadunperusteellahaviottomiinjahaviollisiinmenetelmiin.Haviottomat

menetelmat sailyttavatdatan sellaisenaan ja haviolliset tuottavat jonkin approksi-

maation datasta, jossa pyritaansailyttamaan sovelluksen kannalta tarkeat ominai-

suudet.

Tutkimuksessa kasiteltiin tunnetuimmathaviottomatmenetelmat ja kehitettiin

yksi uusi parametroituihin universaalikoodeihin perustuva menetelma. Uusi me-

netelma oli suorituskyvyltaan samalla tasolla parhaiden tunnettujen menetelmien

kanssa. Aiempiin biosignaaleiden tiivistyksesta saatuihin tuloksiin verrattuna tu-

lokset olivat vertailukelpoisia ja joissain tapauksissa hieman parempiakin. Parhai-

ten toimivillamenetelmillasaatiinsignaalienvaatimatilapienennettya keskimaarin

hiemanalle puoleenalkuperaisesta.

Haviollisistamenetelmistasovellettiintunnettuja skalaarikvantisointia,dieren-

tiaalista pulssikoodimodulaatiota ja muunnoskoodausta. Parhaat tiivistystulokset

saavutettiinmuunnoskoodauksella,jonkaosanatarkasteltiinmyosaallokkeita.Muun-

noksentiivistamisenmenetelmistatestattiinkynnystamistajakehitettiinuusikvan-

tisointimenetelma muunnoksen koodaamiseen. Uudella menetelmalla saavutettiin

selvastiparempia tuloksia kuin kynnystamisella.

pauksessa tunnetuimmat ovat sydansahkokayra, EKG, ja aivosahkokayra, EEG.

Biosignaalientiivistamistaontutkittupaljon,muttatutkimusonkeskittynytlahinna

EKG-signaalientiivistamiseen.Sentyypillisimmatsovellukset ovatsignaalienarkis-

tointi jatkotutkimusta varten ja tiedonsiirtokustannusten vahentaminen. Joissakin

tapauksissamittaustenarkistointisaattaaollamyoslainvaatimaa.Jaladeddineetal.

[18]esittavatyhteenvedonaiemmastatutkimuksestaEKG:ntapauksessajaAntoniol

ja Tonella [2]kasittelevatEEG:n tiivistamista.

Tassa tutkimuksessa kartoitettiin tiivitysmenetelmien toimivuutta uudentyyp-

pisten biosignaalien tapauksessa. Tutkimusmateriaalina oli 69 Helsingin yliopistol-

lisen keskussairaalan otoneurologisessalaboratoriossamitattuasilmanliikesignaalia.

Signaaleitaolineljaaerityyppia:22sakaadia,18sinimuotoistasignaalia,15vestibulo-

okulaaristareeksia ja 14 nystagmusta.

Signaalit mitataan kolmella tavallisella ihoelektrodillapotilaan ohimoilta ja ot-

salta. Sakaadin ja sinimuotoisensignaalin tapauksessa potilasta pyydetaan seuraa-

maan seinalle ilmestyvaa laservalotaplaa katseellaan. Sakaadin tapauksessa tapla

hyppiinopeasti vaakatasossa pisteesta toiseenneljaneripisteen valilla.Sinimuotoi-

sen signaalin tapauksessa piste liikkuu sulavasti vaakatasossa. Kummassakaan ta-

pauksessapotilaaneipitaisiollamahdollistaarvatapisteenliiketta,koskasakaadissa

valotaplanliikkumisenajatjakohteetonsatunnaistettujasinimuotoiseensignaaliin

on sekoitettu kaksi eri taajuista siniaaltoa. Vestibulo-okulaarisen reeksin mittaa-

miseksi potilasta pyydetaan pitamaan katseensa yhdessa paikassa ja kaantamaan

paataansivulta toiselle kuullessaan piippauksen. Nystagmus saadaanaikaan laitta-

malla kylmaatai kuumaailmaa potilaantoiseen korvakaytavaan. [19]

Esimerkkejasignaaleistaonkuvissa2.1-2.4.Jokaisessakuvassaonkymmenense-

kunninmittaisiapatkiamittauksista;testiaineistossamittaustenpituusoli20,60tai

80 sekuntia. Kuvissa signaalin liike ylospain vastaa silmien liiketta oikealle ja liike

alaspainsilmienliikettavasemmalle;vaaka-akselionaikajapystyakselikatseenkul-

ma vaakasuunnassa. Kuvassa 2.1on sakaadimittauksia; kuvan alin signaali on tut-

kimuksen kohinaisin.Kuvassa 2.2 on sinimuotoisiasignaaleja, joissa on vainvahan

kohinaa. Kuvassa 2.3 on vestibulo-okulaarisen reeksisignaalin mittauksia. Mitat-

taessapotilassaattaarapyttaasilmiaan,jokaaiheuttaa hairioita;kuvan2.3toisessa

signaalissaon kaynyt juuri nain. Piikitmittauksessa ovatsilmanrapytyksia; potilas

signaalitovatnystagmusmittauksia.

Silmanliikesignaaleitakaytetaanapuna tasapainosairauksien diagnoosissa. Tun-

netuinnaistaonluultavastiMenierentauti.Diagnoosiavartensignaaleistamitataan

mm. silmanliikkeidennopeutta ja tarkkuutta. [19]

Signaalitonnaytteistetty400 Hz:nnaytteenottotaajuudellajanaytteenottoreso-

luutionaonkaytetty13bittia.Arvioitusignaali-kohina-suhdeonnoin32dB.Hairiota

mittauksiin aiheuttavatpaaasiassa kasvojen lihasten sahkoinen toiminta ja verkko-

virta. Verkkovirran aiheuttama hairio nakyy mitatun signaalin spektrissa 50 Hz:n

ja sen kanssa harmonisessa suhteessa olevien taajuuksien kohdalla. Sita ei voida

suodattaa pois, koska osa tarvittavasta informaatiosta on samalla kaistalla. Osa

korkeammantaajuudenkohinastasuodatetaan yleensa poisennen analyysia.Tassa

tutkimuksessa tutkittiinsekasuodatettujaettasuodattamattomiasignaaleita. Suo-

datukseen kaytettiin muotoa

y(n)=Med (

1

N N

X

i=1

x(n i);x(n);

1

N N

X

i=1

x(n+i) )

(2.1)

olevaahybridimediaanisuodatinta,jonkaonosoitettusailyttavansignaalinlaaketie-

teellisesti kiinnostavat parametrit hyvin [20, 21, 22]. Suodatuksen vaikutusta sig-

naaleihinon havainnollistettukuvassa 2.5.

-4000 -3000 -2000 -1000 0 1000 2000 3000 4000

0 500 1000 1500 2000 2500 3000 3500 4000 Anvasa1d.dat

-4000 -3000 -2000 -1000 0 1000 2000 3000 4000

0 500 1000 1500 2000 2500 3000 3500 4000 Havasa01.dat

-4000 -3000 -2000 -1000 0 1000 2000 3000 4000

0 500 1000 1500 2000 2500 3000 3500 4000 Kovasa1d.dat

-4000 -3000 -2000 -1000 0 1000 2000 3000 4000

0 500 1000 1500 2000 2500 3000 3500 4000 Pgvasa02.dat

Kuva 2.1: Sakaadeja.

-4000 -3000 -2000 -1000 0 1000 2000 3000 4000

0 500 1000 1500 2000 2500 3000 3500 4000 Ausini01.dat

-4000 -3000 -2000 -1000 0 1000 2000 3000 4000

0 500 1000 1500 2000 2500 3000 3500 4000 Hasi3d.dat

-4000 -3000 -2000 -1000 0 1000 2000 3000 4000

0 500 1000 1500 2000 2500 3000 3500 4000 Hisi1d.dat

-4000 -3000 -2000 -1000 0 1000 2000 3000 4000

0 500 1000 1500 2000 2500 3000 3500 4000 Risi5d.dat

Kuva2.2: Sinimuotoisiasignaaleja.

-4000 -3000 -2000 -1000 0 1000 2000 3000 4000

0 500 1000 1500 2000 2500 3000 3500 4000 Abhe1d.dat

-4000 -3000 -2000 -1000 0 1000 2000 3000 4000

0 500 1000 1500 2000 2500 3000 3500 4000 Elhe1d.dat

-4000 -3000 -2000 -1000 0 1000 2000 3000 4000

0 500 1000 1500 2000 2500 3000 3500 4000 Hvhe1d.dat

-4000 -3000 -2000 -1000 0 1000 2000 3000 4000

0 500 1000 1500 2000 2500 3000 3500 4000 Lshe1d.dat

Kuva2.3: Vestibulo-okulaarisiareekseja.

-4000 -3000 -2000 -1000 0 1000 2000 3000 4000

0 500 1000 1500 2000 2500 3000 3500 4000 Gsny1d.dat

-4000 -3000 -2000 -1000 0 1000 2000 3000 4000

0 500 1000 1500 2000 2500 3000 3500 4000 Hany4d.dat

-4000 -3000 -2000 -1000 0 1000 2000 3000 4000

0 500 1000 1500 2000 2500 3000 3500 4000 Hkny1d.dat

-4000 -3000 -2000 -1000 0 1000 2000 3000 4000

0 500 1000 1500 2000 2500 3000 3500 4000 Mtny1d.dat

Kuva2.4: Nystagmuksia.

-4000 -3000 -2000 -1000 0 1000 2000 3000 4000

0 500 1000 1500 2000 2500 3000 3500 4000 Pgvasa02.dat

-4000 -3000 -2000 -1000 0 1000 2000 3000 4000

0 500 1000 1500 2000 2500 3000 3500 4000 Pgvasa02.dat.f

Kuva2.5: Alkuperainen signaali ja signaalihybridimediaanisuodatuksen jalkeen.

ton merkeista,mahdollisimmantiiviissamuodossa. DataD koodataanpienempaan

muotoon(D),jokaonpystyttavapurkamaantakaisinalkuperaiseksidataksi Dtai

joksikin riittavanhyvaksiapproksimaatioksisiita.Tarkeimmattiedon tiivistamisen

edut ovat tiedontallennuskapasiteetin tarpeen pieneneminen ja tiedonsiirtokapasi-

teetin pienentynyt kulutus. [34]

Maaritelma 3.0.1 Tiivistyssuhde (compression ratio) CR mittaa tiivistyksen te-

hokkuutta. Se maaritellaankaavalla

CR= S

D

S

(D)

; (3.1)

missaS

D

ondatankokojollakinyksikollamitattunajaS

(D)

tiivistetyndatankoko

samalla yksikollamitattuna.

Kaikkeatietoa ei voida tiivistaa, mutta lahes kaikessa datassa onredundanssia,

jotatiivistysalgoritmitvoivathyodyntaatiivistamisessa.Algoritmintehokkuus riip-

puupaljondatanluonteesta.Ontodennakoista,ettajollekindatallespesialgoritmi

tuottaa paremman tuloksen kuin geneerinen algoritmi. Teoreettisen pohjan tiedon

tiivistamiselle antaa Shannonin informaatioteoria [33], jonka menetelmillavoidaan

tutkia, kuinka paljontietoa voidaan teoriassatiivistaa.

Tiedontiivistysalgoritmitvoidaan jakaakahteenluokkaan puretun datanlaadun

perusteella. Haviottomilla (lossless, noiseless) algoritmeillapurettu data on ident-

tinen alkuperaisen datan kanssa; haviollisilla (lossy) algoritmeilladekoodattu data

on jokin approksimaatio alkuperaisesta datasta.

1

Toinen mahdollinen algoritmien

jako on niiden toiminnan perusteella: staattiset algoritmit toimivat aina samoin ja

dynaamiset mukautuvat datan paikallisiinvaihteluihin.

Haviottomia tiivistysmenetelmia kutsutaan yleisnimikkeella entropian koodaus.

Entropian koodauksessa ontavoitteena vahentaa lahetettyjen merkkien maaraa si-

ten, etta alkuperainen data pysyy muuttumattomana. Alkuperaisen datan sailymi-

nen sellaisenaanonperusedellytysmonillesovelluksille;esimerkiksiohjelmientiivis-

tyksessayhdenkinbitinvirhevoijohtaasiihen,ettaohjelmastatuleekayttokelvoton.

Entropian koodaajia kaytetaan myos haviollisten menetelmien osana. Haviollisten

1

menetelmien tavoitteena on karsia sovelluksen kannalta merkityksetonta informaa-

tiota.

Entropian koodauksen menetelmista tunnetuimpia ovat kokonaislukujen erilai-

siin esityksiin perustuvat universaalikoodit [7, 38], sanakirjamenetelmat LZ77 [44]

ja LZW [41], optimaalisen etuliitekoodin tuottava Human-koodaus ja viime ai-

koina paljon huomiota saanut informaatioteoreettisesti optimaalinen aritmeettinen

koodaus [10, 16,27, 31, 43]. Osa koodaajista ottaa huomioonmerkkien keskinaisen

jarjestyksen saannonmukaisuudet ja yrittaamallintaa lahdettakoodauksen aikana.

Yleensaalgoritmeistatarkastellaantiivistyssuhteenlisaksiniidentuottamankoo-

din virheensietokykyaja viivetta,ts.tarvitseekoalgoritmiuseampia syotteenmerk-

keja koodin muodostamiseksi vai voiko se lahettaa koodisanan heti, kun syotteen

merkki tulee koodattavaksi. Algoritmin tehokkuus on myos tarkeaa, varsinkin jos

sovellus on reaaliaikainen(esim. musiikintiivistaminen).

Tassaluvussakasitellaanperinteistatiedontiivistamisenteoriaajayleisiahaviot-

tomia algoritmeja.

3.1 Aakkostot, merkit ja merkkijonot

Tiivistysalgoritmikuvaasanomanlahdeaakkostoltakohdeaakkostolle.Jottasanoma

voitaisiin rekonstruoida tiivistetysta tiedosta, on kuvauksen oltava injektio, ts. jo-

kainen merkkijono kuvautuuvainyhdelle kohdeaakkoston merkkijonolleja mitkaan

kaksi erilahdeaakkostonmerkkijonoa eivatkuvaudu samallekohdeaakkostonmerk-

kijonolle.[34]

Maaritelma 3.1.1 Aakkosto (alphabet) on



aarellinen joukko fa

0

;a

1

;:::;a

N g,

joka sisaltaa ainakin yhden alkion. Aakkoston alkioitaa

i

kutsutaanmerkeiksi.

Tyypillinentiedontiivistyksessakaytettyaakkostoonbinaarinenaakkostof0;1g.

Maaritelma 3.1.2 Merkkijono (string) ! yli aakkoston on jono aakkoston

merkkeja.

!=a

1 a

2 :::a

m

; a

i

2; i=1;:::;m: (3.2)

Merkkijonon ! pituutta merkitaan j!j =m. Merkkijonojen x= x

i

; i=1;:::;m ja

y=y

j

; j =1;:::;n katenointiamerkitaan:

xy=x :::x y :::y : (3.3)

Katenoidunmerkkijononpituusonjxyj=jxj+jyj.Lisaksimaaritellaantyhjamerk-

kijono,jossaeioleyhtaanmerkkia.Kaikkienaakkostonmerkkijonojen joukkoa,

mukaanlukien , merkitaan

.

Sanoma on



aarellinen merkkijono yli lahdeaakkoston. Merkkijonoja vertaillaan

toisiinsa etu- ja loppuliitteidenavulla.

Maaritelma 3.1.3 Merkkijono ! on merkkijonon x etuliite (prex) ! @ x, jos

x=!y,jollekin y2

:

Maaritelma 3.1.4 Merkkijono ! on merkkijonon x loppuliite (suÆx) ! A x, jos

x=y!,jollekin y2

:

3.2 Informaatioteoriaa

Claude.E.Shannoninalunperinvuonna1948julkaisemastakommunikaatiotakoske-

vasta teoriasta[33] on muodostunut tiedontiivistyksenteoreettinen perusta. Teok-

sessaan han kasitteli yleista kommunikaatiojarjestelmaa (kuva 3.1), joka koostuu

viidesta osasta:

Informaation lahde, joka tuottaa sanoman taisanomia, jotka valitetaan koh-

teelle.

Lahetin, joka muuttaa sanomansignaaliksi,jokavoidaan lahettaakanavalla.

Kanava, jota pitkin signaali valittyy lahettimesta vastaanottimeen. Kanava

voiollakohinainen.

Vastaanotin, joka tekee lahettimeen nahden kaanteisen operaation, eli

konstruoisanomansignaalista.

Kohde, jolle sanomaon tarkoitettu.

Sanomavalitaanmahdollistensanomien joukosta. Niilla voi ollamerkitys;sanomat

voivatviitatamaailmanolioihintaikasitteisiin.Shannoninteoriaeikuitenkaankoske

kommunikaation semanttista puolta.

Kommunikaationongelmana on rekonstruoida jossain paikassa sanoma,jokaon

valittu muualla. Sanoma olisi pystyttava lahettamaan mahdollisimman taloudelli-

Lähde Vastaanotin Kohde

Kohinalähde

Lähetin Kanava

Kuva 3.1: Yleinen kommunikaatiojarjestelma.

Informaation lahde tuottaasanomanmerkki merkilta.Merkit voidaan valitaeri

todennakoisyyksilla ja merkin valintavoi riippua edellisistamerkeista.Yleensapu-

hutaan lahteen tuottamista tapahtumista.

Jos aiemmilla tapahtumilla ei ole vaikutusta seuraavaan tapahtumaan puhu-

taan 0. asteen lahteesta. Tallaisella lahteella jokaisen tapahtuman todennakoisyys

onainasamaelitapahtumatovatkeskenaantilastollisestiriippumattomia.Tallaisen

lahteen kuvaamiseen riittaa sen todennakoisyysjakauma. Tilastollisesti riippumat-

tomallelahteelle on yhdistetylle tapahtumalle voimassa

p(i;j)=p(i)p(j): (3.4)

Kun tapahtumat ovat toisistaantilastollisestiriippuvia kaytetaan usein lahteen

mallina Markovin prosessia [33]. Markovin prosessilla on



aarellinen joukko tiloja,

joista voidaan siirtya toisiin tiloihin eri todennakoisyyksilla; jokainen tilasiirtyma

tuottaa tapahtuman. Esimerkiksi ensimmaisen asteen Markovin prosessilla tapah-

tuman todennakoisyys riippuuvainedellisesta tapahtumasta. Talloinonvoimassa

p(i;j)=p(jji)p(i): (3.5)

Kyseisessa mallissa tapahtumaketjun x

1

;x

2

;x

3

;x

4

todennakoisyys voidaan laskea

seuraavasti:

p(x

1

;x

2

;x

3

;x

4

)=p(x

2

;x

3

;x

4 jx

1 )p(x

1

) (3.6)

=p(x

3

;x

4 jx

2 )p(x

2 jx

1 )p(x

1

) (3.7)

=p(x

4 jx

3 )p(x

3 jx

2 )p(x

2 jx

1 )p(x

1

): (3.8)

0.5 0.5

0.3 0.2 C

B

A 0.5

0.2 0.4

0.6 C

0.5 A

0.3 B C

C

B

B

Kuva 3.2: Markovin prosesseja.

Y

p(YjX) A B C

A 0 0.4 0.6

X B 0.5 0.3 0.2

C 0 0.5 0.5

Taulukko 3.1: Kuvan 3.2oikeanpuoleisen graanmatriisi.

Esimerkki 3.2.1 Markovinprosessejahavainnollistetaanuseingraaenavulla.Ku-

vassa 3.2 on kuvattu kaksi erilaista Markovin prosessia. Vasemmalla oleva graa

kuvaa 0. asteen ja oikealla oleva 1. asteen Markovin prosessia. Vasen graa vas-

taa lahdetta, jonka tapahtumien todennakoisyydet ovat p(X = A) = 0:5, p(X =

B) = 0:2 ja p(X = C) = 0:3. Oikeanpuoleinen graa voidaan kuvata ehdollisten

todennakoisyyksien taulukkona (taulukko 3.1).

Sanomansisaltamainformaatioriippuusentodennakoisyydestamahdollistensa-

nomienjoukossa. Sanomista kaytetaanmyosnimitystatapahtuma.

Maaritelma 3.2.1 JosX ontapahtuma, jonkamahdollisetvaihtoehdotovatfx

i g,

niintapahtumanX =x

i

informaatio I on

I(X =x

i

)= log

k

p(X =x

i

); (3.9)

missak voidaan valita halutunyksikon mukaan. Kun k =2 informaationmittayk-

jolloinpuhutaan luonnollisista yksikoista (naturalunits tai \nats").[33]

Esimerkiksi yksi desimaaliluku, joka voi saada kymmenen eri arvoa ja jokaisen

samalla todennakoisyydella, sisaltaanoin 3.32 bittiainformaatiota. [33]

Oletetaan, etta tiedetaan vaintapahtumientodennakoisyydet p

i

. Entropia mit-

taa tallaiseen tilanteeseen liittyvaa epavarmuutta tai valintaa. Entropian mitan

H(p

1

;p

2

;:::;p

n

) ontaytettava seuraavatvaatimukset:

1. H onjatkuva.

2. Joskaikki p

i

ovatyhtasuuria,p

i

=1=n,onH monotonisestikasvavan:n funk-

tio.

3. Josvalintajaetaanosiin,niinyhdistettyentropiaonosienentropianpainotettu

summa.

Jaetaan tapahtumat p

i

= f1=2;1=3;1=6g kahteen osaan f1=2g ja f1=3;1=6g.

Talloin

H

1

2

; 1

3

; 1

6

=H

1

2

; 1

2

+ 1

2

H(1)+ 1

2 H

2

3

; 1

3

: (3.10)

Shannonin [33] mukaan ainoa ehdot toteuttava funktioon muotoa

H = K

n

X

i=1 p

i logp

i

; (3.11)

missa K on positiivinen vakio, joka valitaan tassa ykkoseksi. Entropia H on nolla,

jos ja vain jos yhden tapahtuman todennakoisyys on yksi (muiden todennakoisyys

on talloin nolla). Intuitiivisesti tama on selvaa, koska varma lopputulos ei sisalla

epavarmuutta. Jos tapahtumia on n kappaletta, niin maksimissaan entropia on

logn, kun kaikkien tapahtumien todennakoisyydet ovat yhta suuria. Talloin tilan-

teeseen liittyy eniten epavarmuutta. Jokainen muutos, joka tasoittaa lahteen to-

dennakoisyysjakaumaa lisaaentropiaa.

Maaritelma 3.2.2 JosX ontapahtuma, jonkavaihtoehdotovatfx

i

g,ja tapahtu-

mat eivat riipuedellisista tapahtumista,niin X:nentropia on

H(X)= X

p(X =x

i

)logp(X =x

i

); (3.12)

missalogaritminkantaluku valitaanmittayksikon mukaan. [33]

Maaritelma 3.2.3 Olkoot X ja Y tapahtumia, joista X:n vaihtoehdot ovat fx

i g

ja Y:n vaihtoehdot fy

j

g. Yhdistetyn tapahtuman X;Y entropiaon talloin

H(X;Y)= X

i;j

p(X =x

i

;Y =y

j

)logp(X =x

i

;Y =y

j

): (3.13)

TapahtumienX ja Y entropia saadaan

H(X)= X

i;j

p(X =x

i

;Y =y

j )log

X

j

p(X =x

i

;Y =y

j

); (3.14)

H(Y)= X

i;j

p(X =x

i

;Y =y

j )log

X

i

p(X =x

i

;Y =y

j

): (3.15)

Voidaanosoittaa, etta

H(X;Y)H(X)+H(Y): (3.16)

Yhtasuuruus onvoimassavainsilloin,kuntapahtumatX jaY ovatriippumattomia

elip(X =x

i

;Y =y

j

)=p(X =x

i

)p(Y =y

j ).[33]

Maaritelma 3.2.4 Joskaksitapahtumaaeivatoleriippumattomia,jollointodenna-

koisyys Y:n arvolley

j

, jos X:n arvo tiedetaan x

i

:ksi,on

p(Y =y

j

jX =x

i )=

p(X =x

i

;Y =y

j )

P

j

p(X =x

i

;Y =y

j )

: (3.17)

TapahtumanY ehdollinen entropia, jos X tunnetaan, H(YjX) maaritellaanpaino-

tettunakeskiarvonaY:nentropioistakaikillaeriX:narvoilla.Painotuksenakaytetaan

yhdistetyn tapahtumanX =x

i

;Y =y

j

todennakoisyyttaeli

H(YjX)= X

i;j

p(X =x

i

;Y =y

j

)logp(Y =y

j

jX =x

i

)=H(X;Y) H(X):

(3.18)

Ehdolliselleentropiallevoidaan osoittaa,etta onaina voimassa

H(Y)H(YjX): (3.19)

Markovin prosessin entropia voidaan laskeakaavasta

H = X

i P

i H

i

= X

i;j P

i

p(Y =y

j jS =s

i

)logp(Y =y

j jS =s

i

); (3.20)

missa P

i

on tilan S = s

i

todennakoisyys, H

i

tilan S = s

i

entropia ja Y on tapah-

tuma, jonka mahdollisuudetovat kaikki tilasiirtymattilasta s

i

. Markovin prosessin

entropia saadaan siis laskemalla painotettu keskiarvo tilojen entropiasta kayttaen

painotuksena tilan todennakoisyytta.[33]

Datakoostuu informaatiostaja redundanssista.Redundanssionnimensamukai-

sesti toistoa, joka voidaan eliminoida datasta ja myohemmin lisata takaisin datan

muuttumatta.Informaatiotaeivoidapoistaadatastamuuttamattasita.Haviottomat

tiivistysmenetelmatovat redundanssia vahentavia; ne eivat siis vahenna informaa-

tiota.Haviolliset menetelmatvahentavatsekaredundanssiaettainformaatiota.[25]

Maaritelma 3.2.5 Lahteen, joka voituottaa n tapahtumaa, redundanssi R on

R=logn H; (3.21)

missa H onlahteen entropia. [33]

Redundanssi on siis maksimientropian ja todellisen entropian erotus. Lahteella ei

oleredundanssia kun entropia on maksimissaan eliH =logn.

Maaritelma 3.2.6 Lahteensuhteellinenredundanssi Z onlahteenredundanssin ja

maksimientropian suhde:

Z = R

logn

=1 H

logn

: (3.22)

Lynchin [25] mukaan entropian avulla saadaantiivistyssuhteen CR ylarajaksi

CR

max

= logn

H

: (3.23)

Erilaisia lahteenmalleja,yleensatilastollisestiriippumaton 0.asteenlahdettaja

1. asteenMarkovin prosessia, kaytetaantiivistysmenetelmien testaamiseen.[25]

Maksimaalisen haviottoman tiivistyksen saavuttamiseksi voidaan lahteen kayt-

taytyminenmuuttaaMarkovinprosessi-mallistatilastollisestiriippumattomaksimal-

timaalisellakoodauksellakoodisanojenkeskipituus` onsama kuinlahteen entropia

H. [25]

Informaatioteorian mukaan entropia on siis maaritelty suhteessa tilastolliseen

malliin. Usein lahteen todellista mallia ei tunneta, joten se joudutaan jollain me-

netelmalla konstruoimaan empiirisesta aineistosta. Mita parempi lahteen mallion,

sita pienempi onlahteen entropia suhteessa malliin;toisaalta monimutkainen malli

vie enemmantilaatiedostosta.

3.3 Universaalikoodaus

Universaalikoodauksessa ei tarvitse tuntea lahteen jakaumaa, vaan riittaaetta voi-

daanjarjestaatapahtumattodennakoisyyksienmukaanlaskevaanjarjestykseen.Koo-

dauksessa tapahtuman jarjestysnumero koodataan jollain yksinkertaisella koodilla.

Universaalikoodauksen tuottamien koodisanojenkeskipituudelle ` on voimassa

`c

1 H+c

2

; (3.24)

missaH onlahteenentropiajac

1 jac

2

ovatvakioita.Koodiasanotaanasymptootti-

sestioptimaaliseksi,josc

1

=1.Silloinkoodisanojenkeskipituus`lahestyyentropiaa

entropian kasvaessa. Tassa esitetyt koodit ovat staattisia ja yksiselitteisesti puret-

tavia. Staattisuudella tarkoitetaan sita, etta samalle merkille tuotetaan aina sama

esitys.Monienkoodienyksikasitteisyysperustuu siihen,ettakoodisananpituussaa-

daanjotenkinselvillesiitaitsestaan.Esimerkiksi koodinalussavoiollasarjaykkosia

janiidenjalkeennolla;tamanperusteella voidaanpaatellakoodinloppuosanpituus.

[7]

Koodien toteutus on laskennallisesti tehokasta ja varsinkin parametroituja uni-

versaalejakoodejasoveltamallasaadaanhyviatiivistystuloksia.Esimerkiksi Howar-

din jaVitterin progressiivisessaFELICS-kuvantiivistysalgoritmissa[17] onkaytetty

Golomb-,Rice- jaSubexponential-koodeja,joilleyritetaanennustaaparas paramet-

rinarvo.

3.3.1 -koodi

Elias [7] esittaa koodeja, jotka sopivat epatasaisesti jakautuneille kokonaisluvuille.

siten, etta 0 ontodennakoisin. Luvun xkoodi(x) muodostetaan seuraavasti:

(x)= n

z }| {

1:::10 x

0

z }| {

x

n 1 :::x

1

; (3.25)

missa n =0, kun x=0, ja n =b log

2

xc+1, kun x>0, ja x 0

luvun x binaariesitys

ilman ylinta 1-bittia. Saatu koodi on lyhyempi pienille kokonaisluvuille ja pidempi

suurille. Taulukossa 3.2 on esitetty -koodit luvuille 0:::14; pisteella osoitetaan

koodin loogistenosien valit.

x (x) x (x) x (x)

0 0 5 111.0.01 10 1111.0.010

1 1.0 6 111.0.10 11 1111.0.011

2 11.0.0 7 111.0.11 12 1111.0.100

3 11.0.1 8 1111.0.000 13 1111.0.101

4 111.0.00 9 1111.0.001 14 1111.0.110

Taulukko3.2: Lukujen 0:::14-koodit.

3.3.2 Æ-koodi

ToinenEliasinkoodi,Æ,onasymptoottisestioptimaalinen;semuodostetaankoodaa-

mallaensin luvunbinaariesityksenpituus-koodillajasen jalkeenluvun binaariesi-

tys ilman ylinta 1-bittia:

Æ(x)= ( blog

2 (x)c +1)

z }| {

n :::

1 x

0

z }| {

x

k :::x

1

; (3.26)

missa x 0

onluvun xbinaariesitys ilman ylinta 1-bittia.[7]

3.3.3 Golomb-koodi

Golomb-koodionsaanutnimensakehittajaltaanS.W.Golombilta.HowardinjaVit-

terin [17] mukaan se toimiihyvin eksponentiaalisille jakaumille;lisaksisitavoidaan

saataaparametrinavullasopiviksierilaisillejakaumille.Golomb-koodiGol(x;k)pa-

rametrillak luvulle x muodostetaan seuraavasti:

Gol(x;k)= n

z }| {

1:::10 y

z }| {

y :::y ; (3.27)

missa n = bx=kc ja y on luvun x mod k esitys tavalla, jossa saastetaan bitteja,

kun se on mahdollista. Koska x:n jakojaannos k:n suhteen on aina k:ta pienempi,

voidaan useimmissa tapauksissa kayttaa lukujen 0;:::;k 1 esittamiseen vaihtele-

vanmittaista koodia, jolla koodisanojen keskipituus on pienempi kuin pienimmalla

kiinteallabittien maarallasaavutettava dlog

2 ke.

3.3.4 Rice-koodi

Howardin ja Vitterin [17] mukaan R.F. Ricen kehittama Rice-koodi toimii myos

hyvin eksponentiaalisesti jakautuneille luvuille. Sen etuna -koodiin on se, ettei

koodin pituus kasva yhta nopeasti. Rice-koodi on parametroitu, joten se voidaan

sovittaalahteen jakaumallesopivaksi.ItseasiassaRice-koodionGolomb-koodineri-

koistapaus, jossaGolomb-koodinparametrionrajattukahdenpotenssiksi.Luvun x

Rice-koodiR ice(x;k)parametrilla k (k 0)saadaan seuraavasti:

R ice(x;k)= m

z }| {

1:::10 y

z }| {

y

k :::y

1

; (3.28)

missa m = bx=2 k

c ja y on luvun x mod2 k

binaariesitys k bitilla. Rice-koodi on

Golomb-koodia yksinkertaisempi siina, etta etuosan 1-bittien jalkeen on aina va-

kiomaara bitteja; toisaalta Golomb-koodissa on tiheampi parametrointi, joten sita

voidaansaataatarkemmin.Taulukossa3.3onesitettynaRice-koodejaeriparametrin

arvoilla.

x R ice(x;0) R ice(x;1) R ice(x;2) R ice(x;3)

0 0 0.0 0.00 0.000

1 1.0 0.1 0.01 0.001

2 11.0 1.0.0 0.10 0.010

3 111.0 1.0.1 0.11 0.011

4 1111.0 11.0.0 1.0.00 0.100

5 11111.0 11.0.1 1.0.01 0.101

6 111111.0 111.0.0 1.0.10 0.110

7 1111111.0 111.0.1 1.0.11 0.111

8 11111111.0 1111.0.0 11.0.00 1.0.000

Taulukko3.3: Rice-koodeja luvuille0:::8.

3.3.5 Eksponentiaalinen Golomb-koodi

Jukka TeuholankehittamaeksponentiaalinenGolomb-kooditoimiihyvin eksponen-

tiaalisillajakaumilla.EksponentiaalinenGolomb-koodimuistuttaalaheisestiGolomb-

koodia; siina on vain kaytetty eksponentiaalisesti kasvavia jakajia. Koodi

exp-Gol(x;k)parametrilla k muodostetaan seuraavasti:

exp-Gol(x;k)= m

z }| {

1:::10 x

0

z }| {

y

m 1 :::y

1

; (3.29)

missa m = blog

2

xc k, jos blog

2

xc k tai 0,jos blog

2

xc < k ja x 0

on luvun x

binaariesityksen k+m+1 alinta bittia. Eksponentiaalinen Golomb-koodi on kes-

kimaaraisessatapauksessa hieman huonompikuin Golomb-koodi,mutta jos koodin

parametria ennustetaan, niinennustuksessa tehty virhe ei aiheuta suurta tappiota

tiivistyksessa. Eksponentiaalisia Golomb-koodejaonesitetty taulukossa 3.4. [38]

AlunperinGolomb-jaeksponentiaalinenGolomb-koodikehitettiinbittivektorien

juoksunpituuden tiivistykseen; koodillailmoitetaan, montako perakkaista nollaatai

ykkosta onsyotteessa. Bittivektorientiivistyksellaonmoniakaytannonsovelluksia,

kuten mustavalkokuvien tiivistaminen.

x exp-Gol(x;0) exp-Gol(x;1) exp-Gol(x;2) exp-Gol(x;3)

0 0 0.0 0.00 0.000

1 1.0.0 0.1 0.01 0.001

2 1.0.1 1.0.00 0.10 0.010

3 11.0.00 1.0.01 0.11 0.011

4 11.0.01 1.0.10 1.0.000 0.100

5 11.0.10 1.0.11 1.0.001 0.101

6 11.0.11 11.0.000 1.0.010 0.110

7 111.0.000 11.0.001 1.0.011 0.111

8 111.0.001 11.0.010 1.0.100 1.0.0000

Taulukko 3.4: Eksponentiaalisia Golomb-koodejaluvuille0:::8.

3.3.6 Etumerkillisetluvut

Edellakasitellytkoodittoimivatvainpositiivisillekokonaisluvuille.Useinjoudutaan

koodaamaan myosnegatiivisialukuja.Etumerkillistenlukujenkasittelyynonuseita

Yksinkertaisin tapa on lisata koodin peraan yksi bitti ilmoittamaan luvun etu-

merkki; talloin saadaan yhta pitkat koodit luvuille x ja x. Jos luku on nolla, ei

merkkibittia lisata.Tallamenettelyllanollan koodi onlyhyempi kuin muiden.

Negatiiviset luvutvoidaanlimittaapositiivisten sekaan. Koodataan2x 1,kun

x > 0, ja 2x, kun x 0, eli positiiviset luvut esitetaan parittomilla luvuilla ja

negatiiviset parillisilla, nain saadaan positiivisille luvuille lyhyempi koodi kuin ne-

gatiivisille.Samavoidaantehdamyostoisinpain,jolloinnegatiivistenlukujenkoodit

ovathieman lyhyempia kuinpositiivisten.

Muita menetelmia on kirjallisuudessa kasitelty tarkemmin erityisesti haviotto-

mankuvantiivistyksenyhteydessa,jossamerkinkasittelyneritavatonotettumukaan

koodin mukautumisstrategioihin.

3.3.7 Mukautuvat universaalitkoodit

Kehitin yksinkertaisen menetelman, jolla voidaan tehostaa tiivistysta, jos lahteen

merkkien jakaumassa on paikallisia eroja. Menetelman ideana on jakaa syote loh-

koihin ja koodata kukin lohko optimaalisella koodilla.Kaytossa on aina yksi para-

metroitukoodi.

Algoritmissa1esitettymenetelmaonhelppototeuttaa.Optimaalisenparametrin

etsimista voidaan tehostaa huomaamalla, etta puskurin koodatun esityksen pituus

laskee monotonisesti kohti minimia, kun kaytetaan esimerkiksi eksponentiaalinen

Golomb- tai Rice-koodia. Talloin voidaan aloittaa minimipituuden etsinta edelli-

sesta optimaalisesta parametrista ja edeta aina suuntaan, jossa puskurin koodatun

esityksen pituus on pienempi. Vaikka kokonaisuutena menetelma on melko yksin-

kertainen, en loytanyt siitamainintaa kirjallisuudesta.

Algoritmi 1 Mukautuva universaalikoodaus

1: while syotetta jaljellado

2: Lue puskuri tayteen syotetta. Jossyote loppuu kesken, voidaan tayttaa pus-

kuri vain osittain.

3: for all jarkevat koodin pituudet k do

4: Laskepuskurinkoodiesityksenpituus,kunsekoodataankayttaen paramet-

riak.

5: end for

6: Valitse k

opt

, jolla puskurinkoodattu esityksenpituus onlyhin.

7: Koodaa tieto parametristaja puskurin sisalto kayttaen parametria k

opt .

8: endwhile

3.4 Juoksunpituuden koodaus

Juoksunpituudenkoodaus (run-lengthcoding,RLE)perustuuuseintoistuvienmerk-

kien perakkaisten juoksujen pituuksien laskentaan ja juoksujen korvaamiseen nii-

den pituudella. Juoksujen pituudet koodataan sopivalla koodilla (esimerkiksi joku

universaalikoodi tai Human-koodi). RLE-koodaus on ollut kaytossa mm. LBM-

kuvaformaatissa ja faxeissa, joissa yhden varin muodostamat tasaiset alueet tiivis-

tyvat hyvin RLE:lla. Sellaisenaan RLE:n kaytto ei ole kovin yleista, mutta sita

voidaanmonissa tapauksissa soveltaa osana tiivistysjarjestelmaa.

Esimerkki 3.4.1 Merkkijono aaabccbbba voidaan koodata muodossa (3,a), (1,b),

(2,c), (3,b),(1,a).

3.5 Shannon-Fano-koodaus

Kun lahteen jakauma tunnetaan tarkoin, voidaan lahteelle kehittaa universaalikoo-

dejatehokkaampiakoodeja.Ongelmanaonsiisloytaasellainenkoodisanojenjoukko,

jolla`onmahdollisimmanpieni,kunlahteentapahtumientodennakoisyydet tunne-

taan.ShannonjaFanojulkaisivattoisistaanriippumattaalgoritmitongelmanratkai-

semiseksi.Ratkaisueikuitenkaanoleparasmahdollinen.Algoritmitpoikkesivathie-

man toisistaan; Shannonin algoritmi perustui kumulatiivisten todennakoisyyksien

binaariesityksiin ja Fanon joukkoihin jakamiseen. Lopputuloksena saadun koodin

tehokkuus on kuitenkin molemmissa tapauksissa sama. Yksinkertaisuuden vuoksi

esitan vainFanon algoritmin(Algoritmi2), jokaratkaisee ongelman osittavallame-

netelmalla.[33]

Algoritmi 2 Fanon algoritmi,FANO(, !)

Alkuehto: on lahdeaakkosto. Merkkien todennakoisyydet tunnetaan ja en-

simmaisellakutsulla !:n arvo on.

Jattoehto: Kaikkien lahdeaakkoston merkkien a

i

koodisanat ! on maaratty.

1: if jj>1then

2: Jaa aakkosto kahteen todennakoisyyksiltaan suurinpiirtein yhta suureen

joukkoon

1 ja

2 .

3: FANO(

1 ,!0).

4: FANO(

2 ,!1).

5: else

6: Aseta merkin a2 koodisanaksi !.

7: endif

3.6 Human-koodaus

D. A. Human kehitti vuonna 1952 kokoavan menetelman, jolla voidaan muodos-

taa optimaalinenetuliitekoodi,kuntunnetaan lahteen todennakoisyysjakauma. Jos

lahteen merkkien todennakoisyydet ovat 1=2:n potensseja onHumanin algoritmin

tuottama koodioptimaalinenmyosinformaatioteoreettisessa mielessa.[11]

Teoreema 3.6.1 Optimaalisella binaarisella etuliitekoodilla on seuraavat ominai-

suudet:

1. Olkootmerkkienajabkoodisanojenpituudet `(a)ja`(b)jatodennakoisyydet

p(a)jap(b).Josp(a)>p(b),niin`(a)`(b). Todennakoisillamerkeillaonsiis

lyhyemmat koodisanatkuin epatodennakoisilla.

2. Kahdenepatodennakoisimmanmerkinkoodisanat,jotkaovatyhtapitkia,eroa-

vat toisistaanvain koodisananviimeisen merkin osalta.

Todistus: ks. [11, s.270]

Gershon ja Grayn [11] mukaan Humanin algoritmi (Algoritmi 3) tuottaa ah-

neellamenetelmallakoodipuun,jokatayttaateoreeman3.6.1mukaisetoptimaaliseen

binaarisen etuliitekoodin vaatimukset. Itseasiassa teoreema 3.6.1 antaa tarvittavat

tiedot optimaalisenkoodin konstruointiin.Humanin algoritmiyhdistaaaakkoston

kaksiepatodennakoisintamerkkiaa

1 jaa

2

uudeksimerkiksia

1;2

ja muodostaauu-

den aakkoston 0

=( fa

1

;a

2

g)[fa

1;2

g. Nain jatketaan,kunnes aakkostossa on

enaayksi merkki;koodisaadaanmerkkien yhdistamisistasiten, ettajokainen merk-

kien yhdistaminen muodostaa yhden koodipuun solmun (ks. kuva 3.3). Humanin

algoritmivoidaantoteuttaa aikavaatimuksella O(nlogn).

Algoritmin 3 muodostamaa koodipuutakaytetaankoodaukseen siten, etta koo-

disana muodostetaan reitista juuresta merkkia vastaavaan lehtisolmuun. Vasem-

man alipuun valintaa merkitaan 0-bitilla ja oikean 1-bitilla. Koodi on aina yk-

sikasitteisesti purettavissa, koska yhdellakaan solmulla, johon liittyy merkki, ei ole

alipuita. Koodi puretaan siten, etta aloitetaan juuresta, luetaan bitteja ja edetaan

koodipuussa alaspain kunnes tullaan solmuun, johon liittyy merkki. Tulostetaan

merkki ja siirrytaantakaisin juureen.

Esimerkki 3.6.1 Kuvassa 3.3 on esitetty koodin muodostaminen aakkostolle fA;

Algoritmi 3 Humanin algoritmi

Alkuehto: on lahdeaakkosto.

1: while jj>1 do

2: Etsi :n kaksi pienimman todennakoisyyden merkkia a

1 ja a

2

ja muodosta

solmu a

1;2 .

3: p(a

1;2

):=p(a

1

)+p(a

2 ):

4: left(a

1;2 ):=a

1 :

5: right(a

1;2 ):=a

2 :

6: :=( fa

1

;a

2

g)[fa

1;2 g:

7: endwhile

8: :n viimeinen merkkionkoodipuunjuuri.

0.1

A B

0.15 C 0.2

D 0.25

E 0.3

D 0.25

E 0.3 C

0.2

B 0.15 0.1

A 0.25

D 0.25

E 0.3

B 0.15 0.1

A 0.25 C

0.2 0.45

B 0.15 0.1

A 0.25 C

0.2 0.45

E 0.3 D

0.25 0.55

B 0.15 0.1

A 0.25 C

0.2 0.45

E 0.3 D

0.25 0.55 1.0

Kuva 3.3: Human-koodin muodostaminen.

0.15, 0.2, 0.25 ja 0.3. Merkin A koodisanaksi saadaan 010 ja merkin B koodisa-

naksi011. Voidaan todeta,ettaalgoritmintuottamalla koodillaonteoreeman 3.6.1

mukaiset ominaisuudet.

Human-koodaus on kaytossa monissa tunnetuissa tiivistysohjelmissa; usein se

on yhdistetty johonkin toiseen tiivistysmenetelmaan. GNU-projektin tiivistysohjel-

massa bzip2onHuman yhdistetty Burrows-Wheeler-muunnokseen [4]. Muissa yh-

teyksissaonyhdistettymyosLZ77jaHuman.Human-koodaustakaytetaannykyi-

sinkin tehokkaamman aritmeettisen koodauksen tilalla,koska siihen eiliity samoja

patenttiongelmia kuin aritmeettiseen koodaukseen. Toisaalta algoritmion huomat-

tavasti helpompi toteuttaa kuin aritmeettinenkoodaus ja sen tuottamaa staattista

koodia onhelpompi kasitella.

3.7 LZSS-koodaus

LempeljaZivovatkehittaneetuseitatiivistysalgoritmeja.Naistatunnetuimpiaovat

sanakirjamenetelmat (dictionary method) LZ77 [44] ja LZ78 [45], joista paranne-

tut versiot ovat LZSS [35] jaLZW [41]. Sanakirjamenetelmatkayttavat sanakirjaa,

josta etsitaan syotteessa esiintyvia sanoja. Syotteen sanat korvataan viittauksella

sanakirjaan. LZ77:ssa ja LZ78:ssa yksi koodaajan tulostama alkio voi siis vastata

useampaa syotteen merkkia.Molemmatmerkkijonon sovittamiseen perustuvat me-

netelmatovat varsin suosittuja ja toimivia; niiden esittelyn jalkeen merkkijononso-

vituksesta on tulluttarkea tiedontiivistyksenosa-alue.

LZ77-menetelmassa kaytetaan sanakirjana syotteesta jo nahtya ikkunaa. Ikku-

nastaetsitaanmahdollisimmanpitkaasellaistamerkkijonoa,jokaonidenttinenseu-

raavaksikoodattavansyotteenkanssa.Ikkunaliukuueteenpainkoodauksenedetessa;

LZ77-menetelmaa sanotaankin liukuvan sanakirjan menetelmaksi (sliding

dictionarymethod). Menetelmassa etsitaansellaista sovituksen paikkaa k,etta

a

p k+(0:::l )

=a

p+(0:::l )

; (3.30)

missal pyritaansaamaanmahdollisimmansuureksi, ponkoodaajannykyinenpaik-

ka jal sovituksen pituus.Yleensak rajoitetaanlaskennallisen tehokkuuden, muisti-

vaatimusten ja tiivistystehon 2

kannalta sopivalle valille.Jos riittavanpitka sovitus

loytyy, koodataanosoitin sovituksen alkuun k ja sovituksen pituus l ja edetaanso-

2

vituksen pituuden verran. Muussa tapauksessa koodataan osoitin rajatun alueen

ulkopuolelle (taijoku sovittuosoittimen arvo,esim. 0) ja seuraavasyotteen merkki

a

p+1

sellaisenaan ja siirrytaanyksi merkki eteenpain. [44]

Alkuperaisessa LZ77:ssa[44] koodattiinaina osoitinja yksi sovituksen jalkeinen

merkki;osoitinjasovituksenpituuskoodattiinlahdeaakkostonmerkeilla -kantaise-

na(radix- ) esityksena, missa on lahdeaakkoston merkkien lukumaara.Storer ja

Szymanski[35]tehostivatmenetelmaasiten,ettasovitusjayksittainenmerkkierote-

taanvaaranosoittimensijastayhdellabitilla.

3

Osoitinjapituuskirjoitetaanvain,jos

menettelylla saastetaan tilaa verrattuna merkin koodaamiseen sellaisenaan. Pienin

sovituksen pituusriippuukoodaajanparametreista.LZSSonesitetty Algorimissa4.

Esimerkki 3.7.1 Koodataan merkkijono ABCABDCAB LZSS-algoritmilla.Algo-

ritmin toimintaa on havainnollistettu taulukossa 3.5. Kohdatessaan neljannen mer-

kinkoodaajaloytaajonahdystadatastakahdenmerkinmittaisensovituksenkolmen

merkinetaisyydeltajaseitsemannenmerkinkohdallaloydetaankolmenmerkinmit-

tainen sovitusneljan merkin etaisyydelta.Koodauksentulos on ABC(-3,2)D(-4,3).

Syote Tulos

A A

B B

C C

A ( 3;2)

B

D D

C ( 4;3)

A

B

Taulukko 3.5: EsimerkkiLZSS-koodauksesta.

Purettaessa on hyodynnettava aiemminpurettua syotetta. Luetaan tiedostosta

seuraava koodi. Jos kyseessa on sovitus, luetaan sovitus jo puretusta syotteesta,

muutoin puretaan merkki, joka oli koodattu. Purkaminen onnistuu, koska kaikki

data, johon viitataan, onpurettu ennen viittausta.

Algoritmiolettaa,ettasamanmerkkijonontoistuminensyotteessalyhyellavalilla

on todennakoista. Jos nainon, voise saavuttaa suuriakin tiivistyssuhteita. LZSS:n

3

maksimitiivistysriippuukaytetyistaparametreistaelisiita,kuinkapitkasovitusvoi-

daantehda.Tallainenrajaeiolevalttamaton;voidaanhan sovituksenpituuskooda-

ta jollain universaalikoodilla.Yleensa sovituksen pituuden tallettamiseen varataan

melko pieni maara bitteja, koska on yleensa jarkevaa olettaa, etta suurin osa so-

vituksista on lyhyita. Human-koodissa koodattava merkki voidaan pienimmillaan

tallettaayhteenbittiin;periaatteessaLZSSvoipaastahuomattavastiparempaantii-

vistykseen. LZ77 ja sen variantit ovat kaytossa tunnetuissa tiivistysohjelmissa (esi-

merkiksizip).

Algoritmi 4 LZSS-koodaus

Alkuehto: Merkkijonoa=a

1 a

2 :::a

n

onsyote,I ikkunanpituusjaM sovituksen

maksimipituus. Yksinkertaisuuden vuoksi oletetaan, etta a

i

; kun i 0, ovat

jotainsopivia arvoja (esim. 0).

1: j :=1:

2: while j n do

3: Etsi pisin sellainen merkkijono ! = a

p I :::a

p+k I

, p = 0;:::;(I 1);k =

0;:::;M, etta! @a

j :::a

N .

4: if != then

5: Koodaa merkki a

j

,j :=j +1.

6: else

7: Koodaa (p;j!j),j :=j+j!j.

8: end if

9: end while

3.8 Ziv-Lempel-koodaus

Kenties tunnetuin Lempelin ja Zivin kehittamista tiivistysmenetelmista on LZ78,

jonkatunnetuin varianttionWelchinkehittamaLZW[41].Kun LZ77:ssakaytettiin

sanakirjanaaiemminnahtyadataa,rakennetaanLZW:ssasanakirjaajatkuvastikoo-

dauksen aikana. Menetelmaa kutsutaan dynaamisen sanakirjan menetelmaksi

(dynamicdictionarymethod).LZWonkaytossamm.tunnetussaGIF-tiedostoformaa-

tissa, mutta sen kayttoa rajoittaaUnisysinpatentti.

LZWonluonteeltaanmukautuvajasepystyyyhdellamerkillaesittamaanpitkia

sarjojasyotteesta.Seeitarvitsetietoalahteentodennakoisyysjakaumastaennenkoo-

dausta,vaanpystyy dynaamisestisopeutumaansiihenkoodauksenaikana.Sopivalle

lahteelle LZW pystyy saavuttamaan informaatioteoreettisen alarajan; kaytannossa

joudutaan kuitenkin tekemaan kompromisseja, joissa optimaalisuudesta joudutaan

LZW-algoritmi(Algoritmi5)perustuusyotteenrekursiiviseenjasentamiseeneril-

lisiinlohkoihin;samallanahdyistalohkoistamuodostetaan sanakirja. Lohkoksivali-

taan ainapisin sanakirjassaesiintyvasana,jokaesiintyy syotteessaalkaen paikasta,

jossa koodaaja on menossa. Aluksi sanakirja on taytetty kaikilla lahdeaakkoston

merkeillats. jokainen sana sanakirjassa onyhden merkin mittainen. Etsitaan sana-

kirjasta mahdollisimman pitka sana !, joka esiintyy tulevan syotteen etuliitteena

ja koodataan sanan indeksi. Edetaan syotteessa j!j merkkia. Lisataan sanakirjaan

sana !a,jokakoostuusanakirjastaloydetystasanastaja merkista,johonpaadyttiin

syotteessaetenemalla.Sanatindeksoidaansamassajarjestyksessa kuinne onlisatty.

[41]

Algoritmi 5 LZW-koodaus

Alkuehto: on lahdeaakkosto, a=a

1 a

2 :::a

n

onsyote.

1: for all x

i

2do

2: Lisaa sanakirjaansana x

i

indeksiin i.

3: endfor

4: i:=jj:

5: j :=1:

6: while j n do

7: Etsi pisin sellainensanakirjaan kuuluvasana !, etta !@a

j :::a

n .

8: j :=j+j!j.

9: Tulosta!:n indeksi sanakirjassa.

10: Lisaa sanakirjaansana !a

j

indeksiini.

11: i:=i+1:

12: endwhile

Esimerkki 3.8.1 Taulukossa 3.6on esitetty esimerkki LZW:n toiminnasta. Jasen-

nyksessamerkinta!?tarkoittaa,ettajasentajaonjasentamassasanaa!jamerkinta

!a;a? sita, etta on jasennetty ja lisatty sanakirjaan sana !a ja tulostettu sanan !

indeksi.Aluksisanakirjaonf0;1g.Toisenmerkinkohdallaensimmainentuntematon

merkkion1,koska sanaa01eiloydy sanakirjasta.Pisinsovittunutsana oli0,joten

koodataan sen indeksi ja lisataan01sanakirjaan.

Koodaajallaonpurkamisenkannaltatarkeaviimeinen-ensimmainen-ominaisuus

(last-rstproperty),jokatarkoittaasita,ettaviimeksilisatynsananviimeinenmerk-

ki on seuraavan jasennetyn sanan ensimmainen merkki.Ominaisuutta tarvitaanti-

Syote Tulos Sanakirja Jasennys

0 0, 1 0?

1 0 0, 1,01 01,1?

1 1 0, 1,01, 11 11,1?

0 1 0, 1,01, 11,10 10,0?

0 0 0, 1,01, 11,10,00 00,0?

1 0, 1,01, 11,10,00 01?

1 2 0, 1,01, 11,10,00,011 011, 1?

0 0, 1,01, 11,10,00,011 10?

0 4 0, 1,01, 11,10,00,011, 100 100, 0?

1 0, 1,01, 11,10,00,011, 100 01?

EOF 2 0, 1,01, 11,10,00,011, 100 01

Taulukko 3.6: EsimerkkiLZW-koodauksesta

Purkajalukeeindeksinjatulostaasensisaltamanmerkkijonon!.Purkamistajat-

ketaan lukemalla seuraava indeksi ja lisaamallasanakirjaan sana !a, joka muodos-

tetaan edellisesta sanasta ! ja seuraavan indeksin sisaltamansanan ensimmaisesta

merkista a. Purkaja voi saada syotteekseen indeksin, joka ei ole sanakirjan sisalla.

Tama johtuu siita, etta koodaaja on jo lisannyt sanan sanakirjaan, mutta purkaja

ei ole voinut sita tehda, koska ei viela tieda sanan viimeista kirjainta. Ongelma il-

menee,kunkoodaajaonsaanutsyotteekseen x!x!x,missaxonyksittainenmerkki

ja ! joko tyhja tai sellainen merkkijono, etta x! on jo sanakirjassa. Tilanteen rat-

kaisemiseksi on sovellettava viimeinen-ensimmainen-ominaisuutta, jolloin edellisen

puretun merkkijonon ensimmainen kirjain on purettavan merkkijonon viimeinen,

nainongelmaon ratkaistu.[41]

Esimerkki 3.8.2 Purettaessa esiintyvaa ongelmaa ja sen ratkaisua on havainnol-

listettu taulukossa 3.7; viimeinen-ensimmainen-ominaisuuden kaytto on merkitty

(LF):lla. Kun purkaja saa syotteeksi indeksin 2, jolla ei ole vielasanaa sanakirjas-

sakaytetaanviimeinen-ensimmainen-ominaisuuttajaotetaansen viimeiseksikirjai-

meksiedellisella kierroksellapuretun sanan(indeksi 0) ensimmainenmerkki 0.

Algoritmin toteutuksessa ei ole jarkevaa tallettaa sanakirjaan jokaista merkki-

jonoa sellaisenaan, koska ne veisivat liikaatilaa ja merkkijonojen etsimisesta tulisi

vaikeaa. Merkkijonotvoidaantallettaapaallekkainpuuhun siten,ettajokainenpol-

Tiivistys

Syote Tulos Sanakirja Jasennys

0 0,1 0?

0 0 0,1, 00 00, 0?

0 0,1, 00 00?

0 2 0,1, 00,000 000, 0?

0 0,1, 00,000 00?

0 0,1, 00,000 000?

EOF 3 0,1, 00,000 000

Purkaminen

Syote Tulos Sanakirja Jasennys

0 0 0,1, 0? 0, 0?

2 00 0,1, 00(LF), 00? 00, 0?

3 000 0,1, 00,000(LF), 000? 000, 0?

Taulukko 3.7: Viimeinen-ensimmainen-ominaisuuden kaytto.

merkkijonon seuraavanmerkin.

4

Jarjestelyllaonhelpompaaetsia pisinsovitus, kos-

ka oikean polun seuraaminen karsii automaattisesti pois merkkijonot, jotka eivat

sovitu syotteeseen. Taman tietorakenteen avulla saadaan algoritmin aikavaatimus

lineaariseksi syotteen pituuden suhteen, olettaen, etta oikean lapsisolmun valinta

voidaan tehda vakioajassa. Kuvassa 3.4 on esitetty toteutuksen tietorakenteen tila

taulukossa 3.6 esitetyn esimerkin lopussa. Tehtavaksi jaa viela algoritmin tuotta-

mien indeksien koodaaminen; tyypillisesti kaytetaan pieninta maaraa bitteja, jolla

voidaan esittaa sanakirjan koko. Koodaukseen voidaan hyvin kayttaa myos jotain

universaalikoodia.

3.9 Aritmeettinen koodaus

Gershon ja Grayn [11] mukaan Eliasin julkaisemattomaan koodausmenetelmaan

pohjautuva aritmeettinen koodaus on teoreettisesti optimaalinen; se saavuttaa ai-

na informaatioteoreettisen alarajan koodisanan pituudelle. Menetelmaa ovat ke-

hittaneet mm. Rissanen ja Langdon [31], Witten et al. [43], Fenwick [10] ja Moat

[27]. Ensimmaisen monimerkkisella aakkostolla toimivan aritmeettisen koodaajan

kaytannon toteutuksen esittivatWitten et al.[43] vuonna 1987, jonka jalkeen arit-

meettisesta koodauksesta tuli suosittu entropian koodauksen menetelma. Fenwick

4

1 1 0

0 0 1 0 1

Loppuliitteet Etuliite

Kuva 3.4: LZW toteutuksen tietorakenne.

[10] ratkoo mukautuvaan aritmeettiseen koodaukseen liittyvia ongelmia ja Moat

[27] esittaa parannuksia koodaajaan ja yhteenvedon menetelmankehityksesta.

A B C

0

0.5 0.5

1 1 0.6

CAB...

Kuva 3.5: Puhdas aritmeettinenkoodaus.

Aritmeettisen koodauksen ideana onlahettaaviestireaalilukunax valilta[0;1).

Vali jaetaan merkkien todennakoisyyden perusteella osavaleihin niin, etta kunkin

osavalin pituus kuvaa merkin todennakoisyytta. Merkin koodaamiseksi tarvitsee

lahettaa mika tahansa luku, joka kuuluu merkkia kuvaavalle valille. Koko viestin

koodaamiseksi valitjaetaan aina uudelleen rekursiivisesti ja lahetetaan tarkemmin

rajoitettu luku. Jos koodaaja on menossa valilla I = [a;b) ja koodattavaa lukua

vastaa valin [0;1) jaossavali [c;d), niinluvun on kuuluttava valille

I 0

=

a+ b a

c

;a+ b a

d

: (3.31)

[a;b), niinluku alkuperaisellaosavalijaollaon

x 0

=

x a

b a

: (3.32)

Nytpurkajanonvainetsittavasealkuperaisenjaonvali,jollex 0

kuuluujalahdeaak-

koston merkki,jota kyseinen vali vastaa.

Esimerkki 3.9.1 Koodaustaonhavainnollistettukuvassa 3.5, jossaonaakkostona

fA;B;Cg ja merkkien todennakoisyyksina p(A) = 0:2, p(B) = 0:3 ja p(C) = 0:5.

Valit on jaettu siten, etta merkkia A vastaa vali [0;0:2), merkkia B vali [0:2;0:5)

ja merkkia C vali[0:5;1:0). Koodattava viesti alkaa merkeilla CAB. Ensimmainen

merkki C on koodattava valille [0:5;1), joka jaetaan osiin. Merkkeja vastaaviksi

osavaleiksisaadaan[0:5;0:6),[0:6;0:75)ja[0:7;1:0).SeuraavamerkkionA,jolloinon

koodattava vali [0:5;0:6). Jatkamalla menettelya huomataan, etta viestin alkuosan

CAB esittamiseksi voidaan lahettaamikatahansa lukuvalilta [0:52;0:55).

Tarkein aritmeettisen koodaajan etu on sen joustavuus: se erottaa lahteen ti-

lastollisen mallin koodaajasta taysin. Aina kun seuraavaa koodattavaa valia jae-

taan,voidaanvaihtaa jakoakoodaajastariippumatta.Etu onmerkittava,koskaesi-

merkiksiHuman-koodaajastamallin erottaminenon lahesmahdotonta.Aritmeet-

tisen koodaajan optimaalisuus ei ole niin merkittavaa kuin voisi helposti luulla;

Human-koodikin on useissa tapauksissa lahes optimaalista. Suurin ero Human-

koodiin tulee tilanteessa, jossa jonkin merkin todennakoisyys on lahella ykkosta.

Tassa tapauksessa Human-koodi on huonoimmillaan, koska sen on esitettava jo-

kainen lahdeaakkoston merkki vahintaan yhdella bitilla. Aritmeettisessa koodauk-

sessa eitata rajoitusta ole.Kaytannossasuuriintiivistyssuhteisiin paastaanyleensa

vain laadukkaiden tilastollistenmallienavulla. [16]

Suurin aritmeettisenkoodaajan ongelmaonsen hitaus,taydentarkkuuden arit-

meettinen koodaaja on hitaampi kuin Human- tai Ziv-Lempel-koodaus. Toinen

koodaajanongelmaonse,ettei sitavoida toteuttaarinnakkaislaskennanavulla,kos-

ka seuraava koodisana riippuu edellisen koodatun merkin vaikutuksesta koodaajan

tilaan. Koodista ei myoskaan selvia tiedoston loppuminen; tama ongelma ratkais-

taan yleensa erillisen EOF-merkinlisayksella lahteen aakkostoon. [16]

Aritmeettisenkoodaajantoteuttaminensellaisenaaneikaytannossaonnistu,kos-

ka se tarvitsisi aarettoman tarkkaa laskentatarkkuutta. Tarkkuuden tarve kasvaa

koko ajan koodattavan viestin kasvaessa. Witten et al. [43] esittivat yksinkertai-

sopivasti ettei laskutarkkuus paase kasvamaan liian suureksi. Koodaajan tilan tal-

lentamiseksi tarvitaan vain 3 lukua (yla- ja alaraja ja laskuri). Jos koodattava vali

sisaltyy valiin [0;1=2), niin seuraava bitti koodattavan luvun binaariesityksessa on

0, vastaavastijos valisisaltyy valiin[1=2;1), niinseuraava bitti koodattavanluvun

binaariesityksessaon1.Josvalisisaltyyvaliin[1=4;3=4),niinseuraavankoodattavan

bitin jalkeinen bitti on arvoltaan painvastainen. Koodattavaavalia voidaan taman

luokituksen jalkeen laajentaa kaksinkertaiseksi laajentamalla lineaarisesti suurem-

pi vali, jolle se kuului valiksi [0;1). Viimeisen vaihtoehdon tapahtumakerroista on

lisaksi pidettava kirjaa laskurilla. Kun tiedetaan seuraava bitti, pitaa koodata las-

kurinverran bitteja,joiden arvo on painvastainenja nollatalaskuri.

Kaytannontoteutuksessareaalilukujentilallakaytetaankiinteapilkkulukuja(xed

pointnumber)elilukuvali[0;1)skaalataanvaliksi[0;2 b

)jakaytetaanesitykseenvain

valillekuuluviakokonaislukuja,jolloinlukua 1voisivastataesimerkiksi2 16

=65536,

talloinlukua1=2vastaisi2 16

=2=32768.Mitasuurempaamaaraabittejakaytetaan,

sitatarkemmaksikoodaajatuleeja tarkkuudenkasvaessa kasvaamyostiivistysteho,

koskalahteen merkkien todennakoisyydet voidaan esittaatarkemmin.

Moat [27] esittaa parannetun version koodaajasta (Algoritmit 6, 7 ja 8), jos-

sa koodaajan vali esitetaan sen alarajan L ja pituuden R avulla, jolloin saadaan

saastojaaritmeettistenoperaatioidenmaarassa.Algoritmitonesitettysamassamuo-

dossa;operaatioidenjarjestyksellaonmerkitysta,koska kaikkituloksetpyoristetaan

kokonaisluvuiksi. Kaytannon toteutuksessa todennakoisyyksia kasitellaan kumula-

tiivisen frekvenssitaulukon 5

avulla. Koodaajan tilaksi alussa asetetaan L := 0 ja

R := 2 b 1

ja koodauksen lopussa kirjoitetaan L:n b bittia siten, etta ensimmaisen

bitin jalkeen kirjoitetaan c kappaletta bitteja, joiden arvo on painvastainen en-

simmaisen bitinkanssa, jaloputbitit sellaisenaan.Purkajan tilaksialustetaanR:=

2 b 1

ja D:narvoksiluetaan b ensimmaistabittiatiedostosta. Purkaminentapahtuu

kutsumallaensinkohdefrekvenssinpurkua(Algoritmi7)jaetsimallasittenkoodattu

vali, jollekohdefrekvenssi kuuluu. Purkaja paivitetaankoodatullavalillaja uudella

frekvenssitaulukon ylarajalla,jos se onmuuttunut(Algoritmi8).

Kaytannon toteutuksen aiheuttamat menetykset optimaaliseen ratkaisuun ver-

rattuna on osoitettu mitattomiksi. Jos reaalilukuvali [0;1) skaalataan kokonaislu-

kuvaliksi [0;N), niin ylimaarainen koodin pituus syotemerkkia kohti on pienempi

kuin 4=(Nln2) bittia. Tyypillisella N:n arvolla 65536 ylimaarainen koodin pituus

onvahemmankuin10 4

bittiamerkkiakohti.KunEOF-merkkilisataanaakkostoon,

5

Algoritmi 6 Aritmeettinen koodaus

Alkuehto: I =[l;h)onkoodattavavalikumulatiivisessafrekvenssitaulukossa ja t

on yhteenlaskettu merkkien maara (todennakoisyytena valion [l=t;h=t)). Koo-

daaja on menossa valilla, jonka alaraja on L ja pituus R , ja c on bittilaskuri.

Koodaukseen kaytetaan b bittia.

1: r:=R =t.

2: L:=L+rl.

3: if h<t then

4: R :=r(h l).

5: else

6: R :=R rl.

7: endif

8: while R2 b 1

do

9: if L+R 2 b 1

then

10: Tulosta 0-bitti ja ckpl 1-bitteja.

11: c:=0.

12: else if L2 b 1

then

13: L:=L 2 b 1

.

14: Tulosta 1-bitti ja ckpl 0-bitteja.

15: c:=0.

16: else

17: L:=L 2 b 2

.

18: c:=c+1.

19: end if

20: L:=2L.

21: R :=2R .

22: endwhile

Algoritmi 7 Kohdefrekvenssin purkaminen

Alkuehto: Purkaja on menossa valilla, joka pituus on R . D on koodatun luvun

etaisyys valinalarajastaja t onfrekvenssitaulukonylaraja.

Jattoehto: Palautettuarvoonkohdefrekvenssi,jonkaavullavoidaanselvittaakoo-

dattu valifrekvenssitaulukosta.

1: r:=R =t;

2: return minft 1;D=rg.

Algoritmi 8 Aritmeettinendekoodaus

Alkuehto: I =[l;h)onedellisellakierroksellakoodattuvalikumulatiivisessafrek-

venssitaulukossa ja t on yhteenlaskettu merkkien maara. Purkaja on menossa

valilla,jonkaleveys onR . Koodaukseenkaytetaanb bittia.Donpuretun arvon

etaisyys valin alareunasta. Luku r on asetettu edellisessa kutsussa kohdefrek-

venssin purkuun.

1: D:=D rl.

2: if h <t then

3: R :=r(h l).

4: else

5: R :=R rl.

6: endif

7: while R 2 b 2

do

8: R :=2R .

9: D :=2D+luebitti.

10: endwhile

lisaantyy t merkin mittaisen syotteen koodin pituus vahemman kuin

8t=(Nln2)+lgN +7 bittia.[16]

Aritmeettisesta koodauksesta saadaan helposti mukautuva, koska koodaaja ja

purkaja tarvitsevatvainkoodattavialukuvaleja.Ongelmaksimuodostuusiiskumu-

latiivisen frekvenssitaulukon tai jonkin muun vastaavan rakenteen yllapitaminen.

Fenwick [10] esittaaongelmaan elegantinratkaisun,jossamerkin todennakoisyyden

paivittaminen,merkin valin etsiminen ja kohdefrekvenssin valin etsiminen voidaan

suorittaaajassa O(logn) frekvenssitaulukon merkkien lukumaaransuhteen.

me aikoina huomiotaonsaanutvarsinkin musiikintiivistaminen.Signaalinkasittely

ontietojenkasittelytieteen osa-alue,jonka tavoitteenaonmuokata signaaleitasovel-

luksesta riippuvallatavalla.Usein onkyse signaalin vahvistamisesta, kohinan pois-

tamisesta tai signaalin analysoinnista. Yleisesityksia signaalinkasittelysta ovat kir-

joittaneet mm. Defatta et al. [6], Lyons [26] ja Proakis ja Manolakis [30]. Krani-

auskas[24] kasittelee signaalinkasittelynmatemaattista teoriaaseka jatkuvien etta

diskreettien signaaleiden tapauksessa. Taylor [37] keskittyy suodatinten suunnitte-

luunja antaahyvankatsauksenlineaarisistamuunnoksista. Orfanidis[28]kasittelee

satunnaisten signaalien kasittelya. Alexander [1] ja Haykin [13] kasittelevat mu-

kautuvia suodattimiaja niidensovelluksia jasignaalinkasittelyaepastationaarisessa

ymparistossa.Gersho ja Gray [11] kasittelevat signaalientiivistamista.

Tunnettuja signaalien tiivistamisen menetelmia ovat skalaarikvantisointi, die-

rentiaalinenpulssikoodimodulaatioja muunnoskoodaus.Viimeaikoinaovathuomio-

ta paljon saaneet aallokkeisiin perustuvat muunnoskoodauksen menetelmat, joita

tassakin kasitellaan.

4.1 Signaalinkasittelyn teoriaa

Proakis ja Manolakis [30] maarittelevat signaalin fyysiseksi arvoksi, joka muuttuu

ajan tai jonkin muun muuttujan mukana. Matemaattisesti signaalivoidaan esittaa

yhden tai useamman muuttujan funktiona. Esimerkiksi x(t) = 2t on signaali, joka

muuttuu lineaarisesti ajan funktiona. Signaalit voivat olla moniulotteisia; esimer-

kiksi kuvat voidaan tulkita kaksiulotteisiksi signaaleiksi. Signaalilla voi myos olla

useita kanavia, jolloinse saa vektoriarvoja:

x(t)=(x

1 (t);x

2

(t);:::;x

n (t))

T

: (4.1)

Jatkuvatsignaalitovatjatkuvienmuuttujienfunktioitajadiskreetitsignaalitdis-

kreettienmuuttujienfunktioita.Jatkuviasignaaleitaeivoidakasitelladigitaalisesti,

jotenne onmuutettavadiskreettiinmuotoon. Ensin jatkuvasignaali naytteistetaan

(sampling),naytteistettysignaalikvantisoidaan(quantization)jalopuksikvantisoin-

nintuloskoodataan.Kunpuhutaanfyysisistasignaaleista,kokoprosessiakutsutaan

A/D-muunnokseksi (analogia/digitaali)ja kaytettya laitteistoa A/D-muuntimeksi.

Diskreetti signaalisaadaan jatkuvasta signaalistanaytteistamalla:

x(n)=x(nT); n2Z; (4.2)

missa T on naytteenottovalin pituus; talloin naytteenottotaajuus f

s

on 1=T. Dis-

kreetti signaalix(n)onmaariteltyvainn:n kokonaislukuarvoilla.Naytteitaonotet-

tavariittavantiheinvalein,jottasignaalinkaikkivaihtelutsaadaantalteen.Riittava

valien tiheys saadaan nk. naytteistysteoreemasta (samplingtheorem). Sen mukaan

naytteenottotaajuuden pitaa olla vahintaan kaksi kertaa kertaa niin suuri, kuin

suuritaajuisimman naytteistettavassa signaalissa esiintyvan komponentin taajuus.

Niinpajarjestelma,jonkanaytteenottotaajuusonf

s

,voiesittaatarkastivainsignaa-

leita, joiden komponenttien taajuus on alle f

s

=2. Taajuutta f

s

=2 sanotaan Nyquis-

tin taajuudeksi.Naytteistettavastasignaalistapitaisiennennaytteistamistasuodat-

taa poistaajuudet,jotkaylittavatNyquistintaajuuden, taitapahtuu laskostumista

(aliasing).Laskostuminen tarkoittaa korkeampitaajuisen komponentin ilmenemista

matalampitaajuisenakomponenttina naytteistetyssa signaalissa.Jottatarkasteltava

informaatio sailyisi mahdollisimmanlaadukkaana, tama ei tietenkaan ole toivotta-

vaa. [30]

Digitaaliseen muotoonsignaalisaadaan kvantisoimalla:

y(n)=Q[x(n)]; (4.3)

missaQ onkvantisointioperaatio. Kvantisoinninjalkeen signaalivoi yleensa 1

saada



aarellisen maaran arvoja eli kvantisoinnissa muutetaan signaalin arvoalue diskree-

tiksi [30]. Kvantisointia kasitellaan tarkemmin myohemmin signaalien tiivistyksen

yhteydessa.

Tyypillisimmatsignaalilletehtavatoperaatiot ovat skalaarillakertominen (4.4),

yhteenlasku (4.5), kertolasku (4.6) ja siirto ajassa (4.7):

y(n)=ax(n); (4.4)

y(n)=x

1

(n)+x

2

(n); (4.5)

y(n)=x

1 (n)x

2

(n); ja (4.6)

y(n)=z k

x(n)=x(n+k); k2Z: (4.7)

1

Usein tavattaviaoperaatioitaovatmyos naytteenottotaajuuden muuttaminenylos-

(4.8) taialaspain(4.9). (upsampling,downsampling) [30]:

y(m)=x(n)"k;m =n=k; ja (4.8)

y(m)=x(n)#k;m =kn: (4.9)

Signaalit voidaan esittaa muiden signaalien avulla. Tyypillisimpia naista ovat

impulssi (impulse), askel (unit step) ja kompleksiteksponentiaalifunktiot:

Æ(n)= 8

<

:

1;n =0

0;n 6=0

; (4.10)

u(n)= 8

<

:

1;n0

0;n<0

; ja (4.11)

x(n)=re in

; (4.12)

joista viimeisia kaytetaan Fourier-analyysissa. Esimerkiksi signaali x(n) voidaan

esittaa yksikkoimpulssien avullaseuraavasti:

x(n)= 1

X

i= 1

Æ(n i)x(i): (4.13)

Talloin signaalin sanotaan olevan esitettyna aika-alueella (joskus puhutaan myos

ns. standardikannasta). [30]

Maaritelma 4.1.1 Diskreetinepajaksollisensignaalinx(n)Fourier-muunnosX(!)

on

X(!)=Ffx(n)g= 1

X

n= 1 x(n)e

i!n

: (4.14)

Fourier-muunnosonmaariteltysignaalille,jossenitseisarvojensummaon

 aarelli-

neneli P

1

1

jx(n)j<1.DiskreetinsignaalinFourier-muunnoson2-jaksollinen,ts.

X(!)=X(!+2k).Fourier-muunnosesittaa signaalineritaajuisten ja -vaiheisten

siniaaltokomponenttien lineaarikombinaationa. X(!) esittaa signaalin taajuusalu-

eella. Jaksollisten signaalien tapausta kasitellaan myohemmin diskreetin Fourier-

naisuuksien tutkimiseen. [30]

Maaritelma 4.1.2 Suodatin (lter)onjarjestelmaT,jokatuottaatoisen signaalin

syotteenaansaamastasignaalista:

y(t)=T [x(t)]: (4.15)

Maaritelma 4.1.3 JarjestelmaT onlineaarinenjaajastariippumaton(lineartime

invariant, LTI), jos ja vainjos

T [a

1 x

1

(n)+a

2 x

2

(n)]=a

1 T [x

1

(n)]+a

2 T [x

2

(n)], ja (4.16)

T

z k

x(n)

=z k

T [x(n)]: (4.17)

LTI-jarjestelmatovattavallisimpiakaikistasignaalinkasittelynjarjestelmista.Jos

jarjestelma T on LTI, voidaan se taydellisesti kuvata impulssivasteen (impulse

response) h(n) avulla; taman ominaisuuden takia LTI-jarjestelmien analysointi on

helppoa.[30]

Maaritelma 4.1.4 LTI-jarjestelmanT impulssivaste on

h(n)=T [Æ(n)]: (4.18)

Maaritelma 4.1.5 LTI-jarjestelmaT onstabiili, eli setuottaa



aarellisentulossig-

naalin jokaisella aarellisellasyotesignaalilla,jos ja vainjos

1

X

1

jh(n)j<1: (4.19)

Maaritelma 4.1.6 LTI-jarjestelmaa T sanotaan kausaaliseksi, jos

h(n)=0; kun n<0: (4.20)

Kausaalinen jarjestelma pystyy tuottamaan tulossignaalin arvon heti, kun tie-

detaansyotesignaalin arvo. Josjarjestelmaeiolekausaalinen, pystytaansekaytan-

nossa toteuttamaanvainviiveen avulla.[30]

LTI-jarjestelman vaste mielivaltaiseen signaaliin x(n) saadaan helposti selville