Вернер М. Основы кодирования (2004) (1151882), страница 34
Текст из файла (страница 34)
При этом, однако, предполагается согласование алгоритма декодирования и канала, и, поэтому, этотрезультат не может быть распространен на общий случай.Особый класс сверточных кодов образуют так называемые катастрофические сверточные коды. Они не пригодны для использования, так как приводят к катастрофическому размножению ошибок.Рассмотрим пример катастрофического кода, а заодно научимся распознавать класс катастрофических кодов.Пример: Катастрофический сверточный (2,1,2)-код.Пусть сверточный код задан следующими многочленамиgi(X) = l + .1. Постройте схему кодера;(4.57)242Глава 4- Сверточиые коды2. Постройте диаграмму состояний;3. Закодируйте нулевую последовательность, т.е{и[п}} = {0,0,0,...};.4. Закодируйте последовательность {«[ п ]} = {1,1,1,...};5. Предположим, что при передаче последовательности единицпроизошли ошибки в первом, втором и четвертом битах кодовой последовательности.
Как много ошибочных бит в информационной последовательности появится при декодировании?6. Как но диаграмме состояний можно определить, что код является катастрофическим?Решение/1.Рис. 4.11. Схема кодера сверточного (2,1,2)-кода.2.1/00Рис. 4.12. Диаграмма состояний сверточного (2,1,2)-кода.3.
Так как кодирование начинается из нулевого состояния и мывсе время в нем остаемся, кодовым словом будет нулевая последовательность.4. Информационной последовательности единиц соответствуетпоследовательность состояний[*)} = {So,Si,S3,S3,...},(4.58)4-5. Структура сверточных кодов 243,что приводит к кодовой последовательности{t»[n2]} = {1,1,0,1,0,0,0,0,...}.(4.59)5. Если первый, второй и четвертый биты в (4.59) приняты ошибочно как «0», то декодер примет решение, что была передана нулевая информационная последовательность.
Здесь мы имеем граничный случай - размножение ошибок.6. Признаком катастрофичности кода является появление «петли» в модифицированной диаграммые состояний, в которой соответствующие кодовые символы являются нулевыми. На диаграммесостояний рис. 4.12 при переходе из состояния 5з в состояние 5з вессоответствующих кодовых символов равен нулю.В заключении рассмотрим систематические сверточные коды.Эти коды используются достаточно редко, так как в них не достигается оптимальное свободное кодовое расстояние djTee.
Тем не менее, внекоторых приложениях, например, при треллисной модуляции, применение систематических сверточных кодов весьма желательно [12].Пример: Систематический сверточный (2,1,1)-код.Систематический код задан порождающими многочленамиSi = 1 и 92(Х)(4.60)= 1 + Х.1. Постройте схему кодера;2.
Постройте диаграмму состояний;3. Определите dfree с помощью весовой функции кода;4. Является ли код катастрофическим?Решение.1.•v,1Рис. 4.13. Схема кодера систематического сверточного(2,1,1)-кода.^244Глава 4- Сверточные коды2.1/11о/оо/(So)(sT) f i/io0/01Рис. 4.14. Диаграмма состояний систематического сверточного (2,1,1)-кода.3. Вычисление dfree с помощью весовой функции.НачальноесостояниеРис. 4.15. Модифицированная диаграмма состояний сверточного (2Д,2)-кода.Для состояний в узлах рис. 4.15 имеют место два равенстваZx= ID2JZe + IDJZl(4.61)Za= DJ-Zy.(4.62)Связь между входом и выходом определяется как( 4 6 3 )<и, следовательно, получаем весовую функциюT(I, D, J) = ID3J2(1= ID3J2+ IDJ + I2D2J2+ I3D3J3+ I2DAJ3J 4 + / 4 £ > 6 J5 + • • • .+ I3Db+ •••)=( 4 -64)Учитывая, что dfree определяется наименьшим показателем D в весовой функции, имеемdfree = 3.(4.65)4.
Код не является катастрофическим, так как единственная«петля» на модифицированной диаграмме состояний обладает весомIDJ и, следовательно, повышает вес кодовой последовательности наединицу.4-6. Декодирования по максимуму правдоподобия4.6. Декодирования по максимум/ правдоподобияДля декодирования сверточных кодов имеются две альтернативы:последовательное декодирование и алгоритм Витерби.Алготитмы последовательного декодирования - стек-алгоритмили алгоритм Фано могут рассматриваться как методы проб и ошибок при поиске правильного пути на кодовом дереве.
В ряде приложений использование последовательного декодирования может бытьвесьма эффективным. Для ознакомления с алгоритмами последовательного декодирования см. например, [о].В настоящее время для декодирования сверточных кодов используют, как правило, алгоритм Витерби, который является частнымслучаем динамического программирования. Динамическое программирование применяется при решении задач математической оптимизации. Одной из таких задач является, например, прокладка шоссейных дорог на местности.
В этой задаче требуется проложить дорогитаким образом, чтобы общая длина была бы минимальной. Аналогичная задача возникает при декодировании сообщений. Здесь рольместности играют состояния на сетевой диаграмме, а роль общейдлины пути берет на себя некоторая метрика. Идея алгоритма Витерби интуитивно возникает при внимательном рассмотрении сетевой диаграммы, поэтому, прежде всего рассмотрим пример, а затемзаймемся теоретическими обобщениями.Пример: Декодирование сверточного (3,1,2)-кода с использованием сетевой диаграммы.Исходным пунктом декодирования служит сетевая диаграммарис.
4.8. Мы предполагаем, что кодирование начинается и заканчивается в состоянии So- Поиск альтернативных кодовых последовательностей сводится к поиску альтернативных путей на- сетевойдиаграмме (рис. 4.16.).Предположим, что в канале не произошло ошибок, тогда на декодер поступает кодовая последовательность{r[n}} = {v[n}} = {1,1,1,0,1,0,1,1,0,0,1,1,1,1,1,1,0,1,0,1,1}.(4.66)Каким образом декодер может определить, какая последовательностьбыла передана?Декодер сравнивает биты принятой последовательности с битамивозможных кодовых последовательностей и выбирает из всех кодовых последовательностей ту, которая наиболее «похожа» на принятую. Для независимых ошибок в канале мерой «похожести» являетсярасстояние Хэмминга.,246Глава 4- Сверточные кодыРис.
4.16. Сетевая диаграмма сверточного (3,1,2)-кодера,соответствующая (4.36).Сравнение расстояний Хэмминга всех кодовых последовательностей может быть эффективно реализовано с помощью сетевой диаграммы. На рис. 4.17 показан алгоритм декодирования и его результаты.ITinwno 2111Oilууу\по/° г л / т / . т Л пп \03 1 О I 2 Too] 2 I 1001 2НачальноесостояниеП у г ьПринятыйшвектороКонецДекодированная щ = 1последовательностьоюмоЧ-Оон16 Такт7Рис.
4.17. Сетевая диаграмма декодера.На нервом шаге возможны два пути из нулевого состояния ^оДекодер, прежде всего, сравнивает принятую тройку бит с тройками бит двух возможных путей. Найденные при этом расстоянияХэмминга являются метриками этих путей. Так как один путь ве-4-6. Декодирования по максимуму правдоподобиядет в состояние So, а второй в состояние S\, в текущих регистрахметрик состояний So и Si записываются метрики соответствующихим путей (см. рис. 4.17).
Одновременно в текущие регистры путейзаписываются первые разряды соответствующих информационныхпоследовательностей («О» - для So и «1» Si).На втором шаге декодирования из каждого состояния (So и Si)также возможны два перехода. Декодер прибавляет новые расстояния Хэмминга к текущим метрикам прежних состояний So и Si. Полученные таким образом новые метрики заносятся в регистры метрик новых состояний So, Si и S2, S3. В регистры путей этих состояний заносятся соответствующие им теперь уже вторые информационные разряды.
В конце второго шага декодирования все возможныесостояния сетевой диаграммы оказываются достигнутыми.ПредыдущеесостояниеМетрика0Путь11Метрика5Путь01ПоследующеесостояниеНакопленная0+3=3ПриращениеУ5+2=7Метрикаmin3 - -*" метрика111Продолжение. путиВыбор пути снаименьшейметрикойР и с . 4 . 1 8 . Выбор пути с наилучшей метрикой.На третьем шаге декодирования производится аналогичная процедура.
Здесь, однако, впервые оказывается, что в каждое новое состояние ведут два пути. Вот тут то и раскрывается сущность динамического программирования. В качестве примера на рис. 4.18 рассмотрена процедура декодирования нового состояния S3. В новое состояние S3 могут переходить два прежних состояния Si и S3 с приращениями метрик, равными 2 и 3 соответственно. С учетом прежнихзначений, новые метрики путей равны: от состояния Si - 7 и от состояния S3 - 3, поэтому, на третьем шаге декодирования, в качествепредшествующего новому состоянию S3, мы выбираем прежнее состояние Ss- Метрику нового состояния S3 полагаем равной трем и,в качестве третьего информационного разряда, выбираем бит перехода S3 —> S3, равный «1». Дальнейшее приращение метрик путей,выходящих из состояния S3, не зависят от метрики S3, накопленнойна третьем шаге, поэтому, на третьем шаге декодирования, мы мо-Глава 4- Свертпочные кодыжем смело отбросить переход Si —> S3, как обладающий большейметрикой, чем переход S3 —> S3.Таким образом, сущность динамического программирования заключается в том, что на каждом шаге декодирования но сетевой диаграмме для каждого состояния мы выбираем единственный, втекающий в него путь с минимальной метрикой (в случае равных метриквыбор одного из двух путей осуществляется произвольно).Дальнейшие шаги декодирования производятся аналогично.
Припрактической реализации процесс декодирования в данном примереможно существенно упростить. Из рис. 4.7 видно, что уже на третьем шаге всем состояниям предшествует первый бит информационной последовательности, равный «1», поэтому, первый информационный символ уже можно выдать потребителю и в дальнейшем неучитывать. Таким образом снижается длина регистров пути декодера и уменьшается время задержки декодирования. Окончательно, на7-ом шаге декодирования мы выбираем в состоянии So путь, обладающий наименьшей метрикой.
Содержимое регистра пути состояния"So дописывается к ранее продекодированным информационным символам и, тем самым, процесс декодирования заканчивается.Рассмотренный пример раскрывает основы алгоритма Витерби.Процесс декодирования по максимуму правдоподобия обобщает рис.4.19.
Для наглядной интерпретации представим кодовую последовательность в виде вектора v = (VQ, VI,I>2, •..).л нформацион ноеКодовоесловоСверточный! словоUVкодер1Кодирование-* Отображение 2*возможных двоичныхинформационных слов и длины N в2" возможных кодовых слов vПринятое~~Декодер~сверточногоДекодированноесловоДекодированние по максимуму правдоподобия-» Выбор наиболее вероятногокодового слова из 2" возможных 'при известном принятом слове гР и с . 4.19. Декодирование по максимуму правдоподобия.Задачу декодера максимального правдоподобия (МП) можно сформулировать следующим образом: имея принятый вектор г из всехвозможных слов v, принадлежащих коду, выбрать такое v, для которогоP(r/v)=maxP(r/y).(4.67)Решение задачи декодирования по МП зависит от выбранной модели канала.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
