Помехоустойчивое кодирование и декодирование (1151930), страница 5
Текст из файла (страница 5)
9.31. Схема СПИ при использовании прозрачных сверточных кодовчто приводит к увеличениювероятностиошибок.Нетрудно показать, что сверточный код будет прозрачным, если каждый его порождающий многочленсодержит нечетное число членов.Помимо рассмотренного способа задания сверточного кода, возможны и другие. В частности, выходныесимволы можно рассматривать как свертку импульсной характеристики кодера с информационнойпоследовательностью (отсюда происходит название кода).Для пояснения процессов кодирования и декодирования часто используют решетчатую диаграмму,представляющую собой одно из возможных изображений кодового дерева. Такая диаграмма для кодера на рис.9.32 состоит из узлов и ветвей (ребер). Число ветвей, исходящих из узла, равно основанию кода.
Число узлов равно2K–1. Единичному символу сообщения приписываются штриховые линии, а нулевому — сплошные. Выходныесимволы записываются над ветвями. Надписи около узлов характеризуют логическое состояние кодирующегоустройства. Каждой информационной последовательности символов соответствует определенный путь(определенная траектория) на диаграмме. Кодовая последовательность формируется путем считываниякомбинаций над ветвями при прослеживании данного пути. Соответственно, процесс кодирования заключается ввыборе одного из путей диаграммы.Корректирующая способность сверточного кода зависит от так называемого свободного расстояния dсв,которое, по существу, содержит ту же информацию о коде, что и кодовое расстояние для блочных кодов.
Оноопределяется как минимальный вес (минимальное число единиц) пути на решетчатой диаграмме,начинающегося и заканчивающегося в нулевом узле. Например, для кода k0/n0 = 1/2, K = 3 имеем dсв = 5.В табл. 9.1 приведены порождающие многочлены оптимальных сверточных кодов с относительнойскоростью передачи 1/2 и кодовым ограничением длины 3…8, а также значения свободных расстояний этихкодов.Таблица 9.1Длина кодовогоограничения345678Порождающие многочленыq1(x) = 1 x x2q2(x) = 1 x2q1(x) = 1 x x2 x3q2(x) = 1 x x3q1(x) = 1 x x2 x4q2(x) = 1 x3 x4q1(x) = 1 x x2 x4 x5q2(x) = 1 x x5q1(x) = 1 x x2 x3 x6q2(x) = 1 x2 x3 x5 x6q1(x) = 1 x x2 x3 x4 x7q2(x) = 1 x2 x5 x6 x7Свободное расстояние56781010Сверточные коды можно декодировать различными методами.
Различают декодирование свычислением и без вычисления проверочной последовательности.Декодирование с вычислением проверочной последовательности применяется только длясистематических кодов. Оно ничем не отличается от соответствующего метода декодирования блочных кодов.На приемной стороне из принятых информационных символов формируют проверочные символы по томузакону, что и на передающей стороне, которые затем сравнивают с принимаемыми проверочными символами. Врезультате сравнения образуется проверочная последовательность, которая при отсутствии ошибок состоит изодних нулей. При наличии ошибок на определенных позициях последовательности появляются единичныесимволы.
Закон формирования проверочных символов выбирается таким образом, чтобы по структурепроверочной последовательности можно было определить искаженные символы.Декодирование по принципу максимума правдоподобия сводится к задаче отождествления принятойпоследовательности с одной из 2N возможных, где N — длина информационной последовательности.
Решениепринимается в пользу той кодовой последовательности, которая в меньшем количестве позиций отличается отпринятой. Метод применим для любого сверточного кода. Однако при больших значениях N он практическине реализуем из-за необходимости перебора 2N возможных кодовых последовательностей.
Существенноеупрощение процедуры декодирования по максимуму правдоподобия предложил А. Витерби [13]. Характернойособенностью его метода является то, что на каждом шаге декодирования запоминается только 2K–1 наиболееправдоподобных путей. Осуществляется это следующим образом. Для определенности будем рассматриватькод k0/n0 = 1/2.Пусть начальное состояние кодирующего устройства известно. Из анализа решетчатой диаграммыследует, что в любой i-й узел на любом l-м такте из начального состояния ведут несколько путей, которымсоответствуют определенные кодовые последовательности.
Из всех путей выберем тот, которомусоответствует кодовая последовательность Bi (l ), отличающаяся от принятой B% (l ) меньшим числом символов.Этот путь называется выжившим. Обозначим расстояние Хэмминга между последовательностями Вi(l ) и B% (l )через di(l ). Припишем i-му узлу вес, равный di (l ). Подобную процедуру проделаем для всех остальных узлов.Возьмем любой k-й узел решетчатой диаграммы в следующий тактовый момент. Он связан с двумяпредшествующими узлами, например с i-м и j-м, ветвями ik и jk соответственно (см.
рис. 9.32). Длянахождения правильного пути в узел k вычислим величины di (l ) + Δdik и dj (l ) + Δdjk, где Δdik и Δdjk —приращения расстояний Хэмминга при продолжении путей Bi(l ) и Bj(l ) в узел k. Эти приращения находятся попринятому на (l + 1)-м шаге сегменту последовательности и символам, соответствующим ветвям ik и jk. Еслиdi(l ) + Δdik < dj(l ) + Δdjk, то ветвь ik считается истинной и записывается в память декодирующего устройства.Ветвь jk и все ей предшествующие отбрасываются. Аналогичные операции проделывают и для остальныхузлов.
В результате на (l + 1)-м шаге в памяти декодирующего устройства будет храниться 2K–1 путей.Исследования показывают [13], что через l0 ≈ 5K тактов в кодовом дереве остается лишь один путь сминимальным весом. Поэтому решение о том, какое сообщение передавалось в некоторый (m + 1)-й тактовыйН а ч ал ьн о е с о с то я н и емомент, можно принимать на0000000000(m + l0)-мтакте.Для00уменьшенияобъемапамяти1111111111декодирующегоустройстваотрезки, по которым приняты11111101решения, стираются. Для000000этого же из весов всех узлов01010101кодовогодеревапериодическивычитают1010101010минимальный на данном101010такте вес.010101Для пояснения работы11декодера,реализующего012345алгоритмВитерби,рассмотримследующийТ ак тыпример. Пусть используетсяранеерассмотренный код k0/n0Рис.
9.32. Решетчатая диаграмма для кода 1/2 с K = 3= 1/2 при K = 3, q1(x) = 1 x2и q2(x) = 1 x x2.Предположим, что передавалась нулевая последовательность, а принятая последовательность имеет вид 10 0010 00 00 … . Работу декодера иллюстрируют диаграммы (рис. 9.33, а—д), где числа в узлах характеризуютзначения di (l ).На 3-м такте работы декодера (см. рис. 9.33, б) каждый из путей, «выживших» на предыдущем такте(см. рис. 9.33, а), раздваивается. Общее число путей становится равным 8. Декодер сравнивает метрики дляпар путей, ведущих в каждый узел, и из каждой пары оставляет лишь лучший.
Вновь число путей оказываетсяравным 4. Этот процесс повторяется при каждом приеме новой ветви (см. рис. 9.33, в, г, д). Заметим, что на 5-мтакте (см. рис. 9.33, в) метрика нулевого пути оказывается наилучшей.«Выживающие» пути могутотличаться друг от друга втечение многих тактов. Однако на10-м такте (см. рис.
9.33, д)первые восемь ветвей всех«выживших» путей совпадают. Вэтот момент, согласно алгоритмуВитерби, принимается решение опереданных символах, так как все«выжившие» пути приходят изодного узла.Глубина (число тактов), накоторойпроисходитслияниепутей,являетсяслучайнойвеличиной, зависящей от ошибокв принятой последовательности, изаранее не может быть вычислена.Поэтому обычно устанавливаютнекоторуюфиксированнуюглубину декодирования.
При этомРис. 9.33. Диаграмма декодирования исправляемой (а—д) икаждый раз, обрабатывая новуюнеисправляемой (ж—з) комбинаций ошибок с помощью алгоритмаветвь, декодер выдает самыйВитербистарый символ «выжившего» путис наилучшей метрикой.В рассмотренном случае принятая последовательность содержала два ошибочных символа, а код имелсвободное расстояние, равное 5, что позволило ему исправить эти ошибки. Предположим, что принятаяпоследовательность содержит 3 ошибочных символа и имеет вид 11 01 00 00 … . Такая комбинация ошибококазывается неисправляемой.
Заметим, что на 3-м такте (рис. 9.33, е) удаляется правильный путь, чтонеизбежно приводит к ошибке. Кроме того, все «выжившие» пути имеют одну и ту же первую ветвь. На 5-мтакте все выжившие пути имеют одинаковые первые две ветви (рис. 9.33, ж), а на 11-м такте — первые девятьветвей (рис. 9.33, з). Хотя при декодировании возникла ошибка, выбранный ошибочный путь отличается отправильного лишь на коротком отрезке, состоящем из трех ветвей. Информационная последовательность,соответствующая выбранному пути, имеет вид 1000, ..., т. е.
содержит один ошибочный символ.Рассмотренный пример описывает типичное поведение ошибочных последовательностей при использованииалгоритма сверточного декодирования Витерби.Алгоритм Витерби обладает рядом преимуществ. При небольших значениях длины кодовогоограничения декодирующее устройство оказывается достаточно простым, реализуя, в то же время, высокуюпомехоустойчивость. Так, исследования показывают, что применение сверточных кодов с K = 3, 5 и 7 прификсированной вероятности ошибки Pош = 10–5 позволяет получить энергетический выигрыш 4…6 дБ посравнениюссистемой,использующей ФМ-сигналыбез кодирования. Важнымпреимуществомпосравнениюсметодомпоследовательногодекодированияявляетсяфиксациячиславычислительных операций наодиндекодированныйсимвол.ДекодированиепоРис.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
