Постановка задачи минимизации, правило склеивания с поглощением

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

· Уменьшение объёмов оборудования

· Обеспечение быстродействия

· Экономия потребляемой энергии

· Уменьшение тепловыделения

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

Правило склеивания с поглощением:

Аx v A  = А

Если два терма в дизъюнктивной форме записи функции имеют общую часть [А] и отличаются одной и только одной переменной, входящий в один из термов в прямой, а в другой – в инверсной форме, то эти два терма склеиваются, а переменная поглощается.

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

Алгоритм:

1) Функция должна быть представлена в СДНФ (СКНФ)

2) Полученные двоичные эквивалентности группируются по количеству единиц.

3) Производится попарное сравнение термов, находящихся в соседних по номеру группах на предмет поиска пар, удовлетворяющих правилу склеивания.

В результате чего формируются термы меньшего ранга (с меньшим количеством переменных) На месте выпавшей при склеивании переменной ставится прочерк.

4) Повторять 3) до тех пор, пока возможно склеивание.

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

5) Составляется импликантная матрица, заголовками столбцов которой являются термы исходной функции, а заголовками строк – тупиковые формы.

6) Расставляются метки вхождений тупиковой формы в исходные термы.

7) Выбирается минимальная совокупность тупиковых форм, которая своими метками покроет все столбцы исходной функции.

8) Двоичные заменяются на буквенные (выпавшие при склеивании переменные отмечаются прочерками)

 

Графические методы минимизации: Диаграммы Вейча

М-кубом или гиперкубом называется группа единиц на диаграмме Вейча, обладающая следующим свойством:

Она имеет прямоугольную форму

Количество единиц, входящее в гиперкуб: 2 4 8 16

       Алгоритм:

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

2) На диаграмме найти группы единиц (нулей), составляющие м-кубы с максимальным количеством единиц (нулей).

3) Выписать конъюнктивные координаты м-кубов и объединить их дизъюнкциями (взять отрицание каждой переменной, заключить термы в скобки и объединить знаком конъюнкции для СКНФ) получить минимальную форму функции.