8.2.7. Другие алгоритмы декодирования свёрточных кодовАлгоритм Витерби, описанный в разделе 8.2.2, это оптимальный алгоритм декодирования для свёрточных кодов. Однако он требует вычисления Еще до открытия оптимального алгоритма Витерби, были придуманы другие алгоритмы для декодирования свёрточных кодов. Самым ранним был алгоритм последовательного декодирования, впервые предложенный Возенкрафтом и впоследствии модифицированный Фано (1963). Последовательный алгоритм декодирования Фано ищет наиболее правдоподобный путь по дереву или решётке путём проверки каждый раз одного пути. Приращение, добавляемое к метрике вдоль ветви пропорционально вероятности принимаемого сигнала для этой ветви, как в алгоритме Витерби, за исключением того, что к метрике каждой ветви добавляется отрицательная константа. Величина этой константы выбирается так, что метрика правильного пути будет в среднем увеличиваться, в то время как метрика для любого неправильного пути в среднем будет уменьшаться. Путём сравнения метрики претендующего пути с меняющимся (увеличивающимся) порогом алгоритм Фано обнаруживает и отвергает неправильные пути. Для большей конкретности рассмотрим канал без памяти. Метрика для
где
В (8.2.43) Метрика, определённая (8.2.43), в общем применима при декодировании как жёстких, так и мягких решений. Однако она может быть особенно упрощена, когда используется декодирование жёстких решений. В частном случае, если мы имеем ДСК с переходной вероятностью ошибки
где Заметим, что эти метрики требуют хотя бы приближённого знания вероятности ошибки Пример 8.2.6. Предположим, что для передачи информации по ДСК с вероятностью ошибки
Для упрощения расчётов метрики (8.2.45) можно нормировать. Они хорошо аппроксимируются так:
Поскольку скорость кода равна 1/3, то кодер имеет три выходных символа на каждый входной символ. Тогда метрики ветвей, согласующиеся с (8.2.46), равны или, что эквивалентно,
где Таким образом, метрики Первоначально декодер можно заставить выбирать правильную траекторию путём передачи известной цепочки данных. Тогда он продвигается вперед от узла к узлу, выбирая наиболее вероятную (с большей метрикой) ветвь в каждом узле и увеличивая порог так, что его изменение никогда не больше, чем некоторая заранее выбранная величина, скажем, Рис. 8.2.17. Пример поиска пути при последовательном декодировании [Jordan (1966), © 1966 IЕЕЕ] Поскольку метрики неверного пути в среднем уменьшаются, метрика упадет ниже текущего порога, скажем Алгоритм последовательного декодирования требует буферную память в декодере для хранения поступающих данных декодирования в течение периодов, когда декодер ищет альтернативные пути. Когда поиск заканчивается, декодер должен быть в состоянии обрабатывать демодулированные символы достаточно быстро, чтобы освободить буфер для начала нового поиска. Иногда в течение экстремально длинных поисков буфер может переполниться. Это вызывает потерю данных, которые можно восстановить повторением потерянной информации. В этой связи мы хотим напомнить, что предельная скорость Алгоритм последовательного декодирования Фано успешно применяется в различных системах связи. Его качество по вероятности ошибки сравнимо с декодером Витерби. Однако по сравнению с декодером Витерби последовательное декодирование имеет значительно большую задержку декодирования. С другой стороны, последовательное декодирование требует меньше памяти, чем декодирование по Витерби, и, следовательно, оно является привлекательным для свёрточных кодов с большим кодовым ограничением. Рис. 8.2.18. Упрощённая структура алгоритма Фано [Jordan (1966), © 1966 IЕЕЕ] Исследования вычислительной сложности и требований к памяти для последовательного декодирования вызывают интерес, и они все еще продолжаются. Для анализа этих вопросов и других характеристик алгоритмов Фано интересующемуся читателю рекомендуются книги Галлагера (1986), Возенкрафта и Джекобса (1965), Сэвейдж (1966) и Форни (1974). Другой тип алгоритма последовательного декодирования, названный стек-алгоритмом, был предложен независимо Зигангировым (1966) и Елинеком (1969). В противовес алгоритму Витерби, который сохраняет траектории Очевидно, что если ни одно из Стек с накопленными метриками путей
Рис. 8.2.19. Пример работы стек-алгоритма для декодирования свёрточного кода со скоростью 1/3 Из сравнения стек-алгоритма с алгоритмом Витерби следует, что стек-алгоритм требует малого числа сравнений метрик, но его вычислительная экономия в большой степени снижается за счёт вычислений, требуемых для упорядочивания стека после каждой итерации. По сравнению с алгоритмом Фано, стек-алгоритм в вычислительном отношении проще, поскольку здесь нет возвращения по тому же пути, как это делает алгоритм Фано. С другой стороны, стек-алгоритм требует больше памяти, чем алгоритм Фано. Третья альтернатива оптимального декодера Витерби – это метод, названный декодированием с обратной связью (Хеллер 1975), который был разработан для декодирования в ДСК (декодирование жёстких решений). При декодировании с обратной связью декодер делает жёсткое решение об информационном символе на Пример 8.2.7. Рассмотрим использование декодера с обратной связью для свёрточного кода со скоростью 1/3, показанного на рис. 8.2.2. Рис. 8.2.20 иллюстрирует древовидную диаграмму и операции декодера с обратной связью при Следующие шаги сводятся к расширению верхней части дерева (той части дерева, которая выжила) на одну ветвь и к вычислению восьми метрик в ветвях 2, 3 и 4. Для предположения входной последовательности 111 110 011 путь с минимальным расстоянием находится в нижней части секции дерева, вычислившей после первого шага. Итак, второй выходной символ декодера 1. Третий шаг заключается в расширении этой нижней части дерева и повторении процедуры, описанной для двух первых шагов. Рис. 8.2.20. Пример декодирования с обратной связью для свёрточного кода со скоростью 1/3 Вместо вычисления метрик описанным выше способом, декодер с обратной связью в ДСК можно эффективно реализовать путём вычисления синдрома по принимаемой последовательности и используя табличный метод коррекции ошибок. Этот метод похож на тот, который был описан выше для декодирования блоковых кодов. Для некоторых свёрточных кодов декодер с обратной связью упрощается к виду, называемому логический декодер по большинству или пороговый декодер (Месси 1963; Хеллер 1975).
|