Прокис Дж. Цифровая связь (2000) (1151856), страница 90

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 90)

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

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

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

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

Для большей конкретности рассмотрим канал без памяти. Метрика для 1-го пути по дереву или решетке от первой ветви до В-й ветви можно выразить так (8.2.42) зы еы где (8.2.43) В (8,2 43) г,„,— выходная последовательность демодулятора, р(г,„,)с,'„~) означает условную ФПВ г,„, при условии кодового бита с,"„), (ш-й бит в )-й ветви г'-го пути), а л— положительная константа. Л выбирается, как сказано выше, так, что неправильные пути будут иметь уменьшающиеся метрики, в то время как правильный путь в среднем увеличивает метрику. Заметим, что член р(г,„,) в знаменателе не зависит от кодовой последовательности и, следовательно, может быть включен в постоянную, Метрика, определенная (8.2.43), в общем применима при декодировании как жестких, так и мягких решений.

Однако она может быть особенно упрощена, когда используется декодирование жестких решений. В частном случае, если мы имеем ДСК с переходной вероятностью ошибки р, метрика для каждого принятого символа, согласующаяся с формулой (8.2.43), определяется так В) (1о8,[2(1 — р)~ — Л,. при г,„, = с),,), ~1о8, 2р — 11, при г,„~ с)„') (8.2,44) г„,— выходы жестких решений демодулятора, с,.'„,— и-й кодовый символ в~-й ветви 1-го пути дерева, Л, — скорость кода. Заметим, что эти метрики требуют хотя бы приближенного знания вероятности ошибки р, Пример 8.2.6. Предположим, что для передачи информации по ДСК с вероятностью ошибки р = 0,1 используется двоичный сверточный код со скоростью А, = 1/3 .

Вычисление согласно (8.2.44) дает ~ О52 ~( — 2.65 И лМ РО7 г ~ с'). /Н! >П~' Яе 1бе (8.2.45) (г) Р,„= г =с", »а г ~ с~'. >пг рю' (8.2.46) Поскольку скорость кода равна 1/3, то кодер имеет три выходных символа на каждый входной символ. Тогда метрики ветвей, согласующиеся с (8.2.46), равны рь) =3-Ы > или, что эквивалентно, 14~') = 1 — 2с1, (8.2.47) где Ы вЂ” хеммингово расстояние трех принятых бит от трех битов на ветви. И Таким образом,,метрики ц,. просто связаны с расстоянием Хемминга между принимаемыми символами и кодовыми символами72й ветви 1-го пути, Первоначально декодер можно заставить выбирать правильную траекторию путем передачи известной цепочки данных.

Тогда он продвигается вперед от узла к узлу, выбирая наиболее вероятную (с большей метрикой) ветвь в каждом узле и увеличивая порог так, что его изменение никогда не больше, чем некоторая заранее выбранная величина, скажем, т. Теперь предположим, что аддитивный шум (при декодировании мягких решений) или ошибки демодуляции, возникающие из-за шума в канале (при декодировании жестких 429 Для упрощения расчетов метрики (8,2.45) можно нормировать. Они хорошо аппроксимируются так: 4 решений) заставят декодер принять неверный пугь, поскольку он кажется более правдоподобным, чем правильный путь. Это иллюстрирует рис.

8.2.17. 7в о М о о 4в О 2 4 б а 1О 12 14 1б 1а Поыор овв1волв Рис. ь'.2.17. Пример поиска пути при последовательиом декодироваиии ~3огдаа (196Г>), © 1966 УЕЕЕ! Поскольку метрики неверного пути в среднем уменьшаются, метрика упадет ниже текущего порога, скажем т,. Если это случится, декодер возвращается обратно и берет альтернативный путь по дереву (решетке) с меньшей метрикой ветви, в попытке найти другой путь с большей метрикой, которая превосходит порог т„.

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

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

Когда поиск заканчивается, декодер должен быть в состоянии обрабатывать демодулированные символы достаточно быстро, чтобы освободить буфер для начала нового поиска. Иногда в течение экстремально длинных поисков буфер может переполниться. Это вызывает потерю данных, которые можно восстановить повторением потерянной информации. В этой связи мы хотим напомнить, что предельная скорость 114 имеет особый смысл при последовательном декодировании. Это скорость, выше которой среднее число операций декодирования на декодированный символ становится НЕОГРаНИЧЕННЫМ И ОНО ВЫРа>КаЕт >>РИдСЛЫ1У>1> ПЫЧПСттЕЛЫ1У>О СКОРОСтЬ Явв.

На ПРахтИКЕ последовательные декодеры обычно работают при скоростях, близких к Ло. Алгоритм последовательного декодирования Фано успешно применяется в различных системах связи, Его качество по вероятности ошибки сравнимо с декодером Витерби. Однако по сравнению с декодером Витерби последовательное декодирование имеет значительно большую задержку декодирования. С другой стороны, последовательное декодирование требует меньше памяти, чем декодирование по Витерби, и, следовательно, оно является привлекательным для сверточных кодов с большим кодовым ограничением. Старт л =о ! з=о Ужеиьшип, порог иа з г ! ! ! 1 1 1 1 1 1 Хуже Проверь более праадоподобиуш ветвь Проаерь предшдущий узел Хуже 1 ! 1 Проаерь ! эту аетаь 1 Лучше Лучше Лучше Шаг иаэад Шаг епердд Имеется ли здесь более праадоподобпая аетаьу Перашй р:и у этого уэяа Г Да Да Увеличить порог иа з Рис.

8.2,18. Упрощенная структура алгоритма Фано ~3агг1ап (1966), © 1966 1ЕЕЕ1 43! Исследования вычислительной сложности и требований к памяти для последовательного декодирования вызывают интерес, и они все еще продолжаются. Для анализа этих вопросов и других характеристик алгоритмов Фано интересующемуся читателю рекомендуются книги Галлагера (1986), Возенкрафта и Джекобса (1965), Сэвейдж (1966) и Форни (1974). Другой тип алгоритма последовательного декодирования, названный санек-алгорилтмолб был предложен независимо Зигангировым (1966) и Елинеком (1969). В противовес алгоритму Витерби, который сохраняет траектории 2бс ""' путей и соответствующих метрик, стек-алгоритм последовательного декодирования работает с несколькими путями и их соответствующими метриками.

В стек-алгоритме более вероятные пути упорядочиваются согласно их метрик, причем в верхней части (в голове стека) располагается путь, имеющий наибольшую метрику. На каждом шаге алгоритма только путь в голове стека проверяется по разветвлению. Это приносит 2' продолжений и их соответствующих метрик. Эти 2" продолжения вместе с другими путями затем упорядочиваются согласно величинам их метрик, и все пути с метриками, которые располагаются ниже некоторой выбранной величины от метрики главного пути, отбрасываются. Затем процесс продолжения путей с наибольшими метриками повторяется.

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

ооо оть кода 1П ка ветви = 1-Ът' стояние Хемминта гр поспелова" тельиосттк 110 О!! Стек о накопленными метриками путе» Рис. 8.2.19. Пример работы стек-алгоритма для декодирования сверточиото кода со скоростью 1/3 Из сравнении стек-алгоритма с алгоритмом Витерби следует, что стек-алгоритм требует малого числа сравнений мегрик, но его вычислительная экономия в большой степени снижается за счет вычислений, требуемых для упорядочивания стека после каждой итерации. По сравнению с алгоритмом Фано, стек-алгоритм в вычислительном отношении проще, поскольку здесь нет возвращения по тому же пути, как это делает алгоритм Фано. С другой стороны, стек-алгоритм требует больше памяти, чем алгоритм Фано. Третья альтернатива оптимального декодера Витерби — это метод, названный декодированием с обратной связью (Хеллер 1975), который был разработан для декодирования в ДСК (декодирование жестких решений).

Характеристики

Список файлов книги