Минимизация БФ с помощью карг Карно. Факультативные условия и их использование в задачах минимизации

Использование карт Карно позволяет несколько упростить и ускорить процесс минимизации (по сравнению с методом алгебраических преобразований).

Общие правила минимизации:

  • - заданную БФ нанести на карту Карно, при этом, если она задана в форме ДНФ, расширить до стандартной формы (если БФ задана таблицей или в первой числовой форме, то она представляет собой СДНФ и не требует расширения);
  • - выполнить объединение слагаемых (клеток карты), допуская условное сворачивание карты в цилиндр как по вертикали, так и по горизонтали;
  • - полученные в результате объединения выражения записать в качестве слагаемых новой (минимизированной) БФ;
  • - исходные слагаемые, не вошедшие ни в одно объединение, записать в новую БФ в первоначальном виде.

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

Пример 3.1. Минимизировать БФ, заданную в числовой форме:

Подсчитаем эффективность минимизации при реализации ЛС в булевом базисе (таблица 3.1):

Таблица 3.1

Затраты ЛЭ

До минимизации

После минимизации

ЛЭ НЕ

4

3

ЛЭИ

8 на 4 вх.

2 на 2 вх.

ЛЭ ИЛИ

1 на 5 вх.

1 на 2 вх.

Всего

13

6

ТаЛттмтто 7 1

Пример 3.2. Минимизировать БФ, заданную в алгебраической форме: F(A,B, С, D) = ABD v A BCD v ABD

Заданную в ДНФ БФ расширим до стандартной (СДНФ) в процессе ее нанесения на карту Карно и далее выполним минимизацию:

Подсчитаем эффективность минимизаций при реализации ЛС в булевом базисе (таблица 3.2):

Таблица 3.2

Затраты ЛЭ

До минимизации

После минимизации

ЛЭ НЕ

3

3

ЛЭИ

5 на 4 вх.

2

ЛЭИЛИ

1 на 8 вх.

1

Всего

9

6

Как следует из выше приведенных примеров, минимизация БФ приводит к упрощению исходной БФ, а следовательно, и к упрощению соответствующей схемы реализации.

Факультативные условия возникают в тех случаях, когда некоторые наборы переменных по логике работы схемы невозможны. В этом случае БФ на этих наборах можно доопределить произвольно, установив ее значение 0 или 1. При минимизации БФ с помощью карт Карно принимают Ф=1 только в тех клетках карты, которые могут входить в какие-либо объединения. Применение факультативных условий повышает эффективность минимизации.

Пример 3.3. Построить логическую схему, которая реагирует только на нечетные десятичные цифры первого десятка, подаваемые на вход в виде 4-х разрядного двоичного кода.

Представим заданную логику работы БФ в числовой форме:

Нанесем БФ на карту Карно и выполним минимизацию с учетом факультативных условий:

Полагая Ф=1, получим F(A,B,C,D)=D, т.е. если в рассмотрение включить все возможные нечетные числа до 15 (карта Карно это позволяет), то признаком нечетности двоичного числа является наличие 1 в младшем разряде кода (D=l).

Рассмотренные на занятии основополагающие сведения о булевой функции представляют собой фундамент для изучения логических основ построения ЭВМ и техники передачи дискретной информации. Введенные определения и термины, рассмотренные принципы минимизации БФ с помощью карт Карно, широко используются при синтезе простейших ЦУ.

 
Посмотреть оригинал
< Пред   СОДЕРЖАНИЕ   ОРИГИНАЛ     След >