Неравенство Гильберта

Нера́венство Ги́льберта — Варша́мова определяет предельные значения для параметров кодов (не обязательно линейных). Иногда употребляется название неравенство Гильберта — Шеннона — Варшамова, а в русскоязычной научной литературе — неравенство Варшамова — Гильберта.

Формулировка

Пусть

$A_q(n,\;d)$

обозначает максимально возможную мощность $q$-чного кода $C$ длины $n$ и расстояния Хэмминга $d$ ($q$-чным кодом является код с символами из поля $\mathbb{F}_q$, состоящего из $q$ элементов).

Тогда

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

Когда $q$ является степенью простого числа, можно упростить неравенство до $A_q(n,\;d)\geqslant q^k$, где $k$ — наибольшее целое число, для которого $A_q(n,\;d)\geqslant\frac{q^n}{\sum\limits_{j=0}^{d-2}\displaystyle\binom{n-1}{j}(q-1)^j}$.

Доказательство

Пусть $C$ — код максимальной мощности при длине $n$ и расстоянии Хэмминга $d$ :

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

Тогда для любого $x\in\mathbb{F}_q^n$ существует по крайней мере одно кодовое слово $c_x \in C$, так что расстояние Хэмминга $d(x,\;c_x)$ между $x$ и $c_x$ удовлетворяет

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

потому как в противном случае мы могли бы расширить код с помощью слова $x$, оставив расстояние Хэмминга $d$ неизменным, что противоречит предположению относительно максимальной мощности $|C|$.

Поэтому поле $\mathbb{F}_q^n$ можно упаковать объединением множеств всех сфер радиуса $d-1$ с центром в $c\in C$:

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

Объём каждого шара

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

потому что мы можем позволить (или выбрать) не более чем $(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.$

То есть

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

(подставив $|\mathbb{F}_q^n|=q^n$).

Литература

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

См. также

• Граница Синглтона
• Граница Хэмминга
• Граница Джонсона
• Граница Плоткина