4.4. СТРУКТУРА И ХАРАКТЕРИСТИКИ СВЕРТОЧНЫХ КОДОВ

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

Сверточный кодер как конечный автомат с памятью описывают диаграммой состояний. Внутренними состояниями кодера считают символы, содержащиеся в (К — 1) разрядах регистра (начиная от входа кодера). Кодер на рис. 4.3, а может находиться в одном из четырех состояний

Рис. 4.3, Кодеры СК: а — скорость 1/2; б - скорость 2/3

Рис. 4.4. Диаграммы состояний кода (7, 5): а — исходная; модифицированная

Диаграмма представляет собой направленный граф, который содержит все состояния и описывает возможные переходы из одного состояния в другое, а также символы выходов кодера, сопровождающие эти переходы. Пример диаграммы показан на рис. 4.4. В кружках указаны состояния кодера, стрелками — возможные переходы. Около стрелок показаны символы на выходе кодера соответствующие каждому переходу.

Диаграмма построена следующим образом. Первоначально кодер находится в состоянии 00 и поступление на вход символа и — 0 переводит его также в состояние 00. На выходе кодера будут символы На диаграмме этот переход обозначают петлей 00 около состояния 00. Далее при поступлении символа 1 кодер переходит в состояние 10 и на его выходе будут символы 11. Этот переход обозначают стрелкой из состояния 00 в состояние 10. Затем возможно поступление символа 0 либо 1. Кодер переходит в состояние либо 11, а символ на выходе будет 10 либо соответственно. Построение диаграммы заканчивается, когда просмотрены возможные переходы из каждого состояния во все остальные.

Для расчетов помехоустойчивости используют модифицированную диаграмму (рис. 4.4, б), которую получают, расчленяя исходную диаграмму в состоянии 00. Переходы маркируют переменными где число единиц в наборе символов, соответствующих данному переходу; если переход соответствует поступлению на вход информационного символа 0, и если соответствует поступлению на вход символа 1. Например, переходу из состояния 00 в состояние 10 соответствует набор символов Этот переход на модифицированной диаграмме обозначают как Развертка диаграммы

Рис. 4.5. Решетчатая диаграмма кода (7, 5)

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

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

Эта запись означает, что имеется один путь веса 5, обусловленный поступлением на вход кодера одного символа 1 (путь показан на рис. 4.4, а штриховой линией), два пути веса с двумя единицами на входе и т. д. Для простых графов функцию находят аналитически [4]. Для практически используемых кодов необходимы расчеты на ЭВМ (см. § 4.6).

В общем случае кодер содержит к входов (соответственно регистров) и выходов. Для описания кодера последовательности символов на его входах и выходах удобно представлять с использованием оператора задержки в виде бесконечных рядов:

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

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

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

При произвольной скорости символы на выходах кодера определяются выражением

Рассмотрим основные параметры сверточных кодов.

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

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

Столбцовое расстояние порядка I определяют как минимальный вес Хэмминга кодового слова состоящего из

ветвей при действии на входе кодера последовательности и с первым подблоком не равным нулю.

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

Для коротких кодов свободное расстояние можно определить по диаграмме состояний как минимальный вес пути из состояния 00 в это же состояние (исключая петлю у нулевого состояния). Нетрудно убедиться, например, по диаграмме рис. 4.4, а, что свободное расстояние (кратчайший путь, состоящий из трех ветвей 11, 10 и И, показан штриховой линией). Аналогично на решетчатой диаграмме свободное расстояние определяют как минимальный вес пути, ответвляющегося от узла 00 и вновь с ним сливающегося (на рис. 4.5 такой путь из трех ветвей показан штриховой линией).

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

При скорости 1/2 порождающие многочлены систематического кода

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

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

Коды со скоростью удовлетворяющие условию

называются быстропросматриваемыми. Многочлены таких кодов различаются только одним символом. Например, в коде (7,5) многочлены 111 и 101. В этом случае выделение информационной последовательности из принимаемых кодовых последовательностей можно производить сложением по модулю 2. При кодировании Кодовые последовательности принимаются с ошибками: Сложение дает Если ошибок в канале нет в результате сложения получаем информационную последовательность и задержанную на тактов. В канале с ошибками такой способ приводит к их размножению, поскольку учитываются как ошибки в первом подканале так и во втором . В общем случае возможно выделение информационных символов также из последовательностей несистематического кода при использовании инверсных схем, обладающих достаточно сложной структурой [79].