Кодирование и шифрование информации в радиоэлектронных системах передачи информации. Часть 1. Кодирование

Построили решетку кодера:

Рис. 3.83. Решетка кодера Изобразили решетку декодера и произвели декодирование:

Рис. 3.84. Решетка декодера

191

В результате были выявлены 6 ошибок: После декодера был получен результат:

11 10 11 01 10 01. Подчеркиванием выделены места, где были совершены ошибки.

Вариант 2

Сверточный код: g1(X) =X+ X2 + X3, g2(X) = 1 + X + X2.

Входная последовательность: V = 010100.

На рисунке 3.85 представлен сверточный кодер.

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

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

3.6.

Таблица 3.6. Процесс кодирования информационного потока

Рис. 3.86. Решетка кодера Изобразили решетку декодера и произвели декодирование:

Рис. 3.87. Решетка декодера В результате были выявлены 5 ошибок: После декодера был получен результат:

00 00 10 11 01 00. Подчеркиванием выделены места, где были совершены ошибки.

ЗАДАНИЕ №2

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

193

194

Рис. 3.90. График зависимости числа ошибок от вероятности ошибок для двойной длины ошибок

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

требованиям.

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

алгоритма декодирования.

3.4. Декодирование сверточных кодов по методу Витерби

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

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

195

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

Краткие теоретические сведения

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

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

Кодирующее устройство сверточного кода в общем виде представлено.

При поступлении на вход кодера каждого информационного символа Ui мультиплексор

Вх

Ui

M

М последовательно считывает за один такт сигналы с выходов всех сумматоров по модулю 2,

формируя на выходе m символов Vi. Таким образом, при скорости входной последовательности Ввх бит/с скорость выходной последовательности составляет Ввых=mВвх

бит/с.

196

Известны два основных вероятностных алгоритма декодирования сверточных кодов, а

также их различные модификации.

В простейшем случае производят квантование каждого канального символа в отсчетный момент времени на два уровня (именуемое, как «жесткое решение» на выходе демодулятора). При жестком решении число уровней квантования L = 2. При этом жесткое решение представлено одним двоичным символом. Это показано на рисунке 2, б).При

«мягком решении» рисунок 2, г) число уровней квантования L > 2.

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

Отсчет

S2

а)

б)

Отсчет

а, в) – формы противоположных сигналов в момент отсчета на входе решающего

устройства демодулятора. б) – шкала квантования и граф переходов при жестком решении.

г) – шкала квантования и граф переходов при мягком решении.

Алгоритм Витерби для декодирования сверточных кодов

Рассмотрим алгоритм Витерби на примере кода со скоростью Rкод = 1/n.

Пусть, начиная с момента времени t = 0, на вход кодера подается информационная последовательность длиной L символов:

197

aL = (a0, a1, …, aL–1)

Тогда на выходе кодера будет последовательность символов: bL = (b0, b1, ..., bL–1)

Состояние кодера в момент t определяют как набор из w информационных символов: wt = (at, at–1, ..., at–L+1)

Решетчатая диаграмма кода однозначно связывает информационную последовательность aL, последовательность состояний кодера wL и последовательность символов на его выходе bL.

Каждой ветви bt в канале соответствует сигнал, который может быть представлен набором координат [2]:

St = (St(1) , St2 , ..., St( N ) )

где N – размерность пространства сигналов.

Допустим, что в канале действует аддитивная помеха. Тогда поступающая на вход декодера последовательность принимаемого сигнала будет равна:

XL = SL + nL

где SL = (S0, S1, ..., SL–1); nL = (n0, n1, …, nL–1);

nt = (nt(1) , nt(2 ) , ...,nt( N ) ) – N-мерный вектор помехи.

Декодирование состоит в прослеживании по кодовой решетке пути с максимальной апостериорной вероятностью.

Декодированный путь можно указать одним из способов:

–набором оценок кодовых ветвей SL = (S0, S1, ..., SL–1), составляющих путь;

–последовательностью оценок состояний кодера WL = (w0, w1, …., wL–1);

– последовательностью оценок информационных символов на входе кодера

AL = (a0, a1, …, aL–1), которые совпадают с первыми символами оценок состояний S = (s0, s1,

…,st-ν+1).

Последовательность XL будет декодирована с минимальной вероятностью ошибки,

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

обеспечивающая выполнение условия P(SL/XL) = max. В канале без памяти условная вероятность P(SL/XL) пропорциональна произведению условных плотностей суммы сигнала и помехи:

198

При декодировании выбирают последовательность сигналов SL = (S0, S1,…, SL–1) и

однозначно связанную с ней последовательность ветвей SL = (S0, S1, …, SL–1), которая обеспечивает минимум суммы:

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

i-1

Вгауссовском канале метрика ветви пропорциональна квадрату Евклидова расстояния между вектором принимаемой суммы сигнала и помехи Xt и вектором сигнала St,

соответствующего ветви кода At. В дискретном канале для оценки расстояний используют метрику Хемминга.

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

Рассмотрим декодирование кода (7;5), символы которого передаются по дискретному

199