Есть такое дело. Точная формулировка такова. Обозначим через
максимальный объем двоичного кода, имеющего длину
и расстояние Хемминга
. Такой код исправляет примерно
ошибок на одно кодовое слово. Будем рассматривать следующую асимптотику:
,
,
,
. Это означает, что мы фиксируем среднюю долю ошибок на один передаваемый символ, который код способен исправлять (она равна
). Рассматривается функция
Содержательный смысл ее довольно простой - это максимальная (точнее говоря, предельная) скорость передачи информации (число бит информации на один передаваемый двоичный символ), которую можно достичь, исправляя заданную долю ошибок.
Граница Варшамова-Гильберта - это нижняя граница на эту функцию:
,
, где
- двоичная энтропия:
.
Эта граница утверждает, что с указанной скоростью информацию передавать можно. Она основана на утверждении о существовании кода определенного объема, подробности можно почитать, например, в
википедии. Но это утверждение не конструктивное в том смысле, что оно не дает простого алгоритма построения такого кода, а только лишь доказывает, что он существует.
С другой стороны, для функции
существует ряд оценок сверху, но все они больше, чем указанная нижняя оценка. Таким образом, явный вид этой функции неизвестен. Так вот гипотеза утверждает, что данная оценка дает как раз точное значение этой функции. Данная гипотеза существует практически все время существования теории информации, но доказать ее так и не удалось. Как сейчас обстоит дело с этим вопросом, я не знаю.
Добавлено спустя 46 секунд:
Все логарифмы в моем тексте - двоичные.