Логические сети

Вопросы анализа и синтеза невременных схем

Разное

В заключение рассмотрим несколько схем взаимного преобразования триггеров.

На рис. 2.36,а—в показаны схемы делителей частоты на RST-, D- и JK-триггерах соответственно. Триггер D можно преобразовать в Т (делитель на 2), снабдив делитель дополнительным входом разрешения EI (рис 2.36, г). В режиме D-триггера можно использовать JK-и RST-триггеры (рис. 2.36,д,е). Из RST-триггера можно получить JK-триггер по схеме (рис 2.36, ж)

При математическом описании тех или иных физических объектов, как правило, отвлекаются от целого ряда второстепенных факторов и процессов, действующих в этих физических объектах. Такая абстракция необходима для создания общей математической теории для целого класса родственных между собой физических процессов.

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

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

Такую адекватную математическую схему мы будем называть логической сетью.

Дадим более четкое определение понятия логической сети. Пусть мы имеем конечное множество А:

И пусть нам задано множество В, элементами которого являются упорядоченные пары элементов множества А:

Здесь i, j — любые из элементов множества A, i≠j. Пусть, наконец, нам задано некоторое множество F, элементами которого являются логические функции

Установим однозначное соответствие между множествами F и A, т. е. сопоставим каждому элементу множества А один из элементов множества F.

Определение. Совокупность множеств А и В совместно с однозначным отображением множества F на множество А называется логической сетью.

Определенное таким образом понятие логической сети совпадает с понятием ориентированного нагруженного графа. Геометрической интерпретацией логической сети служит некоторая схема логической сети, которая строится следующим образом. На плоскости в произвольном порядке располагаются элементы множества А. (Для их обозначения будем использовать кружок). Эти элементы называются вершинами графа (рис. 3-1,a).

Рис. 3-1.

Символ соответствующего данному кружку элемента i (т.е. номер) пишется справа от этого кружка. Внутри кружка вписывается элемент множества F, сопоставленный при отображении F на А элементу, соответствующему данному кружку. Наконец, все кружки соединяются между собой ориентированными стрелками согласно элементам множества В. Элементу (i, j) соответствует стрелка, идущая от кружка, сопоставленного элементу i, к кружку, сопоставленному элементу j. Эти стрелки носят название ребер графа.

Пример 1. Пусть

и отображение F на А задано как

Соответствующая схема заданной логической сети показана на рис. 3-1,а.

Введем в рассмотрение множество аргументов

Произведем теперь отображение некоторых подмножеств множества X на некоторые элементы множества А

где X* некоторое подмножество множества X. При геометрической интерпретации элементы множества X будем изображать жирными точками и называть входами схемы логической сети. Задание отображения подмножества X* на элементы a_i эквивалентно заданию множества С следующего вида:

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

Пример 2.Для логической сети на рис. 3-1,а заданы:

Соответствующая схема логической сети приведена на рис. 3-1 ,б.

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

Теперь ограничим отображение множества F на А следующим образом. Потребуем, чтобы функция f_j,, сопоставляемая вершине с номером i, зависела бы от стольких аргументов, сколько ребер входит в данную вершину. Эквивалентным требованием является ограничение на элементы множеств В и С при заданном отображении F на А. Суммарное число пар вида (i, j)и (x_i, j) не должно превышать числа аргументов, имеющихся у функции, сопоставленной вершине с номером j. Логическую сеть, для которой выполнено это требование, назовем правильной.

Определение. Упорядоченная и правильная логическая сеть называется регулярной логической сетью (РЛС).

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

Произведем теперь взаимно однозначное отображение некоторого подмножества А* множества А на множество Y. Для возможности такого отображения, очевидно, необходимо выполнение неравенства k≤ m*, где m* — число элементов А*. Геометрической интерпретацией этого отображения будут ребра, направленные от элементов множества А* к соответствующим элементам множества Y. Элементы множества Y, как и элементы множества X, будем обозначать жирными точками.

Пример3. Для логической сети рис. 3-1,б определено множество

и взаимно однозначное отображение

Соответствующая схема логической сети приведена на рис. 3-1,в.

После отображения некоторых вершин графа на множество Y в графе могут остаться вершины, из которых не выходит ни одно ребро. Такие вершины назовем тупиковыми и исключим их, а также ребра, идущие к ним. Оставшуюся после этого схему логической сети будем называть логическим многополюсником. Если множество X содержит п элементов, а множество У — k элементов, то такой логический многополюсник будем называть логическим (п, k) - полюсником.

Пример 4.Для регулярной логической схемы, данной на рис. 3-1,в, вершина 6 является тупиковой. После ее удаления остается логический (5,2)-полюсник, вход х₄ у которого является фиктивным, и поэтому он опущен на схеме логической сети (рис. 3-1,г).

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