Кузьмин С.З. Основы теории цифровой обработки радиолокационной информации (1974) (1186213), страница 12
Текст из файла (страница 12)
В случае автомата Л{1)на стрелках через дробную черту отмечаются также выходные сигналы.Vy,Рис. 2.2. Граф автоматавыдаваемые при переходе автомата по указанному входному сигналу.В случае автомата М2) выходные сигналы ставятся в вершинах графа.На рис. 2.2 и 2.3 приведены графы автоматов Л^ и А^\ заданныхтабл. 2.5 и 2.6 соответственно.Рис. 2.3. Граф автоматаДля аналитического исследования более удобны матрицы переходовконечных автоматов. Матрица переходов автомата М1) с М 4- I состояниями содержит (Λί.+ 1) X (Л1 + 1) элементов.
Элемент строки'i и колонки / обозначается μ^ и определяется так:О=1п,к = 1 , т , если переход i •/ существует., если переход £- / не существует.Для автомата," граф переходов которого изображен на рис. 2.2, матрица переходов имеет видXQ/УОХо!УоxjyoXQ/УОXI/УО0000Х\1Уь000X\i.0 "xJ,57Для автоматов второго рода матрица переходов строится аналогичнорассмотренному выше.
В ней под дробной чертой в элементах μ^ставится выходной сигнал, соответствующий состоянию у. Для детерминированных автоматов каждая строка матрицы переходов содержит пэлементов, не равных нулю, где п — число символов в алфавите входного сигнала.Отметим в заключение, что формы задания цифровых автоматовв виде таблиц переходов получили название стандартных форм.2.1.3. Абстрактный синтез конечных автоматовПервоначально алгоритм функционирования автомата задается всодержательной (словесной) форме. На этапе абстрактного синтезаосуществляется переход от содержательной формы записи алгоритмафункционирования автомата к одной из стандартных форм.
Кроме того*на этапе абстрактного синтеза производится минимизация числавнутренних состояний автомата, что эквивалентно минимизации объемаего памяти.Иногда удается сразу по описанию алгоритма построить таблицупереходов или граф автомата. Однако в общем случае для переходак стандартным формам необходимо сначала перейти к промежуточной,так называемой начальной форме задания автомата. В качестве начальной формы задания автомата выбирают такую, переход к которойот алгоритма, сформулированного описательно, и получение из которой одной из стандартных форм достаточно просто. Одной из известныхначальных форм задания автомата является запись алгоритма егофункционирования на языке регулярных событий [41.
Этот способ позволяет достаточно просто переходить от словесного к строго математическому описанию функционирования автомата и, кроме того,является наиболее удобным при синтезе автоматов для обработки радиолокационной информации.Ниже приводятся необходимые сведения из алгебры событий.Пусть задан некоторый конечный алфавит X — (хи х2, ..., хп).Событием 5 в данном алфавите X называется произвольное множество слов*> в этом алфавите, а сам алфавит X — (xlt χ2> ,.., χη) называется входным алфавитом этого события.Для представления событий, содержащих бесконечное количествослов, конечными выражениями вводят ряд операций над событиями,т.
е. строят алгебру событий. В алгебре событий рассматривают триосновные операции: дизъюнкцию событий, произведение событий иитерацию событий.Дизъюнкцией событий Sx, S2t ..., Sk называется событие S —= Si + S2 -1- ... + Sk, состоящее из всех слов, входящих в событияSlt S2, .... Sk, т. е. дизъюнкция объединяет все слова, входящие в события 5j, 5 2 , .... Sft, Например, если событие 5^содержит слова xlt'' Под словом понимается произвольная последовательностьбукв алфавита.Xj_ x 2 i ^2χΐ> a событие S 2 содержит слова x 2 x 2 , х^о, то дизъюнкция этихсобытий 5i -f S2 содержит слова xlt xlx2t x2Xi, хгх2.Пусть события Si и 5 2 состоят из множества слов {хп, x12t лг13....)и (х 2 1 , ^22 -Чз.--) соответственно.
Произведением этих событий называется событие S = SiSit состоящее из всех слов вида хпхп, хп *гг.хп х23, .... * 1 2 * 2 ι . х1г*гг> ^ Л л ••• т ' е ' и з всех слов, полученных приписыванием к каждому слову события Sj каждого слова события S2. Необходимо заметить, что произведение событий некоммутативно, т, е. SiS2 Ф SiSx.Итерацией события S называется событие {£}, состоящее из пустого слова е и всех слов вида S, 5S, 55S и т. д. до бесконечности.Иначе говоря, если событие S состоит из слов [х, 12, ..., /,,, то итерацияэтого события содержит все возможные произведения этих слов, конечные и бесконечные. Итерация события является одноместной операцией, так как она применяется только к одному событию. Для обозначения итерации вводят фигурные скобки, которые в данном случаеназываются итерационными.Если задан конечный входной алфавит X = (xlt x2, ..., хп), то любое событие, которое можно получить из букв данного алфавита с помощью конечного числа операций дизъюнкции, произведения и итерации, называют регулярным событием, а выражение, составленное с помощью этих операций, — регулярным выражением.В теории автоматов доказывается, что любой алгоритм переработки информации, который может быть записан в виде регулярного выражения, реализуется конечным автоматом.Рассмотрим пример абстрактного синтеза автомата, предназначенного для выделения в бинарной последовательности квантованных сигналов групп, начинающихся единицей и заканчивающихся серией изтрех нулей.
Описательно алгоритм работы синтезируемого автоматаформулируется следующим образом. Если на вход автомата (предварительно возвращенного в исходное состояние) после любой серии нулейпоступает единица, то автомат переходит в новое состояние и вырабатывает сигнал уп, фиксирующий начало группы. Сигнал уи долженвыдаваться до тех пор, пока на вход автомата не поступит серия из трехнулей. При поступлении этой серии автомат выдает сигнал ую фиксирующий конец группы. . •Составим регулярное выражение, описывающее функционированиеавтомата.
При этом учтем, что множество входных сигналов состоитиз двух символов —0 и I, которые закодируем: 0—х 0 , 1 — xv Множество выходных сигналов также состоит из двух символов уп и ук.Событие, состоящее в том, что на вход автомата поступает серия х0,может быть представлено выражением Si — {*„}..Событие, состоящее в том, что после серии нулей на вход автоматапоступит хг, может быть записано в следующем виде 5 2 = .{xo}xvСобытие, состоящее в том, что на вход автомата поступает последовательность, не содержащая трех нулей подряд, записывается в виде59могут быть слова xlt х,х,, ад/., х, и т.
д., иЛиед^вд,^... ЗДИ Т. Д . , ИЛИXQX^X^... X()XQXlИ Т. Д.Таким образом, событиеRl = SvSs ={xo}Xi {Xi -r *o*i 4- xo*o*i}.(2.1.6)состоящее в том, что после произвольной серии нулей на вход автоматапоступает единица, а за ней любая произвольная комбинация нулейРис. 2.4. Граф автоматаи единиц, не содержащая трех нулей подряд, представлено в автоматевыходным сигналом ун.Событие Rt = S2S3xoXoXo, т. е,Яг={XQ}MXI-Г^о^- ^ XOXOXI)XOXOXQ,(2.1.7)состоящее в том, что после наступления события Rx поступает три нуляподряд, представлено в автомате выходным сигналом ук.Рис. 2.5.
Граф автомата o&t'-K- Из сравнения (6) и (7) видно, что регулярное выражение для события Rl входит в регулярное выражение для события R2. Следовательно, для описания работы синтезируемого автомата достаточно записатьрегулярное выражение для события R2, дополнив его указаниеммоментов выдачи сигналов ув и ук. В результате получим регулярноевыражениеописывающее функционирование рассматриваемого автомата в целом,В специальной литературе 12, 3] опубликованы подробные алгоритмы абстрактного, синтеза автоматов по соответствующим регулярным60выражениям.
Для примеров, аналогичных рассматриваемому, краткойописание всех этапов составления отмеченной таблицы переходов автомата МгК имеется в книге [6]. Здесь только заметим, что длянесложных алгоритмов таб.лицу переходов или граф соответствующегоавтомата можно построить непосредственно по регулярному выражению, без применения специальных методов синтеза.Для рассматриваемого алгоритма на рис.
2.4 построен граф автоматавторого рода Л{2), а на рис. 2.5 — граф автомата первого рода Л^КИз сравнения графов следует, что в автомате Л{1) отсутствует состояние 4, так как оно объединяется с состоянием 0. Следовательно, общеечисло состояний автомата уменьшается на-единицу. В дальнейшембудем иметь в виду только автоматы первого рода2.1.4. Композиция (свертка) цифровых автоматовСовместная работа автоматов задается операцией композиции. В общем случае под композицией понимаются различные способы соединений и виды работыавтоматов, такие как последовательное, параллельное н смешанное соединение,одновременная и поочередная работа и т- д.Мы в дальнейшем будем рассматриватьтолько способы соединения цифровых авто| ' "'\у,&)х ({)А.А.1матов.гРассмотрим сначала простейший случай композиции — последовательное соединение двух автоматов .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
