Peittokoodi

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