Борис Цирлин

Рассматриваются дистрибутивные схемы - подкласс схем, не зависящих от скорости, являющийся промежуточным между последовательными и полумодулярными схемами.
Подсчитано количество таких схем, состоящих из двух и трех элементов. Определены и подсчитаны неизоморфные дистрибутивные схемы.

Введение

Предметом исследования являются дистрибутивные схемы, подкласс схем, независящих от скорости, определенных Д. Маллером. Этот подкласс включает в себя последовательные схемы, обсуждаемые в статьях "Последовательные схемы" ч. 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, получим число дистрибутивных схем

Nd = 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, получим

Nd = 92960.

Заключение

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

Приведенные данные для сравнения даны в совокупности с аналогичными из статьи "Изоморфные схемы"