Минимизация систем булевых функций

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

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

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

.

Запишем комплекс для всей системы в одном массиве, при этом отметим номера функций, к которым принадлежит тот или иной 0-куб.

0 0 0 1 2 3

0 0 1 1

0 1 0 1 2

0 1 1 1 2 3

1 0 1 2 3

1 1 0 2

1 1 1 1 2 3

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

Здесь, например 0-кубы 001(1) и 101(2,3) образуют импликанту х01() с пустым множеством соответствующих функций, поэтому импликанта не вносится в результирующий комплекс.

0 0 х 1

0 х 0 1 2

х 0 0 3

0 1 х 1 2

х 1 0 2

1 0 х 3

х 1 1 1 2 3

1 х 1 2 3

1 1 х 2

0 0 0 1 2 3

0 х 0 1 2

х 0 0 3

1 0 х 3

х 1 1 1 2 3

1 х 1 2 3

0 х х 1

х 1 х 2

Построим таблицу покрытий, с учетом принадлежности 0-кубов к соответствующим функциям (табл. 5.5).

Таблица 5.5

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

Далее выберем импликанты х00(3) и 0х0(1,2), покрывающие всю остальную часть таблицы, пометим их знаком “Ù”, а столбцы, покрываемые данной импликантой, пометим “+” во второй строке под таблицей. Таким образом:

0 х 0 1 2

х 1 1 1 2 3

1 х 1 2 3

0 х х 1

х 1 х 2

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

;

;

.

Выполнив поглощения в каждой группе, запишем минимальные покрытия:

;

;

.

Запишем выражения в виде сокращенной ДНФ:

;

;

Вопросы для самоконтроля

1. Различными способами минимизировать булеву функцию от четырех аргументов, описывающую работу порогового элемента с порогом: а)T=2, б)Т=3. Пороговый элемент срабатывает (устанавливается в истинное значение), если число истинных значений аргументов больше или равно значению порога.

2. Минимизировать систему двух булевых функций от трех переменных, описывающую работу секции сумматора (входные переменные: разряд первого операнда (a_i), разряд второго операнда (b_i), перенос из предыдущей секции (p_i-1); функции: разряд суммы (s_i), перенос в следующую секцию (p_i)).

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

Методика синтеза комбинационных схем на логических элементах

Комбинационная схема (КС) представляет собой устройство без памяти, реализующее систему переключательных функций, на которые поступают входные сигналы х₁, х₂,… , х_n и которым вырабатываются выходные сигналы y₁, y₂,… , y_m.

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

Логические элементы

При реализации КС используются логические элементы (ЛЭ), выпускаемые промышленностью в составе интегральных серий. Логический элемент представляет собой электрическую схему, реализующую элементарную логическую функцию.

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

Таблица 5.6

Название логического элемента	Графическое обозначение	Реализуемая функция
Элемент «НЕ»
Элемент «И»		y=x1Ùx2
Элемент «или»	или	y=x1Úx2
Элемент «И-НЕ»		y=
Элемент «ИЛИ-НЕ»	или	y=
Элемент «исключающее или» или «сумма по модулю два»	или или

В общем случае логический элемент может иметь несколько входов. Промышленностью выпускаются ЛЭ, имеющие 1, 2, 4, 8 входов. На рис. 5.18 показан четырехвходовый элемент «И-НЕ», реализующий функцию .

Рис. 5.18. Четырехвходовый логический элемент

Не нашли, что искали? Воспользуйтесь поиском по сайту: