Käyttäjä:NettiKirjoittaja

Muokkausnäkemyksiäni

Tässä yksi kirjoittaja matematiikasta lisää...

.....

Lähdekoodaus (informaatioteoria)

Lähdekoodaus tarkoittaa tiedonpakkauksessa sitä, että kuhunkin lähdeaakkoston $\mathbf {} S=\{s_{1},\dots ,s_{n}\}$ symboliin liitetään bittijono tavalla, joka mahdollistaa näin peräkkäisiksi bittijonoiksi koodattujen lähetyksessä todella peräkkäin toteutuneiden lähdesymbolien jonon yksikäsitteisen selvittämisen riippumatta siitä mikä tämä jono on. Mahdollisen jonon pituutta ei ole rajoitettu ja lähdeaakkoston symbolit saavat esiintyä jonossa useasti.

Lähdeaakkosto ja koodaus

Tässä tarkastelussa lähdeaakkoston $\mathbf {} S$ koko on aina äärellinen (symboleita $\mathbf {} n$ kappaletta), eli tarkastelu on digitaalinen. Symbolien reaalinen merkitys voi olla esimerkiksi kuvan pikselien eri väriarvot. Valittu koodaus tarkoittaa funktiota $\mathbf {} c$, joka liittää kuhunkin symboliin tietyn bittijonon. Jatkossa $\mathbf {} l_{i}$ merkitsee valitun koodauksen $\mathbf {} c$ symboliin $\mathbf {} s_{i}$ liittämän bittijonon pituutta. Esimerkiksi lähdeaakkoston koon ollessa $\mathbf {} 3$ voitaisiin koodaus valita niin, että $\mathbf {} c(s_{1})=010,c(s_{2})=1$ ja $\mathbf {} c(s_{3})=101$, jolloin $\mathbf {} l_{1}=3,l_{2}=1$ ja $\mathbf {} l_{3}=3$. Tällöin esimerkiksi lähdeaakkosten jono $\mathbf {} s_{3}s_{1}s_{2}s_{3}$ lähetettäisiin bittijonona $\mathbf {} c(s_{3})c(s_{1})c(s_{2})c(s_{3})=1010101101$.

Yksikäsitteisen purkautumisen vaatimus

Vastaanottaja näkee vain saapuneen peräkkäisen bittijonon, ja hänen on vain sen perusteella pystyttävä dekoodaamaan eli purkamaan biteiksi koodattuna lähetetyn symbolijonon pituus ja kussakin jonon paikassa oleva symboli. Tästä vaatimuksesta seuraa se, että kaikki koodaukset eivät ole kelvollisia. Triviaali esimerkki on se, jossa koodaus liittäisi kahteen eri symboliin saman bittijonon, jolloin dekoodaaja ei tämän bittijonon vastaanottaessaan pystyisi päättelemään kumpaa symbolia sillä tarkoitettiin. Selvää on myös, että mitään symbolia ei voi koodata bittejä sisältämättömäksi tyhjäksi bittijonoksi, sillä tyhjästä bittijonosta dekoodaaja ei kykenisi päättelemään sitä kuinka monta kertaa tämä symboli on siihen koodattu. On myös monimutkaisempia esimerkkejä kuten edellisessä kappaleessa esitetty esimerkkikoodaus, sillä siinä esimerkkinä esitetty bittijono voisi olla peräisin myös symbolijonosta $\mathbf {} s_{2}s_{1}s_{3}s_{3}$, sillä onhan $\mathbf {} c(s_{2})c(s_{1})c(s_{3})c(s_{3})=1010101101$. Toinen esimerkki saataisiin koodauksesta $\mathbf {} c(s_{1})=01,c(s_{2})=101$ ja $\mathbf {} c(s_{3})=010$, jolloin $\mathbf {} c(s_{1}s_{1}s_{1})=c(s_{1})c(s_{1})c(s_{1})=010101=c(s_{3})c(s_{2})=c(s_{3}s_{2})$. Huomaa, että tässä saman lähetetyn bittijonon tuottivat kaksi eri lähdesymbolijonoa, joilla oli eri pituudet. Yksikäsitteisen dekoodautuvuuden vaatimus koskee tietenkin vain niitä bittijonoja, jotka voivat koodauksessa olla peräisin ainakin yhdestä koodatusta lähdesymbolijonosta, mutta lisäksi voi olla olemassa bittijonoja, jotka eivät ole minkään lähdesymbolijonon koodauksia, mutta tällaisista bittijonoista ei tarvitse välittää. Häviöllisessä koodauksessa luovutaan yksikäsitteisen dekoodautuvuuden vaatimuksesta, mistä aiheutuvien "tietohäviöiden" mittaamista käsittelee Hävikkiteoria.

McMillanin ja Kraftin epäyhtälöt

Oletetaan, että lähdeaakkoston koko on $\mathbf {} n$ ja valittu koodaus $\mathbf {} c$ liittää symboliin $\mathbf {} s_{i}$ bittijonon, jonka pituus on $\mathbf {} l_{i}$. Valittu koodaus voi McMillanin epäyhtälönä tunnetun tuloksen mukaan olla yksikäsitteisesti dekoodattavissa vain silloin, kun

$\sum _{i=1}^{n}{\frac {1}{2^{l_{i}}}}\leq 1.$

Jos koodaus ei toteuta kyseistä epäyhtälöä, voidaan siis löytää kaksi eri lähdesymbolijonoa, jotka koodaus koodaa samaksi lähetettäväksi bittijonoksi. Intuitiivisesti ajatellen McMillanin epäyhtälön vaatimus on, että "liian moni symboli ei saa koodautua liian lyhyeksi bittijonoksi", sillä muuten $\mathbf {} 1/2^{l_{i}}$-yhteissumma sisältäisi liikaa "suuria" termejä ja ylittäisi arvon $\mathbf {} 1$. Triviaali esimerkki tästä "liiasta lyhyydestä" on koodaus $\mathbf {} c(s_{1})=0,c(s_{2})=1$ ja $\mathbf {} c(s_{3})=0$, joka ei toteuta epäyhtälöä (yhteissumma $\mathbf {} =3\cdot 1/2^{1}=3/2>1$), mutta joka ei toteuta yksikäsitteistä dekoodautuvuuttakaan, sillä $\mathbf {} 0$-bitin kohdalla ei voitaisi tietää tarkoittaako se symbolia $\mathbf {} s_{1}$ vai $\mathbf {} s_{3}$. Kuitenkaan tämän epäyhtälön toteutuminen ei vielä takaa yksikäsitteistä dekoodautuvuutta, sillä onhan se toteutunut edellisissä esimerkeissäkin, vaikka niissä koodaukset eivät ole olleet yksikäsitteisesti dekoodattavissa. Kraftin epäyhtälönä tunnettu tulos sanoo kuitenkin, että $\mathbf {} l_{i}$-arvojen toteuttaessa mainitun epäyhtälön voidaan löytää koodaus, joka koodaa lähdeaakkoston symbolit ns. prefix-koodiksi, joka on varmasti yksikäsitteisesti dekoodattavissa. Prefix-koodaus on siis yhtä hyvä kuin mikä tahansa yksikäsitteisesti dekoodattavissa oleva koodaus siinä mielessä, että luopumalla alla kuvattavasta käytetyn koodin prefix-vaatimuksesta ei saataisi hyötyä niin, että symbolit voitaisiin koodata lyhyemmiksi bittijonoiksi yksikäsitteinen dekoodautuvuus säilyttäen. Tästä syystä prefix-koodaus on suositeltava tapa, sillä prefix-koodilla on lisäksi hyödyllisiä ominaisuuksia, joita kuvataan alla.

Prefix-koodaus

Prefix-koodi tarkoittaa koodausta, jossa minkään symbolin bittijono ei ole toisen symbolin bittijonon prefix eli alkuosa tai sama. Tästä seuraa erityisesti se, että prefix-koodauksessa mikään symboli ei voi koodautua tyhjäksi bittijonoksi. Esimerkiksi "Lähdeaakkosto ja koodaus"-kappaleessa esitetty koodaus ei ole prefix-koodaus, sillä siinä symbolin $\mathbf {} s_{2}$ bittijono $\mathbf {} 1$ on symbolin $\mathbf {} s_{3}$ bittijonon $\mathbf {} 101$ alkuosa. Sensijaan esimerkiksi $\mathbf {} 4$-symbolisen lähdeaakkoston koodaus $\mathbf {} c(s_{1})=0,c(s_{2})=100,c(s_{3})=101$ ja $\mathbf {} c(s_{4})=11$ on prefix-koodaus. Prefix-koodi on yksikäsitteisesti purettavissa, mikä nähdään seuraavalla päättelyllä. Jos kaksi eri symbolijonoa koodautuu samaksi bittijonoksi, voidaan olettaa jo niiden ensimmäisten symbolien eroavan toisistaan (Tarvittaessa voidaan tarkastelusta poistaa alusta saman symbolijono-alkuosan tuottama sama bittijono-alku.), mutta koska koodattu bittijono on sama, toisen alku-symbolin bittijonon on pakko sisältyä toisen alku-symbolin bittijonoon (Näistä pidempi sisältää lyhyemmän tai sitten molempien pituus on sama.), mikä on vastoin prefix-koodauksen määritelmää. Tämä päättely johtaa hyvin yksinkertaiseen ja nopeaan dekoodaukseen, jossa edetään bittijonoa vasemmalta oikealle kunnes kuljettu "osabittijono" on jonkin lähdesymbolin koodaus, jolloin voidaan olla varmoja, että juuri tämän symbolin pitää olla seuraavaksi. Jatkamalla bittijonossa löydetyn seuraavan symbolin koodauksen jälkeisestä kohdasta saadaan tätä päättelyä toistamalla dekoodatuksi koko vastaanotettu bittijono. Esimerkiksi bittijono $\mathbf {} 1000110$ on tullut yllä olevalla prefix-koodauksella symbolijonosta $\mathbf {} s_{2}s_{1}s_{4}s_{1}$, sillä jonon alussa on $\mathbf {} 100$, joka on symbolin $\mathbf {} s_{2}$ koodaus, minkä jälkeen loppu bittijonosta on $\mathbf {} 0110$, jonka alusta puolestaan löytyy symbolin $\mathbf {} s_{1}$ koodaus $\mathbf {} 0$, ja samalla tavalla nähdään, että loppu tästä bittijonosta on $\mathbf {} 110$, joka puolestaan koostuu symbolien $\mathbf {} s_{4}$ ja $\mathbf {} s_{1}$ koodauksista.

Symbolijonojen todennäköisyyksien merkitys

Lähdeaakkoston symbolien jonoihin liittyy todennäköisyys, joka kuvaa todennäköisyyttä sille, että kyseinen symbolijono todella toteutuu. Jonon eri paikkoihin toteutuvat symbolit voidaan ajatella yksinkertaisina satunnaismuuttujina $\mathbf {} X_{1},\dots ,X_{m}$, missä alaindeksi ilmaisee symbolin paikkaa jonossa ja $\mathbf {} m$ on koodattavan jonon pituus. Tavallisesti satunnaismuuttujat saavat arvokseen reaalilukuja, mutta nyt voidaan tulkita niin, että satunnaismuuttujan toteutunut arvo ilmaisee symbolin järjestysnumeroa, jolloin esimerkiksi $\mathbf {} X_{3}=2$ tarkoittaa sitä, että jonon kolmanneksi symboliksi toteutuu lähdesymboli $\mathbf {} s_{2}$. Symboleita ilmaisevien satunnaismuuttujien jono $\mathbf {} X_{1},X_{3},X_{3},\dots$ on stokastinen prosessi, ja yksinkertaisimmissa tarkasteluissa tehdään yleensä epärealistinen oletus siitä, että tämä satunnaismuuttujien jono olisi IID (engl. Independent and identically-distributed) eli riippumaton ja samoinjakautunut, mikä tarkoittaa sitä, että sama todennäköisyysjakauma koskee kaikkia $\mathbf {} X_{i}$-satunnaismuuttujia ja jonkin $\mathbf {} m$-pituisen jonon toteutumisen todennäköisyys saadaan yksinkertaisesti tulona yksittäisten lähdeaakkosten sattumisten todennäköisyyksistä. Todennäköisyysjakaumana voi olla esimerkiksi $\mathbf {P} (s_{1})=0.7,\mathbf {P} (s_{2})=0.1,\mathbf {P} (s_{3})=0.2$, jolloin $\mathbf {} 5$-pituisia jonoja tarkasteltaessa jonon $\mathbf {} s_{1}s_{2}s_{2}s_{3}s_{1}$ toteutumisen todennäköisyys $\mathbf {P} (s_{1}s_{2}s_{2}s_{3}s_{1})=0.7\cdot 0.1\cdot 0.1\cdot 0.2\cdot 0.7=0.00098$. IID-oletuksen riippumattomuuden perusteella voidaan todeta, että toteutuneen lähdesymbolijonon biteiksi koodatun jonon pituus jaettuna toteutuneen lähdesymbolijonon pituudella on odotusarvoltaan

$\sum _{i=1}^{n}l_{i}\cdot p_{i}$

, missä $\mathbf {} n$ on lähdeaakkoston symbolien määrä, $\mathbf {} l_{i}$ on käytetyn koodauksen $\mathbf {} c$ symboliin $\mathbf {} s_{i}$ liittämän bittijonon pituus ja $\mathbf {} p_{i}=\mathbf {P} (s_{i})$ eli symbolin $\mathbf {} s_{i}$ toteutumisen todennäköisyys, joka ei IID-oletuksen takia riipu symbolin paikasta jonossa. Selvästikin on syytä pyrkiä minimoimaan tämä odotusarvo, joka ilmaisee sen kuinka monta bittiä koodattu bittijono käyttää lähdesymbolia kohti "tyypillisesti toteutuvassa" lähdesymbolijonossa, jossa symbolin $\mathbf {} s_{i}$ esiintymisosuus on lähellä sen todennäköisyyttä $\mathbf {} p_{i}$. Intuitiivisesti ajatellen tämä minimointi tapahtuu niin, että usein toistuvat korkean todennäköisyyden symbolit koodataan yksikäsitteisen dekoodautuvuuden vaatimus huomioiden mahdollisimman lyhyiksi bittijonoiksi, kun taas harvoin toistuvan symbolin kohdalla voidaan koodauksessa käyttää melko pitkääkin bittijonoa. Käytännössä tämä onnistuu käyttämällä Huffmanin koodausta, josta voidaan osoittaa, että sen tuottama koodi on prefix-koodi, joka minimoi mainitun odotusarvon kaikkien yksikäsitteisen dekoodauksen vaatimuksen toteuttavien mahdollisten koodausten joukossa. ANNA ESIMERKKI JONKIN JAKAUMAN SISÄLLÄ SEN HUFFMAN-KOODISTA JA TOISESTA PREFIX-KOODISTA JOLLA ODOTUSARVO ON AIDOSTI SUUREMPI(EHKÄ 4 SYMBOLIN JOLLA KAIKILLA 2 BITIN KOODI).

!!! Puhu lopussa yleistyksestä niin että koodiaakkostokin isompi kuin binaarinen ja siitä että puhutaan myös häiriöttömäksi koodaukseksi erotuksena kanavakoodauksesta, jossa virheiden varalle lisätään redundanssia ja siitä, että lähdesymbolien jono syntyy satunnaisprosessissa, joka harvoin IID vaan esim. Markovin on realistisempi.

$\mathbb {C}$

Tämä käyttäjä on korkeakoulutason matemaatikko.

Tämä käyttäjä on perehtynyt matematiikkaan.