Декодирование свёрточного кода по алгоритму Витерби, улучшенный алгоритм

Мы уже рассматривали декодирование свёрточного кода по алгоритму Витерби в предыдущей серии статей на эту тему. В новой статье автор предлагает улучшенный (упрощённый и ускоренный) алгоритм.

По прошествии 6 лет прочтение первой части этой статьи повергло её автора в уныние. Вроде написано много, а обещанного объяснения алгоритма декодирования свёрточного кода «на пальцах», так, чтобы «дураку понятно было», не наблюдается. Что же, немедленно исправляемся.- mil1553

1 Вперёд к началу от конца! Основная идея декодирования

Итак, мы уже знаем про решётку, ветви, пути и их метрики. Забудем на время про связи между узлами и посмотрим на узлы решётки без связей между ними, так сказать по мере движения декодирования.

Видно, что в каждом шаге количество узлов одно и то же, расположены они в одном и том же порядке. И картина эта повторяется во времени бесконечно… или точнее – до тех пор, пока из канала принимаются кодовые символы.

Напрашивается мысль: если всё так одинаково, может быть, можно описать какую-то последовательность действий, которая будет одинакова для всех узлов?

Мысль эта совершенно правильная. На самом деле, именно это и делается при декодировании. Мы уже знаем, что в каждый узел текущего шага из ДВУХ узлов предыдущего шага ведут по ОДНОЙ ветви из каждого узла. Из этих двух ветвей нам нужно выбрать одну. Причём, узлы, из которых ведут ветви, для каждой пары «текущий шаг – предыдущий шаг» одинаковы. Отсюда последовательность действий для каждого шага и каждого узла в шаге всегда будет одна и та же:

1. Определить два узла из предыдущего шага, из которых идут ветви в текущий узел.
2. Определить метрики этих ветвей.
3. Сложить метрики путей, которые кончились в двух определённых ранее узлах с метриками ветвей, идущих из этих узлов в текущий узел.
4. Выбрать из двух получившихся метрик путей путь с меньшей метрикой.
5. Записать эту метрику для текущего узла, запомнить, какая из двух ветвей выжила.

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

2 Оглядываясь назад Определение предыдущих узлов

Итак, начнём с первого пункта: как же определить два узла, из которых идут ветви в текущий? В первой части статьи предлагалось записывать связи узлов в ПЗУ. Можно ли сделать это как-то иначе? Можно. Для этого вспомним, как связаны между собой узлы, регистр кодера и отклик кодера.

Для определённости возьмём узел 101. Три бита узла – это три ЛЕВЫХ бита регистра кодера ДО осуществления перехода в следующий узел… или, что то же самое, три правых бита ПОСЛЕ перехода из предыдущего узла. Отсюда понятно, почему из узла ведут две ветви – переход в следующий узел осуществляется кодированием ИЛИ 1, ИЛИ 0.

На рисунке ниже показан узел 101 и соответствующее ему состояние регистра кодера. Крайний правый бит в кодере обозначен буквой A – его значение не важно, потому что при переходе он будет потерян.

При кодировании «1» номер узла 101 смещается на один разряд в регистре ВПРАВО, «выталкивая» бит A. В крайний левый разряд записывается «1». С выходов сумматоров ПОСЛЕ сдвига считываются два бита кодовой комбинации. Теперь крайние левые три бита сдвигового регистра содержат номер узла, В КОТРОРЫЙ произошёл переход – в данном случае это узел 110.

То же самое происходит при кодировании «0», в этом случае переход произойдёт в узел 010.

Видно, что от номера предыдущего узла текущий узел «наследует» два бита начиная СЛЕВА. То есть два крайних ЛЕВЫХ бита предыдущего узла становятся двумя крайними ПРАВЫМИ битами текущего узла.

Отсюда мы можем сказать, что в узел 101 мы можем попасть из двух каких-то других узлов, у которых два ЛЕВЫХ бита равны «01» – это крайние правые биты текущего узла 101.

Остаётся определить значение крайнего ПРАВОГО бита для двух узлов. Вариантов всего два – это «0» или «1». Отсюда сразу получаются номера узлов:

Таким образом, для узла разрядности N (состоящего из N бит) процедура восстановления состоит из двух шагов:

• N-1 бит текущего узла, начиная СПРАВА – это N-1 бит двух предыдущих узлов начиная СЛЕВА.
• Крайний правый бит двух предыдущих узлов принимает значение 0 для чётного узла и 1 для нечётного узла.

Для примера восстановим два предыдущих узла для узла 101. Номер узла трёхразрядный, поэтому N=3.

Шаг	Операция	Иллюстрация
1	N-1 бит текущего узла, начиная СПРАВА – это N-1 бит двух предыдущих узлов начиная СЛЕВА.
2	Крайний правый бит двух предыдущих узлов принимает значение 0 для первого узла и 1 для второго узла.

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

Вернёмся к узлу 101. Мы уже установили, что два предыдущих узла – это узлы 010 и 011. Заполним сдвиговый регистр кодера для каждого из пары найденных узлов, отобразив состояние ДО перехода в текущий узел 101.

Чтобы осуществить переход нам нужно сдвинуть значения в кодовом регистре ВПРАВО, записать в крайний левый разряд кодируемый бит («1» или «0») и посчитать значения на сумматорах:

Какое же значение – «0» или «1» – нужно записать? Ответ на этот вопрос содержится в значении текущего узла – 101. ЛЕВЫЙ разряд текущего узла – это и есть то значение, которое мы должны записать в крайний левый разряд кодового регистра!

Таким образом, зная текущий узел, мы однозначно восстановили:

• 1. Два предыдущих узла, из которых осуществляется переход в текущий.
• 2. Информационный бит, кодирование которого осуществляется при переходе.
• 3. Отклик кодера при переходе.

Посмотрим на построенную в первой части статьи решётку и проверим себя:

И действительно, в узел 101 можно попасть из узла 010 с откликом кодера 10 и из узла 011 с откликом кодера 01.

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

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

3 Из прошлого в будущее Описание процедуры декодирования

Теперь у нас есть всё для описания формальной процедуры декодирования. Рассмотрим очередной шаг декодирования N. Пусть из канала получена комбинация «10». Для каждого из узлов предыдущего шага известны метрика пути, закончившегося в этом узле, и код узла (0/1, чётный/нечётный), из которого осуществлён последний переход:

Для узла 000 определим два узла из предыдущего шага, из которых можно попасть в узел 000 и отклик кодера при таком переходе.

Таким образом, на шаге N в узел 000 ведут два пути из узлов 000 и 001 с метриками 6 и 9. Путь с метрикой 9 отбрасывается, остаётся только путь из ЧЁТНОГО узла 000 с метрикой 6. Остаётся запомнить эти значения, и все операции с узлом 000 на шаге N закончены:

Точно такие же операции выполняются для всех остальных узлов.

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

• 1. Метрика пути, закончившегося в узле.
• 2. Предыдущий узел для узла: чётный или нечётный.
• 3. Минимальная метрика пути на данном шаге.

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

4 Необходимые ресурсы и быстродействие данного алгоритма декодирования

Необходимые для реализации декодера ресурсы легко оценить. Декодер должен хранить пути, образующиеся в процессе работы. Для сохранения пути достаточно для каждого шага и каждого узла в шаге хранить предыдущий узел в формате «чётный/нечётный». То есть для хранения путей достаточно ОЗУ размером L×N, где L – количество шагов, N – количество узлов.

Для кода из примера ОЗУ будет размером L×8, потому что в каждом шаге – 8 узлов. Номер шага используется в качестве адреса ОЗУ, содержимое ОЗУ по адресу – 8 бит, где номер бита (от 0 до 7) соответствует узлу (от 0 до 7), а значение бита – из чётного («0») или нечётного («1») узла был осуществлён переход.

Кроме того, потребуется ОЗУ, состоящее из двух страниц, каждая страница содержит столько элементов, сколько узлов в шаге. Разрядность элемента должна быть достаточна, чтобы вместить значение L×(максимальная метрика ветви). Фактически первая страница хранит метрики путей, закончившихся в узлах в чётном шаге, вторая страница – в нечётном. При каждом новом шаге значения одной из страниц перезаписываются.

Для кода из примера максимальная метрика ветви равна 2 (полное несовпадение двухбитных кодовых комбинаций), для 1000 шагов максимальное значение метрики пути составит 2×1000 = 2000, что составляет 11 двоичных разрядов. То есть ОЗУ хранения метрик путей будет 2×8 элементов по 11 бит. Адрес ОЗУ состоит из двух частей – младшего бита номера шага и узла, младший бит номера шага выступает номером страницы (чётный-нечётный). По адресу размещается значение метрики пути, окончившегося в узле.

За подобную простоту следует расплата. Поскольку все узлы перебираются последовательно, то скорость обработки падает пропорционально количеству узлов в шаге. Для кода из примера если символы поступают из канала с частотой F, то декодер должен перебирать узлы с частотой минимум в 8 раз большей, чтобы успевать сделать один шаг по решётке к моменту поступления очередного символа. Поскольку процедура обработки узла занимает более одного такта, внутренняя частота декодера должна быть выше частоты поступления символов в N×K раз, где N – количество узлов в шаге, K – количество тактов на обработку одного узла.

Для кода из примера, если один узел обрабатывается за 5 тактов и ещё 4 такта уходит на процедуры начала/завершения шага, то на один шаг потребуется 8 × 5 + 4 = 44 такта. Отсюда, если частота поступления входных символов составляет 1 МГц, то для работы в темпе канала декодеру нужно иметь внутреннюю частоту 44 МГц. При тех же условиях для свёрточного кода, который обрабатывает 64 узла в шаге, потребуется внутренняя частота 324 МГц.

5 В два раза быстрее! Увеличение производительности алгоритма

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

В предлагаемой реализации распараллелить обработку «в лоб» не получится. В один момент времени из ОЗУ данные могут запрашиваться или записываться только по одному адресу. При последовательном переборе это условие выполняется – для каждого узла последовательно формируются значения узлов на предыдущем шаге и из ОЗУ вычитывает метрика путей, закончившихся в этих узлах. При параллельной обработке несколько блоков будут запрашивать значения метрик РАЗНЫХ узлов в один и тот же момент времени. Однако это ограничение можно легко обойти, улучшив производительность в два раза.

Для кода из примера выпишем узлы в порядке возрастания, при этом сгруппируем их так, чтобы они отличались только крайним ЛЕВЫМ битом и далее выпишем соответствующие предыдущие узлы:

Видно, что в этом случае узлы разбиваются на пары. В каждой паре текущий узел отличается только одним крайним ЛЕВЫМ битом, а предыдущие узлы одинаковы. Это позволяет разбить узлы на два блока, в которых все операции выполняются параллельно:

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

Запись данных придётся осуществлять за несколько тактов – пока обрабатывается очередная пара узлов, в ОЗУ записываются две метрики, полученные при обработке предыдущей пары. В этом случае частоту работы декодера можно понизить вдвое.

Можно ли ещё увеличить скорость обработки? Можно, но в этом случае опять происходит возврат к «бабочкам». При аппаратной реализации каждую «бабочку» придётся снабдить генератором решётки и собственной двустраничной памятью метрик путей, закончившихся в узлах. Память переходов может быть общей, поскольку запись в неё происходит один раз в конце шага, когда все выжившие ветви уже известны. При аппаратной реализации это даст существенный выигрыш в производительности.

6 «Сейчас с людьми надо помягше» Мягкие решения

До этого момента рассматривались декодеры с так называемыми жёсткими решениями. В случае жёстких решений декодер работает в «однобитном» пространстве, каждый кодовый символ принимает одно из двух значений: «0» или «1».

Для свёрточного кода со скоростью 1/2 возможны всего 4 комбинации. Их можно отобразить в координатной плоскости. По оси X откладывается значение первого кодового символа, по оси Y – второго. Расстояние между принятой кодовой комбинаций и комбинацией при переходе по решётке рассчитывается как количество различий в символах (хэмингово расстояние).

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

При жёстких решениях некоторая схема, стоящая ДО декодера, принимает однозначное решение какой символ принят из канала. При этом про качество этого символа декодер ничего не знает.

Пусть в некоторой линии передачи данных значение символа кодируется амплитудой: +3 В соответствует передаче «1», −3 В соответствует передаче «0».

В этом случае жёсткие решения – это принятие во внимание только знака напряжения. Если напряжение больше 0, то принята «1», в противном случае – «0».

В реальности символы могут быть искажены влиянием помех. Если уровень помех незначителен, то не так уж важно, измерено значение +3 В или +2 В – это однозначно положительное напряжение, а значит принята «1». Однако при большем уровне помех различать «0» и «1» на приёме становится труднее. Измеренное значение +1 В может оказаться как искажённым значением +3 В, из которого помеха «вычла» 2 В, так и значением –3 В, к которому помеха «прибавила» 4 В. При этом, из-за жёсткой оценки значение «+3 В» и «+1 В» с точки зрения декодера равнозначны.

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

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

Если рассматривать полученное значение как число, то оценка будет принимать 8 значений от 0 до 7, где 0 соответствует уверенному приёму «0», «7» – уверенному приёму «1». Худшими значениями будут значения 3 и 4: в этом случае оценка близка к нулю, и приём «1» и «0» равновероятен.

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

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

Пусть при переходе из узла значение кодовых бит для очередной ветви, согласно генератору решётки, должно быть «10». Это значение гарантировано достоверно и потому заменяется оценкой «111_000». На координатной плоскости это правая нижняя точка. При этом из канала принята комбинация «100_101» (обозначена на рисунке квадратом). Чтобы рассчитать метрику ветви, нужно определить расстояние между принятой комбинацией на плоскости и комбинацией от генератора решётки. Это расстояние рассчитывается по формуле Евклида как квадратный корень из суммы квадратов разностей координат. Поскольку в декодере выбирается путь с наименьшей метрикой, вычисление квадрата можно опустить.

Для изображённой на рисунке ситуации:

• координаты точки от генератора решётки: (7,0);
• координаты принятой из канала точки: (4,5).

Квадрат расстояния между точками: S² = (7 – 4)² + (0 – 5)² = (3)² + (–5)² = 9 + 25 = 34

Таким образом, метрика ветви для этого случая составит 34.

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

Трёх бит для оценки значения достаточно, увеличения разрядности не имеет практического смысла. Если трёхбитные оценки дают выигрыш относительно однобитных жёстких решений в ~1,6 раз, то бесконечная разрядная сетка даст выигрыш не более чем в 1,67 раз.

7 Почувствуй себя Вангой! Определение передаваемой информации

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

Пусть уже известным кодом кодируется сообщение 10101011. Длина регистра свёрточного кодера – 4 разряда. Дополним сообщение четырьмя нулями; в этом случае последний бит сообщения, которое мы хотим закодировать, поучаствует в формировании двухбитных комбинаций свёрточного кода: 101010110000.

Путь в решётке начинается от узла 000 и заканчивается в нём же. По-иному быть не может: перед началом кодирования регистр кодера обнуляется, а сообщение дополняется нулевыми битами, за 4 сдвига приводящими регистр кодера также в состояние 0000. Таким образом, мы уже знаем, из какого узла начнётся декодирование и в каком закончится, а также можем проредить решётку, «выбросив» из неё узлы, в которые невозможен переход!

Для первого шага декодирования из восьми узлов нужно рассмотреть только два – узлы 000 и 100. Один из этих узлов определяет первый закодированный бит сообщения: 0 или 1.

Для второго шага опять нет необходимости рассматривать все узлы, ведь мы точно знаем, что перед кодированием второго бита сообщения регистр кодера был 0000 ИЛИ 1000 и никакой другой, соответственно, после кодирования второго бита возможно только четыре состояния регистра кодера и никакие другие: 0000, 1000, 1000, 1100.

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

Решётка для декодирования нашего сообщения будет выглядеть следующим образом:

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

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

8 Небольшая инсинуация Улучшаем качество приёма

Отсечение недопустимых путей в первых шагах декодирования ничего не стоило, для этого нужно лишь соблюдать «договорённость» между приёмником и передатчиком, что каждое сообщение начинается с нулевого состояния кодера. За отсечение невозможных путей в конце сообщения, кроме «договорённости», пришлось заплатить расширением сообщения 4-мя дополнительными битами.

Предположим, что после каждых 4-х бит сообщения мы будем вставлять в него 4 искусственных "0". В этом случае получится периодическое усечение решётки до одного узла, что сильно уменьшит количество путей для выбора, а значит повысит вероятность правильного декодирования, но увеличит объём передаваемых данных в два раза. Попробуем поискать компромисс. Длина сдвигового регистра – 4 бита. Это значит, что если после каждых 4-х бит передаваемого сообщения вводить в кодер бит, равный 0, то на протяжении 4-х шагов можно исключить в решётке декодера половину узлов или ветвей. При этом объём сообщения вырастет на четверть.

Пусть уже известным кодом кодируется сообщение 101010110110. Разобьём сообщение на тетрады, вставим между тетрадами искусственные 0 и дополним сообщение четырьмя нулями: 1010_0_1011_0_0110_0_0000. Тогда решётка для кодирования и декодирования сообщения примет следующий вид:

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

Почему сообщение увеличилось на четверть? Потому что на каждые 4 бита исходного сообщения добавлялся один дополнительный бит. Четыре бита следует из длины регистра кодера. Что будет, если увеличить длину регистра кодера, например, до 20? В этом случае дополнительный бит можно добавлять не чаще каждых 20 бит сообщения, то есть всё сообщение увеличится на 1/20, что не так много. С ростом длины регистра кодера растёт и корректирующая способность кода. Но растёт и сложность декодера. 20 разрядов регистра кодера дадут 2¹⁹ узлов, что составляет 524288 узлов. Это очень большое число, такое количество узлов требует 65 кБ памяти для одного шага на сохранение памяти путей и значительной тактовой частоты и ресурсов для вычислений в самих узлах.

Впрочем, при уменьшении разрядности регистра кодера до 10-12 бит ситуация значительно улучшается. Кроме того, не обязательно вводить дополнительные биты так часто. Поэтому при некоторых условиях подобный способ может использоваться.

Материал прислал наш читатель под псевдонимом MIL1553.