Peittokoodi 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
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ää 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
C = {0134,0223,1402,1431,1444,2123,2234,3002,3310,4010,4341} on 5-ary 2-peittävä neljän merkin pituinen koodi.P.R.J. Östergård, Ylärajat q-peittokoodeille, IEEE Transactions on Information Theory, 37 (1991), 660-664
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 815-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
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 .E.R. Rodemich, Covering by rook-domains, Journal of Combinatorial Theory, 9 (1970), 117-128 Peittävyysongelma liittyy läheisesti pakkausongelmaan , joka on enimmäiskoon määrittäminen q-ary e- virheenkorjauskoodi pituudella n.
Sovelluksia
Standardointi koodien peittämiseksi luettelee seuraavat sovellukset Elsevier (1997) .
Puristus vääristymällä Virheiden ja poistojen purku Lähetys yhteenliitetyissä verkoissa JalkapallopoolitH. 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 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
Luokka:Koodausmenetelmät Luokka:Diskreetti matematiikka