2. Синтез дискретных автоматов

Как уже указывалось выше, основной задачей синтеза является получение математической модели автомата в виде системы уравнений алгебры Буля, определяющих все выходные функции. Если количество входов и выходов автомата невелико, то для вывода логических выходных функций можно использовать таблицу состояний. По таблице состояний для любой из выходных функций можно составить логическую формулу в виде СДНФ или СКНФ, выписав конституенты для единичных или нулевых состояний функции 2. Например, выход К1 (см. табл.1) наиболее удобно представить как дизъюнкцию двух конституентов единицы:

.

Используя теорему склеивания, можно получить более компактную форму этой логической функции, удалив переменную S1:

,

однако для полной минимизации, для «склеивания» необходимо использовать еще и «фиктивные» наборы входных переменных. Для этой цели имеет смысл применять табличные методы минимизации, например Квайна – МакКласски или Гаврилова – Копыленко 2. При большом числе переменных такой подход требует построения громоздких таблиц состояний и большого числа переборов, что весьма затрудняет процесс минимизации и синтеза в целом.

Существует методика синтеза, основанная на анализе циклограмм 5, однако ее алгоритм является громоздким и сложным, особенно для систем с большим количеством входов и выходов.

Рассмотрим подробно блочный метод синтеза, который, на наш взгляд, является наиболее простым и удобным.

Блочный метод синтеза заключается в том, что автомат (см. рис. 1) разбивается на блоки. Каждый блок соответствует лишь одному из m выходов автомата, т.е. реализует лишь одну логическую функцию (рис. 9). В целом же, все блоки в совокупности образуют исходный блок.

Рис. 9

В общем случае каждая из функций Y_i = f(X₁, X₂, …, X_n) есть функция всех n переменных. Однако все переменные по отношению к каждой логической функции выхода можно подразделить на три группы:

1) существенные;

2) несущественные;

3) квазисущественные.

Существенными называются те переменные, изменение состояния которых непосредственно определяет изменение состояния данной выходной функции – порождает выход. Они должны быть обязательно включены в блок определяемой выходной функции. На графе переходов конечного автомата существенные переменные записываются на дугах, определяющих переходы с формированием выходов (см. рис. 7). Аналогично существенные переменные определяются по графу функционирования, где они помещены на дугах непосредственно перед вершиной, соответствующей изменению состояния данного выхода (рис. 8).

Несущественными будут являться те переменные, состояние которых никак не влияет на данную функцию, т.е. при любом их значении ( 0 или 1) функция остается эквивалентной. Такие переменные тоже можно легко определить по графу или по таблице состояний, и они могут быть удалены из блока.

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

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

Известно, что различают комбинационные и последовательностные автоматы 3. Длякомбинационныхавтоматов характерно то, что каждая совокупность состояний выходов (каждая входная последовательность) однозначно определяется одним или несколькими из конечного множества состояний входных переменных. При этом каждая выходная функция характеризуется определеннымикомбинациямивходов. Такие автоматы называют еще автоматами без памяти илитривиальными автоматами.

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

Синтез комбинационных автоматов. Для примера возьмем автоматическую установку, функциональная схема которой представлена на рис. 5. В рассматриваемом примере мы разбиваем автомат на три блока в соответствии с выходами К1, К2 и Y1. Составим таблицу истинности (состояний) для выхода К1. Существенными переменными для него будут S3, определяющая включение в конце цикла (а следовательно, и в начале цикла), и S2, «обнуляющая» выход в конце первого такта цикла. Таким образом, К1 = {S3, S2}.

Таблица 2 Таблица 3

S2	S3	К1		S1	S4	К2
0	1	1		1	0	0
1	1	0		0	0	0
1	0	0		0	1	1
0	0	0		1	1	0

По табл. 2 для единственного единичного значения функции К1 выписываем конституент единицы, получаем . Аналогично по табл. 3 определяем выходную функцию К2, получаем.

Рассмотрим функцию Y1. Здесь существенными переменными будут являться S1 и S2. Можно определить функцию как Y1 = {S1, S2}. Построим таблицу состояний для Y1 – табл. 4.

Анализируя табл. 4, можно увидеть, что имеет место противоречие, т.е функция при значениях переменных S1 = 0 и S2 = 0 имеет противоречивые состояния. В этом случае необходимо доопределить функцию квазисущественной переменной, которая бы на участке противоречия меняла свое состояние нечетное число раз. Если автомат комбинационный, то такая переменная обязательно существует. В нашем случае можно использовать переменные S3 или S4. Выберем переменную S3, тогда Y1 = {S1, S2, S3}.

Таблица 5

	Таблица 4			S1	S2	S3	Y1
S1	S2	Y1		1	0	1	0
1	0	0		0	0	1	0
0	0	0		0	1	1	1
0	1	1	противоречие	0	1	0	1
0	0	1		0	0	0	1
1	0	0		1	0	0	0

Строим таблицу состояний уже для трех переменных (табл. 5). По табл. 5 для единичных значений функции можно составить СДНФ и далее, используя один из методов минимизации, получить МДНФ. Опуская процесс минимизации, заметим, что в данном случае функция будет определена так:

.

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

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

2. Условие работы автомата описывается графом функционирования с использованием всех идентификаторов входных и выходных элементов, которые далее будем называть соответственно переменными и функциями.

3. По графу определяется или назначается начало цикла. Обычно это исходное состояние автоматического устройства. В начале цикла выявляются и выписываются все состояния входных переменных и выходных функций. Для нашего примера началу цикла соответствуют S1=1; S2=0; S3=1; S4=0; K1=1; K2=0; Y1=0, (S1, , S3, , K1, ,).

4. Автомат разбивается на отдельные блоки (функции), и для каждой функции производится синтез. При этом выбираются существенные переменные, для них строится матрица Карно, в которой по графу функционирования прослеживаются все переходы и изменения состояния выходной функции. Начинается анализ с той ячейки матрицы, которая определяется состоянием переменных в начале цикла. Эту ячейку помечают, закрасив уголок клетки матрицы так, чтобы можно было проследить обязательный возврат в эту же клетку в конце цикла.

5. Если при очередном переходе по матрице Карно возникает противоречие, то выбирается дополнительная квазисущественная переменная, которая меняет своё состояние на данном участке нечетное число раз ( 1, 3 и т.д.). При этом матрица расширяется и процесс синтеза начинается сначала. Необходимо добиться возвращения в клетку, помеченную знаком «начало цикла».

6. Когда все переходы в матрице Карно по всему циклу осуществились без противоречий, то производится минимизация выходной функции по единичным или нулевым состояниям по известной методике 1,2,3. Полученные в результате синтеза булевы функции при проектировании автомата реализуются на той или иной элементной базе.

Повторим синтез для автомата, заданного графом (рис. 8), но уже с использованием матриц Карно. Для функций K1 определяем существенные переменные, строим матрицу, помечаем «начало цикла» и следим по графу функционирования за изменением состояний входных переменных. В каждой клетке записываем значение выходной функции, а переходы показываем стрелками (рис. 10).

К1 = {S3,S2} К2 = {S4,S1}

Рис. 10 Рис. 11

Если при обходе цикла по матрице не возникает противоречий и мы возвращаемся в клетку с меткой «начало цикла», то производится анализ матрицы и выделяются единичные состояния функции. В данном случае имеется лишь одна ячейка 01, где S2=0, а S3=1, которая соответствует единичному значению функции К1. Понятно, что .

Y1 = {S1, S2}. Y1 = {S1, S2, S3}

Рис. 12 Рис. 13

Аналогично строим матрицу для функции К2 (рис. 11). .

Для функции Y1 существенными переменными являются S1 и S2. Строим также матрицу для этих переменных (рис. 12). Однако при переходе S2 –возникает противоречие – функция равна 1, а ячейка 00 соответствует нулевому значениюY1. Следовательно, на участке противоречия «S2 –» необходимо выбрать квазисущественную переменную, которая по определению «меняла бы свое состояние на данном участке нечетное число раз». Следует однако сказать, что обычно выбирается переменная, меняющая свое состояние один раз. Для нашего случая можно выбрать, например,S3. Таким образом, функция Y1 доопределяется еще одной переменной, Y1 = {S1, S2, S3}, для этих трех переменных строится матрица Карно (рис. 13), в которой цикл благополучно замыкается. Здесь уже три ячейки (000, 001 и 011) соответствуют единичным состояниям функции, поэтому для определения минимальной формы используем методику с выделением подкубов по единицам, получаем

.

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

Участки противоречий можно установить заранее без построения матрицы. Для этого нужно выписать последовательно в строчку все состояния существенных переменных, которые они принимают в течение цикла. Там, где одна и та же переменная имеет рядом два противоположных состояния, как правило, возникает противоречие. Например, дляY1 цепочка изменения состояний переменных в цикле такова:

––S2 – –S1 – .

Здесь налицо участок противоречия «S2 –» и, учитывая, что цикл работы автомата замкнут, участок «S1 –». Оба эти противоречия можно разрешить включением квазисущественной переменнойS3, тогда получим цепочку ––S2 – ––S1 – S3 –, где противоречий уже не наблюдается.

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

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

Рассмотрим алгоритм синтеза последовательностных автоматов блочным методом с использованием матриц Карно. При этом следует отметить, что первые три пункта – такие же, как и при синтезе комбинационных.

1. Производится анализ автоматического устройства и т.д.

2. Условие работы автомата описывается графом.

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

4. Производится анализ графа и выявляются участки явных противоречий (будем называть явными противоречиями те, которые легко можно определить заранее при анализе графа, не начиная синтеза, в отличие от неявных, которые «выплывают» лишь в процессе синтеза). Такие участки имеют место в случаях, когда одно из ребер графа помечено подряд двойным изменением состояния одной и той же переменной или одна и та же переменная меняет состояние на входящем в вершину ребре и на исходящем из этой же вершины ребре (рис.14, а и б)

Рис 14

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

а) элемент памяти устанавливается на таком участке противоречия, где нет возможности использовать какую-либо квазисущественную переменную;

б) если вводится несколько элементов памяти, то следует последовательно по циклу производить их «включение», а затем в том же порядке их «выключение», что даст возможность закодировать весь цикл и обеспечит минимальное количество памяти;

в) если число противоречий нечетное и «выключение» последнего элемента памяти не находит места, то это следует сделать в самом конце цикла.

6. Производится построение расширенного графа, в котором элементы памяти записываются как равноправные функции, а моменты их «включения» и «выключения» – как равноправные события. Следует помнить, что элемент памяти здесь одновременно играет роль и функции, и входной переменной. Таким образом, количество тактов в цикле увеличивается на величину 2k, где k – количество элементов памяти.

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

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

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

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

В качестве примера произведем синтез и спроектируем дискретный автомат, управляющий технологической установкой, состоящей из трех рабочих силовых механизмов А, В и С, представленных функциональной схемой (рис. 15).

Рис 15

Дадим коротко анализ работы механизмов. Механизм А возвратно-поступательного действия с путевым контролем концевыми выключателями S1 и S2 приводится в движение электродвигателем М1 через редуктор и передачу винт-гайка. Управление производится с помощью реверсивной электромагнитной муфты с электромагнитами Y1 и Y2. Двигатель при этом может быть включенным в течение всего цикла, контактор К1 – использоваться в качестве пускового реле, а его блокировочные контакты – для блокировки кнопки «Пуск».

Механизм В вращательного действия (например, поворотный стол) приводится в движение электродвигателем М2. Его положение контролируется концевым выключателем S3, на который поочередно воздействует один из двух кулачков. Условимся «прямым» ходом «В» считать первую половину оборота механизма, а обратным «» – вторую половину оборота. Управляет механизмом контактор К2.

Механизм С – силовой пневмоцилиндр возвратно-поступательного действия. Контроль перемещения здесь осуществляется также концевыми выключателями S4 и S5, а управление – двухпозиционным пневмораспределителем одностороннего действия с электромагнитом Y3.

Таким образом, основными исполнительными механизмами (выходными функциями автомата) будут являться Y1, Y2, Y3 и К2, а входными переменными – S1, S2, S3, S4 и S5.

Пусть последовательность работы механизмов определится алгоритмом

,

тогда исходное состояние всей технологической установки (начало цикла автомата) будет характеризоваться следующими состояниями входов и выходов: S1=1, S2=1, S3= 0, S4=1 и S5= 0; Y1= 0, Y2= 0, Y3= 0 и К2=1, соответственно S1, S2, ,S4 и ; К2,,и.

Граф функционирования автомата при заданном алгоритме будет

.

Анализ графа показывает, что очевидны три явных участка противоречий. Используя приведенные выше правила, определим места установки элементов памяти:

.

Тогда расширенный граф будет выглядеть следующим образом:

Теперь можно приступать непосредственно к синтезу, т.е. к нахождению булевых функций, определяющих выходные функции автомата. Разбиваем автомат на блоки, соответствующие выходам автомата, и для каждого блока выявляем существенные и квазисущественные переменные. В качестве квазисущественных при возможности следует использовать элементы памяти. Чтобы не перестраивать матрицы Карно при возникновении противоречий, имеет смысл предварительно анализировать цепочки состояний существенных переменных и выбирать заранее все необходимые квазисущественные переменные. Начнем с наиболее сложной функции К2, поскольку она четыре раза меняет свое состояние в течение цикла. Ее существенными переменными будут S2, S3, S4; К2 = S2, S3, S4

Проанализируем цепочку состояний этих переменных в цикле:

–S2 – –S3 –––S4 ––S3 –

Здесь очевидны три возможных противоречия, поэтому доопределяем функцию элементами памяти Р1 и Р2; К2 = S2, S3, S4, Р1, Р2. Сделаем проверку еще раз: – S2 – – Р1 –S3 ––– Р2 –S4 –––S3 –– , чтобы убедиться , что функция будет определена.

Строим матрицу Карно для пяти переменных, определяем начало цикла и отмечаем переходы по клеткам матрицы, проставляя соответствующее значение выходной функции К2.

Производим минимизацию функции, выделяя подкубы по единицам, и получаем булеву функцию в форме ДНФ:

К2 = +S2·+S4·Р1·Р2.

Аналогично определяем все другие выходные функции автомата.

Y1= Р2, S2; – S2 –– Р2 ––.

Y1 = Р2, S2, Р1;

–S2 – Р1 –– Р2 –––.

Y1 = ··

Y2=  S1, S3; – – – S3 –S1 –– S3 –.

Y2 =  S1, S3, Р1;

– ––Р1 – S3 –S1 ––– S3 –.

Y2 = ·S3·Р1

Y3 =  S1, Р2; – – S1– Р2 – –.

Y3 =  S1, Р2, Р1;

– –Р1 – S1– Р2 –––.

Y3 = S1·Р1·

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

Р1 = S3; – –S3 ––S3 –, здесь противоречия очевидны, поэтому доопределяем функцию самими же элементами памяти Р1 и Р2.

Р1 = S3,Р1,Р2;

– –Р1 – S3 – Р2 ––– S3 ––

Р1 = S3·Р1 + ·

Р2 =  S5, S3; – – S3 – S5 –– – S3 –.

Р2 =  S5, S3, Р1, Р2;

– –Р1 – S3 – Р2 ––– S3 ––.

Р2 = S5 +·Р2 + Р1·Р2 = S5 + Р2·(+ Р1).

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

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

Пусть имеется автоматическая технологическая установка, состоящая из двух пневмоцилиндров, управляемых двухпозиционными четырехходовыми распределителями (рис. 16):

Рис. 16

Здесь исполнительными механизмами (выходами) являются электромагниты Y1, Y2, Y3 и Y4, а входными переменными – датчики путевого контроля S1, S2, S3 и S4, Пусть последовательность работы механизмов задана алгоритмом

.

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

.

В начале цикла работы, учитывая исходное положение механизмов, S1 = 1, S2 = 0, S3 = 1, S4 = 0. Состояние выходных функций – Y1 = 1, Y2 = 0 Y3 = 0, а что касается функции Y4, то у нее может быть и 0, и 1, в зависимости от того, когда будет снят управляющий сигнал, а это покажут результаты синтеза.

Определим все функции по известной методике:

Y1 = S3, S4; ––S4 – –S3 –

Для устранения противоречия доопределим функцию квазисущественной переменной S2. Построим матрицу Карно для трех этих переменных, обозначив переходы и проставляя в клетках значения функции.

Проводя минимизацию с выделением подкубов по единицам, получим булеву функцию:

Y1 = S3 + S2·.

Однако учитывая, что распределитель является триггерным устройством и будет сохранять свое состояние и после снятия управляющего сигнала с электромагнитаY1, единичные значения в клетках матрицы 110 и 100 можно считать фиктивными (безразличными). Тогда для определения минимального значения функции Y1 достаточно выделить лишь один подкуб, который охватывает единицу включения (клетка 010). В этом случае функция будет определена так: Y1 = S3.

Для функции Y2 будут те же переменные, что и для Y1, поэтому и переходы в матрице будут теми же, только состояние функции будет альтернативное (вместо нулей – единицы и наоборот).

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

Y2 = S4.

Так же определяются функции Y3 и Y4: Y3 = S2 ; Y4 = S1. По сути дела, вся логика такого автомата сводится к элементарным функциям повторения. Предоставляем читателю самостоятельно проверить правильность этих зависимостей, а также определить по графу, на каких тактах цикла будет производиться снятие управляющих сигналов с электромагнитов Y1, Y2, Y3 и Y4, если реализовать полученные выражения.