Декодер Витерби

декодирует битовый поток с помощью алгоритма Витерби

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

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

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

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

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

• 1 Аппаратная реализация
  • 1.1 Метрическая единица ответвления (BMU)
  • 1.2 Метрическая единица пути (PMU)
  • 1.3 Единица отслеживания (TBU)
• 2 Проблемы реализации
  • 2.1 Квантование для декодирования мягких решений
  • 2.2 Вычисление евклидовой метрики
  • 2.3 Отслеживание
• 3 Ограничения
• 4 Проколотые коды
• 5 Программная реализация
• 6 Приложения
• 7 Ссылки
• 8 Внешние ссылки

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

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

• Метрическая единица ответвления (BMU)
• Метрическая единица пути (PMU)
• Единица отслеживания (TBU)

Метрическая единица ветвления (BMU)

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

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

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

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

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

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

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

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

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

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

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

Пример реализации блока ACS

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

Блок обратной трассировки (TBU)

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

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

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

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

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

$T\; =\; N\; 0\; 2\; k,\; \{\backslash \; displaystyle\; \backslash ,\; \backslash !\; T\; =\; \{\backslash \; sqrt\; \{\backslash \; frac\; \{N\_\; \{0\}\}\; \{2\; ^\; \{k\}\}\; \}\},\}$

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

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

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

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

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

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

Каждый символ в кодовый алфавит также может быть представлен вектором vi= {± 1, ± 1}.

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

$D\; =\; (vr\; \to \; -\; vi\; \to )\; 2\; =\; vr\; \to \; 2-2\; vr\; \to \; vi\; \to \; +\; vi\; \to \; 2\; \{\backslash \; displaystyle\; \backslash ,\; \backslash !\; D\; =\; (\{\backslash \; overrightarrow\; \{v\_\; \{r\}\}\}\; -\; \{\backslash \; overrightarrow\; \{v\_\; \{i\}\}\})\; ^\; \{2\}\; =\; \{\backslash \; overrightarrow\; \{v\_\; \{r\}\}\}\; ^\; \{2\}\; -2\; \{\backslash \; overrightarrow\; \{\; v\_\; \{r\}\}\}\; \{\backslash \; overrightarrow\; \{v\_\; \{i\}\}\}\; +\; \{\backslash \; overrightarrow\; \{v\_\; \{i\}\}\}\; ^\; \{2\}\}$

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

$vi\; \to \; 2\; =\; (\pm \; 1)\; 2\; +\; (\pm \; 1)\; 2\; =\; 2\; \{\backslash \; displaystyle\; \backslash ,\; \backslash \; !\; \{\backslash \; overrightarrow\; \{v\_\; \{i\}\}\}\; ^\; \{2\}\; =\; (\backslash \; pm\; 1)\; ^\; \{2\}\; +\; (\backslash \; pm\; 1)\; ^\; \{2\}\; =\; 2\}$

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

Операция Добавить-Сравнить-Выбрать (ACS) сравнивает метрическое расстояние между полученным символом || v r||и любыми двумя символами в кодовом алфавите, чьи пути сливаются в узле в соответствующем решетка, || v i||и || v i||. Это эквивалентно сравнению

$D\; 0\; =\; vr\; \to \; 2\; -\; 2\; vr\; \to \; vi\; 0\; \to \; +\; vi\; 0\; \to \; 2\; \{\backslash \; displaystyle\; \backslash ,\; \backslash !\; D\_\; \{0\}\; =\; \{\backslash \; overrightarrow\; \{v\_\; \{r\}\}\}\; ^\; \{\; 2\}\; -2\; \{\backslash \; overrightarrow\; \{v\_\; \{r\}\}\}\; \{\backslash \; overrightarrow\; \{v\_\; \{i\}\; ^\; \{0\}\}\}\; +\; \{\backslash \; overrightarrow\; \{v\_\; \{i\}\; ^\; \{0\}\}\}\; ^\; \{2\}\}$

и

$D\; 1\; =\; vr\; \to \; 2\; -\; 2\; vr\; \to \; vi\; 1\; \to \; +\; vi\; 1\; \to \; 2\; \{\backslash \; displaystyle\; \backslash ,\; \backslash !\; D\_\; \{1\}\; =\; \{\backslash \; overrightarrow\; \{v\_\; \{r\}\}\}\; ^\; \{2\}\; -\; 2\; \{\backslash \; overrightarrow\; \{v\_\; \{r\}\}\}\; \{\backslash \; overrightarrow\; \{v\_\; \{i\}\; ^\; \{1\}\}\}\; +\; \{\backslash \; overrightarrow\; \{v\_\; \{i\}\; ^\; \{1\}\}\}\; ^\; \{2\}\}$

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

$min\; (-\; 2\; vr\; \to \; vi\; 0\; \to ,\; -\; 2\; vr\; \to \; vi\; 1\; \to )\; =\; max\; (vr\; \to \; vi\; 0\; \to ,\; vr\; \to \; vi\; 1\; \to )\; \{\backslash \; displaystyle\; \backslash ,\; \backslash !\; \backslash \; min\; (-2\; \{\backslash \; overrightarrow\; \{v\_\; \{r\}\}\}\; \{\backslash \; overrightarrow\; \{v\_\; \{i\}\; ^\; \{0\}\}\},\; -\; 2\; \{\; \backslash \; overrightarrow\; \{v\_\; \{r\}\}\}\; \{\backslash \; overrightarrow\; \{v\_\; \{i\}\; ^\; \{1\}\}\})\; =\; \backslash \; max\; (\{\backslash \; overrightarrow\; \{v\_\; \{r\}\}\}\; \{\backslash \; overrightarrow\; \{v\_\; \{i\}\; ^\; \{0\})\; \}\},\; \{\backslash \; overrightarrow\; \{v\_\; \{r\}\}\}\; \{\backslash \; overrightarrow\; \{v\_\; \{i\}\; ^\; \{1\}\})\}$

, поскольку операция min для отрицательных чисел может интерпретироваться как эквивалентная операция max для положительных величин.

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

$max\; (\pm \; r\; 0\; \pm \; r\; 1,\; \pm \; r\; 0\; \pm \; r\; 1)\; \{\backslash \; displaystyle\; \backslash ,\; \backslash !\; \backslash \; Max\; (\backslash \; pm\; r\_\; \{0\}\; \backslash \; pm\; r\_\; \{1\},\; \backslash \; pm\; r\_\; \{0\}\; \backslash \; pm\; r\_\; \{1\})\}$

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

Traceback

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

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

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

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

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

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

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

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

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

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

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

Викискладе есть носители, относящиеся к кодированию Витерби.

• Форни, Дж. Дэвид-младший (29 апреля 2005 г.). «Алгоритм Витерби: личная история». arXiv : cs / 0504020.
• Подробная информация о декодировании Витерби, а также библиография.
• Описание алгоритма Витерби с акцентом на вопросы аппаратной реализации.
• r = 1/6 k = 15 кодирования для миссии Кассини на Сатурн.
• Онлайн-генератор оптимизированного программного обеспечения декодеров Витерби (GPL).
• GPL Программное обеспечение декодера Витерби для четырех стандартных кодов.
• Описание декодера Витерби ak = 24, который считается крупнейшим в мире Практическое использование.
• Стандартное аппаратное обеспечение декодера Витерби (GPL).