шпорки) , 1ый семестр (Луцик Ю) / 30 Метод Квайна МакКласки

30 Метод Квайна ?Мак-Класки
Этот метод ориентирован на числовое задание ФАЛ в виде кубического комплекса, состоящего из 0-кубов. Метод представляет собой формализованный на этапе нахождения простых импликант метод Квайна. Основной недостаток метода Квайна - необходимость выполнения полного сравнения (склеивания) всех первичных импликант. В случае большого их количества сложность этого сравнения существенно возрастает
f СДНФ(x1x2x3x4) = V (2, 3, 4, 6, 9, 10, 11, 12).
Сформируем кубический комплекс K, состоящий из 0-кубов:K=(0010, 0011, 0100, 0110, 1001, 1010, 1011, 1100).
Выполнив разбиение комплекса K на группы, получим:

Попарное сравнение можно проводить только между соседними по номеру группами кубов, т. к. кубы, порождающие новые кубы, должны иметь кодовое расстояние, равное 1 .
После выполнения первого шага алгоритма простых импликант не выявлено. Полученные 1-кубы разобьем на n групп кубов в зависимости от местоположения свободной координаты в кубе.
, .
Далее выполняется сравнение кубов внутри каждой из групп. В результате могут быть получены 2-кубы, которые, в свою очередь, аналогично 1-кубам будут объединены в группы по совпадению свободных координат и вновь будет выполнено сравнение. На каждом шаге сравнения выявляются кубы, не участвовавшие в образовании новых кубов, и исключаются из дальнейшего упрощения. Для рассматриваемого примера сравнение в группах … привело к образованию двух новых кубов х01х и х01х и кубов, не образовавших новых {х100, 0х10, 10х1, 01х0}. .
Дальнейшее сравнение не приводит к формированию новых кубов . Таким образом, получено множество простых импликант:
fсокр.ДНФ={х100, 0х10, 10х1, 01х0, х01х} .
Аналогично методу Квайна строится импликантная таблица Формирование мин покрытия сводится к выявлению обязательных простых импликант и построению на их основе тупиковых форм.
простая импликант Конституенты единицы
0010 0100 0011 1100 0110 1001 1010 1011
Х100 * *
0х10 * *
10х1 * *
01х0 * *
Х01х * * * *
Из табл =>, что простые импликанты x100, 10x1, x01x являются обязательными. Оставшиеся две простые импликанты не являются обязательными и образуют следующие две тупиковые формы.
f МДНФ = {х100, 10х1, х01х, 0х10} - 1-я тупиковая форма;
f МДНФ = {х100, 10х1, х01х, 01x0} - 2-я тупиковая форма.