Peittokoodi

peittokoodi^lä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

Olkoon $q\geq 2$, $n\geq 1$, $R\geq 0$ kokonaislukuja. Koodia $C\subset Q^{n}$ yli aakkoston Q kooltaan |Q| = q kutsutaan q R -peittäväksi koodiksi pituudeltaan n, jos jokaiselle sanalle $y\in Q^{n}$ on olemassa sellainen koodisana $x\in C$, että Hammingin etäisyys $d_{H}(x,y)\leq R$. 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 $Q^{n}$. 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.

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, K₃(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

Pienimmän koon määrittely $K_{q}(n,R)$ 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 K_q(n, R). Alarajat sisältävät pallon peittävän rajan ja Rodemichin rajat $K_{q}(n,1)\geq q^{n-1}/(n-1)$ ja $K_{q}(n,n-2)\geq q^{2}/(n-1)$. Peittävyysongelma liittyy läheisesti pakkausongelmaan $Q^{n}$, 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