Меню

Минимизация логических функций

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

Способы минимизации:

– алгебраический;

– с помощью диаграмм Вейча (карт Карно).

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

Пример 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) Одним контуром (накрытием) необходимо объединить максимальное количество смежных клеток, содержащих единицы (нули).

Перейти на страницу: 1 2 3 4 5 6

Другие статьи:

Проект реконструкции участка первичной сети ЕВСС
В настоящее время на всех участках первичной сети ВСС (местном, внутризоновом и магистральном) еще достаточно широко используются аналоговые системы передачи (АСП), работающие по металлическим кабелям связи (К-60П по кабе ...

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

Средства постановки помех и помехозащиты на РЛС
Радиолокационные станции (РЛС) управления воздушным движением (УВД) используются для управления движением самолетов в воздухе в районе аэродрома и на земле после посадки. Такие станции позволяют обнаруживать прибывающие самол ...

(C) 2019 | www.techniformula.ru