Кодирование в телекоммуникационных системах.-2

181

Рис. 3.73. Решетчатая диаграмма декодера Витерби

Таким образом, если бы в ситуации, представленной на рисунке 3.64, мы принимали решение на основе последовательного алгоритма, то на первом и втором шаге декодирования мы приняли бы решение идти вниз по решетке, выбирая кратчайшие метрики Хемминга.

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

выбрали бы не самый короткий путь при декодировании. Поэтому, алгоритм Витерби является оптимальным. Однако он сложнее последовательного как в понимании, так и в реализации. В качестве метрики выступает расстояние Хемминга.

Программная реализация сверточного кодера

Подготовка данных к кодированию

Сначала, символы, введенные с клавиатуры ассоциируются со своими десятичными значениями в таблице ASCII. Затем, ASCII-код символа переводится в восьмеричную систему исчисления.

Ранее был объявлен массив «Bit_Array()», который имеет 8 ячеек, в которых содержится двоичное представление чисел от 0 до 7. Так как восьмеричная система имеет всего восемь цифр (0-7) то перебирается массив в цикле от 0 до 7, и находится равенство между индексом массива (счетчиком цикла) и восьмеричной цифрой ASCII-кода, после чего вместо нее подставляется двоичное представление из ячейки массива.

К примеру, цифра 0, будет иметь десятичный ASCII код - 48, в восьмеричный - 60.

Что в двоичной системе исчисления будет 110000. Если ASCII-код - двузначное число,

впереди дописывается 00, чтобы двоичные числа имели одинаковую длину. Формируется строка бит сообщения 00110000.

После того как символы исходного текста ассоциированы с кодами таблицы кодов

ASCII и переведены в двоичный вид, осуществляется свёрточное кодирование.

182

Функция свёрточного кодирования

Разрабатываемый свёрточный кодер является несистематическим, без обратной связи и изображен на рисунке 3.74. Функциональную схему кодера (см. Приложении Б).

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

.поступает в регистр сдвига (в нашем примере памяти = 3, то есть с двумя элементами

входящий в кодер информационный символ приходится два кодовых символа, кодовая скорость равна = 1/2. Если одна из кодовых последовательностей (1) или (2) совпадает с

информационной последовательностью , то, как отмечалось ранее, кодер называется систематическим. В противном случае кодер называется несистематическим [9].

Генераторы свёрточного кодера изображенного на рисунке 3.75. можно описать при помощи полиномов:

G1 = 1+X+X2 G2 = 1+X2

Таким образом, порождающая матрица этого сверточного кодера , в терминах оператора задержки имеет вид:

G(X) = (1+X+X2 1+X2).

Как уже отмечалось ранее, кодер – это автомат. В данном случае имеется классический алгоритм автомата Мили — конечный автомат, выходная последовательность которого (в отличие от автомата Мура) зависит от состояния автомата и входных сигналов.

Это означает, что в графе состояний каждому ребру соответствует некоторое значение

183

(выходной символ). В вершины графа автомата Мили записываются выходящие сигналы, а

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

изображена на рисунке 3.75.

Рис. 3.75. Диаграмма состояний сверточного кодера скорости = 1/2

Свёрточное кодирование кодером со скоростью R= 1/2 в программном комплексе выполняет функция Fun_BitCoder. После объявления массива и его целочисленных переменных обнуляются регистры сдвига, описывается цикл, осуществляющий побитное чтение информационных символов, их сдвиг в регистрах и суммирование по модулю два согласно установленным правилам. Элемент исходного кода программы, отвечающий за реализацию свёрточного кодирования, представлен на рисунке 3.76.

Рис. 3.76. Элемент программного кода функции свёрточного кодирования

В роли сумматоров выступают переменные Y1 и Y2, а в роли ячеек регистра переменные

R1 и R2. Коммутатором является переменная s_res. Для осуществления поочередной коммутации бит с выходов кодера символы переводятся в строковый тип.

Функция имитации канала связи

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

184

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

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

Если помеха ξ(t) складывается с сигналом s ( t ) и на вход приёмника действует их сумма x(t) = s ( t ) + ξ(t) такую помеху называют аддитивной. Если результирующий сигнал равен произведению помехи и передаваемого сигнала x(t) = s ( t ) ∙ ξ(t), то помеху называют

мультипликативной.

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

Выражается мультипликативная помеха в изменении характеристик линии связи

(сопротивление линии связи (ЛС), частота среза ЛС, нелинейность характеристик ЛС).

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

пакета ошибок.

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

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

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

В разрабатываемом программном комплексе имеется возможность пронаблюдать эффективность работы последовательного декодера свёрточных кодов как при наличии однократных ошибок, так и пачек длиною L > 1.

На рисунке 3.77 приведена блок-схема программно реализованного алгоритма имитации канала связи с белым шумом и канала с многолучевым распространением.

185

Рис. 3.77. Блок-схема для алгоритма имитации канала связи

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

max_mistake_dou = length_array * (CInt(probability_mistake) / 100),

где: max_mistake_dou – максимальное количество ошибок length_array – длина сообщения

probability_mistake – вероятность ошибки

Например, если длина сообщения равна 80 бит, а битовая вероятность ошибки – 0.1 то генератор сгенерирует от 0 до 8 ошибок.

Далее, активируется обычный генератор случайных чисел в диапазоне от 1 до 100:

Dim value As Integer = CInt(Int((100 * Rnd()) + 1))

Функция CInt приводит выражение в тип Integer и округляет его до ближайшего целого. После чего число сгенерированных ошибок сверяется с заданным числом ошибок,

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

186

Рис. 3.78. Элемент программного кода функции имитации канала связи Если были заданы двойные ошибки, инвертируются по два соседних бита.

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

Функция вычисления метрик путей

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

Расстояние Хэмминга — число позиций, в которых соответствующие символы двух слов одинаковой длины различны. Согласно выбранному алгоритму вычисления метрик путей, биты сообщения суммируются по модулю два со значениями возможных путей и полученному результату подставляется его десятичное значение, соответствующее величине расстояния Хемминга между слагаемыми. За это отвечает функция «Fun_Metric»,

программная реализация которой приведена на рисунке 3.70, где: s_1 – биты сообщения;

s_2 – возможные значения путей решетки;

res – результат суммирования по модулю два бит сообщения со значениями возможных путей решетки;

res_1 - десятичное значение, соответствующее величине расстояния Хемминга между слагаемыми.

187

Рис. 3.79. Программный код функции вычисления метрик путей Из таблицы 3.4 видно, что значение 00 может стать результатом суммирования

только двух слов, биты которых не отличаются ни в одной из позиций, а это значит, что расстояние Хемминга между такими словами рано 0. Значения res = 01 и res = 10 возможны лишь в том случае, если по модулю 2 суммировались слова, соответствующие биты которых отличаются друг от друга в одной позиции, то есть расстояние Хемминга между ними равно 1. Что же касается значения res = 11, то оно может получиться только в результате сложения двух слов, биты которых в обеих позициях отличаются, и расстояние Хемминга между этими словами равно 2.

Таблица 3.4. Вычисление метрик путей

188

Функция декодирования последовательным алгоритмом

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

S_str_Array()).

Как мы уже знаем из теории, на первом шаге декодирования состояние декодера –

00, возможны только два пути, к узлам 00 и 10, которымсоответствуют кодовые символы с выхода кодера 00 и 11.

Однако на вход декодера могут придти целых четыре комбинации бит сообщения,

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

00 и 01 к переходу в узел 00, а кодовые комбинации 10 и 11 к переходу в узел 10. Так мы избавляемся от неопределённостей, заставляя декодер принять решение, даже если пришла не разрешенная комбинация.

Рис. 3.80. Элемент программного кода функции декодирования последовательным алгоритмом

189

После того как путь выбран, в переменную state_metric записывается значение метрики пути, вычисленное описанной функцией Fun_Metric. Далее ставится метка 0 или 1,

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

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

Далее происходит аналогичные операции, только количество возможных путей увеличивается до 4-х (00, 01, 10, 11), осуществляется переход ко второму шагу декодирования. Граф автомата, каковым является наш декодер, принимает вид показанный на рисунке 3.82

Рис. 3.81. Граф реализуемого последовательного декодера Стратегия представленная на рисунке 3.82 реализуется при помощи алгоритма

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

Если мы находимся в узле 00 или 11, и пришла комбинация 00 или 01 –

считаем что передавался ноль (двигаемся вверх), 10 или 11 – передавалась единица

(двигаемся вниз).

Если мы находимся в узле 01 или 10, и пришла комбинация 00 или 01 –считаем что передавалась единица (двигаемся вниз)., 10 или 11 – передавался ноль (двигаемся вверх).

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

Подготовка к выводу результатов декодирования

Для того чтобы в конечном итоге получить символьный результат организуем цикл реверсирования массива символов сообщения, иначе мы получим строку в зеркальном

190

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

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

Сверточное декодирование. Практическая часть

ЗАДАНИЕ №1

Вариант 1

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

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

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

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

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

3.5.

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