Peittokoodi

Wikipediasta
(Ohjattu sivulta Peittävä koodi)
Siirry navigaatioon Siirry hakuun

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.

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.

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

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
  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