Перейдем к вычислению логических функций по графу для более широкого класса поведений. Будем рассматривать циклические автономные поведения, не содержащие кратных сигналов (или по другому: не содержащие индексированных событий). Еще одно ограничение: для удобства не будем рассматривать соединение параллельных ветвей по ИЛИ. Рассматриваем только соединение по И, то есть событие инициируется только тогда, когда сработают все его события-предшественники.
Для описания поведения будем использовать STG, но с дополнительными ограничениями. Для каждого плэйса количество входящих в него и выходящих из него дуг равно строго по одной. Соответственно, плэйс с входящей и выходящей дугами можно рассматривать как одну дугу, соединяющую два события (перехода). Соответственно маркировка перемещается по дугам. Так как поведения с кратными сигналами сейчас не рассматриваются, индексы при событиях запрещены, они не нужны. Пустые события запрещены. Также запрещена ситуация, когда две дуги, входящие в одно событие, выходят из событий, которые не параллельны друг другу (частный случай — из одного и того же события). Цель этого — избавиться от дуг, не несущих смысловой нагрузки. В остальном рассматривается корректное (нормальное, живое, безопасное) с точки зрения STG поведение с учетом вышеизложенных ограничений. Поведение не содержит CSC конфликтов.
Определение 1. Событие, в которое входит дуга, является следствием события, из которого эта дуга выходит. И наоборот, событие, из которого выходит дуга, является причиной события, в которое эта дуга входит.
Определение 2. Путь — бесконечная последовательность событий — результат изменений маркировки графа, начиная с какой-то конкретной. Каждое событие входит в последовательность бесконечное количество раз. Каждое такое вхождение уникально.
Определение 3. След события A — путь, в котором все события или непосредственное следствие события A, или результат транзитивного замыкания отношения следственности событий относительно события A. Начальная маркировка для следа события A устанавливается следующим образом. При произвольном изменении маркировки, после того как сработает событие A, маркеры в выходных дугах события A фиксируются. Далее происходит движение остальных маркеров до тех пор, пока движение маркеров не станет невозможным без снятия фиксации маркеров в выходных дугах события A. Получившаяся маркировка и есть начальная маркировка для следа события A.
Определение 4. Введем отношение упорядоченности для трех событий (A, B, C). Три события упорядочены (записывается A>B>C) тогда и только тогда, когда для любого следа события A первое вхождение события B в последовательность всегда будет происходить раньше, чем первое вхождение события C.
Замечание. Событие A может быть параллельно обоим событиям B и C (или только C), либо оба события A и B могут быть параллельны событию C.
Варианты расположения упорядоченных событий A, B и C (A>B>C).
Определение 5. Сигнал b (переключения B1 и B2) подхватывает сигнал a (переключения A1 и A2) относительно событий X и Y (события X и Y параллельны или совпадают), если выполняются следующие условия:
1) X>A1>A2;
2) если событие A2 параллельно событию X и не параллельно событию Y, то X>A2>Y;
3) Y>B1>B2;
4) если событие B2 параллельно событию Y и не параллельно событию X, то Y>B2>X;
5) Y>B1>A2;
6) если событие A2 параллельно событию Y и не параллельно событию X, то Y>A2>X.
Замечание 1. Условия 1, 2 и 3, 4 задают упорядоченность переключений сигналов a и b соответственно. Условия 5, 6 задают упорядоченность подхватывающего события B1 и подхватываемого события A2.
Замечание 2. В качестве события X может выступать событие A1. В этом случае условия 1 и 2 вырождаются.
Замечание 3. В качестве события Y может выступать событие B1. В этом случае условия 3, 4 и 5 вырождаются.
Замечание 4. В качестве события X может выступать событие A1, а также одновременно в качестве события Y может выступать событие B1. В этом случае условия 1, 2, 3, 4 и 5 вырождаются.
Теперь приступим к рассмотрению, что такое импликанта. Импликанта характеризуется событиями, в результате наступления которых импликанта меняет свое значение.
Определение 6. Событие, в результате наступления которого импликанта И (ИЛИ) меняет свое значение с 1 (0) на 0 (1), будем называть правой границей импликанты. Сигнал, соответствующий данному событию, будем называть включающим. Импликанта при этом включается.
Определение 7. Событие, в результате наступления которого импликанта И (ИЛИ) меняет свое значение с 0 (1) на 1 (0), будем называть левой границей импликанты. Сигнал, соответствующий данному событию, будем называть выключающим. Импликанта при этом выключается.
Определение 8. Импликанту, у которой какие-либо две правые (или же какие-либо две левые) границы не параллельны друг другу, будем называть прерывающейся.
Пока прерывающиеся импликанты рассматривать не будем. К их рассмотрению вернемся ниже.
Итак, мы имеем: все правые границы импликанты попарно параллельны друг другу, также и левые границы импликанты попарно параллельны друг другу.
Важное свойство. Импликанта включается при наступлении хотя бы одного события, являющегося правой границей импликанты. Импликанта выключается только при наступлении всех событий, являющихся левыми границами импликанты.
Теперь осталось выявить свойства сигналов, образующих импликанту.
Определение 9. Сигнал, входящий в состав импликанты, будем называть переменной.
Первое свойство переменных. Включающие и выключающие сигналы являются переменными.
Второе свойство переменных. Для всякой выключающей переменной (одно из переключений которой — левая граница импликанты L, другое — некоторое событие X) должно существовать событие — какая-то правая граница R этой же импликанты такое, что либо X и R это одно и то же событие, либо R>X>L.
Третье свойство переменных. Для всякой включающей переменной (одно из переключений которой — правая граница импликанты R, другое — некоторое событие X) должно существовать событие — какая-то левая граница L этой же импликанты такое, что либо X и L это одно и то же событие, либо R>X>L.
Четвертое свойство переменных. Для всякой переменной (переключения X1 и X2), не являющейся включающей или выключающей, должны существовать два события: какая-то левая граница импликанты L и какая-то правая граница импликанты R такие, что R>X1>L и R>X2>L. В противном случае импликанта не могла бы сохранять неизменное значение в выключенном положениии.
Пятое свойство переменных. Для всякой пары: какая-то включающая переменная и какая-то выключающая переменная, должна существовать последовательность подхватывающих друг друга переменных относительно каких-то правых границ импликанты (для разных подхватов правые границы могут различаться), начинающаяся с данной включающей переменной и оканчиваюшаяся данной выключающей переменной. В противном случае импликанта не могла бы сохранять неизменное значение во включенном положении.
Шестое свойство переменных. Для всякой включающей переменной a, если правой границей импликанты является событие a+ (a-), то такая переменная a входит в запись импликанты И (ИЛИ) с инверсией, а в запись импликанты ИЛИ (И) без инверсии. Для всякой выключающей переменной a, если левой границей импликанты является событие a- (a+), то такая переменная a входит в запись импликанты И (ИЛИ) с инверсией, а в запись импликанты ИЛИ (И) без инверсии.
Седьмое свойство переменных. В силу четвертого свойства переменных, для всякой переменной a, не являющейся включающей или выключающей, существуют правая граница импликанты R и левая граница импликанты L такие, что R>a+>L и R>a->L. Если R>a+>a-, то такая переменная a входит в импликанту И с инверсией, а в импликанту ИЛИ без инверсии. Если R>a->a+, то такая переменная a входит в импликанту И без инверсии, а в импликанту ИЛИ с инверсией.
Семь перечисленных свойств переменных являются необходимыми свойствами импликанты. Также этих свойств достаточно для описания импликанты.
Замечание. Вышеприведенное описание импликанты не запрещает ситуацию, когда какая-то левая граница импликанты может быть параллельна какой-то правой границе этой же импликанты. Смысл этого явления заключается в том, что в зависимости от скорости параллельных процессов такая импликанта в реальном времени может стать необязательной для реализации соответствующего сигнала и в реальном времени она может не выключиться (если правая граница сработает раньше чем левая граница).
Теперь рассмотрим как из импликант строится нормальная форма логической функции.
Определение 10. Если для какого-то состояния импликанта находится в выключенном положении (значение импликанты И (ИЛИ) равно 1 (0)), будем говорить, что импликанта покрывает это состояние.
Рассмотрим некий сигнал x, для которого надо вычислить логическую функцию. Для построения ДНФ (КНФ) необходимо И(ИЛИ)-импликантами покрыть все состояния, на которых функция x равна 1 (0). При этом необходимо, чтобы ни одна из этих И(ИЛИ)-импликант не покрывала состояния, на которых функция x равна 0 (1). Также при вычислении логических функций необходимо учитывать специфику схемотехники: импликанты должны «перекрываться». То есть, если в каком-то состоянии импликанта может включиться (то есть может быть инициировано событие, являющееся правой границей этой импликанты) и при этом значение функции сигнала x не изменится при этом переключении, то должна существовать другая ипликанта, которая покрывает это состояние и не включается при инициации данного события.
Теперь нам надо разъяснить три вопроса. Что такое состояние в терминах графа? Как определить состояния, на которых функция сигнала x равна 1 (0)? Как определить состояния, которые импликанта покрывает?
Начнем с состояний. Всякая достижимая маркировка это состояние. Поскольку CSC конфликты отсутствуют, каждой достижимой маркировке соответствует уникальное состояние (достижимое). На недостижимых состояниях значение функции произвольно и рассматривать их нет необходимости. Таким образом, каждое состояние, которое мы рассматриваем, однозначно описывается соответствующей маркировкой. Положение каждого маркера однозначно определяется дугой, которую он маркирует. Каждой дуге однозначно сопоставляется пара (упорядоченная) событий: событие, из которого дуга выходит, и событие, в которое дуга входит. Таким образом, всякое достижимое состояние однозначно описывается множеством, состоящим из упорядоченных пар событий.
Определение 11. Пару событий, обозначающую маркированную дугу, будем записывать {P, S}, где P — событие причина, а S — событие следствие.
Определение 12. MM будем называть множество из упорядоченных пар {P, S}, которое описывает какое-то достижимое состояние.
Теперь определим для каких состояний значение функции x равно 1, а для каких — 0. Пусть причинами события x+ являются n событий A1, A2, ..., An, а причинами события x- являются m событий B1, B2, ..., Bm.
Значение функции x равно 1 если:
1) для каждого i от 1 до n, пара {Ai, x+} принадлежит множеству MM;
2) пара {x+, S}, такая что x+>S>x-, принадлежит множеству MM;
3) пара {P, S}, такая что x+>P>x- и x+>S>x-, принадлежит множеству MM;
4) пара {P, x-}, такая что x+>P>x-, принадлежит множеству MM и существует i от 1 до m, такой что пара {Bi, x-} не принадлежит множеству MM.
Значение функции x равно 0 если:
1) для каждого i от 1 до m, пара {Bi, x-} принадлежит множеству MM;
2) пара {x-, S}, такая что x->S>x+, принадлежит множеству MM;
3) пара {P, S}, такая что x->P>x+ и x->S>x+, принадлежит множеству MM;
4) пара {P, x+}, такая что x->P>x+, принадлежит множеству MM и существует i от 1 до n, такой что пара {Ai, x+} не принадлежит множеству MM.
Теперь выясним какие состояния покрывает импликанта. Пусть у импликанты n левых границ L1, L2, ..., Ln и m правых границ R1, R2, ..., Rm.
Импликанта не покрывает состояние, описываемое множеством MM, если хотя бы для одной из пар {P, S}, принадлежащей множеству MM, выполнено следующее условие: существуют такие i от 1 до n и j от 1 до m, что
либо 1) Li и S это одно и то же событие и Rj>P>Li,
либо 2) Rj и P это одно и то же событие и Rj>S>Li,
либо 3) Rj>P>Li и Rj>S>Li.
Это утверждение верно в силу пятого свойства переменных.
Импликанта покрывает состояние, описываемое множеством MM, если ни для одной из пар {P, S}, принадлежащих множеству MM, не выполненяется следующее условие: существуют такие i от 1 до n и j от 1 до m, что
либо 1) Li и S это одно и то же событие и Rj>P>Li,
либо 2) Rj и P это одно и то же событие и Rj>S>Li,
либо 3) Rj>P>Li и Rj>S>Li.
Это утверждение верно в силу второго, третьего и четвертого свойств переменных.
Образно говоря, импликанта покрывает состояние, если все маркеры находятся между левыми и правыми границами импликанты. Если хоть один маркер расположен вне этих границ, то импликанта это состояние не покрывает.
Теперь у нас есть инструмент для вычисления нормальных форм (не выяснен, правда, еще вопрос с прерывающимися импликантами). Но нас интересуют минимальные нормальные формы (с учетом специфики схемотехники). Прежде чем продолжить дальше, вернемся к рассмотрению прерывающихся импликант. Рассмотрим И-импликанту для ДНФ сигнала x (случай с ИЛИ-импликантой для КНФ аналогичен). Пусть две левые границы одной и той же импликанты L1 и L2 не параллельны друг другу и L1>L2>x- (случай для двух правых границ рассматривается аналогично). Тогда должны существовать две правые границы импликанты R1 и R2 такие, что для пар как L1 и R2, так и L2 и R1 должны выполняться второе, третье, четвертое и пятое свойства переменных. Если существует левая граница L3, параллельная L1, то для пары L3 и R2 также должны выполняться вышеуказанные свойства (аналогично в случае существования соответствующих границ импликанты, которые параллельны границам L2, R1 и R2). Но, так как кратные сигналы не используются, должна существовать не прерывающаяся импликанта с границами L1 и R2 (и с параллельными им соответствующими границами, если таковые были у прерывающейся импликанты). При этом не прерывающаяся импликанта состоит из меньшего количества переменных и покрывает все состояния, покрываемые прерывающейся импликантой, на которых значение функции сигнала x равно 1. Отсюда вывод: прерывающиеся импликанты не являются экстремалями и они не могут быть использованы для вычисления минимальных функций.
Подробнее о вычислении минимальных функций в следующей части.
Автор: Быстров Сергей А.
