§ 2.3. Граница Гилберта

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

Теорема 6. При скорости передачи и кодовом ограничении существует по крайней мере один сверточный код с минимальным расстоянием где -наибольшее целое число, удовлетворяющее условию

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

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

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

Так как в начальном кодовом слове всего символов, то неравенство

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

или

а это и есть результат, который утверждается теоремой. Граница, устанавливаемая теоремой 6, эквивалентна границе Гилберта для минимального расстояния в блоковом коде с теми же скоростью передачи и длиной кодовой комбинации [12, стр. 67—68].

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

менее где наибольшее целое число, удовлетворяющее соотношению

где

Доказательство. Для неравенство (43) приводится к виду

Сумма слева ограничена сверху, согласно работе [4], так:

отсюда, если

или, что то же,

то неравенство (48) удовлетворяется и существует хотя бы один сверточный код с минимальным расстоянием не менее что и требовалось доказать.

Неравенство (47) представляет собой обычную асимптотическую форму границы Гилберта и будет использовано в гл. III как мера качества конкретных сверточных кодов.