Минимизация логического устройства с помощью карт Карно

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

Минимизациейназывают – алгебраическое сокращение числа перемен­ных до тех пор пока это сокращение возможно.

Самым простым графическим способам является способ минимизации с по­мощью карты Карно. Этот способ используется если число входных перемен­ных не превышает 5 и заключается в следующем. Для каждого набора перемен­ных составляется карта или таблица, которая имеет строго определённый вид. Карта или таблица представляет собой набор клеток число которых =2ⁿ; значе­ние в переменных клетках строго определ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,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 – целое число. В прямоугольники объединяются со­седние ячейки, соответствующие соседним элементарным произведениям. Те пе­ременные, которые в прямоугольнике изменяют свои значения, исчезают.

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

Рассмотрим несколько примеров.

в)

Чем больше ячеек в прямоугольнике, тем меньше переменных содержится в соответствующем ему элементарном произведении. Например, для карты Карно, изображенной на рисунке 2а, прямоугольнику, содержащему четыре ячейки, со­ответствует произведение , а квадрату из одной ячейки – произведение . Функция Q, соответствующая этому покрытию, имеет вид:

Q= Ú .

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

	б)

	x3,х4
х1,х2
а) 10

	x3,х4
x1,х2

	x3,х4
x1,х2

в)

Рисунок 5– Примеры реализации карт Карно для функций четырех

переменных

Несмотря на то, что карты Карно изображаются на плоскости, соседство ячеек устанавливается на поверхности тора. Верхняя и нижняя границы карты Карно как бы «склеиваются», образуя поверхность цилиндра. При склеивании боковых границ образуется тороидальная поверхность. Так ячейки с координа­тами 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.