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

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

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

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

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

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

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

Запишем эту функцию, выразив импликацию и эквивалентность через отрицание, конъюнкцию и дизъюнкцию согласно формулам (1-3) и (1-5):

Рис. 3-6.

Рис. 3-7.

Разбиваем эту функцию на следующие менее сложные функции:

Тогда

На рис, 3-7,а показана функциональнаясхема на уровне функций На рис. 3-7, б показана реализация в системе базисных элементов НЕ, И, ИЛИ.

Пример 3-9.

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

Соответствующая функциональная схема приведена на рис. 3-8.

Легко установить следующее правило синтеза функциональной схемы на элементах НЕ, И и ИЛИ.

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

Рис. 3-8.

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

если в качестве стандартных логических элементов используются элементы импликации и отрицания.

Выражаем дизъюнкцию и конъюнкцию по формулам (1-19) через отрицание и импликацию:

Соответствующая функциональная схема приведена на рис. 3-9.

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

Рис. 3-9.

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

Пример 3-11. Обратимся к рассмотренной нами в примере 3-8 функции и составим таблицу, определяющую ее:

(см. скан)

Запишем функцию в ДСНФ:

Применим к этой функции метод минимизации Квайна—Мак-Клаоки. Исходные миннтермы имеют номера 4, 6, 7, 9, 12, 14 и 15. Запишем эти миннтермы по группам в двоичном коде.

Нулевая группа:

Вторая группа: .

Третья группа:

Четвертая группа: .

Сравнивая соседние группы, получаем по группам миннтермы 3-го ранга:

Первая группа:

Вторая группа: .

Третья группа:

Теперь получаем минитермы 2-го ранга:

Первая группа: .

Вторая группа:

Сокращенная ДНФ для минимизируемой функции имеет вид:

Составляем функцию меток.

Из этой таблицы вытекает, что СДНФ совпадает с МДНФ. Произведем теперь возможные вынесения за скобки:

Функциональная схема, соответствующая этой записи функции, приведена на рис. 3-10. Интересно сравнить полученную схему со схемой на рис. 3-7. Для схемы на рис. 3-7 требуются четыре элемента НЕ, один элемент И, пять элементов ИЛИ. Для схемы на рис. 3-10 требуются три элемента НЕ, четыре элемента И и два элемента ИЛИ. Если считать, что элементы типа И и ИЛИ одинаковы по сложности, а элементы типа НЕ в 2 раза проще их, то в пересчете на элементы типа НЕ для схемы на рис. 3-7 требуется затратить 16 таких элементов, а для схемы на рис. элементов. Если же допущение об эквивалентности сложности реализации элементов типи И и ИЛИ неверно, то схема на рис. 3-10 может оказаться сложнее схемы на рис. 3-7, при построении которой минимизация не применялась.

Пример 3-12. Пусть задана функция следующей таблицей:

Рис. 3-10.

При минимизации этой функции воспользуемся методом неопределенных коэффициентов:

Отсюда

Система принимает следующий вид:

Следовательно, МДНФ для запишется следующим образом:

После вынесения за скобки получаем минимальную скобочную форму

Соответствующая функциональная схема приведена на рис. 3-11.

Рис. 3-11.

Из рассмотренного в этом параграфе материала можно сделать следующие выводы относительно синтеза функциональных схем с одним выходом:

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

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

3. При решении задачи оптимального синтеза в качестве первого шага можно использовать метод минимальных нормальных форм.

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

Более общие соображения по синтезу схем будут рассмотрены в § 3-4.