§ 2.2. Алгебраическая структура

Проведем теперь тщательное исследование множества начальных кодовых слов сверточного кода, описываемого соотношениями (38) и (39). Наша цель состоит в том, чтобы установить некоторые свойства этих кодовых слов. Они понадобятся позже как основа при выводе границы Гилберта и границы для класса случайных сверточных кодов.

Начнем с доказательства леммы. Пока она выглядит совершенно абстрактной, но в дальнейшем ее полезность станет очевидной.

Лемма 1. Если задан произвольный полином степень которого не превышает и в котором не равно нулю, то, каков бы ни был любой из полиномов степени не выше все полиномы

различны и, следовательно, каждый из полиномов степени не выше встречается один и только один раз.

Доказательство. Допустим, что существует полином степени не выше такой, что

тогда

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

Таким образом, различные полиномы определяют различные что и доказывает лемму.

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

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

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

Теорема 5. Если задано начальное кодовое слово в котором по крайней

мере один из символов отличен от нуля, то это начальное кодовое слово принадлежит в точности различным сверточным кодам со скоростью передачи и кодовым ограничением

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

Из соотношения (38) следует, что задание начального кодового слова фиксирует полиномы Рассмотрим проверочные последовательности, которые задаются системой (39). Эта система может быть записана в виде

для Для любого фиксированного выбора полиномов левая часть этого равенства является фиксированным полиномом. Тогда из леммы 1 следует, что это равенство будет удовлетворено одним и только одним выбором полинома

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

Покажем теперь, как можно использовать теорему 5 при выводе границы Гилберта для сверточных кодов.