Асимптотическая точность границы Гильберта-Варшамова?

[sng1]

Слышал, что есть такая гипотеза об асимптотической точности границы Гильберта-Варшамова для двоичных кодов. Подскажите, пожалуйста, если кто знает, формулировку (можно ссылки). Доказана ли она? Может опровергнута?

[PAV]

Есть такое дело. Точная формулировка такова. Обозначим через $M(n,D)$ максимальный объем двоичного кода, имеющего длину $n$ и расстояние Хемминга $D$. Такой код исправляет примерно $D/2$ ошибок на одно кодовое слово. Будем рассматривать следующую асимптотику: $n\to\infty$, $D=nd$, $d=\mbox{\rm const}$, $0<d<1$. Это означает, что мы фиксируем среднюю долю ошибок на один передаваемый символ, который код способен исправлять (она равна $d/2$). Рассматривается функция

$$R(d)=\overline{\lim}\limits_{n\to\infty}\frac{\log M(n,dn)}{n}.$$

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

Граница Варшамова-Гильберта - это нижняя граница на эту функцию:

$$R(d)\ge 1-h(d)$$

, $0<d<1/2$, где $h(d)$ - двоичная энтропия: $h(d) = -d\log d-(1-d)\log(1-d)$.

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

С другой стороны, для функции $R(d)$ существует ряд оценок сверху, но все они больше, чем указанная нижняя оценка. Таким образом, явный вид этой функции неизвестен. Так вот гипотеза утверждает, что данная оценка дает как раз точное значение этой функции. Данная гипотеза существует практически все время существования теории информации, но доказать ее так и не удалось. Как сейчас обстоит дело с этим вопросом, я не знаю.

Добавлено спустя 46 секунд:

Все логарифмы в моем тексте - двоичные.

[sng1]

Спасибо за ответ. Не известно ли, что либо подобное для линейных кодов?

[sng1]

Еще один вопрос. Построены ли коды лежащие на границе в диапазоне $0<d<1/2$.

[PAV]

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

Тут проблема еще и в том, что когда речь идет о достаточно больших длинах, то практически важно не только (и не столько) построить код достаточно большого объема, но и чтобы существовал достаточно эффективный метод декодирования и исправления ошибок. Банальный перебор может работать слишком медленно.