Hammingova hranice

V teorii kódování Hammingova hranice definuje limity možných hodnot pro parametry libovolného blokového kódu . Také známý jako sférická hranice balení . Kódy, které dosáhnou Hammingovy hranice, se nazývají dokonalé nebo těsně sbalené kódy .

Formulace

Označme maximální možnou mohutnost -ary block length code a minimální vzdálenost ( -ary block length code je podmnožina slov s abecedou sestávající z prvků). $A_q(n,\;d)$ $q$ $C$ $n$ $d$ $q$ $n$ $\mathcal{A}_q^n$ $\mathcal{A}_q$ $q$

Pak

A_q(n,\;d)\leqslant\frac{q^n}{\displaystyle\sum_{k=0}^t\binom{n}{k}(q-1)^k},

kde

t=\levá\lpodlaží\frac{d-1}{2}\pravá\rpodlaží.

Důkaz

Podle definice , pokud k přenosu kódového slova došlo před chybami, pak s pomocí dekódování omezeného minimální vzdáleností budeme schopni přesně rozpoznat přenášené kódové slovo . $d$ $t=\levá\lpodlaží\frac{d-1}{2}\pravá\rpodlaží$

Pro dané kódové slovo zvažte kouli o poloměru kolem . Vzhledem k tomu, že tento kód je schopen opravovat chyby, žádná koule se s žádnou jinou neprotíná a obsahuje $c\in C$ $t$ $C$ $t=\levá\lpodlaží\frac{d-1}{2}\pravá\rpodlaží$

\sum_{k=0}^t \binom{n}{k}(q-1)^k

slova, protože můžeme dovolit (nebo méně) znakům (všech znaků ve slově) nabývat jedné z možných hodnot odlišných od hodnoty odpovídajícího znaku daného slova (připomeňme, že samotný kód je -ic ).

t

n

(q-1)

q

Označme počet slov v . Spojením koulí kolem všech kódových slov si všimneme, že výsledná sada je obsažena v . Protože koule jsou disjunktní, můžeme sečíst prvky každé z nich a získat $M$ $C$ $\mathcal{A}_q^n$

M\times\sum_{k=0}^t\binom{n}{k}(q-1)^k\leqslant|\mathcal{A}_q^n|=q^n,

odkud pro jakýkoli kód $C$

M\leqslant\frac{q^n}{\displaystyle\sum_{k=0}^t\binom{n}{k}(q-1)^k},

a proto,

A_q(n,\;d)\leqslant\frac{q^n}{\displaystyle\sum_{k=0}^t\binom{n}{k}(q-1)^k}.

Perfektní kódy

Kódy, které dosahují Hammingovy hranice, se nazývají dokonalé kódy . Byly objeveny následující typy dokonalých kódů: Hammingovy kódy a Golayovy kódy . Existují také triviální dokonalé kódy: binární kódy liché délky, kódy s jedním kódovým slovem a kódy, které zahrnují celou sadu . $F_q^n$

Titvainen a Van Lint dokázali, že každý netriviální dokonalý kód má parametry Hammingova kódu nebo Golayova kódu [1] [2] .

Poznámky

↑ Tietavainen A., Perko A. Neexistují žádné neznámé dokonalé binární kódy. Annales Universitatis Turkuensis . Ser. A, I 148, 3-10[6], 1971.
↑ Lint van JH Věty o neexistenci pro dokonalé kódy opravující chyby. — Počítače v algebře a teorii čísel . — Sv. IV [6], 1971.

Literatura