Скляр Б. Цифровая связь (2003) (1151859), страница 92
Текст из файла (страница 92)
Такие устройства часто описываются с помощью матричного генератора бесконечного порядка [6). Отметим, что в рассмотренном выше примере входной последовательности из 3 бит и последовательности на выходе из 10 бит эффективная стелень кодирования составляет й1н = 3/1О, что значительно меньше величины 1/2, которую можно было бы ожидать, зная, что каждый бит данных на входе порождает пару канальных битов на выходе. Причина этого заключается в том, что финальные биты данных нужно провести через кодер. Все канальные биты на выходе требуются в процессе декодирования. Если бы сообщение было длиннее, скажем 300 бит, последовательность кодовых слов на выходе содержала бы 640 бит и значение для степени кодирования кода 300/640 было бы значительно ближе к 1/2.
можно записать полиномиальный генератор я,(х) для верхних связей и я,(Х)— для нижних. й,(Х) =1+Х+Х' йг(Х) = 1+Х Здесь слагаемое самого нижнего порядка в полиноме соответствует входному разряду регистра. Выходная последовательность находится следуюшим образом: ЩХ) = гп(Х)й,(Х) чередуется с го(Х)аг(Х). Прежде всего, выразим вектор сообшения ш =101 в виде полинома, т.е.
ш(Х) = 1+ Х~. Для очистки регистра мы снова будем предполагать использование нулей, следующих за битами сообщения. Тогда выходяший полином ЩХ), или выходящая последовательность () кодера (рис. 7.3) для входного сообшения ш может быть найдена следуюшим образом: ш(х)й,(Х) = ().ьх')(1+Х+Хг)=)чх+Х'+Х' (Х)Я (Х) = (1 + Х')(1 + Х') = 1 + Х Х ОХг Хз Хг + ОХ + ОХ' + ОХ' + Х4 ш(Х)я~(Х) = 1 ш(Х) яг(Х) ()(х) = П,ц + (1,0)х + (о,о)х + (1,0)х + (1,цх 1) 11 10 ОО 10 11 7.2.2. Представление состояния и диаграмма состояний Сверточный кодер принадлежит классу устройств, известных как конечный авгломае (Вп!се-агаге гпас)нпе). Это обшее название дано системам, обладавшим памятью о прошедших сигналах.
Прилагательное конечный показывает, что сушествует ограниченное число состояний, которое может возникнуть в системе. Что имеется в виду под состоянием (маге) в системах с конечным его числом? В более общем смысле состояние включает наименьшее количество информации, на основе которой вместе с текушими входными данными можно определить данные на выходе системы. Состояние дает некоторое представление о прошлых событиях (сигналах) и об ограниченном наборе возможных выходных данных в будушем. Будущие состояния ограничиваются прошлыми состояниями. Для сверточного кода со степенью кодирования 1/л состояние представлено содержимым К вЂ” 1 крайних правых разрядов (рис. 7.4). Знание состояния плюс знание следуюших данных на входе является необходимым и достаточным условием для определения данных на выходе.
Итак, пусть состояние кодера в момент времени г, определяется как Х, = и, — 1, т, — 2, ..., и, — К+ 1. ня ветвь кодовых слов У, полностью определяется состоянием Х, и введенными в настоящее время битами т;, таким обра- Глава7. Канальноекодирование:часть2 412 В атом примере мы начали обсуждение с того, что сверточный кодер можно трактовать как набор регистров сдвига кикаического кода.
Мы представили кодер в виде лолиномиальных генераторов, с помошью которых описываются циклические коды. Однако мы пришли к той же последовательности на выходе, что и на рис. 7.4, и к той же, что и в предыдущем разделе„полученной при описании реакции на импульсное возмушение. (Чтобы иметь лучшее представление о структуре сверточного кода в контексте линейной последовательной схемы, обратитесь к работе 17).) зом, состояние Х, описывает предысторию кодера для определения данных на его выходе.
Состояния кодера считаются Марковскими в том смысле, что вероятность Р(Х, + ЦХн ..., Х,) нахождения в состоянии Х, + 1, определяемая всеми предыдущими состояниями, зависит только от самого последнего состояния Х„т.е. она равна Р(Х, ч ЦХ,). Одним из способов представления простых кодируюших устройств является диаграмма состояния (маге б!айгапт); такое представление кодера, изображенного на рис. 7.3, показано на рис.
7.5. Состояния, показанные в рамках диаграммы, представляют собой возможное содержимое К вЂ” 1 крайних правых разрядов регистра, а пути между состояниями — кодовые слова ветвей на выходе, являющиеся результатом переходов между такими состояниями. Состояния регистра выбраны следующими: а =00, Ь =10, с = 01 и с( = 11; диаграмма, показанная на рис. 7,5, иллюстрирует все возможные смены состояний для кодера, показанного на рис. 7.3.
Существует всего два исходящих из каждого состояния перехода, соответствующие двум возможным входным битам. Далее для каждого пути между состояниями записано кодовое слово на выходе, связанное с переходами между состояниями. При изображении путей, сплошной линией принято обозначать путь, связанный с нулевым входным битом, а пунктирной линией — путь, связанный с единичным входным битом. Отметим, что за один переход невозможна перейти из данного состояния в любое произвольное. Так как за единицу времени перемещается только один бит, существует только два возможных перехода между состояниями, в которые регистр может переходить за время прохождения каждого бита. Например, если состояние кодера — 00, при следующем смешении возможно возникновение только состояний 00 илн 10.
оо ое Состояние кодера е обозначения одной бнт О --- Входной бит! зо Рис 7.5. Диаграмма состояний кодера (етепепь кодирования 1/2, К = 3) Пример 7Л. Свертечиее кедироваиие Для кодера, показанного на рис. 7.3, найдите изменение состояний и результирующую последовательность кодовых слов () для последовательности сообщений пт = 1 1 0 1 1, за которой следует К вЂ” 1 = 2 нуля для очистки регистра.
Предполагается, что в исходном состоянии регистр содержит одни нули лзя 7.2. ПРедставление свеоточного коаеоа Решение Кодовое слово ветви в момент времени Г, Входные биты, гнг Содержимое Состшшие в регистра момент времени А Состояние в момент времени Гг„г нг с Последовательность на выходе У = 1 1 0 1 0 1 0 0 0 1 0 1 1 1 Пример 7.2. Сверточное кодирование В примере 7.1 исхолное содержимое регистра — все нули. Это эквивалентно тому, что данной последовательности на входе предшествовали два нулевых бита (кодирование является функпией настоящих информапнонных бит и К вЂ” 1 предьщущнх биту Повторите задание примера 7.1, предполагая, что данной последовательности предшествовали два единичных бита, н убедитесь, что теперь последовательность кодовых слов У лля входной последовательности пг = 1 1 0 1 1 отличается от последовательности, найденной в примере 7,1, Решение Запись "х" обозначает "неизвестно".
Кодовое слово ветви в момент времеви б Входные биты„ш, Содержимое Состояние в Состояние в репмтра момент момент времениб времеви Гыг иг иг Последовательность на выходе 17=10 10 01 00 01 01 11 Глава 7. Канальное кодирование: часть 2 1 1 0 1 1 0 0 000 100 110 011 101 110 011 001 11х 111 111 011 101 110 011 001 00 00 10 11 01 10 11 01 1х 11 11 11 01 10 11 01 00 10 11 01 1О 11 01 00 11 11 11 01 10 11 01 00 1 0 0 0 0 0 1 1 1 0 0 0 0 1 Сравнивая эти результаты с результатами из примера 7.1, можно видеть, что каждое кодовое слово выходной последовательности 1) является функцией не люлько входного бита, но и предыдущих К вЂ” 1 бит. 7.2.3.
Древовидные диаграммы Несмотря на то что диаграммы состояний полностью описывают кодер, по сути, их нельзя использовать для легкого отслеживания переходов кодера в зависимости от времени, поскольку диаграмма не представляет динамики изменений. Древовидная диаграмма (ггее гйайгагп) прибавляет к диаграмме состояния временное измерение. Древовидная диаграмма сверточного кодера, показанного на рис. 7.3, изображена на рис. 7.6. В каждый последующий момент прохождения входного бита процедура кодирования может быть описана с помощью перемещения по диаграмме слева направо, причем каждая ветвь дерева описывает кодовое слово на выходе.
Правило ветвления для нахождения последовательности кодовых слов следующее: если входным битом является нуль, то он связывается со словом, которое находится путем перемещения в следующую (по направлению вверх) правую ветвь; если входной бит — это единица, то кодовое слово находится путем перемещения в следующую (по направлению вниз) правую ветвь. Предполагается, что первоначально кодер содержал одни нули. Диаграмма показывает, что если первым входным битом был нуль, то кодовым словом ветви на выходе будет 00, а если первым входным битом была единица, то кодовым словом на выходе будет 11. Аналогично, если первым входным битом была единица, а вторым — нуль, на выходе вторым словом ветви будет 1О.
Если первым входным битом была единица и вторым входным битом бьша единица, вторым кодовым словом на выходе будет 01. Следуя этой процедуре, видим, что входная последовательность 1 1 0 1! представляется жирной линией, нарисованной на древовидной диаграмме (рис. 7.б). Этот путь соответствует выходной последовательности кодовых слов ! 1 О ! О 1 О О О 1. Добавленное измерение времени в древовидной диаграмме (по сравнению с диаграммой состояния) допускает динамическое описание кодера как функции конкретной входной последовательности. Однако заметили ли вы, что при попытке описания с помощью древовидной диаграммы последовательности произволыюй длины возникает проблема? Число ответвлений растет как 2~, где Ь вЂ” это количество кодовых слов ветвей в последовательности.
При большом Ь вы бы очень быстро исписали бумагу и исчерпали терпение. 7.2 4. Решетчатая диаграмма Исследование древовидной диаграммы на рис. 7.б показывает, что в этом примере после третьего ветвления в момент времени г„структура повторяется (в общем случае древовидная структура ловторнется после К оглвелгвлениа, где К вЂ” длина кодового ограничения). Пометим каждый узел в дереве (рис, 7.б), ставя в соответствие четыре возможных состояния в регистре сдвига: а = 00, Ь = 10, с = 01 и а! = 11. Первое ветвление древовидной структуры в момент времени г, дает пару узлов, помеченных как а и Ь.
При каждом последующем ветвлении количество узлов удваивается. Второе ветвление в момент времени г, дает в результате четыре узла, помеченных как а, Ь, с и Н. После елегльего ветвления всего имеется восемь узлов: лва — а, два — Ь, два — с и два — д. 7.2. Представление свеоточиого кодеРа 415 54 55 51 ГЯ Гз Рис. 7.б. Древовидное представление кодера (степень кодирования 1/2, К= 3) Можно видеть, что все ветви выходят из двух узлов одного и того же состояния, образуя идентичные ветви последовательностей кодовых слов. В этот момент дерево делится на идентичные верхнюю и нижнюю части. Смысл этого становится яснее после рассмотрения кодера, изображенною на рис.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
