Борис Цирлин
Рассматриваются объекты счета, алгоритмы которого описаны в предыдущих частях, а именно последовательные схемы из логических элементов, заданные системами логических уравнений.
Введение
В предыдущих частях был формально определен объект изучения - последовательные схемы, получена верхняя граница их числа при заданном количестве n элементов, введено понятие двух видов изоморфизма и предложен алгоритм подсчета не изоморфных, т.е. действительно различных последовательных схем.
Чтобы не походить на козленка, который умел считать до десяти, обратимся непосредственно к предмету счета, т.е. к собственно последовательным схемам. При этом поведение схемы, заданной системой логических уравнений будем иллюстрировать графом переходов, в котором узлы графа соответствуют состояниям схемы, а направленные дуги, соединяющие эти узлы - возможным переходами схемы из состояния в состояние. В последовательных схемах имеют место переходы между соседними состояниями, т. е. такими, коды которых отличаются только в одном разряде. Для удобства эти графы будем размещать на координатном отрезке, квадрате, кубе нужной размерности. Итак имеет место взаимно однозначное соответствие между графом переходов и системой логических уравнений схемы. Последнюю можно изобразить и схемой из логических элементов в обычном понимании.
Последовательные схемы из одного элемента.
Начнем со схем, состоящих из одного логического элемента, т.е. со случая n = 1. Такие схемы не могут быть не последовательными, т.к. в любом из их двух возможных состояний возбуждено не более одного элемента (второму просто неоткуда взяться). В соответствии с формулой (см. ч.1):
N = (n + 1)**(2**n),
для нашего случая получим N = 4.Перестановочный изоморфизм схем для этого случая невозможен (1! = 1), а изоморфизм за счет инверсии может породить всего 2 варианта. На рис. 1 изображены все 3 не изоморфные схемы, которые можно построить используя ровно 1 логический элемент. Пропущена только схема № 2, изоморфная приведенной схеме № 1.
Последовательные схемы из двух элементов.
Для этого случая общее число последовательных схем N = 81, но нас интересуют только не изоморфные, число которых, определенное описанной программой, равно 15. С помощью той же программы получен список всех не изоморфных схемдля n = 2 с краткими характеристиками, который приведен на рис.2.
Заметим, что схемы выведены не в порядке возрастания их номеров I, что было бы естественно при последовательной реализации программы на CPU, а в соответствии со скоростью их вычисления при параллельной обработке на GPU.
Небольшое количество этих схем позволяет рассчитывать на достаточно простой способ их классификации.
Прежде всего распределим их по, условно говоря, схемотехнической структуре. Первыми выделим композиции одноэлементных последовательных схем - их всего 3 и они приведены на рис.3.
Каждая из них представляет композицию одноэлементных схем № 0 и любой из трех. При этом нет связи выходов элементов со входами других. Из трех полученных ни одна не имеет 8 изоморфных, а двухэлементная схема № 0 вообще уникальна - у нее единственной параметр w = 1.
Следующими рассмотрим схемы в которых выход одноэлементной схемы № 0 соединен со входом второго элемента. Таких схем всего 4, они приведены на рис.4.
Параметр w у них выше, чем у предыдущих и равен либо 4 либо 8 - последнее является максимальным значение для двухэлементных схем.
Еще 2 схемы образованы аналогичным образом, только одноэлементной составляющей у них является схема № 1 вместо № 0 предыдущего случая. Они приведены на рис.5. и имеют высокое значение параметра w (8 и 4).
Заметим, что композиция одноэлементной схемы № 3 возможна только с одноэлементной схемой № 0 и уже была рассмотрена (см. рис. схема № 40).
Оставшиеся 6 схем можно сказать традиционного вида, в каждой из которых любой вход ее элементов присоединен в точности к одному выходу и никакие два выхода не соединены между собой. На рис.6. представлены все эти схемы.
Среди них имеется вторая схема с параметром w = 2,- первой была композиция одноэлементных схем № 0 и № 3.
Графы переходов двухэлементных последовательных схем.
Итак имеются все двухэлементные не изоморфные схемы и можно попытаться найти соответствие между длиной их списков изоморфных (параметр w) и свойствами соответствующих графов переходов. Для этого сначала построим все изоморфные схемы для одной из имеющих наибольшее значение параметра w, а именно № 5 (w = 8 ). Результат приведен на рис.7.
Здесь исходная схема изображена в левом верхнем углу, а справа от нее изоморфные схемы, полученные всеми возможными вариантами инверсий переменных. Нижняя строка схем образованна аналогично, но с учетом единственной возможной перестановки элементов.
Если попарно сравнивать первую схему (вернее ее граф переходов) со следующими в том же ряду, то очевидно, что инвертирование переменной x приводит к отражению графа переходов схемы по горизонтали: вершины 00 и 01 меняются местами с вершинами 10 и 11 соответственно, а переменной y - по вертикали: вершины 00 и10 меняются местами с вершинами 01 и 11. При этом, конечно, нумерация вершин на координатном квадрате сохраняется. Инвертирование обеих переменных вызывает оба отражения, т.е. вершины 00 и 10 меняются местами с вершинами 11 и 01 соответственно.
Единственная возможная перестановка переменных (переход и из одного ряда в другой в одном столбце) меняет местами вершины 10 и 01, при этом вершины 00 и 11 остаются на своих местах. Отметим, что изменение направления дуг на противоположное является не причиной, а следствием такой трансформации графа переходов и, в зависимости от вида исходного графа, может т не возникать.
Очевидно, что наличие симметрии в графе переходов последовательной схем относительно вертикальной или горизонтальной оси координат или одной из диагоналей координатного квадрата приводит к уменьшению ее параметра w. Для иллюстрации рассмотрим пример изоморфизмов для схемы с параметром w = 4, приведенный на рис.8.
Граф переходов исходной схемы № 5 (как впрочем и изоморфной ей схемы №21) симметричен относительно диагонали, соединяющей вершины 00 и 11 координатного квадрата. Отсюда и инвариантность этого графа переходов (и, конечно, системы логических уравнений) этих схем к перестановке переменных. Что касается двух других изоморфных схем, № 29 и № 28, то их графы симметричны относительно другой диагонали, соединяющей вершины 10 и 01 координатного квадрата, и они преобразуются друг в друга, как инвертированием переменной y, так и перестановкой переменных. В итоге и имеем всего 4 изоморфных схемы. В этом случае нет изменения направления дуг во всех этих схемах на противоположное, более того попытка его осуществить вывела бы схему из класса последовательных.
Не изоморфных последовательных схем из двух элементов, имеющих параметр w =2 всего 2 и все они уже были на предыдущих рисунках. На рис.9 они приведены совместно с изоморфными им схемами.
Так как графы переходов этих схем симметричны относительно горизонтальной и вертикальной координатных осей, имеет место инвариантность к инверсиям переменных, а перестановка последних (за счет диагональной асимметрии графов) трансформирует друг в друга схемы № 40 и № 52 в изоморфные им № 80 и № 76 соответственно. Причем эта трансформация, как видно из рисунка, не обязательно приводит изменению направления дуг графа на противоположное.
Заметим, что № 80 - максимальный номер последовательной схемы из двух элементов.
И, наконец, уже приведенная схема № 0 (первая на рис.3) - полученная, как композиция двух одноэлементных схем с таким же номером, имеет вырожденный граф переходов, не содержащий ни одной дуги, и уникальна тем, что не имеет изоморфных. Что, кстати, подтверждается симметрией ее графа относительно обеих координатных осей и диагоналей координатного квадрата.
Заключение. Нормальные схемы.
Рассмотрим некоторые общие характеристики множества не изоморфных последовательных схем. Для краткости назовем последовательные схемы, имеющие максимальное количество изоморфных (максимальный параметр w),- нормальными. Среди одноэлементных последовательных схем нормальной является всего 1 из 3 не изоморфных. Для двухэлементных - доля нормальных возрастает - их 7 из 15 не изоморфных, а для последовательных схем из 3 элементов эта тенденция усиливается: число нормальных составляет 1278 из 1474 не изоморфных, т. е. 86,7%. А если учесть, что в последнем случае каждая нормальная схема имеет 48 изоморфных, то доля таких схем в общем количестве схем оказывается еще значительнее: 93,6% = (48*1278/1474)*100%.
Очевидно, что с ростом числа n элементов, составляющих последовательную схему доля нормальных схем стремительно возрастает, что свидетельствует о правильном выборе этого названия.