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

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

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

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(nR). 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

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
  1. P.R.J. Östergård, Ylärajat q-peittokoodeille, IEEE Transactions on Information Theory, 37 (1991), 660-664
  2. E.R. Rodemich, Covering by rook-domains, Journal of Combinatorial Theory, 9 (1970), 117-128
  3. Elsevier (1997)  ISBN 0-444-82511-8
  4. 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