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

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

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

Формулировка[править | править исходный текст]

Пусть

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

Литература[править | править исходный текст]

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

См. также[править | править исходный текст]