Krycí kód - Covering code - Wikipedia

v teorie kódování, a krycí kód je sada prvků (tzv kódová slova) v prostoru s vlastností, že každý prvek prostoru je v pevné vzdálenosti od nějakého kódového slova.

Definice

Nechat ${ displaystyle q geq 2}$, ${ displaystyle n geq 1}$, ${ displaystyle R geq 0}$ být celá čísla.A kód ${ displaystyle C subseteq Q ^ {n}}$ přes abeceda Q o velikosti |Q| = q je nazývánq-ary R-krytí kódu délky npokud pro každé slovo ${ displaystyle y v Q ^ {n}}$ tady je kódové slovo ${ displaystyle x v C}$takové, že Hammingova vzdálenost ${ displaystyle d_ {H} (x, y) leq R}$Jinými slovy koule (nebo koule nebo havarované domény) poloměr Rs ohledem na Hamminga metrický kolem kódových slov z C muset vyčerpat konečný metrický prostor ${ displaystyle Q ^ {n}}$.v poloměr zakrytí kódu C je nejmenší R takhle C je R-krytí perfektní kód je krycí kód minimální velikosti.

Příklad

C = {0134,0223,1402,1431,1444,2123,2234,3002,3310,4010,4341} je pětičlenný 2-krycí kód délky 4.^[1]

Krycí problém

The odhodlání minimální velikosti ${ displaystyle K_ {q} (n, R)}$ a q-ary R-krytí kódu délky n je velmi těžký problém. V mnoha případech pouze horní a dolní mez jsou známy s velkou mezerou mezi nimi. Každá konstrukce krycího kódu dává horní hranici K._q(n, RDolní hranice zahrnují kouli pokrývající vázané a Rodemichovy hranice ${ displaystyle K_ {q} (n, 1) geq q ^ {n-1} / (n-1)}$ a ${ displaystyle K_ {q} (n, n-2) geq q ^ {2} / (n-1)}$.^[2]Problém s krytím úzce souvisí s problémem s balením v ${ displaystyle Q ^ {n}}$, tj. určení maximální velikosti a q-ary E-oprava chyby kód délky n.

Fotbalové bazény problém

Specifickým případem je problém s fotbalovými bazény, na základě fotbalový bazén sázení, kde je cílem předpovědět výsledky n fotbalové zápasy jako domácí výhra, remíza nebo výhra, nebo alespoň předvídání n - 1 z nich s více sázkami. Tak ternární krytí, K.₃(n, 1), se hledá.

Li ${ displaystyle n = { tfrac {1} {2}} (3 ^ {k} -1)}$ pak 3^n-k jsou potřeba, tak pro n = 4, k = 2, 9 je potřeba; pro n = 13, k = 3, je potřeba 59049.^[3] Nejlepší hranice známé od roku 2011^[4] jsou

Aplikace

Standardní práce^[5] o krycích kódech uvádí následující aplikace.

• Komprese s zkreslení
• Komprese dat
• Dekódování chyby a výmazy
• Vysílání v propojovacích sítích
• Fotbalové bazény^[6]
• Jednorázové vzpomínky
• Hra Berlekamp-Gale
• Kódování řeči
• Buněčný telekomunikace
• Podmnožina částky a Cayleyovy grafy

Reference

externí odkazy

• Literatura o krycích kódech
• Hranice dál ${ displaystyle K_ {q} (n, R)}$