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

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

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

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

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

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

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

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

Слайд 3

3 Литература Савельев А.Я. Прикладная теория цифровых автоматов. М.: Высш. шк., 1987. С. 194. Хаханов В. І., Хаханова І.В., Кулак Е.М., Чумаченко С.В. Методичні вказівки до практичних занять з курсу “Дискретна математика”. Харків, ХНУРЕ. 2001. С.35-43.

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

Слайд 4

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

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

Слайд 5

5 Основные предположения. 1 Известно, что любую булеву функцию можно представить в дизъюнктивной нормальной форме Для функции от трех переменных общий вид ДНФ можно записать так: (1)

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

Слайд 6

6 Основные предположения. 2 Неопределенные коэффициенты принимают значения 0, 1 и подбираются таким образом, чтобы получающаяся после этого ДНФ была минимальной, т.е. запись ДНФ имела минимальное количество букв При определении ДНФ учитывают свойство: дизъюнкция некоторого числа переменных равна нулю, если все входящие в нее переменные равны нулю; равна единице, если хотя бы одна переменная равна единице (2)

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

Слайд 7

7 Основные предположения. 3 Преобразовывая правую часть формулы (1) на каждом наборе переменных, получаем систему уравнений: (3)

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

Слайд 8

8 Основные предположения. 4 Если функция принимает нулевые значения на соответствующем наборе переменных f i =0, то все коэффициенты, входящие в данное уравнение, равны нулю. Тогда в остальных уравнениях системы ( 3 ), где f i =1, следует также положить равными нулю эти коэффициенты.

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

Слайд 9

9 Алгоритм нахождения неопределенных коэффициентов 1. Выбрать строку системы ( 3 ), в которой f i =0. Приравнять нулю все коэффициенты этой строки. 2. Если все нулевые строки просмотрены, то перейти к п.3, иначе – п.1. 3. Из всех строк, где f i =1, вычеркнуть равные нулю коэффициенты, определенные в п.1. 4. Переписать модифицированную систему ( 3 ) с учетом выполненных преобразований. 5. В модифицированной системе выбрать и положить равными единице минимальное количество коэффициентов с минимальным количеством индексов, чтобы удовлетворить данную систему. 6. Составить минимальную ДНФ по выбранным коэффициентам

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

Слайд 10: Time-Out

10 Time-Out

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

Слайд 11

11 Пример минимизации по методу неопределенных коэффициентов 1 1. Постановка задачи Найти минимальную форму для функции методом неопределенных коэффициентов (4)

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

Слайд 12

12 Пример минимизации по методу неопределенных коэффициентов 2 2. Представление системы уравнений (3) для функции (4) в виде таблицы:

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

Слайд 13

13 Пример минимизации по методу неопределенных коэффициентов 3 3. Просмотр всех нулевых строк

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

Слайд 14

14 Пример минимизации по методу неопределенных коэффициентов 4 4. Вычеркивание равных нулю коэффициентов из строк с единицами

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

Слайд 15

15 Пример минимизации по методу неопределенных коэффициентов 5 5. Модифицированная система уравнений с учетом выполненных преобразований имеет вид:

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

Слайд 16

16 Пример минимизации по методу неопределенных коэффициентов 6 6. Выбор минимального покрытия Для обращения уравнений (0), (2), (4) в тождества достаточно, чтобы хотя бы один из коэффициентов был равен единице.

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

Слайд 17

17 Пример минимизации по методу неопределенных коэффициентов 7 7. Составление минимальной ДНФ по выбранным коэффициентам:

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

Слайд 18

18 Пример минимизации по методу неопределенных коэффициентов 8 Можно убедиться путем эквивалентных преобразований, чему равна минимальная форма функции:

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

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

19 Выводы Методы минимизации булевых функций используются во всех программных приложениях, связанных с синтезом вычислительных устройств Они позволяют в среднем на 20-30% получить более экономичный проект с позиции аппаратурных затрат Метод неопределенных коэффициентов в базисе И-ИЛИ-НЕ получать минимальные ДНФ для функций от небольшого количества переменных Недостатком метода является неприемлемая размерность таблицы для минимизации функции от более, чем 10 переменных

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

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

20 Тест-вопросы 1. На каких двоичных наборах функция f(x,y,z)=(x y)z равна 1 а) 000, д) 100, б) 001, е) 101, в) 010, ж) 110, г) 011, з) 111. 2. Конъюнкция некоторого числа переменных равна единице, когда: а) все переменные равны единице; б) все переменные равны нулю; в) хотя бы одна переменная равна единице; г) хотя бы одна переменная равна нулю. 3. Дизъюнкция некоторого числа переменных равна единице, когда: а) все переменные равны единице; б) все переменные равны нулю; в) хотя бы одна переменная равна единице; г) хотя бы одна переменная равна нулю.

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