Peittokoodi
Tätä artikkelia tai sen osaa on pyydetty parannettavaksi, koska se ei täytä Wikipedian laatuvaatimuksia. Voit auttaa Wikipediaa parantamalla artikkelia tai merkitsemällä ongelmat tarkemmin. Lisää tietoa saattaa olla keskustelusivulla. Tarkennus: käännösmokia "Compression with distortion" -> "Puristus vääristymällä". Kirjoittalla ei ole ollut mitään ajatusta aiheesta |
peittokoodilähde? on koodausteoriassa joukko elementtejä (kutsutaan koodisanoiksi) tilassa, jonka ominaisuus on, että tilan jokainen elementti on kiinteän etäisyyden päässä jostakin koodisanasta.
Määrittely
[muokkaa | muokkaa wikitekstiä]Olkoon , , kokonaislukuja. Koodia yli aakkoston Q kooltaan |Q| = q kutsutaan q R -peittäväksi koodiksi pituudeltaan n, jos jokaiselle sanalle on olemassa sellainen koodisana , että Hammingin etäisyys . Toisin sanoen, pallot tai säteet tai rook-domainit halkaisijaltaan R Hamming-mitan suhteen C:n koodisanojen ympärillä täytyy tyhjentääselvennä rajallisen metrisen avaruuden . Koodin C peittävä säde on pienin R siten että C on R-peittävä. Jokainen täydellinen koodi on minimikokoinen peittokoodi.
Esimerkki
[muokkaa | muokkaa wikitekstiä]C = {0134,0223,1402,1431,1444,2123,2234,3002,3310,4010,4341} on 5-ary 2-peittävä neljän merkin pituinen koodi.[1]
Erityinen tapaus on jalkapallopelien pooli-ongelma, joka perustuu jalkapallovedonlyöntiin, jossa tavoitteena on saada aikaan n jalkapallo-ottelun vedonlyöntijärjestelmä, jossa lopputuloksesta riippumatta on korkeintaan R 'häviötä'. Siten n:lle ottelulle, joissa on korkeintaan yksi 'häviö', etsitään kolminkertaista peittoa, K3(n,1).
n | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 |
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
K3(n,1) | 1 | 3 | 5 | 9 | 27 | 71-73 | 156-186 | 402-486 | 1060-1269 | 2854-3645 | 7832-9477 | 21531-27702 | 59049 | 166610-177147 |
K3(n,2) | 1 | 3 | 3 | 8 | 15-17 | 26-34 | 54-81 | 130-219 | 323-555 | 729 | 1919-2187 | 5062-6561 | 12204-19683 | |
K3(n,3) | 1 | 3 | 3 | 6 | 11-12 | 14-27 | 27-54 | 57-105 | 117-243 | 282-657 | 612-1215 | 1553-2187 |
Peittävyysongelma
[muokkaa | muokkaa wikitekstiä]Pienimmän koon määrittely pituuden n peittävälle koodille q-ary R on erittäin kova ongelma. Monissa tapauksissa vain ylä- ja alarajat tunnetaan, ja niiden välillä on suuri ero. Jokainen peittävän koodin rakenne antaa ylärajan Kq(n, R). Alarajat sisältävät pallon peittävän rajan ja Rodemichin rajat ja .[2] Peittävyysongelma liittyy läheisesti pakkausongelmaan , joka on enimmäiskoon määrittäminen q-ary e- virheenkorjauskoodi pituudella n.
Sovelluksia
[muokkaa | muokkaa wikitekstiä]Standardointi koodien peittämiseksi luettelee seuraavat sovellukset [3].
- Puristus vääristymällä
- Virheiden ja poistojen purku
- Lähetys yhteenliitetyissä verkoissa
- Jalkapallopoolit[4]
- Kerran kirjoitetut muistot
- Berlekamp-Gale -peli
- Puheen koodaus. Puhekoodaus on datan pakkaussovellus puhetta sisältäviin digitaalisiin äänisignaaleihin. Puhekoodaus käyttää puhekohtaista parametrien estimointia käyttämällä äänisignaalin käsittelytekniikoita puhesignaalin mallintamiseen yhdistettynä yleisiin tiedonpakkausalgoritmeihin, jotka edustavat tuloksena olevia mallinnettuja parametreja kompaktissa bittivirrassa.
- Matkapulimien tietoliikenne
- Osajoukkosummat ja Cayley-kaaviot
Lähteet
[muokkaa | muokkaa wikitekstiä]- ↑ P.R.J. Östergård, Ylärajat q-peittokoodeille, IEEE Transactions on Information Theory, 37 (1991), 660-664
- ↑ E.R. Rodemich, Covering by rook-domains, Journal of Combinatorial Theory, 9 (1970), 117-128
- ↑ Elsevier (1997) ISBN 0-444-82511-8
- ↑ H. Hämäläinen, I. Honkala, S. Litsyn, P.R.J. Östergård, Football pools - a game for mathematicians, American Mathematical Monthly, 102 (1995), 579-588