Hranice Varshamov-Gilbert

Aktuální verze stránky ještě nebyla zkontrolována zkušenými přispěvateli a může se výrazně lišit od verze recenzované 18. listopadu 2021; ověření vyžaduje 1 úpravu .

Varshamov-Gilbertova mez je nerovnost, která definuje mezní hodnoty pro parametry kódu (ne nutně lineární ), získané nezávisle Edgarem Gilbertem a Romem Varshamovem . Někdy se používá název Gilbert- Shannon - Varshamovova nerovnost a v zahraniční vědecké literatuře - Gilbert-Varshamovova nerovnost .

Formulace

Nechat

A_q(n,\;d)

označuje maximální možnou mohutnost -tého kódu délky a Hammingovy vzdálenosti ( -tý kód je kód se symboly z pole sestávajícího z prvků). $q$ $C$ $n$ $d$ $q$ $\mathbb {F} _{q}$ $q$

Pak

A_q(n,\;d)\geqslant\frac{q^n}{\displaystyle \sum\limits_{j=0}^{d-1}\displaystyle\binom{n}{j}(q-1) ^j}.

Když je mocnina prvočísla , lze nerovnost zjednodušit na , kde je největší celé číslo pro které . $q$ $A_q(n,\;d)\geqslant q^k$ $k$ $\displaystyle A_q(n,\;d)\geqslant\displaystyle \frac{q^n}{\displaystyle \sum\limits_{j=0}^{d-2}\displaystyle \binom{n-1}{j }(q-1)^j}$

Důkaz

Nechť je kód maximálního výkonu pro délku a Hammingovu vzdálenost : $C$ $n$ $d$

|C|=A_q(n,\;d).

Pak pro kterékoli existuje alespoň jedno kódové slovo , takže Hammingova vzdálenost mezi a vyhovuje $x\in\mathbb{F}_q^n$ $c_x \in C$ $d(x,\;c_x)$ $X$ $c_x$

d(x,\;c_x)\leqslant d-1,

protože jinak bychom mohli rozšířit kód o slovo , ponechat Hammingovu vzdálenost nezměněnou, což je v rozporu s předpokladem maximálního výkonu . $X$ $d$ $|C|$

Pole tedy může být zabaleno spojením množin všech sfér o poloměru se středem v : ${\mathbb {F}}_{q}^{n}$ $d-1$ $c\in C$

\mathbb{F}_q^n =\bigcup_{c\in C}B(c,\;d-1).

Objem každého míče

\sum_{j=0}^{d-1}\binom{n}{j}(q-1)^j,

protože můžeme nechat (nebo zvolit ) nanejvýš -th komponenty kódového slova, aby nabyly jedné z dalších možných hodnot. Proto platí následující nerovnost $(d-1)$ $n$ $(q-1)$

|\mathbb{F}_q^n|=\left|\bigcup_{c\in C}B(c,\;d-1)\right|\leqslant\bigcup_{c\in C}|B(c, \;d-1)|=|C|\sum_{j=0}^{d-1}\binom{n}{j}(q-1)^j.

To znamená

A_q(n,\;d)\geqslant\frac{q^n}{\sum\limits_{j=0}^{d-1}\displaystyle\binom{n}{j}(q-1)^j }

(nahrazení ). $|\mathbb{F}_q^n|=q^n$

Literatura

Gilbert EN Porovnání signalizačních abeced // Bell System Technical Journal , 31:504-522 [1], 1952.
Varshamov R. R. Odhad počtu signálů v kódech s opravou chyb // Zprávy Akademie věd SSSR , 117(5):739-741 [1], 1957.

Hranice Varshamov-Gilbert

Formulace

Důkaz

Literatura

Viz také