3-4. СИНТЕЗ ЛОГИЧЕСКИХ СХЕМ СО МНОГИМИ ВЫХОДАМИ

Рассмотрим следующую задачу. Имеется система из собственных функций:

Требуется построить схему, в которой работа выхода определялась бы функцией

Рис. 3-12.

На первый взгляд, задача синтеза -полюсника практически ничем не отличается от задачи синтеза -полюсника, которая рассматривалась в предыдущем параграфе. Это действительно так, если рассматривать задачу синтеза схемы для собственных функций (3-2) как задачу о раздельном синтезе для каждой из Каждая такая функция определяет некоторый -полюсник, а схемой для всей системы (3-2) будет совокупность таких -полюсников.

Пример 3-13. Синтезировать функциональную схему с системой собственных функций следующего вида:

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

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

схема является неонтималыюй и но другой причине. Рассмотрим следующие выкладки:

Они показывают, что можно существенно упростить функциональную схему, если учесть взаимную связь самих функций

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

Можно указать на несколько достаточно общих методов синтеза -полюсников. Однако все эти методы не дают решения задачи оптимального синтеза. Рассмотрим два таких метода. В гл. 5 будет рассмотрен еще один подобный метод.

Идея первого метода связана с нахождением простых импликант системы функций алгебры логики.

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

которая является простой импликантой какой-либо из

Пример 3-14. Найти простые импликаиты для системы функций

На основании определения 3-4 получаем пять простых импликант:

Очевидно, что ДНФ

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

Теперь можно сформулировать очевидное утверждение, вытекающее из определения понятия простой импликанты системы.

Простые импликанты всех возможных произведений функций данной системы, и только они, образуют множество простых импликант данной системы.

Рис. 3-13.

Это утверждение дает нам возможность построить метод синтеза -полюсника и показывает, что для случая системы функций алгебры логики может быть использован аппарат минимизации, развитый нами в гл. 2. Для системы функций можно ввести понятие СДНФ и понятие минимального покрытия.

Предоставляя это сделать читателю, отметим, что схемы, получающиеся в этом случае, будут в ряде случаев далеки от минимальных.

Пример 3-15. Построить функциональную схему для системы функций

Легко видеть, что простые импликанты для системы имеют вид:

При этом Соответствующая схема показана на рис. 3-13.

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

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

Функции зависят от аргументов. Продолжая этот процесс далее, мы придем

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

Пример 3-16. Начертить функциональную схему в соответствии со следующей системой собственных функции:

Разлагаем

На рис. 3-14,а изображена структура последовательного разложения, а на рис. 3-14, б приведена искомая функциональная схема.

Пример 3-17. Начертить функциональную схему для системы собственых функций, заданных в виде таблицы

Записывая в КСНФ, а остальные функции в ДСНФ, получаем:

Рис. 3-14. (см. скан)

Раскрывая в скобки и производя склеивание и поглощение в получаем:

Используя соотношение (3-3), последовательно получаем:

Схема, соответствующая этому разложению, показана на рис. 3-15.

Описанный нами метод синтеза известен под названием метода каскадов. Сложность схемы, получаемой

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

Рис. 3-15. (см. скан)

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