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

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до: навігація, пошук

Метод Куайна — Мак-Класкі (метод простих імлікант) - табличний метод мінімізації булевих функцій розроблений Уілардом Куайном і Едвардом Мак-Класкі. Функціонально ідентичний карті Карно, але таблична форма робить його ефективнішим для використання в комп'ютерних алгоритмах.

Складність[ред.ред. код]

Незважаючи на більшу можливість практичного застосування ніж у карт Карно, коли мова йде про більше ніж чотири змінних, метод Куайна — Мак-Класкі теж має обмеження області застосування через експоненціальне зростання часу зі збільшенням кількості змінних. Можна показати, що для функції від 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

Можна легко записати ДДНФ, просто просумувавши мінтерми (не звертаючи увагу на байдужі стани) де функція приймає значення 1.

f = x'yz't' + xy'z't' + xy'zt' + xy'zt + xyz'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} = BC'D' + AB' + AC \
f_{A,B,C,D} = BC'D' + AD' + AC. \

Обидві ці функції функціонально еквівалентні до:

f_{A,B,C,D} = A'BC'D' + AB'C'D' + AB'C'D + AB'CD' + AB'CD + ABC'D' + ABCD' + ABCD. \

Примітки[ред.ред. код]

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

Див. також[ред.ред. код]

Посилання[ред.ред. код]

  • All about Quine-McClusky, стаття Джека Кренча з порівняння методів Куайна - Мак-Класкі та К-карт. (англ.)
  • Kmap minimizer Флеш програма базована методі Куайна - Мак-Класкі. (англ.)
  • Java-Applet Аплет, що мінімізує булеві функції методом Куайна - Мак-Класкі. (нім.)
  • Karma (Karnaugh Map Viewer) – A CAD tool for Karnaugh map manipulation with didactic features in logic circuit synthesis. Uses Quine–McCluskey algorithm to generate a minimal sum of products.
  • Lecture on the Quine–McCluskey algorithm
  • A. Costa BFunc, QMC based boolean logic simplifiers supporting up to 64 inputs / 64 outputs (independently) or 32 outputs (simultaneously)
  • Java applet to display all the generated primes.
  • Python Implementation by Robert Dick.
  • Quinessence, an open source implementation written in Free Pascal by Marco Caminati.
  • A literate program written in Java implementing the Quine-McCluskey algorithm.
  • minBool a MATLAB implementation by Andrey Popov.
  • QCA an open source, R based implementation used in the social sciences, by Adrian Duşa
  • A series of two articles describing the algorithm(s) implemented in R: first article and second article. The R implementation is exhaustive and it offers complete and exact solutions. It processes up to 20 input variables.
  • [1], an applet for a step by step analyze of the QMC- algorithm by Christian Roth
  • [2] SourceForge.net C++ program implementing the algorithm.
  • Perl Module by Darren M. Kulp.