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

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

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

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

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

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

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

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

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

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

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

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

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

х₂ х₃

_{00 01 11 10}

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

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

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

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

х₂ х₃

_{00 01 11 10}

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

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

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

Дата добавления: 2014-11-18