2) Одним контуром (накрытием) необходимо объединить максимальное количество смежных клеток, содержащих единицы (нули).

3) Необходимо, чтобы каждая единица (нуль) накрывалась хотя бы один раз.

4) Одна и та же единица (нуль) может охватываться несколько раз разными контурами.

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

6) Левый и правый столбцы также считаются смежными - диаграмму можно мысленно свернуть в вертикальный цилиндр.

7) Угловые клетки также считаются смежными - диаграмму можно мысленно свернуть в тор.

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

9) Результатом минимизации является булево выражение в ДНФ (КНФ). Количество конъюнкций в ДНФ (дизъюнкций в КНФ) соответствует числу контуров (накрытий).

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

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

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

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

На рисунке 3.1 показаны диаграммы Вейча при числе логических переменных n=2,3,4. Для n>4 диаграммы содержатся в [18]. Если наборы переменных исходной таблицы истинности упорядочены по убыванию их десятичных эквивалентов, то следует воспользоваться диаграммами Вейча, приведенными в [5, 6]

3.12.2.1.2 Примеры минимизации ПФ с помощью диаграмм Вейча

Пример 1. Для контроля за возможной деформацией металлической конструкции из-за перегрева в ее различных критических точках установлены четыре термодатчика, обозначенные ТД1, ТД2, ТД3, ТД4. Экспериментальные исследования конструкции показали, что в процессе ее эксплуатации возможны шесть сочетаний сработавших и не сработавших датчиков. При этом деформация конструкции возникала в следующих случаях:

1) сработали ТД4, ТД3 и не сработали ТД2 и ТД1;

2) сработали ТД4, ТД3, ТД2 и ТД1;

3) сработали ТД2 и не сработали ТД4, ТД3 и ТД1;

4) сработали ТД3, ТД2 и ТД1 и не сработал ТД4;

В случаях, когда:

5) сработали ТД4, ТД3, ТД2 и не сработал ТД1;

6) сработали ТД2, ТД1 и не сработали ТД4, ТД3

деформация конструкции не возникала.

Таблица 3.5

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

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

Обозначим цифровые сигналы на выходе термодатчиков логическими переменными: ТД4→D; ТД3→С; ТД2→В; ТД1→А, а логическую функцию, которую должно реализовать устройство контроля – F.

Составим таблицу истинности, отражающую требуемую логическую функцию (таблица 3.6).

Таблица 3.6

Диаграмма Вейча, отражающая данную таблицу, показана на рисунке 3.2.

Рисунок 3.2

Если будем производить минимизацию по единицам, то в клетки, содержащие прочерки проставим дополнительные единицы.

Основные единицы накрываем тремя контурами: 1-й контур (1I) образуют клетки первой и последней строки, 2-й (1II) - клетки 2-го столбца и 3-й (1III) - 4-го столбца.

Итоговое булево выражение минимизированной ПФ имеет вид

.(3.9)

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

Рассматриваемую функцию можно минимизировать и по нулевым значениям (нулям). Для этого доопределяем клетки с номерами 1,6,9 и 11 нулями и накрываем два основных нуля двумя прямоугольниками, включающими два и четыре элемента (нуля). Первый прямоугольник (0I) охватывает клетки с номерами 6,14, второй (0II) – 1,3,11 и 9.

Итоговое булево выражение минимизированной ПФ имеет вид

.(3.10)

Оба выражения (3.9) и (3.10) эквивалентны, и применять следует то из них, которое проще реализуется на конкретном наборе логических элементов (базисе). Этот вопрос будет рассмотрен в следующих лекциях.

Пример 2. Необходимо разработать блок приоритетных прерываний от 2-х внешних устройств: ВУ1 и ВУ2. ВУ с меньшим номером соответствует более высокий приоритет. Упрощенная структура проектируемой системы показана на рисунке 3.3.

Страницы: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33