Учебно-методический комплекс дисциплины обсужден на заседании кафедры информационной безопасности «7»
|
Скачать 3.52 Mb.
|
Алгоритм декодирования ВитербиДля сверточных кодов разработаны алгоритмы синдромного, последовательного декодирования и декодирования по максимуму правдоподобия (алгоритм Витерби). На практике широко используется последний метод, что объясняется простотой реализации при небольших длинах кодового ограничения и получаемым выигрышем от кодирования. Алгоритм Витерби является рекуррентной процедурой, направленной на поиск пути по кодовой решетке, ближайшего к принимаемой последовательности. Как уже указывалось, декодирование по минимуму расстояния является оптимальным в канале с независимыми ошибками. Основные операции алгоритма поясним при декодировании кода примера 5.15. Пусть для простоты передается нулевое кодовое слово, а в канале произошла трехкратная ошибка, так что принятая последовательность имеет вид 10 10 00 00 10 00 ... 00 ... Результаты поиска ближайшего пути после приема 14 элементарных блоков показаны на рис. 5.12. Промежуточные этапы работы декодера при сделанных предположениях подробно рассмотрены в [3].  На правой части рисунка видны четыре пути, ведущие в каждый узел решетки. Рядом проставлены расстояния (меры расходимости) этих путей от принятой последовательности на отрезке из 14 блоков. Мера верхнего пути значительно меньше мер нижних. Поэтому можно предположить, что верхний путь наиболее вероятен. Однако декодер Витерби, не зная следующих фрагментов принимаемой последовательности, вынужден запомнить все четыре пути на время приема  элементарных блоков. Число  называется шириной окна декодирования. Понятно, что для уменьшения ошибки декодирования следует выбирать достаточно большим, в несколько раз превышающим длину блока, что, естественно, усложняет декодер. В данном случае  .Отметим, что тактика выбора и последующего анализа только одного пути с наименьшим расстоянием составляет сущность более экономного последовательного декодирования [3, 26]. На средней части рис. 5.12 видно, что все пути имеют общий отрезок и, следовательно, прием новых блоков не может повлиять на конфигурацию этого участка наиболее правдоподобного пути. Поэтому декодер уже может принимать решение о значении информационных символов, соответствующих этим элементарным блокам. Поскольку рассматриваемый отрезок составлен из верхних ребер кодовой решетки, то согласно правилу ее построения оценки информационных символов равны 0. Левая часть рисунка демонстрирует возможную ситуацию неисправляемой ошибки. Существует два пути с одинаковыми мерами расходимости. Декодер может разрешить эту неопределенность двумя способами. Отметить этот участок как недостоверный или принять одно из двух решений: информационная последовательность равна 00000... или 10100.... Очевидно, расширение окна декодирования не позволяет исправить такую ошибку. Ее исправление возможно при использовании кода с большей корректирующей способностью. Поступление из канала нового элементарного блока вызывает сдвиг картинки в окне декодирования влево. В результате левое ребро пути исчезает, а справа появляется новый столбец решетки, к узлам которого должны быть продолжены сохраненные пути от узлов предыдущего столбца. Для этого выполняются следующие операции. 1. Для каждого узла нового столбца вычисляются расстояния между принятым блоком и маркировкой ребер, ведущих в данный узел. 2. Полученные меры расходимости ребер суммируются с расстоянием путей, которые они продолжают. 3. Из двух возможных путей оставляется путь с меньшим расстоянием, а другой отбрасывается, так как следующие поступающие блоки не могут изменить соотношения расстояний этих путей. В случае равенства расстояний или случайно выбирается один путь, или сохраняются оба. Еще до открытия оптимального алгоритма Витерби, были придуманы другие алгоритмы для декодирования свёрточных кодов. Самым ранним был алгоритм последовательного декодирования, впервые предложенный Возенкрафтом и впоследствии модифицированный Фано (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. - Пример поиска пути при последовательном декодировании [Jordan (1966), © 1966 IЕЕЕ] Поскольку метрики неверного пути в среднем уменьшаются, метрика упадет ниже текущего порога, скажем  . Если это случится, декодер возвращается обратно и берёт альтернативный путь по дереву (решётке) с меньшей метрикой ветви, в попытке найти другой путь с большей метрикой, которая превосходит порог . Если приходит удача в альтернативном пути, это продолжается вдоль пути все время, и выбирается наиболее правдоподобная ветвь в каждом узле. С другой стороны, если не существует пути, который превышает порог , порог уменьшается на величину и декодер возвращается к первоначальному пути. Если первоначальный путь не находится выше нового порога, декодер начинает обратный поиск других путей. Эта процедура повторяется с уменьшением порога на при каждом повторении до тех пор, пока декодер не найдет путь, который остаётся выше установленного порога. Упрощённая структурная схема алгоритма Фано показана на рис. 8.2.18.Алгоритм последовательного декодирования требует буферную память в декодере для хранения поступающих данных декодирования в течение периодов, когда декодер ищет альтернативные пути. Когда поиск заканчивается, декодер должен быть в состоянии обрабатывать демодулированные символы достаточно быстро, чтобы освободить буфер для начала нового поиска. Иногда в течение экстремально длинных поисков буфер может переполниться. Это вызывает потерю данных, которые можно восстановить повторением потерянной информации. В этой связи мы хотим напомнить, что предельная скорость  имеет особый смысл при последовательном декодировании. Это скорость, выше которой среднее число операций декодирования на декодированный символ становится неограниченным и оно выражает предельную вычислительную скорость  . На практике последовательные декодеры обычно работают при скоростях, близких к .Алгоритм последовательного декодирования Фано успешно применяется в различных системах связи. Его качество по вероятности ошибки сравнимо с декодером Витерби. Однако по сравнению с декодером Витерби последовательное декодирование имеет значительно большую задержку декодирования. С другой стороны, последовательное декодирование требует меньше памяти, чем декодирование по Витерби, и, следовательно, оно является привлекательным для свёрточных кодов с большим кодовым ограничением.  Рисунок. 8.2 Упрощённая структура алгоритма Фано [Jordan (1966), © 1966 IЕЕЕ] Исследования вычислительной сложности и требований к памяти для последовательного декодирования вызывают интерес, и они все еще продолжаются. Для анализа этих вопросов и других характеристик алгоритмов Фано интересующемуся читателю рекомендуются книги Галлагера (1986), Возенкрафта и Джекобса (1965), Сэвейдж (1966) и Форни (1974). Другой тип алгоритма последовательного декодирования, названный стек-алгоритмом, был предложен независимо Зигангировым (1966) и Елинеком (1969). В противовес алгоритму Витерби, который сохраняет траектории  путей и соответствующих метрик, стек-алгоритм последовательного декодирования работает с несколькими путями и их соответствующими метриками. В стек-алгоритме более вероятные пути упорядочиваются согласно их метрик, причём в верхней части (в голове стека) располагается путь, имеющий наибольшую метрику. На каждом шаге алгоритма только путь в голове стека проверяется по разветвлению. Это приносит  продолжений и их соответствующих метрик. Эти продолжения вместе с другими путями затем упорядочиваются согласно величинам их метрик, и все пути с метриками, которые располагаются ниже некоторой выбранной величины от метрики главного пути, отбрасываются. Затем процесс продолжения путей с наибольшими метриками повторяется. Рис. 8.2.19 иллюстрирует несколько первых шагов стек-алгоритма.Очевидно, что если ни одно из продолжений пути с наибольшей метрикой не остаётся в голове стека, следующий шаг поиска выполняет продолжение другого пути, который приближается к голове стека. Отсюда следует, что алгоритм не всегда даёт быстрое продвижение по начатой траектории при любой итерации. Следовательно, некоторую величину памяти нужно зарезервировать для вновь принятых символов и ранее принятых символов для того, чтобы позволить алгоритму расширить поиск по одному из более коротких путей, когда такой путь достигает головы стека. Стек с накопленными метриками путей
Рисунок. 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). Вопросы для самопроверки:
Список литературы: 1. Шеннон К.Е. Математическая теория связи //Работы по теории информации и кибернетике. -М., 2006. С. 243-332. 2. Котельников В.А. Теория потенциальной помехоустойчивости. -M.-JL: Госэнергоиздат, 2005. 152 с. 3. Блох Э.Л., Зяблов В.В. Обобщенные каскадные коды М: Связь 1976. 240 с. 4. Зяблов В.В. и др. Высокоскоростная передача сообщений в реальных каналах /В.В. Зяблов, Д.Л. Коробков, С.Л. Портной. М.:Радио и связь, 1991. 228 с. 5. Помехоустойчивость и эффективность систем передачи информации /А. Г. Зюко, А. И. Фалько, И. П. Панфилов и др.; Под ред. Л. Г. Зюко. -М.: Радио и связь, 1985. 272 с. 6. Банкет В.Л., Дорофеев В.М. Цифровые методы в спутниковой связи. М.: Радио и связь, 1988. 240 с. 7. Колесник В. Д., Мирончиков Е. Т. Декодирование циклических кодов. -М.: Связь, 1968. 251 с. 8. Самойленко С.И., Давыдов А.А., Золотарев В.В., Третьякова Е.И. Вычислительные сети -М.: Наука, 1981. 9. Золотарев В.В. Использование помехоустойчивого кодирования в технике связи //Электросвязь, №9, 2004. С.7-10. 10. Ю.Золотарев В.В. Реальный энергетический выигрыш кодирования для спутниковых каналов //В кн.: 4-я Международная Конференция «Спутниковая связь ICSC-2000», Т.2, М.: МЦНТИ, 2000. С. 20-25. 11. Возенкрафт Дж., Джекобе И. Теоретические основы техники связи: Пер. с англ./Под ред. Р. Л. Добрушина. М.: Мир, 1969. 640 с. 12. Галлагер Р. Теория информации и надежная связь //Пер. с англ. под ред. М.С. Пинскера и Б.С. Цыбакова. М.: Сов. радио, 1974. 720 с. 13. Витерби А. Границы ошибок для сверточных кодов и асимптотически оптимальный алгоритм декодирования //Некоторые вопросы теории кодирования. М., 1970. С. 142-165. http://e.lanbook.com/books/element.php?pl1_cid=25&pl1_id=5133 |
Похожие:
 |
Учебно-методический комплекс дисциплины обсужден на заседании кафедры... Учебно-методический комплекс дисциплины составлен на основании требований государственного образовательного стандарта высшего профессионального... |
|
Учебно-методический комплекс дисциплины обсужден на заседании кафедры... Учебно-методический комплекс составлен в соответствии с требованиями государственного образовательного стандарта высшего профессионального... |
 |
Учебно-методический комплекс дисциплины обсужден на заседании кафедры... Защита информационных процессов в компьютерных системах 090104. 65 – Комплексная защита объектов информатизации Форма подготовки... |
|
Учебно-методический комплекс дисциплины Туризм, утвержденного приказом Министерства образования и науки РФ от 20. 01. 2006 г. №739гум/бак. Учебно-методический комплекс обсужден... |
|
Учебно-методический комплекс дисциплины «Формальности проживания в гостинице» Туризм, утвержденного приказом Министерства образования и науки РФ от 20. 01. 2006 г. №739гум/бак. Учебно-методический комплекс обсужден... |
|
Учебно-методический комплекс дисциплины обсужден на заседании кафедры... Учебно-методический комплекс составлен в соответствии с требованиями государственного образовательного стандарта высшего профессионального... |
|
Учебно-методический комплекс дисциплины обсужден на заседании кафедры... Учебно-методический комплекс составлен в соответствии с требованиями государственного образовательного стандарта высшего профессионального... |
|
Учебно-методический комплекс дисциплины обсужден на заседании кафедры «Финансы и кредит» Учебно-методический комплекс составлен в соответствии с требованиями государственного образовательного стандарта высшего профессионального... |
|
Учебно-методический комплекс дисциплины организация работы гостиниц 100200. 62 «Туризм» Туризм, утвержденного приказом Министерства образования и науки РФ от 20. 01. 2006 г. №739гум/бак. Учебно-методический комплекс обсужден... |
|
Учебно-методический комплекс дисциплины обсужден на заседании кафедры компьютерных систем «03» Учебно-методический комплекс составлен в соответствии с требованиями федерального государственного образовательного стандарта высшего... |
|
Учебно-методический комплекс дисциплины обсужден на заседании кафедры... Учебно-методический комплекс составлен в соответствии с требованиями федерального государственного образовательного стандарта высшего... |
|
Учебно-методический комплекс дисциплины обсужден на заседании кафедры... Учебно-методический комплекс составлен в соответствии с требованиями государственного стандарта высшего профессионального образования... |
|
Проект) (КР,КП), Расчётно-графическая работа (ргр) Домашнее задание... Учебно-методический комплекс дисциплины обсуждён и утверждён на заседании кафедры «Гидротехнические сооружения» |
|
Учебно-методический комплекс составлен на основании требований государственного... Учебно-методический комплекс дисциплины обсуждена на заседании кафедры Информационные системы управления «29» июня 2011 г |
|
Учебно-методический комплекс дисциплины материаловедение направление... Учебная программа обсуждена на заседании кафедры технологии и предпринимательства |
|
Учебно-методический комплекс Наименование дисциплины Аритмология... Переутверждено на заседании кафедры госпитальной хирургии с курсом детской хирургии |