Категории: ДомЗдоровьеЗоологияИнформатикаИскусствоИскусствоКомпьютерыКулинарияМаркетингМатематикаМедицинаМенеджментОбразованиеПедагогикаПитомцыПрограммированиеПроизводствоПромышленностьПсихологияРазноеРелигияСоциологияСпортСтатистикаТранспортФизикаФилософияФинансыХимияХоббиЭкологияЭкономикаЭлектроника |
Минимизация нормальных форм булевых функций.
Существуют следующие методы минимизации: 1. Ручные методы минимизации. 2. Машинные методы минимизации. Ручные методы минимизации используют, если число переменных не больше 7. В основе машинных методов минимизации лежит алгоритм Квайна - Мак Класки, алгоритмы Роота, а также методы математического программирования. В дальнейшем будем рассматривать ручные методы минимизации. Ручные методы минимизации делятся на: 1. Аналитические; 2. Топологические. Аналитические методы минимизации основаны на законах булевской алгебры. Особую роль играют законы склеивания, поглощения, введения и исключения лишних связок: - минимальная форма. С использованием правила введения и исключения лишних связок нет необходимости в переходе к совершенным формам: .
Минимизация с помощью диаграмм Карно. Диаграмма Карно эквивалентна таблице истинности. Это прямоугольная таблица, содержащая клеток, где n - число переменных функции. Каждому набору переменных функций соответствует своя клетка. Различают два вида таблиц: - дизъюнктивную диаграмму Карно (ДДК). В ней записывают единичные значения функции; - конъюнктивную диаграмму Карно (КДК). В ней записывают нулевые значения функции. В пределах одной и той же таблицы нельзя использовать 1 и 0 одновременно.
Код называется циклическим, если его соседние наборы отличаются только в одном разряде. Это касается первого и последнего набора. Из рисунка 2.6. видно, что кодировка переменных по каждой из сторон карт Карно удовлетворяет правилу образования циклического кода (кода Грея). Это правило можно использовать для построения диаграмм Карно с любым числом переменных. На рисунке 2.7. приведена диаграмма Карно для n=5, при построении которой использовалось выше приведённое правило.
Топологическая интерпретация правил минимизации.
Единицы, симметричные относительно оси диаграммы, делящие её на две половинки, в одной из которых переменная равна единице, а в
другой равна нулю, называются смежными или соседними. Изображённые на диаграмме единицы являются соседними относительно оси, делящей диаграмму Карно на две половинки , и склеивание осуществляется по переменной . .
Смежные или соседние единицы могут быть объединены в одну группу, причём число единиц в группе равно , например, для рис. 2.9. эта группа состоит из четырёх единиц и ей соответствует конъюнкция db. Таким образом, минимизация с помощью диаграммы Карно основана на законах склеивания и поглощения и использует правило смежности и симметрии единиц (нулей) относительной осей диаграммы Карно. Правила минимизации:
1. Объединяем единицы (нули) в группы, число которых в группе равно , причём k=0…n, где n – число переменных, каждой группе соответствует конъюнкция n-k переменных. Исключаются k переменных, относительно осей которых выполняется правило симметрии. 2. В объединение включается как можно большее число единиц и нулей. 3. Одни и те же единицы (нули) могут входить в разные объединения. 4. Минимизация начинается с тех единиц (нулей) которые образуют единственно возможные максимальные объединения. 5. Объединения должны покрывать все единицы (нули) функции.
Пример 2.9.
; . Минимизация неполностью определённых функций. Поскольку значение переменных из запрещённого набора не могут появляться на входе схем, то доопределение функции на этих наборах осуществляется произвольно, так чтобы реализация была минимальна. ; . На одних и тех же запрещённых наборах при образовании различных форм функция может доопределяться по разному.
|
|||||||||||||||||||
Последнее изменение этой страницы: 2016-08-11 lectmania.ru. Все права принадлежат авторам данных материалов. В случае нарушения авторского права напишите нам сюда... |