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

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

Складність

Незважаючи на більшу можливість практичного застосування ніж у карт Карно, коли мова йде про більше ніж чотири змінних, метод Куайна — Мак-Класкі теж має обмеження області застосування через експоненціальне зростання часу зі збільшенням кількості змінних. Можна показати, що для функції від n змінних верхня границя кількості основних імплікант 3n/n. Якщо n = 32 їх може бути більше ніж 6.5 * 1015. Функції з великою кількістю змінних мають бути мінімізовані з допомогою потенційно не оптимального евристичного алгоритму, на сьогодні евристичний алгоритм мінімізації Еспресо є фактичним світовим стандартом[1].

Приклад

Крок 1: знаходимо основні імпліканти

Нехай функція задана за допомогою наступної таблиці істинності:

#
0 0000 0
1 0001 0
2 0010 0
3 0011 0
4 0100 1
5 0101 0
6 0110 0
7 0111 0
#
8 1000 1
9 1001 x
10 1010 1
11 1011 1
12 1100 1
13 1101 0
14 1110 x
15 1111 1

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

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

Кількість 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: таблиця простих імплікант

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

4810111215
m(4,12)XX-100
m(8,9,10,11)XXX10--
m(8,10,12,14)XXX1--0
m(10,11,14,15)XXX1-1-

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

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

Примітки

  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.
  • , an applet for a step by step analyze of the QMC- algorithm by Christian Roth
  • SourceForge.net C++ program implementing the algorithm.
  • Perl Module by Darren M. Kulp.
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.