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