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

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

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

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

Например, соседними являются минтермы Х1·Х2·Х3 и Х1·Х2·Х3, которыеотличаются только формой вхождения Х3.

Минтермы Х1·Х2·Х3 и Х1·Х2·Х3 - не являются соседними.

Два соседних минтерма могут быть склеены. В результате получаем импликанту т.е. конъюкцию, число аргументов в которой на один меньше, чем в исходном минтерме.

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

__ __ __ __ __ __

Х1·Х2·Х3  Х1·Х2·Х3 = Х1·Х2·(Х3·Х3) = Х1·Х2; ( Х3·Х3 = 1),

__

импликанта Х1·Х2 не зависит от Х3.

Процесс склеивания может быть продолжен и для импликант, если они смежные:__ __ __ __ __ __ __ __

( Х1·Х2·Х3·Х4  Х1·Х2·Х3·Х4)  ( Х1·Х2·Х3·Х4  Х1·Х2·Х3·Х4 ) =

__ __ __

I - й этап: = Х1·Х2·Х4  Х1·Х2·Х4 = (склеивание по Х3)

__

II - й этап: = Х1·Х2; (склеивание по Х4).

Итак, при склеивании двух соседних минтермов от n переменных получаем импликанту, которая зависит от (n-1) переменных, при склеивании четырех минтермов - от (n-2) переменных, восьми минтермов - от (n-3) переменных и, в общем случае, при склеивании (2 в степени m) соседних минтермов получаем импликанту от (n-m) переменных. Процесс многоступенчатого склеивания приводит к получению импликант, которые не склеиваются с другими. Такие импликанты называются простыми. Вместе с исходными минтермами, которые не имели соседних и не подвергались процессу склеивания, простые импликанты входят в результирующую ДНФ логической функции, которую называют сокращенной ДНФ.

Простые импликанты, наличие или отсутствие которых в сокращенной ДНФ

не сказывается на значении функции, называются избыточными.

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

Среди методов минимизации ЛФ наибольшее распространение получили метод Квайна и метод карт Карно.

7.1. Метод Квайна

Метод Квайна применяют к ЛФ, заданным в СДНФ. На первом этапе выполняется переход от СДНФ к сокращенной ДНФ путем проведения всех возможных склеиваний. Для этого каждый раз в группе конъюнкций отыскиваются пары A_i·x_i и A_i·x_i, где А_i - общая часть конъюнкций. С учетом закона повторения, каждая конъюнкция может участвовать в нескольких склеиваниях (т.е. она может иметь другую пару A_j·x_j и A_j·x_j ). Полученные импликанты вновь подвергают попарному сравниванию, и так до тех пор, пока не получим сокращенную ДНФ.

Пример:

__1__ __ __ 2 3__ __ 4__ 5

F = Х1·Х2·Х3 + Х1·Х2·Х3 + Х1·Х2·Х3 + Х1·Х2·Х3 + Х1·Х2·Х3.

Проверяем все возможные пары конъюнкций 1-2, 1-4, 1-5, 2-3, 2-4, 2-5, 3-4, 3-5, 4-5 и находим, что склеивание возможно для пар 1-3, 2-5, 3-4, 4-5

( 4-я - 2 раза). __ __ __ __ __ __ __ __

F = ( Х1·Х2·Х3 + Х1·Х2·Х3 ) + ( Х1·Х2·Х3 + Х1·Х2·Х3 ) + (Х1·Х2·Х3 +

__ __ __1__ 2 3__ 4

Х1·Х2·Х3 ) + ( Х1·Х2·Х3 + Х1·Х2·Х3 ) = Х2·Х3 + Х2·Х3 + Х1·Х2 + Х1·Х3.

Опять сравниваем попарно конъюнкции 1-2, 1-3, 1-4, 2-3, 2-4, 3-4. Эти пары уже не смежные, не склеиваются, т.е. получили сокращенную ДНФ.

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

Для выявления лишних простых импликант строится импликантная матрица, которая иногда также называется таблицей покрытий. Каждая строка импликантной матрицы соответствует одной простой импликанте, а столбцы - конъюнкциям исходного выражения ( минтермам ).

1 2 3 4 5

	x1 x2 x3	x1x2x3	x1x2 x3	x1x2x3	x1x2x3
1) x2 x3	x		x
2) x2x3		x			х
3) x1x2			x	x
4) x1x3				х	х

Каждая импликанта сравнивается со всеми минтермами. Если импликанта является частью некоторого минтерма (то есть ее можно получить из минтерма зачеркиванием некоторых букв), то говорят, что импликанта поглощает (покрывает) минтерм, и на пересечении строки и столбца ставится условный знак-отметка. Покрытие означает, что на соответствующих наборах аргументов импликанта обеспечивает единичные значения логической функции. Для нашего примера импликанта (1) покрывает минтермы (1) и (3). Аналогично заполняем и другие строки таблицы. Минимальной ДНФ будет соответствовать такая система минимального количества строк таблицы, которая будет иметь отметки во всех столбцах, то есть будет обеспечивать покрытие всех минтермов. Рекомендуется следующий алгоритм выявления тупиковых ДНФ:

1) Выделяются все обязательные (или существенные) импликанты, которые имеют пометку, единственную в каком-либо столбце. Такие импликанты нельзя удалять, они обязательно будут присутствовать в минимальной ДНФ, и далее они не проверяются.

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

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

Из таблицы примера видим, что простая импликанта (1) обеспечивает единичное значение логической функции на наборе 000 (и только эта импликанта, больше пометок в этом столбце нет), импликанта (2) - на наборе 011 (и она тоже единственная). Поэтому эти импликанты существенные, и их удалять нельзя. Простую импликанту (3) можно считать лишней и вычеркнуть. После этого импликанту (4) вычеркивать нельзя, она осталась единственной в четвертом столбце таблицы. Однако, если изменить порядок испытаний и сначала испытать импликанту (4), то ее можно удалить, но оставить импликанту (3).

В результате получаем две тупиковые ДНФ:

__ __ __

1. F1т = Х2·Х3+Х2·Х3+Х1·Х3, в которую не включена импликанта Х1·Х2;

__ __ __

2) F2т = X2·X3+X2·X3+X1·X2, в которую не включена импликанта Х1·Х3.

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

Для этого метода разработаны различные модификации, в том числе ориентированные на ЭВМ.