Рейтинг@Mail.ru

Кодирование и декодирование свёрточного кода по алгоритму Витерби

Print Friendly, PDF & Email
По свёрточным кодам написано достаточно литературы, как по кодерам, так и по декодерам. Тем не менее, понятного и простого описания аппаратной реализации декодера, реализующего алгоритм Витерби, мне найти не удалось ни в русскоязычном, ни в англоязычном интернете. Если чего-то нет – иногда проще восполнить пробел и сделать самому. Этот материал написан именно из таких соображений, максимально простым языком, с избыточными подробностями. Надеюсь, что он в достаточной мере раскрывает тему построения кодера и декодера свёрточного кода.

1 Кодер свёрточного кода

Кодер свёрточного кода представляет собой сдвиговый регистр, выводы которого подключены к сумматорам. Количество сумматоров определяет количество бит кода, соответствующих одному биту данных. Два сумматора – два бита кода на один бит данных, три сумматора – три бита кода на один бит данных и т.д. Соотношение «бит данных/количество бит кода» называется скоростью кодирования, обычно обозначается R. Для двух бит кода на один бит данных R=1/2, для трёх бит кода на один бит данных R=1/3 и т.д.

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

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

На рисунке ниже показаны кодеры свёрточного кода с порождающими многочленами (15,17) и (5,7).

Кодер (15, 17) Витерби
Кодер (15, 17) Витерби
Кодер (5, 7) Витерби
Кодер (5, 7) Витерби

Число 158 в восьмеричном представлении записывается как 1310 в десятичном и 11012 в двоичном. Поэтому 1, 2 и 4-я ячейки сдвигового регистра подключены к сумматору 158. Число 178 в восьмеричном представлении – 11112 в двоичном (все ячейки регистра подключены к 2-му сумматору).

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

Таким образом, для порождающих многочленов (15,17) длина регистра сдвига составит 4 элемента.

Для чисел 58 и 78 в восьмеричной системе соответствующее десятичное представление будет 510 и 710, двоичное – 1012 и 1112. Длина регистра сдвига – 3 элемента.

В отечественной и зарубежной обучающей литературе повсеместно используется кодер с порождающими многочленами (5,7). Мне этот пример, несмотря на его простоту, не нравится, т.к. скрывает многие подводные камни. Первый из них виден сразу: восьмеричное и десятичное представление чисел порождающих многочленов (5,7) совпадает. Второй – симметрия двоичного представления порождающих многочленов, не ясно, в каком порядке подключать выводы сдвигового регистра к сумматору. И третий – и кодовая комбинация, и состояния кодера описываются одинаковыми двухбитовыми комбинациями, что вносит путаницу. Поэтому дальше я буду описывать кодер и декодер с порождающими многочленами (15,17); описание несколько объёмнее, но более понятное.

Работа кодера Витерби

В исходном состоянии в ячейках сдвигового регистра содержатся нули. Далее на вход, в первую слева ячейку, поступает первый информационный символ. Одновременно с записью символа в первую ячейку её содержимое переписывается во вторую, второй – в третью и т.п. На сумматорах образуется сумма по модулю два содержимого ячеек кодера. Ключ К1 переводится в положения 1 и на выход кодера поступает сумма верхнего сумматора. Далее ключ переводится в положение 2, и на выход кодера поступает сумма нижнего сумматора. В таблице ниже показан процесс кодирования комбинации 11012. Комбинация вводится в кодер, начиная с крайнего левого символа.

Исходное состояние кодера Витерби: 0000
Исходное состояние кодера Витерби: 0000
Первый символ 1101
Кодер витерби Кодер витерби Кодер витерби Кодер витерби
«1» введена в кодер Выход: 1 xor 0 xor 0 = 1 Выход: 1 xor 0 xor 0 xor 0 = 1 Выход отключён от регистра
Второй символ 1101
Кодер витерби Кодер витерби Кодер витерби Кодер витерби
«1» введена в кодер Выход: 1 xor 1 xor 0 = 0 Выход: 1 xor 1 xor 0 xor 0 = 0 Выход отключён от регистра
Третий символ 1101
Кодер витерби Кодер витерби Кодер витерби Кодер витерби
«0» введён в кодер Выход: 0 xor 1 xor 0 = 1 Выход: 0 xor 1 xor 1 xor 0 = 0 Выход отключён от регистра
Четвёртый символ 1101
Кодер витерби Кодер витерби Кодер витерби Кодер витерби
«1» введена в кодер Выход: 1 xor 0 xor 1 = 0 Выход: 1 xor 0 xor 1 xor 1 = 1 Выход отключён от регистра

Можно составить следующую таблицу:

Состояние регистраКомбинация на выходе кодера
100011
110000
011010
101101

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

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

От чего зависит состояние сдвигового регистра? Только от передаваемых информационных символов. При этом какое бы количество информационных символов не передавалось, количество состояний сдвигового регистра конечно и составляет 2k, где k – длина сдвигового регистра.

Это важное замечание, и его следует выделить: количество состояний сдвигового регистра кодера конечно, не зависит от объёма передаваемых данных и составляет 2k, где k – длина сдвигового регистра.

Для нашего кодера k=4, 2k = 16. Значит, какие бы данные не кодировались этим кодером, количество состояний сдвигового регистра не превысит 16. При этом каждому состоянию сдвигового регистра всегда однозначно соответствует одна и та же комбинация на выходе кодера. Все возможные состояния можно свести в таблицу:

NoСостояние регистраКомбинация на выходе кодера
1000000
2000111
3001001
4001110
5010011
6010100
7011010
8011101
9100011
10100100
11101010
12101101
13110000
14110111
15111001
16111110

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

Выбор значения на выходе кодера Витерби
Выбор значения на выходе кодера Витерби

Декодирование свёрточного кода основано на сочетании трёх факторов:

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

Построение решётки

Рассмотрим k−1 крайних правых бит в сдвиговом регистре. В нашем случае k=4, k−1=3. Что произойдёт при переходе кодера в следующее состояние? Как показано на рисунке ниже, в результате сдвига бит из 4-ой ячейки будет потерян, биты из 2-ой и 3-ей ячеек займут, соответственно, 3-ю и 4-ю ячейки. А во второй ячейке окажется бит, занимавший ранее 1-ю ячейку и выпадавший из рассмотрения.

Построение решётки
Построение решётки

Таким образом, рассматривая только k−1 крайних правых бит сдвигового регистра нельзя знать, какой именно бит данных поступил в кодер в данный момент. Но если рассматривать правые биты двух последовательных состояний, то переданный бит определяется однозначно.

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

Рассмотрим рисунок выше. В первоначальный момент времени в крайних правых разрядах сдвигового регистра установлена комбинация 1102. Содержимое крайнего левого разряда не рассматривается, поэтому нельзя сказать, какая комбинация установится на выходе кодера. В следующий момент времени в кодер поступит очередной бит данных и кодер перейдёт в одно из двух состояний, зависящих от того, какой бит находился в крайнем левом разряде регистра сдвига в первоначальный момент времени. Если этот бит был «1», то новое состояние будет Y1112, если «0», то Y0112. Здесь Y – значение крайнего левого бита в новый момент времени. Можно составить дерево переходов, описывающее связь между состояниями и возникающие на выходе кодера комбинации при переходе из состояния в состояние.

Сделать это очень просто, следуя алгоритму:

  1. Определить длину сдвигового регистра k.
  2. Вычесть из k единицу.
  3. Выписать в таблицу в порядке возрастания все числа от 0 до 2k−1−1 в двоичной форме.
  4. Для каждого из чисел выполнить операции:
  • приписать слева «0» к очередному числу разрядности k−1;
  • рассматривая получившуюся комбинацию как состояние сдвигового регистра, вычислить кодовую комбинацию на выходе кодера;
  • взять k−1 бит, начиная СЛЕВА, и записать их;
  • приписать слева «1» к очередному числу разрядности k−1;
  • рассматривая получившуюся комбинацию как состояние сдвигового регистра, вычислить кодовую комбинацию на выходе кодера;
  • взять k−1 бит, начиная СЛЕВА, и записать их.

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

1. Определить длину сдвигового регистра k.

Известны порождающие многочлены – (15,17). Они даны в восьмеричном представлении, при переводе в двоичное получаем числа 11012 и 11112. Разрядность получившихся чисел равна 4. Отсюда k=4.

2. Вычесть из k единицу.

На предыдущем шаге определено k=4. Следовательно, k−1=3.

3. Выписать в таблицу в порядке возрастания все числа от 0 до 2k−1−1 в двоичной форме.

Определим 2k−1 − 1 = 23 − 1 = 8 − 1 = 7. Выпишем числа от 0 до 7 в двоичном представлении:

Десятичное значениеДвоичное значение
0000
1001
2010
3011
4100
5101
6110
7111

4. Для каждого из чисел выполнить операции…

Для числа 0002:

  • Приписываем слева «0», получаем 00002.
  • Рассматривая получившуюся комбинацию как состояние сдвигового регистра, вычисляем кодовую комбинацию на выходе кодера: «00».
  • Берём k−1=3 бит, начиная СЛЕВА, и записываем их: 000.
  • Приписываем слева «1», получаем 10002.
  • Рассматривая получившуюся комбинацию как состояние сдвигового регистра, вычисляем кодовую комбинацию на выходе кодера: «11».
  • Берём k−1=3 бит, начиная СЛЕВА, и записываем их: 100.

Для числа 0012:

  • Приписываем слева «0», получаем 00012.
  • Рассматривая получившуюся комбинацию как состояние сдвигового регистра, вычисляем кодовую комбинацию на выходе кодера: «11».
  • Берём k−1 = 3 бит, начиная СЛЕВА, и записываем их: «000».
  • Приписываем слева «1», получаем 10012.
  • Рассматривая получившуюся комбинацию как состояние сдвигового регистра, вычисляем кодовую комбинацию на выходе кодера: «00».
  • Берём k−1 = 3 бит, начиная СЛЕВА, и записываем их: «100».

Для числа 0102:

  • Приписываем слева «0», получаем 00102.
  • Рассматривая получившуюся комбинацию как состояние сдвигового регистра, вычисляем кодовую комбинацию на выходе кодера: «01».
  • Берём k−1 = 3 бит, начиная СЛЕВА, и записываем их: «001».
  • Приписываем слева «1», получаем 10102.
  • Рассматривая получившуюся комбинацию как состояние сдвигового регистра, вычисляем кодовую комбинацию на выходе кодера: «10».
  • Берём k−1 = 3 бит, начиная СЛЕВА, и записываем их: «101».

Для числа 0112:

  • Приписываем слева «0», получаем 00112.
  • Рассматривая получившуюся комбинацию как состояние сдвигового регистра, вычисляем кодовую комбинацию на выходе кодера: «10».
  • Берём k−1 = 3 бит, начиная СЛЕВА, и записываем их: «001».
  • Приписываем слева «1», получаем 10112.
  • Рассматривая получившуюся комбинацию как состояние сдвигового регистра, вычисляем кодовую комбинацию на выходе кодера: «01».
  • Берём k−1 = 3 бит, начиная СЛЕВА, и записываем их: «101».

Для числа 1002:

  • Приписываем слева «0», получаем 01002.
  • Рассматривая получившуюся комбинацию как состояние сдвигового регистра, вычисляем кодовую комбинацию на выходе кодера: «11».
  • Берём k−1 = 3 бит, начиная СЛЕВА, и записываем их: «010».
  • Приписываем слева «1», получаем 11002.
  • Рассматривая получившуюся комбинацию как состояние сдвигового регистра, вычисляем кодовую комбинацию на выходе кодера: «00».
  • Берём k−1 = 3 бит, начиная СЛЕВА, и записываем их: «110».

Для числа 1012:

  • Приписываем слева «0», получаем «0101».
  • Рассматривая получившуюся комбинацию как состояние сдвигового регистра, вычисляем кодовую комбинацию на выходе кодера: «00».
  • Берём k−1 = 3 бит, начиная СЛЕВА, и записываем их: «010».
  • Приписываем слева «1», получаем «1101».
  • Рассматривая получившуюся комбинацию как состояние сдвигового регистра, вычисляем кодовую комбинацию на выходе кодера: «11».
  • Берём k−1 = 3 бит, начиная СЛЕВА, и записываем их: «110».

Для числа 1102:

  • Приписываем слева «0», получаем 01102.
  • Рассматривая получившуюся комбинацию как состояние сдвигового регистра, вычисляем кодовую комбинацию на выходе кодера: «10».
  • Берём k−1 = 3 бит, начиная СЛЕВА, и записываем их: «011».
  • Приписываем слева «1», получаем 11102.
  • Рассматривая получившуюся комбинацию как состояние сдвигового регистра, вычисляем кодовую комбинацию на выходе кодера: «01».
  • Берём k−1 = 3 бит, начиная СЛЕВА, и записываем их: «111».

Для числа 1112:

  • Приписываем слева «0», получаем 01112.
  • Рассматривая получившуюся комбинацию как состояние сдвигового регистра, вычисляем кодовую комбинацию на выходе кодера: «01».
  • Берём k−1 = 3 бит, начиная СЛЕВА, и записываем их: «011».
  • Приписываем слева «1», получаем 11112.
  • Рассматривая получившуюся комбинацию как состояние сдвигового регистра, вычисляем кодовую комбинацию на выходе кодера: «10».
  • Берём k−1 = 3 бит, начиная СЛЕВА, и записываем их: «111».

Каждое число от 0 до 2k−1−1 = 7 представляет собой узел решётки или состояние кодера. Два числа разрядности k−1=3 – это два узла, в которые можно попасть из текущего, в зависимости от того, «0» или «1» поступит на вход кодера. Кодовые комбинации на выходе кодера соответствуют поступившим «0» и «1» на вход кодера в исходном его состоянии. Результаты можно свести в таблицу:

Узел в десятичном представленииУзел в двоичном представленииПереход в узелВыход кодераПереход в узелВыход кодера
00000000010011
10010001110000
20100010110110
30110011010101
41000101111000
51010100011011
61100111011101
71110110111110

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

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

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

Узел 000 Узлы 000…001 Узлы 000…010 Узлы 000…011
Узел решётки 000 Узлы решётки 000-001 Узлы решётки 000-010 Узлы решётки 000-011
Узлы 000…100 Узлы 000…101 Узлы 000…110 Узлы 000…111
Узлы решётки 000-100 Узлы решётки 000-101 Узлы решётки 000-110 Узлы решётки 000-111

Ниже показан пример кодирования комбинации 10102. Данные вводятся в кодер, начиная с крайнего левого бита.

Кодирование бита «1» из 10102. Исходный узел – «000». Из этого узла можно попасть в узлы «000» или «100». Поскольку кодируется бит «1», переход осуществляется в узел «100». На выходе кодера будет «11». Кодирование бита «0» из 10102. Исходный узел – «100». Из этого узла можно попасть в узлы «010» или «110». Поскольку кодируется бит «0», переход осуществляется в узел «010». На выходе кодера будет «11».
Кодирование бита 1 из 1010 Кодирование бита 0 из 1010
Кодирование бита «1» из 10102. Исходный узел – «010». Из этого узла можно попасть в узлы «001» или «101». Поскольку кодируется бит «1», переход осуществляется в узел «101». На выходе кодера будет «10». Кодирование бита «0» из 10102. Исходный узел – «101». Из этого узла можно попасть в узлы «010» или «110». Поскольку кодируется бит «0», переход осуществляется в узел «010». На выходе кодера будет «10».
Кодирование бита 1 из 1010 Кодирование бита 1 из 1010

Таким образом, на выходе кодера 4 бита входных данных 10102 преобразуются в 8 бит свёрточного кода 11_11_10_002.

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

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

Шаги кодирования числа 1010 по алгоритму Витерби
Шаги кодирования числа 1010 по алгоритму Витерби

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

ШагУзелИнформационный бит
11001
20100
31011
40100

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

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

Декодирование может быть прервано в любой момент (на самом деле желательно пройти более чем 5×(k−1) шагов). Из всех существующих путей выбирается путь с наименьшей метрикой.

Метрика ветви – это хэмингово расстояние между принятой на шаге кодовой комбинацией, и комбинацией, которую должен был бы сгенерировать кодер при переходе из одного узла в другой. На каждом шаге имеется ровно 2k метрик ветвей, т.к. из каждого узла выходят две ветви, или, иными словами, из каждого узла имеется два пути.

Метрика пути – это сумма метрик ветвей, входящих в путь.

Хэмингово расстояние рассчитывается следующим образом: принятая комбинация складывается по модулю два (побитово) со сгенерированной комбинацией и далее рассчитывается количество единиц в получившемся значении. Например, хэмингово расстояние для двух комбинаций 012 и 002 рассчитывается следующим образом: количество единиц (0 xor 0; 1 xor 0) = количество единиц (01) = 1.

Рассмотрим декодирование на примере.

Пусть в декодер поступает комбинация 111110002, первым принимается крайний левый бит.

1 На первом шаге имеется ровно 2k = 24 = 16 ветвей, исходящих из узлов в начале шага.

Для каждой ветви рассчитывается метрика. Метрики ветвей складываются с метриками путей; на первом шаге метрики путей равны 0. Далее для каждого из 8-ми узлов в конце шага имеется по два конкурирующих пути. Один из путей, имеющий большее значение метрики, отбрасывается. Если два пути имеют одинаковую метрику, отбрасывается произвольный путь.

Ниже показана таблица всех возможных путей для первого шага, на котором приняты кодовые символы 112. Символом HD обозначено хэмингово расстояние. В колонке ZZ в таблице указаны символы, генерируемые кодером при переходе из узла во второй колонке в узел в колонке «Куда».

NУзелКудаZZПринятоHD ветвиМетрика пути
10000000011HD (00;11) = 20 + 2 = 2
20001001111HD (11;11) = 00 + 0 = 0
30010001111HD (11;11) = 00 + 0 = 0
40011000011HD (00;11) = 20 + 2 = 2
50100010111HD (01;11) = 10 + 1 = 1
60101011011HD (10;11) = 10 + 1 = 1
70110011011HD (10;11) = 10 + 1 = 1
80111010111HD (01;11) = 10 + 1 = 1
91000101111HD (11;11) = 00 + 0 = 0
101001100011HD (00;11) = 20 + 2 = 2
111010100011HD (00;11) = 20 + 2 = 2
121011101111HD (11;11) = 00 + 0 = 0
131100111011HD (10;11) = 10 + 1 = 1
141101110111HD (01;11) = 10 + 1 = 1
151110110111HD (01;11) = 10 + 1 = 1
161111111011HD (10;11) = 10 + 1 = 1

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

Между собой конкурируют ветви, входящие в один узел. Можно видеть, что в таблице эти ветви размещены через строку (ветви, выходящие из узлов 000 и 001, 010 и 011, 100 и 101, 110 и 111). Метрики путей для первого шага совпадают с метриками ветвей.

  • В узел 000 входят две ветви: из узла 000 и узла 001 (1 и 3 строки таблицы). Метрики этих ветвей равны 2 и 0. 0 меньше 2, следовательно, выживает ветвь (001;000).
  • В узел 001 входят две ветви: из узла 010 и узла 011 (5 и 7 строки таблицы). Метрики этих ветвей обе равны 1. Отбрасывается произвольная ветвь, пусть это будет (011;001). Следовательно, выживет ветвь (010;001).
  • В узел 010 входят две ветви: из узла 100 и узла 101 (9 и 11 строки таблицы). Метрики этих ветвей равны 0 и 2. 0 меньше 2, следовательно, выживает ветвь (100;010).
  • В узел 011 входят две ветви: из узла 110 и узла 111 (13 и 15 строки таблицы). Метрики этих ветвей обе равны 1. Отбрасывается произвольная ветвь, пусть это будет (111;011). Следовательно, выживет ветвь (110;011).
  • В узел 100 входят две ветви: из узла 000 и узла 001 (2 и 4 строки таблицы). Метрики этих ветвей равны 0 и 2. 0 меньше 2, следовательно, выживает ветвь (000;100).
  • В узел 101 входят две ветви: из узла 010 и узла 011 (6 и 8 строки таблицы). Метрики этих ветвей обе равны 1. Отбрасывается произвольная ветвь, пусть это будет (011;101). Следовательно, выживет ветвь (010;101).
  • В узел 110 входят две ветви: из узла 100 и узла 101 (10 и 12 строки таблицы). Метрики этих ветвей равны 2 и 0. 0 меньше 2, следовательно, выживает ветвь (101;110).
  • В узел 111 входят две ветви: из узла 110 и узла 111 (14 и 16 строки таблицы). Метрики этих ветвей обе равны 1. Отбрасывается произвольная ветвь, пусть это будет (111;111). Следовательно, выживет ветвь (110;111).

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

 ПутьМетрика пути
Шаг 1 работы декодера Витерби000;1000
001;0000
010;0011
010;1011
100;0100
101;1100
110;0111
110;1111

2 На втором шаге принята комбинация «11».

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

NУзелКудаZZПринятоHD ветвиМетрика пути
10000000011HD (00;11) = 20 + 2 = 2
20001001111HD (11;11) = 00 + 0 = 0
30010001111HD (11;11) = 01 + 0 = 1
40011000011HD (00;11) = 21 + 2 = 3
50100010111HD (01;11) = 10 + 1 = 1
60101011011HD (10;11) = 10 + 1 = 1
70110011011HD (10;11) = 11 + 1 = 2
80111010111HD (01;11) = 11 + 1 = 2
91000101111HD (11;11) = 00 + 0 = 0
101001100011HD (00;11) = 20 + 2 = 2
111010100011HD (00;11) = 21 + 2 = 3
121011101111HD (11;11) = 01 + 0 = 1
131100111011HD (10;11) = 10 + 1 = 1
141101110111HD (01;11) = 10 + 1 = 1
151110110111HD (01;11) = 11 + 1 = 2
161111111011HD (10;11) = 11 + 1 = 2
  • В узел 000 входят две ветви: из узла 000 и узла 001 (1 и 3 строки таблицы). Метрики этих ветвей равны 2 и 0. Метрики путей равны 2 и 1. 1 меньше 2, следовательно, выживает ветвь (001;000) и путь (010;001;000).
  • В узел 001 входят две ветви: из узла 010 и узла 011 (5 и 7 строки таблицы). Метрики этих ветвей обе равны 1. Метрики путей равны 1 и 2. 1 меньше 2, следовательно, выживает ветвь (010;001) и путь (100;010;001).
  • В узел 010 входят две ветви: из узла 100 и узла 101 (9 и 11 строки таблицы). Метрики этих ветвей равны 0 и 2. Метрики путей равны 0 и 3. 0 меньше 3, следовательно, выживает ветвь (100;010) и путь (000;100;010).
  • В узел 011 входят две ветви: из узла 110 и узла 111 (13 и 15 строки таблицы). Метрики этих ветвей обе равны 1. Метрики путей равны 1 и 2. 1 меньше 2, следовательно, выживает ветвь (110;011) и путь (101;110;011).
  • В узел 100 входят две ветви: из узла 000 и узла 001 (2 и 4 строки таблицы). Метрики этих ветвей равны 0 и 2. Метрики путей равны 0 и 3. 0 меньше 3, следовательно, выживает ветвь (000;100) и путь (001;000;100).
  • В узел 101 входят две ветви: из узла 010 и узла 011 (6 и 8 строки таблицы). Метрики этих ветвей обе равны 1. Метрики путей равны 1 и 2. 1 меньше 2, следовательно, выживает ветвь (010;101) и путь (100;010;101).
  • В узел 110 входят две ветви: из узла 100 и узла 101 (10 и 12 строки таблицы). Метрики этих ветвей равны 2 и 0. Метрики путей равны 2 и 1. 1 меньше 2, следовательно, выживает ветвь (101;110) и путь (010;101;110).
  • В узел 111 входят две ветви: из узла 110 и узла 111 (14 и 16 строки таблицы). Метрики этих ветвей обе равны 1. Метрики путей равны 1 и 2. 1 меньше 2, следовательно, выживает ветвь (110;111) и путь (101;110;111).

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

 ПутьМетрика пути
Шаг 2 работы декодера Витерби(010;001;000)1
(100;010;001)1
(000;100;010)0
(101;110;011)1
(001;000;100)0
(100;010;101)1
(010;101;110)1
(101;110;111)1

На втором шаге появляются узлы, у которых нет выживших ветвей: узлы 0112 и 1112. Так как в каждый узел в конце шага должна входить одна ветвь, появляются и узлы, у которых выживают обе ветви 0102 и 1102.

3 На третьем шаге принята комбинация «10».

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

NУзелКудаZZПринятоHD ветвиМетрика пути
10000000010HD (00;10) = 11 + 1 = 2
20001001110HD (11;10) = 11 + 1 = 2
30010001110HD (11;10) = 11 + 1 = 2
40011000010HD (00;10) = 11 + 1 = 2
50100010110HD (01;10) = 20 + 2 = 2
60101011010HD (10;10) = 00 + 0 = 0
70110011010HD (10;10) = 01 + 0 = 1
80111010110HD (01;10) = 11 + 1 = 2
91000101110HD (11;10) = 10 + 1 = 1
101001100010HD (00;10) = 10 + 1 = 1
111010100010HD (00;10) = 11 + 1 = 2
121011101110HD (11;10) = 11 + 1 = 2
131100111010HD (10;10) = 01 + 0 = 1
141101110110HD (01;10) = 21 + 2 = 3
151110110110HD (01;10) = 21 + 2 = 3
161111111010HD (10;10) = 01 + 0 = 1

Выжившие пути в таблице обозначены жирной рамкой.

 ПутьМетрика пути
Шаг 3 работы декодера Витерби(010;001;000;000)2
(101;110;011;001)1
(001;000;100;010)1
(010;101;110;011)1
(010;001;000;100)2
(000;100;010;101)0
(001;000;100;110)1
(101;110;111;111)1

4 На четвёртом шаге принята комбинация «00».

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

NУзелКудаZZПринятоHD ветвиМетрика пути
10000000000HD (00;00) = 02 + 0 = 2
20001001100HD (11;00) = 22 + 1 = 3
30010001100HD (11;00) = 21 + 2 = 3
40011000000HD (00;00) = 01 + 0 = 1
50100010100HD (01;00) = 11 + 1 = 2
60101011000HD (10;00) = 11 + 0 = 1
70110011000HD (10;00) = 11 + 1 = 2
80111010100HD (01;00) = 11 + 1 = 2
91000101100HD (11;00) = 22 + 2 = 4
101001100000HD (00;00) = 02 + 0 = 2
111010100000HD (00;00) = 00 + 0 = 0
121011101100HD (11;00) = 20 + 2 = 2
131100111000HD (10;00) = 11 + 1 = 2
141101110100HD (01;00) = 11 + 1 = 2
151110110100HD (01;00) = 11 + 1 = 2
161111111000HD (10;00) = 11 + 1 = 2

Выжившие пути в таблице обозначены жирной рамкой.

 ПутьМетрика пути
Шаг 4 работы декодера Витерби(010;001;000;000;000)2
(001;000;100;010;001)2
(000;100;010;101;010)0
(001;000;100;110;011)2
(101;110;011;001;100)1
(001;000;100;010;101)1
(010;001;000;100;110)2
(001;000;100;110;111)2

В конце 4-го шага проведём оценку метрик путей. Видно, что имеется только один путь с наименьшим значением метрики, это путь (000;100;010;101;010), его метрика равна 0. На рисунке ниже этот путь выделен наиболее жирными линиями.

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

Путь с наименьшей метрикой
Путь с наименьшей метрикой

После того, как восстановлен путь, можно определить исходную информационную последовательность. Для этого достаточно взять крайние левые биты узлов, составляющих путь, начиная со второго: (000;100;010;101;010) = 10102.

Аппаратную реализацию декодера рассмотрим в следующей статье.

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

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

Последнее изменениеЧетверг, 24 Март 2022 20:19 Прочитано 1016 раз

Поделиться

Print Friendly, PDF & Email

Оставить комментарий