Васин В.И. Информационные технологии в радиотехнических системах. Под ред. И.Б.Федорова (2003) (1151848), страница 116
Текст из файла (страница 116)
Помекоустойчивое кодирование и декодирование Начальное состояние ~ОО] [О2~ Я Я О ! 2 1l Такты Рис. 9.32. Решетчатая диаграмма для кода 1/2 с К = 3 Для пояснения процессов кодирования и декодирования часто используют решетчатую диаграмму, представляющую собой одно из возможных изображений кодового дерева. Такая диаграмма для кодера на рис. 9.32 состоит из узлов и ветвей (ребер). Число ветвей, исходящих из узла, равно основанию кода. Число узлов равно 2к '. Единичному символу сообщения приписываются штриховые линии, а нулевому — сплошные. Выходные символы записываются над ветвями. Надписи около узлов характеризуют логическое состояние кодирующего устройства. Каждой информационной последовательности символов соответствует определенный путь (определенная траектория) на диаграмме.
Кодовая последовательность формируется путем считывания комбинаций над ветвями при прослеживании данного пути. Соответственно, процесс кодирования заключается в выборе одного из путей диаграммы. Корректирующая способность сверточного кода зависит от так называемого свободного расстояния И„, которое, по существу, содержит ту же информацию о коде, что и кодовое расстояние для блочных кодов. Оно определяется как минимальный вес (минимальное число единиц) пути на решетчатой диаграмме, начинающегося и заканчивающегося в нулевом узле. Например, для кода ка/нс = 1/2, К = 3 имеем Н„= 5.
В табл. 9.1 приведены порождающие многочлены оптимальных сверточных кодов с относительной скоростью передачи 1/2 и кодовым ограничением длины 3...8, а также значения свободных расстояний этих кодов. 591 9. Радиотехнические системы передачи информации Таблица 9.1 Порождающие многочлены оптимальных сверточиых кодов Сверточные коды можно декодировать различными методами. Различают декодирование с вычислением и без вычисления проверочной последовательности. Декодирование с вычислением проверочной последовательности применяется только для систематических кодов.
Оно ничем не отличается от соответствующего метода декодирования блочных кодов. На приемной стороне из принятых информационных символов формируют проверочные символы по тому закону, что и на передающей стороне, которые затем сравнивают с принимаемыми проверочными символами.
В результате сравнения образуется проверочная последовательность, которая при отсутствии ошибок состоит из одних нулей. При наличии ошибок на определенных позициях последовательности появляются единичные символы. Закон формирования проверочных символов выбирается таким образом, чтобы по структуре проверочной последовательности можно было определить искаженные символы.
Декодирование по принципу максимума правдоподобия сводится к задаче отождествления принятой последовательности с одной из 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) состоит из синхронизатора, устройства управления и тактирования, устройства для вычисления мегрик ветвей, устройства для обновления и хранения метрик ветвей, устройства для обновления и хранения гипотетических информационных последовательностей и решающего устройства.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
