Граница Варша́мова — Ги́лберта — неравенство, определяющее предельные значения для параметров кодов (не обязательно линейных), полученное независимо и Ромом Варшамовым. Иногда употребляется название неравенство Гилберта — Шеннона — Варшамова, а в иноязычной научной литературе — неравенство Гилберта — Варшамова.
Формулировка Пусть
обозначает максимально возможную мощность -чного кода длины и расстояния Хэмминга (-чным кодом является код с символами из поля , состоящего из элементов).
Тогда
Когда является степенью простого числа, можно упростить неравенство до , где — наибольшее целое число, для которого .
Доказательство Пусть — код максимальной мощности при длине и расстоянии Хэмминга :
Тогда для любого существует по крайней мере одно кодовое слово , так что расстояние Хэмминга между и удовлетворяет
потому как в противном случае мы могли бы расширить код с помощью слова , оставив расстояние Хэмминга неизменным, что противоречит предположению относительно максимальной мощности .
Поэтому поле можно упаковать объединением множеств всех сфер радиуса с центром в :
Объём каждого шара
потому что мы можем позволить (или выбрать) не более чем -му из компонентов кодового слова принять одно из других возможных значений. Поэтому верно следующее неравенство
То есть
(подставив ).
Литература Gilbert E. N. A comparison of signalling alphabets // Bell System Technical Journal, 31:504-522 , 1952. Варшамов Р. Р. Оценка числа сигналов в кодах с коррекцией ошибок // Доклады Академии наук СССР, 117(5):739-741 , 1957.
См. также Граница Синглтона Граница Хэмминга Граница Джонсона Граница Плоткина
Категория:Теория информации Категория:Теория кодирования Категория:Неравенства Категория:Теоремы теории информации