Минимизацией называют процедуру упрощения аналитического выражения, представляющего переключательную (логическую) функцию, направленную на то, чтобы булево выражение ПФ содержало минимальное количество членов с минимальным числом переменных.
Способы минимизации:
– алгебраический;
– с помощью диаграмм Вейча (карт Карно).
В некоторых простых случаях можно осуществить минимизацию булевого выражения ПФ, используя тождества и теоремы булевой алгебры.
Пример 1. Исходное булево выражение:
.
(3.4)
Применяя теорему склеивания, получим булево выражение
,
(3.5)
которое равносильно (эквивалентно) исходному, но значительно проще его.
Пример 2. Исходное булево выражение:
.
(3.6)
Используя тождество А=А+А
и теорему склеивания получим более простое выражение
.
(3.7)
Такие элементарные приемы минимизации удается использовать, если исходное булево выражение содержит малое количество членов с небольшим числом переменных.
Более наглядным и удобным является минимизация с применением диаграмм Вейча (карт Карно).
Минимизация ПФ с использованием диаграмм Вейча (карт Карно)
Диаграммы Вейча (карты Карно) [3, 11, 18] построены так, что их соседние клетки содержат члены исходной ПФ, отличающиеся значением одной переменной: один член содержит эту переменную в прямой форме, а другой – в инверсной. Благодаря этому возникает наглядное представление о различных вариантах склеивания смежных членов.
Минимизация ПФ с помощью диаграмм Вейча
Исходным продуктом для применения диаграмм Вейча является представление ПФ таблицей истинности, в которой возможные наборы переменных упорядочены по возрастанию или по убыванию их десятичных эквивалентов (таблица 3.1). Вид диаграмм Вейча зависит от числа переменных минимизируемой ПФ - nи от того, как упорядочены наборы переменных в таблице. Если наборы упорядочены по возрастанию их десятичных эквивалентов, то диаграммы Вейча для n=2,3,4имеют вид, приведенный на рисунке 3.1.
Рисунок 3.1
Число клеток диаграммы равно количеству наборов переменных
Nкл=Nнаб=2n
.
(3.8)
Если n=2, то Nкл=22=4; n=3 – Nкл=8, n=4 – Nкл=16.
Каждая клетка соответствует определенному набору переменных и имеет номер, одинаковый с номером набора.
Строки и столбцы диаграммы, помеченные чертой, определяют наборы, в которых переменные принимают единичные значения (входят в прямой форме). Строки и столбцы, не помеченные чертой, соответствуют наборам, в которых те же переменные принимают нулевые значения (входят в инверсной форме). Например, для n=3
(рисунок 3.1) двум левым столбцам соответствует единичное значение переменной В
(в
входит в прямой форме), а двум правым – нулевое значение (в
входит в инверсной форме).
В клетки записываются значения ПФ на соответствующем наборе (нулевое или единичное). Если на каком-то наборе функция не определена, то в клетке диаграммы ставится прочерк.
ПФ считается неопределенной, если:
1) данный набор переменных в реальном логическом устройстве невозможен;
2) значение функции на данном наборе безразлично.
После заполнения диаграммы можно приступить непосредственно к минимизации, которую производят по единицам или нулям.
В первом случае результатом минимизации будет булево выражение в ДНФ, а во втором – в КНФ.
3.12.2.1.1 Общие правила минимизации
Минимизацию можно проводить по единицам (нулям). При этом:
1) Смежные единицы (нули) диаграммы условно охватывают (накрывают) прямоугольными контурами. Каждый контур может содержать 2,4,8,16, . единиц (нулей).
2) Одним контуром (накрытием) необходимо объединить максимальное количество смежных клеток, содержащих единицы (нули).
Архитектупа супер ЭВМ, построенная на принципах схемной эмуляции
Очевидно,
что создание высокопроизводительных вычислительных систем входит в число
важнейших программ ведущих государств мира. Без суперкомпьютеров невозможно
обеспечить конкурентоспособность страны на мировом рынк ...
Моделирование работы узла коммутации сообщений
Данная курсовая работа по теме: «Моделирование процессов
обработки информации» имеет следующее задание.
В узел коммутации сообщений, состоящий из входного буфера,
процессора, двух выходных буферов и двух выходных линий, пос ...
Светоизлучающие диоды. Светодиодное освещение
Светодиодные лампы - это современная альтернатива традиционной лампе накаливания.
Светодиодные энергосберегающие
лампы предназначены для использования, как на улице, так и внутри помещения,
сочетают в себе традиционное исп ...