Историки об Елизавете Петровне: Елизавета попала между двумя встречными культурными течениями, воспитывалась среди новых европейских веяний и преданий...
Семя – орган полового размножения и расселения растений: наружи у семян имеется плотный покров – кожура...
Топ:
Марксистская теория происхождения государства: По мнению Маркса и Энгельса, в основе развития общества, происходящих в нем изменений лежит...
Техника безопасности при работе на пароконвектомате: К обслуживанию пароконвектомата допускаются лица, прошедшие технический минимум по эксплуатации оборудования...
Характеристика АТП и сварочно-жестяницкого участка: Транспорт в настоящее время является одной из важнейших отраслей народного хозяйства...
Интересное:
Средства для ингаляционного наркоза: Наркоз наступает в результате вдыхания (ингаляции) средств, которое осуществляют или с помощью маски...
Как мы говорим и как мы слушаем: общение можно сравнить с огромным зонтиком, под которым скрыто все...
Финансовый рынок и его значение в управлении денежными потоками на современном этапе: любому предприятию для расширения производства и увеличения прибыли нужны...
Дисциплины:
2023-01-16 | 24 |
5.00
из
|
Заказать работу |
|
|
Существует несколько способов минимизации булевых функций. Прежде всего это метод Квайна-Мак-Класки, метод Блека-Порецкого и метод минимизации с помощью карт Карно или диаграмм Вейча [13, 22, 29]. Здесь будет подробно излагаться метод карт Карно, как самый удобный метод, позволяющий быстро решать задачи минимизации булевых функций от достаточно большого числа аргументов (6-12). При этом получается минимальная форма в базисе И, ИЛИ, НЕ.
Существуют карты Карно на 2 , 3 , 4 , 5 и 6 переменных[13,22]. Причем последние стали использоваться достаточно недавно. На рисунке представлены карты Карно для 2, 3, 4, 5 и 6 аргументов.
Карты и прямоугольники Карно.
Метод Карно основан на законе склеивания. Склеиваются наборы , отличающиеся друг от друга значением одного разряда. Такие наборы называются соседними. Карно закодировал клетки своей карты так ,что в соседних клетках оказались соседние, а значит, склеивающиеся наборы. Соседними могут быть не только отдельные клетки, которые мы назовем элементарными квадратами Карно, но и целые группы соседних клеток(назовем их прямоугольниками Карно). Под прямоугольником Карно[13] будем понимать некоторую, зачастую разрозненную фигуру покрытия, все соседние клетки которой закодированы соседними наборами. Например, на вышеприведённом рисунке в поле карты для 4-х переменных изображён прямоугольник Карно P, состоящий из четырёх элементарных квадратов Карно, описываемых наборами x4'x3'x2'x1' , x4'x3'x2x1' , x4x3'x2'x1' , x4x3'x2x1' . Если над логической суммой этих четырёх наборов произвести последовательно операции склеивания, то мы аналитически получим результат в виде импликанты (под импликантой будем понимать неполный набор)x3'x1'. Карта Карно позволяет получить этот результат графически значительно быстрее и проще. Для решения этой задачи используем алгоритм графической минимизации.Кстати говоря,сам Карно никакого алгоритма не предложил.
|
Алгоритм "НИИРТА" графической минимизации булевых функций.
1. Заполнить карту Карно нулями и единицами в соответствии с таблицей истинности.
2. Покрыть все единичные наборы минимальным количеством прямоугольников Карно, каждый из которых имеет максимальную площадь.
3. Каждому прямоугольнику Карно соответствует одна импликанта, причём, если в границах прямоугольника Карно какая-либо переменная принимает значения как 0 , так и 1 , то она склеивается.
Примечание.
Если в карте Карно нулей окажется меньше чем единиц, то удобнее прямоугольниками Карно покрыть все нулевые наборы. В результате мы получим инверсию минимизируемой функции.
Сущность алгоритма достаточно прозрачна. Стремление к минимальному количеству прямоугольников Карно приводит в результате к минимальному количеству слагаемых в булевой функции. Требование получения максимальной площади прямоугольника Карно вызвано стремлением минимизировать длину каждого слагаемого булевой функции.
Применим карту Карно для решения задачи 1. Возможны два варианта решения.
f = x4x1 + x4x2 + x4x3 + x3x2x1f' = x4'x1' + x4'x2' + x4'x3' + x3'x2'x1'Эти выражения представляют собой пример дизъюнктивной нормальной формы (ДНФ).
В некоторых случаях приведение результата минимизации к скобочной форме позволяет уменьшить количество ИС , необходимые для реализации булевой функции. Скобочная форма для f имеет вид:
f = x4(x1 + x2 + x3) + x3x2x1Карта Карно для решения задачи 1.
|
|
Историки об Елизавете Петровне: Елизавета попала между двумя встречными культурными течениями, воспитывалась среди новых европейских веяний и преданий...
Состав сооружений: решетки и песколовки: Решетки – это первое устройство в схеме очистных сооружений. Они представляют...
Адаптации растений и животных к жизни в горах: Большое значение для жизни организмов в горах имеют степень расчленения, крутизна и экспозиционные различия склонов...
Особенности сооружения опор в сложных условиях: Сооружение ВЛ в районах с суровыми климатическими и тяжелыми геологическими условиями...
© cyberpedia.su 2017-2024 - Не является автором материалов. Исключительное право сохранено за автором текста.
Если вы не хотите, чтобы данный материал был у нас на сайте, перейдите по ссылке: Нарушение авторских прав. Мы поможем в написании вашей работы!