Прокис Дж. - Цифровая связь (1266501), страница 88
Текст из файла (страница 88)
просто связаны с расстоянием Хемминга между ) б (ю) ; принимаемыми символами и кодовыми символами у-й ветви 1-го пути. П ервоначально декодер можно заставить выбирать правильную траекторию путем .-, передачи известной цепочки данных. Тогда он продвигается вперед от узла к узлу, выбирая : наиболее вероятную (с большей метрикой) ветвь в каждом узле и увеличивая порог так, что его изменение никогда не больше, чем некоторая заранее выбранная величина, скажем, . ь Теперь предположим, что алдитивный шум (при декодировании мягких решений) или '.;. ошибки демодуляции, возникающие из-за шума в канале (при декодировании жестких решений) заставят декодер принять неверньш путь, поскольку он кажется более правдоподобным, чем правильный путь. Это иллюстрирует рис.
8.2.17. а 2 4 6 Х !а 12 1Л м !Х !Ьп рлпн~ол:1 Рис. К 2.17. Пример поиски п> тп прн послеаавлтельпои лоюлпроваппп ~.Ант/пи (1966) © 1966 Л;И) Поскольку метрики неверного пути в среднем уменьшаются, метрика упадет ш1же текущего порога, скажем т„. Если это случится, декодер возвращается обратно и бере~ альтернативный путь по дереву 1решетке) с меньшей метрикой ветви, в попытке найти другой путь с большей метрикой, которая превосходит порог т„. Если приходит удача в альтернативном пути, это продолжается вдоль пути все время, и выбирается наиболее правдоподобная ветвь в каждом узле. С другой стороны, если не существует нуги, который превышает порог т„, порог уменьшается на величину т и декодер возвращается к первоначальному пути.
Если первоначальный путь не находится выше нового порога, декодер начинает обратный поиск других путей. Эта процедура повторяется с уменьшением порога на т при каждом повторении до тех пор, пока декодер не найдет путь, который остается выше установленного порога. Упрощенная структурная схема алгоритма Фано показана на рис. 8.2.18, Алгоритм последовательного декодирования требует буферную память в декодере для хранения поступающих данных декодирования в течение периодов, когда декодер ищет альтернативные пути. Когда поиск заканчивается, декодер должен быть в состоянии обрабатывать демодулированные символы достаточно быстро, чтобы освободить буфер для начала нового поиска.
Иногда в течение экстремально длинных поисков буфер может переполниться. Это вызывает потерю данных, которые можно восстановить повторением потерянной информации. В этой связи мы хотим напомнить, что предельная скорость Л, имеет особый смысл при последовательном декодировании. Это скорость, выше которой среднее число операций декодирования на декодированный символ становится неограниченным и оно выражает прес)ельи19о ьычпс.лллсльп)вв скоуюсшь Л„„. На практике последовательные декодеры обычно работают при скоростях, близких к Л„.
Алгоритм последовательного декодирования Фано успешно применяется в различных системах'связи. Его качество по вероятности ошибки сравнимо с декодером Витерби. Однако по сравнению с декодером Витерби последовательное декодирование имеет значительно большую задержку декодирования. С другой стороны, последовательное декодирование требует меньше памяти, чем декодирование по Витерби, и, следовательно, оно является привлекательным для сверточных кодов с большим кодовым ограничением.
4 1(1 Рнс. 8.2.18. Унрощеннаа структура аагорнтма Фана 1)он!он (1966), © 196(> ИК1'.1 Исследования вычислительной сложности и требований к памяти для последовательного декодирования вызывают интерес, и они все еще продолжаются. Для анализа этих вопросов и других характеристик алгоритмов Фано интересующемуся читателю рекомендуются книги Галлагера (1986), Возенкрафта и Джекобса (1965), Сэвейдж (1966) и Форин (1974). Другой тип алгоритма последовательного декодирования, названный снеек-алгорнтзтом, был предложен независимо Зигангировым (1966) и Елинеком (1969).
В противовес алгоритму Витерби, который сохраняет траектории 2сс ' " путей и соответствующих метрик, стек-алгоритм последовательного декодирования работает с несколькими путями и их соответствующими метриками. В стек-алгоритме более вероятные пути упорядочиваются согласно их метрик, причем в верхней части (в голове стека) располагается путь, имеющий наибольшую метрику.
На каждом шаге алгоритма только путь в голове стека проверяется по разветвлению. Это приносит 2' продолжений и нх соответствующих метрик. Эти 2' продолжения вместе с другимн путями затем упорядочиваются согласно величинам их метрик, и все пути с метриками, которые располагаются ниже некоторой выбранной величины от метрики главного пути, отбрасываются. Затем процесс продолжения путей с наибольшими метриками повторяется.
Рис. 8.2.19 иллюстрирует несколько первых шагов стек-алгоритма. Очевидно, что если ни одно из 2" продолжений пути с наибольшей метрикой не :- остается в голове стека, следующий шаг поиска выполняет продолжение другого пути, который приближается к голове стека. Отсюда следует, что алгоритм не всегда дает : быстрое продвижение по начатой траектории при любой итерации. Следовательно, : некоторую величину памяти нужно зарезервировать для вновь принятых символов и ранее : принятых символов для того, чтобы позволить алгоритму расширить поиск по одному из Голее коротких путей, когда такой путь достигает головы стека.
431 ооо ад ь вада 1 3 ы астап 1-тс! сыкиис Хсмм инга ппсисдсва- 101 110 О!1 П1 Стск с г!амгииспгпами агстрикаа!и пугай Рис. 8.2, 19. Г1рииер работы стек-алгоритма дла декодирования сварточиого кода со скоростью 1/3 Из сравнении стек-алгоритма с алгоритмом Витерби следует, что стек-алгоритм требует малого числа сравнений метрик, но его вычислительная зкономия в большой степени снижается за счет вычислений, требуемых для упорядочивания стека после каждой итерации.
По сравнению с алгоритмом Фано, стек-алгоритм в вычислительном отношении проще, поскольку здесь нет возвращения по тому же пути, как это делает алгоритм Фано. С другой стороны, стек-алгоритм требует больше памяти, чем алгоритм Фано. Третья альтернатива оптимального декодера Витерби — это метод, названный декодированием с обратной связью (Хеллер 1975), который был разработан для декодирования в ДСК (декодирование жестких решений). При декодировании с обратной связью декодер делает жесткое решение об информационном символе на ~-м шаге. основываясь на метриках, вычисленных от 1-го до (!+и!)-го шага, где и! — выбранное целое число.
Таким образом, решение об информационном символе в пользу О или ! зависит от того, каково минимальное расстояние по Хеммингу для пути, который начинается на 1-ы шаге и кончается на Ц+л!)-м шаге и сколько содержится «0» или «1» в ветви, исходящих от шага у. Решение выносится один раз об информационном символе на у шаге, и только часть дерева, которая связана с этим символом, сохраняется (половина путей, исходящих из узла у), а остальные пути исключаются.
Так осуществляется обратная связь в декодере. Следующий шаг заключается в расширении части дерева, которая вышла до шагау+1+и и Пример 8.2.7. Рассмотрим использование декодера с обратной связью для сверточного када са скоростью !/3, показанного на рис. 8.2.2. Рис. 8.2.20 иллюстрирует древовидную диаграмму и операции декодера с обратной связью при и=2. Это значит, что при декодировании символа ветви 1, декодер рассматривает луги на ветвях1', 1+1 ну+2. Начиная с первой ветви, декодер рассчитывает восемь метрик (расстояние Хемминга) и решает, чта символ в первой ветви является О, если путь с минимальным расстоянием находится в верхней части дерева и, что символ 1, если пугь с минимальным расстоянием находится в нижней части дерева. В этом примере принимаемая последовательность для первых трех ветвей полагается такой 101 ! 11 110, поэтому путь с минимальным расстоянием находится в верхней части дерева, следовательно, первый выход символа декодера О.
Следующие шаги сводятся к расширению верхней части дерева (тай части дерева, которая выжила) на одну ветвь и к вычислению восьми метрик в ветвях 2, 3 и 4, Для предположения входной последовательности 111 110 О11 путь с минимальным расстоянием находится в нижней части секции дерева, вычислившей после первого шага. Итак, второй выходной символ декодера 1. Третий шаг заключается в расширении этой ишкней части дерева и повторении процедуры, описанной для двух первых шагов.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
