Kvajn–Maklaskijev algoritam
Kvajn–Maklaskijev algoritam (engl. Quine–McCluskey algorithm, metod prostih implikanata) je metod koji se koristi za minimalizaciju logičkih funkcija koji su otkrili Vilard Van Orman Kvajn i Edvard Dž. Maklaski 1956. godine.[1][2][3] Ovaj metod je vrlo funkcionalan, baš kao i karnoove karte, ali njegova tablična forma ga čini lakšim i praktičnijim za programiranje, takođe, daje i deterministički put pronalaženja minimalne forme koji upravo garantuje da je dobijena istinitosna funkcija minimalna. Zovu ga još i tablični metod.
Metod čine dva koraka:
- Pronalaženje prostih inplikanata funkcije.
- Koristi te proste implikante u tabeli prostih implikanata da pronađe samo bitne proste implikante funkcije, kao i druge proste implikante koji su potrebni da pokriju celu funkciju.
Kompleksnost
urediIako praktičniji od karnovih karti, kada kao ulaz funkcija dobija više od četiri promennjive, Kvajn–Maklaskijev algoritam ima takođe ograničen spektar upotrebe, jer problem spada u NP-teške probleme: vreme izvršavanja Kvajn–Maklaskijevog algoritma raste eksponencijalno sa porastom promenljivih. Može se pokazati da je za funkciju od n promennjivih gornja granica broja primarnih implikanata 3n/n. Za n = 32 može biti preko 6.5 * 1015 prostih implikanata. Funkcije sa velikim brojem promenljivih moraju biti minimalizovane sa neoptimalnim heurističnim metodama, zapravo algoritam ESPRESSO je standard.[4]
Primer
urediKorak 1: pronalaženje prostih implikanata
urediMinimalizovaćemo jednu proizvoljnu funkciju:
Izraz naznačuje da će izlazna vrednost funkcije f biti 1 za ulazne vrednosti 4,8,10,11,12 i 15 (označene sa 'm'). Takođe, govori da nam izlazna vrednost ukoliko ulazni podaci odgovaraju decimalnim brojevima 9 i 14 nisu bitne. ('d' označava nebitne vrednosti).
| 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 |
Lako se može formirati izraz kanonskog zbira proizvoda iz ove tabele, upravo sumirajući kolone na kojima se kao izlazna vrednost dobija 1 (bez nebitnih vrednosti).
Ova funkcija nije minimalna. Da bi je optimizovali, potrebno je grupisati sve članove Funkcije, tako da svi članovi jedne grupe imaju isti broj cifara "1" u svojoj binarnoj predstavi. Nebitne vrednosti su takođe ubačene u tablu tako da se mogu kombinovati sa članovima funkcije.
| Broj jedinica | Min član | Binarna reprezenzacija |
|---|---|---|
| 1 | m4 | 0100 |
| m8 | 1000 | |
| 2 | m9 | 1001 |
| m10 | 1010 | |
| m12 | 1100 | |
| 3 | m11 | 1011 |
| m14 | 1110 | |
| 4 | m15 | 1111 |
U ovom trenutku možemo početi sa kombinovanjem članova funkcije sa drugim članovima. Ukoliko se dva člana razlikuju na tačno jednom mestu(u binarnom obliku) ta cifra biva zamenjena crticom '-', što implicira da ona nije bitna. Članovi koji više ne mogu biti kombinovane su označene sa '*'. Kada se prelazi sa kombinacija veličine dva, na kombinacije veličine četiri, smatrati '-' kao treću vrednost bitova. Primer: -110 i -100 ili -11- mogu biti kombinovane, međutim, -110 i 011- ne mogu. (Napomena: mesta na kojima se nalaze '-' moraju da se poklapaju.)
| Broj jedinica | Min člam | 0-kocka | veličina 2 implikanata | veličina 4 implikanata |
|---|---|---|---|---|
| 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- |
Napomena: U ovom primeru, ni jedan član veličine 4 se ne može kombinovati u nastavku. Ovo implicira da je kraj prvog koraka algoritma, ukoliko bi bila moguća dalja kombinovanja algoritam bi trebalo nastaviti (članovi veličine 8 ).
Korak 2: tabela prostih implikanata
urediNi jedan od članova ne može biti dalje kombinovan, dakle možemo pristupiti pronalaženju bitnih primarnih implikanata. Redove tablice predstavljaju implikanti koji su nastali, dok kolone čine članovi funkcije. Nebitne vrednosti nisu postavljene kao zasebne kolone - one su suvišne za ovaj deo algoritma jer ih ne moramo implementirati(nisu obavezni kao ulazi).
| 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 | - |
Ovde, svaki od bitnih prostih implikanata je označen * - drugi prost implikant može biti pokriven trećim i četvrtim, i treći prost implikant može biti pokriven drugim i prvim, međutim to nije ni bitno. Ako je prost implikant od suštinskog značaja, kao što je i očekivano, potrebno ga je uključiti u minimalnu formu. U nekim slučajevima, bitni prosti implikatori ne pokrivaju sve članove funkcije, u tom slučaju dodatna procedura algoritma mora biti upošljena. Jednostavna "dodatna procedura" je presuđivanje i greška, ali više sistematičniji način je Patrikov metod. U ovom primeru, bitni prosti implikatori ne pokrivaju sve članove, dakle, u ovom slučaju mogu se kombinovati bitni implikanti sa jednim od dva nebitna pa se tako dobija jedno od dva moguća rešenja:
- .
- .
Oba rešenja su ekvivalentna originalnom , ne minimalnom rešenju:
- .
Vidi još
urediReference
uredi- ^ 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. Pristupljeno 24. 08. 2014.
- ^ V.P. Nelson e.a., Digital Circuit Analysis and Design, Prentice Hall, 1995, pag. 234
Spoljašnje veze
uredi- 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)