3-5. СИНТЕЗ СХЕМ ПО НЕПОЛНОСТЬЮ ОПРЕДЕЛЕННЫМ СОБСТВЕННЫМ ФУНКЦИЯМ

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

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

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

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

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

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

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

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

Если на всех запрещенных комбинациях доопределить данную функцию нулями, то, как это видно из рис. 3-17. МДНФ для функции будет иметь следующий вид:

Рис. 3-16.

Рис. 3-17.

Если же произвести доопределение единицами, то МДНФ примет вид:

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

Рис. 3-18.

Рис. 3-19.

Это доопределение показано на рис. 3-19. При этом

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

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

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

Теорема 3-1. МДНФ неполностью определенной функции получается как дизъюнкция наиболее коротких (по числу букв) импликант которые в совокупности покрывают все импликанты в ДСНФ для причем среди выбранных импликант нет лишних.

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

Пример 3-20. Для функции из примера 3-19 найти минимальное доопределение.

ДСНФ имеет вид:

ДНСФ имеет вид:

Получаем для сокращенную ДНФ, используя для этого метод Квайна—Мак-Класки до этапа построения таблицы покрытий. Тогда

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

Крестик в клегке этой таблицы означает, что соответствующая простая импликанта накрывает конъюнкцию из ДСНФ Выбирая минимальное покрытие, получаем минимальное доопределение для в следующем виде:

Этот результат совпадает с результатом примера найденным методом перебора всех возможных доопределений.

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

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

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

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

Так как аргумент этой функции зависит от то зависит от тех же переменных, что и хотя формально число аргументов равно Потребуем теперь выполнения равенства

Выполнения равенства (3-4) можно добиться, так как функция является не полностью определенной.

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

Рассмотрим табличное значение

Запишем теперь таблицу для функции

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

Запишем теперь в следующем виде:

где

При этом очевидно, что соотношение (3-4) выполняется.

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

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

1. Для построения одномерного единичного куба надо взять два нуль-мерных единичных куба (точки) на расстоянии, равном единице. Соединив эти точки отрезком прямой и приняв направление этой прямой за первое координатное направление, получим одномерный куб.

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

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

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

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

При доопределении всех запрещенных комбинаций нулями получим:

(кликните для просмотра скана)

Рис. 3-21.

Рис. 3-22.

Это доопределение не самое хорошее. На рис. 3-22 показано другое доопределение, полученное в соответствии с теоремой 3-1, при котором функция принимает

Построим теперь функциональную схему для заданной системы собственных функций (рис. 3-23).

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

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

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