Граница Варшамова — Гилберта

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

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

Пусть

$A_{q}(n,\;d)$

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

Тогда

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

Когда $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}}}$.

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

Пусть $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}$).

Литература

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

См. также

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