Минимизация методом Квайна-Мак-Класки
Метод минимизации Квайна-Мак-Класки является одним из систематических методов, основанных на формализованном порядке упрощения формул. Метод описывается строгим алгоритмом, поддается программированию и его применение дает возможность использовать ЭВМ, что неизбежно при минимизации ФАЛ большого числа переменных. При минимизации функций алгебры логики по этому методу последовательно выполняются два этапа преобразования выражения функции: на первом переходят от канонической формы к сокращенной, на втором - от сокращенной формы логического выражения к минимальной. Процедуру минимизации в соответствии с этим методом обычно выполняют по десятичным или двоичным эквивалентам конституент заданной функции. Пусть функция задана своими единичными наборами, представленными десятичными кодами f = {0,1,2,3,4,5,6,7,8,9,11,15} X 1 X 2 X 3 X 4, что соответствует аналитическому заданию функции алгебры логики
Наборы разбиваются на группы так, чтобы члены любой группы в своем двоичном представлении имели одинаковое число единиц (табл.4.12). Число единиц в двоичном коде можно назвать его весом, тогда все члены одной группы будут иметь одинаковый вес. Каждый член группы, начиная с первого набора первой группы, сравниваем последовательно со всеми членами следующей группы, в результате чего будет происходить исключение одной переменной, на месте которой будем ставить прочерк. Таблица 4.12
Результаты сравнения приведены в табл.4.13. Каждый член, участвующий в сравнении, отмечен.
|
