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

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

Складність

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

Приклад

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

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

#	${y}$	${z}$	${t}$	$f({x},{y},{z},{t})$
0	0	0	0	0
1	0	0	1	0
2	0	1	0	0
3	0	1	1	0
4	1	0	0	1
5	1	0	1	0
6	1	1	0	0
7	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
1	m8	1000
2	m9	1001
	m10	1010
	m12	1100
3	m11	1011
3	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.\

Примітки

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.

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