uzluga.ru
добавить свой файл


ЛЕКЦИЯ 4


Последовательностные автоматы

  • Изменение во времени состояния входа комбинационного автомата, мы можем получить некоторую последовательность входных состояний, которую можно представить соответствующей последовательностью значений вектора X. На выходе автомата образуется в этом случае последовательность выходных состояний представляемых соответствующими значениями вектора Y. При этом каждый член входной последовательности будет однозначно определять каждый член входной последовательности. Например, если значение 1001 вектора X соответствует значение 001 вектора Y, то это соответствие будет реализовываться комбинационным автоматом всегда вне зависимости от предшествующего значения вектора X. Именно это свойство комбинационных автоматов имеют в виду, называя их автоматами без памяти: поведение таких автоматов не зависит от прошлого, а полностью определяется текущим входным состоянием.

  • Итак, можно сказать, что комбинационный автомат реализует некоторое однозначное отображение множества входных состояний во множество выходных состояний.



Принципиально по другому ведет себя автомат с памятью или последовательностный автомат. Само это название говорит о том что, он реализует функциональную связь уже не между отдельными состояниями, а между их последовательностями, точнее между входной и выходной последовательностью.

  • Принципиально по другому ведет себя автомат с памятью или последовательностный автомат. Само это название говорит о том что, он реализует функциональную связь уже не между отдельными состояниями, а между их последовательностями, точнее между входной и выходной последовательностью.

  • Последовательностный автомат может по разному реагировать на одинаковые выходные состояния, ставя им в соответствие различные выходные состояния . Его реакция зависит, вообще говоря, от всей последовательности входных состояний, реализованной к текущему моменту времени, и выражается выдачей некоторой последовательности выходных состояний.

  • Такое поведение последовательностного автомата становится понятным, если учесть, что он обладает некоторым множеством внутренних состояний, в каждом из которых он ведет себя подобно некоторому комбинационному автомату, т.е. реализует однозначную функциональную связь между входными и выходными состояниями.

  • Однако наряду с этим его реакция на очередное входное состояние может выразиться также в смене внутреннего состояния, т.е. в переходе в другое внутреннее состояние, в котором автомат уже по иному будет реагировать на следующее входное состояние.



Заметим, что множество всевозможных значений булева вектора x, используемых для представления входных состояний автомата, принято называть структурным входным алфавитом, а множество значений вектора y- структурным выходным алфавитом. Такая терминология оправдана, т.к. значение векторов X и Y задают входные и выходные состояния автомата, как некоторые комбинации состояний его полюсов, т.е. действительно показывают внутреннюю структуру состояний автомата.

  • Заметим, что множество всевозможных значений булева вектора x, используемых для представления входных состояний автомата, принято называть структурным входным алфавитом, а множество значений вектора y- структурным выходным алфавитом. Такая терминология оправдана, т.к. значение векторов X и Y задают входные и выходные состояния автомата, как некоторые комбинации состояний его полюсов, т.е. действительно показывают внутреннюю структуру состояний автомата.

  • Между тем при рассмотрении ряда задач удобно абстрагироваться от структуры входных и выходных состояний автомата и представлять их довольно произвольными символами, беспокоясь лишь о том, чтобы разные состояния оказались представленными различными символами. Будем считать, что эти символы выбираются из некоторого множества и , называемых соответственно абстрактным входным и абстрактным выходным алфавитом. Допустимо также называть эти множества – множествами входных и выходных состояний (заданных в абстрактных алфавитах).

  • Вводя в рассмотрение множество внутренних состояний автомата, будем пока считать, что эти состояния заданы также в абстрактном алфавите.



Синхронный автомат

  • Наиболее известной разновидностью последовательностный автоматов является синхронный и асинхронный автоматы.

  • Синхронный способ заключается в следующем. Вводится шкала времени, которая делится на отрезки одинаковой длины (такты); границы тактов называются моментами автоматного времени и нумеруются натуральными числами, начиная с нуля. Длина такта принимается за единицу времени. Входное слово (последовательность букв) рассматривается как временная последовательность сигналов или импульсов (каждый сигнал соответствует букве); интервал между соседними импульсами равен в точности длине такта. При такой интерпретации импульс является точечным. Можно считать, что сигнал длится на протяжении всего такта. Следовательно, слово длины k занимает во времени ровно k тактов, его буквы можно считать функциями от времени:

  • - буква, появившаяся на входе в момент .



Поведение синхронного автомата рассматривается в дискретном времени , представляющем собою последовательность моментов ,обозначаемых через 1, 2, 3, … и т.д. Такое рассмотрение связывается с наличием некоторых тактовых генераторов в технических реализациях автомата. Поведение автомата определяется реализуемым им отношением между входными и выходными последовательностями. При этом считается, что члены входной последовательности представляют собой входные состояния автомата в следующие друг за другом моменты дискретного времени. Аналогично определяется выходная последовательность.

  • Поведение синхронного автомата рассматривается в дискретном времени , представляющем собою последовательность моментов ,обозначаемых через 1, 2, 3, … и т.д. Такое рассмотрение связывается с наличием некоторых тактовых генераторов в технических реализациях автомата. Поведение автомата определяется реализуемым им отношением между входными и выходными последовательностями. При этом считается, что члены входной последовательности представляют собой входные состояния автомата в следующие друг за другом моменты дискретного времени. Аналогично определяется выходная последовательность.

  • Поведением синхронного автомата является следующая пара функций, называемых соответственно функцией переходов и функцией выходов .



Пример последовательностного автомата

  • Как можно упростить решение задачи?

  • В силовой установке необходимо постоянно контролировать направления вращения вала с помощью автономно работающего прибора. Прибор в определенные моменты времени должен выдавать сигнал, который соответствует направлению вращения вала, который далее может использоваться в других узлах системы.

  • Допустим, что в качестве датчика используется шайба, которая закреплена на конце вала. Шайба разделена на четыре сектора. Из которых одна пара противоположных секторов сделана проводящей, а другая не проводящей (рисунок 2.1). B1 и B2 скользящие контакты. Они касаются края шайбы и могут пробегать при вращении выделенные секторы один за другим, и могут одновременно находится в пределах наименьшего из секторов.





B1 и B2 – являются входами конструируемого автомата А и принимают значения 0 и 1.

  • B1 и B2 – являются входами конструируемого автомата А и принимают значения 0 и 1.

  • В качестве выхода автомата можно использовать =1, если шайба вращается по часовой стрелке и =0, если шайба вращается против часовой стрелки.

  • Есть датчик тактов времени, в которые автомат А воспринимает входы и вырабатывает соответствующий выход.

  • Рассуждаем:

  • Имеется 4 варианта входных воздействий автомата А: , где пара i,j означает, что к контакту В1 приложено напряжение i, а к контакту B2 – напряжение j .

  • Очевидно, что по отдельному входу автомата направление вращения не может быть определено. Для этого автомат должен в некотором смысле суммировать входы в предшествующие моменты времени и запоминать каким-либо способом состояние системы в данный момент времени для использования этой информации в дальнейшем.

  • В качестве состояний системы будем рассматривать 8 пар. Первая компонента которых – последний по времени вход, а вторая – выход (0 или 1).



Состояния

  • По состоянию и (новому) входу например ,по (Z1 и a), или по (Z1 и b), или по (Z1 и d) и т.д. непосредственно может быть определенно направление вращения выход

  • при Z1 и a =1,

  • при Z1 и b =1,

  • при Z1 и d =0 и т.д.

  • Некоторые комбинации состояний и выходов недопустимы:



Следует предполагать, что произошла ошибка и автомат должен порождать выход 1, сигнализирующий об этом. Мы будем считать, что ошибочный вход прекращается в тот момент, когда в автомат А поступает сигнал отличный от ошибочного.

  • Следует предполагать, что произошла ошибка и автомат должен порождать выход 1, сигнализирующий об этом. Мы будем считать, что ошибочный вход прекращается в тот момент, когда в автомат А поступает сигнал отличный от ошибочного.

  • Итак, автомат имеет 2 выхода (выходных информаций): один – для указания направления вращения вала, другой – для сигнализации об ошибке (0 – если ошибки не было).

  • Автомат имеет четыре выходных комбинации:

  • p=(00);q=(10);r=(1,1);s=(0,1),

  • где первая компонента каждой пары означает направления движения вращения вала.

  • Теперь можно описать функционирование автомата А таблицей, в которой новое состояние и соответствующий выход ставятся в соответствие старому состоянию и полученному входу (при этом вместо Zi мы пишем просто i).



Таблица

  • Таблица



Функционирование этого автомата (зависимость изменения состояний и выходов от входов) будет задаваться таблицей, т.е. двумя функциями:

  • Функционирование этого автомата (зависимость изменения состояний и выходов от входов) будет задаваться таблицей, т.е. двумя функциями:

  • состояния выходы

  • Автомат может быть удобно описан графом. Рисунок 2.2.