Минимизация логического устройства с помощью карт Карно
Полученные алгебраические формы не являются оптимальными с практической точки их реализации, поэтому данные формы минимизируются.
Минимизациейназывают – алгебраическое сокращение числа переменных до тех пор пока это сокращение возможно.
Самым простым графическим способам является способ минимизации с помощью карты Карно. Этот способ используется если число входных переменных не превышает 5 и заключается в следующем. Для каждого набора переменных составляется карта или таблица, которая имеет строго определённый вид. Карта или таблица представляет собой набор клеток число которых =2n; значение в переменных клетках строго определeно.
Структура карт Карно для функций двух, трех и четырех переменных показана ниже.
| x2 | |||
| x1 | |||
| f(0,0) | f(0,1) | ||
| f(1,0) | f(1,1) |
| x1 | x2 | f(x1,x2) |
| f(0,0) | ||
| f(0,1) | ||
| f(1,0) | ||
| f(1,1) |
|
| |
а)
Рисунок 2- Таблица истинности (а) и структура карты Карно (б) для функции
двух переменных
| x1 | x2 | x3 | f(x1,x2,x3) |
| f(0,0,0) | |||
| f(0,0,1) | |||
| f(0,1,0) | |||
| f(0,1,1) | |||
| f(1,0,0) | |||
| f(1,0,1) | |||
| f(1,1,0) | |||
| f(1,1,1) |
| x2,x3 | ||||||
| x1 | ||||||
| f(0,0,0) | f(0,0,1) | f(0,1,1) | f(0,1,0) | |||
| f(1,0,1) | f(1,1,1) | f(1,1,0) |
а)
Рисунок 3-Таблица истинности (а) и структура карты Карно (б) для функции трех
переменных
| x3,х4 | |||||
| x1,х2 | |||||
| f(0,0,0,0) | f(0,0,0,1) | f(0,0,1,1) | f(0,0,1,0) | ||
| f(0,1,0,0) | f(0,1,0,1) | f(0,1,1,1) | f(0,1,1,0) | ||
| f(1,1,0,0) | f(1,1,0,1) | f(1,1,1,1) | f(1,1,1,0) | ||
| f(1,0,0,0) | f(1,0,0,1) | f(1,0,1,1) | f(1,0,1,0) |
Рисунок 4-Cтруктура карты Карно для функции четырех переменных.
Карта размечается системой координат, соответствующих значениям входных переменных. Например, верхняя строка карты для функции от трех переменных соответствует нулевому значению переменной х1, а нижняя – ее единичному значению. Каждый столбец этой карты характеризуется значениями двух переменных: х2 и х3.
Обратим внимание на то, что координаты строк и столбцов следуют не в естественном порядке возрастания двоичных кодов, а в порядке 00, 01, 11, 10. Это код Грея. Изменение порядка следования наборов сделано для того, чтобы соседние наборы (отличающиеся между собой лишь цифрой одного разряда) были соседними в геометрическом смысле.
Ячейки, в которых функция принимает единичное значение, заполняются единицами. В остальные ячейки записываются нули. Процесс минимизации использует закон склеивания и заключается в формировании прямоугольников, содержащих по 
ячеек, где k – целое число. В прямоугольники объединяются соседние ячейки, соответствующие соседним элементарным произведениям. Те переменные, которые в прямоугольнике изменяют свои значения, исчезают.
Совокупность прямоугольников, покрывающих все единицы, называется покрытием. Заметим, что одна и та же ячейка может покрываться несколько раз.
Рассмотрим несколько примеров.
|
, а квадрату из одной ячейки – произведение 
. Функция Q, соответствующая этому покрытию, имеет вид:
Q= Ú .
Формула, получающаяся в результате минимизации логической функции с помощью карт Карно, содержит сумму стольких элементарных произведений, сколько произведений имеется в покрытий.
|
| x3,х4 | ||||||
| х1,х2 | ||||||
|
| x3,х4 | |||||
| x1,х2 | |||||
| x3,х4 | |||||
| x1,х2 | |||||
в)
| |
переменных
Несмотря на то, что карты Карно изображаются на плоскости, соседство ячеек устанавливается на поверхности тора. Верхняя и нижняя границы карты Карно как бы «склеиваются», образуя поверхность цилиндра. При склеивании боковых границ образуется тороидальная поверхность. Так ячейки с координатами 1011 и 0011 являются соседними (рисунок 5б) и объединяются в один прямоугольник. Действительно, указанным ячейкам соответствует следующая сумма элементарных произведений:
.
Аналогично объединяются и остальные четыре единичные ячейки. В результате их объединения получаем элементарное произведение 
. Окончательно функция P, соответствующая покрытию, изображенному на рисунке 5б, имеет вид: 
Карта Карно, показанная на рисунке в, содержит единичные ячейки по углам. Все они являются соседними и после объединения дадут элементарное произведение 
.
Рассмотренные примеры позволяют сформулировать последовательность действий, выполненных для минимизации логических функций с использованием карт Карно:
Изображается таблица для nпеременных и производится разметка ее сторон.
Ячейки таблицы, соответствующие наборам переменных, обращающих функцию в единицу, заполняются единицами, остальные – нулями.
Выбирается наилучшее покрытие таблицы прямоугольниками. Наилучшим считается такое покрытие, которое образовано минимальным числом прямоугольников, а если таких вариантов несколько, то из них выбирается тот, который дает максимальную суммарную площадь прямоугольников.
ЛИТЕРАТУРА
1 Галкин В. И., Пелевин Е. В. Промышленная электроника и микроэлектроника – Мн: Беларусь,2000.
2ДунаевС.Д. Электроника, микроэлектроника и автоматика:Учебник для техникумов и колледжей ж.-д. транспорта,- М.:Маршрут.2003.
3 Калабеков Б.А. Цифровые устройства и микропроцессорные системы: Учебник для техникумов связи. – М.:Горячая линия- Телеком,2002.
4 Келим Ю.М. Электромеханические и магнитные элементы системы автоматики – М.: Высшая школа,1983.
5 Королев Г.В. Электронные устройства автоматики.-М.:Высшая
школа,1991.
6 Левшина Е.С., Новицкий П.В. Измерительные преобразователи.-Ленинград: Энергоатомиздат,1983.
7 Мышляева И.М. Цифровая схемотехника: Учебник для сред. проф. образовани /Ирина Михайловна Мышляева.- М.:Издательский центр “Академия”, 2005.
8 Нешумова К.А. ЭВМ и системы.-М.: Высшая школа, 1989.
9 Опадчий Ю. Ф.: Аналоговая и цифровая электроника. – М: Горячая линия Телеком, 2000.
10 Русак И.М.. Луговский В.П. Технические средства ПЭВМ.-Мн.: Вышэйшая школа, 1996.
11Семененко В..А. Электронные вычислительные машины.М.:Высшая школа, 1991.
12Соломенчук В.Г.Аппаратные средства персональных компьютеров. – СПб:БХВ-Петербург,2003.
13 Средства автоматики и телемеханики /Н.И.Бохан,И.Ф.Бородин, Ю.В.Дробышев и др. М.:Агропромиздат,1992.
14 Стрыгин В.В., Щарев Л.С. Основы вычислительной, микропроцессорной техники и программирования.-М.: Высшая школа, 1989.