Метод Куайна — Мак-Класки

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

Метод Куайна—Мак-Класки (англ. Quine–McCluskey method) — табличный метод минимизации булевых функций, предложенный Уиллардом Куайном и усовершенствованный Эдвардом Мак-Класки. Представляет собой попытку избавиться от недостатков метода Куайна.

Алгоритм минимизации[править | править вики-текст]

  1. Термы (конъюнктивные в случае СДНФ и дизъюнктивные в случае СКНФ), на которых определена ФАЛ записываются в виде их двоичных эквивалентов;
  2. Эти эквиваленты разбиваются на группы, в каждую группу входят эквиваленты с равным количеством единиц (нулей);
  3. Производится попарное сравнение эквивалентов (термов) в соседних группах, с целью формирования термов более низких рангов;
  4. Составляется таблица, заголовком строк в которой являются исходные термы, а заголовком столбцов — термы низких рангов;
  5. Расставляются метки, отражающие поглощение термов высших рангов (исходных термов) и далее минимизация производится по методу Куайна.

Особенности[править | править вики-текст]

Специфика метода Куайна — Мак-Класки по сравнению с методом Куайна в сокращении количества попарных сравнений на предмет их склеивания. Сокращение достигается за счет исходного разбиения термов на группы с равным количеством единиц (нулей). Это позволяет исключить сравнения, заведомо не дающие склеивания.

Несмотря на большую возможность практического применения чем у карт Карно когда речь идёт о более чем четыре переменных, метод Куайна—Мак-Класки тоже имеет ограничения области применения, так как время работы метода растёт экспоненциально с увеличением входных данных. Можно показать, что для функции от n переменных верхняя граница количества основных импликант 3n/n. Если n = 32 их может быть больше чем 6.5 * 1015. См. также Трансвычислительная задача.

Функции с большим количеством переменных должны быть минимизированы с помощью потенциально не оптимального эвристического алгоритма. На сегодня эвристический алгоритм минимизации эспрессо является фактическим мировым стандартом[1].

Пример[править | править вики-текст]

Шаг 1: находим основные импликанты[править | править вики-текст]

Пусть функция задана с помощью следующей таблицы истинности:

# {x} {y} {z} {t} f({x}, {y}, {z}, {t})
0 0 0 0 0 0
1 0 0 0 1 0
2 0 0 1 0 0
3 0 0 1 1 0
4 0 1 0 0 1
5 0 1 0 1 0
6 0 1 1 0 0
7 0 1 1 1 0
# {x} {y} {z} {t} f({x}, {y}, {z}, {t})
8 1 0 0 0 1
9 1 0 0 1 x
10 1 0 1 0 1
11 1 0 1 1 1
12 1 1 0 0 1
13 1 1 0 1 0
14 1 1 1 0 x
15 1 1 1 1 1

Можно легко записать CДНФ, просто просуммировав минтермы (не обращая внимание на неполностью определённые термы), где функция принимает значение 1.

f = \bar x y \bar z \bar t + x \bar y \bar z \bar t + x \bar y z \bar t + xy \bar z t + xy \bar z \bar t + xyzt.

Для оптимизации запишем минтрермы, включая те, которые соответствуют равнодушным состояниям, в следующую таблицу:

Количество 1 Минтерм Двоичное представление
1 M4 0100
M8 1000
2 M9 1001
M10 1010
M12 1100
3 M11 1011
M14 1110
4 M15 1111

Теперь можно начинать комбинировать между собой минтермы, то есть проводить операцию склеивания. Если два минтерма отличаются лишь символом, стоит в одной и той же позиции в обеих, заменяем этот символ на «-», это означает, что данный символ для нас не имеет значения. Термы, не поддающиеся дальнейшему комбинированию, обозначаются «*». При переходе к импликантам второго ранга, трактуем «-» как третье значение. Например: −110 и −100 или −11- могут быть скомбинированы, но не −110 и 011-. (Подсказка: Сначала сравнивай «-».)

 Количество "1"   Минтермы     | Импликанты 1-го уровня | Импликанты 2-го уровня
 ------------------------------|-----------------------|----------------------
 1             m4       0100   | m(4,12)  -100*        | m(8,9,10,11)   10--*
               m8       1000   | m(8,9)   100-         | m(8,10,12,14)  1--0*
 ------------------------------| m(8,10)  10-0         |----------------------
 2             m9       1001   | m(8,12)  1-00         | m(10,11,14,15) 1-1-*
               m10      1010   |-----------------------|
               m12      1100   | m(9,11)  10-1         |
 ------------------------------| m(10,11) 101-         |
 3             m11      1011   | m(10,14) 1-10         |
               m14      1110   | m(12,14) 11-0         |
 ------------------------------|-----------------------|
 4             m15      1111   | m(11,15) 1-11         |
                               | m(14,15) 111-         |

Шаг 2: таблица простых импликант[править | править вики-текст]

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

4 8 10 11 12 15
m(4,12) X X -100
m(8,9,10,11) X X X 10--
m(8,10,12,14) X X X 1—0
m(10,11,14,15) X X X 1-1-

Принцип выбора импликант такой же как и в методе Куайна. Простые импликанты, которые является ядрами выделены жирным шрифтом. В этом примере, ядра не перекрывают все минтермы, в таком случае может быть выполнена дополнительная процедура упрощения таблицы (см. Метод Петрика). Есть два варианта:

f_{A,B,C,D} = B \bar C \bar D + A \bar B + AC \
f_{A,B,C,D} = B \bar C \bar D + A \bar D + AC. \


Примечания[править | править вики-текст]

  1. V.P. Nelson e.a., Digital Circuit Analysis and Design, Prentice Hall, 1995, pag. 234

Литература[править | править вики-текст]

  • Савельев А.Я. Основы информатики. — Москва: Издательство МГТУ им. Н.Э. Баумана, 2001. — С. 232—239. — 328 с. — (Информатика в техническом университете). — ISBN 5703815150.