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