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

На практике область применения рассмотренных ранее методов минимизации логических функций с использованием карт Карно или Вейча ограничивается числом логических переменных не более пяти. Это объясняется двумя основными причинами:

– при увеличении числа переменных метод теряет свою наглядность, что снижает эффективность его применения;

– так как выбор покрытий производится по большей части интуитивно, то конечный результат минимизации сильно зависит от индивидуального опыта разработчика. Последнее препятствует применению для минимизации ЭВМ.

При увеличении числа переменных для минимизации логических функций используются методы, обладающие однозначностью алгоритма, что является предпосылкой применения ЭВМ. К таким методам относятся метод Квайна и Мак-Класки [3, 7, 11].

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

Пример 2.7. Минимизировать функцию четырех переменных методом Квайна и Мак-Класки.

.

Решение

1 этап. 1. Запишем численно заданную функцию в виде СДНФ

.

Функцию можно записать и через наборы, представленные в двоичной форме:

.

2. Все члены в этой форме СДНФ разбивают на группы по числу единиц, содержащихся в представленных в двоичной форме наборах. Эта разбивка наборов на группы для рассматриваемой функции приведена в графе I этапа табл. 2.7.

Таблица 2.7

Номер группы	Наборы
	I этап	II этап	III этап
0	0000	000* 00*0 0*00 *000	0*0* *0*0 0*0* **00 *0*0 **00
1	0001 0010 0100 1000	0*01 *010 010* *100 10*0 1*00	1**0 1**0
2	0101 1010 1100	01*1 1*10 11*0	01*1
3	0111 1110	*111 111*	*111 111*
4	1111

3. Далее производят склеивание наборов. Склеиваться могут только наборы соседних групп, различающихся лишь в одном разряде. Для этого каждый набор из строки сравнивается с каждым из наборов соседней нижележащей строки. Результат склеивания пары наборов содержит на месте разряда с различающимися значениями в наборах символ * и заносится в графу следующего этапа, а пара склеивающихся наборов подчеркивается (при этом эти наборы должны использоваться в последующих поисках склеивающихся пар наборов). Так, склеивание пары наборов 0001 и 0101 графы I этапа приводит к набору 0*01, записываемому в графе II этапа. Неподчеркнутые наборы также переносятся в следующий этап.

4. Наборы последнего этапа изображают простые импликанты функции, т.е. члены сокращенной ДНФ.

В рассматриваемом примере сокращенная ДНФ функции

.

Эта запись соответствует логическому выражению, получаемому по правилу: каждый набор соответствует отдельной импликанте; каждому символу в наборе соответствует переменная функции с индексом, совпадающим с номером позиции символа в наборе; если символом является *, то соответствующая переменная в выражении импликанты отсутствует; если символом является 0, то соответствующая переменная в выражении импликанты присутствует с инверсией; при символе 1 переменная записывается без инверсии.

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

Отмечаются (например, крестиками) столбцы членов СДНФ, поглощаемых отдельными простыми импликантами. Например, в табл. 2.8 простая импликанта 01*1 поглощает члены 0101 и 0111.

Таблица 2.8

Простые импликанты	Наборы СДНФ
	0000	0001	0010	0100	0101	0111	1000	1010	1100	1110	1111
01*1					×	×
*111						×					×
111*										×	×
0*0*	×	×		×	×
**00	×			×			×		×
*0*0	×		×				×	×
1**0							×	×	×	×

Импликанты, которые не могут быть лишними и, следовательно, не могут быть исключены из сокращенной формы, составляют ядро. Входящие в ядро импликанты легко определяются по импликантной матрице. Для каждой из них имеется хотя бы один столбец, перекрываемый только данной импликантой. В рассматриваемом примере ядро составляют импликанты 0*0* и *0*0 (так как только они перекрывают столбцы 0001 и 0010 соответственно).

2. Далее из таблицы вычеркивают столбцы и строки, покрытые импликантами ядра Квайна. Результат приведен в табл. 2.9.

Таблица 2.9

Простые импликанты	Наборы СДНФ
	0111	1100	1110	1111
01*1	×
*111	×			×
111*			×	×
**00		×
1**0		×	×

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

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

Итак, произведем сжатие по столбцам и строками для нашего примера. Первоначальное сжатие по столбцам не выполняется, так как в таблице отсутствуют столбцы, полностью входящие в любой из оставшихся. Таблица сжимается по строкам, так как первая строка полностью входит во вторую, а четвертая в пятую. Поэтому из таблицы вычеркиваются строки с номерами один и четыре. Оставшаяся таблица может быть сжата по столбцам, так как первый столбец полностью входит в четвертый, в второй столбец – в третий. На основании этого из таблицы вычеркиваются третий и четвертый столбцы. Полученная таблица больше не может быть сжата ни по строкам, ни по столбцам. При этом импликанта 111* является лишней, так как она не покрывает ни одну из оставшихся конституент единицы. Полученная после ее исключения таблица и является циклической.

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

.

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