Борис Цирлин

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

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

Дистрибутивные схемы, ч.2