Грава 4. СВЕРТОЧНОЕ КОДИРОВАНИЕ

1. Бесконечные деревья

В гл. 3 мы рассмотрели задачу о декодировании первого информационного символа в предположении, что каждая последовательность х длиной в таких символов задает некоторое передаваемое сообщение из конечного случайного древовидного множества Если передача ведется непрерывным образом и первоначальная процедура декодирования приложима поочередно к каждому последовательному символу в бесконечной последовательности х, то полное кодовое множество должно также простираться до бесконечности и расти как при всех (как при так и при ).

Бесконечное дерево легко образовать, используя понятие образующих элементов группового кода, рассмотренное в гл. 2. Пусть длина кодовых ограничений (которая соответствует длине блока для блоковых кодов) есть и пусть скорость передачи равна где целое. число. Выберем порождающую последовательность состоящую из двоичных символов

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

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

Рис. 13. Схематическое представление базисных элементов для бесконечного дерева. Каждое переносится на символов относительно подмножество базисных элементов для декодирования подмножество базисных элементов для декодирования

Для удобства мы будем всегда рассматривать лишь такие длины кодовых ограничений, которые делятся на

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

последовательности Так как порождающий элемент имеет длину ясно, что влияет только на первые символов в Определим далее усеченное множество как множество всех последовательностей, которые являются первыми символами из и ограничимся при декодировании х, рассмотрением вместо Из рис. 13 очевидно, что множество образует групповой код: оно состоит из линейных комбинаций образующих элементов. Образующие элементы, которые используются при определении на рис. 13 заключены в пунктирный прямоугольник, обозначенный символом

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

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

то ясно, что прибавление любого известного "хвоста“ s к и каждому из оставляет совокупность неизменной. Таким образом, особый групповой код впервые рассмотренный Элайесом [21] и названный им сверточным кодом, обладает свойствами групповой симметрии, рассмотренными в гл. 2. Поведение этого кода при декодировании во всех отношениях не зависит от выбора информационной последовательности х.