Табличные методы минимизации. КартыКарно

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

Карты Карно – это графическое представление таблиц истинности логических функций. Они представляют собой таблицы, содержащие по 2nпрямоугольных ячеек, где n – число логических переменных.

На рис. 2.1, 2.2 и 2.3 приведены структуры карт Карно для функции двух, трех и четырех переменных, а в таблицах 2.4 и 2.5 представлены таблицы истинности для функции двух, трех переменныхсоответственно.

Таблица 2.4

 

х1	х2	f(x1, x2)
0	0	f(0, 0)
0	1	f(0, 1)
1	0	f(1, 0)
1	1	f(1, 1)

 

 

х2 х1	0	1
0	f(0,0)	f(0,1)
1	f(1,0)	f(1,1)

Рис. 2.1. Структура карты Карно для функции двух переменных

 

 

Таблица 2.5

 

х1	х2	х3	f(x1, x2, х3)
0	0	0	f(0,0,0)
0	0	1	f(0,0,1)
0	1	0	f(0,1,0)
0	1	1	f(0,1,1)
1	0	0	f(1,0,0)
1	0	1	f(1,0,1)
1	1	0	f(1,1,0)
1	1	1	f(1,1,1)

 

 

х2х3 х1	00	01	11	10
0	f(0,0,0)	f(0,0,1)	f(0,1,1)	f(0,1,0)
1	f(1,0,0)	f(1,0,1)	f(1,1,1)	f(1,1,0)

 

Рис. 2.2. Структура карты Карно для функции трех переменных

 

 

х3х4 х1х2	00	01	11	10
00	f(0, 0, 0, 0)	f(0, 0, 0, 1)	f(0, 0, 1, 1)	f(0, 0, 1, 0)
01	f(0, 1, 0, 0)	f(0, 1, 0, 1)	f(0, 1, 1, 1)	f(0, 1, 1, 0)
11	f(1, 1, 0, 0)	f(1, 1, 0, 1)	f(1, 1, 1, 1)	f(1, 1, 1, 0)
10	f(1, 0, 0, 0)	f(1, 0, 0, 1)	f(1, 0, 1, 1)	f(1, 0, 1, 0)

 

Рис. 2.3. Структура карты Карно для функции четырех переменных

 

 

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

 

 

столбца. Так, в случае карты Карно для функции четырех переменных, функция, рас- положенная в ячейках столбца с координатами 01, вычисляется при значениях пе- ременных х3 = 0, х4 = 1. Функция, расположенная в ячейке на пересечении этого столбца и строки с координатами 11, определяется при наборе входных переменных x1=l,x2=l,х3=0,х4=1.

Если на указанном наборе функция равна 1, то ее СДНФ обязательносодержит

элементарное произведение х1 × х2 × х 3 × х4, принимающее при этом наборе единичное значение. Таким образом ячейки карты Карно, представляющие функцию, содержат столько единиц, сколько элементарных произведений содержится в ее СДНФ, причем каждой единице соответствует одно из элементарных произведений.

Координаты строк и столбцов в карте Карно следуют не в естественном поряд- ке возрастания двоичных кодов, а в порядке 00; 01; 11; 10. Изменение порядка следо- вания наборов кодов сделано для того, чтобы соседние наборы, отличающиеся между собой лишь цифрой какого-либо одного разряда, были соседними в геометрическом смысле.

Рассмотрим таблицу истинности (таблица 2.6) и структуру карты Карно

(рис. 2.4) для функции f(xl, x2, x3) = х1 Ú х 2 × х 3.

Таблица 2.6

 

х1	х2	х3	f(x1, x2, х3)
0	0	0	1
0	0	1	1
0	1	0	1
0	1	1	1
1	0	0	0
1	0	1	1
1	1	0	0
1	1	1	0

 

х2х3 х1	00		01			11	10
0		1		1		1	1
1	0			1		0	0

 

Рис. 2.4. Структура карты Карно для функции

 

 

Ячейки, в которых функция принимает значение 1, заполняются единицами. Процесс минимизации заключается в формировании прямоугольников, содержащих по 2kячеек, где k – целое число. В прямоугольники объединяются соседние ячейки, которые соответствуют соседним элементарным произведениям. Например, на рис. 2.4 объединены ячейки с координатами 001 и 101. При объединении этих ячеек образовался прямоугольник, в котором х1 изменяет свое значение. Следовательно, оно исчезает при склеивании соответствующих элементарных произведений

х1 × х 2 × х 3 и х1 × х 2 × х 3. Ячейки, расположенные в первой строке, содержат 1 и явля-

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

мент

х1. Это следует из того, что четырем ячейкам первой строки соответствует сум-

ма четырех элементарных произведений:

х1 × х 2 × х 3 Ú х1 × х 2 × х 3 Ú х1 × х 2 × х 3 Ú х1 × х 2 × х 3 =

=х1×х2×(х3Ú х3)Úх1×х2×(х3Ú х3)=х1×х2Úх1×х2

 

 

= х1 × (х 2 Ú х 2)= х1.

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

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

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

 

 

Несмотря на то, что карты Карно изображаются на плоскости, соседство ячеек устанавливается на поверхности тора или цилиндра. Верхняя и нижняя границы кар- ты Карно как бы «склеиваются», образуя цилиндр. При склеивании боковых границ получается тороидальная поверхность. Поэтому в примере (рис. 2.5) ячейки с коорди- натами 1011 и 0011 являются соседними и объединяются в прямоугольники. Действи- тельно, указанным ячейкам соответствует сумма элементарных произведений

х1 × х 2 × х 3 × х 4 Ú х1 × х 2 × х 3 × х 4 = х 2 × х 3 × х 4 × (х1 Ú х1) = х 2 × х 3 × х 4.

 

х3х4 х1х2	00		01	11			10
00	0		0		1		0
01	1		0	0				1
11	1		0	0				1
10	0		0		1		0

 

Рис. 2.5. Карта Карно для функции четырех переменных

 

 

Аналогично объединяются и остальные четыре единичные ячейки. В результа- те их объединения получаем:

х1 × х 2 × х 3 × х 4 Ú х1 × х 2 × х 3 × х 4 Ú х1 × х 2 × х 3 × х 4 Ú х1 × х 2 × х 3 × х 4 =

= х 2 × х 3 × х 4 × (х1 Ú х1) Ú х 2 × х 3 × х 4 × (х1 Ú х1) = х 2 × х 4 (х 3 Ú х 3)= х 2 × х 4.

Поэтому окончательно f(x1, x2, x3, x4) =

х 2 × х3 × х 4 Ú х 2 × х 4.

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

1. Изображается таблица для n переменных и производится разметка еесторон.

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

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

 

 

Качество минимизации оценивается коэффициентом покрытия:

k = m/s,

где m – общее количество прямоугольников; s – суммарное количество покры- тых ячеек. Покрытиесчитаетсятемлучше, чемменьшеегокоэффициент k.