Кузьмин С.З. Основы теории цифровой обработки радиолокационной информации (1974) (1186213), страница 13
Текст из файла (страница 13)
i j H ^ г (рис. 2.6).Рис. 2.6. Последовательное соедиНа входе автомата „-#ι действует сигналнение двух автоматов.Xj (/). Автомат J&2 получает на, вход выходные сигналы автомата j$lt.т. е.*>(0 = М О = φ ΐ ί θ ΐ . ( 0 . АЧ(0].Для нормального функционирования второго автомата необходимо, чтобыалфавит выходных сигналов автомата j$x совпадал с алфавитом входных сигналов'автомата я$г. Сигнал на выходе второго автомата можно записать в видеУг (0 - Ф 2 {(ла (0.
<Х>1 Ui (0. Ч (01 } = Ф> [θι (0. аг (t), xx (t)).Если каждую пару состояний ах (ί) и а2 (ί) составляющих автоматов связатьс одним состоянием a.(t) объединенного автомата, то получимy2(t) = ! / ( / ) = Ф [ а ( 0 , ^ ( 0 1 .а ( / + 1) = F \a {t), xx (()]•Таким образом, объединенный автомат с& есть конечный автомат. Если автомат Ж-χ имеет ЬАХ + 1 состояний, а автомат ^ 2 ~ Мг + I, то общее число состояний объединенного автомата М -Ь 1 = (Λί: + 1) X (М а + 1). Каждой паресостояний автоматов <$х и j i 2 соответствует одно состояние автомата ^ ί . Состояния объединенного автомата обозначаются (at •«-.
а,).(1)Обозначим элементы матрицы переходов первого автомата μί/ , а второго —через μί/'. Тогда элементы матрицы переходов а в т о м а т а ^ определяются по правилу^k.^i^iPAV(2.1.8)Умножение элементов матриц переходов производится следующим образом [8].Пусть (Xj/f/i) — пара вход — выход, соответствующая переходу μι}), а {хг/уя) —61аналогичная пара для перехода. Тогда„(П„(20(2.1.9),еслиДополнительные правила умножения элементов матриц устанавливаются наосновании законов и равносильностей алгебры логики.Рассмотрим пример последовательного соединения двух автоматов, предназначенных для обработки стационарной последовательности дискретных сигналов, каждый из которых может принимать только два значения — нуль и единица.Пусть автомат <&х предназначен для восстановления одиночных пропусковединиц во входной последовательности сигналов, Матрица переходов этого автомата имеет вид (10)0/0 Ι/Ι(2.1.10)0/1 1/1Второй автомат ^ 2 получает на вход выходные сигналы автомата 4%^ и предназначен для выделения серий из четырех и более единиц в последовательностиэтих сигналов.Матрица переходов автомата j&2 имеет вид (II)0/0 1/0 00о/о 0 1/0 00/0 0 • 0 1/0о/о 0 0 1/1(2.1.11)Пользуясь правилом (9), образуем матрицу переходов объединенного автомата с&, представляющего собой последовательное соединение автоматов J£X и<&г.
Эта матрица имеет видО -«-> 0 '0/0;о/оо/оо/о100000000о/о00000000000000о/оо' о/оо. 0/1000000001/00001/000001/00001/000001/01/1001/01/1(2.1.12)Из матрицы (12) следует, что состояние 1 *-* 0 автомата является не достижимым из любого другого состояния. Следовательно, его можно исключить. Приэтом исключается также состояние 0 *-* \, в которое автомат переходит толькоиз состояния 1 *-* 0.Таким образом, объединенный автомат имеет 6 состояний и функционируетв соответствии с матрицей переходов (13)0/0 00/0 0о/о 0М=0 о/о0000621/0 000000 i/0о/о 0 000/1 0000001/01/101/01/1(2.1.13)-•рассмотрим теперь пример более сложной последовательно-параллельнойкомпозиции автоматов, в соответствии со схемой сЪединения, приведенной нарис. 2.7.Пусть автомат j£x выдает сигнал (единицу), если во входной последовательности квантованных сигналов (нулей и единиц) появляется (обнаруживается)серия из двух единиц или условленная комбинация из двух единиц на трех смежных позициях. (11 или 101).
Автомат j&2 предназначен для фиксации во входнойпоследовательности квантованных сигналов серий из двух нулей.Выходные сигналы автоматов αφλ и j&2 поступают на вход третьего автоматаj#s, предназначенного для счета тактов от момента срабатывания автоматадо момента сброса накопленной информации при появлении серии из двухнулей. При сбросе автомат с43 выдаетв двоичном коде число тактов междусрабатываниями автоматом j&x и &&2В качестве автомата j$3 в дальнейшем ьвыбирается двухразрядный двоичный _;счетчик.Образуем сначала свертку автоматов j£x и \?$2, соединение которых яв -1ляется смешанным (последовательноРис. 2.7. Последовательно-параллельпараллельным).ная композиция автоматов.В соответствии с алгоритмом работыавтомата <&х и с учетом воздействия наего входах сигналов х 1 ( 1 ) и xi(i> — у2 (алфавит этих сигналов одинаковый и содержит только две буквы — 0 и 1) матрица его переходов имеет вид01/0+00/001/0+00/0010/00010/1001/0 + 00/0010/0010/1+00/101/000(2.1.14)В матрице (!4) входные сигналы обозначены двумя символами, первый (левый) из которых соответствует сигналу хг П ) , а второй (правый) — сигналу * 2 (пАлфавит входных сигналов автомата теперь содержит четыре буквы — 00, 01,10, 11.
Из них буква 11 является запрещенной, так как, исходя из логики работы автомата &&г, сигнал единица на его выходе не может появиться одновременно с получением единицы во входной последовательности обрабатываемых сигналов.Матрица переходов автомата ^фг эаписывлется в видеЕ; О / 1Элементы f^ ^ ,.I/O(2.1.15)матрицы переходов для последовательно-параллель-ного соединения автоматов образуются по правилупри1} * 2 ([) {Ч)=Уг («/)•2)х,((i)=xz(kl);{l)При 1) * 2 ( I ) ('/) ^ У2 ( * 0 ι2) *,Щ)фх2(к1){1)Для рассматриваемой композиции автоматов,^, иимеет вид0/010/000/010/00000/0100 00 00 00 00 00 00 00 00 0/01 0 00 0/00 0 00 00 00 00 0I/OO1/000000000000/Ю; матрица переходов0О1/101/10(2.1.16)1/101/101/101/10Рис.
2.8. Граф автомата, полученного в результате последовательного соединения двух автоматов.В этой матрице состояния 0-*-+ i, i -*-* 1, н 2 * - * 0 являются недостижимыми. Вычеркивая эти состояния и производя прео'бразования, получим окончательноматрицу£\0/01j 0/0I=0001/00000001/100/010/0000001/001/100000/101/10(2.1.17)В соответствии с матрицей (17) на рис. 2.8 изображен граф автомата с&1,полученного в результате свертки а в т о м а т о в ^ и Jtit По графу легко проследитьфункционирование этого автомата.Рассмотрим теперь последовательное соединение автоматов Ji\ и Л-г.В качестве автомата ^ 3 мы условились для простоты взять двухразрядныйсчетчик, на выходе которого можно получить сигналы, соответствующие накоплению 0, 1, 2 и 3 единиц.Матрица переходов автомата <&л (двухразрядного счетчика) имеет вид0000/1 (01)+01/1 (01)00/0(00)010/0(00)000/1 (10)+01/1 (10)0010/0(00)0000/1 ( П ) + 0 1 / 1 (11)-Ь 10/1 (II)10/0(00)г,(2.1.18)0В этой матрице входные сигналы также помечены двумя символами, в соответствии с алфавитом выходных сигналов автомата j%"%.
При наличии сигнала 00 на выходе автомата а%\ счетчик сбрасывается в нуль. Последнее условие срабатывания64автомата <?&3 являтся дополнительным н устанавливается исходя из требуемойпоследовательности работы схемы.Выходные сигналы счетчика также имеют двойную нумерацию. Первыйпредставляет собой сигнал обнаружения (единица) или.
необнаружения (нуль)заданной комбинации нулей и единиц на входе автомата j&3, а второй (в скобках)—число в двоичном коде, снимаемое со счетчика в момент сброса накопленной информации.Порядок составления матрицы переходов при последовательной композициидвух автоматов рассматривался выше. Здесь мы опустим громоздкие промежуточные операции и приведем только в окончательном г виде граф полученногообъединенного автомата, представляющего собой последовательно-параллельную композицию из трех рассмотренных автоматов (рис. 2.9).У/1/0(00) ^У1/0(00) \Yr/O(OO)Рис.
2.9. Граф объединенного автомата.Рассмотренные примеры композиции автоматов охватывают практическивсе случаи, встречающиеся при синтезе специализированных устройств цифровойобработки радиолокационной информации.В дальнейшем в книге этапы синтеза и композиции автоматов будут опускаться.2.1.5. Модель конечного автомата со случайными переходамиДо сих пор рассматривались конечные автоматы, для которых задание входного сигнала {входного слова) xt и.состояния a (t— I) однозначно определяет выходной сигнал (выходное слово) yt и новое состояниеа (/).
Такие автоматы называются детерминированными.Наряду с детерминированными в приложениях находят применениеконечные автоматы, в которых переходы из состояния в состояниеявляются случайными. Такие автоматы называются автоматами со случайными переходами. В автомате со случайными переходами заданиевходного сигнала и состояния определяет лишь вероятности ntj (х)перехода из состояния at в состоянием, под воздействием входного сигнала xt. Очевидно,' датерминированный автомат является частным случаем автомата со случайными переходами, так как в нем.3 Зак. 6 И65вероятность одного определенного перехода равна единице, а остальных — нулю.В общем случае конечный автомат со случайными переходами Лгзадается следующей шестеркой характеристикЛс = ЛС{Х, У, А, с 0 ( П(Х()Ф [а (/), xt]}t(2.1.19)где X и У— непустые конечные множества входных и выходных сигналов автомата, элементы которых обозначаются через xt и yt соответственно; А — непустое конечное множество физических состоянийавтомата; а0 — начальное состоя'ние автомата; П {xt) — множествоквадратных матриц порядка (М + 1) X (Λί + 1), где М + 1 числосостояний автомата, определяющее вероятностный закон изменениясостояний автомата под воздействием входного сигнала xt (элементыntj (Xt) этой матрицы определяют вероятность того, что в результатевоздействия сигнала xt на входе автомат, находящийся в состоянии с г в момент времени t — 1, перейдет в состояние а} в моментвремени t)\ Ф [a (t), xt]—неслучайная функция "выходов автомата,представляющая собой отображение множества пар состояний автомата и входных сигналов на множество выходных сигналов У.Таким образом, автомат со случайными переходами отличается отдетерминированного автомата тем, что вместо детерминированнойфункции переходов его функционирование определяется множествомматриц переходных вероятностей.В теории синтеза устройств и алгоритмов цифровой обработкирадиолокационной информации особое место занимает конечный автомат с неизменной структурой, на вход которого поступает последовательность случайных сигналов, принимающих значения 0 и 1 с вероятностями q.и р соответственно (р -\- q = 1).
Переходы автомата из одного внутреннего состояния в другое носят в этом случае вероятностный характер, так как они определяются случайными воздействиями«внешней среды». Следовательно, систему «среда — автомат» можнорассматривать как некоторую вероятностную систему, функционирование которой аналогично функционированию автомата со случайными переходами.В дальнейшем под автоматами со случайными переходами понимается именно рассмотренная система «случайный входной сигнал +детерминированный одновходовый автомат». Функционирование такогоавтомата полностью определяется с помощью единственной матрицыпереходных вероятностей. Для определенности считается,, что перваястрока (как и первый столбец) матрицы переходных вероятностей соответствует начальному состоянию автомата.
Выходные сигналы в матрице переходных вероятностей не отмечаются (отождествляется с состояниями).Если вероятности q и р не изменяются во времени, т. е. от такта к такту работы автомата, то автомат со случайными переходаминазывается однородным. Например, матрица переходных вероятностейоднородного автомата со случайными переходами, эквивалентного66детерминированному автомату, синтезированному в п. 2.1.3 (граф нарис. 2.5), имеет видЯ Р 00 Р я0 Р 0Я Р 000я0(2.1.20)По матрице переходных вероятностей для ОДНОВХОДОЁОГО автоматасо случайными переходами обычным образом может быть построенграф, дуги которого отмечаются вероятностями переходов между соответствующими состояниями.Можно показать, что матрицы переходных вероятностей обладаютследующими свойствами:а) элементы матрицы представляют собой неотрицательные вещественные числа, т.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
