Quine-McCluskey módszer

Az oldal jelenlegi verzióját még nem ellenőrizték tapasztalt közreműködők, és jelentősen eltérhet a 2021. március 28-án felülvizsgált verziótól ; az ellenőrzések 23 szerkesztést igényelnek .

A Quine – McCluskey módszer egy táblázatos módszer a Boole-függvények minimalizálására ,  amelyet Willard Quine javasolt , és Edward McCluskey fejlesztett tovább . Ez egy kísérlet arra, hogy megszabaduljon Quine módszerének hiányosságaitól .

Minimalizálási algoritmus

  1. A logikai algebrai függvényt (FAL) definiáló kifejezések (SDNF esetén konjunktív és SKNF esetén diszjunktív) bináris megfelelőiként vannak felírva ;
  2. Ezek az ekvivalensek csoportokra vannak osztva, mindegyik csoportban azonos számú egyes (nulla) szerepel;
  3. A szomszédos csoportok ekvivalenseinek (kifejezéseinek) páronkénti összehasonlítása az alacsonyabb rangú tagok kialakítása érdekében történik;
  4. Összeállítunk egy táblázatot, amelyben a sorok fejlécei a kezdeti, az oszlopok fejlécei pedig az alacsony rangú kifejezések;
  5. Olyan címkéket helyezünk el, amelyek a magasabb rangú kifejezések (kezdeti kifejezések) elnyelését tükrözik, majd a minimalizálást Quine módszere szerint hajtjuk végre .

Jellemzők

A Quine-McCluskey módszer sajátossága a Quine módszerrel összehasonlítva, hogy csökkenti a páronkénti összehasonlítások számát a ragasztásukhoz. A csökkentést a kifejezések kezdeti azonos számú egyes (nullák) csoportokra osztása okozza. Ez lehetővé teszi az olyan összehasonlítások kizárását, amelyek nyilvánvalóan nem adnak ragasztást.

Habár négynél több változóról van szó, praktikusabb, mint a Karnaugh-leképezés , a Quine-McCluskey módszernek hatóköri korlátai is vannak, mivel a metódus futási ideje exponenciálisan nő a bemeneti adatok növekedésével. Megmutatható, hogy n változós függvényre a fő implikánsok számának felső korlátja 3 n / n . Ha n = 32, akkor több mint 6,5 * 10 15 lehet . Lásd még: transzszámítási probléma .

A nagyszámú változót tartalmazó függvényeket potenciálisan szuboptimális heurisztikával minimalizálni kell . Ma a presszókávé - minimalizálási heurisztikus algoritmus a de facto világszabvány [1] .

Példa

1. lépés: keresse meg a fő implikánsokat

Adjuk meg a függvényt a következő igazságtáblázat segítségével :

#
0 0 0 0 0 0
egy 0 0 0 egy 0
2 0 0 egy 0 0
3 0 0 egy egy 0
négy 0 egy 0 0 egy
5 0 egy 0 egy 0
6 0 egy egy 0 0
7 0 egy egy egy 0
#
nyolc egy 0 0 0 egy
9 egy 0 0 egy egy
tíz egy 0 egy 0 egy
tizenegy egy 0 egy egy egy
12 egy egy 0 0 egy
13 egy egy 0 egy 0
tizennégy egy egy egy 0 egy
tizenöt egy egy egy egy egy

Az SDNF egyszerűen írható a mintermek egyszerű összegzésével (a nem teljesen definiált kifejezések figyelmen kívül hagyásával ), ahol a függvény az 1 értéket veszi fel.

Az optimalizálás érdekében az alábbi táblázatba írjuk a mintermeket, beleértve azokat is, amelyek közömbös állapotoknak felelnek meg:

1. mennyiség Minterm Bináris ábrázolás
egy M4 0100
M8 1000
2 M9 1001
M10 1010
M12 1100
3 M11 1011
M14 1110
négy M15 1111

Most elkezdheti kombinálni a mintermeket egymással, vagyis végrehajtani a ragasztási műveletet. Ha két minterm csak egy olyan karakterben különbözik, amely mindkettőben azonos pozícióban van, akkor ezt a karaktert „-”-ra cseréljük, ami azt jelenti, hogy ez a karakter számunkra nem számít. Azokat a kifejezéseket, amelyek nem kombinálhatók további kombinációkkal, "*" jelöli. Amikor átadunk a második rangú implikánsoknak, a "-"-t harmadik értékként értelmezzük. Például: -110 és -100 vagy -11- kombinálható, de -110 és 011- nem. (Tipp: Hasonlítsa össze először a "-" jelet.)

Mennyiség "1" Minterms | 1. szintű implikánsok | 2. szintű implikánsok -------------------------------------|-------------- ------- ----|---------------------- 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. lépés: elsődleges implikáns tábla

Ha a további kombináció már nem lehetséges, összeállítunk egy táblázatot a prímimplikánsokról. Itt csak a függvénynek azokat a kimeneteit vesszük figyelembe, amelyek számítanak, vagyis nem figyelünk a hiányosan meghatározott állapotokra.

négy nyolc 9 tíz tizenegy 12 tizennégy tizenöt
m(4,12) x x -100
m(8,9,10,11) x x x x tíz--
m(8,10,12,14) x x x x 1--0
m(10,11,14,15) x x x x 1-1-

Az implikáns szelekciós elv ugyanaz, mint Quine módszerében . Az egyszerű implikánsok, amelyek magok, félkövéren vannak szedve. Ebben a példában a kernelek nem fednek le minden mintermet, ebben az esetben egy további táblázat egyszerűsítési eljárás is végrehajtható (lásd Petrik módszerét ). A következő lehetőséget kapjuk:

Jegyzetek

  1. ↑ Nelson ea alelnök, Digitális áramkör-elemzés és -tervezés , Prentice Hall, 1995, p. 234

Linkek