Quine-McCluskey-menetelmä

Kokeneet kirjoittajat eivät ole vielä tarkistaneet sivun nykyistä versiota, ja se voi poiketa merkittävästi 28. maaliskuuta 2021 tarkistetusta versiosta . tarkastukset vaativat 23 muokkausta .

Quine – McCluskey -menetelmä on Willard Quinen ehdottama ja Edward McCluskeyn parantama taulukkomenetelmä Boolen funktioiden minimoimiseksi . Se on yritys päästä eroon Quinen menetelmän puutteista .

Minimointialgoritmi

Termit (konjunktiivinen SDNF:n tapauksessa ja disjunktiivinen SKNF :n tapauksessa), joille looginen algebrafunktio (FAL) määritellään, on kirjoitettu niiden binäärivastineiksi;
Nämä vastineet on jaettu ryhmiin, jokaisessa ryhmässä on ekvivalentteja, joissa on yhtä monta ykköstä (nollaa);
Naapuriryhmien ekvivalenttien (termien) parivertailu tehdään alemman tason termien muodostamiseksi;
Kootaan taulukko, jossa rivien otsikot ovat alkutermejä ja sarakkeiden otsikot ovat alempien luokkien termejä;
Laitetaan tarrat, jotka kuvastavat korkeamman luokan termien absorptiota (alkutermit), ja sitten suoritetaan minimointi Quinen menetelmän mukaisesti .

Ominaisuudet

Quine-McCluskey-menetelmän spesifisyys verrattuna Quine-menetelmään on vähentää parivertailujen määrää niiden liimaamiseksi. Vähennys saavutetaan, koska termit jaetaan alun perin ryhmiin, joissa on yhtä suuri määrä ykkösiä (nollia). Näin voidaan sulkea pois vertailut, jotka eivät ilmeisesti anna liimausta.

Vaikka Quine-McCluskey-menetelmällä on enemmän kuin neljä muuttujaa käytännöllisempi kuin Karnaugh-kartat , sillä on myös laajuusrajoituksia, koska menetelmän käyttöaika kasvaa eksponentiaalisesti syötetietojen kasvaessa. Voidaan osoittaa, että n muuttujan funktiolle pääimplikanttien lukumäärän yläraja on 3 n / n . Jos n = 32, voi olla enemmän kuin 6,5 * 10 15 . Katso myös transcomputing problem .

Funktiot, joissa on suuri määrä muuttujia, on minimoitava mahdollisesti alioptimaalisella heuristiikalla . Nykyään espresson minimoinnin heuristinen algoritmi on de facto maailmanstandardi [1] .

Esimerkki

Vaihe 1: etsi tärkeimmät implikantit

Anna funktio seuraavan totuustaulukon avulla :

#	${\näyttötyyli {y}}$	${\näyttötyyli {z))$	${\näyttötyyli {t))$	$f({x},{y},{z},{t})$
0	0	0	0	0
yksi	0	0	yksi	0
2	0	yksi	0	0
3	0	yksi	yksi	0
neljä	yksi	0	0	yksi
5	yksi	0	yksi	0
6	yksi	yksi	0	0
7	yksi	yksi	yksi	0

#	${x}$	${\näyttötyyli {y}}$	${\näyttötyyli {z))$	${\näyttötyyli {t))$	$f({x},{y},{z},{t})$
kahdeksan	yksi	0	0	0	yksi
9	yksi	0	0	yksi	yksi
kymmenen	yksi	0	yksi	0	yksi
yksitoista	yksi	0	yksi	yksi	yksi
12	yksi	yksi	0	0	yksi
13	yksi	yksi	0	yksi	0
neljätoista	yksi	yksi	yksi	0	yksi
viisitoista	yksi	yksi	yksi	yksi	yksi

SDNF voidaan kirjoittaa helposti yksinkertaisesti summaamalla mintermit (jätä huomioimatta epätäydellisesti määritellyt termit ), jossa funktio saa arvon 1.

f={\bar {x}}y{\bar {z}}{\bar {t}}+x{\bar {y}}{\bar {z}}{\bar {t}} +x{\bar {y}}z{\bar {t}}+x{\bar {y}}zt+xy{\bar {z}}{\bar {t}}+xyzt.

Optimointia varten kirjoitamme seuraavaan taulukkoon mintermit, mukaan lukien ne, jotka vastaavat välinpitämättömiä tiloja:

Määrä 1	Minterm	Binääriesitys
yksi	M4	0100
yksi	M8	1000
2	M9	1001
	M10	1010
	M12	1100
3	M11	1011
3	M14	1110
neljä	M15	1111

Nyt voit aloittaa mintermien yhdistämisen keskenään eli liimauksen suorittamisen. Jos kaksi mintermiä eroavat toisistaan vain merkissä, joka on samassa paikassa molemmissa, korvaamme tämän merkin merkillä "-", mikä tarkoittaa, että tällä merkillä ei ole meille merkitystä. Termit, joita ei voida yhdistää muihin yhdistelmiin, on merkitty "*". Kun siirrytään toisen luokan implikantteihin, tulkitsemme "-" kolmantena arvona. Esimerkiksi: -110 ja -100 tai -11- voidaan yhdistää, mutta ei -110 ja 011-. (Vihje: vertaa ensin "-".)

Määrä "1" Minterms | Tason 1 implicantit | Tason 2 implikantit -------------------------------------|-------------- ------- ----|---------------------- 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- |

Vaihe 2: prime implikanttitaulukko

Kun lisäyhdistelmä ei ole enää mahdollista, muodostamme alkuimplikanttien taulukon. Tässä huomioidaan vain ne funktion lähdöt, joilla on merkitystä, eli emme kiinnitä huomiota epätäydellisesti määriteltyihin tiloihin.

	neljä	kahdeksan	9	kymmenen	yksitoista	12	neljätoista	viisitoista
m(4,12)	X					X			-100
m(8,9,10,11)		X	X	X	X				kymmenen--
m(8,10,12,14)		X		X		X	X		1--0
m(10,11,14,15)				X	X		X	X	1-1-

Implikanttivalintaperiaate on sama kuin Quinen menetelmässä . Yksinkertaiset implikantit, jotka ovat ytimiä, on lihavoitu. Tässä esimerkissä ytimet eivät kata kaikkia mintermejä, jolloin voidaan suorittaa ylimääräinen taulukon yksinkertaistamismenettely (katso Petrikin menetelmä ). Saamme seuraavan vaihtoehdon:

f_{x,y,z,t}=y{\bar {z}}{\bar {t}}+x{\bar {y}}+xz.\

Muistiinpanot

↑ VP Nelson ea, Digital Circuit Analysis and Design , Prentice Hall, 1995, sivu. 234

Linkit

Saveliev A.Ya. Tietojenkäsittelytieteen perusteet . - Moskova: Kustantaja MSTU im. N.E. Bauman, 2001. - S. 232-239 . — 328 s. — (Teknillisen yliopiston informatiikka). — ISBN 5703815150 .