Презентация на тему: МИНИМИЗАЦИЯ БУЛЕВЫХ ФУНКЦИЙ. МЕТОДЫ КВАЙНА И КВАЙНА-МАК-КЛАСКИ

МИНИМИЗАЦИЯ БУЛЕВЫХ ФУНКЦИЙ. МЕТОДЫ КВАЙНА И КВАЙНА-МАК-КЛАСКИ
Цель лекции – изучить методы Квайна и Квайна-Мак-Класки для минимизации булевых функций, описывающих комбинационные подсхемы цифровых проектов
МИНИМИЗАЦИЯ БУЛЕВЫХ ФУНКЦИЙ. МЕТОДЫ КВАЙНА И КВАЙНА-МАК-КЛАСКИ
МИНИМИЗАЦИЯ БУЛЕВЫХ ФУНКЦИЙ. МЕТОДЫ КВАЙНА И КВАЙНА-МАК-КЛАСКИ
МИНИМИЗАЦИЯ БУЛЕВЫХ ФУНКЦИЙ. МЕТОДЫ КВАЙНА И КВАЙНА-МАК-КЛАСКИ
МИНИМИЗАЦИЯ БУЛЕВЫХ ФУНКЦИЙ. МЕТОДЫ КВАЙНА И КВАЙНА-МАК-КЛАСКИ
МИНИМИЗАЦИЯ БУЛЕВЫХ ФУНКЦИЙ. МЕТОДЫ КВАЙНА И КВАЙНА-МАК-КЛАСКИ
МИНИМИЗАЦИЯ БУЛЕВЫХ ФУНКЦИЙ. МЕТОДЫ КВАЙНА И КВАЙНА-МАК-КЛАСКИ
МИНИМИЗАЦИЯ БУЛЕВЫХ ФУНКЦИЙ. МЕТОДЫ КВАЙНА И КВАЙНА-МАК-КЛАСКИ
МИНИМИЗАЦИЯ БУЛЕВЫХ ФУНКЦИЙ. МЕТОДЫ КВАЙНА И КВАЙНА-МАК-КЛАСКИ
МИНИМИЗАЦИЯ БУЛЕВЫХ ФУНКЦИЙ. МЕТОДЫ КВАЙНА И КВАЙНА-МАК-КЛАСКИ
МИНИМИЗАЦИЯ БУЛЕВЫХ ФУНКЦИЙ. МЕТОДЫ КВАЙНА И КВАЙНА-МАК-КЛАСКИ
МИНИМИЗАЦИЯ БУЛЕВЫХ ФУНКЦИЙ. МЕТОДЫ КВАЙНА И КВАЙНА-МАК-КЛАСКИ
МИНИМИЗАЦИЯ БУЛЕВЫХ ФУНКЦИЙ. МЕТОДЫ КВАЙНА И КВАЙНА-МАК-КЛАСКИ
МИНИМИЗАЦИЯ БУЛЕВЫХ ФУНКЦИЙ. МЕТОДЫ КВАЙНА И КВАЙНА-МАК-КЛАСКИ
МИНИМИЗАЦИЯ БУЛЕВЫХ ФУНКЦИЙ. МЕТОДЫ КВАЙНА И КВАЙНА-МАК-КЛАСКИ
МИНИМИЗАЦИЯ БУЛЕВЫХ ФУНКЦИЙ. МЕТОДЫ КВАЙНА И КВАЙНА-МАК-КЛАСКИ
МИНИМИЗАЦИЯ БУЛЕВЫХ ФУНКЦИЙ. МЕТОДЫ КВАЙНА И КВАЙНА-МАК-КЛАСКИ
МИНИМИЗАЦИЯ БУЛЕВЫХ ФУНКЦИЙ. МЕТОДЫ КВАЙНА И КВАЙНА-МАК-КЛАСКИ
МИНИМИЗАЦИЯ БУЛЕВЫХ ФУНКЦИЙ. МЕТОДЫ КВАЙНА И КВАЙНА-МАК-КЛАСКИ
МИНИМИЗАЦИЯ БУЛЕВЫХ ФУНКЦИЙ. МЕТОДЫ КВАЙНА И КВАЙНА-МАК-КЛАСКИ
Time-Out
МИНИМИЗАЦИЯ БУЛЕВЫХ ФУНКЦИЙ. МЕТОДЫ КВАЙНА И КВАЙНА-МАК-КЛАСКИ
МИНИМИЗАЦИЯ БУЛЕВЫХ ФУНКЦИЙ. МЕТОДЫ КВАЙНА И КВАЙНА-МАК-КЛАСКИ
МИНИМИЗАЦИЯ БУЛЕВЫХ ФУНКЦИЙ. МЕТОДЫ КВАЙНА И КВАЙНА-МАК-КЛАСКИ
МИНИМИЗАЦИЯ БУЛЕВЫХ ФУНКЦИЙ. МЕТОДЫ КВАЙНА И КВАЙНА-МАК-КЛАСКИ
МИНИМИЗАЦИЯ БУЛЕВЫХ ФУНКЦИЙ. МЕТОДЫ КВАЙНА И КВАЙНА-МАК-КЛАСКИ
МИНИМИЗАЦИЯ БУЛЕВЫХ ФУНКЦИЙ. МЕТОДЫ КВАЙНА И КВАЙНА-МАК-КЛАСКИ
МИНИМИЗАЦИЯ БУЛЕВЫХ ФУНКЦИЙ. МЕТОДЫ КВАЙНА И КВАЙНА-МАК-КЛАСКИ
МИНИМИЗАЦИЯ БУЛЕВЫХ ФУНКЦИЙ. МЕТОДЫ КВАЙНА И КВАЙНА-МАК-КЛАСКИ
МИНИМИЗАЦИЯ БУЛЕВЫХ ФУНКЦИЙ. МЕТОДЫ КВАЙНА И КВАЙНА-МАК-КЛАСКИ
МИНИМИЗАЦИЯ БУЛЕВЫХ ФУНКЦИЙ. МЕТОДЫ КВАЙНА И КВАЙНА-МАК-КЛАСКИ
МИНИМИЗАЦИЯ БУЛЕВЫХ ФУНКЦИЙ. МЕТОДЫ КВАЙНА И КВАЙНА-МАК-КЛАСКИ
МИНИМИЗАЦИЯ БУЛЕВЫХ ФУНКЦИЙ. МЕТОДЫ КВАЙНА И КВАЙНА-МАК-КЛАСКИ
Выводы
Тест-вопросы
1/36
Средняя оценка: 4.2/5 (всего оценок: 25)
Код скопирован в буфер обмена
Скачать (757 Кб)
1

Первый слайд презентации: МИНИМИЗАЦИЯ БУЛЕВЫХ ФУНКЦИЙ. МЕТОДЫ КВАЙНА И КВАЙНА-МАК-КЛАСКИ

1 МИНИМИЗАЦИЯ БУЛЕВЫХ ФУНКЦИЙ. МЕТОДЫ КВАЙНА И КВАЙНА-МАК-КЛАСКИ ЛЕКЦИИ 13, 14 В.И. ХАХАНОВ Факультет компьютерной инженерии и управления, кафедра АПВТ, ХНУРЭ ДИСКРЕТНАЯ МАТЕМАТИКА БУЛЕВА АЛГЕБРА

Изображение слайда
2

Слайд 2: Цель лекции – изучить методы Квайна и Квайна-Мак-Класки для минимизации булевых функций, описывающих комбинационные подсхемы цифровых проектов

2 Цель лекции – изучить методы Квайна и Квайна-Мак-Класки для минимизации булевых функций, описывающих комбинационные подсхемы цифровых проектов Содержание: Смысл процесса минимизации Понятие импликанты Этапы метода Квайна Недостатки метода Квайна Метод Квайна-Мак-Класки Примеры Тема: Минимизация булевых функций. Методы Квайна и Квайна-Мак-Класки

Изображение слайда
3

Слайд 3

3 Литература Савельев А.Я. Прикладная теория цифровых автоматов. М.: Высш. шк., 1987. 222-240 с. Богомолов А.М., Сперанский Д.В. Аналитические методы в задачах контроля и анализа дискретных устройств. Саратов: Изд-во Саратовкого ун-та, 1986. 240с. Хаханов В.И. Техническая диагностика элементов и узлов персональных компьюторов. К.: ИСМО, 1997. 308 с. Хаханов В. І., Хаханова І.В., Кулак Е.М., Чумаченко С.В. Методичні вказівки до практичних занять з курсу “Дискретна математика”. Харків, ХНУРЕ. 2001. С.35-43.

Изображение слайда
4

Слайд 4

4 Базовые понятия: Булева переменная Булева функция Двоичная система счисления Числовое представление ФАЛ Кубическое представление ФАЛ СДНФ и СКНФ Термины Ключевые слова: Минимизация Импликанта Существенные импликанты Минимальное покрытие

Изображение слайда
5

Слайд 5

5 Смысл процесса минимизации. 1 Различные выражения одной и той же булевой функции описывают различные схемы Пример № х 1 х 2 х 3 f(x 1,x 2,x 3 ) № х 1 х 2 х 3 f(x 1,x 2,x 3 ) 0 0 0 0 1 4 1 0 0 0 1 0 0 1 0 5 1 0 1 1 2 0 1 0 0 6 1 1 0 1 3 0 1 1 1 7 1 1 1 0

Изображение слайда
6

Слайд 6

6 Смысл процесса минимизации. 2 Преобразуем СДНФ к виду: Схемотехническое представление формул дает схемы из 12 и 10 контактов соответственно:

Изображение слайда
7

Слайд 7

7 Определения Исходная функция задана в СДНФ Def : импликанта функции – это некоторая логическая функция, обращаемая в нуль на том же наборе переменных, на котором равна нулю сама функция Любой конъюнктивный терм или группа термов, соединенных знаками дизъюнкции, входящие в СДНФ, являются импликантами исходной функции Def : первичная импликанта функции – это импликанта типа элементарной конъюнкции, никакая часть которой уже не является импликантой

Изображение слайда
8

Слайд 8

8 Историческая справка КУАЙН Уиллард ван Онрман Американский математик Профессор Гарвардского университета Читал лекции в Сан-Пауло (Бразилия), Оксфорде (Англия), Токио, Париже, Упсале (Швеция) Крупнейший специалист в области математической логики и оснований математики Член Американской Академии наук и искусств в Бостоне

Изображение слайда
9

Слайд 9

9 Задача минимизации по методу Квайна 1 Состоит в попарном сравнении всех импликант, входящих в СДНФ, в целях выявления возможности поглощения какой-то переменной на основе закона склеивания Удается понизить ранг термов Процедура проводится до тех пор, пока не останется ни одного члена, допускающего поглощение с другим термом Термы, подвергшиеся поглощению, отмечаются Неотмеченные термы представляют собой первичные импликанты Полученное логическое выражение не всегда оказывается минимальным

Изображение слайда
10

Слайд 10

10 Задача минимизации по методу Квайна 2 Исследуется возможность дальнейшего упрощения Составляется таблица, в строках которой указываются найденные первичные импликанты, а в столбцах – термы исходного выражения Клетки таблицы отмечаются, если первичная импликанта входит в состав какого-либо терма В итоге задача упрощения сводится к тому, чтобы найти такое минимальное количество первичных импликант, которые покрывают все столбцы

Изображение слайда
11

Слайд 11

11 Этапы метода Квайна Определение первичных импликант Расстановка меток Нахождение существенных импликант Определение и удаление лишних столбцов Определение и удаление лишних первичных импликант Выбор минимального покрытия Составление минимальной формы исходной функции

Изображение слайда
12

Слайд 12

12 Пример минимизации по методу Квайна Требуется минимизировать функцию: Представим функцию в виде СДНФ

Изображение слайда
13

Слайд 13

13 1. Определение первичных импликант Составляется таблица исходных термов Номера столбцов 1 2 3 4 5 6 7 8 Двоичные наборы 0011 0100 0101 0111 1001 1011 1100 1101 Исходные термы 1 1 1 1 1 1 1 1

Изображение слайда
14

Слайд 14

14 1. Определение первичных импликант Ранг термов понижается Номера столбцов 1 2 3 4 5 6 7 8 9 Первичные импликанты 3-го ранга 1 1 1 1 1 1 1 1

Изображение слайда
15

Слайд 15

15 2. Расстановка меток Номера столбцов 1 2 3 4 5 6 7 8 Н аборы 0011 0100 0101 0111 1001 1011 1100 1101 Импликанты 3-го и 2-го ранга * * * * * * * * * * * * * * * ставится на пересечении строки и столбца, если импликанта входит в какой-либо исходный терм

Изображение слайда
16

Слайд 16

16 3. Нахождение существенных импликант Номера столбцов 1 2 3 4 5 6 7 8 Н аборы 0011 0100 0101 0111 1001 1011 1100 1101 Импликанты 3-го и 2-го ранга * * * * * * * * * * * * * * C ущественной является импликанта, напротив которой в столбце стоит единственная *

Изображение слайда
17

Слайд 17

17 4. Удаление лишних столбцов 1 Номера столбцов 1 2 3 4 5 6 7 8 Н аборы 0011 0100 0101 0111 1001 1011 1100 1101 Импликанты 3-го и 2-го ранга * * * * * * * * * * * * * * Выделяются столбцы, в которых * стоит напротив существенной импликанты

Изображение слайда
18

Слайд 18

18 4. Удаление лишних столбцов 2 Номера столбцов 1 2 3 4 5 6 7 8 Н аборы 0011 0100 0101 0111 1001 1011 1100 1101 Импликанты 3-го и 2-го ранга * * * * * * * * * * * * * * Если в таблице имеются два столбца с метками в одних и тех же строках, то один из них вычеркивается. В данном примере такие отсутствуют.

Изображение слайда
19

Слайд 19

19 5. Вычеркивание лишних первичных импликант Номера столбцов 1 4 5 6 Н аборы 0011 0111 1001 1011 Импликанты 3-го и 2-го ранга * * * * * * * * Если после исключения некоторых столбцов в таблице появляются строки, в которых нет ни одной метки, то первичные импликанты, соответствующие этим строкам, исключаются из дальнейшего рассмотрения, так как они не покрывают оставшиеся термы.

Изображение слайда
20

Слайд 20

20 6. Выбор минимального покрытия 7. Составление минимальной формы исходной функции Минимальная форма складывается из суммы существенных импликант, определенных в п.3 (это ) и первичных импликант, покрывающих оставшиеся минтермы, определенных в п.6: и : Предпочтение отдается покрытию с минимальным суммарным количеством букв в импликантах

Изображение слайда
21

Слайд 21

21 Недостаток метода Квайна Необходимость попарного сравнения всех термов на первом этапе при нахождении первичных импликант С ростом числа исходных термов увеличивается количество попарных сравнений, что усложняет решение Выход: модификация метода

Изображение слайда
22

Слайд 22: Time-Out

22 Time-Out

Изображение слайда
23

Слайд 23

23 Метод Квайна-Мак-Класки – модификация метода Квайна Основывается на числовом и кубическом представлении термов ДНФ Числовое представление ФАЛ – упрощение процедуры нахождения первичных импликант на первом этапе Исходное задание функции определяется для удобства десятичными кодами двоичных кубов, соответствующих ДНФ Кубы предварительно разбиваются на подгруппы, определяемые одинаковым количеством единиц Разбиение дает возможность сравнивать кубы только соседних по числу единиц групп для уменьшения количества переборов Модификация метода Квайна – метод Квайна-Мак-Класки 1

Изображение слайда
24

Слайд 24

24 Модификация метода Квайна – метод Квайна-Мак-Класки 2 Исходные термы записываются в виде их двоичных номеров Все номера разбиваются на непересекающиеся группы по количеству единиц Условие образования r -куба – наличие расхождения в ( r -1)-кубах только по одной координате в одном двоичном разряде и наличие общих независимых координат В i -группу включают все номера наборов, имеющие в своей записи i единиц Попарное сравнение проводится только между соседними по номеру группами

Изображение слайда
25

Слайд 25

25 Пример минмизации по методу Квайна-Мак-Класки 1 Минимизировать функцию: № х 1 х 2 х 3 х 4 f(x 1,x 2,x 3, х 4 ) № х 1 х 2 х 3 х 4 f(x 1,x 2,x 3, х 4 ) 0 0 0 0 0 0 8 1 0 0 0 0 1 0 0 0 1 0 9 1 0 0 1 1 2 0 0 1 0 0 10 1 0 1 0 0 3 0 0 1 1 1 11 1 0 1 1 1 4 0 1 0 0 1 12 1 1 0 0 1 5 0 1 0 1 1 13 1 1 0 1 1 6 0 1 1 0 0 14 1 1 1 0 0 7 0 1 1 1 1 15 1 1 1 1 0

Изображение слайда
26

Слайд 26

26 Пример минмизации по методу Квайна-Мак-Класки 2 Выпишем все 0 - кубы (точки) в виде комплекса K 0 :

Изображение слайда
27

Слайд 27

27 Пример минмизации по методу Квайна-Мак-Класки 3 Разобьем комплекс K 0 на группы по количеству единиц в каждом двоичном наборе. Таких групп будет три :

Изображение слайда
28

Слайд 28

28 Пример минмизации по методу Квайна-Мак-Класки 4 1. Определение первичных импликант: а) сравниваем соседние по номеру группы кубов : Склеивание кубов

Изображение слайда
29

Слайд 29

29 Пример минмизации по методу Квайна-Мак-Класки 5 По результатам склеивания составляем K 1 23 куб : Склеивание кубов

Изображение слайда
30

Слайд 30

30 Пример минмизации по методу Квайна-Мак-Класки 6 б) разбиваем все 1-кубы на группы в зависимости от положения независимых координат Х : Нижний индекс соответствует порядковому номеру расположения независимой координаты Х

Изображение слайда
31

Слайд 31

31 Пример минмизации по методу Квайна-Мак-Класки 7 Сравниваем кубы внутри каждой группы в целях получения K 2 -кубов:

Изображение слайда
32

Слайд 32

32 Пример минмизации по методу Квайна-Мак-Класки 8 Номера столбцов 1 2 3 4 5 6 7 8 Н аборы 0011 0100 0101 0111 1001 1011 1100 1101 0 X11 * * X011 * * 01X1 * * 10X1 * * 1X01 * * X10X * * * * 2. Составление таблицы и расстановка меток. Составляем таблицу исходных термов и тех импликант, которые не принимали участие в склеивании. Если в исходный терм входит какая-нибудь первичная импликанта, то на пересечении соответствующей строки и столбца указывается метка *

Изображение слайда
33

Слайд 33

33 3. Нахождение существенных импликант. Существенная имплитанта определяется единственной меткой в каком-либо столбце таблицы. Существенной импликантой второго ранга является терм, соответствующий 2-кубу Х10Х. Выделяем столбцы соответствующие существенной импликанте. Пример минмизации по методу Квайна-Мак-Класки 9 Номера столбцов 1 2 3 4 5 6 7 8 Н аборы 0011 0100 0101 0111 1001 1011 1100 1101 A 0 X11 * * B X011 * * C 01X1 * * D 10X1 * * E 1X01 * * X10X * * * *

Изображение слайда
34

Слайд 34

34 Пример минмизации по методу Квайна-Мак-Класки 9 Номера столбцов 1 4 5 6 Н аборы 0011 0111 1001 1011 A 0 X11 * * B X011 * * C 01X1 * D 10X1 * * E 1X01 * A ν D С учетом полученной существенной импликанты выписываем окончательное представление функции: 4. Минимальное покрытие. Составляем таблицу для оставшихся невыделенных термов и импликант. Решаем задачу покрытия строк столбцами.

Изображение слайда
35

Слайд 35: Выводы

35 Выводы Методы минимизации булевых функций используются во всех программных приложениях, связанных с синтезом вычислительных устройств Они позволяют в среднем на 20-30% получить более экономичный проект с позиции аппаратурных затрат Наиболее практически ориентированным является метод Квайна-Мак-Класки, который оперирует кубическим представлением булевых функций Недостатком обоих методов является применение импликантной таблицы для решения задачи нахождения минимального покрытия, которое требует большого объема памяти для реальных объектов

Изображение слайда
36

Последний слайд презентации: МИНИМИЗАЦИЯ БУЛЕВЫХ ФУНКЦИЙ. МЕТОДЫ КВАЙНА И КВАЙНА-МАК-КЛАСКИ: Тест-вопросы

36 Тест-вопросы 1. Указать, какие кубы склеиваются: а) Х00, Х10 ; б) 011, 100; в) 10Х, 01Х; г) ни одна пара не склеивается. 2. Склеивание кубов 010 и 011 дает: а) Х00; б) 0ХХ; в) 101; г) 01Х. 3. Куб ХХ1 является а) 1-кубом; б) 2-кубом; в) 0-кубом. 4. Куб 00Х является а) 1-кубом; б) 2-кубом; в) 0-кубом. 5.Куб 011 является а) 1-кубом; б) 2-кубом; в) 0-кубом. 6. Каждая импликанта в СДНФ соответствует а) нулевому значению функции; б) значению функции, равному единице. 7. Каждая импликанта в СКНФ соответствует а) нулевому значению функции; б) значению функции, равному единице.

Изображение слайда