ПОЗНАВАТЕЛЬНОЕ

Оси и плоскости тела человека - Тело человека состоит из определенных топографических частей и участков, в которых расположены органы, мышцы, сосуды, нервы и т.д.

Отёска стен и прирубка косяков - Когда на доме не достаёт окон и дверей, красивое высокое крыльцо ещё только в воображении, приходится подниматься с улицы в дом по трапу.

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

Общие понятия о сверточном кодировании

СВЁРТОЧНЫЕ КОДЫ

и описание работы сверточного кодера.

В течение последнего десятилетия наиболее популярным видом кодирования было свёрточное кодирование, поскольку во многих приложениях свёрточные коды лучше блочных при той же конструктивной сложности кодера и декодера. В разработку сверточных кодов большой вклад внесли американские ученые. Сверточные коды были впервые введены Т.П.Элайсом в 1955году.

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

В 1957 году Дж.Возенкрафтом был разработан метод последовательного декодирования для этих кодов, который впоследствии был усовершенствован А.М.Фано Основным рабочим инструментом при разработке кодирующих и декодирующих устройств в то время для сверточных кодов было так называемое кодовое дерево.

В 1967 году Д.Форни вместо кодового дерева ввел эквивалентную, но более экономичную (с точки зрения объема вычислений) структуру, получившую название - решетчатая структура. И в том же 1967 году известный американский ученый А.Д. Витерби предложил новый метод декодирования сверточных кодов в виде простой итеративной процедуры, названный его именем – алгоритм декодирования Витерби.

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

На рис. 1 изображен простейший двоичный сверточный кодер, в состав которого входит регистр сдвига, состоящий из трех ячеек (1, 2 и 3), и два сумматора по модулю 2, соединенных с соответствующими ячейками регистра сдвига.

Рис. 1 Сверточный кодер.

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

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

Блочные коды , которые рассматривали раньше, характеризуются двумя целыми числами , где:

- количество информационных символов, поступающих на вход кодера в виде информационного блока;

- количество кодовых символов, поступающих с выхода кодера в виде кодового блока.

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

Сверточный код описывается тремя целыми числами: Смысл этих чисел (параметров) следующий:

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

-если то и отношение здесь также имеет смысл степени кодирования [1], как и для блочного кода. В других источниках, например, в [2] отношение обозначают, как и называют скоростью. На практике и - это небольшие целые числа.

На рис. 2 изображен кодер, для которого параметры и имеют значения: т.е. степень кодирования (или скорость) равна .

Рис. 2. Сверточный кодер.

На рис. 3 изображен кодер, для которого параметры и имеют значения: т.е. степень кодирования (или скорость) равна

Рис. 3. Сверточный кодер.

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

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

Существует несколько способов описания связей между разрядами в регистре сдвига и сумматорами по модулю 2:

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

Единица (1) на позиции вектора означает, что разряд с номером связан с сумматором, а нуль (0) означает, что связи между разрядом с номером и сумматором не существует. Так, для кодера на рис. 1 число сумматоров и будет вектор связи для верхнего сумматора и вектор связи для нижнего сумматора. С учетом сказанного эти векторы связи будут иметь вид

= 1 1 1

= 1 0 1 (1)

Для кодера на рис. 2 получим векторы связи:

= 1 0 0

= 0 1 1

= 1 1 1 (2)

2. Второй способ позволяет представить связи между разрядами регистра и сумматорами в виде набора из полиномиальных генераторов где - количество сумматоров.

Полиномиальные генераторы (или просто полиномы) имеют порядок или меньше. Они описывают связь между разрядами регистра сдвига и соответствующими сумматорами практически так, как и векторы связи . В зависимости от того, имеется ли связь между соответствующими разрядами регистра сдвига и сумматором, в каждом слагаемом полинома коэффициенты принимают только два значения 1 или 0. Для кодера рис. 1 полиномиальные генераторы будут иметь следующий вид

(3).

Сравнивая (1) с (3), заключаем, что составляющие векторов связи в (1) соответствуют коэффициентам полиномов в (3). С помощью полиномиальных генераторов легко определить кодовые символы на выходе кодера, когда на его вход поступает заданная последовательность информационных символов.

Пусть, например, на вход кодера поступает последовательность информационных символов:

Этой последовательности соответствует полином

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

(значения сумм в круглых скобках определяем по модулю 2).

Полином коэффициентами которого будут кодовые символы на выходе кодера, определим сложением

(здесь сложение не по модулю 2)

Последовательность кодовых символов определяется двойными коэффициентами в круглых скобках полинома т.е.

= 11 01 10 01 11 00 00……

Избыточность, которая вводится при сверточном кодировании, позволяет, как и в случае блочных кодов, исправлять определенное количество ошибок, которые появляются на выходе демодулятора из-за действия сигнала помехи. Подробно вопрос декодирования свёрточного кода будет рассмотрен ниже. Отметим, что в определенных случаях при сверточном декодировании возможно возникновение такого явления, как «катастрофическая ошибка». Эта ошибка возникает, когда конечное число ошибок на выходе демодулятора вызывает бесконечное число ошибок на выходе декодера.

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

Например, сверточному кодеру, изображенному на рис. 4 соответствуют следующие полиномиальные генераторы: =1+ ,

Рис. 4 Сверточный кодер

Эти генераторы и имеют общий полиномиальный множитель 1+ , т.к.

следовательно, в кодере на рис. 4 может происходить распространение катастрофической ошибки при декодировании.

Кодеру рис. 1 , как уже отмечалось, соответствуют полиномиальные генераторы

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

Рассмотрим работу кодера рис. 1 на двух примерах, при поступлении на его вход двух последовательностей информационных символов.

1. В этом примере на вход кодера подана последовательность информационных символов: 10000 . Реакция кодера на этот входной сигнал является важной характеристикой, которая называется импульсной характеристикойкодера (по аналогии с названием «импульсная характеристика линейной цепи», которая является реакцией цепи на импульс).

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

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

Таблица 1

№ тактового интервала k	Входные символы	Содержимое ячеек регистра	Символы на контактах коммутатора (на выходе)
				Верхний	Нижний
	Исходное состояние

коммутатора появится третья кодовая последовательность 11. После поступления на вход кодера четвертого информационного символа 0 в ячейках регистра будет записана последовательность 000 и на выход через коммутатор поступит четвертая кодовая последовательность 00. Рассмотренный пример характеризует таблица 1 и рис. 5.

Рис.5 а) Сигнал на входе кодера, изображенного на рис. 1;

б) Напряжение на выходе первой ячейки регистра;

в) Сигнал на выходе: импульсная характеристика свёрточного кодера.

На рис. 5 введены следующие обозначения:

величина тактового интервала для входного сигнала;

- величина тактового интервала для выходного сигнала.

На рис.5б стрелками показаны моменты переключения коммутатора.

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

На рис. 5а входной сигнал, соответствующий символу 1, имеет длительность , т.е. занимает интервалы и причем, на интервале этот сигнал имеет форму прямоугольного импульса с амплитудой 1, а на интервале этот сигнал равен нулю.

Форму сигнала, соответствующего символу 1, можно изменять, т.е. длительность прямоугольного импульса с амплитудой 1 может быть меньше длительности интервала ; только не допускается , чтобы длительность прямоугольного импульса превышала длительность интервала Например, нельзя, чтобы длительность прямоугольного импульса на входе была равна сумме длительностей интервалов и то есть равна величине . Причина этого ограничения заключается в том, что при его нарушении сигнал на выходе кодера нельзя представить в виде свертки импульсной характеристики кодера и входной последовательности. Для получения свертки, необходимо, чтобы длительность прямоугольных импульсов на входе кодера не превышала длительность прямоугольных импульсов на выходе кодера.

2. Рассмотрим работу кодера при поступлении на его вход произвольной последовательности информационных символов, например: 1110000…..

На этом примере поясним, почему рассматриваемый метод кодирования называется сверточным. Построив для заданной входной последовательности таблицу, аналогичную таблице 1, найдем, что соответствующая кодовая последовательность на выходе кодера будет иметь вид 11 01 10 01 11 00 00 00 (4).

Эту выходную последовательность (4) можно также определить и другим способом, а именно на основе следующей формулы

(5),

формула (5) является дискретным аналогом известной формулы

(6),

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

В отличие от (6) в (5) сигналы на выходе и входе кодера рассматриваются не при непрерывном изменении времени , как в (6), а на соответствующих тактовых интервалах, указанных на рис. 6, на которых эти сигналы принимают постоянные значения равные 0 (В) или 1 (В).

В (5) используются такие обозначения:

- номер тактового интервала длительностью (см. рис. 6); этот параметр

при суммировании принимает целые значения и является аналогом переменной интегрирования в (6);

Рис. 6 а) импульсная характеристика свёрточного кодера;

б) входной сигнал;

в) сигнал ;

г) сигнал .

- номер тактового интервала длительностью на выходе кодера, на котором определяется выходной сигнал ; этот параметр является аналогом времени наблюдения выходного сигнала в (6);

- значение импульсной характеристики кодера на интервале длительностью (рис.6);

график функции получается из графика функции путем сдвига этого графика на тактовых интервалов вправо, (если );

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

- символ суммирования в (5) является аналогом символа интегрирования в (6); при этом суммирование в (5) осуществляется по модулю 2.

На рис. 6, а изображена импульсная характеристика сверточного кодера;

На рис. 6, б изображен входной сигнал , соответствующий заданной последовательности информационных символов 1110000….;

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

Аналогично, график сигнала при любом значении получается из графика сигнала путем его сдвига вправо на - тактовых интервалов равных длительности . Учитывая свойства графиков функций и , изображенных на рис. 6, (т.е. то, что при и = 0 при ) в формуле (5) можно изменить пределы суммирования, т.е. бесконечные пределы заменить на конечные

(7)

По формуле (7) найдем значения сигнала на выходе сверточного кодера для значений : = 0,1,2,…,10,11.

При вычислении значений по (5) необходимо придерживаться такого порядка:

вначале определяем обычную сумму для (5), а затем - значение этой суммы по модулю 2.

Так, вычисляется согласно (5) при , т. е. необходимо определить

где функция изображена на рис. 6, а, а на рис. 6, в.

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

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

Теперь нужно определить значение этой суммы по модулю 2 1 (mod 2)=1. Итак, окончательное значение .

Значение вычисляется при аналогично, т. е.

Кривая по-прежнему изображена на рис. 6, а, а кривая на рис. 6, г. Из этих рисунков видно, что снова имеется только один интервал, (теперь это ), где обе кривые одновременно отличаются от нуля и поэтому снова окончательное значение .

При значении имеем только два тактовых интервала (это и ), на которых обе функции и не равны 0. Поэтому обычная сумма будет равна 2, но так как 2(mod 2)=0, то . Повторяя эту процедуру вычислений при найдем все остальные значения . Полученные результаты сведем в таблицу 2:

Таблица 2.

Входные информационные символы

-номер тактового интервала на выходе кодера

Кодовые символы

В таблице 2 представлены кодовые символы, когда на вход кодера поступает информационная последовательность 111000. Сравнивая кодовую последовательность, представленную этой таблицей с последовательностью (4) видим, что они идентичны. Но кодовая последовательность в таблице 2 получена на основе формулы (5), которая является дискретной сверткой импульсной характеристики кодера с входной последовательностью информационных символов. Отсюда и появилось название «сверточный кодер» для кодера, изображенного на рис. 1; а по названию кодера стали называть и сам метод кодирования- « cверточное кодирование».