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

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

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

Формулировка[править | править вики-текст]

Пусть

обозначает максимально возможную мощность -чного кода длины и расстояния Хэмминга (-чным кодом является код с символами из поля , состоящего из элементов).

Тогда

Когда является степенью простого числа, можно упростить неравенство до , где  — наибольшее целое число, для которого .

Доказательство[править | править вики-текст]

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

Тогда для любого существует по крайней мере одно кодовое слово , так что расстояние Хэмминга между и удовлетворяет

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

Поэтому поле можно упаковать объединением множеств всех сфер радиуса с центром в :

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

потому что мы можем позволить (или выбрать) не более чем -му из компонентов кодового слова принять одно из других возможных значений. Поэтому верно следующее неравенство

То есть

(подставив ).

Литература[править | править вики-текст]

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

См. также[править | править вики-текст]