[6].
Заметим, что граница Хэмминга – это максимально возможное число слов в коде, исправляющем ошибки. Но это еще не означает, что такой максимальный код можно найти. Представьте, что мы имеем дело с обычными шарами. Нельзя уложить круглые апельсины в ведро или коробку так, чтобы между соседними апельсинами не было пустот! Где же гарантия, что все последовательности из нулей и единиц можно разбить на шары Хэмминга так, чтобы они не пересекались и между ними не было свободного места? Оказывается, такое разбиение во многих случаях возможно. Мы не станем здесь описывать конструкцию, ее можно найти в специальной литературе (см.{6}).
Впрочем, сделано в этом направлении далеко не все. Конструкции есть, но только асимптотические, то есть такие, в которых длина кодового слова очень большая и увеличивается до бесконечности, а количество ошибок при этом маленькое и фиксированное. Однако во многих практических задачах чем длиннее кодовое слово, тем больше ошибок. В такой ситуации проблема отыскания правильных верхних границ и построения максимальных кодов по-прежнему открыта! Более того, в этой ситуации известно, что граница Хэмминга, как правило, не точна, и есть еще масса более аккуратных оценок, среди которых и оценка Владимира Иосифовича Левенштейна, замечательного российского математика, и границы линейного программирования. Эти конструкции очень сложны и выходят далеко за рамки нашей книги.
Особый интерес вызывают так называемые равновесные коды. В них все кодовые слова содержат одинаковое количество единиц. Для таких кодов можно найти границу, аналогичную границе Хэмминга. И снова возникает вопрос о существовании равновесного кода, достигающего полученной границы. В начале 80-х годов XX века Войцех Рёдль придумал очень хитрую вероятностную технику, позволившую доказать наличие равновесных кодов, в которых число кодовых слов асимптотически равно верхней границе{7}.
Буквально пару лет назад Питер Киваш из Оксфордского университета объявил о построении равновесных кодов, в которых количество слов достигает теоретической верхней границы. Это очень объемная и трудная математическая работа; она до сих пор тщательно проверяется и потому опубликована только в интернете{8}.
Что же касается случаев, когда число ошибок и число единиц в равновесном коде пропорциональны длине кодового слова, то здесь пока все безнадежно. А именно эти случаи особенно важны! Вот такая она, математика. На первый взгляд кажется, что все давно известно. А на самом деле вопросов, на которые по-прежнему нет ответов, несмотря на всю естественность их возникновения и важность для практики, гораздо больше, чем тех, ответы на которые уже получены.