Метод Квайна

Июль 25, 2022

Главная
Информатика
Метод Квайна

Содержание

2. способ представления функции в ДНФ или КНФ с минимальным количеством членов и минимальным набором переменных Преобразование
3. Первый этап (получение сокращённой формы)
4. Получение сокращённой формы
5. Пример Пусть есть таблица истинности
6. Результаты упрощения
7. Рассмотренный выше пример уже удовлетворяет определению минимальной формы, однако далеко не всегда после первого этапа сокращённая
8. Пример
9. Получение СДНФ
10. Мы вновь получили дизъюнкцию простых импликант, на этот раз в количестве пяти штук. Чтобы получить минимальную
11. Импликанты, не подлежащие исключению, образуют ядро. Такие импликанты определяются по вышеуказанной матрице. Для каждой из них
12. Выбор остальных импликант, что войдут в минимальную форму, сводится к нахождению минимального набора неядровых импликант, которые
13. Структурная схема, при минимизации функции методом Квайна
14. Использование метода для получения минимальной КНФ
15. Нахождение первичных импликант; Эти импликанты разбиваются на группы, в каждую группу входят импликанты с равным количеством
16. Положим, что функция записана в виде СДНФ. Тогда первичными импликантами будут 010~, 0~11, 1~01, 111~, ~1~1.
17. Существенными импликантами будут те, где в соответствующих столбцах стоит только одна метка. Без любой из них
18. Убираем лишние строки (в данном случае только одну) и выберем такую совокупность первичных импликант, что включает
19. Его можно применять на большом количестве переменных в САПР, с использованием ЭВМ для минимизации полностью или
20. Затруднительна ручная минимизация функций с шестью и более переменных; Метод Куайна — Мак-Класки алгоритмически неинвариантен: время
21. в теории сложности вычислений задача, для решения которой требуется обработка более чем 1093 бит информации. Число
22. Сумматор логический операционный узел, выполняющий арифметическое сложение кодов двух чисел. При арифметическом сложении выполняются и другие
23. четвертьсумматоры; полусумматоры; полные одноразрядные двоичные сумматоры По числу входов и выходов одноразрядные, многоразрядные. По количеству одновременно
24. Четвертьсумматор
25. Реализация сумматора
26. Реализация сумматора
27. Полусумматор
28. Полный одноразрядный двоичный сумматор
29. Реализация на двух полусумматорах и одном элементе ИЛИ
30. Схемы реализации
31. Полувычитатель
32. Реализация полувычитателя
33. Универсальное устройство
34. ТИ полного вычитателя
36. Схема полного вычитателя
38. Скачать презентацию

Слайд 2

способ представления функции в ДНФ или КНФ с минимальным количеством членов

и минимальным набором переменных
Преобразование функции можно разделить на два этапа:
на первом этапе осуществляется переход от канонической формы (СДНФ или СКНФ) к так называемой сокращённой форме;
на втором этапе — переход от сокращённой формы к минимальной форме.

Метод Квайна

Слайд 3

Первый этап (получение сокращённой формы)

Слайд 4

Получение сокращённой формы

Слайд 5

Пример
Пусть есть таблица истинности

Слайд 6

Результаты упрощения

Слайд 7

Рассмотренный выше пример уже удовлетворяет определению минимальной формы, однако далеко не

всегда после первого этапа сокращённая форма совпадает с минимальной.
Ещё могут оставаться члены, чьё удаление не изменяет конечный результат.
На данном этапе требуется удалить лишние переменные.

Второй этап (табличный)

Слайд 8

Пример

Слайд 9

Получение СДНФ

Слайд 10

Мы вновь получили дизъюнкцию простых импликант, на этот раз в количестве

пяти штук.
Чтобы получить минимальную форму, воспользуемся импликантной матрицей.
Столбцы в ней соответствуют членам СДНФ, а строки — членам сокращённой формы.
Отмечаются столбцы членов СДНФ, которые поглощаются отдельными простыми импликантами:

Обработка импликантной матрицы.

Слайд 11

Импликанты, не подлежащие исключению, образуют ядро.
Такие импликанты определяются по вышеуказанной

матрице.
Для каждой из них имеется хотя бы один столбец, перекрываемый только этой импликантой.
Исключить все остальные члены сокращённой формы, однако, нельзя, так как это может привести к превращению какой-либо другой импликанты в нелишнюю.

Слайд 12

Выбор остальных импликант, что войдут в минимальную форму, сводится к нахождению

минимального набора неядровых импликант, которые покроют столбцы, не перекрываемые ядровыми.
Применительно к рассматриваемому случаю это будут третий и четвёртый столбец.
То, что можно исключить остальные импликанты, легко проверяется. На соответствующих наборах мы получаем значение 1, которая получается и на удалённых импликантах.

Слайд 13

Структурная схема, при минимизации функции методом Квайна

Слайд 14

Использование метода для получения минимальной КНФ

Слайд 15

Нахождение первичных импликант;
Эти импликанты разбиваются на группы, в каждую группу

входят импликанты с равным количеством единиц (нулей);
Производится попарное сравнение эквивалентов (термов) в соседних группах, с целью формирования термов более низких рангов;
Составляется таблица, где строкам соответствуют первичные импликанты, а заголовкам столбцов — термы низких рангов;
Расставляются метки, отражающие поглощение термов высших рангов (исходных термов).
Находятся существенные импликанты;
Вычёркиваются лишние столбцы;
Вычёркиваются лишние первичные импликанты;
Выбирается минимальное покрытие максимальными интервалами.

Метод Квайна—Мак-Класки

Слайд 16

Положим, что функция записана в виде СДНФ. Тогда первичными импликантами будут

010~, 0~11, 1~01, 111~, ~1~1.

Пример

y=f(0011,0100,0101,0111,1001,1101,1110,1111)

Слайд 17

Существенными импликантами будут те, где в соответствующих столбцах стоит только одна

метка.
Без любой из них не будет полного покрытия исходных минтермов.
Итого получается, что в данном примере существенные импликанты — 0~11, 010~, 1~01, 111~.

Слайд 18

Убираем лишние строки (в данном случае только одну) и выберем такую

совокупность первичных импликант, что включает метки во всех столбцах. Предпочтение отдаётся минимальной выборке.
Получаем искомую форму

Слайд 19

Его можно применять на большом количестве переменных в САПР, с использованием

ЭВМ для минимизации полностью или частично определённых функций;
Не принципиально, задана функция в СДНФ или СКНФ;
Удобно минимизировать системы булевых функций в связи с простым выделением общих частей реализуемой системы ФАЛ;
Данный метод — алгоритмически систематический, он легко формализуется и алгоритмизируется. Не зависит от навыков разработчика;
Позволяет последовательно осуществить все этапы минимизации (склеивание и выявление лишних импликант, получение минимальных покрытий).

Достоинства метода

Слайд 20

Затруднительна ручная минимизация функций с шестью и более переменных;
Метод Куайна —

Мак-Класки алгоритмически неинвариантен: время работы растёт экспоненциально с увеличением входных данных.
Можно показать, что для функции от n переменных верхняя граница количества основных импликант 3n/n. Если n = 32 их может быть больше чем 6.5 * 1015.

Недостатки метода

Слайд 21

в теории сложности вычислений задача, для решения которой требуется обработка более

чем 1093 бит информации.
Число 1093, называемое «пределом Бремерманна»

Трансвычисли́тельная зада́ча

Слайд 22

Сумматор логический операционный узел, выполняющий арифметическое сложение кодов двух чисел.
При

арифметическом сложении выполняются и другие дополнительные операции: учет знаков чисел, выравнивание порядков слагаемых и тому подобное.
Указанные операции выполняются в арифметическо-логических устройствах (АЛУ) или процессорных элементах, ядром которых являются сумматоры.

Сумматоры

Слайд 23