Последовательное декодирование

По признанию Джона Возенкрафта , последовательное декодирование представляет собой метод с ограниченной памятью для декодирования древовидных кодов . Последовательное декодирование в основном используется в качестве алгоритма приближенного декодирования для сверточных кодов с большой длиной ограничения . Этот подход может быть не таким точным, как алгоритм Витерби , но может сэкономить значительный объем компьютерной памяти. Он использовался для декодирования сверточного кода в миссии «Пионер-9» в 1968 году .

Последовательное декодирование исследует код дерева таким образом, чтобы попытаться минимизировать вычислительные затраты и требования к памяти для хранения дерева.

Существует ряд подходов последовательного декодирования, основанных на выборе метрики и алгоритма. Метрики включают в себя:

Метрика Фано
Метрика Зигангирова
Метрика Галлагера

Алгоритмы включают в себя:

Алгоритм стека
Алгоритм Фано
Алгоритм крипера

Метрика Фано

Учитывая частично исследованное дерево (представленное набором узлов, которые являются пределом исследования), мы хотели бы знать лучший узел для дальнейшего исследования. Метрика Фано (названная в честь Роберта Фано ) позволяет рассчитать, какой узел лучше всего исследовать дальше. Эта метрика является оптимальной при отсутствии других ограничений (например, памяти).

Для двоичного симметричного канала (с вероятностью ошибки $p$ ) метрика Фано может быть получена с помощью теоремы Байеса . Мы заинтересованы в том, чтобы следовать по наиболее вероятному пути. $P_{i}$ учитывая исследованное состояние дерева $X$ и полученная последовательность ${\mathbf {r} }$ . Используя язык вероятности и теорему Байеса, мы хотим выбрать максимум из $i$ из:

\Pr(P_{i}|X,{\mathbf {r} })\propto \Pr({\mathbf {r} }|P_{i},X)\Pr(P_{i}|X)

Теперь введем следующие обозначения:

$N$ для обозначения максимальной длины передачи в ветвях
$b$ для представления количества бит в ветви кода (знаменатель скорости кода , $R$ ).
$d_{i}$ для представления количества битовых ошибок на пути $P_{i}$ ( расстояние Хэмминга между метками ветвей и полученной последовательностью)
$n_{i}$ быть длиной $P_{i}$ в филиалах.

Мы выражаем вероятность $\Pr({\mathbf {r} }|P_{i},X)$ как $p^{d_{i}}(1-p)^{n_{i}b-d_{i}}2^{-(N-n_{i})b}$ (с использованием вероятности двоичного симметричного канала для первого $n_{i}b$ битов, за которыми следует равномерный априор над остальными битами).

Мы выражаем предшествующее $\Pr(P_{i}|X)$ с точки зрения количества выбранных вами ветвей, $n_{i}$ и количество ветвей от каждого узла, $2^{Rb}$ .

Поэтому:

{\begin{aligned}\Pr(P_{i}|X,{\mathbf {r} })&\propto p^{d_{i}}(1-p)^{n_{i}b-d_{i}}2^{-(N-n_{i})b}2^{-n_{i}Rb}\\&\propto p^{d_{i}}(1-p)^{n_{i}b-d_{i}}2^{n_{i}b}2^{-n_{i}Rb}\end{aligned}}

Мы можем эквивалентно максимизировать лог этой вероятности, т.е.

{\begin{aligned}&d_{i}\log _{2}p+(n_{i}b-d_{i})\log _{2}(1-p)+n_{i}b-n_{i}Rb\\=&d_{i}(\log _{2}p+1-R)+(n_{i}b-d_{i})(\log _{2}(1-p)+1-R)\end{aligned}}

Это последнее выражение является метрикой Фано. Важно отметить, что здесь у нас есть два термина: один основан на количестве неправильных битов, а другой основан на количестве правильных битов. Поэтому мы можем обновить метрику Фано, просто добавив $\log _{2}p+1-R$ для каждого несовпадающего бита и $\log _{2}(1-p)+1-R$ для каждого совпадающего бита.

Скорость отсечки вычислений

Чтобы последовательное декодирование было хорошим выбором алгоритма декодирования, количество исследуемых состояний должно оставаться небольшим (в противном случае алгоритм, который намеренно исследует все состояния, например алгоритм Витерби более подходящим может оказаться ). Для определенного уровня шума существует максимальная скорость кодирования. $R_{0}$ называется вычислительной скоростью отсечки, где существует конечный предел обратного отслеживания. Для двоичного симметричного канала:

R_{0}=1-\log _{2}(1+2{\sqrt {p(1-p)}})

Алгоритмы

Алгоритм стека

Самый простой алгоритм для описания — это «алгоритм стека», в котором наилучший $N$ пути, найденные на данный момент, сохраняются. Последовательное декодирование может привести к дополнительной ошибке по сравнению с декодированием Витерби, если правильный путь указан. $N$ или более высоко оцененные пути над ним; в этот момент лучший путь выпадет из стека и больше не будет рассматриваться.

Алгоритм Фано

Знаменитый алгоритм Фано (названный в честь Роберта Фано ) требует очень мало памяти и, следовательно, подходит для аппаратных реализаций. Этот алгоритм исследует взад и вперед от одной точки дерева.

Алгоритм Фано — это алгоритм последовательного декодирования, не требующий стека.
Алгоритм Фано может работать только с деревом кодов, поскольку он не может проверять слияние путей.
На каждом этапе декодирования алгоритм Фано сохраняет информацию о трех путях: текущем пути, его непосредственном предшественнике и одном из его последующих путей.
На основе этой информации алгоритм Фано может перейти от текущего пути либо к его непосредственному предшественнику, либо к выбранному последующему пути; следовательно, для постановки в очередь всех проверенных путей стек не требуется.
Движение алгоритма Фано управляется динамическим порогом T , который кратен фиксированному размеру шага Δ.
только тот путь, метрика пути которого не меньше T. В следующий раз можно посетить Согласно алгоритму, процесс поиска кодового слова продолжает двигаться вперед по кодовому пути до тех пор, пока метрика Фано вдоль кодового пути остается неубывающей.
Как только все метрики пути преемника станут меньше T , алгоритм переходит назад к пути предшественника, если метрика пути предшественника превосходит T ; после этого пороговая проверка будет впоследствии выполнена на другом пути-преемнике этого пересмотренного предшественника.
Если метрика пути предшественника также меньше T , порог T снижается на один шаг, чтобы алгоритм не застревал на текущем пути.
Для алгоритма Фано, если путь повторно посещается, текущий динамический порог всегда ниже, чем мгновенный динамический порог при предыдущем посещении, гарантируя, что зацикливания в алгоритме не произойдет и что алгоритм в конечном итоге сможет достичь конечного узла дерево кода и остановитесь.

Ссылки

Джон Возенкрафт и Б. Райффен, Последовательное декодирование , ISBN 0-262-23006-2
Рольф Йоханнессон и Камил Ш. Зигангиров, Основы сверточного кодирования (глава 6), ISBN 0-470-27683-5

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

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