Разделы презентаций
- Разное
- Английский язык
- Астрономия
- Алгебра
- Биология
- География
- Геометрия
- Детские презентации
- Информатика
- История
- Литература
- Математика
- Медицина
- Менеджмент
- Музыка
- МХК
- Немецкий язык
- ОБЖ
- Обществознание
- Окружающий мир
- Педагогика
- Русский язык
- Технология
- Физика
- Философия
- Химия
- Шаблоны, картинки для презентаций
- Экология
- Экономика
- Юриспруденция
МИНИМИЗАЦИЯ БУЛЕВЫХ ФУНКЦИЙ. МЕТОД СУЩЕСТВЕННЫХ ПЕРЕМЕННЫХ
Содержание
- 1. МИНИМИЗАЦИЯ БУЛЕВЫХ ФУНКЦИЙ. МЕТОД СУЩЕСТВЕННЫХ ПЕРЕМЕННЫХ
- 2. Цель лекции – изучить метод существенных переменных
- 3. Литература Савельев А.Я. Прикладная теория цифровых автоматов.
- 4. Базовые понятия: Булева переменнаяБулева функцияДвоичная система счисленияДНФМинимальная форма функцииТерминыКлючевые слова: Минимизация Минимальная ДНФ Неопределенные коэффициенты
- 5. Основные положения. 1Метод существенных переменных предназначен для
- 6. Time-Out
- 7. Пример реализации метода существенных переменных
- 8. Пример реализации метода существенных переменных
- 9. Пример реализации метода существенных переменных 3Импликантная матрица для ДНФ:
- 10. Пример реализации метода существенных переменных 4Импликантная матрица для КНФ:С инверсией xi
- 11. Пример реализации метода существенных переменных
- 12. Пример реализации метода существенных переменных 6При более сложной импликантной таблице, например:
- 13. Алгоритм минимизации по методу существенных переменныхПроцедура минимизации:Построение
- 14. ВыводыМетоды минимизации булевых функций используются во всех
- 15. Связь булевой алгебры с другими разделами
- 16. Выводы к разделу «Булева алгебра» Булева алгебра
- 17. Скачать презентанцию
Цель лекции – изучить метод существенных переменных для минимизации булевых функций, описывающих комбинационные схемы цифровых проектов Содержание: Основные положения Алгоритм нахождения неопределенных коэффициентов Пример реализации алгоритмаТема: Минимизация булевых функций.
Слайды и текст этой презентации
Слайд 1МИНИМИЗАЦИЯ БУЛЕВЫХ ФУНКЦИЙ. МЕТОД СУЩЕСТВЕННЫХ ПЕРЕМЕННЫХ
ЛЕКЦИЯ 18
В.И. ХАХАНОВ
Факультет компьютерной инженерии
и управления, кафедра АПВТ, ХНУРЭ
Слайд 2Цель лекции – изучить метод существенных переменных для минимизации булевых
функций, описывающих комбинационные схемы цифровых проектов
Содержание:
Основные положения
Алгоритм нахождения неопределенных коэффициентовПример реализации алгоритма
Тема: Минимизация булевых функций.
Метод существенных переменных
Слайд 3Литература
Савельев А.Я. Прикладная теория цифровых автоматов. М.: Высш. шк.,
1987. С. 194.
Хаханов В.І., Хаханова І.В., Кулак Е.М., Чумаченко
С.В. Методичні вказівки до практичних занять з курсу “Дискретна математика”. Харків, ХНУРЕ. 2001. С.35-43.
Слайд 4Базовые понятия:
Булева переменная
Булева функция
Двоичная система
счисления
ДНФ
Минимальная форма функции
Термины
Ключевые слова:
Минимизация
Минимальная ДНФ
Неопределенные коэффициенты
Слайд 5Основные положения. 1
Метод существенных переменных предназначен для минимизация неполностью определенных
булевых функций от большого числа переменных
Основывается на понятии существенности переменной
xiПеременная xi существенна, если
Слайд 7Пример реализации метода существенных переменных 1
Пусть функция
задана в виде:
Построим таблицу существенных переменных, где столбцам соответствуют единичные
кубы, строкам - нулевые коды:
Слайд 8Пример реализации метода существенных переменных 2
Входы для вершин
первого ряда формируют значения выходов указанных вершин:
ДНФ
КНФ
кубы
кубы
Слайд 10Пример реализации метода существенных переменных 4
Импликантная матрица для
КНФ:
С инверсией xi
Слайд 11Пример реализации метода существенных переменных 5
При более сложной
импликантной таблице, например:
алгоритм решения задачи покрытия включает пункты:
1. Определение ядра
– таких строк таблицы, которые покрывают отдельные столбцы, при этом не существует других строк, покрывающих эти же столбцы: К=x2x3;2. Строится конъюнкция дизъюнкций по столбцам матрицы:
Слайд 12Пример реализации метода существенных переменных 6
При более сложной
импликантной таблице, например:
Слайд 13Алгоритм минимизации по методу существенных переменных
Процедура минимизации:
Построение таблицы покрытия булевой
функции, где строки определяют нулевые, а столбцы – единиичные термы
Определение
координат таблицы покрытия путем нахождения номеров существенных переменных, по которым различаются нулевые и единичные термыСинтез минимальной таблицы покрытия нулевых (единичных) термов с помощью минимального числа существенных переменных
Оптимизация числа термов существенных переменных, покрывающих нулевые (единичные) термы для записи минимальной КНФ или ДНФ
Слайд 14Выводы
Методы минимизации булевых функций используются во всех программных приложениях, связанных
с синтезом вычислительных устройств
Они позволяют в среднем на 20-30% получить
более экономичный проект с позиции аппаратурных затратМетод существенных переменных позволяет обрабатывать логические схемы большой размерности, содержащие сотни переменных
Недостатком метода является необходимость наличия нулевых и единичных термов, заданных в явном виде
Слайд 16Выводы к разделу «Булева алгебра»
Булева алгебра может выступать в
качестве модели для схем из логических элементов
Она имеет связь
с такими разделами математики как теория множеств, теория групп, логика, теория структур, теория переключательных схемТеория булевых алгебр положена в основу построения модели, описывающей поведение переключательных схем
Булева алгебра является эффективным математическим аппаратом для их исследования
