Минимизация логических функций | MegaDOCs

Минимизация логических функций

ТЕМА 2 Анализ и синтез комбинационных автоматов
ЛЕКЦИЯ 3 Минимизация логических функций

Вопросы лекции:
  1.  Постановка задачи и этапы минимизации логических функций.

Минимизация комбинационных автоматов.

Литература: 

Контрольные вопросы:

1. Постановка задачи и этапы минимизации логических функций 

Структурная схема логически (цифровых) устройств может быть получена непосредственно и по ДНФ или СДНФ (КНФ или СКНФ). Однако, этот метод, обеспечивающий правильность функционирования цифровых устройств, требует использования большого числа логических элементов, имеет низкую экономичность и надежность.

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

Пример. (Лекция 2, пример 3, функция )

Упростим эту функцию, используя операции склеивания (распределительный закон)

Как видно для реализации исходной логической функции необходимо 8 логических элементов: 3 элемента НЕ, 4 трехвходовых элементов И, четырехвходовый элемент ИЛИ. Для реализации упрощенной формулы необходимо только четыре логических элемента (2 элемента НЕ, 2 двухвходовых элементов И, двухвходовый элемент ИЛИ) или один элемент неравнозначность.

На практике для представления логических функций чаще всего используется ДНФ (СДНФ). Поэтому в дальнейшем остановимся на этом представлении.

Вспомним некоторые определения и введем новые.

Дизъюнктивной нормальной формой (ДНФ) логической функции  называется дизъюнкция различных элементарных конъюнкций.

Совершенной дизъюнктивной нормальной формой (СДНФ) логической функции  переменных  называется дизъюнкция элементарных конъюнкций ранга .

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

Задача построения МДНФ носит название минимизации. Она сводится к проблеме выбора базиса (функционально полной системе логических функций) и экономного представления функции в этом базисе.

Иногда ставится аналогичная задача построения ДНФ, содержащей минимальной число конъюнкций. Такая ДНФ называется кратчайшей.

Этапы получения МДНФ.

  1.  Получение сокращенной ДНФ.

Получение всех возможных тупиковых ДНФ.

Выбор МДНФ из тупиковых ДНФ.

2. Минимизация комбинационных автоматов

Комбинационным автоматом называется конечный автомат без памяти.

В комбинационных автоматов, в отличии от автоматов с памятью, существует однозначная зависимость между входными и выходными сигналами

Функционирование КА определяется реализуемой им логической функцией, следовательно, структура КА определяется выбором представления реализуемой функции.

Рассмотрим методы минимизации логических функций, исходное представление которых задано в СДНФ.

Понятия об импликантах логических функций

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

Пример.

В логической функции  импликантами являются все конституенты «1» (логическая функция, единичное значение которой определено только на одном наборе переменных): .

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

Пример.

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

.

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

Минимизация логических функций методом Квайна.

Алгоритм получения сокращенной ДНФ.

  1.  Логическая функция, подлежащая минимизации представляется в СДНФ;
  2.  проводится операция неполного склеивания ко всем возможным парам конъюнкций ();
  3.  выполняется операция поглощения ();
  4.  полученные импликанты  проверяются на «простоту»;
  5.  если полученные импликанты являются простыми, то полученная формула является сокращенной ДНФ, если нет то перейти к 2.

Пример.

1) ;

2) выполним операции склеивания первого и второго, а также третьего и четвертого слагаемых:

  1.  выполним операции поглощения:

4)  являются простыми импликантами, следовательно, полученная формула является сокращенной ДНФ.

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

Трудоемкость отыскания всех возможных пар склеиваемых конъюнкций, особенно при увеличении числа переменных и конституент «1».

Минимизация логических функций методом Квайна-Мак-Класки.

Идея Мак-Класки основана на упрощении процедуры склеивания заменой операций с буквенными выражениями операциями с двоичными числами: каждой конституенте «1» сопоставляется двоичное число, соответствующее номеру набора.

Алгоритм поиска по методу Квайна-Мак-Класки рассмотрим на примере.

  1.  Логической функции  соответствуют числа .
  2.  Числа, отличающиеся значением только в одном разряде, называются соседними, например, .
  3.  Для облегчения поиска соседних чисел (склеиваемых пар) все числа разбиваются на группы имеющие одинаковое количество единиц (индексы чисел), например,. ; .
  4.  Склеиваемые пары ищутся в группах, индекс которых различается на единицу, например, , .
  5.  Все склеиваемые импликанты помечаются, несклеиваемые являются простыми.
  6.  При склеивании соседних чисел в разряд с разными значениями ставится прочерк. Для рассматриваемого примера получим , , ,.. Все полученные наборы имеют одинаковый индекс, следовательно они являются несклеиваемые, их помечаем - они являются простыми импликантами, участвующими в образовании сокращенной ДНФ.
  7.  В результате получим Ск. ДНФ -

Получение тупиковых ДНФ с помощью импликантных таблиц

В Ск. ДНФ могу быть «лишние» простые импликанты. Их необходимо удалить.

Ск. ДНФ, в которой нельзя удалить ни одной простой импликанты называется тупиковой ДНФ (ТДНФ).

В импликантной таблице количество строк соответствует количеству простых импликант в Ск. ДНФ, количеству столбцов - количеству конституент «1» в СДНФ.

Если какая-то импликанта входит в конституенту, то соответствующая ячейка помечается. Каждый столбец оказывается помечен не менее одного раза, что иллюстрирует тот факт получения Ск. ДНФ из СДНФ.

Вычеркиваем строк с импликантами так, чтобы в каждом столбце осталась по крайней мере одна метка.

Составим таблицу для рассмотренного примера.

********

 

Можно вычеркнуть вторую или четвертую строки. В результате получим две возможные тупиковые формы:

.

По количеству различных символов они равнозначны.

Минимизация логических функций картами Карно

Алгоритм минимизации

  1.  Минимизируемая логическая функция представляется картой Карно.

При этом аргументы делятся на две группы, комбинации значений аргументов одной группы приписываются столбцам карты, комбинации значений аргументов другой группы - строкам карты. Столбцы и строки обозначаются комбинациями, соответствующими последовательности чисел в коде Грея (). Единицы заносятся в клетки соответствующие разрешенным наборам.

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

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

Используя все найденные импликанты, находится Ск.ДНФ.

Для получения ТНДФ выбираются такие максимальные контуры, которые по совокупности охватили все единичные клетки, а каждый контур содержал бы хотя бы одну единичную клетку, принадлежащую этому контуру.