Борис Цирлин
Рассматриваются дистрибутивные схемы - подкласс схем, не зависящих от скорости, являющийся промежуточным между последовательными и полумодулярными схемами. В этой статье коснемся только параллельно-последовательных схем, подкласса дистрибутивных. Эти схемы были описаны в книге "Автоматное управление асинхронными процессами в ЭВМ и дискретных системах, вышедшей под редакцией В.И.Варшавского в 1986 г. Класс параллельно-последовательных (далее ПП) схем включает в себя все последовательные, как это можно понять из его названия. Подсчитано количество таких схем, состоящих из двух и трех элементов. Определены и подсчитаны неизоморфные ПП схемы.
Введение
Предметом исследования являются дистрибутивные схемы, подкласс схем, независящих от скорости, определенных Д. Маллером. Этот подкласс включает в себя последовательные схемы, обсуждаемые в статьях "Последовательные схемы" ч. 1, ч. 2, ч. 3 и ч. 4. В свою очередь, дистрибутивные являются подклассом полумодулярных схем, рассмотренных в статье с очевидным названием. Обсуждаемые ПП схемы занимают промежуточное положение между последовательными и дистрибутивными.
Как и в этих статьях ограничимся только автономными схемами, т.е. не имеющими внешних входов и выходов, т.к. для полумодулярных это ограничение обходится (по известной теореме Малера) размыканием провода, соединяющего выход любого элемента схемы со входами остальных ее элементов.
Напомним, что схемы описываются системами из n логических уравнений, задающих поведение каждого из n ее элементов. Для элемента в каждом из G = 2**n состояний схемы определено понятие "возбуждения" - когда значение его выхода не соответствует значению определяющей его логической функции. Задание схемы и определение ее свойств (принадлежность тому или иному классу) осуществляется с помощью "вектора возбуждений", т.е. последовательности Q из G чисел, где каждая компонента Q[i] вектора возбуждение может иметь одно из G возможных значений (0=<Q[i]<G) соответствующих номерам элементов с возбуждёнными выходами, или их суммам, если возбуждений несколько. Очевидно, что таких векторов может быть N = G**G = (2**n)**(2**n), что и определяет число различных схем из n элементов.
Чтобы использовать уже опробованные методы подсчета схем, для подкласса ПП надо (как, в свое время, для последовательных и полумодулярных) определить локальные признаки нарушения этого свойства, которые можно формализовать используя компоненты Q[i] вектора возбуждения схемы.
Признак принадлежности схемы классу ПП.
Очевидно возбужденный выход элемента может стать устойчивым двумя способами: либо изменив значение выхода через время, определяемое его физической задержкой, либо за счет изменения входного набора его логической функции при котором ее значение придет в соответствие с не изменившимся выходом элемента. Второй вариант может привести к нарушениям правильного функционирования схемы (состязаниям, например) и разработчик стараются его избежать.
В полумодулярных схемах в каждом состоянии возбужденный выход может стать устойчивым при переходе схемы в другие состояния только за счет изменения своего значения (второй вариант исключен).
В последовательных схемах в каждом состоянии возбужден выход не более одного элемента. В силу этого второй вариант перехода из возбужденного состояния выхода элемента в устойчивое в них не возможен — ничто не изменит его входной набор, кроме, разве что, изменения значения выхода самого этого элемента. Т.е. последовательные схемы являются и полумодулярными, точнее, являются их подклассом.
Здесь требование полумодулярности, как и последовательности, относится ко всем состояниям схемы. То же предположим и для ПП схем.
Чтобы упростить словесную формулу принадлежности схемы классу ПП введем некоторые определения.
Состояние схемы называется следующим для данного, если схема в него переходит путем изменения значения выходов одного или нескольких элементов, возбужденных в данном.
Следующее для данного состояния схемы называется финальным, если оно отличается от данного только значениями выходов всех элементов, возбужденных в данном состоянии.
Полумодулярная схема является ПП, если при возбуждении в данном состоянии выходов одного или нескольких элементов она не может не оказаться в финальном состоянии.
Для последовательных схем каждое следующее состояние является и финальным, откуда очевидна их (схем) принадлежность подклассу ПП. Что касается отношения подклассов полумодулярных и ПП схем, то оно очевидно из определения последних.
Формализация признаков ПП схем
Как и в статье "Полумодулярные схемы" рассмотрим условия принадлежности схем интересующему подклассу только для случаев n = 2 и 3, т. к. из-за взрывного роста вычислительной сложности уже при n = 4 предлагаемые алгоритмы невозможно реализовать на доступных вычислительных средствах за приемлемое время.
Как было показано в той же статье, для i-го состояния схемы финальным является состояние
j = i^Q[i],
где Q[i] - i-я компонента вектора Q возбуждения схемы. При этом для n = 2 потенциальную опасность с точки зрения нарушения полумодулярности имеют те состояния i для которых Q[i]=3 (возбуждены оба элемента), причем следующие для них, кроме финального, состояния j = i^1 и j = i^2. Достижение же финального состояния безопасно, как с точки зрения полумодулярности, так и, интересующей нас, ПП схем.
Иное дело два других следующих состояния для i-го: i^1 и i^2. Как было показано, для первого случая условие нарушения полумодулярности:
(Q[j] == 0) or (Q[j] == 1).
Если же Q[j] == 3, то полумодулярность сохраняется (элемент номер 2 хотя и не изменил значение, но сохранил возбуждение), а ПП нарушается, т.к. появляется возможность возврата из j-го состояние в i-е, т.е. образуется цикл между двумя этими состояниями, а финальное может быть и не достигнуто. Добавив это условие в предыдущее, получим:
(Q[j] == 0) or (Q[j] == 1) or (Q[j] == 3),
которое можно очевидным образом упростить:
Q[j] != 2
Очевидно, для второго случая это условие имеет вид:
Q[j] != 1.
В цитируемой статье описана программа для подсчета схем различных подклассов. Подставив в нее полученную проверку на ПП для n = 2, получим число ПП схем
Npp = 93.
Для n = 3 программа, естественно, имеет ту же структуру с той лишь разницей, что потенциально опасных компонент вектора возбуждений не одна, как в предыдущем случае, а четы��е - три пары и одна тройка.
Возбуждение первого, второго и третьего элементов соответствуют значениями 1, 2 и 4 компоненты Q[i] вектора возбуждений, а возбуждение пар выходов:
Q[i] = 3 = 1+2
Q[i] = 5 = 1+4
Q[i] = 6 = 2+4
Тройка же возбужденных элементов даст:
Q[i] = 7 =1+2+3
Принцип проверки потенциально опасных компонент Q[i] сохраняется тот же, что и для n = 2, а именно: в состоянии j, следующим за i-м (если j не финальное) должны быть возбуждены выходы тех и только тех элементов которые были возбуждены в i-м, но не сработали при переходе в j-е состояние. Причем для тройки, если переход вызван срабатыванием только одного элемента, то в следующем состоянии будет возбуждена пара не сработавших и наоборот.
Программный блок проверки на ПП, построенный по этому принципу, приведен на листинге 1. Подставив этот блок в упомянутую программу для n = 3, получим
Npp = 92960.
Заключение
Полученные результаты хорошо согласуются с иерархическим положением подкласса ПП схем, который является промежуточным между полумодулярными и последовательными. Все они включены в таблицы 1 и 2 из которых также видно, что автор не мог не воспользоваться открывшейся возможностью разобраться и с изоморфизмом для обсуждаемых дистрибутивных схем.
Приведенные данные для сравнения даны в совокупности с аналогичными из статьи "Изоморфные схемы"
