Упрощение и оптимизация логических схем. (Лекция 3)

1. Упрощение логических схем

2.

1. Группировка
Применение закона ассоциативности
Применение тождеств – законы отрицания
Пример:
Возможно использование тождества не относящееся к базовым
Пример:

3.

Теорема о непротиворечивости
Пример:
Пусть В·С = Х, а D·E = Y, тогда
Применяя теорему непротиворечивости получаем:

4.

Приведение выражения к каноническому виду с последующем
упрощением
1. Выражение записанное в дизъюнктивной форме можно привести к СДНФ
путём умножения импликат на множитель типа
2.После
раскрытия
скобок,
члены
выражения
могут
быть
перегруппированы, что в результате получится упрощенное выражение.
так
Порядок
выполнения
операций:
сначала
выполняются
операции
конъюнкций, а затем дизъюнкций. В сложных логических выражениях
для задания порядка выполнения используют скобки.
При необходимости для формирования групп можно ввести повторяющиеся
члены.
Пример:

5.

Использование теоремы де Моргана
После инвертирования правых частей
Пример:

6.

Минимизация с помощью карт Карно
Правила разметки:
Вертикальная ось размечается независимо от горизонтальной.
Начинать разметку можно с любого сочетания переменных.
Все сочетания переменных должны быть перечислены.
Для соседних клеток сочетания переменных должны отличаться не более
чем одним знаком.
Соседними являются крайние клетки строки или столбца.

7.

Диаграмма Вейча

8.

Правила составления контуров
Контуры должны быть прямоугольными и содержать количество единиц,
равное 2n, где n – целое число, т.е. в контуре может быть 1, 2, 4, 8. и т. д.
единиц.
Количество единиц в контуре должно быть максимальным, при этом
контуры могут пересекаться между собой.
Количество контуров должно быть минимальным, но все единицы
должны быть охвачены контурами.

9.

Пример 1:
СДНФ → ДНФ

10.

Пример 2:
СДНФ → ДНФ

11.

Пример 3:
СДНФ → ДНФ

12.

Пример 4:
СКНФ → КНФ

13. Построение логических схем

14.

При построении логических схем следует придерживаться следующей
последовательности:
Этап I. Составление таблицы истинности производится на основе
задания содержащего неформальные признаки (определения,
«хотелки») допускающие неоднозначную трактовку.
Основная цель – формализация задания.
Результат этапа – составление задания, неоднозначное
толкование которого невозможно, то есть составление полностью и
однозначно определённой таблицы истинности.
Этап II. Если функция определена не на всех наборах аргументов, то
доопределить функцию нулями или единицами, но так, чтобы
уменьшить число членов СДНФ прямой функции или её инверсии.
Этап III. По полностью определённой таблице истинности составить
СДНФ или несколько СДНФ в зависимости от количества вариантов
доопределения.

15.

Этап IV. Минимизировать СДНФ любым доступным методом.
Этап V. Реализовать получившиеся дизъюнктивные формы на логическом
базисе заданного семейства элементов.
Этап VI. Оценить двойственный вариант логической схемы с учётом
изменения числа входных и выходных инверторов.
Этап VII. Попытаться найти такую декомпозицию функции, чтобы каждый
фрагмент полученного разложения зависел от возможно меньшего числа
аргументов, чем исходная функция. Попытаться выполнить это
различными способами.
Этап VIII. Выбрать из полученных на этапах V, VI, VII вариантов наиболее
подходящих с точки зрения поставленной задачи

16.

Оценка качества функциональных схем
Основные критерии качества функциональной схемы:
1. Время задержки распространения сигнала – Т
2. Аппаратурные затраты – W

17.

Пример.
На логических элементах серии К155 построить оптимальную схему
реализующую ДНФ вида:
Вариант А

18.

К155ЛН1
T = 3t
W = ЛН1 + ЛР3 = 5·1/6 +1 =22/12

19.

Рассмотрим другие варианты реализации заданной переключательной функции
Применив правило де Моргана получим:
К155ЛА3
К155ЛА4
Т = 3·t
Вариант Б
W = 1ЛН1 + 1ЛА3 + 1ЛА4 =
= 3·1/6 + 2·1/4 + 1·1/3 = 16/12

20.

Преобразуем выражение так, чтобы уменьшить количество инверторов на
входе:
К155ЛР1
Вариант В
T = 2·t
W = 1ЛР1 + 1ЛН1 + 1ЛЛ1 =
= 1·1/2 + 1·1/6 + 1·1/4 = 11/12
К155ЛЛ1

21.

T = 3·t
W = 1ЛИ1 + 1ЛЛ1 + 1ЛА3 =
= 1·1/4 + 1·1/4 + 1·1/4 = 9/12
Вариант Д
T = 1·t
W = 12/12 = 1
Вариант Г

22.

Решением задачи оптимизации, с несколькими критериями, является
множество Парето.
х доминирует над х* “по Парето”, если х не хуже х* по всем
критериям и хотя бы по одному критерию превосходит х*. В таком случае в
выборе х* нет смысла, так как х по всем параметрам не уступает, а по какимто и превосходит х.
Говорят, что
Если рассматривать всего два критерия, то на рисунке 1 показана область
пространства, доминируемая решением А. Эта область «замкнута»: элементы
на ее границе также доминируемы А.
Элемент х* {X} – называется
“оптимальным по Парето”, если не
существует такого х {X} , который
будет “лучше”
Рисунок 1 – Доминируемые решения
х*.

23.

Множество оптимальных “по Парето” решений, то есть недоминируемых
решений также называют Парето фронтом.
Рисунок 2 – Парето фронт

24.

Соотношение величин задержек Т и аппаратурных затрат W
W дано в 1/12 долях
• – реальные схемы
х – гипотетические схемы
Множество объектов
оптимальных по Парето.