Просмотр кода страницы Граница Варшамова — Гилберта

'''Граница Варша́мова — Ги́лберта''' — неравенство, которое определяет предельные значения для параметров кодов (не обязательно [[линейный код|линейных]]), полученное независимо {{iw|Гилберт, Эдгар|Эдгаром Гилбертом|en|Edgar Gilbert}} и {{iw|Варшамов, Ром Рубенович|Ромом Варшамовым|en|Rom Varshamov}}. Иногда употребляется название ''неравенство Гилберта — [[Шеннон, Клод Элвуд|Шеннона]] — Варшамова'', а в иноязычной научной литературе — ''неравенство Гилберта — Варшамова''.

== Формулировка ==
Пусть
: <math>A_q(n,\;d)</math>
обозначает максимально возможную мощность <math>q</math>-чного кода <math>C</math> длины <math>n</math> и [[Расстояние Хэмминга|расстояния Хэмминга]] <math>d</math> (<math>q</math>-чным кодом является код с символами из [[Поле (алгебра)|поля]] <math>\mathbb{F}_q</math>, состоящего из <math>q</math> элементов).

Тогда
: <math>A_q(n,\;d)\geqslant\frac{q^n}{\displaystyle \sum\limits_{j=0}^{d-1}\displaystyle\binom{n}{j}(q-1)^j}.</math>
Когда <math>q</math> является степенью простого числа, можно упростить неравенство до <math>A_q(n,\;d)\geqslant q^k</math>, где <math>k</math> — наибольшее целое число, для которого <math>\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}</math>.

== Доказательство ==
Пусть <math>C</math> — код максимальной мощности при длине <math>n</math> и [[Расстояние Хэмминга|расстоянии Хэмминга]] <math>d</math> :
: <math>|C|=A_q(n,\;d).</math>
Тогда для любого <math>x\in\mathbb{F}_q^n</math> существует по крайней мере одно кодовое слово <math>c_x \in C</math>, так что [[расстояние Хэмминга]] <math>d(x,\;c_x)</math> между <math>x</math> и <math>c_x</math> удовлетворяет
: <math>d(x,\;c_x)\leqslant d-1,</math>
потому как в противном случае мы могли бы расширить код с помощью слова <math>x</math>, оставив [[Расстояние Хемминга|расстояние Хэмминга]] <math>d</math> неизменным, что противоречит предположению относительно максимальной мощности <math>|C|</math>.

Поэтому поле <math>\mathbb{F}_q^n</math> можно упаковать [[Объединение множеств|объединением множеств]] всех [[сфера|сфер]] радиуса <math>d-1</math> с центром в <math>c\in C</math>:
: <math>\mathbb{F}_q^n =\bigcup_{c\in C}B(c,\;d-1).</math>
Объём каждого шара
: <math>\sum_{j=0}^{d-1}\binom{n}{j}(q-1)^j,</math>
потому что мы можем позволить (или [[биномиальные коэффициенты|выбрать]]) не более чем <math>(d-1)</math>-му из <math>n</math> компонентов кодового слова принять одно из <math>(q-1)</math> других возможных значений. Поэтому верно следующее неравенство
: <math>|\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.</math>
То есть
: <math>A_q(n,\;d)\geqslant\frac{q^n}{\sum\limits_{j=0}^{d-1}\displaystyle\binom{n}{j}(q-1)^j}</math>
(подставив <math>|\mathbb{F}_q^n|=q^n</math>).

== Литература ==
* ''Gilbert E. N.'' A comparison of signalling alphabets // ''Bell System Technical Journal'', 31:504-522 [1], 1952.
* ''Варшамов Р. Р.'' Оценка числа сигналов в кодах с коррекцией ошибок // ''Доклады Академии наук СССР'', 117(5):739-741 [1], 1957.

== См. также ==
* [[Граница Синглтона]]
* [[Граница Хэмминга]]
* [[Граница Джонсона]]
* [[Граница Плоткина]]

[[Категория:Теория информации]]
[[Категория:Теория кодирования]]
[[Категория:Неравенства]]
[[Категория:Теоремы теории информации]]