Введение

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

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

Метрическая единица пути (PMU)

Метрический блок пути суммирует метрики ветвей для получения метрик путей, где K – ограничение длины кода, один из которых в конечном итоге может быть выбран как оптимальный. На каждом такте он принимает решения, намеренно отбрасывая неоптимальные пути. Результаты этих решений записываются в память блока восстановления. Основными элементами МБП являются блоки ACS (Add Compare Select). Способ их соединения определяется диаграммой решетки конкретного кода. Поскольку метрики ветвей всегда положительны, необходима дополнительная схема (не показана на рисунке), предотвращающая переполнение счетчиков метрик. Альтернативный метод, устраняющий необходимость контроля роста метрики пути, заключается в разрешении "переполнения" метрик пути; для использования этого метода необходимо обеспечить достаточное количество битов в аккумуляторах метрик пути, чтобы значения "лучшего" и "худшего" путей не сближались на расстояние меньше 2(n+1). Схема сравнения по существу остается неизменной. Уровень шума во входящем битовом потоке можно контролировать, отслеживая скорость роста метрики "лучшего" пути. Более простой способ – контролировать одно местоположение или "состояние" и наблюдать за его прохождением "вверх" через, например, четыре дискретных уровня в диапазоне аккумулятора. При прохождении через каждый из этих порогов инкрементируется счетчик, отражающий "шум" во входящем сигнале.

Отслеживающая единица (TBU)

Устройство обратной трассировки восстанавливает (почти) наиболее вероятный путь на основе решений, принятых PMU. Поскольку это делается в обратном направлении, декодер Витерби включает в себя буфер FILO (первый пришел – последний вышел) для восстановления правильной последовательности. Обратите внимание, что реализация, показанная на рисунке, требует удвоенной частоты. Существуют приемы, позволяющие избежать этого требования.

Квантизация для декодирования мягких решений

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

где – спектральная плотность мощности шума, а k – число битов для мягкого решения.

Отслеживание

Общий подход к отслеживанию заключается в накоплении метрик пути до пятикратной длины ограничения (5(K–1)), поиске узла с наибольшей накопленной стоимостью и начале отслеживания с этого узла. Распространенное эмпирическое правило о глубине обрезки, равной пятикратному значению памяти (длина ограничения K–1) сверточного кода, верно только для кодов со скоростью 1/2. Для произвольной скорости более точным эмпирическим правилом является 2.5(K–1)/(1–r), где r – скорость кодирования. Однако вычисление узла, накопившего наибольшую стоимость (либо наибольшую, либо наименьшую интегральную метрику пути), требует нахождения максимумов или минимумов нескольких (обычно 2K–1) чисел, что может быть ресурсоемким при реализации на встроенных аппаратных системах. Большинство систем связи используют декодирование Витерби, работающее с пакетами данных фиксированного размера, содержащими фиксированный шаблон битов/байт либо в начале, либо в конце пакета. Используя известный шаблон битов/байт в качестве опорного значения, можно установить начальный узел в фиксированное значение, тем самым обеспечивая оптимальный путь максимального правдоподобия при отслеживании.

Ограничения

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

Внедрение программного обеспечения

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