УНИВЕРСИТЕТ ИТМО
Кафедра «Технологии программирования»

Использование граф-схем и графов переходов при программной реализации алгоритмов логического управления. Часть 2

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

Пусть задан граф переходов автомата без выходного преобразователя с принудительным кодированием состояний (рис.8), в котором при импульсных переменных x1 и x2 генерирующие контура отсутствуют.

Рис. 8.

Кодирование названо принудительным, так как коды, определяющие состояния, совпадают со значениями выходных переменных, формируемых в соответствующих состояниях (вершинах). Этот вид кодирования использован ввиду того, что в рассматриваемом графе переходов комбинации значений выходных переменных во всех вершинах различны. Этот граф переходов предлагается реализовать ГСА4 [1] (рис.9), тело которой состоит из трех слоев.

Рис. 9.

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

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

Понимаемость этой граф-схеме придает также и то, что она обладает в отличие, например от ГСА2 (рис.2 [1]), глубиной, определяемой только одним переходом в графе переходов, что является чрезвычайно важным и полезным свойством этого класса граф-схем. Кроме того в этой граф-схеме за один проход в отличии от граф-схемы (рис.3 [1]) не приходится неоднократно пересчитывать значения ни одной выходной переменной, а в отличие от граф-схемы (рис.5 [1]) — многократно проверять значения одной и той же входной переменной. Эта граф-схема не только структурирована в традиционном понимании, но и хорошо организована в том смысле, что условные вершины с пометками Z и X не перемешаны между собой и с операторными вершинами.

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

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

Например, несмотря на то, что ГСА2 (рис.3 [1]), реализующая R-триггер, идеально соответствует принципам структурного программирования, она обладает двумя недостатками, затрудняющими ее чтение: пересчет значения z при x1 = x2 = 1 и отсутствие в модели указания в явном виде значения z при x1 = x2 = 0. Этих недостатков лишена граф-схема алгоритма с дешифратором состояний (рис.10), которая, несмотря на большую сложность по сравнению с граф-схемой (рис.3 [1]), понимается лучше.

Рис. 10.

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

Рис. 11.

4. Реализация автоматов без выходного преобразователя с принудительно-свободным кодированием состояний

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

Рис. 12.

Для того, чтобы различать вершины графа переходов, используем принудительно-свободное кодирование состояний автомата, введя отсутствующую в алгоритме управления внутреннюю переменную y (рис.13).

Рис. 13.

Название этого вида кодирования определяется тем, что значения части разрядов кода принудительно задаются значениями выходных переменных z, а значения остальных разрядов, обозначаемых переменными y, могут быть выбраны при программной реализации свободно (произвольно). На рис.14 приведена граф-схема алгоритма, эквивалентная этому графу переходов.

Рис. 14.

Зависимость состояний автомата от значений выхода z в рассмотренных граф-схем алгоритмов (рис.9, 10 и 14) может создать трудности при условии, что эти значения могут изменяться в других компонентах алгоритма управления. Поэтому сделаем независимыми состояния автомата от его выходных значений, перейдя к модели автомата Мура.

5. Реализация автоматов Мура с двоичным логарифмическим кодированием состояний

На рис.15 приведен граф переходов автомата Мура, реализующий счетный триггер, для рассматриваемого варианта кодирования, а на рис.16 — соответствующая ему граф-схем алгоритма.

Рис 15.

Рис. 16.

Тело этой граф-схемы является четырехслойным (дешифратор состояний, формирование значений выходов, реализация функций переходов, формирование следующего состояния). Недостатки этой граф-схемы состоят в значительной глубине пирамидального дешифратора и большом числе вновь вводимых переменных yi, где 0 < i < ]log s[ - 1; s — число состояний автомата. Первый из этих недостатков устраняется в разд. 6, а оба недостатка — в разд. 7.

6. Реализация автоматов Мура с двоичным (единичным) кодированием состояний

Такой вариант кодирования вершин графа переходов автомата Мура (рис.17), названный в [2] единичным (в j-ой вершине графа переходов только битовая переменная yj принимает значение равное единице, а в остальных вершинах значение этой переменной равно нулю), позволяет использовать в граф-схеме алгоритмов (рис.18) линейный дешифратор состояний вместо пирамидального, который применялся в граф-схемах алгоритмов автоматов Мура при других видах кодирования. Недостаток граф-схемы в этом случае состоит в еще большем (по сравнению с предыдущим случаем) числе вновь вводимых битовых переменных yj (0 < j < s - 1), каждую из которых приходится не только устанавливать, но и принудительно сбрасывать.

Рис. 17.

Рис. 18.

7. Реализация автоматов Мура с многозначным кодированием состояний

Все недостатки предыдущих вариантов кодирования устраняются при переходе к многозначному кодированию состояний автоматов [5, 6]. При этом для автоматов Мура, Мили и смешанных автоматов, реализуемых в виде одной компоненты, для кодирования состояний достаточно иметь одну переменную Y значности s, которую не требуется принудительно сбрасывать, так как она автоматически сбрасывается при переходе от одного значения к другому. При этом для реализации N-компонентного алгоритма управления (реализуемого N графами) с помощью указанных классов автоматов требуется N многозначных переменных Yj, где j=0,..., N-1. Этот вариант кодирования, практически нереализуемый при аппаратной реализации автоматов, по мнению автора, при отсутствии жестких ограничений на объем памяти программ и возможности работы с многозначными переменными должен стать основным при программной реализации автоматов.

На рис.19 в качестве примера приведена граф-схема алгоритма для рассматриваемого варианта кодирования, построенная по графу переходов автомата Мура счетного триггера (рис.7 [1]).

Рис. 19.

В этой граф-схеме за счет ухудшения понимаемости условная вершина с пометкой Y = 3 и вторая операторная вершина с пометкой z = 1 могут быть исключены.

Граф-схема алгоритма аналогичной структуры может быть построена для любого графа переходов автомата Мура. При этом в отличие от графа переходов такая граф-схема алгоритма всегда может быть планарной. Применение всего лишь одной промежуточной переменной при "хорошей" организации структуры делает использование граф-схем этого типа весьма привлекательным. Единственный недостаток, кроме громоздкости, такого типа структур (если умалчивание значений выходных переменных исключено) состоит в том, что так как в них связь между фрагментами осуществляется не непосредственно как в графах переходов, а по данным (значениям переменной Y), то визуальное обнаружение генерирующих контуров становится весьма затруднительным.

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

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

Рис. 20.

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

При этом отметим, что и один граф переходов являясь последовательным по состояниям обычно является параллельным по входам и выходам (например, графы переходов на рис.7 и 8).

8. Реализация автоматов Мили с многозначным кодированием состояний

В автоматах Мили, также как в автоматах Мура, могут использоваться различные виды кодирования состояний, однако, исходя из изложенного, рассмотрим только многозначное кодирование. На рис.8 [1] приведен граф переходов автомата Мили, реализующий счетный триггер при принятом варианте кодирования, а на рис.21 — соответствующая граф-схема алгоритма.

Рис. 21.

В этой граф-схеме могут быть исключены условная вершина с пометкой Y = 3 и вторые операторные вершины с пометками z = 1 и z = 0. Отличие этой граф-схемы от граф-схемы автомата Мура состоит в размещении слоя операторных вершин, помеченных значениями выходной переменной, не до дешифраторов значений входных переменных, а после них.

Второй пример реализации этого класса автоматов приведен на рис.22 для последовательностного одноразрядного сумматора (рис.10 [1]).

Рис. 22.

В этой граф-схеме для минимизации числа вершин слой значений выходной переменной z расположен после слоя со значениями следующего состояния P. Тело этой граф-схемы, состоящее всего лишь из девяти вершин, построено с помощью модификации метода Блоха, изложенной в [8].

9. Реализация смешанных автоматов с многозначным кодированием состояний

На рис.23 изображено тело граф-схемы алгоритма, реализующей смешанный автомат с флагом, представленный на рис.11 [1].

Рис. 23.

Эта граф-схема является пятислойной: дешифратор состояний, формирование значений выходных переменных, реализация функций переходов, формирование значений флага, формирование следующего состояния. В приведенной граф-схеме переменная x1 определяет содержимое счетного триггера (еще одной компоненты алгоритма управления), который также управляется и от другого источника информации — кнопки. В этой граф-схеме в отличие от графа переходов противоречивость устранена ортогонализацией и используется булев признак T вместо неравенства t > D.

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