Декодер Витерби - Viterbi decoder

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

Существуют и другие алгоритмы декодирования сверточно закодированного потока (например, Алгоритм Фано ). Алгоритм Витерби является наиболее ресурсоемким, но он делает максимальная вероятность расшифровка. Чаще всего он используется для декодирования сверточных кодов с ограничениями длины k≤3, но на практике используются значения до k = 15.

Декодирование Витерби было разработано Эндрю Дж. Витерби и опубликовано в газете Витерби, А. (апрель 1967). "Границы ошибок для сверточных кодов и асимптотически оптимального алгоритма декодирования". IEEE Transactions по теории информации. 13 (2): 260–269. Дои:10.1109 / tit.1967.1054010.

Существуют как аппаратные (в модемах), так и программные реализации декодера Витерби.

Декодирование Витерби используется в итеративное декодирование Витерби алгоритм.

Аппаратная реализация

Распространенный способ реализации аппаратного декодера Витерби

Аппаратный декодер Витерби для базового (непроколотого) кода обычно состоит из следующих основных блоков:

Метрическая единица отделения
Единица измерения пути (PMU)
Блок обратного прослеживания (TBU)

Метрическая единица измерения отделения (БМУ)

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

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

Есть твердое решение и мягкое решение декодеров Витерби. Декодер Витерби с жестким решением принимает на вход простой битовый поток, а Расстояние Хэмминга используется как метрика. Декодер Витерби с мягким решением принимает битовый поток, содержащий информацию о надежность каждого полученного символа. Например, в 3-битной кодировке это надежность информация может быть закодирована следующим образом:

ценность	смысл
000	сильнейший	0
001	относительно сильный	0
010	относительно слабый	0
011	самый слабый	0
100	самый слабый	1
101	относительно слабый	1
110	относительно сильный	1
111	сильнейший	1

Конечно, это не единственный способ кодирования данных о надежности.

В в квадрате Евклидово расстояние используется в качестве метрики для декодеров мягких решений.

Единица измерения пути (PMU)

Пример реализации единицы измерения пути для конкретного декодера K = 4

Единица метрики пути суммирует метрики ветви, чтобы получить метрики для ${ displaystyle 2 ^ {K-1}}$ путей, где K - длина ограничения кода, один из которых в конечном итоге может быть выбран как оптимальный. Каждые часы это делает ${ displaystyle 2 ^ {K-1}}$ решения, выбрасывающие заведомо неоптимальные пути. Результаты этих решений записываются в память модуля трассировки.

Основные элементы PMU: ACS (Добавить-Сравнить-Выбрать) единицы. Способ, которым они связаны между собой, определяется конкретным кодом решетчатая диаграмма.

Поскольку показатели отрасли всегда ${ displaystyle geq 0}$ , должна быть дополнительная схема (на рисунке не показана), предотвращающая переполнение счетчиков метрик. Альтернативный метод, который избавляет от необходимости отслеживать рост метрики пути, состоит в том, чтобы позволить метрике пути «пролонгировать»; чтобы использовать этот метод, необходимо убедиться, что аккумуляторы метрики пути содержат достаточно битов, чтобы «лучшее» и «худшее» значения не попадали в 2^(п-1) друг друга. Схема сравнения практически не изменилась.

Пример реализации блока САУ

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

Блок обратного прослеживания (TBU)

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

Блок обратного прослеживания восстанавливает (почти) путь максимального правдоподобия из решений, принятых PMU. Поскольку он делает это в обратном направлении, декодер Витерби содержит буфер FILO (first-in-last-out) для восстановления правильного порядка.

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

Проблемы реализации

Квантование для декодирования с мягким решением

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

{ displaystyle , ! T = { sqrt { frac {N_ {0}} {2 ^ {k}}}},}

где ${ displaystyle N_ {0}}$ - спектральная плотность мощности шума, а k - количество бит для мягкого решения.

Вычисление евклидовой метрики

Квадрат норма ( ${ displaystyle ell _ {2}}$ ) расстояние между принятыми и фактическими символами в кодовом алфавите может быть дополнительно упрощено до линейной формы суммы / разности, что делает его менее требовательным к вычислениям.

Рассмотрим 1/2 сверточный кодер, который генерирует 2 бита (00, 01, 10 или 11) для каждого входного бита (1 или 0). Эти Возврат к нулю сигналы переводятся в Без возврата к нулю форма показана рядом.

кодовый алфавит	векторное отображение
00	+1, +1
01	+1, −1
10	−1, +1
11	−1, −1

Каждый принятый символ может быть представлен в векторной форме как v_р = {r₀, р₁}, где r₀ и г₁ - значения мягкого решения, величины которых означают совместная надежность полученного вектора, v_р.

Аналогичным образом каждый символ в кодовом алфавите может быть представлен вектором v_я = {±1, ±1}.

Фактическое вычисление метрики евклидова расстояния:

{ displaystyle , ! D = ({ overrightarrow {v_ {r}}} - { overrightarrow {v_ {i}}}) ^ {2} = { overrightarrow {v_ {r}}} ^ {2 } -2 { overrightarrow {v_ {r}}} { overrightarrow {v_ {i}}} + { overrightarrow {v_ {i}}} ^ {2}}

Каждый квадратный член представляет собой нормированное расстояние, отображающее энергия символа. Например, энергия символа v_я = {± 1, ± 1} может быть вычислено как

{ displaystyle , ! { overrightarrow {v_ {i}}} ^ {2} = ( pm 1) ^ {2} + ( pm 1) ^ {2} = 2}

Таким образом, энергетический член всех символов в кодовом алфавите постоянен (при (нормализованный) значение 2).

В Добавить-Сравнить-Выбрать (ACS) операция сравнивает метрическое расстояние между полученными символами || v_р|| и любые 2 символа в кодовом алфавите, чьи пути сливаются в узле соответствующей решетки, || v_я⁽⁰⁾|| и || v_я⁽¹⁾||. Это эквивалентно сравнению

{ displaystyle , ! D_ {0} = { overrightarrow {v_ {r}}} ^ {2} -2 { overrightarrow {v_ {r}}} { overrightarrow {v_ {i} ^ {0} }} + { overrightarrow {v_ {i} ^ {0}}} ^ {2}}

и

{ displaystyle , ! D_ {1} = { overrightarrow {v_ {r}}} ^ {2} -2 { overrightarrow {v_ {r}}} { overrightarrow {v_ {i} ^ {1} }} + { overrightarrow {v_ {i} ^ {1}}} ^ {2}}

Но сверху мы знаем, что энергия из v_я является постоянным (равным (нормализованному) значению 2), а энергия из v_р одинаково в обоих случаях. Это сокращает сравнение до минимальной функции между двумя (средними) скалярное произведение термины,

{ displaystyle , ! min (-2 { overrightarrow {v_ {r}}} { overrightarrow {v_ {i} ^ {0}}}, - 2 { overrightarrow {v_ {r}}} { overrightarrow {v_ {i} ^ {1}}}) = max ({ overrightarrow {v_ {r}}} { overrightarrow {v_ {i} ^ {0}}}, { overrightarrow {v_ {r }}} { overrightarrow {v_ {i} ^ {1}}})}

так как $мин$ операцию с отрицательными числами можно интерпретировать как эквивалент $Максимум$ работа с положительными величинами.

Каждый скалярное произведение срок может быть расширен как

{ displaystyle , ! max ( pm r_ {0} pm r_ {1}, pm r_ {0} pm r_ {1})}

где знаки каждого члена зависят от символов, v_я⁽⁰⁾ и v_я⁽¹⁾, сравнивая. Таким образом в квадрате Расчет евклидовых метрических расстояний для вычисления метрика отрасли может выполняться с помощью простой операции сложения / вычитания.

Проследить

Общий подход к трассировке заключается в накоплении метрик пути до пятикратной длины ограничения (5 (K - 1)), найдите узел с наибольшей накопленной стоимостью и начните обратную трассировку с этого узла.

Обычно используемое эмпирическое правило глубины усечения в пять раз превышает объем памяти (длина ограничения K-1) сверточного кода точен только для кодов со скоростью 1/2. Для произвольной ставки точное практическое правило - 2,5 (K - 1)/(1−р) где р кодовая скорость.^[1]

Однако вычисление узла, который накопил наибольшую стоимость (наибольшую или наименьшую метрику интегрального пути), включает в себя поиск максимумы или минимумы из нескольких (обычно 2^K-1) чисел, что может занять много времени при реализации во встроенных аппаратных системах.

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

Ограничения

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

На выходе декодера Витерби при декодировании сообщения, поврежденного аддитивным гауссовым каналом, ошибки сгруппированы в пакеты ошибок.^[2]^[3]Коды с исправлением одиночных ошибок в одиночку не может исправить такие всплески, так что либо сверточный код и декодер Витерби должен быть достаточно мощным, чтобы снизить количество ошибок до приемлемой скорости, или пакетные коды с исправлением ошибок должны быть использованы.

Проколотые коды

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

Депунктор, который преобразует входной поток в поток, который выглядит как исходный (не проколотый) поток с метками ERASE в местах, где были стерты биты.
Базовый декодер Витерби, понимающий эти метки ERASE (то есть не использующий их для расчета метрики ветвления).

Программная реализация

Одна из самых трудоемких операций - это бабочка ACS, которая обычно реализуется с помощью язык ассемблера и соответствующие расширения набора команд (например, SSE2 ), чтобы ускорить время декодирования.

Приложения

Алгоритм декодирования Витерби широко используется в следующих областях:

Радиосвязь: цифровое ТВ (ATSC, QAM, DVB-T, так далее.), радиореле, спутниковая связь, PSK31 цифровой режим для любительское радио.
Расшифровка модуляция с решетчатым кодом (TCM), метод, используемый в модемах телефонной линии, чтобы выжать спектральная эффективность из аналоговых телефонных линий с полосой пропускания 3 кГц.
Компьютерные запоминающие устройства, такие как жесткие диски.
Автоматическое распознавание речи

использованная литература

^ Б. Моисион, «Эмпирическое правило глубины усечения для сверточных кодов», 2008 г., семинар по теории информации и приложениям, Сан-Диего, Калифорния, 2008 г., стр. 555-557, Дои:10.1109 / ITA.2008.4601052.
^ Стефан Хост, Рольф Йоханнессон, Дмитрий К. Зигангирод, Камил Ш. Зигангирод, Виктор Васильевич Зяблод.«О распределении длин выходных пакетов ошибок для декодирования сверточных кодов по Витерби».
^ Карри, С. Дж .; Хармон, В. Д.«Ограничение длины пакета ошибок декодера Витерби».

внешние ссылки

[1] Б. Моисион, «Эмпирическое правило глубины усечения для сверточных кодов», 2008 г., семинар по теории информации и приложениям, Сан-Диего, Калифорния, 2008 г., стр. 555-557, Дои:10.1109 / ITA.2008.4601052.

[2] Стефан Хост, Рольф Йоханнессон, Дмитрий К. Зигангирод, Камил Ш. Зигангирод, Виктор Васильевич Зяблод.«О распределении длин выходных пакетов ошибок для декодирования сверточных кодов по Витерби».

[3] Карри, С. Дж .; Хармон, В. Д.«Ограничение длины пакета ошибок декодера Витерби».

[1]

[2]

[3]