Varshamov-Gilbert raja

Kokeneet kirjoittajat eivät ole vielä tarkistaneet sivun nykyistä versiota, ja se voi poiketa merkittävästi 18.11.2021 tarkistetusta versiosta . vahvistus vaatii 1 muokkauksen .

Varshamov-Gilbert-sidottu on epäyhtälö, joka määrittää koodiparametreille raja-arvot (ei välttämättä lineaarisia ), jotka Edgar Gilbert ja Rom Varshamov ovat hankkineet itsenäisesti . Joskus käytetään nimeä Gilbert- Shannon - Varshamov epätasa-arvo ja ulkomaisessa tieteellisessä kirjallisuudessa - Gilbert-Varshamov epäyhtälö .

Sanamuoto

Päästää

A_q(n,\;d)

tarkoittaa pituus- ja Hamming-etäisyyden -:nnen koodin suurinta mahdollista kardinaalisuutta ( -:s koodi on elementeistä koostuvan kentän symboleilla varustettu koodi ). $q$ $C$ $n$ $d$ $q$ $\mathbb {F} _{q}$ $q$

Sitten

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

Milloin on alkuluvun potenssi, epäyhtälö voidaan yksinkertaistaa muotoon , missä on suurin kokonaisluku , jolle . $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}$

Todiste

Olkoon pituuden ja Hamming-etäisyyden maksimitehokoodi : $C$ $n$ $d$

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

Sitten millä tahansa on vähintään yksi koodisana , joten Hamming-etäisyys ja välillä täyttyy $x\in\mathbb{F}_q^n$ $c_x \in C$ $d(x,\;c_x)$ $x$ $c_x$

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

koska muuten voisimme laajentaa koodia sanalla , jättäen Hammingin etäisyyden ennalleen, mikä on ristiriidassa maksimitehooletuksen kanssa . $x$ $d$ $|C|$

Siksi kenttä voidaan pakata yhdistämällä kaikkien sädepallojen joukkoja , joiden keskipiste on : ${\mathbb {F}}_{q}^{n}$ $d-1$ $c\in C$

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

Jokaisen pallon tilavuus

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

koska voimme antaa (tai valita ) enintään -: nnen koodisanan komponenttien ottaa yhden muista mahdollisista arvoista. Siksi seuraava epäyhtälö on totta $(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.

Tuo on

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

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

Kirjallisuus

Gilbert FI Signaaliaakkosten vertailu // Bell System Technical Journal , 31:504-522 [1], 1952.
Varshamov R. R. Arvio signaalien määrästä koodeissa, joissa on virhekorjaus // Neuvostoliiton tiedeakatemian raportit , 117(5):739-741 [1], 1957.

Varshamov-Gilbert raja

Sanamuoto

Todiste

Kirjallisuus

Katso myös