1.4.1. Верхняя граница Хэмминга

Здесь будет получена так называемая верхняя граница Хэмминга [3].

Теорема 1.1. Если существует -ичный блоковый код длины со скоростью и минимальным расстоянием Хэмминга или более, то

Доказательство. Для каждого кодового слова рассмотрим следующее множество последовательностей длины

т.е. включает все последовательности отличающиеся от до не более чем в компонентах. Следовательно, число последовательностей длины входящих в равно

Так как множества соответствующие различным кодовым словам, не имеют общих элементов, то

где К — общее число кодовых слов. Отсюда и из равенства следует справедливость теоремы.

Если для некоторого кода верхняя граница Хэмминга выполняется со знаком равенства, то код называется совершенным. Как можно видеть из вывода границы Хэмминга, для

совершенных кодов введенные выше множества или, другими словами, «сферы» радиуса центрами которых являются кодовые слова, попарно не пересекаются и заполняют все пространство В силу этого совершенные коды иногда называют также плотноупакованными кодами.

Кроме тривиальных двоичных кодов из примера 1.1, кодовые слова которых получаются повторением одного и того же символа некоторое фиксированное число раз, совершенными кодами являются также следующие: 1) -ичные совершенные коды, исправляющие одиночные ошибки и имеющие длину где простое число (обобщенные коды Хэмминга из утверждения ] нелинейные коды Васильева [12] и Шёнгейма [13] с теми же параметрами), 2) двоичный -код Голея, исправляющий тройные ошибки (пример 4.2) и 3) троичный -код Голея. исправляющий двойные ошибки (пример 4.3. Если является степенью простого числа, то не существует других -ичных совершенных кодов, за исключением кодов, эквивалентных указанным выше, и тривиальных нелинейных кодов, получающихся сложением каждого кодового слова указанных выше линейных совершенных кодов с некоторой фиксированной последовательностью длины Это было доказано Титвайненом

Утверждение 1.8. Если существует -ичный систематический совершенный код длины то

где число проверочных символов.

Идея доказательства. Поскольку код систематический, то Далее следует воспользоваться верхней границей Хэмминга в частном случае

Как будет показано ниже (утверждение 3.2), если является степенью простого числа, -ичные совершенные коды длины всегда существуют.

Утверждение 1.9. (Фарр [2, 4]). Если -ичный блоковый код длины со скоростью такой, что

то

Краткое доказательство.

Отсюда и из теоремы 1.1, непосредственно следует, что неравенство не может иметь места. Это утверждение используется для получения верхней оценки минимального расстояния некоторых двоичных БЧХ-кодов (см. гл. 4) [2, 4].

Верхнюю границу Хэмминга можно записать следующим образом:

Используя неравенство Чернова, можно показать, что при фиксированном отношении и достаточно больших граница Хэмминга имеет вид

Так как то в интервале функция монотонно возрастает от 0 до 1. Поэтому для любого существует единственное значение х, при котором Обозначим это значение х через Из формулы (1.7) непосредственно следует справедливость следующего утверждения.

Следствие 1.1. Для любого блокового кода со скоростью и минимальным расстоянием при достаточно больших