Неравенство Гильберта — Варшамова

Неравенство Гильберта — Варшамова

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

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

Пусть

$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.

См. также

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