Логические и арифметические основы и принципы работы ЭВМ


Метод Квайна – Мак – Класки


Основное неудобство метода Квайна состоит в том, что при поиске простых импликант необходимо производить попарные сравнения вначале всех конститутент единицы, затем полученных в результате склеивания произведений.

С целью упрощения этой процедуры Мак – Класки предложил алгоритм, существо которого сводится к следующему:

  1. вводится понятие цифрового эквивалента для каждого произведения по следующему правилу: некоторому произведению ставится в соответствие цифровой эквивалент с использованием цифр 0 и 1 и – (прочерк). Переменной, входящей в произведение в прямом виде ставится в соответствие единица (1), в инверсном – нуль (0), отсутствие переменной обозначается прочерком;
  2. в любом произведении переменные располагаются только в одном порядке, а именно – по возрастанию индексов;
  3. склейке подлежат только те произведения, в которых прочерки расположены соответственно, количество нулей (или единиц) отличается на единицу и они расположены так же соответственно.

Пример:

Произведению x1x2x4 для функции, зависящей от пяти переменных нужно поставить в соответствие следующий цифровой набор: x1x2x4: 11-0-

Приведем графическое изображение процесса поиска простых импликант для функции, представленной в следующей СДНФ:

f(x1x2x3x4) = x1x2x3x4

x1x2x3x4
x1x2x3x4
x1x2x3x4

запишем выражение функции в виде дизъюнкции цифровых эквивалентов:

f(x1x2x3x4) = 1101

1010
0101
1000

При графическом способе отыскания простых импликант вначале все цифровые наборы разбивают на группы и располагают эти группы в следующем порядке: вначале идет группа цифровых эквивалентов, содержащих только нули (такой набор может быть один), затем следует группа с наборами, содержащими по одной единице, затем по две и т.д. Сравнением наборов соседних групп устанавливается возможность склейки, делается необходимая пометка и пишется результат склейки. Процесс продолжается до тех пор, пока возможны склейки. Все несклеенные наборы, а также конечные результаты склейки дают простые импликанты. Расшифровка полученных цифровых эквивалентов - очевидна.




- Начало -    - Вперед -