Peittokoodi

Koodausteoriassa peittokoodi on 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,
A koodi  yli aakkosten 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 R Hammingin suhteen  metristen koodisanojen ympärillä C täytyy tyhjentää rajallisen metrisen avaruuden . Koodin peittävä säde C on pienin R kuten 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.

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

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

 Puristus vääristymällä
 Virheiden ja poistojen purku
 Lähetys yhteenliitetyissä verkoissa
 Jalkapallopoolit
 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 

Koodausmenetelmät
Diskreetti matematiikka