Васин В.И. Информационные технологии в радиотехнических системах. Под ред. И.Б.Федорова (2003) (1092038), страница 116

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

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

При наличии ошибок на определенных позициях последовательности появляются единичные символы. Закон формирования проверочных символов выбирается таким образом, чтобы по структуре проверочной последовательности можно было определить искаженные символы. Декодирование по принципу максимума правдоподобия сводится к задаче отождествления принятой последовательности с одной из 2 возможных, где Ю вЂ” длина информационной последовательности. Решение принимается в пользу той кодовой последовательности, которая в меньшем количестве позиций отличается от принятой. Метод применим для любого сверточного кода.

Однако при больших значениях Ф он практически не реализуем из-за необходимости перебора 2 возможных кодовых последовательностей. Существенное упрощение процедуры декодирования по максимуму правдоподобия предложил А. Витерби 1131. Характерной особенностью 592 9.5. //омехоустойчивое кодирование и декодирование его метода является то, что на каждом шаге декодирования запоминается только 2» ' наиболее правдоподобных путей, Осуществляется это следующим образом. Для определенности будем рассматривать код Ып, = 1/2. Пусть начальное состояние кодирующего устройства известно. Из анализа решетчатой диаграммы следует, что в любой 1-й узел на любом 1-м такте из начального состояния ведут несколько путей, которым соответствуют определенные кодовые последовательности. Из всех путей выберем тот, которому соответствует кодовая последовательность В;(1), отличающаяся от принятой В(!) меньшим числом символов.

Этот путь называется выжившим. Обозначим расстояние Хэмминга между последовательностями В;(1) и В(1) через ас(!). Припишем с-му узлу вес, равный с/с(1). Подобную процедуру проделаем для всех остальных узлов. Возьмем любой /с-й узел решетчатой диаграммы в следующий тактовый момент. Он связан с двумя предшествующими узлами, например с 1-м и /'-м, ветвями Й и //с соответственно (см. рис. 9.32).

Для нахождения правильного пути в узел /с вычислим величины с/с(1) + Лс/я и сЦ/) + Лф„где Л4» и Лад — приращения расстояний Хэмминга при продолжении путей В(!) и В/(!) в узел /с Эти приращения находятся по принятому на (1+ 1)-м шаге сегменту последовательности и символам, соответствующим ветвям Й и //с. Если с/(1)+ Лс/я < ф/) + Лс/м то ветвь Й считается истинной и записывается в память декодирующего устройства.

Ветвь //с и все ей предшествующие отбрасываются. Аналогичные операции проделывают и для остальных узлов. В результате на (1 + 1)-м шаге в памяти декодируюшего устройства будет храниться 2 ' путей. Исследования показывают [13), что через /в = 5К тактов в кодовом дереве остается лишь один путь с минимальным весом. Поэтому решение о том, какое сообщение передавалось в некоторый (ос + 1)-й тактовый момент, можно принимать на (ос + 1о)-м такте.

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

Пусть используется ранее рассмотренный код /св/не = 1/2 при К = 3, с/~(х) = 1 Ю х н с/,(х) = 1 О+ х 9 х . Предположим, что передавалась нулевая последовательность, а принятая последовательность имеет вид 10 00 10 00 00 .... Работу декодера иллюстрируют диаграммы (рис. 9.33, а — д), где числа в узлах характеризуют значения с/,(1). На 3-м такте работы декодера (рнс. 9.33, б) каждый из путей, «выживших» на предыдущем такте (рис. 9.33, а), раздваивается. Общее число путей становится равным 8.

Декодер сравнивает метрики для пар путей, ведущих в каждый узел, и нз каждой пары оставляет лишь лучший. Вновь 593 9. Радиотехнические системы передачи информации 1 1 1 1 2 1 1 2 2 2 2 2 2 2 2 1 1 2 2 2 1 1 2 2 2 2 2 2 2 Рис. 933. Диаграмма декодирования исправляемой (а — д) и неисправляемой (лс — з) комбинаций ошибок с помощью алгоритма Витерби число путей оказывается равным 4. Этот процесс повторяется при каждом приеме новой ветви (рис. 9.33, в, г, д).

Заметим, что на 5-м такте (см. рис. 9.33, в) метрика нулевого пути оказывается наилучшей. «Выживающие» пути могут отличаться друг от друга в течение многих тактов. Однако на 10-м такте (см. рис. 9.33, д) первые восемь ветвей всех «выживших» путей совпадают. В этот момент согласно алгоритму Витерби принимается решение о переданных символах, так как все «выжившие» пути приходят из одного узла. Глубина (число тактов), на которой происходит слияние путей, является случайной величиной, зависящей от ошибок в принятой последовательности, и заранее не может быть вычислена.

Поэтому обычно устанавливают некоторую фиксированную глубину декодирования. При этом каждый Раз, обрабатывая новую ветвь, декодер выдает самый старый символ «выжившего» пути с наилучшей метрикой. В рассмотренном случае принятая последовательность содержала два ошибочных символа, а код имел свободное расстояние, равное 5, что позволило ему исправить эти ошибки. Предположим, что принятая последовательность содержит 3 ошибочных символа и имеет вид 11 01 00 00 .... Такая комбинация ошибок оказывается неисправляемой. Заметим, что на 3-м 594 9.5.

Памекоустойчивое кодирование и декодирование Устройство управления и тактирования Устройство обновления и хранения информационных последова- тельностей Устройство вычисления и хранения метрик ветвей Устройство вычисления метрики ветвей Выходное решающее устройство Выход Вход Синхрони- затор Рис. 9.34. Структурная схема декодера, реализующего алгоритм Витербн 595 такте (рис. 9.33, е) удаляется правильный путь, что неизбежно приводит к ошибке.

Кроме того, все «выжившие» нуги имеют одну и ту же первую ветвь. На 5-м такте все выжившие пути имеют одинаковые первые две ветви (рис. 9,33, ж), а на 11-м такте — первые девять ветвей (рис. 9.33, з). Хотя при декодировании возникла ошибка, выбранный ошибочный пугь отличается от правильного лишь на коротком отрезке, состоящем из трех ветвей, Информационная последовательность, соответствующая выбранному пути, имеет вид 1000, ..., т. е. содержит один ошибочный символ.

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

Так, исследования показывают, что применение сверточных кодов с К = 3, 5 и 7 при фиксированной вероятности ошибки Р = 10 ' позволяет получить энергетический выигрыш 4...6 дБ по сравнению с системой, использующей ФМ сигналы без кодирования. Важным преимуществом по сравнению с методом последовательного декодирования является фиксация числа вычислительных операций на один декодированный символ. Декодирование по методу Витерби особенно перспективно в каналах с независимыми ошибками. Декодер Витерби (рис. 9.34) состоит из синхронизатора, устройства управления и тактирования, устройства для вычисления мегрик ветвей, устройства для обновления и хранения метрик ветвей, устройства для обновления и хранения гипотетических информационных последовательностей и решающего устройства.

Устройство хранения и обновления метрик путей осуществляет сложение метрик ветвей с хранящимися метриками путей, проделывает необходимые сравнения и запоминает новые метрики путей. Устройство хранения и обновления гипотетических информационных последовательностей может быть выполнено на сдвигающих регистрах, в 9. Радиотехнические системы передачи информации каждом из которых хранится полная информационная последовательность символов, соответствующая одному из «выживших» путей.

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

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

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