В теории кодирования оценка Гилберта – Варшамова ( полученная Эдгаром Гилбертом [1] и независимо Ром Варшамовым [2] ) является пределом на параметры (не обязательно линейного ) кода . Иногда она известна как граница Гилберта – Шеннона – Варшамова (или граница GSV ), но название «граница Гилберта – Варшамова», безусловно, является наиболее популярной. Варшамов доказал эту оценку, используя вероятностный метод для линейных кодов. Подробнее об этом доказательстве см. Граница Гилберта – Варшамова для линейных кодов .
Заявление о привязке
Позволять
обозначают максимально возможный размер q -арного кодадлины n и минимального расстояния Хэмминга d ( q -арный код - это код над полем из q элементов).
Потом:
Доказательство
Позволять быть кодом длины и минимальное расстояние Хэмминга имеющий максимальный размер:
Тогда для всех , существует хотя бы одно кодовое слово такое, что расстояние Хэмминга между а также удовлетворяет
так как в противном случае мы могли бы добавить x к коду, сохраняя минимальное расстояние Хэмминга кода - противоречие о максимальности .
Следовательно, весь содержится в объединении всех шаров радиусаимея свой центр в некоторых :
Теперь у каждого шара есть размер
поскольку мы можем разрешить (или выбрать ) до принадлежащий Компоненты кодового слова отклоняться (от значения соответствующего компонента шара центра ) к одному из возможные другие значения (напомним: код q-ичный: принимает значения в ). Отсюда выводим
Это:
Усовершенствование в случае основной мощности
Для степени q можно улучшить оценку догде k - наибольшее целое число, для которого
Смотрите также
Рекомендации
- ^ Гилберт, Е. Н. (1952), "Сравнение сигналов алфавитов", Технический журнал Bell System , 31 : 504-522, DOI : 10.1002 / j.1538-7305.1952.tb01393.x.
- ^ Варшамов Р. Р. (1957) "Оценка количества сигналов в кодах с исправлением ошибок", Докл. Акад. АН СССР , 117 : 739–741..