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

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

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

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

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

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

Число 15₈ в восьмеричном представлении записывается как 13₁₀ в десятичном и 1101₂ в двоичном. Поэтому 1, 2 и 4-я ячейки сдвигового регистра подключены к сумматору 15₈. Число 17₈ в восьмеричном представлении – 1111₂ в двоичном (все ячейки регистра подключены к 2-му сумматору).

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

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

Для чисел 5₈ и 7₈ в восьмеричной системе соответствующее десятичное представление будет 5₁₀ и 7₁₀, двоичное – 101₂ и 111₂. Длина регистра сдвига – 3 элемента.

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

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

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

Первый символ 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	Выход отключён от регистра

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Для числа 000₂:

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

Для числа 001₂:

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

Для числа 010₂:

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

Для числа 011₂:

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

Для числа 100₂:

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

Для числа 101₂:

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

Для числа 110₂:

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

Для числа 111₂:

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

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

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

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

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

Узел 000	Узлы 000…001	Узлы 000…010	Узлы 000…011
Узлы 000…100	Узлы 000…101	Узлы 000…110	Узлы 000…111

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Между собой конкурируют ветви, входящие в один узел. Можно видеть, что в таблице эти ветви размещены через строку (ветви, выходящие из узлов 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).

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

	Путь	Метрика пути
	000;100	0
	001;000	0
	010;001	1
	010;101	1
	100;010	0
	101;110	0
	110;011	1
	110;111	1

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

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

• В узел 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).

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

	Путь	Метрика пути
	(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

На втором шаге появляются узлы, у которых нет выживших ветвей: узлы 011₂ и 111₂. Так как в каждый узел в конце шага должна входить одна ветвь, появляются и узлы, у которых выживают обе ветви 010₂ и 110₂.

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

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

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

	Путь	Метрика пути
	(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».

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

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

	Путь	Метрика пути
	(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) = 1010₂.

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

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

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