Минимизация с диаграммами Вейча

Минимизация этим методом предполагает использование специальных форм - диаграмм Вейча (или карт Карно).

Карта Карно для «n» логических переменных представляет собой множество квадратов (клеток), объединённых в близкую к квадрату прямоугольную форму. Каждая такая клетка соответствует одному набору логических переменных, причем наборы двух соседних клеток должны отличаться на значение одной переменной (их наборы образуют склеивающиеся конъюнкции).

На рис. 1.3‑1 приведены карты Карно для n = 1, 2, 3. На рис. 1.3‑1 а, б показана разметка колонок и строк, а также указан для каждой составляющей клетки соответствующие ей набор. Разметка колонок (строк) указывает, какие значения данная переменная имеется в клетках, находящихся в данной колонке (строке). На рис.2.2.3,в приведен пример компактной разметки карты, соответствующей карте на рис.2.2.3, б. Здесь помечаются колонки (строки), в которых соответствующая переменная имеет прямое значение. На рис.2.2-3, г приведена карта Карно для n = 3, сформированная посредством зеркального отображения карты Карно для n=2 (рис.2.2-3, в) относительно правой границы. Этот прием универсальный; его можно использовать для построения карты для заданного «n» на основании имеющейся карты Карно для «n -1» переменной. Клетка, отмеченная знаком «*», соответствует набору .

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

Рис. 2.2‑3

Записываемая функция должна быть представлена в СДНФ. Запись функции в карту осуществляется за счет установки «1» в те клетки карты, которые соответствуют конституентам единиц записываемой функции.

Например, если задана логическая функция «y» трех переменных в виде выражения

то её запись в карту Карно будет иметь вид, приведенный на рисунке рис.2.2-4.

Рис. 2.2‑4

Для выполнения минимизации представленной в карте Карно функции необходимо выполнить два этапа:

- охватить множество клеток карты Карно контурами;

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

Охват клеток карты контурами выполняется с соблюдением следующих правил:

- контур должен иметь прямоугольную форму;

- в контур может входить такое количество клеток, которое равно целой степени числа «2»;

- в контур могут входить клетки, являющиеся логическими соседями;

- в контур необходимо включить максимальное количество клеток с учетом вышеприведенных требований;

- контурами необходимо охватить все клетки с единичными значениями;

- контуров должно быть минимальное количество;

- количество клеток в контуре должно быть равно 2 ^DR, где D _R - разность ранга (дельта ранга) конституент единицы заданной функции и ранга конъюнкции, соответствующей контуру.

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

Для того чтобы быть логическими соседями, клеткам достаточно быть геометрическими соседями. Считая, что карта является пространственным объектом и заворачивается по горизонтали и вертикали, сливаясь своими крайними горизонтальными и крайними вертикальными границами, можно считать, что соответствующие крайние горизонтальные и вертикальные клетки являются геометрическими соседями. Логическими соседями могут быть клетки, которые не являются геометрическими соседями. К числу таких клеток относятся клетки, которые по горизонтали или вертикали симметричны относительно линий зеркального отображения, которые были использованы при переходе от «n» к «n+1» переменным.

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

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

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

Для функции, заданной в карте Карно, приведенной на рис.2.2-4, контуры имеют вид, приведенный на рис.2.2-5.

Для примера, контур 1 представлен на рисунке в виде двух клеток: клетки, соответствующей набору x₁x₂x₃, и клетки, соответствующей набору _, поэтому данному контуру будет соответствовать конъюнкция x₁ x₂.

Минимальное логическое выражение для функции имеет вид:

y = x₁ x₂+ x₁ x₃ + x₂ x₃.

1 2 3

.

Рис. 2.2‑5

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

На рис.2.2-6, a, b приведены карты Карно для четырех и пяти переменных.

На рис.2.2-7 приведена карта Карно для шести переменных. В этой карте приведен пример расположения четырех геометрически соседних клеток с единичными значениями, которые нельзя объединить единым контуром (1). Эти, рядом лежащие клетки, необходимо охватить двумя контурами (2, 3). Действительно, конъюнкция для неправильного контура 1 имеет вид и дельта ранга D_R при ранге шесть конституент единицы исходного выражения, составляет значение «3», отсюда количество клеток, входящих в контур, должно быть равно третьей степени двойки. Это требование не выполняется (контур охватывает только четыре клетки), следовательно контур 1 введен неправильно. В приведенной ситуации необходимо для охвата рассматриваемых клеток использовать два контура, соответственно контур 2 и контур 3.

Пример

Минимизировать функцию «y», заданную в карте Карно, приведенной на рис.2.2-8.

Решение

Карта Карно с введенными контурами, приведена на рисунке рис.2.2-9.

.

Рис. 2.2‑6

Рис. 2.2‑7

Рис. 2.2‑8

Рис. 2.2‑9

Минимальное выражение для «у», составленное по введенным контурам, имеет вид

у =	_ _ _ x1 x2 x3 x4 +	x3 x4 x5 x6 +	x1x2 x3x4 +	_ x1x2 x3x4 x5+
. +	_ _ _ x1x2x3x4x5+	_ x1x2x3x5x6+	x1x3 x4 x6 .

Под каждой конъюнкцией указан номер контура, которому она соответствует.

Дата добавления: 2014-01-07