Борис Цирлин

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

Предметом исследования являются полумодулярные схемы (далее ПМС), подкласс схем,
независящих от скорости, определенных Д. Малером в 1961 году. Этот подкласс включает
в себя последовательные схемы, обсуждаемые в статьях с очевидным названием,
опубликованные здесь же.

Как и в случае последовательных схем ограничимся только автономными схемами, т.е.
такими, которые не имеют внешних входов и выходов, т.к. для ПМС это ограничение
обходится (в соответствии с известной теоремой Малера) размыканием провода,
соединяющего выход любого элемента схемы со входами остальных ее элементов.
Схемы описываются системами логических уравнений, задающих поведение каждого
элемента.

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

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

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

В последовательных схемах в каждом состоянии возбужден выход не более одного элемента. В силу этого второй вариант перехода из возбужденного состояния выхода элемента в устойчивое в них не возможен — ничто не изменит его входной набор, кроме, разве что, изменения значения выхода самого этого элемента. Т.е. последовательные схемы, согласно определению, являются и ПМС или, иначе говоря, является их подклассом.
Здесь надо отметить, что требование полумодулярности, как и раньше последовательности,
относится ко всем состояниям схемы, тогда как классическая теория схем, не зависящих
от скорости рассматривает только некоторое подмножество состояний (назовем его рабочим), попав в которое схема покинуть его не может, не принимая во внимание остальные.

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

Оценка количества схем, заданных системой логических уравнений

Итак, пусть схема построена из n логических элементов. Поскольку для выхода каждого
из этих элементов возможны всего 2 значения (0 и 1), то такая схема имеет всего

G = 2**n

состояний (2 в степени n - здесь и далее используются обозначения языка Питон, который будет использован для реализации предлагаемых алгоритмов). С другой стороны каждое из этих состояний может иметь 2**n вариантов, т.е. всего может быть

N = G**G = (2**n)**(2**n)

различных схем.

Вернемся к последовательным схемам, в каждом из состояний которых возбужден либо 1 из n элементов, либо ни одного. Каждому состоянию можно поставить в соответствие натуральное число на отрезке от 0 до n, т.е. n+1 значений. Тогда, каждой последовательной схеме можно соотнести набор Q из G чисел, назовем его "вектором возбуждений".
Для всех схем получим:

Np = (n + 1)**G = (n + 1)**(2**n)

таких векторов, что и определяет число последовательных схем из n логических элементов.
Такое же представление "векторами возбуждения" можно использовать и для нумерации
произвольных схем из n элементов, представленных системами логических уравнений. Только в общем случае необходимо учитывать, кроме единичных возбуждений и возможность возбуждения
пар, троек,..., n-ок выходов элементов. Таким образом получим число различных векторов
возбуждения как сумму чисел сочетаний из n элементов по k, где k = 0,..., n, т. е.:

sum(C(n,k) for k in range(0,n+1))

где C(n,k) - число сочетаний из n элементов по k.

Легко показать, что эта сумма равна 2**n, которое можно представить в виде (1+1)**n и
сравнить биноминальное разложение этого выражения с приведенной выше формулой суммы.

Отсюда можно сделать вывод, что задание состояний векторами возбуждения Q дает вполне
корректное кодирование произвольных схем, заданных системами логических уравнений.
В заключение этого раздела приведена таблица значений N и Np для n = 1, 2, 3 и 4.

Подсчет числа ПМС

Начнем с простейшего случая n = 1. Очевидно, что все 4 возможные схемы в этом случае
последовательные - в них не может быть возбуждено больше одного элемента (второго просто нет), а следовательно и ПМС, т.к. последовательные являются подклассом ПМС, т. е.

Nпсм = 4 при n =1.

Для построения алгоритма подсчета ПМС используем очевидный способ кодирования
векторов возбуждения. Как следует из вышесказанного, для их представления достаточно n-разрядного двоичного кода. Обозначим номера выходов n элементов числами от 1 = 2**0 до 2**(n-1), т. е. наличие 1 в каком-либо разряде кода будет соответствовать возбуждению выхода соответствующего элемента схемы. Тогда наличие единиц в нескольких разрядах эквивалентно возбуждению выходов соответствующей группы элементов. Ну и, очевидно, нулевой код соответствует устойчивому состоянию всех выходов. Заметим, что такое сопоставление номеров элементов с разрядами двоичного кода имеет место и в нумерации состояний схемы, с той лишь разницей, что разрядами кода являются значения выходов соответствующих элементов, а не их состояния, как в векторах возбуждения.

Поясним сказанное на примере n = 2. Для записи векторов возбуждения здесь достаточно двухразрядного двоичного кода, значения которого соответствуют: 0 - все выходы устойчивы, 1 - возбужден выход первого элемента, 2 - второго и 3 = 1 + 2 - возбуждены оба выхода. Понятно, что опасность, с точки зрения принадлежности к ПМС, представляет только последний случай, т.е. из 2**n состояний схемы выделим такие, у которых компонента вектора возбуждений равна 3. Для каждого такого потенциально опасного состояния определим возможные следующие состояния - их ровно 3. Первое, в которое попадают
в результате срабатывания обоих вместе элементов. Этот случай не противоречит определению ПМС и поэтому также исключается из рассмотрения. Зато переход в состояние по срабатыванию только одного из элементов, чьи выходы возбуждены, нарушает определение ПМС, если в нем выход не успевшего сработать элемента становится устойчивым.

Если рассматривается состояние с номером i, то состояние j, в которое перейдет схема при срабатывании первого элемента определяется формулой:

j = i ^ 1

где ^ оператор Питона "побитовая сумма по mod 2" (иначе говоря, xor).

Аналогично, для второго элемента справедливо:

j = i ^ 2

Тогда проверяя компоненту Q[j] вектора возбуждений этой схемы легко выявить факт нарушения определения ПМС. Для первого случая это:

(Q[j] == 0) or (Q[j] == 1),

а для второго:

(Q[j] == 0) or (Q[j] == 2).

Для построения алгоритма подсчета числа ПМС осталось рассмотреть преобразование целого (в смысле Питона) номера I (0=< I > n), что используется при построении функции num2quater(I,2), определение которой приведено в самом начале программы.

В программе подсчета числа ПМС для n = 2, представленной листингом 1, номера I схем от 0 до 255 перебираются в главном цикле. Первым делом каждый номер преобразуется в вектор Q возбуждения упомянутой функцией Q=num2quater(I,2). При этом априори полагается, что очередная схема является ПМС, что маркируется значением истина
флага f:

f=True

Далее для во вложенном цикле (по i) проверяется каждый компонент Q[i] вектора возбуждения на нарушение определения ПМС и в случае его обнаружения значение "истина" флага f сбрасывается, а вложенный цикл прерывается:

f=False break

И в завершении каждой итерации основного цикла, наращивается на единицу счетчик N ПМС, если, конечно, флаг f к этому моменту сохранил значение "истина":

if f: N+=1

Вот собственно и вся программа для n = 2, выполнение которой насчитало Nпмс = 98.
Напомним, что последовательных схем при n = 2 всего Np = 81, т. е. допущенный в ПМС параллелизм добавляет всего 17 схем.

Для 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[j] вектора возбуждений, нарушающих определение ПМС. Для выберем Q[i] = 3 для наглядности. Очевидно, при срабатывании первого элемента, а значит в состоянии:

j = i ^ 1

нарушение определение ПМС будет при:

(Q[j] == 0) or (Q[j] == 1) or (Q[j] == 4) or (Q[j] == 5).

т. е. появились значения компоненты, связанные с третьим элементом. Аналогично, при срабатывании второго элемента, т. е. при:

j = i ^ 2

определение ПМС будет нарушено при:

(Q[j] == 0) or (Q[j] == 2) or (Q[j] == 4) or (Q[j] == 6)

Сложнее организуется проверка при возбуждении выходов всех трех элементов т.к. приходится анализировать не только три одинарных срабатывания, но и столько же двойных. Хотя принцип проверки сохраняется во всех получаемых "следующих" состояниях j проверяется компоненты Q[j] на наличие устойчивого состояния выхода не сработавших элементов.
Полученная таким образом программа приведена на листинге 2, а ее выполнение определило, что число ПМС при n = 3 равно Nпмс = 112020. Если учесть что для этого n число последовательных схем равно Np = 65536, то видно, что добавка (46484) от параллелизма в ПМС стала существенной.

Все полученные результаты сведены в таблицу 2.

Заключение

Может возникнуть вопрос почему для каждого обсчитанного значения n надо было строить отдельную программу, вместо того чтобы сделать универсальную, для которой эта переменная была бы входным параметром, как, например, для функции num2quater(I,n). Но даже из двух приведенных примеров видно, что с ростом n структура проверочных соотношений и их число существенно меняется и учет этих обстоятельств потребовал бы известных ухищрений существенно усложняющих программу и, как правило, снижающих её
эффективность.

Но главная причина во взрывном росте вычислительной сложности алгоритма подсчета ПМС с увеличением n. Уже для n = 4 надо перебрать N = 18 446 744 073 709 551 616 схем, что невозможно реализовать на доступных вычислительных средствах за приемлемое время. В теории сложности вычислений такие алгоритмы обозначаются как non‑elementary time и являются сверхэкспоненциальными (super‑exponential). Утверждается даже, что при n = 10 число итераций (2**10240) больше, числа атомов в наблюдаемой Вселенной.

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