11.7. АСИМПТОТИЧЕСКИЕ МЕТОДЫ СИНТЕЗА ПЕРЕКЛЮЧАТЕЛЬНЫХ СХЕМ

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

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

Оптимизация переключательных схем производится в основном по трем критериям: сложности, надежности и быстродействию. Наиболее важным является критерий сложности Шеннона, который непосредственно влияет и на два других. Традиционно сложность комбинационных схем, построенных из функциональных элементов типа И, ИЛИ, НЕ, оценивается числом двух входовых элементов. Шеннон поставил задачу определения числа элементов, требуемого для реализации произвольной переключательной функции переменных, в предположении, что принимает большие значения, и в пределе Функция зависимости сложности схемы от параметра имеет две границы (оценки): верхнюю и нижнюю. Упрощенно можно считать, что нижняя оценка — это число элементов, необходимое для реализации произвольной функции переменных, а верхняя — достаточное. Нижняя оценка была найдена Шенноном с использованием подхода, который можно назвать информационным: он сравнивал число различных схем, которые можно было бы построить, имея элементов, с числом функций из Нижняя оценка оказалась равной Верхние оценки (для различных типов схем, в различных базисах, при разных ограничениях) практически всегда определяются конструктивным путем, т. е. предлагается конкретный метод синтеза. Шеннон предложил такой метод синтеза схемы для реализации произвольной переключательной функции и получил верхнюю оценку сложности где при для схем из контактных элементов. В приложении к схемам из функциональных элементов этот метод дает оценку . Метод основан на использовании разложения произвольной функции (см. гл. 9):

Если выполнить такое разложение по переменным и раскрыть скобки, то получится дизъюнкция членов вида

где

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

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

Универсальный многополюсник переменных — схема, реализующая все булевы функции переменных. Иными словами, это схема с выходами, на каждом из которых реализуется своя булева функция. Покажем, что схема универсального многополюсника требует не более элементов, т. е. одного элемента на функцию. Действительно, к любой схеме реализующей к функций к элементами можно добавить элемент, таким образом, чтобы новая схема имела выход и реализовала различных функций. Это всегда возможно, если рассматриваемая система элементов реализует функционально полную систему функций. В качестве схемы можно взять схему из одного элемента. Процесс присоединения элементов следует продолжить до реализации всех функций т. е. до получения универсального многополюсника. Очевидно, что сложность равна (за вычетом элементов, предназначенных для реализации переменных и констант). Отсюда следует, что существует много различных схем универсальных многополюсников. Интересно, что среди них есть такой, в котором для каждой функции можно выделить подсхему, реализующую эту функцию с абсолютно минимальной сложностью. Примером конкретной схемы универсального многополюсника является схема, предложенная Шенноном и построенная на основе приведенного разложения. Исходя из универсального многополюсника переменных строится универсальный многополюсник переменных следующим образом: вначале с помощью элементов типа И строятся все возможные произведения вида и затем, используя элементы типа ИЛИ, строятся все еще не реализованные функции переменной — каждый раз новую функцию одним элементом.

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

Более сильный метод был предложен О. Б. Лупановым. Функция задается в виде прямоугольной матрицы с строками и 2 столбцами. Затем матрица разбивается на полосы по строк. Каждая полоса рассматривается как таблица истинности какой-то функции, и для нее строится своя подсхема на основе дешифраторов кип — переменных. После этого все подсхемы объединяются с помощью элементов ИЛИ. Выбирая параметры и таким образом, чтобы получить минимум сложности, О. Б. Лупанов показал, что этот метод приводит к схеме, оценка сложности которой совпадает с нижней

О. Б. Лупановым предложены наиболее сильные методы синтеза и для других типов схем с учетом различных ограничений на синтез

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

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

Методы синтеза переключательных схем и, в частности, асимптотические, вначале развивались применительно к контактным схемам, поэтому дадим о них хотя бы общее представление. При анализе и синтезе контактных схем рассматриваются» как правило, двухполюсники (рис. 11.57). Единичное значение функции соответствует наличию проводимости между полюсами нулевое — отсутствию проводимости. Контакты бывают нормально замкнутые и нормально разомкнутые: первые реализуют функцию а вторые Функ ни и И и ИЛИ реализуются последовательным и параллельным соединением двух контактов (рис. 11.58).

Любое логическое выражение, представленное операциями И, ИЛИ, НЕ, например, ДНФ, соответствует, очевидно, определенной параллельно-последовательной контактной схеме. Таким образом, рассмотренные выше методы минимизации пригодны в полной мере при синтезе контактных схем. Однако, как известно, контакты обладают двусторонней проводимостью, и это накладывает определенную специфику на процесс синтеза. Характерной особенностью контактных схем, связанной с двусторонней проводимостью, является возможность построения мостиковых схем. Простейшим примером мостиковой схемы является схема, представленная на рис. 11.59. Здесь каждая буква х, означает, что в соответствующем участке схемы имеется нормально разомкнутый

Рис. 11.57

Рис. 11.58

Рис. 11.59

Рис. 11.60

Рис. 11.61

контакт (если контакт нормально разомкнут, пишут Из рисунка видно, что схема содержит 5 контактов. Аналитическая форма представления функции проводимости между

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

Схема логического дерева (рис. 11.60) реализует все конституенты единицы и содержит в общем случае контактов.

Такое дерево называется разделительным» так как между двумя контактами для любых никогда не существует гальванической связи. Неразделительное дерево может содержать меньшее число контактов.

Базовый симметричный многополюсник — схема» реализующая все базовые симметричные функции. Функция называется симметричной, если она не зависит от перестановки аргументов. Очевидно, что если совершенная ДНФ симметричной функции содержит конституенту единицы, включающую переменных с отрицаниями, то она должна содержать все остальные конституенты единицы с отрицаниями. Симметричная функция называется базовой, если ее СДНФ включает только конституенты с одинаковым числом отрицаний. На рис. 11.01 приведен контактный базовый симметричный многополюсник трех переменных.

Приведенные примеры характеризуют определенные особенности синтеза контактных схем. Можно отметить также, что универсальный многополюсник, построенный из контактных элементов, требует немногим меньше чем контактов при Метод каскадов хорошо иллюстрируется на примере логического дерева (рис. 11.60): соединяются полюса соответствующие единичным наборам функции, причем упрощения схемы производятся, начиная с последнего каскада дерева. Например, функция, представленная табл. 11.9, реализуется схемой, изображенной на рис. и после упрощения на рис. 11.62, б. Фактически всегда остается некоторая часть дерева.

Таблица 11.9

Рис. 11.62