- [ 0 в противном случае; J 1, если на ;-ю горизонталь поступил вызов; Л6- \ 0 в противном случае;

Л ( 1, если свободен прибор, подключенный к 1-й вертикали; Л7- \ 0 в противном случае,сп

Используя эти операторы и логические условия, составим следующие ЛСА:

а)для первого режима

Л1 = i3 Fi pi fi РзТл4л pt T3 Pa T4 /2 T4 л1АЛ coT2 ,3 As cot2 I1 ; (3.9)

б)для второго режима

ЛЦ = I1 FjPt Г-Ps T1 iF p-, T3/?, T4 л1 /4<o T1 i3 Л3 a T112.(3.10)

Очевидно, микропрограммный автомат, реализующий условия, заданные ЛСА (3.9) и (3.1.0), должен иметь один внешний вход, одно из состояний которого. пусть г=0. сопоставим с ЛСА 2Ii, а состоян.ие г=1 - с ЛСА 21 ц.

Если на внешнем входе /-=0, то выполняется первый режим работы микропрограммного автомата в соответствии с ЛСА Яг; если г=1-то второй в соответствии с ЛСА Мп.

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

ЛСА.

Иногда процесс работы ДУ приходится представлять в виде иерархии частных ЛСА. Например, ДУ

работает в двух режимах, первый из которых удобно представить в виде трех этапов, а второй - двух.

После выполнения первого режима ДУ переходит к выполнению второго, затем вновь первого и т. д.

При этом первый этап первого режима работы ДУ совпадает с первым этапом второго режима, а на

остальных этапах алгоритмы функционирования ДУ различаются.

Вначале составляем ЛСА для каждого из этапов: ЛСА 2Ii, описывающую алгоритм функционирования ДУ на первом этапе как первого, так и второго режимов работы ДУ; ЛСА Щ и 2tg на втором и третьем этапах первого режима и 2Л на втором этапе второго режима. Далее задаем последовательность выполнения частных ЛСА для каждого из режимов. Пусть aStiSIat/t11 Для первого режима и 2[„ =2Л21:4 для второго режима. Затем составим общий алгоритм функционирования

ДУ в виде ЛСА

ЭД = л 9Ii ЭД„ (of = Л л л q]2 Яд л SIi л cof1.(3.11)

Таким образом, общая ЛСА составлена за три шага: вначале были составлены частные ЛСА этапов, затем - частные ЛСА режимов и только после этого-общая ЛСА, задающая условия работы микропрограммного автомата.

Легко видеть, что в ЛСА (3.11) частная ЛСА 21, встречается дважды, так как Я, встречается как в Я;,так и в Sin. Однако нетрудно построить общую ЛСА с одним вхождением ЛСА 2I,. Для этого, как и в предыдущем примере, введем дополнительное логическое условие г, одно из значений которого (г=0) припишем ЛСА 2Ii, а второе (г== 1) - ЛСА 2[„.

Поскольку как ЛСА 2t,, так и ЛСА 2Г„ начинаются с ЛСА а, общая ЛСА также будет начинаться с ЛСА 2Ii. Однако после выполнения ЛСА 21, в первом режиме следует выполнять ЛСА 2Л, а во втором - ЛСА Sл. Поэтому по окончании 21, необходимо приписать логическое условие г, значение которого и укажет на необходимость выполнения одной из этих двух ЛСА, т. е. общая логическая схема должна иметь вид Я = л 2Ff f2 21Л2 щ ллзЛю+i.(3.12)

Из ЛСА (3.12) видно, что при г=0 выполняется ЛСА SI,, а при r=l-ЛСАЛп. Однако, поскольку в данном случае, в отличие от предыдущего примера, режимы чередуются, в процессе работы МА необходимо менять значение логического условия г. Так, после выполнения ЛСА 2ti значение логического условия г должно измениться с нуля на единицу, а после выполнения ЛСА 2I„ - с единицы на нуль. Очевидно, изменение значения г здесь уже не может производиться извне, а поэтому в ЛСА необходимо ввести специальные операторы, обычно обозначаемые через f{, которые и будут устанавливать необходимые значения логического условия г.

Пусть Fi устанавливает значение г=0, а. Рц-значение г=\. Тогда окончательно общая ЛСА может быть записана в виде

ЯЛЛЭДЛзэДзЛЛду2л"л32л®4-(3.13)

Следует заметить, что функции операторов f{ могут выполнять операторы частных ЛСА.

3.4. Составление логических схем алгоритмов

Условия работы МА не всегда легко записывать непосредственно на языке ЛСА. Оказывается, более удобно алгоритм функционирования вначале записать на так называемых вспомогательных языках, а затем от них уже перейти к ЛСА. В качестве таких вспомогательных языков рассмотрим два: язык формул переходов (ФП) и язык секвенций [З].

Алгоритм функционирования автомата, в том числе и МА, представим в виде причинно-следственных связей операторов (актов алгоритма) или ФБ, в которых эти операторы реализуются. В таких причинно-следственных связях выделим два типа операторов: операторы-предшественники, т. е. такие, которые к рассматриваемому моменту времени закончили свою работу, и операторы-последователи, т. е. такие, которые должны выполняться после завершения работы операторов-предшественников. Такие причинно-следственные связи между k+\ операторами Ло,..., A.k заданного алгоритма функционирования можно представить в виде матричной схемы алгоритма (МСА) [3]

ЭД==Л,4,(3.14)

где каждая строка сопоставлена с оператором-предшественником Ai, i==0,l,... ,k-1, а столбец-с оператором-последователем Л;, /=1,... , k. Элемент а,, МСА представляет собой логическую функцию от логических переменных (логических условий) pi, р„, т. е.

viS=f(Pb •-, Рп),(3.15)

определяющих условия выполнения оператора А, после окончания работы оператора Ai.

Заметим, что МСА и матрица переходов автомата (3.8) имеют много общего. Так, если операторы сопоставим с внутренними состояниями автомата, а вместо функции а„ выпишем те наборы значений всех логических условий pi, рп (т. е. всех входных переменных), на которых аг,==1, то МСА превратится в матрицу переходов.

Условие выполнения оператора А] после любого оператора МСА может быть представлено в виде дизъюнкции отмеченных функций ciij столбца А, МСА, т. е. в виде

V "„л,ьл,(3.16)

(•=0г.....k- 1

называемой секвенцией.

Для простоты в секвенции функции aijAi, где аЛ-ssO, не выписываются. Очевидно, если будут выписаны секвенции для каждого из k столбцов МСА, то полученное секвенциальное описание автомата будет задавать алгоритм его функционирования.

Так как в секвенциях не выписываются функции аЛ==0, то секвенциальное описание, очевидно, задает алгоритм функционирования автомата значительно более компактнее, чем МСА, а следовательно, и матрица, и таблица переходов.

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

А1 -> V aij Aj(317)

j=1,.., k

называемую формой переходов (ФП), или формулой Дьяченко.

В ФП, как и в секвенции, функции а<з=0 не выписываются. Таким образом, если секвенция (3.16) определяет подмножество у,-= {Aji,...,Ajrj}, 0<:rj-Ak, операторов-предшественников из множества М={Ао, Ai,..,Ak}, после выполнения которых при условиях, определяемых функциями (3.15), должен выполняться оператор-последователь А, (рис. 3.12,а), то формула Дьяченко (3.17) определяет подмножество рг= {Ац,... ,Агг, }, 0<ri<S:k, операторов-последователей из множества операторов М (рис. 3.12,6).

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

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

4

Рис. 3.1!

В теории автоматов разработан достаточно эффективный метод перехода от секвенций к ФП, изложенный в [З]. Однако мы рассмотрим более громоздкий, но значительно более понятный метод. Громоздкость метода вытекает из того, что необходимо строить МСА которая, как указывалось выше, не обеспечивает компактности описания алгоритма функционирования МА.

Пример 37 Пусть проектировщиком составлено смешанное описание алгоритм •ЛнкционйрованияМА, включающее две формулы переходов:

для операторов Ло и Аъ при этом получим

ляютсГЛмиC=ЛopЛ, -ЛЛ~Л

63

Аг А2 А3 Ak

Ах

А9

Pi Pi

Pi Р2

Рассмотрим теперь первую секвенцию (для оператора Аз). Так заполним столбец Аз матрицы и получим

(3.18)

как секвенц. ия соответствует столбцу МСА, то по

21 =

Ао Аг А, А,

лх л2 л3 Pi P~i

Pl

Pi Pi

Ah

PlPi

(3.19)

Затем заполним столбец Ai по второй секвенции. При этом заметим, что элементы Ctoi и 02i уже заполнены по ФП для операторов А» и Ла. Поэтому к тем элементам ai, МСА, которые были заполнены ранее, логически (дизъюнктивно) прибавляем соответствующие логические функции из рассматриваемой секвенции и при возможности упрощаем их. В результате получаем

(3.20)

Аналогично заполняем второй и четвертый столбец МСА по третьей и четвертой секвенциям соответственно.