3.4 Синтез логических схем со многими выходами

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

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

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

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

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

Рисунок 3.10 -

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

Рассмотрим следующие выкладки:

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

3.5 Синтез схем по неполностью определенным собственным функциям

Определение. Функция алгебры логики f(х₁,х₂, ..., х_п) называется неполностью определенной, если ее значения заданы меньше чем на 2^п наборах аргументов.

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

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

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

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

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

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

Пример 19. При доопределении функции примера 18 на наборе <1,0> нулем получим функцию y = x₂, а при доопределении ее единицей — функцию y = х₁Vх₂. Ясно, что с точки зрения минимизации доопределение нулем выгоднее.

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

Пример 20. Доопределить функциюfс учетом ее дальнейшей минимизации в классе нормальных форм.

На рисунках 3.11 и 3.12 показаны карты Карно, с применением которых представляется возможность использования простого наглядного способа доопределения неполностью определенных функций.

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

х₂ х₃

_{00 01 11 10}

0	(1)*	(1)*	1
1	1	(1)*	0

Рисунок 3.11 – Карта Карно

При доопределении всех неопределенных состояний единичными значениями (рисунок 3.11) произошло три объединения соседних клеток, что приводит к получению окончательного результата в виде выражения

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

х₂ х₃

_{00 01 11 10}

0	(0)*	(1)*	1
1	1	(0)*	0

Рисунок 3.12 – Карта Карно

Легко видеть, что другие возможные доопределения дадут результат не лучший, чем доопределение единицей на наборе <0, 1, l> и нулями на остальных запрещенных наборах. Это доопределение показано на рис. 3.12. При этом объединений смежных клеток получилось минимальное количество и в итоге функция принимает вид