Koodaus- ja informaatioteoria [PDF]

Zitiervorschau

KOODAUS- JA INFORMAATIOTEORIA Keijo Ruohonen

1999

i

Sisältöluettelo 1 1 3 5 8 9 10

I LINEAARISET KOODIT 1. Lohkokoodit 2. Ekskursio: Alkukunnat 3. Lineaariset koodit 4. Systemaattinen koodaus 5. Standardidekoodauskaavio 6. Hamming-koodit

13 13 13 15 18 18 20 21

II SYKLISET KOODIT 1. Syklinen koodi 2. Ekskursio: Polynomirenkaat ja äärellinen z-muunnos 3. Syklinen koodi polynomi-ihanteena 4. Syklisen koodin systemaattinen koodaus 5. Syklisen koodin generoija- ja tarkistusmatriisit 6. Meggitt-dekoodaus 7. Golay-koodit

22 22 28 32

III BCH-KOODIT 1. Ekskursio: Äärelliset kunnat 2. BCH-koodit 3. Dekoodaus Berlekamp–Massey-algoritmi

38 39

4. 5.

Reed–Solomon-koodit Pyyhkiymien korjaus

43 43 46 51 53 55

IV PURSKEVIRHEIDEN KORJAUS 1. Yleistä 2. Tulokoodit 3. Kiedotut koodit 4. Katenoidut koodit 5. Fire-koodit

59 59 60

V KOODIRAJOJA 1. Yleistä 2. Ylärajoja Plotkin-raja Hamming-raja Muita ylärajoja

64

3.

Alarajoja Gilbert-raja Varshamov-raja

66 70 70 74 79 80

4.

Rajojen vertailua

VI KONVOLUUTIOKOODAUS 1. Ekskursio: Lineaariset järjestelmät 2. Konvoluutiokoodaus 3. Viterbi-dekoodaus 4. Jonodekoodaus m-algoritmi Pinoalgoritmi Monipinoalgoritmi Fano-algoritmi

ii 86 VII INFORMAATIO JA ENTROPIA 86 1. Ekskursio: Diskreetti todennäköisyys 90 2. Informaatio 90 3. Entropia 93 4. Ehdollinen entropia. Keskinäisinformaatio 98 5. Kolme tapausjärjestelmää: Data–Processing-lause 101 6. Entropian yksikäsitteisyys 106 7. Jatkuvan satunnaismuuttujan entropia 108 VIII LÄHTEEN KOODAUS 108 1. Yleistä 108 2. Muistiton lähde, lohkokoodi 114 3. Muistiton lähde, vaihtuvapituinen koodi 117 4. Optimikoodaus 120 5. Huffman-koodaus 122 6. Muita koodausmenettelyjä Juoksulukukoodaus Aritmeettinen koodaus

124

7.

Muistillinen lähde

125 IX KANAVAKOODAUS 125 1. Muistiton kanava. Kanavan kapasiteetti 126 2. Kanavakoodauslause 127 3. Binäärinen symmetrinen kanava 129 X MAKSIMIENTROPIAPERIAATE 129 1. Yleistä 130 2. Maksimientropiajakaumat 133 134

K IRJALLISUUTTA HAKEMISTO

Esipuhe Käsillä oleva moniste muodostaa TTKK:n matematiikan kurssien Koodausteoria ja Informaatioteoria luentorungon. Moniste on tarkoitus täydentää luennoilla esimerkein sekä lisäyksin. Mainitut kurssit on tarkoitettu tukemaan lähinnä signaalien käsittelyyn, tietoliikennetekniikkaan sekä elektroniikkaan liittyviä kursseja. Koska kurssit Koodausteoria ja Informaatioteoria luennoidaan erikseen ja jälkimmäinen ei suinkaan pelkästään ole tarkoitettu tukemaan edellistä, on informaatioteorian osuus kirjoitettu paljolti erilleen koodausteoriasta, toisin kuin monissa kirjoissa. Itseopiskelijalle suositellaan monisteen ohella käytettäväksi joitain runsaasti esimerkkejä sisältäviä kirjoja (esim. ANDERSON & MOHAN , SWEENEY ja YAGLOM & YAGLOM). Keijo Ruohonen

1

I LUKU LINEAARISET

KOODIT

1. Lohkokoodit Viestiä lähetettäessä on käytössä tietyt symbolit, ns. viestisymbolit. Viesti jaetaan tasapituisiin osiin, ns. lohkoihin eli viestisanoihin. Koodattaessa kukin viestin lohko korvataan ns. koodisymboleista muodostetulla koodisanalla. Kahta eri lohkoa ei saa vastata sama koodisana, mikä takaa koodatun viestin dekoodautuvuuden. Usein koodisymbolit ovat samat kuin viestisymbolit. Jos kaikki koodisanat ovat samanpituisia, on kyseessä ns. lohkokoodi. Yhteinen koodisanojen pituus on ns. koodin pituus. (Koodausteoria käyttää nimenomaan lohkokoodeja.) Kaikki koodisanat muodostavat joukkona koodin. Jos koodisymboleja on kaksi (yleensä bitit 0 ja 1) puhutaan binäärikoodista. Koodauksen tarkoitus on saada aikaan mahdollisuus dekoodattaessa paljastaa ja korjata tietty määrä tiedonsiirrossa tai -talletuksessa syntyviä virheitä koodisanaa kohti. Jatkossa merkitään viesti- ja koodilohkoja lihavalla: Esimerkiksi m = m1m 2⋅⋅⋅m k on viestisana, jonka symbolit ovat m1,m2,…,mk ja jonka pituus on k. Viestisanojen pituutta merkitään jatkossa useimmiten k:lla ja koodin pituutta n:llä. Luku n – k on ns. redundanssi.

ESIMERKKI. Yksinkertainen tapa saada aikaan virheiden paljastamis/korjaamiskyky on käyttää toistokoodausta. Tällöin viestisanaa m vastaava koodisana on c = m r = m1m 2 Lm k Lm1m 2 Lm k . 1444442444443 r kertaa

Tällainen koodaus pystyy joko paljastamaan r – 1 virhettä tai korjaamaan (r – 1)/2 virhettä. Jos siis r = 2, voidaan yhden virheen esiintyminen havaita, mutta sitä ei pystytä korjaamaan.

2 Kahden koodisanan c1 ja c2 ns. (Hamming-)etäisyys d(c1,c2) on niissä olevien erojen lukumäärä. Koodin C ns. minimietäisyys, merkitään dmin(C ), on pienin esiintyvä kahden eri koodisanan etäisyys.

E SIMERKKI . Jos binäärikoodin koodisymbolit ovat bitit 0 ja 1, niin koodisanojen c 1 = 001001100 ja c 2 = 101101100 etäisyys on d(c 1 ,c 2 ) = 2. Koodin pituus on tässä 9.

ESIMERKKI. Valitaan toistokoodauksessa viestisymboleiksi 0 ja 1, viestisanan pituudeksi 3 ja vielä r = 3. Saadun binäärikoodin C pituus on 9, koodisanoja on 23 = 8 kpl ja dmin(C ) = 3. Koodia on tapana ajatella “geometrisesti” pistejoukkona kaikkien mahdollisten koodisymboleista muodostettujen n:n (= koodin pituus) pituisten sanojen muodostamassa “avaruudessa”. Etäisyys d on geometrisen vastineensa kaltainen sikälikin, että se noudattaa kolmioepäyhtälöä, ts. d(c 1 ,c 2 ) ≤ d(c 1 ,c 3 ) + d(c 3 ,c 2 ) (helppo todeta). Jos c on koodisana, niin c-keskinen R-säteinen pallo on B(c,R) = {d d(c,d) ≤ R}. Seuraava perustulos on aivan yksinkertaisesti pääteltävissä:

L AUSE 1.

(i)

Koodi C korjaa t virhettä tarkalleen silloin, kun d min (C ) ≥ 2t + 1 (eli silloin, kun koodisanakeskiset t-säteiset pallot eivät leikkaa toisiaan).

(ii)

Koodi C paljastaa s virhettä tarkalleen silloin, kun d min (C ) ≥ s + 1 (eli silloin, kun mikään koodisana ei ole toisen koodisanan s-säteisessä pallossa). ■

HUOM! Jos koodin C halutaan samanaikaisesti korjaavan t virhettä ja paljastavan s virhettä, tarvitaan toisenlainen ehto. Tietysti s ≥ t. (Eo. Esimerkissä oleva 9-pituinen toistokoodi ei ilmeisestikään pysty yhtaikaiseen yhden virheen korjaamiseen ja kahden virheen paljastukseen.) Geometrisesti esitettynä ehto on seuraava: Jokaiselle koodisanalle c ∈ C jokaisen toisen C :n koodisanan etäisyys pallon B(c,s) sanoista on suurempi kuin t. Kolmioepäyhtälöä käyttäen voi todeta, että tämä on sama kuin ehto d min (C ) ≥ t + s + 1 (jätetään lukijalle). Koodi C on täydellinen t virhettä korjaava koodi, jos

3 (1)

d min(C ) ≥ 2t + 1 (ks. Lause 1i) ja

(2)

Uc∈C B(c,t ) käsittää kaikki koodiaakkoston sanat, ts. jokai-

nen koodiaakkoston sana kuuluu johonkin koodisanakeskiseen t-säteiseen palloon.

Täydellinen (t virhettä korjaava) koodi toimii “ekonomisesti”, mutta se korjaa väärin tilanteet, joissa lohkossa on virheitä enemmän kuin t kpl. Pyyhkiymä on virhe, jossa symbolin paikalle ei tule toinen symboli, vaan symboli katoaa kokonaan. Näin ollen pyyhkiymien kohdat ovat välittömästi saatavissa, mutta eivät pois pyyhkiytyneet symbolit. Aivan ilmeisesti koodi C korjaa p pyyhkiymää tarkalleen silloin, kun d min (C ) ≥ p + 1. Yleisemmin koodi C korjaa p pyyhkiymää ja t “tavallista” virhettä tarkalleen silloin, kun d min (C ) ≥ 2t + p + 1.

2. Ekskursio: Alkukunnat Lineaarisen koodin koodisanat käsitetään symboliensa muodostamiksi vektoreiksi (jotka vielä muodostavat lineaarisen aliavaruuden). Jotta tällainen olisi mahdollista, pitää koodisymboleille määritellä “tutut” laskutoimitukset +, –, × ja / siten, että tavalliset laskusäännöt pitävät paikkansa. Jos joukossa F on määritelty yhteenlasku + ja kertolasku × sekä nolla-alkio 0 ja ykkösalkio 1 siten, että

(1)

+ ja × ovat liitännäiset sekä vaihdannaiset,

(2)

osittelulait pätevät,

(3)

jokaisella alkiolla a on vasta-alkio –a, ts. a + (–a) = 0 ,

(4)

jokaisella muulla alkiolla a paitsi 0 :lla on käänteisalkio a–1, ts. a × a–1 = 1 , ja

(5)

0 ja 1 “käyttäytyvät” kuten pitää, ts. a + 0 = a ja a × 1 = a, (ja lisäksi vielä 1 ≠ 0 ) ,

niin näillä laskuoperaatioilla varustettuna F on ns. kunta. Tuttuja kuntia ovat reaalilukujen kunta R, rationaalilukujen kunta Q ja kompleksilukujen

4 kunta C. Nämä ovat kuitenkin äärettömiä eivätkä tule kysymykseen koodisymbolien joukkoina. Koodisymbolien joukoksi sopivan kunnan pitääkin olla joukkona äärellinen, ns. äärellinen kunta eli Galois’n kunta. Yksinkertaisia äärellisiä kuntia ovat ns. alkukunnat eli jäännösluokkien modulo alkuluku p muodostamat kunnat (p = 2,3,5,7,…). Merkitään Zm:llä jäännösluokkia modulo m. Zm:n alkiot ovat 0 = { kmk = 0,±1,±2,… }, 1 = { km + 1k = 0,±1,±2,… }, 2 = { km + 2k = 0,±1,±2,… }, ⋅⋅⋅ m – 1 = { (k + 1)m – 1k = 0,±1,±2,… }.

Jäännösluokkaa i voidaan merkitä ja se voidaan antaa minkä tahansa edustajansa avulla, ts. i = km + i. Erityisesti 0 = m ja –1 = m – 1. Laskuoperaatiot määritellään nyt seuraavasti: i+ j=i+ j

ja

i × j = ij.

On helppo todeta, että operaatiot on näin hyvin määritelty eli tulos ei riipu siitä mitkä edustajat i ja j jäännösluokista valitaan. Nolla-alkio on luonnollisesti 0 ja ykkösalkio 1 , edelleen – i = – i. Yleisesti 0 :n lisäksi Z m :ssä voi olla muitakin alkioita, joilla ei ole käänteisalkiota. Jos m = p on alkuluku, niin muilla kuin 0 :lla on kuitenkin aina käänteisalkio (ks. kurssi 73265 Symbolinen analyysi 1). Näin saadut kunnat Zp eli GF(p) ovat ns. alkukunnat. E SIMERKKI. Yksinkertaisin alkukunta on binäärikunta Z 2 eli GF(2), jonka alkioita 0 ja 1 voidaan pitää bitteinä 0 ja 1. Laskuoperaatiot saadaan tauluista + 0 1

0 0 1

1 1 0

ja

× 0 1

0 0 0

1 0 1

Kaikki “tavalliset” lineaarialgebran käsitteet kuten vektorit ja matriisit sekä näiden laskuoperaatiot*, determinantit, ortogonaalisuus, lineaarinen riippumattomuus ja riippuvuus, dimensio, kanta, vektorijoukon virittämä aliavaruus ja sen ortogonaalinen komplementti, matriisin rangi ym. voidaan nyt määritellä vektoreille, joiden alkiot ovat jonkin alkukunnan al*

Koodausteoriassa vektorit kirjoitetaan yleensä vaakavektoreiksi v = (v1 ,…,vn) ja vektori kerrotaan matriisilla oikealta.

5 kioita. (Huomaa kuitenkin, ettei vektorien pistetulolla varsinaisesti ole mitään tekemistä vektorien välisen “kulman” kanssa, eikä ominaisarvoja ja -vektoreita yleisesti tarvita.) Koska nämä käsitteet ovat tuttuja peruskursseilta reaalilukukunnan tapauksessa ja ovat alkukuntien tapauksessa hyvin samankaltaisia, ei niitä tässä sen tarkemmin määritellä. Kaikkien (alku)kunnan F alkioista muodostettujen n-ulotteisten vektorien joukkoa merkitään F n:llä. HUOM! On muitakin äärellisiä kuntia kuin alkukunnat ja näitäkin tarvitaan tehokkaissa koodausmenetelmissä. Asiaan palataan myöhemmin III.1:ssä.

3. Lineaariset koodit Kun koodisymbolien joukoksi valitaan alkukunta F (tai yleisesti äärellinen kunta), voidaan sanat ja vektorit täydellisesti samaistaa: c = c1 c 2 ⋅⋅⋅c n = (c1 ,c2 ,…,c n ). Koodia C ⊆ Fn sanotaan lineaariseksi koodiksi, jos se on Fn:n lineaarinen aliavaruus, ts.

(i)

jos c 1 ja c 2 ovat koodisanoja, niin samoin on c 1 + c 2 (vektorien yhteenlasku) ja

(ii)

jos c on koodisana ja f on kunnan F alkio, niin fc on koodisana.

Näin ollen nollavektori 0 on aina lineaarisen koodin koodisana ja samoin on kunkin koodisanan c vastavektori –c. (Huomaa, että alkukunnille F ehto (ii) seuraa (i):stä ja on siis itse asiassa tarpeeton, sillä jos i on positiivinen kokonaisluku, niin ic = c+L+c 1 424 3.) i kpl

Lineaarista koodia, jonka pituus on n ja dimensio k (lineaarisena aliavaruutena), sanotaan (n,k)-koodiksi. Vektorin v Hamming-pituus eli Hamming-paino w(v) on siinä olevien nollaalkiosta 0 eroavien komponenttien lukumäärä. Näin ollen d(v 1 ,v 2 ) = w(v 1 – v 2 )

ja

w(v) = d(v,0)

ja lineaarisen koodin C minimietäisyys dmin (C ) on pienin positiivinen koodisanan paino.

6 E SIMERKKI . F:n alkioita symboleina käyttäen muodostetut toistokoodit ovat lineaarisia.

Koska lineaarinen koodi C on lineaarinen aliavaruus, sillä on kanta g1,g2,…,gk (itse asiassa tietysti useampiakin kantoja, mutta ei äärettömän monta). Koodisanan c valinta tarkoittaakin sen kantaesityksessä tarvittavien lineaariyhdelmän c = d1 g 1 + d2 g 2 +⋅⋅⋅+ dk g k kerrointen d1 ,d 2 ,…,d k valintaa. Koodattaessa pitää siis kutakin viestisanaa m kohti määrittää vastaavan koodisanan kantaesityksen kertoimet. Yksinkertaisesti tämä käy, mikäli valitaan viestisymbolien joukoksi myös F ja kertoimiksi viestisymbolit itse. Jos siis viestisana on m = m1m 2⋅⋅⋅m k = (m1,m 2,…,m k), niin koodauksessa tulee sitä vastaamaan koodisana c = m1g1 + m2g2 +⋅⋅⋅+ mkgk. Huomaa, että viestisanoja on nyt tarkalleen yhtä paljon kuin koodisanoja, ts. qk kpl, missä q on kunnan F alkioiden lukumäärä. Valitsemalla eri kantoja saadaan erilaisia koodauksia. Viestisanat muodostavat viestiavaruuden Fk ja koodaus voidaan käsittää lineaarikuvaukseksi Fk:lta C :lle. Tällainen lineaarikuvaus voidaan suorittaa matriisia, ns. generoijamatriisia, käyttäen: c = mG, missä  g1   g11 g12 L g1n  g g g L g 2n  G =  2  =  21 22 .  M   M M O M   g k   g k1 g k2 L g kn 

Matriisin G (oikea) nolla-avaruus muodostuu niistä vektoreista h, joille Gh T = 0 kT . Tunnetusti nolla-avaruus on Fn:n lineaarinen aliavaruus, ja sen dimensio on n – k. Näin ollen nolla-avaruudessa on qn – k vektoria. Valitaan nolla-avaruuden kanta h1,h2,…,hn – k ja muodostetaan niistä matriisi  h1   h11 h h H =  2  =  21  M   M     h n– k   h n– k,1

h12 h 22 M h n– k,2

L L O L

h1n  h 2n ,  M h n– k,n 

7 ns. tarkistusmatriisi. (Valitusta kannasta riippuen mahdollisia tarkistusmatriiseja on useita.) Silloin GH T = O k×(n – k) ja

HG T = O (n – k)×k.

g1,g2,…,gk puolestaan muodostavat näin H:n nolla-avaruuden kannan ja mainittu nolla-avaruus on siis C . Näin ollen koodisanat ovat tarkalleen ne sanat c, jotka toteuttavat ns. tarkistusyhtälön cH T = 0n – k. Tämä onnistuu with(linalg)):

Maple -ohjelmistollakin (ensin annetaan latauskäsky

> G:=array([[1,0,1,1,0],[0,1,1,0,1],[1,1,1,1,1],[0,0,0,0,0],[0,0,0,0,0]]);  1 0 1 1 0  0 1 1 0 1   G :=  1 1 1 1 1  0 0 0 0 0  0 0 0 0 0 > Nullspace(G) mod 2;

{ [ 1, 0, 0, 1, 0 ], [ 0, 1, 0, 0, 1 ] }

Dekoodaus olisi helppoa, jos pitäisi vain löytää kutakin koodisanaa vastaava viestisana, mutta dekoodauksessa pitää myös korjata tai paljastaa haluttu määrä syntyneitä virheitä. Jos saatu (mahdollisesti) virheellinen sana on r ja vastaava koodisana c, niin e = r – c on virhesana eli virhevektori. Virheiden lukumäärä on virhesanan paino w(e). Dekoodauksen tarkoitus on löytää virhesana, jolloin oikea koodisana c saadaan välittömästi r:stä: c = r – e. Binäärikoodin tapauksessa riittää itse asiassa löytää vain virhekohdat. Dekoodauksessa on usein käyttökelpoinen saadun sanan r = c + e (koodisana + virhesana), ns. syndromi s = rH T = (c + e)H T = eH T . Koodisanan syndromi on aina 0 ja vastaanotetun sanan r syndromi on sama kuin virheen e syndromi. Näin ollen syndromi sisältää koodisanasta c riippumatonta tietoa virheestä e.

A PULAUSE. Jos jonkin koodisanan paino on d, niin tarkistusmatriisissa H on d lineaarisesti riippuvaa saraketta. Todistus. Valitaan koodisana c = (c1 ,…,c n ), jonka paino on d. Näin ollen c:ssä on tarkalleen d nolla-alkiosta eroavaa komponenttia ci1 ,…,cid . Koska c on koodisana, on cHT = 0n – k. ■

8 L AUSE 2. Lineaarisen koodin C minimietäisyys on vähintään d tarkalleen silloin, kun mitkä tahansa d – 1 tarkistusmatriisin H saraketta ovat lineaarisesti riippumattomat. Todistus. Jos dmin(C ) ≥ d, niin mitkään d – 1 tarkistusmatriisin H eri saraketta f iT1 ,…,f iTd–1 eivät voi olla lineaarisesti riippuvat. Muussa tapauksessa olisi sellaiset kertoimet ci1 ,…,c id – 1 , jotka kaikki eivät ole nolla-alkioita, että ci1 fi1 +⋅⋅⋅+ cid – 1f id – 1 = 0 n – k ja näin ollen sellainen koodisana c ≠ 0, että w(c) ≤ d – 1. Jos taas mitkä tahansa d – 1 tarkistusmatriisin H saraketta ovat lineaarisesti riippumattomat, niin Apulauseen nojalla d min (C ) ≥ d. ■

4. Systemaattinen koodaus Jos generoijamatriisi on muotoa G = ( I k P ), missä I k on k×k-identiteettimatriisi ja P on k×(n – k)-matriisi, kyseessä on ns. systemaattinen koodaus. Systemaattisessa koodauksessa k ensimmäistä symbolia muodostavat viestisanan ja loput symbolit ovat tarkistussymboleja. (Usein tosin toisin päin, ks. II.4.) HUOM! Binäärikunnan Z2 tapauksessa tarkistus on ns. pariteetintarkistus ja puhutaan pariteetintarkistusmatriisista, pariteetintarkistussymboleista, jne.. L AUSE 3. Jos lineaarisen koodin generoijamatriisi on G = ( I k P ) (systemaattinen koodaus), niin H = – P T I n– k on vastaava tarkistusmatriisi. Vastaavasti, jos lineaarisen koodin tarkistusmatriisi on H = ( Q I n– k ) , niin G = I k – Q T on vastaava (systemaattinen) generoijamatriisi.

(

(

)

)

Todistus. Näytetään vain ensimmäinen toteamus (toinen menee vastaavasti). H on (n – k)×n-matriisi, jonka vaakarivit ovat lineaarisesti riippumattomat. Edelleen –P  GH T = ( I k P ) I = – P + P = O k×(n– k) .  n– k 

■

E SIMERKKI . Toistokoodin (ks. Esimerkki s. 1) generoijamatriisi on G = ( I k I k L I k ). 1442443 r kpl

Kyseessä on systemaattinen koodaus. Lauseen 2 mukaan vastaava tarkistusmatriisi on

9  – Ik  – Ik  H= I n– k  .  M   – Ik  (Koska n = rk, niin n – k = (r – 1)k.)

5. Standardidekoodauskaavio Joukkoja

e + C = { e + c c ∈ C },

missä e on mielivaltainen virhesana, kutsutaan sivuluokiksi. Sivuluokka e + C sisältää ne sanat, joiksi virhe e muuntaa koodisanat. Erityisesti C = 0+C.

A PULAUSE . Jos kahden sivuluokan leikkaus ei ole tyhjä, niin ne ovat samat. Todistus. Jos (e1 + C ) ∩ (e2 + C ) ei ole tyhjä, niin on olemassa sana e1 + c1 = e2 + c2, missä c 1 ,c 2 ∈ C . Näin ollen e 1 ∈ e 2 + C ja e 2 ∈ e 1 + C , joten sivuluokat sisältyvät toisiinsa ja ovat siis samat. ■ Jokainen sana v ∈ Fn kuuluu johonkin sivuluokkaan ja sivuluokat ovat samankokoiset. Näin ollen sivuluokassa on qk sanaa ja sivuluokkia on qn – k kpl (eli sama määrä kuin generoijamatriisin nolla-avaruuden alkioita). (q on F:n alkioluku.) Standardidekoodauskaavio muodostetaan seuraavalla tavalla:

(1)

Järjestetään koodisanat jonoksi aloittaen 0:sta: c1 = 0,c2,c3,…,cqk . Näin saadaan kaavion ensimmäinen rivi. (2)

Etsitään kustakin sivuluokasta painoltaan pienin alkio (mahdollisuuksia voi olla useita). Näin saadaan ns. sivuluokkien johtajat e1 = 0,e2,e3,…,eqn – k.

10 Näistä muodostetaan kaavion ensimmäinen sarake. (C :n johtaja on tietysti 0.) (3)

Kaavion i:nnen rivin ja j:nnen sarakkeen alkio on ei + cj.

ESIMERKKI. Binäärikoodin C (kaavion ylin rivi) standardidekoodauskaavio on johtaja 00000 10000 00001 10001

10010 00010 10011 00011

01010 11010 01011 11011

sivuluokka 00101 11000 10111 10101 01000 00111 00100 11001 10110 10100 01001 00110

01111 11111 01110 11110

11101 01101 11100 01100

Standardidekoodauskaaviota käytetään dekoodauksessa seuraavasti: Etsitään kaaviosta saatu sana r ja dekoodataan se vastaavan sarakkeen ylimmäksi sanaksi c ∈ C . Tulos on luonnollisesti vastaava oikea viestisana vain siinä tapauksessa, että virhe e oli r:n sisältävän sivuluokan johtaja. Menettely on näin käyttökelpoinen lähinnä vain binäärikoodien tapauksessa ja silloin, kun sivuluokkien johtajiksi on saatu “edustava” kokoelma virheitä. Täydellinen kaavio sisältää qn – k riviä ja qk saraketta, mikä on yleensä liian paljon. Syndromeja käyttäen saadaan tilantarvetta pienennettyä. Sivuluokan alkioilla on nimittäin sama syndromi ja eri sivuluokkien alkioilla eri syndromit, kuten helposti voi todeta. Koska saadusta sanasta r on helposti laskettavissa sen syndromi s = rH T , riittää muodostaa syndromien luettelo ja liittää kuhunkin syndromiin vastaavan sivuluokan johtaja. Dekoodattaessa lasketaan ensin saadun sanan r syndromi s ja etsitään luettelosta vastaava sivuluokan johtaja e. r dekoodataan sitten r – e:ksi. Tämäkään menettely ei ole kovin käyttökelpoinen, jos n – k on suuri.

6. Hamming-koodit Tarkistusmatriisi määrittelee lineaarisen koodin siinä kun generoijamatriisikin. Lauseen 2 nojalla lineaarisen koodin C minimietäisyys on vähintään 3 tarkalleen silloin, kun sen tarkistusmatriisin H mitkään kaksi saraketta eivät ole lineaarisesti riippuvat. Lineaarinen koodi on Hammingkoodi, jos sen tarkistusmatriisi sisältää suurimman mahdollisen määrän parittain lineaarisesti riippumattomia sarakkeita eli suurimman mahdollisen määrän sarakkeita, joita ei saada toisistaan vakiolla (eli kunnan F alkiolla) kertomalla. Paljonko sitten Hamming-koodin tarkistusmatriisissa on sarakkeita? Ilmeisesti voidaan olettaa, että kunkin sarakkeen ylhäältälukien ensimmäinen nolla-alkiosta eroava alkio on ykkösalkio. Sarakkeita, joissa ylin alkio on ykkösalkio, on selvästi qn – k – 1 kpl (q on kunnan F alkioluku). Edelleen sarakkeita, joiden ylin alkio on nolla-alkio ja toiseksi ylin alkio ykkösalkio, on qn – k – 2 kpl, jne.. Kaiken kaikkiaan sarakkeita on siis

11 qn – k – 1 qn – k – 1 + qn – k – 2 +⋅⋅⋅+ q + 1 = =n q – 1 kpl. Merkitään n – k = r. Silloin Hamming-koodin pituus ja viestisanan pituus ovat qr – 1 n= q – 1

ja

k=

qr – 1 – r. q – 1

Samalla tuli esille eräs tapa muodostaa Hamming-koodin tarkistusmatriisi H, joka ei ole sen huonompi kuin muutkaan. Voidaankin olettaa, että H saadaan juuri tällä tavalla. Vastaavan generoijamatriisin saa vaikkapa käyttämällä Lausetta 3. Huomaa, että H:ssa on mukana kaikki r sellaista saraketta, joissa yksi alkioista on ykkösalkio ja muut nolla-alkioita, ts. koodaus on olennaisesti systemaattinen. Näin ollen H kannattaa kirjoittaa muotoon H = Q T I r . Triviaalien tapausten poissulkemiseksi oletetaan, että n ≥ 3.

(

)

Kuten todettiin, Lauseesta 2 seuraa, että Hamming-koodin minimietäisyys on ainakin 3. Itse asiassa se on tarkalleen 3, sillä yo. tavalla saatu H sisältää aina lineaarisesti riippuvat kolme saraketta  1  1  0  0  1  1  0 , 0 , 0 .  M   M   M   0  0  0

LAUSE 4. Hamming-koodi on täydellinen yhden virheen korjaava koodi. Todistus. 1-säteiset koodisanakeskiset pallot ovat erilliset ja niitä on qk kpl. Kussakin tällaisessa pallossa on ilmeisesti n(q – 1) + 1 alkiota. Siispä mainituissa palloissa on yhteensä qk(n(q – 1) + 1) = qn alkiota eli ne peittävät koko Fn:n. ■ Yhden virheen korjaava dekoodaus Hamming-koodilla on helppoa. Jos saadussa sanassa r = c + e on yksi virhe, ts. e = aei, missä e i on vektori, jonka i:s alkio on ykkösalkio ja muut nolla-alkioita, niin syndromi on s = eH T = ae iH T = afi, missä f iT on H:n i:s sarake. Koska H:n sarakkeet ovat erilaisia, paljastuu näin syndromista virheen paikka i ja virhe a (= ensimmäinen s:n nolla-alkiosta eroava komponentti). Dekoodaus tuottaa oikean koodisanan

12 c = r – aei. Jos taas syndromi on 0, ei virhettä ole tapahtunut eikä mitään korjausta tarvita. E SIMERKKI. Binäärisen Hamming-koodin pituus on n = 2r – 1 ja viestisanan pituus k = 2r – r – 1. Näin ollen binäärinen Hamming-koodi o n (2 r – 1,2r – r – 1)-koodi. Pariteetintarkistusmatriisin H sarakkeina esiintyvät kaikki 2r – 1 kpl r:n pituisia bittivektoreita paitsi nollavektori. Jos nämä kirjoitetaan H:ssa sellaiseen järjestykseen, että i:nnen sarakkeen bitit muodostavat luvun i binääriesityksen, on dekoodaus todella helppoa: Syndromi nimittäin on virheen paikan binääriesitys! (Itse virhe on ilmeinen, sillä virheen sattuessa 0 vaihtuu 1:ksi tai 1 vaihtuu 0:ksi.) Valitettavasti vain H ei tällöin ole muotoa Q T I r ja generoijamatriisin etsiminen ei mene aivan suoraan Lausetta 3 käyttäen. Systemaattinen koodaus saadaan kuitenkin myös pariteetintarkistusyhtälöä käyttäen. Yhtälöstä cHT = 0 r voidaan nimittäin ratkaista esimerkiksi ck + 1,…,cn lausuttuna ensimmäisten koodisymbolien c1,…,ck avulla. Näin voidaan c1c2⋅⋅⋅ck valita viestisanaksi m ja loput koodisymbolit ovat pariteetintarkistussymboleja. Esimerkiksi valitaan r = 3, jolloin saadaan (7,4)-Hamming-koodi ja pariteetintarkistusmatriisi on

(

)

 0 0 0 1 1 1 1 H =  0 1 1 0 0 1 1 .  1 0 1 0 1 0 1 Ratkaistaan yhtälö cHT = 03 kin):

Maplella (näin pieni menisi toki käsipelissä-

> solve({c4+c5+c6+c7=0,c2+c3+c6+c7=0,c1+c3+c5+c7=0},{c5,c6,c7}): > " mod 2; { c6 = c4 + c1 + c3, c7 = c2 + c4 + c1, c5 = c3 + c2 + c4 }

Systemaattisessa koodauksessa valitaan c1c2c3c7 = m ja loput koodisymbolit lasketaan näistä yhtälöistä. (Menettelyä voi käyttää myös muille kuin binäärisille Hamming-koodeille.) Binäärisiä Hamming-koodeja ja niiden variantteja käytetään paljon tiedon talletuksessa, ks. RAO & FUJIWARA.

13

I I LUKU SYKLISET

KOODIT

1. Syklinen koodi Lineaarinen koodi on syklinen, jos aina kun c1⋅⋅⋅cn – 1cn on koodisana, niin samoin on cn c 1 ⋅⋅⋅c n – 1. Syklisen koodin koodisanan c1 ⋅⋅⋅c n – 1c n kaikki sykliset siirrot cn – i⋅⋅⋅c n c 1 ⋅⋅⋅c n – i – 1 (i = 0,…,n – 2) ovat näin ollen myös koodisanoja. Syklinen koodi on luonnollinen valinta, mikäli koodausta ajatellaan operaationa, joka toteutetaan lineaarisen järjestelmän avulla. Koodisana c = c1c2⋅⋅⋅cn samaistetaan paitsi vektoriin (c1,c2,…,cn) myös sen (äärelliseen) z-muunnokseen c(z) = c1 + c2 z +⋅⋅⋅+ cn z n – 1. c(z) on formaalinen* enintään astetta n – 1 oleva z:n polynomi, ns. koodipolynomi, jonka kertoimet ovat kunnan F alkioita. Koodaus “taajuustasolla” tapahtuu kertomalla viestin (äärellinen) z-muunnos m(z) “siirtofunktiolla” g(z), joka sekin on formaalinen enintään astetta n – 1 oleva z:n polynomi, ns. generoijapolynomi. Jottei asteluku nousisi yli sallitun n – 1:n, pitää tulosta vielä redusoida korvaamalla zn jokaisessa esiintymässään 1 :llä, ts. merkitsemällä zn – 1 = 0 . Asia on parhaiten esitettävissä polynomialgebraa käyttäen.

2. Ekskursio: Polynomirenkaat ja äärellinen z-muunnos Algebrallisena käsitteenä rengas määritellään samaan tyyliin kuin kunta (ks. I.2), mutta jättäen pois joitain vaatimuksia. Jos joukossa M on määritelty yhteenlasku + ja kertolasku × sekä nolla-alkio 0 ja ykkösalkio 1 siten, että *

Formaalinen polynomi ei ole sama kuin sen antama polynomikuvaus. Esimerkiksi polynomin 1 + z + z2 antama Z2 :n kuvaus on vakiofunktio 1.

14 (1)

+ ja × ovat liitännäiset sekä vaihdannaiset,

(2)

osittelulait pätevät,

(3)

jokaisella alkiolla a on vasta-alkio –a, ts. a + (–a) = 0 , ja

(4)

0 ja 1 “käyttäytyvät” kuten pitää, ts. a + 0 = a ja a × 1 = a,

niin näillä laskuoperaatioilla varustettuna M on ns. rengas.

H UOM ! Tarkemmin sanoen tällainen M on ns. vaihdannainen 1-rengas, varsinainen rengas on algebrallisesti vieläkin yleisempi käsite. Ks. kurssi 73115 Algebra 1. Jatkossa renkaasta puhuttaessa kyseessä on siis aina juuri tällainen vaihdannainen 1-rengas.

Jokainen kunta on myös rengas. Tuttuja renkaita, jotka eivät ole kuntia, ovat mm. kokonaislukujen rengas Z sekä erilaiset polynomirenkaat, esimerkiksi rationaali-, reaali-, kompleksi- ja kokonaiskertoimisten polynomien renkaat Q[z], R[z], C[z] ja Z[z]. Myös Zm eli jäännösluokat modulo m muodostavat renkaan. Polynomit, jotka muodostetaan formaalisesti käyttäen kunnan F alkioita kertoimina, muodostavat ns. F:n polynomirenkaan F[z]. Koodausteoriassa tarvitaan nimenomaan äärellisten kuntien polynomirenkaita. Tavalliseen tapaan F[z]:n nollapolynomi samaistetaan F:n nolla-alkioon 0 ja vakiopolynomit vastaaviin F:n alkioihin. Polynomin p(z) aste deg(p(z)) määritellään edelleen tavalliseen tapaan korkeimman esiintyvän z:n potenssin eksponentiksi. Nollapolynomin asteeksi voidaan sopia vaikkapa –1. Kunnan polynomirenkaan polynomeille a(z) ja b(z) ≠ 0 on määritelty yksikäsitteinen osamäärä q(z) ja jakojäännös j(z), ts. voidaan kirjoittaa a(z) = q(z)b(z) + j(z),

deg ( j(z) ) < deg( b(z) ) .

(Käytännössä tällainen jakolasku voidaan suorittaa “pitkänä jakolaskuna” paperilla, myös esimerkiksi Maple-ohjelmisto osaa jakaa polynomeja äärellisissä kunnissa.) j(z):n sanotaan olevan a(z):n jäännös modulo b(z), merkitään a(z ), vrt. vastaava käsite kokonaisluvuille I.2:ssa. b(z) on ns. moduli. Kaikki jäännökset modulo b(z) muodostavat ns. jäännösluokkarenkaan eli tekijärenkaan F[z]/〈b(z)〉. On helppo nähdä, samaan tapaan kuin kokonaisluvuille, että jäännökset modulo b(z) voidaan voidaan antaa ja niillä voidaan laskea “edustajan välityksellä”, ts. a1 (z ) + a 2 (z ) = a1 (z ) + a 2 (z ) ja a1 (z ) × a 2 (z ) = a1 (z )a 2 (z ). (Jakojäännöstä j(z) vastaavan jäännösluokan edustajia ovat ne polynomit a(z), joiden jäännös modulo b(z) on j(z). Jäännösluokka voidaan myös sa-

maistaa edustajiensa muodostamaan joukkoon.) Näin ollen F[z]/〈b(z)〉 on todellakin rengas. Vektorin v = (v1,v2,…,vn) ∈ Fn äärellinen z-muunnos on F[z]:n polynomi v(z) = v1 + v2z +⋅⋅⋅+ vnzn – 1, mutta samaistettuna jäännösluokkaan modulo S(z) = zn – 1 . Itse asiassa äärelliset z-muunnokset ovat siis jäännösluokat modulo zn – 1 ja niillä lasketaan redusoiden aina zn ykkösalkioksi, sillä z n – 1 = 0 eli z n = 1 .

3. Syklinen koodi polynomi-ihanteena Ellei sekaannusta satu, ts. deg(v(z)) < n, samaistetaan polynomi v(z), sen edustama jäännösluokka v(z ), vektori v = (v1,v2,…,vn) ja sana v = v1v2⋅⋅⋅vn täysin. Koodisanan c(z) = c1 +⋅⋅⋅+ cn – 1z n – 2 + cn z n – 1 syklinen siirto tapahtuu silloin z:lla eli koodisanalla 0 1 0L0 kertomalla: zc(z ) = cn + c1z +⋅⋅⋅+ cn – 1zn – 1. Joukkoa

〈 f(z) 〉 = { v(z )f (z ) v(z) ∈ F[z]/〈S(z)〉 } kutsutaan f(z):n generoimaksi ihanteeksi eli ideaaliksi. Huomaa. että tällainen ihanne on kaikkien niiden tulosten joukko, jotka saadaan operoimalla “siirtofunktiolla” f(z) äärellisiin z-muunnoksiin v(z). Aivan ilmeisesti koodina 〈 f(z)〉 on syklinen koodi, mutta f(z) ei (välttämättä) ole sen generoijapolynomi.

L AUSE 5. Koodi on syklinen n-pituinen koodi täsmälleen silloin, kun se on muotoa

{ v(z)g(z) v(z) ∈ F[z]/〈 S(z)〉 , deg(v(z)) < n – deg(g(z)) } = 〈 g(z)〉 , missä g(z) on S(z):n (eli zn – 1 :n) tekijä, ns. generoijapolynomi. Todistus. Todetaan ensin, että

{ v(z)g(z) v(z) ∈ F[z]/〈 S(z)〉 , deg(v(z)) < n – deg(g(z)) } todellakin on tällöin g(z):n generoima ihanne 〈g(z)〉 ja näin ollen syklinen koodi. Aivan ilmeisesti se sisältyy mainittuun ihanteeseen 〈g(z)〉. Jos g(z) on S (z):n tekijä, voidaan kirjoittaa S (z) = g (z)h (z) ja deg( h (z) ) = n –

15

deg(g(z)). Valitaan mielivaltainen v(z) ∈ F[z]/〈S(z)〉, tulkitaan se F[z]:n polynomiksi ja jaetaan h(z):lla: v(z) = q(z)h(z) + j(z), deg( j(z) ) < n – deg( g(z) ) . Modulo S(z) on v(z)g(z) näin ollen sama kuin j(z)g(z) ja v(z):n asteen voidaan siis olettaa olevan pienempi kuin n – deg(g(z)). Oletetaan sitten, että C on syklinen koodi ja valitaan sen asteeltaan pienin nollapolynomista eroava koodipolynomi g(z). Syklisyydestä ja lineaarisuudesta johtuen myös polynomit v(z )g(z ), v(z) ∈ F[z]/〈 S(z)〉 , ovat koodipolynomeja, sillä jos v(z) = v1 + v2z +⋅⋅⋅+ vnzn – 1, niin v(z)g(z) = v1 g(z) + v2 zg(z) +⋅⋅⋅+ vn z n – 1g(z). Jaetaan S(z) g(z):llä: S(z) = q(z)g(z) + j(z),

deg( j(z) ) < deg( g(z) ) .

Modulo S(z) on j(z) näin ollen sama kuin –q(z)g(z) ja on siis koodipolynomi. g(z):n asteen minimaalisuudesta johtuen pitää j(z):n olla nollapolynomi, jolloin g(z) on S(z):n tekijä. Samaan tapaan voidaan jakolaskulla todeta, että g(z) on jokaisen C :n koodipolynomin tekijä. C on näin ollen esitettyä muotoa. ■ Syklisen koodin* koodaus voidaan suorittaa generoijapolynomilla g(z) kertomalla, kunhan viestisana m = m1m2⋅⋅⋅mk samaistetaan viestipolynomiksi m(z) = m1 + m2 z +⋅⋅⋅+ mk z k – 1, missä k = n – deg(g(z)): c(z) = m (z)g(z).

E SIMERKKI . Lineaarinen toistokoodi (ks. Esimerkki s. 1) on syklinen ja sen koodaus voidaan suorittaa generoijapolynomilla 1 + zk + z2 k +⋅⋅⋅+ z(r – 1)k. Koska syklisen koodin generoijapolynomi g(z) on S(z):n tekijä, voidaan kirjoittaa S(z) = g(z)h(z), missä h(z) on ns. tarkistuspolynomi. Nimi on sattuva (vrt. tarkistusmatriisi), sillä modulo S(z) on g(z)h(z) näin 0 . Edelleen saadaan *

Muidenkin koodien kuin syklisten koodien koodaus voidaan suorittaa tällä tavoin, mutta koodipolynomit eivät tällöin muodosta lineaarisen järjestelmän koko tulosjoukkoa ja koodaus on tietyssä mielessä tehotonta. Esimerkiksi (lineaarisen) koodin {000,101} koodaus voidaan suorittaa polynomilla 1 + z2 (joka ei ole 1 + z3 :n tekijä).

16

17 L AUSE 6. Jos syklisen koodin tarkistuspolynomi on h(z), niin c(z) on koodipolynomi täsmälleen silloin, kun c(z)h(z) on nollapolynomi modulo S(z). Todistus. Jos c(z) on koodipolynomi, niin se on muotoa m(z)g(z), missä g(z) on tarkistuspolynomia h(z) vastaava generoijapolynomi. Näin ollen tällöin c(z)h(z) = m(z)g(z)h(z) = m(z)S(z) on nollapolynomi modulo S(z). Oletetaan sitten, että c(z)h(z) on nollapolynomi modulo S(z). Jaetaan c(z) generoijapolynomilla g(z): c(z) = q(z)g(z) + j(z),

deg ( j(z) ) < deg( g(z) ) .

Silloin myös j(z)h(z) on nollapolynomi modulo S(z), ts. muotoa p(z)S(z). Mutta astelukuja ajatellen tämä on mahdollista vain, jos j(z) on itse nollapolynomi, jolloin c(z) = q(z)g(z) on koodisana. ■ Yleensä generoijapolynomi g(z) valitaan pääpolynomiksi, ts. siinä valitaan zn – k:n kerroin ykkösalkioksi. Tämä ei mitenkään rajoita tilannetta. Seurauksena myös vastaava tarkistuspolynomi on pääpolynomi. Analogisesti aikaisemmin esillä olleen syndromin määritelmän mukaisesti polynomia r(z )h(z ) = s(z ) kutsutaan saadun sanan r(z) syndromipolynomiksi. Syndromipolynomi määräytyy vain virhesanasta eikä riipu koodisanasta. Jos s(z) ≠ 0 , tiedetään virheen sattuneen. Vaihtoehtoisesti virhe voitaisiin paljastaa jakamalla r(z) g(z):lla, jolloin jakojäännös on syndromipolynomi. Jos jakojäännös ei ole nollapolynomi, tiedetään virheen tapahtuneen. Jos syklisen koodin C 1 generoijapolynomi g1(z) on toisen syklisen koodin C 2 generoijapolynomin g2(z) tekijä, niin C 2 sisältyy C 1:een. Syklistä koodia sanotaankin maksimaaliseksi, jos sen generoijapolynomi g(z) on jaoton, ts. (vakiopolynomien lisäksi) g(z):llä ei ole muita tekijöitä kuin se itse. ESIMERKKI. Valitaan n = 7 ja F = Z 2. Polynomin z7 – 1 eli z7 + 1 jaottomat tekijät ovat 1 + z, 1 + z + z3 ja 1 + z2 + z3, kuten kokeilemalla voi havaita. Nämä kukin generoivat maksimaalisen syklisen koodin. Koodissa 〈1 + z〉 on 26 koodisanaa, 〈1 + z + z3〉:ssa 24 = 16 koodisanaa ja samoin koodissa 〈1 + z2 + z3〉. Kaikki mahdolliset sykliset 7-pituiset binäärikoodit saadaan etsimällä vielä muut generoijapolynomit: (1 + z)(1 + z + z3 ) = 1 + z2 + z3 + z4

((7,3)-koodi),

(1 + z)(1 + z2 + z3 ) = 1 + z + z2 + z4

((7,3)-koodi),

(1 + z + z3 )(1 + z2 + z3 ) = 1 + z + z2 + z3 + z4 + z5 + z6

((7,1)-koodi).

18 Viimemainittu (7,1)-koodi on itse asiassa toistokoodi {0 ,1111111}. Lisäksi voidaan ottaa mukaan “degeneroituneet tapauksetkin” eli valita generoijapolynomeiksi 1 1 + z7

((7,7)-koodi F 7 ), ((7,0)-koodi {0}).

Kaikkiaan näitä koodeja on siis 23 = 8 kpl. Jos zn – 1 :n jako jaottomiin pääpolynomeihin p 1(z),…,p m (z) on zn – 1 = p 1 (z) k 1 ⋅⋅⋅p m (z)k m , niin syklisiä n-pituisia koodeja on (k1 + 1)⋅⋅⋅(km + 1) kpl, kun mukaan luetaan myös “degeneroituneet” koodit F n ja {0} (vrt. yo. Esimerkki). Syklisen koodin koodaus on yleensä helposti digitaalisesti toteutettavissa (onhan se lineaarinen järjestelmä), samoin syndromin lasku. Ks. ANDER SON & MOHAN.

4. Syklisen koodin systemaattinen koodaus Edellisen pykälän koodausmenettely ei ole systemaattinen. Systemaattinen koodaus saadaan kuitenkin vähän muuntaen koodausmenettelyä. Kerrotaan viestipolynomi m(z) ennen koodausta zn – k:lla ja jaetaan se sitten generoijapolynomilla g(z): z n – km (z) = q(z)g(z) + u(z),

deg ( u(z) ) < n – k.

Silloin –u(z) + zn – km(z) = q(z)g(z) on koodipolynomi ja vastaava koodivektori on (–u,m ). Viestisana m onkin tässä koodisanan lopussa (eikä alussa kuten I.4:ssä käsitellyssä systemaattisessa koodauksessa) ja alkuosa –u muodostuu tarkistussymboleista. Koska polynomeja –u(z) + zn – km(z) on aivan yhtä monta (qk kpl) kuin koodipolynomeja yhteensä, saadaan näin yleinen systemaattinen koodausmenettely.

5. Syklisen koodin generoija- ja tarkistusmatriisit Viestipolynomin m(z) kertomista generoijapolynomilla g(z) = g1 + g2z +⋅⋅⋅+ gn – k + 1zn – k vastaa vektorin m kertominen matriisilla

19  g1  G = 0 M  0 

g2 g1 M 0

g3 g2 M 0

L L O L

gk g k–1 M g1

L L O L

g n– k+1 g n– k M g n– 2k+2

0 g n– k+1 M g n– 2k+3

0 0 M g n– 2k+4

L L O L

 0  0 . M  g n– k+1 

Näin ollen tämä matriisi G voidaan ottaa generoijamatriisiksi. (Ilmeisesti G:n rivit ovat lineaarisesti riippumattomat.) Jos taas vastaava tarkistuspolynomi on h(z) = h1 + h2z +⋅⋅⋅+ hk + 1zk, niin siitä saadaan matriisi 0  M H= 0   h k+1

0 M h k+1 hk

0 M hk h k–1

L O L L

0 M h2 h1

L O L L

0 M 0 0

h k+1 M 0 0

hk M 0 0

L O L L

h1  M  . 0   0 

Nyt polynomitulossa g(z)h(z) zi:n kerroin on i

∑ g i+1− jh j+1 , j=0

kun sovitaan, että gn – k + 2 = gn – k + 3 =⋅⋅⋅= 0 , g0 = g–1 =⋅⋅⋅= 0 , hk + 2 = hk + 3 =⋅⋅⋅= 0 , h0 = h–1 =⋅⋅⋅= 0 , kuten matriiseissa on. Mutta g(z)h(z) = zn – 1 , joten i

∑ g i+1− jh j+1 = 0

(i = 1,…,n − 1).

j=0

Nämä ovat juuri ne summat, jotka esiintyvät muodostettaessa matriisitulo GH T , joten se on = O k×(n – k). Koska H:n rivit ilmeisestikin ovat lineaarisesti riippumattomat, on H tarkistusmatriisi, joka vastaa generoijamatriisia G. Jos edelleen kyseessä on edellisen pykälän systemaattinen koodaus, ovat koodisanat –u i(z) + zn – k + i (i = 0,…,k – 1) lineaarisesti riippumattomat, joten niistä voidaan muodostaa koodin kanta. Kun merkitään ui(z) = ui1 + ui2z +⋅⋅⋅+ ui,n – kzn – k – 1

(i = 0,…,k – 1),

20 saadaan näin generoijamatriisi  −u01  G =  −u11  M  −u k−1,1

L −u0,n−k L −u1,n−k O M L −u k−1,n−k

1 0 M 0

0 1 M 0

L L O L

0 0  = −U I . k)  ( M 1

Käyttäen Lausetta 3 vähän muunnetussa muodossa saadaan edelleen vastaavaksi tarkistusmatriisiksi

(

)

H = I n−k U T .

6. Meggitt-dekoodaus Jos syndromi s(z ) = r(z )h(z ) = ((c(z ) + e(z )) h(z ) = e(z )h(z ) ei ole nollapolynomi, tiedetään virheen tapahtuneen. Koska

(

)

z i s(z ) = z i e(z ) h(z ), voidaan kokeilemalla läpi arvot i = 0,…,n – 1 siirtyä tilanteeseen, jossa virhe tapahtuu viimeisessä koodisymbolissa, mikä helpottaa dekoodausta. Tähän periaatteeseen perustuvaa dekoodausta kutsutaan Meggitt-dekoodaukseksi. Pseudokoodi

BEGIN INPUT s(z) IF s(z) = 0 THEN OUTPUT “Ei havaittuja virheitä” ELSE BEGIN i := n – 1; WHILE s(z) ≠ s1(z),…,sq – 1(z)

AND i > 0 DO

BEGIN i := i – 1; s(z) := zs(z ); END; IF s(z) = sj(z) THEN OUTPUT “Virhe aj paikassa i + 1” ELSE OUTPUT “Virhe paljastui, ei voida korjata” END;

END. missä s1(z),…,sq – 1(z) ovat virheitä a1zn – 1,…,aq – 1zn – 1 vastaavat syndromit, antaa yhden virheen korjaavan Meggitt-dekoodauksen. Meggitt-de-

21 koodauksella voidaan korjata myös useampia virheitä käyttäen syndromitaulua, missä ovat edustettuina kaikkien niiden korjattavissa olevien virheiden syndromit, joissa yksi virheistä tapahtuu viimeisessä koodisymbolissa. Myös jakojäännössyndromia voitaisiin käyttää Meggitt-dekoodauksessa. Meggitt-dekoodaus on myös varsin helposti digitaalisesti toteutettavissa (Ks. ANDERSON & MOHAN.)

7. Golay-koodit Binäärinen Golay-koodi on binäärinen syklinen (23,12)-koodi. Jaetaan z23 + 1 jaottomiin tekijöihinsä Maplella:

> Factor(z^23+1) mod 2; ( z 11 + z 9 + z 7 + z 6 + z 5 + z + 1 ) ( z + 1 ) ( z 11 + z 10 + z 6 + z 5 + z 4 + z 2 + 1 )

1 + z:n generoima syklinen koodi ei ole kovin kiinnostava. Sen sijaan tekijät 1 + z + z5 + z6 + z7 + z9 + z11 ja 1 + z2 + z4 + z5 + z6 + z10 + z1 1 kumpikin generoivat binäärisen Golay-koodin. Tämän koodin minimietäisyys on 7 ja se on täydellinen kolmen virheen korjaava koodi (vaikea todistaa, ks. esimerkiksi BLAHUT , tietokoneella asia voidaan tietysti todentaa). Ternäärinen Golay-koodi on syklinen (11,6)-koodi, jonka koodiaakkosto on Z3. Jaetaan z11 – 1 jaottomiin tekijöihinsä Maplella: > Factor(z^11-1) mod 3; (z 5+ z 4+ 2 z 3+ z 2+ 2) (z + 2) (z 5+ 2 z 3+ z 2+ 2 z + 2)

Jälleen tekijät 2 + 2 z + z2 + 2 z3 + z5 sekä 2 + z2 + 2 z3 + z4 + z5 kumpikin generoivat ternäärisen Golay-koodin. Tämän koodin minimietäisyys on 5 ja se on täydellinen kahden virheen korjaava koodi.

H UOM ! Hamming-koodien ja Golay-koodien lisäksi muut täydelliset lineaariset koodit ovatkin sitten yksinkertaisia toistokoodeja. Tämän oudon ja erittäin syvällisen tuloksen todisti lopullisesti v. 1971 suomalainen matemaatikko (TTKK:ssakin aikanaan matematiikan professorina ollut) Aimo Tietäväinen.

22

III LUKU BCH–KOODIT 1. Ekskursio: Äärelliset kunnat Alkukunnat saatiin I.2:ssa muodossa Zp eli jäännösluokkina modulo jokin alkuluku p. Valitaan nyt alkukunnan Zp (eli GF(p)) polynomirenkaan Zp[z] polynomi p(z), joka on jaoton pääpolynomi (ks. II.2–3). Jäännökset modulo p(z) muodostavat jäännösluokkarenkaan Z p[z]/〈p(z)〉, ks. II.2. Aivan samalla tavoin kuin tehtiin osoitettaessa, että jokaisella muulla Z p :n alkiolla kuin nolla-alkiolla on käänteisalkio, voidaan näyttää, että jokaisella muulla Z p [z] /〈 p(z) 〉 :n alkiolla kuin nolla-alkiolla on käänteisalkio, ks. kurssi 73265 Symbolinen analyysi 1. Tätä varten tarvitaan Zp[z]:n polynomien suurin yhteinen tekijä sekä Eukleideen algoritmi. Z p[z]:n polynomien a(z) ja b(z) suurin yhteinen tekijä on korkeinta astetta oleva oleva polynomi d(z), joka jakaa tasan sekä a(z):n että b(z):n, merkitään d(z) = syt(a(z),b(z)). Huomaa, että tällainen suurin yhteinen tekijä ei ole yksikäsitteinen, sillä jos d(z) = syt(a(z),b(z) ) ja i ∈ Z p -{ 0 }, niin myös i d(z) on syt(a(z),b(z)). (Usein vaaditaankin lisäksi, että d(z) on pääpolynomi.) Jos d(z) = syt(a(z),b(z)), niin, kuten nähdään, on sellaiset polynomit c 1 (z) ja c 2 (z), että d(z) = c 1 (z)a(z) + c 2 (z)b(z). Merkitään SYT ( a(z),b(z) ) = ( d(z),c 1 (z),c 2 (z) ) ja oletetaan, että deg( a(z) ) < deg(b(z)). Eukleideen algoritmi on seuraava rekursio:

(1)

Jos a(z) = 0 , niin tulostetaan SYT(a(z),b(z)) = (b(z), 0 , 1 ) ja lopetetaan.

(2)

Jos a(z) ≠ 0 , niin etsitään b(z):n jäännös j(z) modulo a(z), ts. kirjoitetaan b(z) = q(z)a(z) + j(z), missä deg( j(z) ) < deg( a(z) ) . Etsitään sitten SYT( j(z),a(z) ) = ( d(z),e 1 (z),e 2 (z) ) . Koska d(z) = e 1 (z)j(z) + e 2 (z)a(z), on nyt d(z) = syt( a(z),b(z) ) ja

23 d(z) = e 1 (z)j(z) + e 2 (z)a(z) = e 1 (z) ( b(z) – a(z)q(z) ) + e 2 (z)a(z) = ( e 2 (z) – e 1 (z)q(z) ) a(z) + e 1 (z)b(z). Tulostetaan SYT( a(z),b(z)) = ( d(z),e 2 (z) – e 1 (z)q(z),e 1 (z) ) ja lopetetaan.

Rekursio on päättyvä, koska min ( deg ( j(z) ) ,deg ( a(z) )) < min( deg ( a(z),deg ( b(z) )) , ts. aina kutsuttaessa SYT ko. minimiarvo pienenee. Jos nyt p(z) on jaoton ja a(z) ei ole muotoa c(z)p(z), niin syt( a(z),p(z) ) = i ≠ 0 ja voidaan kirjoittaa 1 = e 1 (z)a(z) + e 2 (z)p(z). Näin ollen a(z):lla on tällöin käänteisalkio e 1 (z) modulo p(z) eli a(z ):lla on Z p [z]/〈p(z)〉:ssä käänteisalkio e1 (z ). (Samalla tuli esitettyä menetelmä, jolla käänteisalkion voi löytää.) Siispä Z p [z] /〈 p(z) 〉 on äärellinen kunta, jossa on pdeg(p(z)) alkiota. Huomaa, että koska p(z ) on Z p[z]/〈p(z)〉:n nollaalkio, z on itse asiassa Z p [z] /〈 p(z) 〉 :n polynomirenkaassa p(z):n juuri. Usein merkitäänkin z:a Z p[z]/〈p(z)〉:n alkiona esimerkiksi α:lla ja kirjoitetaan p(α) = 0 . Muut alkiot voidaankin sitten kirjoittaa muotoon c1 + c2α + c3α 2 +⋅⋅⋅+ cnα n – 1, missä n = deg( p(z) ) ja kertoimet c1 ,c 2 ,…,c n ovat Z p :n alkioita, eli oleellisesti n-vektoreiksi, joiden komponentit ovat Z p:ssä. Voidaan näyttää (sivuutetaan tässä, ks. kurssi 73115 Algebra 1 tai esimerkiksi ADÁMEK ), että kaikki äärelliset kunnat saadaan tällä tavoin. (Myös alkukunta Z p itse, kun valitaan p(z):ksi vaikkapa jaoton polynomi z + 1 .) Äärellisen kunnan alkioiden lukumäärä on siis aina alkuluvun potenssi. Äärellisiä kuntia voidaan konstruoida monella tavalla, samaa astetta olevia jaottomia Z p[z]:n polynomejakin löytyy yleensä useampia, mutta aina äärellinen kunta, jossa on pn alkiota, on rakenteeltaan samanlainen eli isomorfinen jonkin kunnan Z p[z]/〈p(z)〉:n kanssa, missä deg(p(z)) = n. Näin ollen äärellisiä kuntia, joissa on pn alkiota, on vain yksi, ja sitä merkitään GF(pn ):llä. Jokaista mahdollista alkuluvun potenssia pn kohti on edelleen olemassa GF(pn), ts. jokaisesta polynomirenkaasta Zp[z] löytyy kaikkia astelukuja n ≥ 1 olevia jaottomia polynomeja. Esimerkiksi GF(26 ):n konstruoimiseksi voidaan valita Z 2 [z];n astetta 6 oleva jaoton polynomi p(z) = z6 + z + 1. Tarkistetaan Maple lla, että p(z) todella on jaoton:

24 > Irreduc(z^6+z+1) mod 2;

true

Maplen GF-paketilla voidaan laskea äärellisissä kunnissa, tosin vähän kankeasti. Kokeillaan sitä GF(26):ssä: > readlib(GF): > G64:=GF(2,6,alpha^6+alpha+1): > a:=G64[ConvertIn](alpha); > b:=G64[`^`](a,2);

a := 10000

b := 100000000

> G64[ConvertOut](b); α2 > c:=G64[inverse](a);

c := 100000000000000000001

> G64[ConvertOut](c); α5+ 1 > G64[`+`](a,G64[`^`](c,39)); 10000000000010001 > G64[ConvertOut]("); α4+ α + 1

Maplella on oma esitysmuotonsa kunnan alkioille, johon/josta konvertoidaan käskyillä ConvertIn/ConvertOut. Ellei tiedä yhtään sopivaa jaotonta Zp[z]:n polynomia, etsii Maple kyllä jonkin sellaisen: > readlib(GF): > G81:=GF(3,4): > G81[extension];

10001000200020002

> G81[ConvertOut]("); ?4+ ?3+ 2 ?2+ 2 ?+ 2

Valinnan saa selville extension-käskyllä, tässä se oli Z3[z]:n jaoton polynomi z4 + z3 + 2 z2 + 2 z + 2 . Koska äärellisessä kunnassa on vain äärellinen määrä alkioita, on sen alkion β erilaisia potensseja β j vain tietty äärellinen määrä. Ko. lukumäärä on β:n kertaluku, merkitään ord(β). Voidaan osoittaa, että jokaisessa äärellisessä kunnassa GF(pn ) on alkioita, joiden kertaluku on suurin mahdollinen eli pn – 1, ks. kurssi 73115 Algebra 1. Tällaisia alkioita sanotaan GF(pn):n primitiivisiksi alkioiksi. Jos γ on GF(pn):n primitiivinen alkio, voidaan jokainen muu GF(pn):n alkio, nolla-alkiota lukuunottamatta, esittää γ:n potenssina ja kunnan alkiot ovat siis

25 0 , 1 , γ,

γ2 ,

…,

γp n – 2 .

Tästä on se seuraus, että jokainen GF(pn ):n alkio β on polynomin zp n – z juuri. Tapaus β = 0 on selvä ja jos β = γi, niin β p n = γipn = γi(γp n – 1)i = γi = β. Jokainen muu alkio kuin nolla-alkio on edelleen polynomin zpn – 1 – 1 juuri. Jokainen GF(pn ):n alkio β on edellä olevan nojalla jonkin Z p[z]:n polynomin juuri. Alinta astetta olevaa tällaista Zp[z]:n polynomia kutsutaan β:n minimipolynomiksi. Minimipolynomi on Zp[z]:n jaoton polynomi, muutoin β olisi sen jonkin tekijän juuri. Usein valitaan minimipolynomiksi pääpolynomi. Edelleen β:n minimipolynomin aste on enintään n. Jos nimittäin kirjoitetaan β:n potenssit 1 ,β,β2,…,βn muotoon β i = ci1 + ci2α + ci3α 2 +⋅⋅⋅+ cinα n – 1

(i = 0,…,n),

niin kertoimista saadut n + 1 vektoria (ci1 ,c i2 ,c i3 ,…,c in ) (i = 0,…,n) ovat lineaarisesti riippuvat ja näin löytyy sellaiset kertoimet e1,…,e n + 1, jotka eivät kaikki ole nolla-alkioita, että e1 + e2β + e3β2 +⋅⋅⋅+ en + 1βn = 0 . Vielä todetaan, että β:n minimipolynomi m(z) on tekijänä jokaisessa Z p[z]:n polynomissa n(z), jonka juuri β on. Tämä paljastuu jaettaessa n(z) m(z):lla n(z) = q(z)m (z) + j(z),

deg ( j(z) ) < deg( m (z) ) ,

sillä tällöin β on myös j(z):n juuri ja näin j(z):n on oltava nollapolynomi. Erityisesti minimipolynomit ovat polynomin zpn – z tekijöitä. Minimipolynomeilla on aivan keskeinen rooli BCH-koodien konstruktiossa.

Maple osaa testata onko annettu alkio primitiivinen: > G64[isPrimitiveElement](a);

true

Tässä sattui GF(26 ):n generoinnissa käytetty alkio α olemaan primitiivinen. Näin käy, jos käyttää generoinnissa jaottomana polynomina p(z) jonkin primitiivisen alkion minimipolynomia. Esimerkki toisesta tilanteesta: > G9:=GF(3,2,alpha^2+1): > a:=G9[ConvertIn](alpha); > G9[isPrimitiveElement](a);

a := 10000 false

Maplella voi etsiä primitiivisen alkion:

26 > b:=G9[PrimitiveElement]();

b := 20001

> G9[ConvertOut](b);

2 α+ 1

Kunnassa GF(pn) on summien ja polynomien p:nteen potenssiin korottaminen hyvin helppoa. Binomikerroin  p  = p(p − 1)L(p − i + 1)  i 1 ⋅ 2Li on nimittäin jaollinen p:llä, kun i = 1,…,p – 1. Näin ollen p

p

(β + γ ) =

∑  piβi γ p−i = βp + γ p, i=0

mikä pätee myös polynomeille. Käyttäen kaavaa toistuvasti saadaan myös useampitermisten summien p:nnet potenssit samalla tavalla, esimerkiksi (β + γ + δ)p = β p + (γ + δ)p = β p + γp + δ p . Toisaalta alkukunnan Zp alkiot i ovat polynomin zp – z juuria, joten niille i p = i . Siispä Z p[z]:n polynomeille a(z) kaava on vieläkin yksinkertaisempi: a(z) p = a(z p ).

Toistuvat p:nteen potenssiin korotukset johtavat edelleen kaavoihin (β + γ)p j = βpj + γpj ja

a(z)p j = a(zpj )

(j = 0,1,…).

Jos nyt β on Z p[z]:n polynomin a(z) juuri GF(pn):ssä, niin samoin ovat sen potenssit βpj (j = 1,2,…). Äärellisissä kunnissa pätee R[z]:stä tuttu tulos (todistuskin on sama): APULAUSE. Jos β on polynomin a(z) juuri GF(pn):ssä, niin z – β jakaa a(z):n GF(p n ):n polynomirenkaassa. a(z):n eri juuria on näin ollen enintään t = deg (a(z)) kpl ja jos eri juuria β 1 ,…,β t on nimenomaan t kpl, niin voidaan kirjoittaa a(z) = γ (z – β 1 )⋅⋅⋅(z – β t), missä γ on GF(pn):n alkio. ■ Eräs seuraus Apulauseesta on, että jos GF(pn) on { 0 , 1 ,β1,…,βpn – 2}, niin

27 zpn

– z = z(z – 1 )(z – β 1 )⋅⋅⋅(z – β p n – 2),

ja myös, että zp – z = z(z – 1 )⋅⋅⋅(z – p − 1) . L AUSE 7. Jos GF(pn):n alkion β minimipolynomi (pääpolynomi) on m(z) ja d = deg(m(z)), ovat β,β p,β p2 ,…,βpd – 1 sen eri juuret ja m(z) = (z – β)(z – β p )(z – β p 2 )⋅⋅⋅(z – βpd – 1 ) . Todistus. Ilmeisesti β,βp,βp2 ,…,βpd – 1 ovat m(z):n juuria, joten pitää näyttää, että ne ovat eri alkioita. Asetetaan vastaoletus: βpi = βpj , missä i < j, ja valitaan j – i pienimmäksi mahdolliseksi. Silloin 0 = βpj – β pi = (β pj – i – β)pi, joten β p j – i = β. Koska j – i on pienin mahdollinen, ovat potenssit β,β p , βp2 ,…,β p j – i – 1 eri alkioita. Otetaan tarkasteltavaksi astetta j – i < d oleva pääpolynomi n 1 (z) = (z – β)(z – β p )(z – β p 2 )⋅⋅⋅(z – β p j – i – 1) = γ1 + γ2z +⋅⋅⋅+ γj – i zj – i – 1 + zj – i, jonka juuret nämä eri alkiot ovat, ja n2 (z ) = γ1p + γ 2p z +L+ γ pj−i z j−i−1 + z j−i . Silloin n 2(β ph) = n 1(β ph – 1)p = 0

(h = 1,…,j – i).

Polynomeilla n 1 (z) ja n 2 (z) on samat keskenään erilaiset juuret, joten yo. Apulauseen nojalla ne ovat samat polynomit. Kertoimet γ1 ,γ2 ,…,γj – i ovat näin ollen polynomin zp – z juuria, mutta, kuten todettiin, nämä juuret ovat 0 , 1 ,…, p − 1. Siispä n 1(z) on Z p[z]:n polynomi. Tämä on mahdotonta, sillä tällöinhän m(z) ei olisikaan β:n minimipolynomi. Vastaoletus on siis väärä. ■

2. BCH-koodit Syklinen koodi, jonka koodisymbolit ovat Z p:n alkioita ja jonka generoijapolynomi saadaan säännöillä

28 (i)

valitaan äärellinen kunta GF(pm), luku kä kertalukua n oleva GF(pm):n alkio β,

(ii)

muodostetaan GF(pm ) (eri) alkioiden β,β 2 ,…,β 2t minimipolynomien m 1(z),…,m 2t(z) (pääpolynomeja) pienin yhteinen jaettava, ts. kerrotaan minimipolynomit keskenään, mutta otetaan kukin minimipolynomi tuloon mukaan vain kerran (alkioilla β,β 2 ,…,β 2t kun voi olla samojakin minimipolynomeja; Lauseen 7 mukaan erityisesti alkioiden βjp, j = 1,2,…, minimipolynomeja ei tarvitse ottaa mukaan),

n (= koodin pituus) se-

(iii) valitaan saatu pienin yhteinen jaettava generoijapolynomiksi g(z), on ns. BCH-koodi* C , jonka suunniteltu virheenkorjauskyky on t. Jos β on GF(p m ):n primitiivinen alkio, kyseessä on primitiivinen BCH-koodi. Primitiivisen BCH-koodin pituus on pm – 1. Koska

β jn = 1

(j = 1,…,2t),

jakavat minimipolynomit m 1(z),…,m 2t(z) kukin polynomin zn – 1 :n ja samoin tekee niiden pienin yhteinen jaettava g(z). Näin ollen C on todellakin syklinen koodi, jonka pituus on n (Lause 5). Huomaa, että redundanssi on deg (g(z)) = n – k ≤ m(2t – 2t/p), binääritapauksessa (p = 2) erityisesti n – k ≤ mt. H UOM ! Yleisemmin voitaisiin ottaa generoijapolynomiksi alkioiden β h , βh + 2,…,βh + 2t minimipolynomien pienin yhteinen tekijä. BCH-koodi voidaan myös muodostaa käyttäen koodisymboleina mielivaltaisen äärellisen kunnan alkioita. Eräs esimerkki tällaisesta on myöhemmin käsiteltävä Reed–Solomon-koodi (ks. III.4).

BCH-koodi voidaan määritellä koodipolynomien juurirakenteen avulla:

L AUSE 8. Yllä oleva BCH-koodi C muodostuu tarkalleen niistä enintään astetta n – 1 olevista Zp[z]:n polynomeista, joiden juuria β,β2,…,β2t ovat. Todistus. Jos β,β 2 ,…,β 2t ovat enintään astetta n – 1 olevan Z p [z]:n polynomin c(z) juuria, niin minimipolynomit m 1 (z),…,m 2t (z) ovat c(z):n tekijöitä ja samoin on niiden pienin yhteinen jaettava g(z). Näin ollen c(z) on *

Tarkemmin sanoen Bose–Ray-Chaudhuri–Hocqhuenghem-koodi, mutta tämä nimi on liian pitkä.

29 koodipolynomi. Jos taas c(z) on koodipolynomi, niin generoijapolynomi g(z) on sen tekijä ja samoin ovat minimipolynomit m 1(z),…,m 2t(z). ■ Lauseen mukaan C = { c(z)  c(β i) = 0 (i = 1,…,2t) ja deg( c(z) ) < n }, ts. koodivektorit c ovat tarkalleen ne vektorit, jotka toteuttavat matriisiyhtälön cHT = 02t. missä H on matriisi 1  1  H = 1   M 1 

β β2 β3 M

β2

β3

( β2 ) ( β2 ) 3 2 3 3 β β ( ) ( ) 2

M

3

M

( ) (β )

β2t β

2t 2

2t 3

 n−1  β2   n−1 . β3  M  2t n−1  β 

L β n−1

( ) L( ) L

O

L

( )

Vaikka H ei olekaan I.3:ssa olevan tarkistusmatriisin tyyppiä (sen alkiot ovat GF(pm ):n alkioita), se kuitenkin käyttäytyy samalla tavoin ja tästä syystä H:ta kutsutaan myös tarkistusmatriisiksi. Matriisia H käyttäen voidaan näyttää, että BCH-koodin todellinen virheenkorjauskyky on ainakin suunniteltu. Tätä varten tarvitaan muotoa 1  a1 V =  a12   Ml−1  a1

1 a2 a2 2 M l−1 a2

1 a3 a2 3 M l−1 a3

L L L O L

1  al   a2 l  M  a l−1 l 

olevia matriiseja eli ns. Vandermonden matriiseja koskeva aputulos, joka pätee missä tahansa kunnassa.

APULAUSE.

det( V ) =

∏ (a j − a i )

1≤i< j≤l

Todistus. Ilmeisestikin kaava on oikea, kun l = 2 . Jos taas l on suurempi, voidaan sen arvoa toistuvasti pienentää:

30 1 a1 a12 M a1l−1

1 a2 a2 2 M l−1 a2

1 a3 a2 3 M l−1 a3

L L L O L

1 1 1 1 al 0 a 2 − a1 a 3 − a1 = 0 a2 a2 a2 l 2 − a1a 2 3 − a1a 3 M M M M l−1 l−2 l−1 l−2 a l−1 0 a − a a a − a1a 3 l 2 1 2 3

1 a2 = (a 2 − a1 )(a 3 − a1 )L(a l − a1 ) a 2 2 M l−2 a2

1 a3 a2 3 M l−2 a3

L L L O L

L 1 L a l − a1 L a2 l − a1a l O M L a l−1 − a1a l−2 l l

1 al =L= (a j − a i ). ■ a2 l M 1≤i< j≤l a l−2 l

∏

L AUSE 9. (BCH-RAJA ) BCH-koodi korjaa vähintään niin monta virhettä kuin on sen suunniteltu virheenkorjauskyky. Todistus. Näytetään, että jos BCH-koodin C suunniteltu virheenkorjauskyky on t, niin dmin (C ) ≥ 2t + 1. Valitaan sitä varten C :n koodivektori c ≠ 0, jonka paino on pienin. Jos w(c) ≥ 2t + 1, niin asia on selvä. Jos taas w(c) ≤ 2t, niin valitaan c:n nolla-alkiosta eroavat komponentit ci1 ,…,cid , missä i1 t, niin pyyhitään jälleen pois sellainen rivi, jolla on suurin κi, otetaan uudeksi R′:ksi näin saatu matriisi, ja mennään 2):een. Muussa tapauksessa sarakkeen dekoodaus onnistui ja ν ≤ t ja siirrytään seuraavaan sarakkeeseen. 4)

Menettely pysähtyy, kun kaikki sarakkeet on saatu dekoodatuksi tai kun kaikki rivit on pyyhitty pois. Ensin mainitussa tapauksessa r:n dekoodaus onnistui, viimemainitussa tapauksessa taas virhe paljastui, mutta sitä ei voitu korjata.

Tulokoodeja sekä niiden dekoodausta on käsitelty laajemmin viitteissä BLAHUT ja LIN & COSTELLO, ks. myös SWEENEY.

3. Kiedotut koodit Koodista C saadaan l-kertaisesti kiedottu koodi C (l) seuraavasti. Otetaan kaikin tavoin l C :n koodisanaa c i = ci1 c i2 ⋅⋅⋅c in (i = 1,…, l) (eivät välttämättä kaikki eri sanoja) ja muodostetaan niistä matriisi  c1   c11  c2  =  c21  M   M     c l   c l1

c12 c22 M c l2

L L O L

c1n  c2n  . M  c ln 

Vastaava C (l) :n koodisana saadaan lukemalla matriisi sarakkeittain ylhäältä alaspäin. Jos C on (n,k)-koodi, niin C (l) on ( ln, lk)-koodi. Polynomimuodossa yo. matriisia vastaa polynomi c1 (z l ) + zc2 (z l ) + z 2c3 (z l )+L+ z l−1c l (z l ). L AUSE 19. Jos C korjaa enintään d-pituiset purskevirheet, niin C (l) korjaa enintään ld-pituiset purskevirheet. Näin ollen, jos C on Reiger-optimaalinen, niin samoin on C (l) . Todistus. Enintään l d-pituinen purskevirhe C (l) :n koodisanassa aiheuttaa enintään d-pituiset purskevirheet koodisanan konstruktiossa käytetyissä C :n koodisanoissa c1,…, c l . ■ Lineaarisuus säilyy kietomisessa ja samoin syklisyys:

51

52 L AUSE 20. Jos C on syklinen (n,k)-koodi, jonka generoijapolynomi on g(z) ja vastaava tarkistuspolynomi h(z), niin C (l) on syklinen ( ln, lk)-koodi, jonka generoijapolynomi on g(z l ) ja vastaava tarkistuspolynomi h(z l ). Todistus. Jos C (l) :n sanaa vastaava matriisi on  c1   c11  c2  =  c21  M   M     c l   c l1

c12 c22 M c l2

L L O L

c1n  c2n  , M  c ln 

niin syklisellä yhden symbolin siirrolla saatavaa sanaa vastaa matriisi  c21  c31  M   c12

c22 c32 M c13

L L O L

c2n  c3n  , M  c11 

jonka rivit c2,…, c l ja c12 c 13 ⋅⋅⋅c 1,n – 1c 11 ovat C :n koodisanoja. Jos siis C on syklinen, niin samoin on C (l) .

Oletetaan sitten, että g(z) on C :n generoijapolynomi ja h(z) vastaava tarkistuspolynomi. Koska g(z) on zn – 1 :n tekijä, niin g(z l ) on z nl − 1 :n tekijä. Otetaan tarkasteltavaksi (mielivaltainen) C (l) :n viestipolynomi m(z) ja kirjoitetaan se muotoon m(z ) = m1 (z l ) + zm2 (z l )+L+ z l−1m l (z l ). Silloin polynomit m 1(z),…, m l (z ) ovat (mielivaltaisia) C :n viestipolynomeja, niitä vastaavat C :n koodipolynomit c i(z) = m i(z)g(z) (i = 1,…, l) ja

(

)

m(z )g(z l ) = m1 (z l ) + zm2 (z l )+L+ z l−1m l (z l ) g(z l ) l

l

2

l

= c1 (z ) + zc2 (z ) + z c3 (z )+L+ z

l−1

c l (z l ).

C (l) :n koodipolynomit ovat näin tarkalleen kaikki muotoa m(z) g(z l ) olevat polynomit. Koska z nl − 1 = g(z l ) h(z l ), on h(z l ) C (l) :n g(z l ):tä vastaava tarkistuspolynomi. ■

Kietomalla voidaan siis esimerkiksi muodostaa mielivaltaisen pitkiä purskevirheitä korjaavia Reiger-optimaalisia syklisiä koodeja käyttäen s. 45 olevan taulukon koodeja. Koodisanojen c1,…, c l avulla saatu matriisi voidaan lukea muillakin tavoin kiedotuksi koodisanaksi purskevirheenkorjauskyvyn pysyessä sykliselle koodille C Lauseen 19 mukaisena (yo. tapa on ns. lohkokietominen). Voi-

53 daan edetä esimerkiksi lävistäjittäin vasemmalta oikealle ja ylhäältä alas (lihavointi) aloittaen päälävistäjästä c11 c21 c31 c 41

c12 c22 c32 c 42

c13 c23 c33 c 43

c14 c24 c34 c 44

c15 c25 c21 c35 c31 c32 c 45 c41 c42 c43

c11 c21 c31 c 41

c12 c22 c32 c 42

c13 c23 c33 c 43

c14 c24 c34 c 44

c15 c11 c12 c13 c25 c21 c22 c35 c31 c 45

tai vastalävistäjästä

Jälkimmäisen tavan muunnelma, jossa l = n ja sovitaan, että ensimmäiset ja viimeiset l – 1 C :n koodisanaa ovat kiinteitä (vaikkapa c = c1⋅⋅⋅cn), on erityisen kätevä kiedottaessa uusia C :n koodisac1 c2 c3 c 4 noja jatkuvasti mukaan “unohtaen” entisiä, ks. oheic1 c2 c3 c 4 nen esimerkki. Lävistäjät luetaan koodisanaksi ylimc1 c2 c3 c 4 mästä aloittaen alhaalta ylös (miksei ylhäältä alas?). c 41 c 42 c 43 c 44 Tämä menettely on ns. viivekiedonta. c51 c52 c53 c54 c61 c62 c63 c64 Kietominen voidaan tehdä myös käyttäen useampaa M M M M koodia. Ristikietomisessa tehdään (k1 ,n 1 )-koodista c c c c N1 N2 N3 N4 C 1 ja (k2,n2)-koodista C 2 kiedottu koodi seuraavasc 1 c2 c3 c 4 ti. Muodostetaan k2:sta C 1:n koodisanasta c 1,…,c k c c4 1 c2 c 3 matriisi c1 c2 c3 c 4 c12  c1   c11   c2  = c21 c22  M   M M c    k 2   c k 21 c k 2 2

L c1n1  L c2n1   O M L c k 2 n1 

aivan kuten edellä. Sen sijaan, että luettaisiin matriisi sarakkeittain koodisanaksi, tulkitaankin nyt sarakkeet C 2:n viestisanoiksi ja koodataan ne. Näin saadaan n1 kpl C 2:n koodisanoja, jotka taas kiedotaan joko kaikki tai sitten l:n ryhmissä (jos l ei ole n1:n tekijä, voidaan yli jääneet C 2:n koodisanat “säästää” ja käyttää seuraavassa kietomisessa). Ristikiedotun koodin ominaisuudet ovat paljolti samantapaiset kuin katenoidun koodin (ks. seuraava pykälä).

4. Katenoidut koodit Koodien katenoinnissa ideana on koodata ensin yhdellä koodilla Culko, ns. ulkokoodilla, tulkita koodisymbolit toisen koodin C sisä , ns. sisäkoodin, viestisanoiksi sekä sitten koodata vielä tällä koodilla. Dekoodattaessa toimitaan päinvastaisessa järjestyksessä.

54 C ulko :n kooderi

Tulkitaan C ulko :n koodisymbolit C sisä :n viestisanoiksi.

C sisä :n kooderi virheet

C ulko :n dekooderi

Tulkitaan C sisä :n viestisanat C ulko :n koodisymboleiksi.

siirto tai talletus

C sisä :n dekooderi

Vastaavalla tavalla voitaisiin katenoida useampiakin kuin kaksi koodia. Yleensä käytetään ulkokoodina ja sisäkoodina lineaarisia koodeja, joiden koodisymbolit ovat vastaavasti äärellisten kuntien GF(pM ) ja GF(pm ) alkioita, missä m on M:n tekijä eli M = km. Tällöin GF(pM ):n alkiot voidaan samaistaa M-pituisiksi vektoreiksi, joiden komponentit ovat alkukunnan Z p alkioita. Koska m on M:n tekijä, voidaan nämä vektorit lohkoa m-pituisiin osavektoreihin, jotka taas voidaan edelleen samaistaa GF(pm ):n alkioihin. Näin jokainen ulkokoodin koodisymboli voidaan samaistaa k-pituiseksi vektoriksi, jonka alkiot ovat sisäkoodin koodisymboleja. Jos nyt C ulko on (N,K)-koodi ja C sisä on (n,k)-koodi ja tulkitaan myös C ulko:n viestisymbolit k-pituisiksi vektoreiksi, joiden alkiot ovat sisäkoodin koodisymboleja, niin katenoimalla saatu koodi on lineaarinen (Nn,Kk)-koodi. Katenoidussa koodissa sisäkoodin tehtävänä on korjata “hajavirheet”. Ulkokoodi puolestaan korjaa purskevirheet, jotka sen näkökulmasta ovat tavallisia hajavirheitä. Jos ulkokoodilla on vielä hyvä purskevirheiden korjauskyky, voidaan katenoidulla koodilla korjata pitkiäkin purskevirheitä. Purskevirheen sattuessa sisäkoodi joko dekoodaa väärin, mikä aiheuttaa ulkokoodille yhden virheen, tai sitten ei pysty dekoodaamaan lainkaan. Jälkimmäisessä tapauksessa voidaan joko ilmoittaa ulkokoodille vastaava koodisymboli pyyhkiytyneeksi — ja käyttää ulkokoodin mahdollista tehokasta pyyhkiymien korjausta — tai sitten antaa ulkokoodille mielivaltainen koodisymboli, joka todennäköisesti on virheellinen. Hyvän katenoimalla saadun koodin suunnittelu ei ole aivan helppo tehtävä.* Sisäkoodin viestin pituuden k tulisi olla pieni, jotta ulkokoodin koodisymbolit eivät tulisi kovin suuresta kunnasta GF(pkm ). Tämä taas joko rajoittaa sisäkoodin tehokkuutta (n on liian suuri k:hon verrattuna) tai sitten sen virheenkorjauskykyä ja ulkokoodi saakin korjattavakseen paljon virheitä. Ks. SWEENEY. *

Alkuperäisviite FORNEY , G.D.: Concatenated Codes. MIT Press (–66) on edelleen hyvin käyttökelpoinen.

55 5. Fire-koodit Otetaan koodisymbolit alkukunnasta Zp ja valitaan generoijapolynomiksi g(z) = (zc – 1 )p (z), missä p(z) on astetta m oleva Zp[z]:n jaoton polynomi ja c valitaan sopivasti. (Yleisemminkin voitaisiin valita koodisymbolit mielivaltaisesta äärellisestä kunnasta.) Polynomin p(z) ns. jakso on pienin sellainen luku e, että p(z) on polynomin ze – 1 tekijä. (Koska p(z):tä voitaisiin käyttää äärellisen kunnan GF(pm ) konstruktiossa, se on minimipolynomi, joten sillä on jakso, ks. III.1.) Nyt c valitaan siten, että e ei ole sen tekijä. Koodin pituudeksi n otetaan c:n ja e:n pienin yhteinen jaettava pyj(c,e) eli pienin luku, jonka sekä c että e jakavat tasan. Jotta saataisiin syklinen koodi, pitää g(z):n olla polynomin zn – 1 tekijä. Tämän toteaminen* ei ole ihan helppoa. Fire-koodeilla on erinomaisen hyvät purskevirheiden paljastus- ja korjaamisominaisuudet, jopa yhtaikaisesti. Asian selvittämiseksi esitetään seuraava dekoodausmenettely.

(1)

Saatu polynomi on muotoa r(z) = c(z) + zib(z), missä c(z) on koodipolynomi ja zib(z) on purskevirhepolynomi ja b(z):n vakiotermi on ≠ 0 . Muodostetaan siitä jakamalla zc – 1 :llä ja p(z):lla purskearvosyndromi s 1 (z) sekä purskekohtasyndromi s 2 (z): z ib(z) = q 1 (z)(z c – 1 ) + s 1 (z), z ib(z) = q 2 (z)p(z) + s 2 (z),

*

deg( s 1 (z) ) < c, deg ( s 2 (z) ) < m.

Todetaan ensin yleisesti, että zu – 1 on zv – 1 :n tekijä siinä tapauksessa, että u on v:n tekijä. Jos nimittäin u on v:n tekijä, niin v = uw. Ilmeisesti z – 1 on zw – 1 :n tekijä, joten tällöin edelleen zu – 1 on zuw – 1 :n eli zv – 1 :n tekijä. Nyt c on n:n tekijä, joten zc – 1 on zn – 1 :n tekijä. Toisaalta p(z) on ze – 1 :n tekijä ja e on n:n tekijä, joten myös p(z) on zn – 1 :n tekijä. Edelleen c ei ole e:n tekijä, joten jaettaessa c e:llä saadaan c = qe + j, missä 0 < j < e. Jos nyt p(z) olisi zc – 1 :n tekijä, olisi se myös erotuksen (zc – 1 ) – (ze – 1 ) = ze (z c – e – 1 ) tekijä ja jaottomana zc – e – 1 :n tekijä. Jatkamalla näin q kertaa todettaisiin lopulta, että p(z) olisi zj – 1 :n tekijä, mikä on mahdotonta, koska 0 < j < e. Siispä p(z) ei ole z c – 1 :n tekijä ja, koska p(z) on jaoton, 1 = syt( p(z),z c – 1 ) ja (ks. III.1) 1 = a(z)p(z) + b(z)(zc – 1 ). Kuten todettiin, zc – 1 on zn – 1 :n tekijä, joten zn – 1 = f(z)(zc – 1 ). Koska myös p(z) on zn – 1 :n tekijä, on se edelleen polynomin f(z) = f(z)a(z)p(z) + b(z)f(z)(zc – 1 ) = f(z)a(z)p(z) + b(z)(zn – 1 ) tekijä. Kaiken kaikkiaan siis g(z) = (zc – 1 )p(z) on zn – 1 :n tekijä, kuten pitikin.

(2)

Jos s 1 (z) = s 2 (z) = 0 , katsotaan r(z) virheettömäksi* ja lopetetaan.

(3)

Jos nyt purskevirheen pituus on enintään c eli deg( b(z) ) ≤ c – 1, on s 1 (z) ≠ 0 ja purskevirhe paljastuu (se voidaan vielä kuitenkin korjata väärin!). Jos samalla s 2 (z) = 0 , katsotaan purskevirhe vain paljastuneeksi ja lopetetaan. Pitkä purskevirhe voi myös johtaa tilanteeseen, jossa s 1 (z) = 0 ja s 2 (z) ≠ 0 , ja myös tällöin katsotaan se vain paljastuneeksi ja lopetetaan.

(4)

Muussa tapauksessa sekä s1(z) ≠ 0 että s 2 (z) ≠ 0 . Tällöin yritetään korjata purskevirhe. Sitä varten lasketaan siirretyt purskearvo- ja purskekohtasyndromit s1(l) (z ) ja s(l) 2 (z ) jakamalla z l s1 (z ) = q1(l) (z )(z c − 1 ) + s1(l) (z ), (l) z l s2 (z ) = q (l) 2 (z )p(z ) + s2 (z ),

(

)

deg s1(l) (z ) < c,

(

)

deg s(l) 2 (z ) < m

peräkkäin arvoille l = 0,1,2,…. (Huomaa, että s1(l) (z ) itse asiassa saadaan syklisellä siirrolla s 1 (z):stä ja että s1(0) (z ) = s1 (z ) sekä s(0) 2 (z ) = s2 (z ). ) (5)

Kun löytyy tilanne, missä nämä syndromit s1(l) (z ) ja s(l) 2 (z ) ovat samat, löytyy samalla i sekä b(z) ja purskevirhe voidaan korjata, edellyttäen että sen pituus on t ≤ m. Mainittu tilanne tulee nimittäin tällöin lopulta vastaan, sillä s1(n−i) (z ) = s(n−i) (z ) = b(z ). 2 Jos nyt c ≥ s = deg( b(z) ) + 1 ≥ t ja b:ssä on ainakin c – t peräkkäistä nolla-alkiota, voi paljastunut s-pituinen purskevirhe tulla näin väärin dekoodatuksi, mutta muutoin sitä ei tapahdu. Näin ollen tällainen purskevirhe paljastuukin varmasti (ts. tulematta väärin dekoodatuksi), jos sen pituus on s ≤ c – t + 1.

(6)

*

Ellei (5):ssä mainittua tilannetta esiinny n – 1 siirron aikana, on purskevirhe liian pitkä korjattavaksi. Sen katsotaan vain paljastuneen ja lopetetaan.

Tällöin nimittäin sekä z c – 1 että p(z) ovat r(z):n tekijöitä. Kirjoitetaan r(z) = v(z)(zc – 1 ). Koska 1 = syt(p(z),zc – 1 ) (ks. edellinen alaviite), voidaan kirjoittaa 1 = a1 (z)p(z) + a2 (z)(z c – 1 ) ja edelleen v(z) = v(z)a 1 (z)p(z) + a 2 (z)r(z). p(z) siis on v(z):n tekijä ja näin ollen g(z) = (zc – 1 )p(z) on r(z):n tekijä eli r(z) on todellakin koodipolynomi.

56

57 H UOM ! Algoritmia tutkiessa voi arvella, että ellei korjaamista yritetä, niin sillä saavutetaan osin vieläkin parempi purskevirheen paljastuskyky. Itse asiassa voidaan esimerkiksi näyttää, että s1-pituisen ja s2-pituisen purskevirheen muodostama purskevirhepari paljastuu, mikäli m ≥ min(s1,s2) ja s1 + s2 ≤ c + 1. (Tämä ei ole ihan helppoa, jossei nyt niin kovin vaikeaakaan.) Esitetyssä dekoodausmenettelyssä voi siirrettyjä syndromeja joutua laskemaan enimmillään ec – 1 kpl. Nopeampi menettely saadaan huomaamalla, että koska p(z) on ze – 1 :n tekijä, niin voidaan kirjoittaa ze = 1 + o (z)p (z) jollekin polynomille o(z). Näin ollen siirrettyjen syndromien jono s(0) 2 (z ), s(1) (z ),… toistuu jaksollisesti samana s(e−1) (z ):n jälkeen* . Tämän nopeam2

2

man dekoodausmenettelyn kohdat (1)–(3) ovat samat kuin edellä ja loput kohdat ovat seuraavat:

(4')

Muussa tapauksessa sekä s1(z) ≠ 0 että s 2 (z) ≠ 0 . Tällöin yritetään korjata purskevirhe. Sitä varten lasketaan siirrettyjä purskearvosyndromeja s1(l) (z ) jakamalla z l s1 (z ) = q1(l) (z )(z c − 1 ) + s1(l) (z ),

(

)

(

)

deg s1(l) (z ) < c

peräkkäin arvoille l = 0,1,2,…, kunnes deg s1( l )( z ) < t ja talletetaan tarvittavien siirtojen määrä l = l 1 sekä silloinen synd(l )

romi s1 1 (z ). (Huomaa, että itse asiassa s1(l) (z ) saadaan syklisellä siirrolla s 1 (z):stä ja että s1(0) (z ) = s1 (z ).) Jollei tämä onnistu enintään c – 1 siirrolla, on purskevirhe liian pitkä korjattavaksi, jolloin se katsotaan paljastuneeksi ja lopetetaan. (5')

Lasketaan siirrettyjä purskekohtasyndromeja s(l) 2 (z ) jakamalla (l) z l s2 (z ) = q (l) 2 (z )p(z ) + s2 (z ),

(

)

deg s(l) 2 (z ) < m (l )

1 peräkkäin arvoille l = 0,1,2,…, kunnes s(l) 2 (z ) = s1 (z ) ja talletetaan tarvittavien siirtojen määrä l = l 2 . Jollei tämä onnistu enintään e – 1 siirrolla, on purskevirhe liian pitkä korjattavaksi, jolloin se katsotaan paljastuneeksi ja lopetetaan.

*

Mutta ei sitä ennen! Muutoin nimittäin p(z) on b(z)(zd – 1 ):n tekijä ja 0 < d < e. Koska p(z) ei ole b(z):n tekijä, on 1 = syt( p(z),b(z) ) ja 1 = a 1 (z)p(z) + a 2 (z)b(z) ja zd – 1 = (zd – 1 )a1 (z)p(z) + (zd – 1 )a2 (z)b(z) ja p(z) on silloin zd – 1 :n tekijä. Tämä on kuitenkin mahdotonta, sillä d < e ja e on p(z):n jakso.

(6')

Siirtojen määristä l 1 sekä l 2 saadaan nyt laskettua kohdassa (5) (edellinen algoritmi) tarvittava siirtojen määrä l. Periodisuuksista johtuen nimittäin l toteuttaa jotkin yhtälöt  l = a1c + l1 l = a e + l , 2 2  missä a1 ja a2 ovat kokonaislukuja. Jos nyt olisi kaksi ratkaisua l = l′ ja l = l′′ , missä l′ > l′′ , niin saataisiin yhtälöt  l′ = a1′ c + l1  l′ = a ′ e + l 2 2 

ja

 l′′ = a1′′c + l1  l′′ = a ′′ e + l . 2 2 

Mutta tällöin sekä c että e olisivat l′ − l′′ :n tekijöitä eikä n olisikaan pyj(c,e). Näin ollen l määräytyy yksikäsitteisesti luvuista l 1 ja l 2 ja nämä arvot voidaan taulukoida etukäteen. (l )

Kun on saatu l sekä s2 2 (z ), voidaan dekoodaus suorittaa.

Tässä menettelyssä tulee siirtoja enintään e + c – 2 kpl, mikä yleensä on huomattavasti vähemmän kuin ec – 1. Kootaan yhteen yo. dekoodausalgoritmien antamat tulokset. Huomaa erityisesti tapaus t = 0, joka seuraa siitä, että p(z) ei ole zc – 1 :n tekijä (alaviite s. 55). L AUSE 21. Fire-koodi, jonka generoijapolynomi on g(z) = (zc – 1 )p(z), yhtaikaisesti paljastaa purskevirheet, joiden pituus on s ≥ t, ja korjaa purskevirheet, joiden pituus on t ≤ deg(p(z)), mikäli c ≥ s + t – 1. ■ Ns. yleistetyn Fire-koodin generoijapolynomi on muotoa g(z) = (zc – 1 )p 1 (z)⋅⋅⋅p h (z), missä p 1(z),…,p h(z) ovat erilaisia jaottomia (pää)polynomeja ja niiden jaksot e1 ,…,e h eivät ole c:n tekijöitä. Koodin pituus on lukujen c,e1 ,…,e h pienin yhteinen jaettava n = pyj(c,e1 ,…,e h ). Tällaiselle koodille saadaan hyvin samantapaiset, mutta vielä nopeammat koodausmenettelyt kuin edellä “tavalliselle” Fire-koodille, ks. RAO & FUJIWARA . Viitteessä BLAHUT on hyvä esitys Fire-koodeista.

58

59

V LUKU KOODIRAJAT 1. Yleistä Koodin “hyvyyttä” sekä suorituskykyä voidaan mitata useillakin tunnusluvuilla. Jotta päästäisiin vertailemaan koodeja, skaalataan nämä luvut sopivasti. Näin saadaan (n,k)-koodin C koodaussuhde k ρ =n sekä virheenkorjaussuhde λ =

d min (C ) . n

E SIMERKKI . Toistokoodille (ks. Esimerkki s. 1) ρ = 1/r ja λ = 1/k. Hamming-koodille (ks. I.6) r(q – 1) ρ = 1 – qr – 1

ja

3(q – 1) λ = qr – 1 .

Koodirajat ovat epäyhtälöitä, joilla arvioidaan yo. tunnuslukuja. Arviot ovat yleisiä. Asymptoottisissa rajoissa oletetaan koodin pituuden olevan suuri, jolloin mukaan tulee pieni virhetermi εn , joka lähenee nollaa pituuden n kasvaessa. Jatkossa (n,K,d)-koodilla tarkoitetaan n-pituista koodia, jonka koodisanojen lukumäärä on K ja minimietäisyys d. Koodisymbolien lukumäärää merkitään q:lla. Lineaariselle koodille on siis K = qk , missä k on viestin pituus. Yleisesti merkitään k = logq K (K:n q-kantainen logaritmi, ei välttämättä kokonaisluku) ja vastaavasti ρ =

Yksinkertaisin koodiraja on

log q K n .

60 L AUSE 22. (SINGLETON -RAJA ) (n,k,d)-koodille d ≤ n – k + 1 eli 1 λ≤1–ρ+n. Asymptoottisesti λ ≤ 1 – ρ + εn. Todistus. Asia on aivan ilmeinen sykliselle koodille, koska sen generoijapolynomi on koodipolynomi ja sen aste on n – k. Edelleen asia on ilmeinen myös lineaariselle koodille, sillä mitkä tahansa sen tarkistusmatriisin n – k + 1 saraketta ovat lineaarisesti riippuvat. Mutta Singleton-raja pätee aivan yleisesti. Merkitään K:lla kaikkien koodisanojen lukumäärää. Jos nyt olisi K > qn – d + 1, niin koodisanojen joukossa olisi kaksi eri sanaa, joiden n – d + 1 ensimmäistä symbolia ovat samat ja joiden etäisyys olisi näin enintään d – 1. Koska tämä ei ole mahdollista, on K ≤ qn – d + 1 eli k ≤ n – d + 1. ■ Koodeja, jotka ovat Singleton-rajalla, ts. d = n – k + 1, kutsutaan MDS-koodeiksi*. Reed–Solomon-koodit (ks. III.4) ovat MDS-koodeja.

2. Ylärajoja Singleton-rajan tapaisia ylärajoja tunnetaan useita. Johdetaan joitakin yksinkertaisia ylärajoja ja annetaan valmiina muutama lisää.

Plotkin-raja Koodin C = {c1,…,cK} ns. kokonaisetäisyys on d total (C ) =

∑ d(ci ,c j ). i≠ j

Jos q koodisymbolia ovat a1 ,…,a q , niin merkitään Kij:llä niiden koodisajen lukumäärää, joiden i:s symboli on aj. Silloin q

K =

∑ K ij j=1

n

ja

dtotal (C ) =

q

n

q

∑ ∑ K ij(K − K ij ) = nK − ∑ ∑ K 2ij , i=1 j=1

2

i=1 j=1

eikö totta. Toisaalta Cauchy–Schwarzin epäyhtälön (ks. peruskurssit) nojalla

*

“MDS” = “maximum distance separable”

61  n q   1 ⋅ K ij     i=1 j=1 

2

∑∑

 n q  n q  2 2  K ij ≤ 1     i=1 j=1   i=1 j=1 

∑∑

∑∑

eli 2 2

n K ≤ nq

n

q

∑ ∑ K 2ij , i=1 j=1

(missä yhtäläisyysmerkki on voimassa tarkalleen silloin, kun kaikki Kij:t saavat saman arvon (=K/q)). Näin ollen d total(C ) ≤ nK2

q – 1 q .

Koska ilmeisesti on d total (C ) d min (C ) ≤ K(K – 1) , saadaan

L AUSE 23. (PLOTKIN -RAJA ) (n,K,d)-koodille nK(q – 1) d ≤ (K – 1)q

eli

K(q – 1) q – 1 λ ≤ (K – 1)q = . ■ q(1 – q –nρ )

Näin ollen, jos halutaan saavuttaa tietty virheenkorjaussuhde λ > 1 – 1/q, pitää olla qλ 1 ρ ≤ n logq . qλ – q + 1

Tietyssä mielessä asymptoottinen Plotkin-raja on siis λ ≤ 1 – 1/q + ε n . Toisaalta Plotkin-rajaa ovelasti käyttäen saadaan parempiakin rajoja. Ilmeisesti C :ssä on ainakin K/qT = qk – T sellaista koodisanaa, joiden T ensimmäistä symbolia ovat samat. Valitaan nimenomaan K′ = qk – T sellaista sanaa ja muodostetaan niistä n – T-pituinen koodi C ' poistamalla kustakin sanasta T ensimmäistä symbolia. C ′ on ns. C :stä lyhennetty koodi. Tällöin dmin (C ) ≤ dmin (C ′). Valitsemalla nyt T sopivasti saadaan todistettua L AUSE 24. (PARANNETTU P LOTKIN -RAJA ) (n,qk ,d)-koodille C

62 n − k + log q k   1 1 d ≤ 1 −  ( n − k ) + 1 −  log q k + (q − 1). q q k−q    1 Asymptoottisesti λ ≤ 1 −  (1 – ρ) + ε n . q  Todistus. Merkitään l = log q k ja valitaan koodia C lyhennettäessä T:ksi k – l. Sovelletaan näin saadulle (n – T,K′,d′)-koodille C ′ Plotkin-rajaa ja arvioidaan ylöspäin: d min (C ) ≤ d min (C ′ ) ≤

( n − T )K ′(q − 1) (K ′ − 1)q

 ( n − T )(q − 1) 1 = 1 −  ( n − T ) + (K ′ − 1)q q  n − k + log q k   1 1 (q − 1). ≤ 1 −  ( n − k ) + 1 −  log q k + q q k−q   Asymptoottinen raja seuraa tästä. ■

Hamming-raja R-säteisessä koodisanakeskisessä pallossa B(c,R) on sanoja V(R ) =

R

∑  ni  (q − 1)i i=0

kpl, eikö totta. Tätä yksinkertaista tietoa käyttäen saadaan

L AUSE 25. (HAMMING -RAJA ) Jos (n,K,d)-koodi C korjaa t virhettä, niin ρ ≤1−

1 log q V( t ). n

Todistus. Jos nyt olisi KV(t) > qn , niin d < 2t + 1 eikä C korjaisi t virhettä. Siispä KV(t) ≤ qn eli V(t) ≤ qn – k eli logq V(t) ≤ n – k. ■ Hamming-koodit ovat Hamming-rajalla. Hamming-rajan asymptoottisen muodon saamiseksi pitää arvioida V(t):tä. Merkitään lyhyyden vuoksi

63 n A i =  i  (q − 1)i  

(i = 0,1,…,t).

Silloin V(t) ≥ At. Ns. heikon Stirlingin kaavan (ks. kurssi nen analyysi 1) mukaan jj j j+1 ≤ j! ≤ . e j−1 e j−1

73265 Symboli-

Sovelletaan tätä At:n binomikertoimeen:  q − 1 1 1 1 ( n t − 1) (q − 1)t = At ≥   . n n−t et(n − t ) (1 − t n ) et(n − t ) (1 − t n )  tn  t

t

Silloin nähdään, että 1 1 1  t log q A t ≥ log q + Hq ,  n n n et( n − t ) missä Hq(x) on entropiafunktio H q (x) = – (1 – x) log q (1 – x) – x log q

x q – 1

1 log q ( et(n − t )) → 0, kun n → ∞, joten se “kuuluu n 3 t λ < < ja entropiafunktio on jatkuva funktio, joten 2n n 2

(vrt. VII.3). Tässä − λ 2

osaan ε n ”. Nyt

−

Hamming-rajan asymptoottinen muoto on ρ ≤ 1 – H q (λ/2) + εn . Muita ylärajoja Yhdistämällä Plotkin-rajaa sekä Hamming-rajaa johdettaessa käytettyjä menetelmiä saadaan vahvempi raja, ns. Elias-raja (asymptoottinen)  1 q  ρ ≤ 1 − Hq  1 −  1 − 1 − λ + εn q q − 1    (ks. esimerkiksi VAN L INT ). Edelleen menetelmiä terästämällä saadaan eräs parhaita tunnetuista asymptoottisista ylärajoista, ns. McEliece– Rodemich–Rumsey–Welch-raja    1 2 2 ρ ≤ Hq 1 − − λ 1 −  − λ(1 − λ )(q − 1) + ε n q q q   

64 (binäärisen koodin tapauksessa ks. esimerkiksi VAN LINT, yleisen tapauksen todistikin* muuten suomalaismatemaatikko Matti Aaltonen).

3. Alarajoja Ylärajat määrittävät alueita, joilla mielivaltaisen (n,K,d)-koodin parametrikolmikko (n,K,d) (tai vastaavasti (n,ρ,λ)) ei voi olla. Alarajojen tarkoituksena on antaa alueita, joilla (n,K,d)-koodeja on.

Gilbert-raja

L AUSE 26. (GILBERT -RAJA ) Jos V(d – 1)
ω. Jos Yi:ssä on nyt T merkitsemätöntä polkua p1,…,pT (paremmuusjärjestyksessä), merkitään vielä nämä polut ja asetetaan i ← i + 1 sekä Yi ← [p1,…,pT). Mennään kohtaan (3). ( 2 . 2 ) Jos merkitsemättömiä polkuja ei ole tarpeeksi ja i ≥ 1, poistetaan pino Yi, asetetaan i ← i – 1 ja palataan kohtaan (2). (2.3) Jos merkitsemättömiä polkuja ei ole tarpeeksi ja i = 0, tulostetaan W:n P – M ensimmäistä termiä ja lopetetaan.

(3)

Käydään läpi “tavallinen” pinoalgoritmi pinossa Y i , jonka maksimikorkeus on K. (3.1) Jos tämä tuottaa tuloksena polun p juuresta lehteen v, niin poistetaan pino Yi ja asetetaan i ← i – 1. Jos vielä w( p ) < ω , asetetaan W ← A(v) ja ω ← w(p ). Mennään kohtaan (2). (3.2) Jos taas pino Yi täyttyy, mennään kohtaan (2).

84 Käytännössä kaikkien yhtaikaa käytössä olevien pinojen yhteiskorkeudelle pitää asettaa maksimi ja lopettaa, kun tämä saavutetaan. Jos tällöin ω < ∞ eli on löytynyt polku p juuresta lehteen, tulostetaan W:n P – M ensimmäistä termiä. Jos ω = ∞, ei dekoodausta voitu suorittaa lainkaan! Monipinoalgoritmin etuna verrattuna “tavalliseen” pinoalgoritmiin on vähäisempi muistitilan tarve ja matalien lisäpinojen nopea lajiteltavuus.

Fano-dekoodaus Fano-dekoodauksessa verrataan kulloinkin tutkittavan polun p painoa tiettyyn kynnysarvoon σ ja polkua jatketaan niin kauan kuin kynnysarvo ei ylity. Kynnysarvon ylityttyä palataan polkua takaisin yhden oksan verran ja yritetään jatkaa sitä jotain toista oksaa pitkin, jne.. Jos tämäkään ei onnistu, nostetaan lopulta kynnysarvoa tietyllä lisäyksellä δ ja jatketaan, kunnes polku juuresta lehteen on löytynyt. Merkitään S(p):llä kaikkia polusta p yhdellä oksalla jatkamalla saatujen polkujen joukkoa ja N(p ):llä kaikkien polusta p viimeisen oksan osalta eroavien polkujen joukkoa. I(p ):llä taas merkitään polkua, joka saadaan poistamalla p :stä viimeinen oksa. Jotta saataisiin S(p):n ja N(p):n polut järjestettyä “paremmuusjärjestykseen”, menetellään seuraavasti: Määritellään ensin järjestys kaikille mahdollisille syötevektoreille. Tämä järjestäminen on mielivaltainen, mutta sen pitäisi olla laskennallisesti nopeasti testattavissa. Määritellään sitten järjestys p poluille: p p q , jos joko w(p ) < w(q ) tai sitten on w(p ) = w( q ) ja p :n viimeistä oksaa vastaava syötevektori on järjestyksessä pienempi kuin q:n vastaava. Huomaa, että p todella järjestää S(p ):n ja N(p ):n polut paremmuusjonoon.

(1)

Asetetaan σ ← 0 ja p ← o (tyhjä polku, jonka alku- ja loppupiste on koodauspuun juuri).

(2)

Jos p on polku juuresta lehteen v, tulostetaan A(v):n P – M ensimmäistä termiä ja lopetetaan. Muussa tapauksessa muodostetaan S(p ):n polut ja valitaan niistä paras polku q ( p:n suhteen).

(3)

Jos w(q) ≤ σ, asetetaan p ← q ja mennään kohtaan (2).

(4)

Jos p = o , asetetaan σ ← σ + δ ja mennään kohtaan (2). Muussa tapauksessa muodostetaan N(p):n polut.

(5)

(5.1) Mikäli N(p):ssä on polkuja, joiden paino ei ylitä kynnysarvoa σ, valitaan näistä poluista paras sellainen polku r, joka toteuttaa ehdon p p r, asetetaan p ← r ja mennään kohtaan (2). (Huomaa, miten vaatimus p p r estää jo kokeiltujen polkujen uudelleen valitsemisen.)

(5.2) Jos taas kaikkien ehdon p p r toteuttavien N(p ):n polkujen r painot ylittävät kynnysarvon σ, asetetaan p ← I(p) ja mennään kohtaan (4).

Fano-dekoodaus käyttää muistitilaa minimaalisen vähän. Sen sijaan siltä saattaa kulua hyvinkin paljon aikaa koodauspuussa “kulkemiseen”. (Ilmankos HEISE & QUATTROCCHI käyttääkin nimeä “Decodiereraffe”.) Etsintämielessä Viterbi-dekoodaus sekä m-algoritmi ovat “breadth–firsttyyppisiä”, pinoalgoritmi on “best–first-tyyppinen” ja Fano-dekoodaus taas “depth–first-tyyppinen” (ks. kurssi 73119 Graafiteoria). Monipinoalgoritmi on “best–first-depth–first-hybridi”. Lähemmin konvoluutiokoodauksen dekoodausta käsitellään viitteissä ANDERSON & MOHAN, LIN & COSTELLO, MCELIECE ja VITERBI & OMURA.

85

86

V I I LUKU INFORMAATIO

JA ENTROPIA

1. Ekskursio: Diskreetti todennäköisyys Kerrataan joitakin tilastomatematiikan kurssin käsitteitä ja otetaan käyttöön uusia merkintöjä. Jos A ja B ovat tapauksia, niin 1)

A ∪ B = {A tai/ja B tapahtuu};

2)

A ∩ B = {A ja B molemmat tapahtuvat};

3)

A ja B ovat erilliset, jos P(A ∩ B) = 0;

4)

P(A ∪ B) = P(A) + P(B) – P(A ∩ B);

5)

A:n todennäköisyys, kun B:n tiedetään tapahtuvan, (ehdollinen todennäköisyys) on P(A ∩ B) = P(A|B). P(B)

6)

Jos siis P(B) ≠ 0, niin P(A ∩ B) = P(A|B)P(B). Kaava yleistyy, sillä P(A1 ∩⋅⋅⋅∩ An) = P(A1|A2 ∩⋅⋅⋅∩ An)P(A2 ∩⋅⋅⋅∩ An) = P(A1|A2 ∩⋅⋅⋅∩ An)P(A2|A3 ∩⋅⋅⋅∩ An)P(A3 ∩⋅⋅⋅∩ An) =⋅⋅⋅= P(A1|A2 ∩⋅⋅⋅∩ An)P(A2|A3 ∩⋅⋅⋅∩ An)⋅⋅⋅P(An – 1|An)P(An).

7)

Tapaukset A ja B ovat riippumattomat, jos P(A ∩ B) = P(A)P(B). Muussa tapauksessa ne ovat riippuvat. Jos A ja B ovat riippumattomat ja P(B) ≠ 0, niin P(A|B) = P(A).

87 SUURTEN LUKUJEN LAKI. Toistetaan (stokastista) koetta, jossa suotuisan tapauksen todennäköisyys on p. Merkitään Sn:llä suotuisien tapausten lukumäärää n koetoistossa (toistot ovat riippumattomat). Kaikille positiiviluvuille ε ja δ (miten tahansa pienille) on olemassa sellainen vakio Nε,δ, että  S  P  n − p < ε  > 1 − δ , kun n > Nε,δ. ■  n  Tapaukset A1,…,An muodostavat täydellisen tapausjärjestelmän, jos (i)

P(A 1 ) +⋅⋅⋅+ P(An ) = 1 ja

(ii)

P(Ai ∩ Aj) = 0, kun i ≠ j, ts. tapaukset ovat parittain erilliset.

K OKONAISTODENNÄK ö ISYYSKAAVA . Jos A1,…,A n on täydellinen tapausjärjestelmä, niin n

P(B) =

n

∑ P(B ∩ A i ) = ∑ P(B A i )P( A i ). i=1

■

i=1

Jos S 1: A1,…,An ja S 2: B1,…,B m ovat täydellisiä tapausjärjestelmiä, niin samoin on yhteistapausjärjestelmä S 1 ∩ S 2: Ai ∩ Bj (i = 1,…,n;j = 1,…,m). Ensinnäkin Kokonaistodennäköisyyskaavan nojalla n

m

n

∑ ∑ P( A i ∩ B j ) = ∑ P( A i ) = 1, i=1 j=1

i=1

ja toiseksi, jos i1 ≠ i2 tai/ja j1 ≠ j2, niin P ( (A i1 ∩ Bj1 ) ∩ (Ai2 ∩ Bj2 ) ) = P( (A i1 ∩ Ai2 ) ∩ (Bj1 ∩ Bj2 ) ) = 0. Olettaen, että P(B1),…,P(Bm) ≠ 0, saadaan ehdollinen tapausjärjestelmä S 1|S 2 : Ai|B j (i = 1,…,n;j = 1 ,…,m). Tämä ei ole täydellinen tapausjärjestelmä, vaan oikeastaan m:n täydellisen tapausjärjestelmän S 1|Bj : A1|Bj,…,An|Bj kokoelma. Vastaavasti saataisiin S 2|S 1.

(j = 1 ,…,m)

88 Laskettaessa (esimerkiksi Matlab-ohjelmistolla) on kätevää siirtyä vektori/matriisinotaatioon. Täydellisen tapausjärjestelmän S 1: A1,…,An todennäköisyydet P(A 1 ) = p1 ,…, P(An ) = pn kirjoitetaan tapausjärjestelmän todennäköisyysvektoriksi p = (p1 ,…,p n ). Vastaavasti kahden tapausjärjestelmän S 1: A1,…,An ja S 2: B1,…,Bm yhteistapausjärjestelmän S 1 ∩ S 2 todennäköisyydet P(A i ∩ Bj) = pij

(i = 1,…,n;j = 1,…,m)

kirjoitetaan todennäköisyysmatriisiksi  p11 L p1m  P =  M O M . p L p   n1 nm  Ehdollisen tapausjärjestelmän todennäköisyydet P(A i|B j) = pi|j

(i = 1,…,n;j = 1,…,m)

voidaan myös kirjoittaa ns. ehdolliseksi todennäköisyysmatriisiksi  p11 L p1 m  . Q= M O M p  L p nm  n1 Jos otetaan käyttöön myös S 2:n todennäköisyysvektori q = (q1 ,…,q m ), missä P(B 1 ) = q1 ,…, P(Bm ) = qm , sekä ykkösvektori 1n = (1,…,1 123 ), n kpl

niin (Kokonaistodennäköisyyskaavan nojalla) saadaan seuraavat yhtälöt: p = 1 m P T , q = 1n P, p = qQ T,

P = Qq,

89 Q=

Pq–1

(tässä q on lävistäjämatriisi, joka saadaan ottamalla lävistäjäalkioiksi q:n komponentit). Jos p ja Q tunnetaan, mutta ei q:ta (eikä P:tä), niin se voidaan ratkaista (tai ainakin löytää jokin q) yhtälöstä p = qQT. Huomaa, että tällöin automaattisesti 1mqT = 1nQqT = 1npT = 1. Lasketaan Matlabilla esimerkki:

P = 0.0187 0.0402 0.0212 0.0287

0.0001 0.0185 0.0667 0.0201

0.0753 0.0405 0.0488 0.0037

0.0222 0.3014 0.1739 0.0806

0.0042 0.0143 0.0086 0.0122

0.4149

0.3193

0.1453

0.1055

0.1683

0.5781

0.0393

0.4473 0.2405 0.2900 0.0222

0.0384 0.5213 0.3009 0.1394

0.1078 0.3638 0.2194 0.3090

»p=sum(P') p = 0.1205 »q=sum(P) q = 0.1088

»Q=P*inv(diag(q)) Q = 0.1716 0.3693 0.1950 0.2641

0.0009 0.1758 0.6329 0.1904

Jos q ei olisi tunnettu, voitaisiin yrittää etsiä se käyttäen Q T:n yleistettyä käänteismatriisia, ensin Moore–Penrose-inverssiä ja sitten pienimmän neliösumman inverssiä:

»p*pinv(Q') ans = 0.0937

0.1040

0.1708

0.5788

0.0527

0.0948

0.1865

0.5835

0.1351

»p/Q' ans = 0

90 2. Informaatio Tapauksen A (itse)informaatio on –log P(A) = I(A). Varman tapauksen informaatio on siis 0 ja mahdottoman tapauksen ∞. Logaritmin kantaluku määrää informaation yksikön. Mikä tahansa kantaluku a > 1 on mahdollinen. Tavallisimmat valinnat ovat a = 2: a = e: a = 10:

I(A) = –log2 P(A) bittiä I(A) = –ln P(A) nattia I(A) = –lg P(A) dittiä

Yksikön vaihto käy tavalliseen tapaan: log2 x ln x lg x log2 a = ln a = lg a = loga x.

3. Entropia Täydellisen tapausjärjestelmän S : A1,…,An entropia on n

H( S ) =

∑ I( A i )P( A i ), i=1

ts. entropia on järjestelmän tapausten keskimääräinen informaatio. Entropian yksikkö on sama kuin käytetty informaation yksikkö. Tässä sovitaan, että 0 log 0 = 0. Tämä on sopusoinnussa sen peruskursseilta tutun seikan kanssa, että lim x ln x = 0. x→ 0+ Jos p =(p1,…,pn) on S :n todennäköisyysvektori, niin n

H( S ) = −

∑ pi log pi = −p log p T , i=1

kun merkitään log p = (log p 1,…,log p n ). Vastaavasti, jos kyseessä on yhteistapausjärjestelmä S 1 ∩ S 2, jonka todennäköisyysmatriisi on P, niin n

H( S1 ∩ S 2 ) = −

m

∑ ∑ pij log pij = −trace(P log P T ), i=1 j=1

91

missä * on merkitty  log p11 L log p1m  O M log P =  M  .  log p L log p  n1 nm  Esimerkiksi yo.

Matlab-esimerkissä

»H=-p*log(p')/log(2) H = 1.8247 »HS12=-trace(P*log(P'))/log(2) HS12 = 3.3843

(yksikkönä bitti). Merkitään g(p) = –p log p. Silloin ilmeisesti g(0) = g(1) = 0 ja g(p) > 0, kun 0 < p < 1. H(S ) on näin ollen ei–negatiivinen ja H(S ) = 0 tarkalleen siinä tapauksessa, että yksi todennäköisyyksistä p1 ,…,p n on =1 muiden ollessa =0. g(p):n maksimiarvo leen voidaan todeta, että jos p

1 bittiä saavutetaan, kun p = 1/e. e ln 2 = p1 + p2 ja p1,p2 ≠ 0, niin (nateissa)

Edel-

p1 p2 g(p) = –(p1 + p2) ln p = p1 ln p + p2 ln p + g(p1 ) + g(p2 ) < g(p1 ) + g(p2 ). Piirretään vielä

*

Maplella g(p):n kuvaaja (biteissä):

Matriisin trace eli jälki on sen lävistäjäalkioiden summa. Seuraavat tracen ominaisuudet ovat helposti todettavissa: (i)

trace(A + B) = trace(A) + trace(B),

(ii)

trace(AT) = trace(A),

(iii)

trace(cA) = c trace(A), kun c on vakio,

(iv)

trace(AB) = trace(BA),

(v)

trace(ABT) =

n m

∑ ∑ a ijb ij , kun A = (aij ) ja B = (bij ).

i=1 j=1

Ominaisuus (v) antaa matriisien skalaaritulon, jota nimenomaan käytetään laskettaessa entropiaa H(S 1 ∩ S 2 ).

92 0.5

0.4

0.3

0.2

0.1

0

0.2

0.4

0.6

0.8

p 1

0

APULAUSE. ln x ≤ x – 1, kun x > 0. Yhtäsuuruus esiintyy vain x:n arvolla 1. Todistus. Funktion x – 1 – ln x ainoa ääriarvo on pisteessä x = 1 oleva minimiarvo 0. ■ LAUSE 30. H(S ) ≤ log n. Yhtäsuuruus esiintyy vain tapauksessa p1 =⋅⋅⋅= pn. Todistus. Jos pi = 0, niin 1 –p i ln n – pi ln p i = 0 < – pi. n Jos taas pi ≠ 0, niin Apulauseen nojalla 1 1 1 – 1 = n – pi –p i ln n – pi ln p i = pi ln np ≤ pi  np i i ja yhtäsuuruus esiintyy vain jos pi = 1/n. Näin ollen n

n

i=1

i=1

∑ (−pi ln n − pi ln pi ) ≤ ∑

1 −p  = i n

n

∑ i=1

1 − n

n

∑ pi = 1 − 1 = 0 i=1

93 ja yhtäsuuruus esiintyy vain tapauksessa p1 =⋅⋅⋅= pn = 1/n. Edelleen (nateissa) H( S ) = −

n

n

n

i=1

i=1

i=1

∑ pi ln pi ≤ ∑ pi ln n = ln n ∑ pi = ln n

ja yhtäsuuruus pätee vain ym. tapauksessa. Muille informaatioyksiköille tulos saadaan kertomalla puolittain sopivalla vakiolla. ■ Entropia on maksimissaan kun kaikki mahdollisuudet (tapausjärjestelmä) ovat yhtä todennäköisiä, ts. (a priori) epävarmuus tuloksesta on suurin. Entropia on epävarmuuden mitta: mitä suurempi entropia sitä epävarmempaa on tulos. Jotta kokeesta saataisiin mahdollisimman paljon tulosta, se kannattaa asettaa siten, että epävarmuus kokeen tuloksesta on ennalta suuri (maksimientropiaperiaate, ks. Luku X). Mukana voi olla lisäehtoja, jolloin Lauseen 30 antamaa suurinta entropiaa ln n nattia ei voida saavuttaa. Tällöin entropia maksimoidaan annettujen lisäehtojen puitteissa. Katsotaan paria entropian kasvattamiseen liittyvää asiaa. Valitaan täydelliset tapausjärjestelmät S : A1,A2,A3,…,An ;

S ': A1 ∪ A2,A3,…,An

ja

S ": B,C,A3,…,An ,

missä p1 = P(A1 ) < P(B) < P(C) < P(A2 ) = p2 . Koska g(p1 + p2 ) < g(p1 ) + g(p 2 ), on H(S ) > H(S '). Entropian kasvattamiseksi pitää siis aina jakaa tilanteet osiin mahdollisuuksien mukaan. Merkitään nyt q1 = P(B) ja q2 = P(C) sekä q1 – p1 = w, jolloin myös p2 – q2 = w (miksi?). Silloin (nateissa) q1 q2 g(p 1 ) + g(p2 ) – g(q1 ) – g(q2 ) = p1 ln p + p2 ln p + w ln 1 2  q1   q2  q q ≤ p1  − 1 + p2  − 1 + w ln 1 = w ln 1 < 0, q2 q2  p1   p2 

q1 q2

ts. H(S ") > H(S ). Jaettaessa tilanteita ym. tavalla osiin, kannattaa entropian maksimoimiseksi siis pyrkiä mahdollisimman tarkasti yhtä todennäköisiin osiin.

4. Ehdollinen entropia. Keskinäisinformaatio Tapauksen A ehdollinen informaatio ehdolla, että B on tapahtunut, on –log P(A|B) = –log

p(A ∩ B) P(B) = –log P(A ∩ B) + log P(B)

= I(A ∩ B) – I(B)

= I(A|B)

94

(olettaen tietysti, että P(B) ≠ 0). Tarkastellaan kahta täydellistä tapausjärjestelmää S 1 : A1,…,An

ja

S 2 : B1,…,Bm

ja yhteistapausjärjestelmää S 1 ∩ S 2 : Ai ∩ Bj (i = 1,…,n;j = 1,…,m). S 1:n ehdollinen entropia ehdolla S 2 on n

H( S1 S 2 ) =

m

I( A i B j )P ( A i ∩ B j ). ∑ ∑ j=1 i=1

P(B j )≠0

Ehdollinen entropia H(S 1|S 2) on S 1:n tapausten keskimääräinen ehdollinen informaatio S 2:n tapauksilla ehdollistettuina. Odotusarvo (eli keskiarvo) otetaan yli yhteistapausjärjestelmän S 1 ∩ S 2. H(S 1|S 2) kuvaa näin ollen S 1:n keskimääräistä epävarmuutta, kun S 2:n tulos tiedetään. Merkitään S 1 :n ja S 2 :n todennäköisyysvektoreita p:llä ja q:lla sekä yhteistapausjärjestelmän todennäköisyysmatriisia ja ehdollista todennäköisyysmatriisia P:llä ja Q:lla. Jos P(Bj) = qj ≠ 0, on silloin p ij P(A i|B j) = q j ja p ij I(A i|B j) = –log q . j Mikäli nyt pij = 0 (mutta qj ≠ 0), on luonnollista sopia, että p ij p ij log q = pij log p ij – pij log q j = 0. j Ulotetaan tämä sopimus myös tapaukseen qj = 0 (jolloin myös pij = 0), ts. tällöinkin* *

Myös tämä on sopusoinnussa raja-arvotulosten kanssa. Jos nimittäin P(B) ≠ 0, on P(A ∩ B) = P(A|B)P(B) ≤ P(B). Toisaalta, jos (p,q) → (0,0) ja 0 ≤ p ≤ q, niin 0 ≤ |p ln q| = p|ln q| ≤ q|ln q| = |q ln q| → 0.

95 p ij p ij log q = 0 j ja tietysti myös pij log qj = 0. Näin ollen voidaan kirjoittaa n

H( S1 S 2 ) = −

m

∑ ∑ pij log qijj = −trace(P log Q T ). p

i=1 j=1

Tässä on merkitty  log p11 L log p1 m  . log Q =  M O M  log p  n1 L log p n m   Jatketaan eo.

Matlab-esimerkkiä:

»HS1S2=-trace(P*log(Q'))/log(2) HS1S2 = 1.6205

LAUSE 31. H(S 1|S 2) = H(S 1 ∩ S 2) – H(S 2) Todistus. Kokonaistodennäköisyyskaavan nojalla n

H( S1 S 2 ) = −

m

∑∑p i =1 j=1 n

=−

ij log

pij qj

n

=−

i =1 j=1

∑∑p

m

ij log p ij

+

i =1 j=1

m

∑∑p

m

n

∑∑p

ij log q j

j=1 i =1

m

ij log p ij

+

∑ q log q j

j

= H( S1 ∩ S 2 ) − H( S 2 ). ■

j=1

H(S 1) mittaa S 1:n keskimääräistä epävarmuutta ennen kuin S 2:n tapahtumista tiedetään mitään ja H(S 1 |S 2 ) sen jälkeen. Erotus H(S 1 ) – H(S 1|S 2) mittaa jonkinlaista järjestelmien “yhteistä” informaatiota. Täydellisten tapausjärjestelmien S 1 ja S 2 keskinäisinformaatio on H(S 1 ) – H(S 1 |S 2 ) = I(S 1 ,S 2 ). Lauseen 31 nojalla H(S 1 |S 2 ) + H(S 2 ) = H(S 1 ∩ S 2 ) = H(S 2 ∩ S 1 ) = H(S 2 |S 1 ) + H(S 1 )

96 eli H(S 1 ) – H(S 1 |S 2 ) = H(S 2 ) – H(S 2 |S 1 ). Näin ollen I(S 1 ,S 2 ) = I(S 2 ,S 1 ), ts. tapausjärjestelmien keskinäisinformaatio ei riipu niiden järjestyksestä. Lauseen 31 nojalla edelleen I(S 1 ,S 2 ) = H(S 1 ) + H(S 2 ) – H(S 1 ∩ S 2 ). Vielä Lauseesta 31 saadaan kaava I(S 1,S 2) = H(S 1 ∩ S 2) – H(S 1|S 2) – H(S 2|S 1).

H(S 2)

H(S 2|S 1)

I(S 1,S 2)

H(S 1)

H(S 1|S 2)

Kaaviona:

H(S 1 ∩ S 2)

n

LAUSE 32. I( S1, S 2 ) =

m

∑∑ i=1 j=1

pij log

pij piq j

= trace (P log (Q T p–1 ))

(Jälleen sovitaan, että jos jokin todennäköisyyksistä pij, pi tai qj on =0, niin ko. termi summassa on =0. Huomaa, että jos pi = 0 tai/ja qj = 0, niin myös pij = 0.) Todistus. Kokonaistodennäköisyyskaavan mukaisesti I( S1, S 2 ) = H( S1 ) + H( S 2 ) − H( S1 ∩ S 2 ) =−

n

m

i=1

j=1

n

m

∑ pi log pi − ∑ q j log q j + ∑ ∑ pij log pij i=1 j=1

97 n

=−

m

m

n

m

∑ ∑ pij log pi − ∑ ∑ pij log q j + ∑ ∑ pij log pij i=1 j=1

n

=

n

j=1 i=1

m

∑ ∑ pij log piqij j . p

i=1 j=1

■

i=1 j=1

Tapausjärjestelmien S 1 ja S 2 sanotaan olevan riippumattomat, jos p ij = pi q j

(i = 1,…,n;j = 1,…,m)

eli P = p T q, ts. jos järjestelmien tapaukset ovat parittain keskenään riippumattomat.

L AUSE 33. Jos S 1 ja S 2 ovat riippumattomat, niin I(S 1 ,S 2 ) = 0 (ja siis seurauksena H(S 1|S 2) = H(S 1) sekä H(S 2|S 1) = H(S 2) ja H(S 1 ∩ S 2) = H(S 1 ) + H(S 2 )). Todistus. Seuraa suoraan Lauseesta 32. ■

Yleisesti on voimassa L AUSE 34. H(S 1 |S 2 ) ≤ H(S 1 ) ja yhtäsuuruus pätee tarkalleen silloin, kun S 1 ja S 2 ovat riippumattomat. Sama asia toisin: I(S 1 ,S 2 ) ≥ 0 ja yhtäsuuruus pätee tarkalleen silloin, kun S 1 ja S 2 ovat riippumattomat. Todistus. Jos pij = 0, niin pij –p ij ln p q = 0 ≤ piq j – 0 = piq j – pij i j ja yhtäsuuruus esiintyy tarkalleen silloin, kun piqj = 0 = pij. Jos taas pij ≠ 0 (jolloin myös pi ≠ 0 ja qj ≠ 0), niin sivun 92 Apulauseen nojalla p iq j pij p iq j –p ij ln p q = pij ln p ≤ pij  p – 1 = pi q j – pij i j ij ij ja yhtäläisyys esiintyy tarkalleen silloin, kun pij = piqj. Näin ollen nateissa n

m

n m  pij  −I( S1, S 2 ) = (pi q j − pij )  −pij ln p q  ≤ i j  i=1 j=1 i=1 j=1

∑∑

∑∑

98 =

n

m

i=1

j=1

n

m

∑ pi ∑ q j − ∑ ∑ pij = 0 i=1 j=1

ja yhtäsuuruus pätee tarkalleen silloin, kun se pätee kaikille yhteenlaskettaville eli tarkalleen silloin, kun p ij = pi q j

(i =1,…,n;j =1 ,…,m)

eli tarkalleen silloin, kun S 1 ja S 2 ovat riippumattomat. Lause pätee siis nateille ja näin ollen muillekin informaatioyksiköille. ■

Määritelmästä seuraa, että I(S 1 ,S 2 ) ≤ min (H(S 1 ),H(S 2 )).

5. Kolme tapausjärjestelmää: Data–Processing-lause Tarkastellaan kolmea täydellistä tapausjärjestelmää S 1 : A1,…,An ;

S 2 : B1,…,Bm

ja

S 3 : C1,…,Cr.

Yleisesti, jos P(C) ≠ 0 ja S : D1,…,Ds on täydellinen tapausjärjestelmä, niin S |C : D1|C ,…, Ds|C on myös täydellinen tapausjärjestelmä. Näin ollen S 1 |C k ja S 2 |C k ovat täydellisiä tapausjärjestelmiä, mikäli P(Ck) ≠ 0 (k = 1,…,r). Keskinäisinformaatio I(S 1|Ck,S 2|Ck) mittaa S 1:n ja S 2:n keskimääräistä “yhteistä” informaatiota, kun tietyn S 3 :n tapauksen Ck tiedetään sattuneen. Keskimäärin S 1 :n ja S 2 :n “yhteinen informaatio”, kun tiedetään S 3:n tapauksen sattuneen, on r

I( S1 Ck , S 2 Ck )P(Ck ) = I( S1, S 2 S 3 ), ∑ k=1 P(C k )≠0

ns. S 1:n ja S 2:n ehdollinen keskinäisinformaatio ehdolla S 3. Jos S 1 |C k ja S 2 |C k ovat riippumattomat kaikille k:n arvoille k = 1,…,r, joille P(Ck ) ≠ 0, ovat S 1 ja S 2 riippumattomat ehdolla S 3 . Ts. S 1 ja S 2 ovat riippumattomat ehdolla S 3, jos

99

P(A i ∩ Bj|C k ) = P(Ai|C k )P(B j|C k ) (i = 1,…,n;j = 1,…,m;k = 1,…,r ja P(Ck ) ≠ 0). Jos P(Ck) ≠ 0, niin Lauseen 34 nojalla I(S 1,S 2|Ck) ≥ 0 ja yhtäläisyys pätee tarkalleen silloin, kun S 1 |C k ja S 2 |C k ovat riippumattomat. Näin ollen saadaan välittömästi L AUSE 35. I(S 1,S 2|S 3) ≥ 0 ja yhtäläisyys pätee tarkalleen silloin, kun S 1 ja S 2 ovat riippumattomat ehdolla S 3. ■ Lauseen 32 mukaan (olettaen, että P(Ck) ≠ 0) n

I( S1 Ck , S 2 Ck ) =

m

P( A ∩ B C )

∑ ∑ P( A i ∩ B j Ck ) log P( A i Ci k )P(Bj j kCk ) i=1 j=1 n

=

m

∑∑ i=1 j=1

P( A i ∩ B j ∩ Ck ) P(Ck )

log

P( A i ∩ B j Ck ) P( A i Ck )P(B j Ck )

(missä yhteenlaskettava on =0, jos jokin esiintyvistä todennäköisyyksistä on nolla). Näin ollen r

I( S1, S 2 S 3 ) =

n

m

P( A ∩ B C )

∑ ∑ ∑ P( A i ∩ B j ∩ Ck ) log P( A i Ci k )P(Bj j kCk ) ,

k=1 i=1 j=1

missä yhteenlaskettava on =0, jos jokin esiintyvistä todennäköisyyksistä on =0. (Huomaa, että jos P(Ck) = 0, niin myös P(Ai ∩ Bj ∩ Ck) = 0.) LAUSE 36. I(S 1,S 2|S 3) = I(S 1 ∩ S 3,S 2) – I(S 2,S 3) Todistus. Kokonaistodennäköisyyskaavan nojalla r

I( S1, S 2 S 3 ) =

n

P( A i ∩B j ∩C k )

m

∑ ∑ ∑ P( A i ∩ B j ∩ Ck ) log P( A ∩CP(C) P(B) ∩C k

i

k=1 i=1 j=1 r n m

k

P(C k )

j

k)

P(C k )

 P( A i ∩ B j ∩ Ck ) P(B j ∩ Ck )  P( A i ∩ B j ∩ Ck ) log − log P( A i ∩ Ck )P(B j ) P(B j )P(Ck )   k=1 i=1 j=1 n r m P ( A i ∩ Ck ) ∩ B j ) = P ( A i ∩ Ck ) ∩ B j log P( A i ∩ Ck )P(B j ) =

∑∑∑

∑∑∑ ( i=1 k=1 j=1

)

(

)

100 m

−

r

n

P(B ∩ C )

∑ ∑ ∑ P( A i ∩ B j ∩ Ck ) log P(B jj)P(Ckk ) j=1 k=1 i=1

= I( S1 ∩ S 3 , S 2 ) − I( S 2 , S 3 ). ■

L AUSE 37. (DATA –P ROCESSING – LAUSE ) Jos S 1 ja S 2 ovat riippumattomat ehdolla S 3, niin I(S 1 ,S 2 ) ≤ I(S 2 ,S 3 )

ja

I(S 1 ,S 2 ) ≤ I(S 1 ,S 3 ).

Todistus. Jos S 1 ja S 2 ovat riippumattomat ehdolla S 3 , niin (Lause 35) I(S 1, S 2|S 3) = 0. Lauseen 36 nojalla on tällöin I(S 1 ∩ S 3,S 2) = I(S 2,S 3). Toisaalta (Lause 36, vaihdetaan S 1 ja S 3 keskenään) I(S 1 ∩ S 3,S 2) = I(S 3 ∩ S 1,S 2) = I(S 3,S 2|S 1) + I(S 2,S 1) ≥ I(S 1,S 2). Siis I(S 1,S 2) ≤ I(S 2,S 3). Vaihtamalla S 1 ja S 2 keskenään saadaan I(S 1 , S 2 ) = I(S 2 ,S 1 ) ≤ I(S 1 ,S 3 ). ■ Lauseen nimi tulee seuraavasta tulkinnasta. Tapausjärjestelmä S 1 liittyy tietojen syöttöön, S 2 tulostukseen prosessoinnin jälkeen ja S 3 välitilaan prosessoinnin aikana. (Mieti miten riippumattomuusoletus liittyy tähän tilanteeseen.) Lause sanoo tällöin, että tietojen prosessointi ei voi lisätä informaatiota! Prosessoinnilla voi luonnollisesti muokata tietoja huomattavasti käyttökelpoisempaan muotoon. Samalla todistuksella saadaan

L AUSE 38. (KONVEKSISUUSLAUSE ) Jos S 1 ja S 2 ovat riippumattomat ehdolla S 3, niin I(S 2,S 3) ≥ I(S 2,S 3|S 1). Todistus. Edellisen todistuksen nojalla I(S 2 ,S 3 ) = I(S 3 ,S 2 |S 1 ) + I(S 2 ,S 1 ) ≥ I(S 2 ,S 3 |S 1 ). ■ Samantapaisia tuloksia voidaan todistaa useammallekin kuin kolmelle tapaussysteemille (ks. esimerkiksi MCE LIECE).

101 6. Entropian yksikäsitteisyys Informaatioteoria antaa useita perustavaa laatua olevia rajatuloksia tiedonsiirrossa (Data–Processing-lause, koodaus). Nämä menettäisivät merkityksensä, jos edellä oleva informaatiomitta ja entropia olisivat valittavissa oleellisesti toisella tavalla, joka olisi yhtä käyttökelpoinen, mutta johtaisi eri tuloksiin. Näin ei ole! Ajatellaan täydellistä tapausjärjestelmää S : A1,…,An

(n ≥ 2)

jonka todennäköisyysvektori on p = (p1,…,pn). Jos f(p1,…,pn) on S :n entropiaa vastaava suure, niin se toteuttaa seuraavat hyvin luonnolliset vaatimukset: (1)

(jatkuvuus) f(p1,…,pn) on muuttujien p1,…,pn jatkuva funktio, kun pi ≥ 0 (i = 1,…,n) ja p1 +⋅⋅⋅+ pn = 1.

(2)

(symmetrisyys) f(p1,…,p n ) on symmetrinen funktio, ts. muuttujien p1,…,pn järjestyksen vaihtaminen ei muuta funktion arvoa.

(3)

f(p 1 ,…,p n ) saa suurimman arvonsa, kun p1 =⋅⋅⋅= pn = 1/n ja mainittu suurin arvo on ≠0.

(4)

f ei muutu, jos täydelliseen tapausjärjestelmään lisätään mahdoton tapaus An + 1 (jolloin siis pn + 1 = 0), ts. f(p 1 ,…,p n ,0) = f(p1 ,…,p n ).

Viidennen vaatimuksen esittämiseksi tarkastellaan kahta S :stä saatua täydellistä tapausjärjestelmää S ': A1,…,Ai – 1,Ai + 1,…,Aj – 1,C,Aj + 1,…,An) ja S |C : A1|C,…,An|C, missä C = Ai ∪ Aj ei ole mahdoton tapaus. Silloin P(C) = P(Ai ∪ Aj) = P(Ai) + P(Aj) = pi + pj (≠ 0). Edelleen P(A i|C) = sekä vastaavasti

P (A i ∩ (A i ∪ A j)) P(A i ) pi = =p + p P(A i ∪ A j) i j P(A i ∪ A j)

102 pj P(A j|C) = p + p i j ja P(A k |C) =

P (A k ∩ (A i ∪ A j)) =0 P(A i ∪ A j)

(k = 1,…,n;k ≠ i,j).

S ' saadaan samaistamalla Ai ja Aj yhdeksi tapaukseksi Ai ∪ Aj. S |C puolestaan saadaan olettamalla Ai:n tai Aj:n tapahtuneen. On luonnollista vaatia, että S :n entropia = (S ':n entropia) + P(Ai ∪ Aj) × (S |C:n entropia) (muista, että entropia on keskimääräisen epävarmuuden mitta). Näin ollen vaaditaan, että

(5)

(koherenssi) f(p1 ,…,p n ) = f(p1 ,…,p i – 1,pi + 1,…,p j – 1,pi + pj,pj + 1,…,p n ) pi pj + (pi + pj)f  pi + pj , pi + pj ,

kun pi + pj ≠ 0.

L AUSE 39. (INFORMAATIOTEORIAN YKSIKÄSITTEISYYSLAUSE) Jos f toteuttaa eo. ehdot (1)–(5), niin se on muotoa n

f (p1,…,pn ) = −C

∑ pi ln pi , i=1

missä C on positiivinen vakio. Todistus. Merkitään 1

1

g(n) = f( n ,…, n ) ja etsitään ensin g(n):n lauseke. Vaihe 1 Näytetään, että g(n) ≤ g(n + 1): 1

1

1

1

1

1

g(n) = f( n ,…, n ) =(4) f( n ,…, n ,0) ≤(3) f( n + 1 ,…, n + 1) = g(n + 1).

103 Vaihe 2 Etsitään g(n):n lauseke. Yleisesti, jos p ≠ 0, niin p

p

f(p 1 ,…,p n–r ,p,…,p) =(5) f(p1 ,…,p n–r ,p,…,p,2p) + (p + p)f(p + p , p + p) 1

1

= f(p1 ,…,p n – r,p,…,p,2p) + 2pf( 2 , 2) = (5) f(p1 ,…,p n – r,p,…,p,3p) p

2p

1

1

1

1

+ (p + 2p)f( p + 2p , p + 2p) + 2pf( 2 , 2) 1

2

= f(p1 ,…,p n – r,p,…,p,3p) + 3pf( 3 , 3) + 2pf( 2 , 2) . Jatkamalla samalla tavoin saadaan lopulta kaava A

f(p1 ,…,p n – r,p,…,p) = f(p1 ,…,p n – r,rp) 1

+ rpf( r ,

r–1 r )

1

2

1

1

+⋅⋅⋅+ 3pf( 3 , 3) + 2pf( 2 , 2) .

Tätä kaavaa voidaan soveltaa g(n):ään valitsemalla r = n – 1: B

1

1

1

g(n) = f( n ,…, n ) = f( n , +

n–1 n

n–1 n ) 1

n–2

3

1

2

2

1

1

f( n – 1 , n – 1) +⋅⋅⋅+ n f( 3 , 3) + n f( 2 , 2) .

Kaavoista A ja B saadaan näin ollen kaava C

f(p1 ,…,p n – r,p,…,p) = f(p1 ,…,p n – r,rp) + rpg(r)

( B :ssä n:n tilalle r). Jos nyt m ≥ 2 ja r ≥ 2, niin 1

1

1

1

1

1

g(rm ) = f( rm ,…, rm) =C f( rm ,…, rm , r rm) + r rm g(r) 1

1

1

1

1

= (2),C f( rm ,…, rm , r rm , rm – 1) + 2 rm –1 g(r). Jatkamalla samalla tavoin saadaan lopulta kaava D

g(rm ) = g(rm – 1) + g(r)

(tähän tarvitaan rm – 1 yo. operaation toistoa). Edelleen g(r m ) =D g(rm – 1) + g(r) =D g(rm – 2) + 2g(r) =D ⋅⋅⋅ =D g(r) + (m – 1)g(r)

104 eli saadaan kaava E

g(rm ) = mg(r)

(olettaen, että m ≥ 1 ja r ≥ 2). Jos nyt m ≥ 1 ja r ≥ 2, niin voidaan valita sellainen luku t ≥ 1, että 2 t ≤ rm ≤ 2t + 1. Silloin (Vaihe 1)

g(2 t ) ≤ g(rm ) ≤ g(2t + 1)

eli kaavan E nojalla tg(2) ≤ mg(r) ≤ (t + 1)g(2). Tästä näkyy, että g(2) ≥ 0, jolloin (3):n nojalla itse asiassa g(2) > 0. Jaetaan nyt yo. kaksoisepäyhtälö puolittain mg(2):llä: g(r) t + 1 t ≤ g(2) ≤ m . m Toisaalta myös t ln 2 ≤ m ln r ≤ (t + 1)ln 2, joten samoin ln r t + 1 t ≤ ≤ m . m ln 2 Yhdistetään näin saadut kaksi kaksoisepäyhtälöä: t + 1 g ( r ) ln r t + 1 t t – m ≤ g(2) – ≤ m –m . ln 2 m Annetaan tässä m → ∞ (pitäen r “paikoillaan”): g ( r ) ln r = g ( 2 ) ln 2 eli g(2) g(r) = ln 2 ln r . Valitaan nyt C = g(2)/ln 2 > 0, jolloin F

g(r) = C ln r

(r = 2,3,…).

Vaihe 3 Tarkastellaan tapausta, jossa p1,…,pn ovat rationaalilukuja, ts. (tehdään samannimisiksi)

105 mi pi = M

(i = 1,…,n).

Silloin m1 +⋅⋅⋅+ mn = M ja C :n perusteella (valitaan r = mn,mn – 1,… > 1) 1

1

1

1

mn

mn

1

1

mn – 1 M

,pn ) +

f( M ,…, M ) = f( M ,…, M , M ) + M g(mn ) = f( M ,…, M ,

mn – 1 M

g(mn – 1) + pn g(m n )

=⋅⋅⋅= f(p1 ,…,p n ) + p1 g(m 1 ) +⋅⋅⋅+ pn g(m n ). (Jos mi on 0 tai 1, jää vastaava askel pois, ts. sovitaan, että 0g(0) = 0 ja g(1) = 0.) Siis f(p1 ,…,p n ) = g(M) – p1 g(m 1 ) –⋅⋅⋅– pn g(m n ) =F C ln M – p1C ln m1 –⋅⋅⋅– pnC ln mn n

n

i=1

i=1

= C ln M ∑ pi – C ∑ p i ln m i n

n

i=1

i=1

= –C ∑ p i(ln m i – ln M) = –C ∑ p i ln p i. Lause siis pitää paikkansa rationaalisille todennäköisyyksille. Vaihe 4 Siirrytään yleisiin todennäköisyyksiin. Mikä tahansa todennäköisyysvektori (p1,…,pn) saadaan rationaalisten todennäköisyysvektorien raja–arvona (miten?). Koska n

–C ∑ p i ln p i i=1

on jatkuva ja samoin f(p1,…,pn) (vaatimus (1)), seuraa tästä että yleisestikin n

f(p1,…,p n ) = –C ∑ p i ln p i. ■ i=1

Helposti voidaan tietysti todeta, että edellä määritelty entropia H(S ) toteuttaa vaatimukset (1)–(5).

106 7. Jatkuvan satunnaismuuttujan entropia Entropian yleistys täydelliseen tapausjärjestelmään, jossa on numeroituvasti ääretön määrä tapauksia S : A1,A2,…, on suoraviivaista. Jos p1,p2,… ovat vastaavat todennäköisyydet, niin ∞

H( S ) = −

∑ pi log pi . i=1

Huomaa, että tällainen entropia voi olla ääretön, toisin kuin äärelliselle tapausjärjestelmälle. Jos merkitään satunnaismuuttujan x arvoksi i, mikäli Ai tapahtuu, niin sekä äärelliselle että äärettömälle tapausjärjestelmälle S H(S ) = E(–log p x ). Jatkuvalle satunnaismuuttujalle x, jonka tiheysfunktio on f(x), px:ää vastaa differentiaali f(x)dx ja –log(f(x)dx) ei ole määritelty! Jatkuvalle satunnaismuuttujalle ei olekaan samanlaista informaation ja entropian käsitettä kuin diskreeteille satunnaismuuttujille. Jos tavoitteena on vain entropioiden additiivinen vertailu (esimerkiksi maksimientropiamenetelmissä, ks. Luku X), voidaan kuitenkin menetellä seuraavasti. Jaetaan reaaliakseli ∆:n pituisiin väleihin [i∆,(i + 1)∆), i = …,–1,0,1,2,…, ja valitaan kultakin tällaiselta väliltä [i∆,(i + 1)∆ ) piste xi, jolle (i+1)∆

P ( i∆ ≤ x < (i + 1)∆ ) =

∫ f ( x )dx = f ( x i )∆ = pi

i∆

(integraalilaskennan väliarvolauseen nojalla tällainen xi on olemassa). Otetaan tarkasteltavaksi täydellinen tapausjärjestelmä S ∆: …,A–1,A0,A1,A2,…, missä Ai = {i∆ ≤ x < (i + 1)∆ } (i = …,–1,0,1,2,…). Silloin H( S ∆ ) = − =−

∞

∞

i=−∞ ∞

i=−∞

∑ pi log pi = − ∑ f ( x i )∆ log ( f ( x i )∆ ) ∑ f ( x i )∆ log f ( x i ) − log ∆.

i=−∞

107 Vertailtaessa entropioita additiivisesti supistuu hankaluuksia aiheuttava termi –log ∆ pois ja rajalla ∆ → 0+ saadaan vertailusuure, ns. x:n differentiaalientropia ∞

H( x ) = −

∫ f ( x ) log f ( x )dx = E( − log f ( x )).

−∞

Vastaavasti saadaan jatkuvan satunnaisvektorin x differentiaalientropia ∞

H(x) = −

∫ f (x) log f (x)dx = E( − log f (x)).

−∞

Paitsi maksimientropiamenetelmissä, voi differentiaalientropiaa soveltaa tapauksissa, joissa on kyseessä entropioiden erotus. Tällaisia ovat esimerkiksi ehdollinen entropia sekä keskinäisinformaatio. Huomaa, että differentiaalientropia voi olla ääretön tai negatiivinen, jopa –∞. Differentiaalientropiaa on käsitelty laajemmin esimerkiksi viitteessä MCELIECE.

108

VIII LUKU LÄHTEEN

KOODAUS

1. Yleistä Lähde (tarkemmin sanoen diskreetti lähde) on systeemi, joka tuottaa tietyn symbolijoukon eli aakkoston (lähdeaakkoston) A = {a1,…,aN} symboleja tietyllä todennäköisyydellä. Jos tämä todennäköisyys ei riipu lähteen aikaisemmin tuottamista symboleista, on kyseessä muistiton lähde, muuten muistillinen. Lähteen tuottama symbolijono jaetaan n-pituisiin peräkkäisiin lohkoihin, ns. lähdesanoihin, merkitään u = u1⋅⋅⋅un (ui on siis lähdesanan u i:s symboli). Vrt. Luvun I viestisanat ja viestiaakkosto. Menetellään samoin kuin Luvussa I eli kun lohkon pituus n on valittu, syötetään lähteen tuottama symbolijono lähdesanoittain kooderiin. Kooderi muuntaa lähdesanan koodiaakkoston C = {c1,…,cM} sanaksi, ns. koodisanaksi. Koodisanat muodostavat ns. koodin. Jos koodin kaikki koodisanat ovat samanpituiset, on kyseessä lohkokoodi, muuten ns. vaihtuvapituinen koodi. Tarkoitus luonnollisesti on, että koodattu viesti (lähdesana) voidaan saada esiin dekoodauksella joko aina tai ainakin tietyllä suurella todennäköisyydellä.

2. Muistiton lähde, lohkokoodi Koska lähde on muistiton, on kunkin lähdesymbolin esiintymistodennäköisyys vakio. Siis tapaukset A i = {“lähdesymboli on ai”}

(i = 1,…,N)

109 muodostavat täydellisen tapausjärjestelmän A, jonka todennäköisyysvektori p = (p1 ,…,p N ) tunnetaan. Jatkossa oletetaan, että kaikki lähdesymbolit ovat mahdollisia, ts. pi ≠ 0

(i = 1,…,N).

Lähteen entropia on tällöin H(A ). Jos lähdesanassa u lähdesymboli ai esiintyy ni kertaa (i = 1,…,N), niin P(u) = P(“lähdesana on u”) = P(“(lähdesanan) 1. symboli on u1, 2. symboli on u2,… ja n:s symboli on un”) = P(“n:s symboli on un”|“1. symboli on u1,… ja n – 1:s symboli on un – 1”)⋅ ⋅P(“1. symboli on u1,… ja n – 1:s symboli on un – 1”) = P(“n:s symboli on un”)P(“1. symboli on u1,… ja n – 1:s symboli on un – 1”) =⋅⋅⋅= P(“n:s symboli on un ”)P(“n – 1:s symboli on un – 1”)⋅ ⋅⋅⋅P(“1. symboli on u1 ”) n

n

= p1 1 LpNN . Suurten lukujen lain mukaan ni n ≅ pi

(i = 1,…,N),

kun n on suuri. (Valitaan suotuisaksi tapaukseksi symbolin ai esiintyminen, jolloin Sn = ni.) Siispä suurelle n:n arvolle on (todennäköisesti) n

n

np1

P(u) = p1 1 LpNN ≅ p1 = 2

(

p

p

log 2 p1 1 Lp NN

ts. A

–

log 2 P(u) ≅ H(A) bittiä. n

)

np N

LpN

(

p

p

= p1 1 LpNN

)

n

n

= 2n (–H(A)) = 2–nH(A),

110 Tämä arvio tarvitaan kuitenkin tarkemmassa muodossa: L AUSE 40. (OSITUSLAUSE ) Kaikille positiivisille luvuille η ja π (miten tahansa pienille) on olemassa sellainen vakio Nηπ , että log 2 P(u)  P   + H(A )  ≥ η < π, n kun n > Nηπ . (Sama asia sanoin: Todennäköisyys, että arvio A ei päde tietyllä (miten tahansa pienellä) tarkkuudella saadaan miten tahansa lähelle nollaa kasvattamalla n:n arvoa.) Todistus. Suurten lukujen lain mukaan  n  P  i − pi < ε  > 1 − δ  n  eli   n P  i − pi ≥ ε  < δ  n 

(i = 1,…,N),

kun n on kyllin suuri (n > Nεδ). Valitaan ensin ε niin pieneksi, että jos

ni −pi n

< ε (i = 1,…,N), niin

log 2 P(u)  + H(A )  < η.  n Tämä onnistuu vaikkapa valitsemalla ε=

η N − ∑ log 2 p i i=1

.

Jos nimittäin npi – nε < ni < npi + nε (i = 1,…,N), niin silloin 1 n

log 2 P(u ) + H( A) =

(

1 n

1 = n

n

n

N

∑

1 n i log 2 pi +H( A)< n

i=1

=

)

log 2 p1 1 LpNN + H( A) N

∑(npi − nε) log2 pi +H( A) i=1

N

N

i=1

i=1

∑ pi log2 pi −ε∑ log2 pi +H( A)=η

111 ja vastaavasti 1 n

1 n

log 2 P(u ) + H( A) >

N

∑ (npi + nε) log2 pi + H( A) i=1

=

N

N

i=1

i=1

∑ pi log2 pi +ε∑ log2 pi +H( A)=−η.

Jos nyt tämän valinnan jälkeen log 2 P(u)  + H(A )   ≥ η, n niin ainakin yhdelle i:n arvolle n i   n – p i ≥ ε. Merkitään N  n  P = max P  i − pi ≥ ε  .  n  i=1

Siispä (Suurten lukujen laki, valitaan δ = π/N), P < π/N, kun n on kyllin suuri. Nyt log 2 P(u)   + H(A ) P    ≥ η n n2  n N  n1  ≤ P   n – p1 ≥ ε tai  n – p2 ≥ ε tai ⋅⋅⋅ tai  n – pN  ≥ ε N

≤

∑ P  i=1

ni  − pi ≥ ε  ≤ NP < π ,  n

kun n on kyllin suuri (n > Nεδ = Nηπ ). (Summa-arvio löytyy tilastomatematiikan kurssilta.) ■ Palataan koodaukseen. Koodisanojen lukumäärä on Mm, jos koodin pituus (eli koodisanojen yhteinen pituus) on m. Lähdesanoja on vastaavasti Nn kpl. Jos nyt Mm ≥ Nn eli m n

log2 M ≥ log2 N,

niin jokaiselle lähdesanalle riittää oma koodisanansa ja asia on selvä.

112 Jos Mm < Nn, ei kaikille lähdesanoille riitä omaa koodisanaa. Tällöin suoritetaan ositus, ts. jaetaan lähdesanat kahteen luokkaan R = {sanat, joilla on oma koodisana} ja W = {muut lähdesanat}. Kaikille W :n sanoille ei ole omaa koodisanaa, ts. niille joudutaan antamaan jonkin toisen lähdesanan koodisana. Tämä johtaa dekoodausvirheeseen. R :n sanat taas dekoodataan (koodauksen jälkeen) oikein. Tavoitteena on luonnollisesti saada todennäköisyys P0 = P(u ∈ W ) (virhetodennäköisyys) pieneksi. Kuten lukija arvannee, käytetään ositukseen Osituslausetta. Merkitään tätä varten  log 2 P(u)  + H(A )  < η G =  sanat u, joille  n 

ja F = {muut lähdesanat}. Silloin Osituslauseen nojalla (kun n > Nηπ) P(u ∈ F ) < π ja jos u ∈ G , niin –η
B 2 –n (η + H(A)). P min = umin ∈ G

Silloin

  

1 ≥ P(u ∈ G ) =

∑ P(u) ≥ NG P min

u∈G

>C NG

2 –n (η + H(A))

113

eli D

N G < 2n (η + H(A)).

L AUSE 41. (SHANNONIN LÄHTEEN KOODAUSLAUSE) Kaikille positiiviluvuille η ja π (miten tahansa pienille) on olemassa sellainen vakio Nηπ, että m

(i)

jos n log2 M ≥ H(A) + η , niin P0 < π, ja

(ii)

jos n log2 M ≤ H(A ) – 2η , niin P0 > 1 – 2π (olipa ositus mikä tahansa!),

m

kun n > Nηπ. Todistus. Valitaan Nηπ siten, että Osituslause toteutuu ja että 2–nη ≤ π, kun n > Nηπ . m

(i) Jos n log2 M ≥ H(A) + η, niin M m ≥ 2n (H(A) + η ) > D NG ja valitaan R = G . Silloin

P 0 = P(u ∈ F ) < π.

m

(ii) Jos n log2 M ≤ H(A) – 2η, niin M m ≤ 2n (H(A) – 2η ). Niiden G :n sanojen lkm, joilla on oma koodisana, on silloin enintään Mm ja P(“u ∈ G ja u:lla on oma koodisana”) ≤ Mm P max ≤ 2n(H(A) – 2η)P max < C 2n (H(A) – 2η )2 n (η – H(A)) = 2–nη ≤ π. Edelleen (Kokonaistodennäköisyyskaavan nojalla) 1 – P0 = P(“u:lla on oma koodisana”) = P(“u ∈ G ja u:lla on oma koodisana”) + P(“u ∈ F ja u:lla on oma koodisana”) < π + P(“u ∈ F ja u:lla on oma koodisana”)

≤ π + P(u ∈ F ) < 2π

114

eli P0 > 1 – 2π. ■ m

Jos nyt n log2 M > H(A), niin löytyy sellainen η, että m n

Tällöin myös

log2 M > H(A) + η.

km kn

log2 M > H(A) + η

ja Lähteen koodauslause saadaan käyttöön kasvattamalla k:ta, ts. pidentämällä lähde- ja koodisanoja samassa suhteessa. Virhetodennäköisyys saadaan tällöin miten tahansa pieneksi (k:ta kasvattamalla). Lauseen kohta m

(ii) osoittaa, ettei tämä onnistu, jos n log2 M < H(A ), itse asiassa päinm

vastoin. (Tapaus n log2 M = H(A ) ei juuri esiinny, sillä H(A )/log 2 M on enimmäkseen irrationaaliluku.)

3. Muistiton lähde, vaihtuvapituinen koodi Vaihtuvapituisen koodin sanat voivat olla eripituisia. Mikä tahansa äärellinen koodisymboleista muodostettujen sanojen joukko ei kuitenkaan ole koodi: Koodin vaatimuksena on, että koodattu viesti on yksikäsitteisesti dekoodattavissa, ts. että mikä tahansa koodisymbolien jono on enintään yhdellä tavalla tulkittavissa koodisanojen jonoksi. Jos w = w1L w l on koodisana (jolloin siis w1 ,…, w l ovat koodisymboleja), niin sanat w, w1L w l−1, w1L w l−2 ,…, w1w2, w1 ( l kpl) ovat ns. w:n prefiksit. Äärellinen sanojen joukko W on ns. prefiksikoodi, jos mikään W :n sana ei ole toisen W :n sanan prefiksi.

L AUSE 42. Prefiksikoodi on koodi. Todistus. Pitää näyttää, että prefiksikoodin sanoista yhdistämällä ei saada kahdella eri tavalla yhdistäen samaa sanaa: Mikäli wi1,…,wip ovat prefiksikoodin W sanoja, niin sanaa w = w i1w i2⋅⋅⋅w ip ei voida kirjoittaa muulla tavoin W :n sanojen yhdyssanaksi. Jos nimittäin

w = w j1 w j2 ⋅⋅⋅w jq ,

115

missä myös w j1,…,w jq ∈ W , niin sanoista w i1 ja w j1 toinen on toisen prefiksi ja siis (prefiksikoodi) w i1 = w j1 . Näin ollen w i2 ⋅⋅⋅w ip = w j2 ⋅⋅⋅w jq . Mutta samalla perusteella wi2 = wi2 ja jne.. Siispä q = p ja w i1 = w j1 ,…,w ip = w jp . ■ Kaikki koodit eivät ole prefiksikoodeja.

L AUSE 43. (KRAFTIN LAUSE) Prefiksikoodi, jonka koodisanojen pituudet ovat l1,…,lk , on olemassa tarkalleen silloin, kun 1 1 + +L+ ≤1 Mlk M l1 M l2 1

(ns. Kraftin ehto).

(M on tässäkin koodisymbolien lkm.) Todistus. Vaihtamalla tarvittaessa koodisanojen järjestystä voidaan olettaa, että l1 ≤ l2 ≤L≤ lk . Oletetaan ensiksi, että Kraftin ehto toteutuu, ts. (kun kerrotaan puolittain M l k :lla) M l k −l1 + M l k −l2 +L+M l k −l k −1 + 1 ≤ M l k . lk :n pituisia sanoja on M l k kpl, merkitään niiden joukkoa V :llä. Jos nyt valitaan joukko sanoja W sillä tavalla, että kullakin V :n sanalla on enintään yksi W :n sana prefiksinä ja W :n sanojen pituus ei ylitä lk :ta, niin W on prefiksikoodi. Näytetään, että tämä voidaan tehdä siten, että W :n sanojen pituudet ovat l1,…,lk : 1)

Merkitään V 1 = V . Valitaan V 1 :stä sana ja sen l1:n pituinen prefiksi w 1. Poistetaan V 1:stä kaikki sanat, joiden prefiksi w 1 on. Näitä on M l k −l1 kpl. Jäljelle jäävän joukon V 2 sanojen lkm on M l k − M l k −l1 .

2)

Valitaan V 2:sta sana ja sen l2 :n pituinen prefiksi w 2 . (Kraftin ehdon nojalla tämä on mahdollista.) Poistetaan V 2:sta sanat, joiden prefiksi w 2 on. Näitä on M l k −l2 kpl.

116 3)

Jne.. Lopulta saadaan haluttu prefiksikoodi W = {w1,…,wk}.

Oletetaan toiseksi, että W = {w 1 ,…,w k } on prefiksikoodi, jonka sanojen pituudet ovat l1,…,lk . Kullakin V :n sanalla on enintään yksi W :n sana prefiksinä. Sanoja, joiden prefiksinä on w i, on M l k −l i kpl (i = 1,…,k). Siis M l k −l1 + M l k −l2 +L+M l k −l k −1 + 1 ≤ M l k . eli Kraftin ehto toteutuu. (Huomaa, että ainoa V :n sana, jonka prefiksi on w k , on w k itse.) ■ Luonnollisesti myös sanajoukot, jotka eivät ole koodeja, voivat toteuttaa Kraftin ehdon. Toisaalta jokainen koodi toteuttaa Kraftin ehdon (!), kuten seuraavassa lauseessa osoitetaan.

L AUSE 44. (MC M ILLANIN LAUSE) Jokainen koodi toteuttaa Kraftin ehdon. Todistus. Tarkastellaan koodia {w 1 ,…,w k }, jonka koodisanojen pituudet ovat l1 ≤ l2 ≤L≤ lk . Otetaan mielivaltainen positiivinen kokonaisluku r (lopulta r → ∞). Silloin r

1 1  1 1   1 1 1   1  1  l + l +L+ l  =  l + l +L+ l  L  l + l +L+ l  M 1 M 2 M 1 M 2  M 1 M 2 M k M k4 M k3 14444444444 244444444444 r kpl

k

=

k

k

∑ ∑ ∑ Ml

1

L

i1 =1i 2 =1

i r =1

i1

1 M

li2

L

1 M

li r

k

=

k

k

∑∑ ∑ L

i1 =1i 2 =1

M

−(l i1 +l i 2 +L+l i r )

.

i r =1

Summa li1 + li 2 +L+li r on r:n koodisanan yhdyssanan w i1w i2⋅⋅⋅w ir pituus. Indeksien i1 ,…,i r kulkiessa toisistaan riippumatta arvot 1,…,k saadaan kaikki r:n koodisanan yhdyssanat (mahdolliset toistot mukaanlukien). Merkitään nyt sj = niiden r:stä koodisanasta eri tavoin yhdistämällä saatujen sanojen lkm (mahdolliset toistot mukaanlukien), joiden pituus on j. Ilmeisesti mahdolliset j:n arvot ovat j = rl1,…,rlk . Näin ollen r

1 1   1  l + l +L+ l  = M 1 M 2 M k

rl k

∑ s jM− j.

j=rl1

117 Mutta koodi on yksikäsitteisesti dekoodattavissa, joten kahdella eri tavalla r:stä koodisanasta yhdistämällä ei voi saada samaa sanaa (ts. toistoja ei itse asiassa ole). Siis sj ≤ j:n pituisten sanojen lkm = Mj

(j = rl1,…,rlk )

ja r

1 1   1  l + l +L+ l  ≤ M 1 M 2 M k

rl k

∑ M jM− j = rlk − rl1 + 1 ≤ rlk .

j=rl1

Otetaan puolittain r:s juuri ja annetaan r → ∞: 1 M

l1

+

1 M

l2

+L+

1 Mlk

≤

r

rlk → 1,

sillä (l’Hospitalin sääntö) lim ln

r→ ∞

r

1

ln r – ln lk r – 0 = lim rlk = lim r 1 =0. r→∞ r→∞

Koska arvion vasen puoli ei riipu r:stä, pätee arvio sille myös rajalla r → ∞, ts. Kraftin ehto on voimassa. ■

L AUSE 45. Jokainen koodi voidaan sananpituudet säilyttäen korvata prefiksikoodilla. Todistus. Kraftin lause ja McMillanin lause. ■

Näin ollen voidaan tämä luvun tavoitteita ajatellen rajoittua prefiksikoodeihin.

4. Optimikoodaus Kutakin koodisanaa w i (i = 1,…,k) vastaa kääntäen yksikäsitteisesti lähdesana ui. Merkitään P i = P(“lähdesana on u i”) = P(“koodisana on w i”) U = {u 1,…,u k} (lähdesanojen joukko) ja k

H(U) = – ∑ P i log P i i=1

(i = 1,…,k),

118 (lähdesanaentropia). H(U):ta ei pidä sekoittaa lähteen entropiaan H(A). Käyttäen toistuvasti sitä tietoa (Lause 33), että jos tapausjärjestelmät S 1 ja S 2 ovat riippumattomat, niin H(S 1 ∩ S 2 ) = H(S 1 ) + H(S 2 ), nähdään, että itse asiassa H(U) = nH(A) (missä n on lähdesanan pituus). Merkitään edelleen l = P1l1 +L+P k lk (koodisanojen keskipituus), missä l1,…,lk ovat koodisanojen pituudet. Jatkossa oletetaan, että P1,…,Pk ≠ 0, ts. että kaikki lähdesanat ovat mahdollisia. Optimikoodaus tarkoittaa, että koodi valitaan siten, että l on pienin mahdollinen. Lauseen 45 nojalla voidaan rajoittua prefiksikoodeihin. Tehtävänä on näin valita sellaiset kokonaisluvut l1,…,lk , että  l = P1l1 +L+P k lk = min!  1 1  1  l1 + l2 +L+ l k ≤ 1 M M M  l ,…,l ≥ 1 k 1 Optimikoodaus siis tiivistää viestin mahdollisimman tehokkaasti (keskimäärin). l voidaan arvioida H(U):n avulla alhaalta olipa koodi mikä tahansa (optimaalinen tai ei). Käytetään ensin natteja: k  k H(U) – l ln M = – ∑ Pi ln Pi –  ∑ P i li  i=1 i=1

  ln M 

k

k

i=1

i=1

= – ∑ P i (ln P i + li ln M) = ∑ P i ln

1 P i Mli

k

k k 1 1   ≤ ∑ Pi  – 1 = ∑ – ∑ P i ≤ 0. li  i=1 M l i i=1 i=1  P i M

Siis nateissa l ln M ≥ H(U) ja näin ollen mielivaltaiselle kantaluvulle H(U ) l ≥ log M . Todettakoon vielä, että arviossa esiintyy yhtäsuuruus tarkalleen silloin, kun

k

1 Pi M

li

=1

(i = 1,…,k)

ja

∑

i=1

119 1 Mli

=1

eli kun P i = 1/ M l i (i = 1,…,k). Jos todennäköisyydet P1,…,Pk ovat “sopimattomia” (eivät M:n negatiivisia potensseja), niin tähän minimiarvoon ei voida päästä. Toisaalta kuitenkin optimikoodauksessa päästään melko lähelle:

L AUSE 46. (SHANNONIN KOODAUSLAUSE) Optimikoodille H(U ) H(U ) ≤ + 1 l < log M log M ja näin ollen H(A ) l lim n = log M . n→ ∞

Todistus. Alaraja tuli jo todettua yllä. Ylärajan todistamiseksi valitaan kullekin todennäköisyydelle Pi lähin M:n negatiivinen potenssi, ts. kokonaisluku li ≥ 1 siten, että 1 M

1

≤ Pi
l′i+1 , niin vaihdetaan w ′i ja w ′i+1 , ts. lähdesana u i koodataan w ′i+1 :ksi ja lähdesana ui+1 koodataan w ′i :ksi. Koodisanojen keskipituuden muutos on P i l′i+1 + P i+1l′i − (P i l′i + P i+1l′i+1 ) = (P i − P i+1 )( l′i+1 − l′i ) ≤ 0. Toisaalta koodi oli optimaalinen, joten ko. muutos on =0 ja koodi pysyy vaihdonkin jälkeen optimaalisena (prefiksi)koodina. Toistamalla vaihto– operaatio (tarvittaessa) kyllin monta kertaa voidaan olettaa, että l1 ≤L≤ lk . Näinkin saatuja optimikoodeja voi hyvinkin olla useita. Valitaankin jatkossa käytetty optimikoodi siten, että l1 +L+lk on pienin mahdollinen, ja merkitään (✳ )

∆=M

lk

k

−

∑ Ml i=1

k −l i .

121 McMillanin lauseen nojalla ∆ ≥ 0. Jos toisaalta olisi ∆ ≥ M – 1, niin pituudet l1,…,lk−1,lk − 1 toteuttaisivat Kraftin ehdon, mikä on mahdotonta, koska l1 +L+lk oli pienin mahdollinen. Siispä 2 ≤ M – ∆ ≤ M. Merkitään nyt r:llä pituutta lk olevien koodisanojen lukumäärää. Silloin r ≥ 2. Muussa tapauksessa voitaisiin wk:n viimeinen symboli poistaa ja saada prefiksikoodi (mahdotonta, koska l1 +L+lk oli pienin mahdollinen). Yhtälöstä (✳) seuraa, että ∆ ≡ –r (mod M) eli r ≡ M – ∆ (mod M). Koska toisaalta 2 ≤ M – ∆ ≤ M, on r kirjoitettavissa muotoon r = tM + (M – ∆), missä t ≥ 0. Yhtälöstä (✳) seuraa edelleen, että ∆ ≡ 1 – k (mod M – 1) (sillä M ≡ 1 (mod M – 1)) eli M – ∆ ≡ k (mod M – 1). Näin nähdään, että M – ∆ on juuri (i):ssä mainittu luku s ja r ≥ s. Tarvittaessa indeksointia vaihtamalla voidaan olettaa, että koodin lk -pituisista sanoista w k – r + 1,…,w k sanat w k – t,…,w k ovat sellaisia, että niiden lk − 1-pituiset prefiksit z 1 ,…,z t + 1 ovat keskenään erilaiset. Muista, että r = tM + s. Korvataan nyt sanat w k – r + 1,…,w k sanoilla z 1 c 1 ,…,z 1 c M , z2c1,…,z2cM ,…,ztc1,…,ztcM ,zt + 1c1,…,zt + 1cs. Tämä ei hävitä koodin prefiksisyyttä eikä optimaalisuutta. Saatu koodi on vaadittu {w1,…,wk}. ■ Tarkastellaan sanoja v 1 ,…,v k – s + 1, jotka saadaan Apulauseen koodista {w1,…,wk} seuraavasti: (a)

v1 = w1,…,vk – s = wk – s ja

(b)

vk – s + 1 saadaan, kun poistetaan wk:sta sen viimeinen symboli (= cs ).

{v 1 ,…,v k – s + 1} on prefiksikoodi. Ajatellaan sillä koodattavaksi k – s + 1 lähdesanaa, joiden todennäköisyydet ovat P1,…,Pk – s,Pk – s + 1 +⋅⋅⋅+ Pk. Koodisanojen keskipituus on tällöin l′ =

k−s

k

k

i=1

i=k−s+1

i=k−s+1

∑ Pili + ∑ Pi (lk − 1) = l − ∑ Pi .

Koodi {v 1 ,…,v k – s + 1} on näin ollen myös optimaalinen. (Muutoin olisi jokin pienemmän koodisanojen keskipituuden omaava prefiksikoodi { v1′ ,…, v ′k−s+1 } ja prefiksikoodin { v1′ ,…, v ′k−s , v ′k−s+1c1,…, v ′k−s+1cs } koodisanojen keskipituus olisi pienempi kuin l ′ + P k−s+1 +L+P k = l. ) Toisaalta, jos { v1′ ,…, v ′k−s+1 } on optimaalinen prefiksikoodi (vastaten lähdesanatodennäköisyyksiä P1,…,Pk – s,Pk – s + 1 +⋅⋅⋅+ Pk), niin sen koodisa-

122 nojen keskipituus on l ′ ja { v1′ ,…, v ′k−s , v ′k−s+1c1,…, v ′k−s+1cs } on optimaalinen prefiksikoodi (vastaten lähdesanatodennäköisyyksiä P1,…,Pk). Muussa tapauksessa olisi Apulauseen antama optimikoodi, jonka koodisanojen keskipituus olisi pienempi kuin l ′ + Pk − s +1 + L + Pk ja tästä saataisiin kohtien (a) ja (b) avulla vielä koodia { v1′ ,…, v ′k−s+1 } “optimaalisempi” koodi. Huffman–koodaus on seuraava rekursio, joka yllä esitetyn mukaan tuottaa optimikoodin saatuaan syöttönä lähdesanatodennäköisyydet P1,…,Pk (vähenevässä järjestyksessä):

(1)

Jos k ≤ M, niin valitaan w1 = c1,…,wk = ck ja lopetetaan.

(2)

Muutoin koodi {w1,…,wk} (vastaten lähdesanatodennäköisyyksiä P1,…,Pk) saadaan, kun koodi {v1,…,vk – s + 1} tunnetaan: w1 = v1 ,…, wk – s = vk – s , wk – s + 1 = vk – s + 1c1 ,…, wk = vk – s + 1cs. Koodin {v1,…,vk – s + 1} saamiseksi lasketaan s sekä asetetaan Q1 ← P1 ,…, Qk – s ← Pk – s , Qk – s + 1 ← Pk – s + 1 +⋅⋅⋅+ Pk. Edelleen asetetaan todennäköisyyksien P1,…,Pk – s + 1 arvoiksi Q1,…,Qk – s + 1 vähenevässä järjestyksessä, k ← k – s + 1 ja palataan kohtaan (1).

H UOM ! Ensiksi valittava s toteuttaa ehdon s ≡ k (mod M – 1), jolloin “uusi k” eli k – s + 1 on ≡1 (mod M – 1). Näin ollen seuraava s:n arvo onkin M. Itse asiassa näin jatkaen todetaan, että kaikki muutkin uudet s:n arvot ovat =M ja siis vain ensimmäinen s:n arvo pitää laskea! Huomaa myös, että tapauksessa M = 2 (binäärinen Huffman-koodi) aina s = 2.

6. Muita koodausmenettelyjä Juoksulukukoodaus Juoksulukukoodauksessa ajatellaan lähdesanat vaihtuvapituisiksi ja koodisanat ovat vakiopituisia. Koodausta käytetään silloin, kun jokin lähdesymboleista esiintyy huomattavasti muita useammin. Tarkastellaan esimerkkinä binäärisen lähteen tapausta, missä 1 esiintyy huomattavasti useammin kuin 0. Valitaan juoksun maksimipituus n. Koska J = {0,10,12 0,1 3 0,…,1 n – 10,1 n }

123 on prefiksikoodi, voidaan lähteen tuottama bittijono yksikäsitteisesti jakaa J :n sanoiksi. Asetetaan sitten J :n sanaa 1i0 tai 1i vastaamaan juoksuluvun i binääriesitys täydennettynä alkunollilla maksimipituuteen m = log2 n + 1. Tämä koodaus ei yleensä yllä lähellekään Huffman-koodauksen “pakkauskykyä”, mutta on nopeampi suorittaa.

Aritmeettinen koodaus Muuttamalla koodausmenettely Huffman-koodauksesta poikkeavaksi voidaan lähestyä Shannonin koodauslauseen alarajaa H(U)/log M. Eräs tällainen menettely on aritmeettinen koodaus. Lähdesymboleja a1 ,…,a N – 1,aN vastaamaan asetetaan välin [0,1) osavälit [0,p1) , [p1,p1 + p2) , [p1 + p2,p1 + p2 + p3) ,…, [p1 +⋅⋅⋅+ pN – 1,1). Merkitään ai:tä vastaavaa väliä [qi,ri):llä (i = 1,…,k). Lähdesymboli aN on loppumerkki, ts. se esiintyy vain lähdesanan viimeisenä lähdesymbolina. Aritmeettisen koodauksen ideana on asettaa kutakin käypää lähdesanaa eli sellaista lähdesymbolien jonoa, jossa aN esiintyy vain viimeisenä symbolina, vastaamaan yksikäsitteinen välin [0,1) osaväli. Tämä tapahtuu seuraavasti: (1)

Asetetaan L ← 0 ja U ← 1.

(2)

Luetaan lähdesanan seuraava symboli a = ai. Lasketaan L* = L + (U – L)qi

ja

U* = L + (U – L)ri.

Huomaa, että U* – L* = pi(U – L). (3)

Jos a = aN , tulostetaan [L*,U*) ja lopetetaan. Muutoin asetetaan L ← L* ja U ← U* ja mennään kohtaan (2).

p5

1

p4 p3 p2 p1

a4

a4 a2

a1

On ilmeistä, että lähdesanaa tulee aina vastaamaan yksikäsitteinen väli [L*,U*). Jos lähdesana on u = ai1 ai2 ⋅⋅⋅a in , niin U* – L* = pi1 p i2 ⋅⋅⋅p i n = P(u).

124 Lähdesanan pituuden ei tässä kuitenkaan tarvitse olla kiinteä, mikä tahansa sana, jossa aN esiintyy vain viimeisenä symbolina, käy. Itse asiassa välin [L*,U*) asemasta riittää antaa yksikin välillä oleva reaaliluku x. Kun valitaan kokonaisluku R siten, että 10–R ≤ U* – L* < 10–R + 1, niin voidaan valita x:ksi luku x = X/10R , missä X on välillä [0,10R ) oleva kokonaisluku. Lähdesanaa u vastaavaksi koodisanaksi voidaankin ottaa X ja X:n pituus on enintään R = –lg (U* – L*) = –lg P(u). Jos käytetään n-pituisia lähdesanoja, niin koodisanan keskipituus on k

l≤

k

∑ Pi  − lg Pi  < − ∑ Pi lg Pi + 1 = H(U ) + 1 i=1

(diteissä ),

i=1

kuten Shannonin koodauslauseen mukaan pitää ollakin. (Loppumerkin aN todennäköisyydeksi otetaan tällöin pN = 1/n ja muut todennäköisyydet skaalataan vastaavasti.) Käytännössä l on kuitenkin useimmiten lähellä alarajaansa H(U) dittiä. Huomaa, että saadut sanat X eivät sellaisenaan muodosta (prefiksi)koodia ja ne pitää lähetettäessä erottaa. Aritmeettisen koodauksen implementointi on ilmeisen vaativa tehtävä ja se myös vaikuttaa kriittisesti koodauksen “pakkauskykyyn”, ks. esimerkiksi WITTEN , I.H. & NEAL , R.M. & CLEARY , J.G.: Arithmetic Coding for Data Compression. Communications of the Association for Computing Machinery 30 (-87), 520–540. Mainittakoon, että ensimmäiset aritmeettisen koodauksen käytännön menetelmät kehitti suomalaissyntyinen informaatioteoreetikko Jorma Rissanen*.

7. Muistillinen lähde Muistillisen lähteen tapauksessa lähteen tuottaman lähdesymbolin todennäköisyys riippuu sen aikaisemmin tuottamista symboleista, ts. lähde “muistaa”. Lähteen tuottaman symbolijonon voidaan ajatella alkaneen “äärettömän kauan sitten”, ts. se on muotoa …,un – 2,un – 1,un,… Lähdesymbolien jono muodostaa tällöin ns. stokastisen prosessin (ks. kurssi 73126 Stokastiset prosessit). Rajoittamalla tämä sopivaan tapaukseen (stationäärisyys, ergodisuus) voidaan todistaa eo. pykälien perustuloksia vastaavat tulokset myös muistillisille lähteille. Ks. esimerkiksi BLAHUT. *

R ISSANEN , J.J.: Generalized Kraft Inequality and Arithmetic Coding. IBM Journal of Research and Development 20 (-76), 198–203.

125

I X LUKU KANAVAKOODAUS 1. Muistiton kanava. Kanavan kapasiteetti Palataan Luvun VIII tilanteeseen ja lisätään mukaan kanava, jonka kautta koodisanat lähetetään vastaanottajalle. Lähdeaakkoston A sekä koodiaakkoston C lisäksi tarvitaan siis vielä vastaanottoaakkosto B = {b1,…,bL}. Kanava on tässä kohiseva, ts. se voi aiheuttaa virheitä. Todennäköisyydet P(“vastaanotetaan bi”|”lähetetään cj”) = pi|j

(i = 1,…,L;j =1 ,…,M)

oletetaan tunnetuksi. Kyseessä ovat ehdollisen tapausjärjestelmän B |C : Bi|Cj

(i = 1,…,L;j = 1 ,…,M),

missä Bi = {“vastaanotetaan bi”} ja Cj = {”lähetetään cj”} (i = 1,…,L;j = 1, …,M), todennäköisyydet, jotka voidaan koota ehdolliseksi todennäköisyysmatriisiksi Q (ks. VII.1). Kyseessä on tällöin ns. muistiton kanava. (Muistillisia kanavia ei tässä käsitellä.) Dekooderin tehtävä on paitsi “purkaa” koodaus, pyrkiä vähentämään kanavan aiheuttamien häiriöiden vaikutusta. Myös koodaus voidaan valita siten, että kanavan on mahdollisimman vaikea häiritä koodattua viestiä. Luvuissa I–VI käsitelty virheitä korjaava koodauskin pyritään suunnittelemaan kanavan ominaisuuksia ajatellen, mikäli mahdollista. Tämä saattaa vaikuttaa oleellisestikin koodin valintaan. Kanava karakterisoidaan antamalla Q. Merkitään tällaista kanavaa K:llä. Jos merkitään täydellisen tapausjärjestelmän B : B1 ,…,B L todennäköisyysvektoria p:llä, tapausjärjestelmän C : C1,…,CM todennäköisyysvektoria q:lla sekä yhteistapausjärjestelmän B ∩ C todennäköisyysmatriisia P:llä, niin lähetetyn ja vastaanotetun symbolin välinen keskinäisinformaatio on (ks. Lause 32) I(B ,C ) = trace(P log (Q T p –1 )) = trace(Qq log (Q T qQ T  –1 )) = I(q), eli summamuodossa

126 L

I(q 1 ,…,q M ) = ∑

M

∑ pi|jq j log

i=1 j=1

p i|j p i , missä

M

pi = ∑ p i|jq j

(i = 1,…,L).

j=1

Suurin mahdollinen I(q):n arvo on ns. kanavan K kapasiteetti, merkitään C(K). Kapasiteetti saadaan siis optimointitehtävän

 I(q1,…,qM ) = max! q1 +⋅⋅⋅+ qM = 1 q1 ≥ 0,…,qM ≥ 0 ratkaisuna. Tehtävä ratkaistaan joko numeerisesti tai ns. Kuhn–Tuckerehtoja käyttäen, ks. 73112 Matemaattinen optimointiteoria 1. Voidaan osoittaa, että kyseessä on ns. konveksi optimointitehtävä, mikä helpottaa ratkaisua. (Tähän tarvitaan Konveksisuuslausetta! Ks. esimerkiksi MCELIECE .)

2. Kanavakoodauslause Merkitään nyt, kuten Luvussa VIII, n = lähdesanan pituus, m = koodisanan pituus, H(A) = lähteen entropia, P0 = dekoodausvirheen todennäköisyys. Silloin saadaan (vrt. Shannonin lähteen koodauslause) L AUSE 47. (SHANNONIN KANAVAKOODAUSLAUSE) Kaikille positiiviluvuille η ja π (miten tahansa pienille) on olemassa sellainen vakio Nηπ , että jos n m

H(A) ≤ C(K) – η, niin P0 < π, kun koodaus ja dekoodaus valitaan sopivasti sekä n > Nηπ.

Todistus. Ks. esimerkiksi YAGLOM & YAGLOM tai MCELIECE. ■

Myöskin vastaava “negatiivinen” tulos (vrt. Shannonin lähteen koodauslauseen osa (ii)) on olemassa, ks. YAGLOM & YAGLOM. Entropian tulkinnan mukaan n m H(A ) = keskimääräinen lähdeinformaatio kanavaan lähetettyä symbolia kohti.

127 Shannonin kanavakoodauslauseen mukaan tämä voidaan saada mielivaltaisen lähelle arvoa C(K), jos sallitaan (häviävän) pieni virhetodennäköisyys. (Mainittu “negatiivinen” tulos sanoo suurin piirtein, että se ei voi ylittää arvoa C(K), ilman että virheen todennäköisyys jää merkittävän suureksi.)

3. Binäärinen symmetrinen kanava (BSC) Binääriselle symmetriselle kanavalle B = C = {0,1} ja 1–p p  Q =  . p 1–p  Näin ollen kumpikin virheistä 0 ← 1 sekä 1 ← 0 on kanavassa yhtä todennäköinen. Merkitään edelleen q = (q,1 – q). Silloin p = qQ T = (p + q – 2pq,1 – p – q + 2pq), p(1 – q)  (1 – p)q  P = Qq =    pq (1 – p)(1 – q)  ja

p–1Q

=

 p +1q ––p2pq   1 – p – pq + 2pq

p p + q – 2pq 1–p 1 – p – q + 2pq

 . 

Näin ollen (biteissä) 1–p p I = I(q,1 – q) = (1 – p)q log 2 + p(1 – q) log 2 p + q – 2pq p + q – 2pq p 1–p + pq log2 1 – p – q + 2pq + (1 – p)(1 – q) log 2 1 – p – q + 2pq .

Jos erityisesti p = 1/2, niin I = 0, ts. kanava ei välitä informaatiota. I on symmetrinen pisteen q = 1/2 suhteen. Näin ollen kanavan kapasiteetti saavutetaankin, kun q = 1/2 ja C(K) = 1 + (1 – p) log 2 (1 – p) + p log 2 p bittiä, jonka kuvaaja (Maplella piirrettynä) on seuraavannäköinen:

128

0.8

0.6

0.4

0.2

0

0.2

0.4

0.6

p 1

0.8

0

I:n kuvaaja sekä p:n että q:n funktiona on seuraavanlainen (jälleen la piirrettynä):

0.800

0.400

00 0

0.200

0.200

0.400 q 0.600

0.600 0.800

0.800 1.00 1.00

0.400 p

Maplel-

129 “The place that PME occupies in our present revolution is that it is one of the principles that has proved useful—and fairly general— in the task of developing that missing half (logically, the first half) of probability theory.” E.T. JAYNES (SYNTHESE 63 (-85))

X LUKU M AKSIMIENTROPIAPERIAATE 1. Yleistä Tilastotieteen kantavana periaatteena on mallintaa satunnaistilanne käyttäen tunnettuja parametrisoituja jakaumia ja estimoida parametrit otoksia käyttäen (ks. tilastomatematiikan kurssit). Maksimientropiaperiaate tarkoittaa jakauman valintaa tiettyjen ehtojen puitteissa siten, että jakauman entropia (differentiaalinen tai “tavallinen”) maksimoituu pysyen äärellisenä. Jakaumatyyppiä ei tällöin kiinnitetä, vaan se on valittavissa vapaasti. Entropian maksimoinnin perustana on seuraava ominaisuus:

APULAUSE. (i) (Diskreetti jakauma) Jos p ja q ovat todennäköisyysvektoreita (äärellisiä tai äärettömiä), niin –∑ pi log p i ≤ –∑ p i log q i i

i

ja yhtäläisyys on voimassa tarkalleen silloin, kun p = q. (ii)

(Jatkuva jakauma) Jos f(x) ja g(x) ovat tiheysfunktioita, niin −

∞

∞

−∞

−∞

∫ f (x) log f (x)dx ≤ − ∫ f (x) log g(x)dx

ja yhtäläisyys on voimassa tarkalleen silloin, kun f(x):n määrittämässä jakaumassa P(f(x) ≠ g(x)) = 0. Molemmissa tapauksissa oletetaan, että esiintyvät sarjat/integraalit suppenevat.

130 Todistus. (i) Voidaan olettaa, että pi ≠ 0 (jättämällä vastaavat tapaukset pois tapausjärjestelmästä). Silloin sivun 92 Apulauseen nojalla q



∑ pi ln q i − ∑ pi ln pi = ∑ pi ln pii ≤ ∑ pi  pii − 1 ≤ 0. q

i

i

i

i

(ii) Integrointi voidaan rajoittaa alueeseen, jossa f(x) ≠ 0. Sen jälkeen todistus on samanlainen kuin kohdan (i). ■

2. Maksimientropiajakaumat Tapausjärjestelmää S : A1 ,A 2 ,… (äärellistä tai ääretöntä) vastaten asetetaan diskreetti satunnaismuuttuja x seuraavasti: x = i, jos Ai tapahtuu. L AUSE 48. (MAKSIMIENTROPIAMENETELMÄ N PERUSLAUSE) (i)

(Diskreetti tapaus) Jos diskreetin satunnaismuuttujan x otosavaruus {1,…,N} tai {1,2,…} ja odotusarvo E ( g(x) ) =∑ p ig(i) = θ, i

missä g = (g1 ,…,g n ) ja θ = (θ 1 ,…,θ n ), on kiinnitetty, niin maksimientropiajakauma (mikäli olemassa) on muotoa p MEi = γe –λg(i)T

(i = 1,…,N tai i = 1,2,…).

Vakiot γ ja λ = (λ1,…,λn) valitaan siten, että

∑ pMEi = 1

ja

i

(ii)

∑ pMEi g(i) = θ. i

(Jatkuva tapaus) Jos jatkuvan satunnaismuuttujan x otosavaruus Ω ja odotusarvo E ( g(x)) =

∫ f (x)g(x)dx = θ ,

Ω

missä g = (g1 ,…,g n ) ja θ = (θ 1 ,…,θ n ), on kiinnitetty, niin maksimientropiajakauma (mikäli olemassa) on muotoa fME (x) = γe –λg(x)T

(x ∈ Ω).

Vakiot γ ja λ = (λ1,…,λn) valitaan siten, että

131

∫ f ME (x)dx = 1

ja

Ω

∫ f ME (x)g(x)dx = θ.

Ω

Todistus. Näytetään vain kohta (ii) (kohdan (i) todistus on täysin analoginen). Lasketaan (nateissa) ln fME (x) = ln γ – λg(x)T ja differentiaalientropia

∫

(

∫

)

H ME = − f ME (x ) ln f ME (x)dx = − f ME (x ) ln γ − λg(x) T dx = − ln γ + λθ T . Ω

Ω

Sen näyttämiseksi, että kyseessä todella on maksimientropiajakauma, pitää osoittaa, että jos f(x) on otosavaruuden Ω toinen tiheysfunktio, jolle odotusarvoehto E(g(x)) = θ toteutuu, niin sitä vastaava entropia ei ole suurempi kuin HME. Apulauseen nojalla mainittu entropia onkin ∞

−

∞

∫ f (x) ln f (x)dx ≤ − ∫ f (x) ln f ME (x)dx −∞ −∞ = − f (x )( ln γ − λg(x) T ) dx = − ln γ + λθ T = H ME ∫ Ω

ja jakauma on myös yksikäsitteinen. ■ Vakioiden γ ja λ etsimiseksi saadaan n + 1 yhtälöä, joista ne (numeerisesti) ratkaistaan. (Tässä esimerkiksi Maple on hyvin kätevä apuväline.) On tietysti huomattava, ettei maksimientropiajakaumaa aina olekaan, ts. annettujen ehtojen puitteissa entropia saadaan miten tahansa suureksi. Toisinaan on kätevää etsiä vakioiden λ arvot käyttäen ns. ositusfunktiota. Diskreetille jakaumalle ositusfunktio on Z(λ) =∑ e –λg(i)T = i

jolloin

1 , γ

1 ∂Z –Z = γ∑ g j(i)e –λg(i)T = θ j ∂λ j i

(j = 1,…,n).

Vastaavasti jatkuvan jakauman ositusfunktio on Z(λ ) =

∫

Ω

T

e −λg(x) dx =

1 γ

132 ∂Z 1 = θj (j = 1,…,n). Näin saadaan n yhtälöä tuntemattomille ja samoin – Z ∂λ j λ1,…,λn. H UOM! Valitsemalla g siten, että

g(x) =

a1 ≤ x ≤ b1 cc12,, kun kun a2 ≤ x ≤ b2  M ck, kun ak ≤ x ≤ bk

missä a1 < b1 < a2 < b2