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

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

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

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

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

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

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

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

Слайд 3

3 Литература Савельев А.Я. Прикладная теория цифровых автоматов. М.: Высш. шк., 1987. 222-240 с. Хаханов В. І., Хаханова І.В., Кулак Е.М., Чумаченко С.В. Методичні вказівки до практичних занять з курсу “Дискретна математика”. Харків, ХНУРЕ. 2001. С.35-43. Дискретная математика: Гипертекстов ые учебные материалы (электронный учебник) / В.И. Хаханов, С.В. Чумаченко. 2004. http/…/10.13.20.100/nserv/library/education/Чумаченко/Дискретная математика/Дистанционный_учебник/index.htm. Арифметические и логические основы цифровых автоматов. Гипертекстовые учебные материалы (электрон. учебник) / А.С. Шкиль. 2004. http/…/10.13.20.100/nserv/library/education/Шкиль/ ЛМ/Лк_лб/st_text/index.htm.

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

Слайд 4

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

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

Слайд 5

5 Представление ФАЛ на картах Карно Карта Карно является графическим способом представления булевых функций от нескольких переменных Таблицы истинности функции от 2, 3, 4-х переменных могут быть перестроены в карты Карно Пример: карта Карно для двух переменных № набора x 1 x 2 f( x 1, x 2 ) 0 0 0 1 0 1 2 1 0 3 1 1 x 1 x 2 0 1 3 2 00 01 11 10

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

Слайд 6

6 Карта Карно для трех переменных x 2 x 3 00 01 11 10 0 1 3 2 4 5 7 6 x 1 0 1 № х 1 х 2 х 3 f(x 1,x 2,x 3 ) 0 0 0 0 1 0 0 1 2 0 1 0 3 0 1 1 4 1 0 0 5 1 0 1 6 1 1 0 7 1 1 1

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

Слайд 7

7 Карта Карно для четырех переменных x 3 x 4 00 01 11 10 0 1 3 2 4 5 7 6 12 13 15 14 8 9 11 10 00 01 11 10 x 1 x 2 № х 1 х 2 х 3 х 4 f(x 1,x 2,x 3, х 4 ) 0 0 0 0 0 1 0 0 0 1 2 0 0 1 0 3 0 0 1 1 4 0 1 0 0 5 0 1 0 1 6 0 1 1 0 7 0 1 1 1 8 1 0 0 0 9 1 0 0 1 10 1 0 1 0 11 1 0 1 1 12 1 1 0 0 13 1 1 0 1 14 1 1 1 0 15 1 1 1 1

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

Слайд 8

8 Представление ФАЛ на картах Карно Для представления функции на карте достаточно в те клетки, где функция равна единице, поместить единицы Считается, что в остальных клетках содержатся нули Примеры x 2 x 3 00 01 11 10 1 1 1 1 x 1 0 1 x 1 x 2 1 1 00 01 11 10

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

Слайд 9

9 Свойства карт Карно Карты организованы таким образом, что соседние по строке или по столбцу клетки отличаются значением только одной переменной Если две комбинации значений переменных отличаются только по одной координате, то клетки являются соседними В карте Карно двух переменных клетки на противоположных концах карты тоже являются соседними Это свойство сохраняется для карт Карно трех и четырех переменных: противоположные концы каждой строки или столбца являются соседними

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

Слайд 10

10 Упрощенный стандарт карт Карно x 1 x 1 x 2 x 2 x 3 x 3 x 4 x 1 x 2 Для упрощения строки и столбцы, где переменная х i равна 1, обозначают фигурной скобкой. При этом значение ноль эта переменная имеет в неотмеченных местах

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

Слайд 11

11 Примеры представления функций на картах Карно с использованием упрощенного стандарта x 1 1 1 1 1 1 1 x 1 1 1 1 1 x 2 x 2 x 3 x 3 x 4 x 1 x 2

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

Слайд 12

12 Р-подкубы. Покрытия 1 Р- клетки – клетки с единицами Две соседние единицы образуют одномерный р-подкуб Одномерный р-подкуб соответствует произведению, в котором всегда отсутствует один первичный терм Переменная, отсутствующая в произведении, определяется по карте – она имеет различные значения для двух единиц соответствующего подкуба x 1 1 1 x 2 1 1 x 3 x 4 x 1 x 2

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

Слайд 13

13 Р-подкубы. Покрытия 2 Четыре соседние единицы образуют двумерный р-подкуб Двумерный р-подкуб соответствует произведению без двух первичных термов Опущены те переменные, которые не сохраняют постоянное значение на этом подкубе 1 1 1 1 x 3 x 4 x 1 x 2 1 1 1 1 x 3 x 4 x 1 x 2

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

Слайд 14

14 1 1 1 1 1 1 1 1 x 3 x 4 x 1 x 2 1 1 1 1 1 1 1 1 x 3 x 4 x 1 x 2 Трехмерные р-подкубы содержат по 8 единиц Одномерный р-подкуб соответствует ребру, имеющему две соседние вершины Двумерный р-подкуб соответствует двумерному подкубу n -мерного куба Чтобы представить функцию, следует покрыть все единицы карты р-подкубами Р-подкубы. Покрытия 3

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

Слайд 15

15 Представления функций р-подкубами 1 1 1 1 1 1 1 1 x 3 x 4 x 1 x 2 1 1 1 1 1 1 1 x 3 x 1 x 2 x 4

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

Слайд 16: Time-Out

16 Time-Out

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

Слайд 17

17 Правила минимизации Две соседние клетки образуют 1-куб Несущественная координата для двух кубов обозначается символами X : 101  111=1Õ1 Четыре клетки объединяются, образуя 2-куб : 100  101  110  111=1ÕÕ В общем случае могут объединяться соседние клетки, число которых равно 2 k, где k =1,2,3... (2,4,8,16,32,...) с образованием k -кубов

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

Слайд 18

18 Примеры минимизации по картам Карно 1 1 1 1 1 x 3 x 4 x 1 x 2 1 1 1 1 x 3 x 4 x 1 x 2

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

Слайд 19

19 Примеры минимизации по картам Карно 2 1 1 1 1 x 3 x 4 x 1 x 2 Склеивание соседних ячеек дает: 3 и 7  5 и 7  8  Итак, результирующая ДНФ имеет вид:

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

Слайд 20

20 Примеры минимизации по картам Карно 3 1 1 1 1 1 1 1 1 x 3 x 4 x 1 x 2 Не всегда выбранное покрытие оказывается минимальным. Например: требуется получить минимальную ДНФ для функции Y=1 на наборах {0,1,2,5,6,11,13,15} 1 1 1 1 1 1 1 1 x 3 x 4 x 1 x 2 Все возможные попарные склеивания НЕ дадут минимальную форму функции!

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

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

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

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

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

22 Тест-вопросы x 1 1 1 1 1 1 1 1 x 1 1 1 1 1 1 1 1 x 2 x 2 x 3 x 3 x 4 x 1 x 2 Обозначить на картах Карно минимизирующие контуры Указать результаты склеивания x 1 1 1 1 x 2 А Б В Г

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