Ташатов Н.Н.

Евразийский национальный университет им. Л.Н. Гумилева, г. Астана

декодирование с обратной связью

сверточных кодов

Сверточный код описывается тремя целыми числами n, k и K. Отношение называется степенью кодирования кода (информация, приходящаяся, на закодированный бит) и является мерой добавленной избыточности. Целое число K является параметром, который называется длиной кодового ограничения.

Обычный сверточный кодер, показанный на рисунке 1, реализуется с kK – разрядным регистром сдвига и п сумматорами по модулю 2, где K – длина кодового ограничения [1].

Рисунок 1 – Сверточный кодер с длиной кодового ограничения K и

степенью кодирования k / п

Длина кодового ограничения – это количество k-битовых сдвигов, после которых один информационный бит может повлиять на выходной сигнал кодера. В каждый момент времени на место первых k разрядов регистра перемещаются k новых бит. Все биты в регистре смещаются на k разрядов вправо, и выходные данные п сумматоров последовательно дискретизируются, давая, в результате, биты кода. Затем эти символы кода используются модулятором для формирования сигналов, которые будут переданы по каналу. Так как для каждой входной группы из k бит сообщения имеется п бит кода, степень кодирования равна, бит сообщения на бит кода, где k < п.

Будем рассматривать часто используемые двоичные сверточные кодеры, для которых k = 1, т.е. те кодирующие устройства, в которых биты сообщения сдвигаются по одному биту за один раз [2, 3]. Для такого кодера за i - й момент времени бит сообщения m_i, будет перемещен на место первого разряда регистра сдвига. Тогда все предыдущие биты в регистре будут смещены на один разряд вправо, а выходной сигнал n сумматоров будет последовательно оцифрован и передан. Так как для каждого бита сообщения имеется n бит кода, то степень кодирования будет равна . В момент времени t_i, имеющиеся n кодовых символов составляют i - e кодовое слово ветви, , где – j - й кодовый символ, принадлежащий i - му кодовому слову ветви. kK – разрядный регистр сдвига будем называть K - разрядным регистром, а длину кодового ограничения K – длиной кодового ограничения в битах.

Декодер с обратной связью реализует жесткую схему принятия решений относительно информационного бита в разряде j, исходя при этом из метрик, полученных из разрядов j, j + 1, ... , j + m, где m – заранее установленное положительное целое число. Через L обозначим длину упреждения, которая определяется как L = m + 1. L – это количество принятых кодовых символов, выраженных через соответствующее число входных битов, задействованных для декодирования информационного бита. Решение о том, является ли информационный бит 0 или 1, принимается в зависимости от того, на какой ветви путь минимального расстояния Хэмминга переходит в окне упреждения из разряда j в разряд j + m. Поясним это на конкретном примере.

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

Рисунок 2 – Сверточный кодер степенью кодирования 1/2 и

длиной кодового ограничения K = 3

На рисунке 3 приведена древовидная диаграмма и работа декодера с обратной связью при L = 3. Другими словами, при декодировании бита из ветви j декодер содержит пути из ветвей j, j + 1 и j + 2.

Начиная из первой ветви, декодер вычисляет 2^L (восемь) совокупных метрик путей расстояния Хэмминга и решает, что бит для первой ветви является нулевым, если путь минимального расстояния содержится в верхней части дерева, и единичным, если путь минимального расстояния находится в нижней части дерева. Пусть принята последовательность Z = 1 1 0 0 0 1 0 0 0 1. Рассмотрим восемь путей от момента t₁, до момента t₃ в блоке A, (рисунок 3), и рассчитаем метрики, сравнивая эти восемь путей для первых шести принятых кодовых символов (три ветви вглубь умножить на два символа для ветви). Начиная с верхнего пути и выписав метрики Хэмминга общих путей, видно, что они имеют следующие значения:

метрики верхней части 3, 3, 6, 4

метрики нижней части 2, 2, 1, 3

Рисунок 3 – Пример декодирования с обратной связью

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

Наименьшая метрика содержится в нижней части дерева. Следовательно, первый декодированный бит является единицей и определяется сдвигом вниз на дереве. Следующий шаг будет состоять в расширении нижней части дерева (выживающий путь) на один разряд глубже, и здесь снова вычисляется восемь метрик, теперь уже для моментов t₂ – t₄. Получив, таким образом, два декодированных символа, теперь можно сдвинуться на два символа вправо и снова начать расчет метрик путей, но уже для шести кодовых символов. Эта процедура видна в блоке В. И снова, проследив метрики верхних и нижних путей, находим следующее:

метрики верхней части 2, 4, 3, 3

метрики нижней части 3, 1, 4, 4

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

Процедура продолжается до тех пор, пока не будет декодировано все сообщение целиком. Декодер называется декодером с обратной связью, т.к. найденное решение обратно подается в декодер, чтобы потом использовать его в определении подмножества кодовых путей, которые будут рассматриваться следующими. В двоичном симметричном канале BSC декодер с обратной связью может оказаться почти таким же эффективным, как и декодер, работающий по алгоритму Витерби. Кроме того, он может исправлять все наиболее вероятные модели ошибки, которые имеют весовой коэффициент менее или равный , где d_f – просвет кода. Важным параметром разработки сверточного декодера с обратной связью является длина упреждения L. Увеличение L приводит к повышению эффективности кодирования, но при этом растет сложность конструкции декодера.

СПИСОК ЛИТЕРАТУРЫ

1. Скляр Б. Цифровая связь. Теоретические основы и практическое применение. Изд. 2-е, испр. : Пер. с англ. – Издательский дом «Вильямс», 2004. – 1104 с. ил.

2. Галлагер Р. Теория информации и надежная связь. М., Советское радио, 1974, 720 с.

3. Fano R. M. Heuristic Discussion of Decoding. IRE Trans. Inf. Theory, vol. IT9. n. 2,1963, pp. 64 – 74.