Презентация на тему "Минимизация функций"

Содержание

• 
  Слайд 1

  Минимизация функций

  Схемы функциональных элементов. Задача минимизации функций алгебры логики. Каноническая задача минимизации. Расчётный метод. Метод Квайна. Метод Карно.

• 
  Слайд 2

  Схемы функциональных элементов

  x g(f(x))

• 
  Слайд 3

  Логические схемы

  x y  

• 
  Слайд 4

  Задача минимизации ФАЛ

  Пример: сумматор, складывает два 16 битных числа. Количество входов: 32 Количество выходов 33 СДНФ: 33 формулы по 2^32 конъюнкта, в каждом по 32 переменные.

• 
  Слайд 5
  

  1. F = 2. F = 3. F = 4. F =  

• 
  Слайд 6
  

  5. F = F =  

• 
  Слайд 7

  Каноническая задача минимизации

  Минимизировать число букв в нормальной форме

• 
  Слайд 8

  Методы минимизации

  Метод непосредственных преобразований Метод Квайна-МакКласки Метод Петрика Табличный метод (карты Карно) Геометрический метод Метод факторизации Метод функциональной декомпозиции И др.

• 
  Слайд 9

  Этапы минимизации

  Склейка. Преобразование СДНФ в сокращённую ДНФ Удаление лишних импликант. Преобразование сокращённой ДНФ в тупиковую (минимальную) ДНФ Переход од ДНФ к минимальной форме

• 
  Слайд 10

  Расчётный метод

  этап. Склейка. F = Сокращённая ДНФ: F =  

• 
  Слайд 11
  

  2 этап. Выявление лишних импликант: F = = 1 ( импликанта )  

• 
  Слайд 12
  

  F = 1. 2.  поглощается 3 и 1 3.  поглощается 2 и 4 4. Тупиковые ДНФ: F = F =  

• 
  Слайд 13
  

  3этап. Магия: F =  

• 
  Слайд 14

  Метод квайна

  1. Составить таблицу импликант:

• 
  Слайд 15

  Метод Квайна

  2. Выделить существенные импликанты:

• 
  Слайд 16
  

  2. Выделить существенные импликанты. 3. Удалить избыточные столбцы и строки. F =  

• 
  Слайд 17
  

  4. Выбрать минимальное покрытие максимальными интервалами. F = F =  

• 
  Слайд 18

  Геометрический метод

  Fтднф=   Fсднф =  

• 
  Слайд 19
  

  F =   F =  

• 
  Слайд 20
  

  F =  

• 
  Слайд 21

  Метод карт Карно

  Fтднф=   http://ru.wikipedia.org/wiki/Карта_Карно

• 
  Слайд 22
  

  F =   F =  

• 
  Слайд 23
  

  F =  

• 
  Слайд 24

  Эталонная карта Карно для 3 переменных

• 
  Слайд 25

  Эталонная карта для 4 переменных

• 
  Слайд 26

  Правила выбора областей на картах Карно

  Выбираются области 1x1, 1x2, 1x4, 2x2, 2x4, 4x2, 4x4,… клеток В область могут включаться клетки, находящиеся по краям Надо выбрать минимальное количество самых больших областей Существуют эквивалентные покрытия

• 
  Слайд 27

  Примеры склейки

• 
  Слайд 28

  Запись ТДНФ по карте