§ 2.4. Верхняя граница минимального расстояния

Способом, аналогичным использованному Плоткиным [13] для блоковых кодов, можно подсчитать средний вес начального кодового слова хотя бы с одним отличным от нуля первым информационным символом, а затем воспользоваться средним весом, чтобы оценить минимальное расстояние.

Так как множество начальных кодовых слов сверточного кода образует линейный код, а следовательно, группу (ср. § 1.1), то каждый элемент из встречается на данной позиции в точности в части всех кодовых слов. (Мы полагаем, что для каждого по крайней мере один из символов отличен от нуля. Это необходимое и достаточное условие того, что ни одна из позиций в начальном кодовом слове не будет содержать только нули во всех кодовых словах, т. е. не будет ни одной «бесполезной» позиции.) Этот факт проверяется следующим образом: сложение любого кодового слова, имеющего в данной позиции элемент со всеми кодовыми словами должно, согласно свойству замкнутости группы, воспроизвести первоначальное множество кодовых слов в некотором порядке. Тогда нуль на данной позиции окажется в стольких словах, в скольких первоначально на этой позиции стоял элемент Так как 0 выбран произвольно, то во множестве кодовых слов все элементы поля должны встретиться на данной позиции одинаковое число раз. Таким образом, так как в множестве начальных кодовых слов имеется всего кодовых слов, а в каждом слове позиций, то общее число ненулевых позиций во всем множестве начальных кодовых слов равно

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

элементов в множестве всех таких начальных кодовых слов.

Средний вес кодового слова, в котором хотя бы один из множества первых информационных символов отличен от нуля, изображается в виде

Используя предыдущие результаты, это равенство можно переписать так:

Равенство (52) можно привести к виду

Поскольку минимальный вес кодового слова с некоторыми ненулевыми первыми информационными символами должен быть целым числом, которое в свою очередь не должно превосходить среднего веса, мы получаем в итоге следующий результат.

Теорема 7. Минимальное расстояние сверточного кода удовлетворяет неравенству

Следствие. Минимальное расстояние двоичного сверточного кода со скоростью передачи удовлетворяет неравенству

Доказательство следствия дается подстановкой в неравенство (54). Неравенство (55) представляет собой ту форму верхней границы

минимального расстояния, которая будет использована в гл. III.

Неравенства (54) и (55) не дают хороших верхних границ минимального расстояния при произвольном так как для больших эти границы лишь приблизительно не зависят от скорости передачи Для нас эти границы интересны по следующей причине. В § 3.6 мы докажем существование класса кодов с заранее заданными значениями и для которых в (55) достигается знак равенства.