8.2.7. Другие алгоритмы декодирования свёрточных кодов

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

Еще до открытия оптимального алгоритма Витерби, были придуманы другие алгоритмы для декодирования свёрточных кодов. Самым ранним был алгоритм последовательного декодирования, впервые предложенный Возенкрафтом и впоследствии модифицированный Фано (1963).

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

Для большей конкретности рассмотрим канал без памяти.

Метрика для -го пути по дереву или решётке от первой ветви до -й ветви можно выразить так

, (8.2.42)

где

. (8.2.43)

В (8.2.43) - выходная последовательность демодулятора, означает условную ФПВ при условии кодового бита (-й бит в -й ветви -гo пути), а - положительная константа. выбирается, как сказано выше, так, что неправильные пути будут иметь уменьшающиеся метрики, в то время как правильный путь в среднем увеличивает метрику. Заметим, что член в знаменателе не зависит от кодовой последовательности и, следовательно, может быть включен в постоянную.

Метрика, определённая (8.2.43), в общем применима при декодировании как жёстких, так и мягких решений. Однако она может быть особенно упрощена, когда используется декодирование жёстких решений. В частном случае, если мы имеем ДСК с переходной вероятностью ошибки , метрика для каждого принятого символа, согласующаяся с формулой (8.2.43), определяется так

(8.2.44)

где - выходы жёстких решений демодулятора; - -й кодовый символ в -й ветви -го пути дерева; - скорость кода.

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

Пример 8.2.6. Предположим, что для передачи информации по ДСК с вероятностью ошибки используется двоичный свёрточный код со скоростью . Вычисление согласно (8.2.44) дает

(8.2.45)

Для упрощения расчётов метрики (8.2.45) можно нормировать. Они хорошо аппроксимируются так:

(8.2.46)

Поскольку скорость кода равна 1/3, то кодер имеет три выходных символа на каждый входной символ. Тогда метрики ветвей, согласующиеся с (8.2.46), равны

или, что эквивалентно,

, (8.2.47)

где — хеммингово расстояние трёх принятых бит от трёх битов на ветви.

Таким образом, метрики просто связаны с расстоянием Хемминга между принимаемыми символами и кодовыми символами -й ветви -го пути.

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

Поскольку метрики неверного пути в среднем уменьшаются, метрика упадет ниже текущего порога, скажем . Если это случится, декодер возвращается обратно и берёт альтернативный путь по дереву (решётке) с меньшей метрикой ветви, в попытке найти другой путь с большей метрикой, которая превосходит порог . Если приходит удача в альтернативном пути, это продолжается вдоль пути все время, и выбирается наиболее правдоподобная ветвь в каждом узле. С другой стороны, если не существует пути, который превышает порог , порог уменьшается на величину и декодер возвращается к первоначальному пути. Если первоначальный путь не находится выше нового порога, декодер начинает обратный поиск других путей. Эта процедура повторяется с уменьшением порога на при каждом повторении до тех пор, пока декодер не найдет путь, который остаётся выше установленного порога. Упрощённая структурная схема алгоритма Фано показана на рис. 8.2.18.

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

Алгоритм последовательного декодирования Фано успешно применяется в различных системах связи. Его качество по вероятности ошибки сравнимо с декодером Витерби. Однако по сравнению с декодером Витерби последовательное декодирование имеет значительно большую задержку декодирования. С другой стороны, последовательное декодирование требует меньше памяти, чем декодирование по Витерби, и, следовательно, оно является привлекательным для свёрточных кодов с большим кодовым ограничением.

Исследования вычислительной сложности и требований к памяти для последовательного декодирования вызывают интерес, и они все еще продолжаются. Для анализа этих вопросов и других характеристик алгоритмов Фано интересующемуся читателю рекомендуются книги Галлагера (1986), Возенкрафта и Джекобса (1965), Сэвейдж (1966) и Форни (1974). Другой тип алгоритма последовательного декодирования, названный стек-алгоритмом, был предложен независимо Зигангировым (1966) и Елинеком (1969). В противовес алгоритму Витерби, который сохраняет траектории путей и соответствующих метрик, стек-алгоритм последовательного декодирования работает с несколькими путями и их соответствующими метриками. В стек-алгоритме более вероятные пути упорядочиваются согласно их метрик, причём в верхней части (в голове стека) располагается путь, имеющий наибольшую метрику. На каждом шаге алгоритма только путь в голове стека проверяется по разветвлению. Это приносит продолжений и их соответствующих метрик. Эти продолжения вместе с другими путями затем упорядочиваются согласно величинам их метрик, и все пути с метриками, которые располагаются ниже некоторой выбранной величины от метрики главного пути, отбрасываются. Затем процесс продолжения путей с наибольшими метриками повторяется. Рис. 8.2.19 иллюстрирует несколько первых шагов стек-алгоритма.

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

Стек с накопленными метриками путей

Шаг	Шаг	Шаг	Шаг	Шаг	Шаг
-1	-2	-2	-2	-2	-3
-2	-2	-3	-3	-3	-3
	-3	-3	-3	-3	-3
		-4	-3	-4	-4
			-5	-5	-4
				-8	-5
					-8

Рис. 8.2.19. Пример работы стек-алгоритма для декодирования свёрточного кода со скоростью 1/3

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

Третья альтернатива оптимального декодера Витерби – это метод, названный декодированием с обратной связью (Хеллер 1975), который был разработан для декодирования в ДСК (декодирование жёстких решений). При декодировании с обратной связью декодер делает жёсткое решение об информационном символе на -м шаге, основываясь на метриках, вычисленных от -го до -го шага, где - выбранное целое число. Таким образом, решение об информационном символе в пользу 0 или 1 зависит от того, каково минимальное расстояние по Хеммингу для пути, который начинается на -м шаге и кончается на -м шаге и сколько содержится «0» или «1» в ветви, исходящих от шага . Решение выносится один раз об информационном символе на шаге, и только часть дерева, которая связана с этим символом, сохраняется (половина путей, исходящих из узла ), а остальные пути исключаются. Так осуществляется обратная связь в декодере. Следующий шаг заключается в расширении части дерева, которая вышла до шага и рассмотрении путей от шага -го до -гo для принятия решения о символе на шаге . Так процедура повторяется на каждом шаге. Параметр - это просто число шагов по дереву, которое декодер учитывает при вынесении жёсткого решения. Поскольку большая величина ведет к большой величине памяти, желательно выбрать как можно меньше. С другой стороны, должно быть достаточно большим, чтобы избежать существенного ухудшения качества. Чтобы сбалансировать эти два противоречивых требования, обычно выбирается в области , где - кодовое ограничение. Заметим, что эта задержка при декодировании значительно меньше, чем задержка при использовании алгоритма Витерби, которая обычно около .

Пример 8.2.7. Рассмотрим использование декодера с обратной связью для свёрточного кода со скоростью 1/3, показанного на рис. 8.2.2. Рис. 8.2.20 иллюстрирует древовидную диаграмму и операции декодера с обратной связью при . Это значит, что при декодировании символа ветви , декодер рассматривает пути на ветвях и . Начиная с первой ветви, декодер рассчитывает восемь метрик (расстояние Хемминга) и решает, что символ в первой ветви является 0, если путь с минимальным расстоянием находится в верхней части дерева и, что символ 1, если путь с минимальным расстоянием находится в нижней части дерева. В этом примере принимаемая последовательность для первых трёх ветвей полагается такой 101 111 110, поэтому путь с минимальным расстоянием находится в верхней части дерева, следовательно, первый выход символа декодера 0.

Следующие шаги сводятся к расширению верхней части дерева (той части дерева, которая выжила) на одну ветвь и к вычислению восьми метрик в ветвях 2, 3 и 4. Для предположения входной последовательности 111 110 011 путь с минимальным расстоянием находится в нижней части секции дерева, вычислившей после первого шага. Итак, второй выходной символ декодера 1. Третий шаг заключается в расширении этой нижней части дерева и повторении процедуры, описанной для двух первых шагов.

Рис. 8.2.20. Пример декодирования с обратной связью для свёрточного кода со скоростью 1/3

Вместо вычисления метрик описанным выше способом, декодер с обратной связью в ДСК можно эффективно реализовать путём вычисления синдрома по принимаемой последовательности и используя табличный метод коррекции ошибок. Этот метод похож на тот, который был описан выше для декодирования блоковых кодов. Для некоторых свёрточных кодов декодер с обратной связью упрощается к виду, называемому логический декодер по большинству или пороговый декодер (Месси 1963; Хеллер 1975).