Квајн–Макласкијев алгоритам
Квајн–Макласкијев алгоритам (енгл. Quine–McCluskey algorithm, метод простих импликаната) је метод који се користи за минимализацију логичких функција који су открили Вилард Ван Орман Квајн и Едвард Џ. Макласки 1956. године.[1][2][3] Овај метод је врло функционалан, баш као и карноове карте, али његова таблична форма га чини лакшим и практичнијим за програмирање, такође, даје и детерминистички пут проналажења минималне форме који управо гарантује да је добијена истинитосна функција минимална. Зову га још и таблични метод.
Метод чине два корака:
- Проналажење простих инпликаната функције.
- Користи те просте импликанте у табели простих импликаната да пронађе само битне просте импликанте функције, као и друге просте импликанте који су потребни да покрију целу функцију.
Комплексност[уреди | уреди извор]
Иако практичнији од карнових карти, када као улаз функција добија више од четири променњиве, Квајн–Макласкијев алгоритам има такође ограничен спектар употребе, јер проблем спада у НП-тешке проблеме: време извршавања Квајн–Макласкијевог алгоритма расте експоненцијално са порастом променљивих. Може се показати да је за функцију од n променњивих горња граница броја примарних импликаната 3n/n. За n = 32 може бити преко 6.5 * 1015 простих импликаната. Функције са великим бројем променљивих морају бити минимализоване са неоптималним хеуристичним методама, заправо алгоритам ESPRESSO је стандард.[4]
Пример[уреди | уреди извор]
Корак 1: проналажење простих импликаната[уреди | уреди извор]
Минимализоваћемо једну произвољну функцију:
Израз назначује да ће излазна вредност функције f бити 1 за улазне вредности 4,8,10,11,12 и 15 (означене са 'm'). Такође, говори да нам излазна вредност уколико улазни подаци одговарају децималним бројевима 9 и 14 нису битне. ('d' означава небитне вредности).
| A | B | C | D | f | ||
|---|---|---|---|---|---|---|
| m0 | 0 | 0 | 0 | 0 | 0 | |
| m1 | 0 | 0 | 0 | 1 | 0 | |
| m2 | 0 | 0 | 1 | 0 | 0 | |
| m3 | 0 | 0 | 1 | 1 | 0 | |
| m4 | 0 | 1 | 0 | 0 | 1 | |
| m5 | 0 | 1 | 0 | 1 | 0 | |
| m6 | 0 | 1 | 1 | 0 | 0 | |
| m7 | 0 | 1 | 1 | 1 | 0 | |
| m8 | 1 | 0 | 0 | 0 | 1 | |
| m9 | 1 | 0 | 0 | 1 | x | |
| m10 | 1 | 0 | 1 | 0 | 1 | |
| m11 | 1 | 0 | 1 | 1 | 1 | |
| m12 | 1 | 1 | 0 | 0 | 1 | |
| m13 | 1 | 1 | 0 | 1 | 0 | |
| m14 | 1 | 1 | 1 | 0 | x | |
| m15 | 1 | 1 | 1 | 1 | 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- не могу. (Напомена: места на којима се налазе '-' морају да се поклапају.)
| Број јединица | Мин члам | 0-коцка | величина 2 импликаната | величина 4 импликаната |
|---|---|---|---|---|
| 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- |
Напомена: У овом примеру, ни један члан величине 4 се не може комбиновати у наставку. Ово имплицира да је крај првог корака алгоритма, уколико би била могућа даља комбиновања алгоритам би требало наставити (чланови величине 8 ).
Корак 2: табела простих импликаната[уреди | уреди извор]
Ни један од чланова не може бити даље комбинован, дакле можемо приступити проналажењу битних примарних импликаната. Редове таблице представљају импликанти који су настали, док колоне чине чланови функције. Небитне вредности нису постављене као засебне колоне - оне су сувишне за овај део алгоритма јер их не морамо имплементирати(нису обавезни као улази).
| 4 | 8 | 10 | 11 | 12 | 15 | => | A | B | C | D | ||
| m(4,12)* | X | X | -100 | => | - | 1 | 0 | 0 | ||||
| m(8,9,10,11) | X | X | X | 10-- | => | 1 | 0 | - | - | |||
| m(8,10,12,14) | X | X | X | 1--0 | => | 1 | - | - | 0 | |||
| m(10,11,14,15)* | X | X | X | 1-1- | => | 1 | - | 1 | - |
Овде, сваки од битних простих импликаната је означен * - други прост импликант може бити покривен трећим и четвртим, и трећи прост импликант може бити покривен другим и првим, међутим то није ни битно. Ако је прост импликант од суштинског значаја, као што је и очекивано, потребно га је укључити у минималну форму. У неким случајевима, битни прости импликатори не покривају све чланове функције, у том случају додатна процедура алгоритма мора бити упошљена. Једноставна "додатна процедура" је пресуђивање и грешка, али више систематичнији начин је Патриков метод. У овом примеру, битни прости импликатори не покривају све чланове, дакле, у овом случају могу се комбиновати битни импликанти са једним од два небитна па се тако добија једно од два могућа решења:
- .
- .
Оба решења су еквивалентна оригиналном , не минималном решењу:
- .
Види још[уреди | уреди извор]
Референце[уреди | уреди извор]
- ^ Quine, W. V. (1952). „The Problem of Simplifying Truth Functions”. The American Mathematical Monthly. 59 (8): 521—531. JSTOR 2308219. doi:10.2307/2308219.
- ^ Quine, W. V. (1955). „A Way to Simplify Truth Functions”. The American Mathematical Monthly. 62 (9): 627—631. JSTOR 2307285. doi:10.2307/2307285.
- ^ McCluskey, E.J., Jr. (1956). „Minimization of Boolean Functions”. Bell System Technical Journal. 35 (6): 1417—1444. doi:10.1002/j.1538-7305.1956.tb03835.x. Приступљено 24. 08. 2014.
- ^ V.P. Nelson e.a., Digital Circuit Analysis and Design, Prentice Hall, 1995, pag. 234
Спољашње везе[уреди | уреди извор]
- Quine-McCluskey algorithm implementation with a search of all solutions Архивирано на сајту Wayback Machine (3. новембар 2013), by Frédéric Carpon.
- All about Quine-McClusky, article by Jack Crenshaw comparing Quine-McClusky to Karnaugh maps
- Kmap minimizer Архивирано на сајту Wayback Machine (3. март 2012) Flash application based on Quine-McCluskey Algorithm.
- Karma 3, A set of logic synthesis tools including Karnaugh maps, Quine-McCluskey minimization, BDDs, probabilities, teaching module and more. Logic Circuits Synthesis Labs (LogiCS), Brazil.
- A. Costa BFunc Архивирано на сајту Wayback Machine (10. јун 2015), QMC based boolean logic simplifiers supporting up to 64 inputs / 64 outputs (independently) or 32 outputs (simultaneously)