Quine-McCluskey-metoden

Den aktuella versionen av sidan har ännu inte granskats av erfarna bidragsgivare och kan skilja sig väsentligt från versionen som granskades den 28 mars 2021; kontroller kräver 23 redigeringar .

Quine –McCluskey-metoden är en  tabellform för att minimera booleska funktioner som föreslagits av Willard Quine och förbättrats av Edward McCluskey . Det är ett försök att bli av med bristerna i Quines metod .

Minimeringsalgoritm

  1. Termerna (konjunktiva i fallet med SDNF och disjunktiva i fallet med SKNF ) på vilka den logiska algebrafunktionen (FAL) är definierad skrivs som deras binära ekvivalenter;
  2. Dessa ekvivalenter är indelade i grupper, varje grupp inkluderar ekvivalenter med lika många ettor (nollor);
  3. En parvis jämförelse av ekvivalenter (termer) i angränsande grupper görs för att bilda termer av lägre rang;
  4. En tabell sammanställs där rubrikerna på raderna är de initiala termerna, och rubrikerna på kolumnerna är termerna för låga rangord;
  5. Etiketter placeras som återspeglar absorptionen av termer av högre rang (initial termer) och sedan utförs minimering enligt Quines metod .

Funktioner

Specificiteten hos Quine-McCluskey-metoden i jämförelse med Quine-metoden är att minska antalet parvisa jämförelser för deras limning. Minskningen uppnås på grund av den initiala indelningen av termer i grupper med lika många ettor (nollor). Detta gör det möjligt att utesluta jämförelser som uppenbarligen inte ger limning.

Även om det är mer praktiskt än Karnaugh-kartor när det kommer till fler än fyra variabler, har Quine-McCluskey-metoden också begränsningar i omfattningen, eftersom metodens körtid växer exponentiellt med ökande indata. Det kan visas att för en funktion av n variabler är den övre gränsen för antalet huvudimplikanter 3 n / n . Om n = 32 kan det vara fler än 6,5 * 10 15 . Se även omräkningsproblem .

Funktioner med ett stort antal variabler måste minimeras med en potentiellt suboptimal heuristik . Idag är den heuristiska algoritmen för espressominimering den de facto världsstandarden [1] .

Exempel

Steg 1: hitta de viktigaste implikanterna

Låt funktionen ges med hjälp av följande sanningstabell :

#
0 0 0 0 0 0
ett 0 0 0 ett 0
2 0 0 ett 0 0
3 0 0 ett ett 0
fyra 0 ett 0 0 ett
5 0 ett 0 ett 0
6 0 ett ett 0 0
7 0 ett ett ett 0
#
åtta ett 0 0 0 ett
9 ett 0 0 ett ett
tio ett 0 ett 0 ett
elva ett 0 ett ett ett
12 ett ett 0 0 ett
13 ett ett 0 ett 0
fjorton ett ett ett 0 ett
femton ett ett ett ett ett

Man kan enkelt skriva SDNF genom att helt enkelt summera mintermerna (ignorera ofullständigt definierade termer ), där funktionen tar värdet 1.

För optimering skriver vi mintermerna, inklusive de som motsvarar likgiltiga tillstånd, i följande tabell:

Kvantitet 1 Minterm Binär representation
ett M4 0100
M8 1000
2 M9 1001
M10 1010
M12 1100
3 M11 1011
M14 1110
fyra M15 1111

Nu kan du börja kombinera minterms med varandra, det vill säga utföra limningsoperationen. Om två mintermer skiljer sig endast i ett tecken som är i samma position i båda, ersätter vi detta tecken med "-", vilket betyder att detta tecken inte spelar någon roll för oss. Termer som inte är tillgängliga för ytterligare kombination betecknas med "*". När vi övergår till implikanter av den andra rangen tolkar vi "-" som det tredje värdet. Till exempel: -110 och -100 eller -11- kan kombineras, men inte -110 och 011-. (Tips: Jämför "-" först.)

Kvantitet "1" Minterms | Nivå 1 implikanter | Nivå 2 implikanter ------------------------------------|------------- ------- ----|--------------------- 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- |

Steg 2: prime implicant table

När ytterligare kombination inte längre är möjlig, konstruerar vi en tabell med primära implikanter. Här tar vi bara hänsyn till de utgångar från funktionen som spelar roll, det vill säga vi uppmärksammar inte ofullständigt definierade tillstånd.

fyra åtta 9 tio elva 12 fjorton femton
m(4,12) X X -100
m(8,9,10,11) X X X X tio--
m(8,10,12,14) X X X X 1--0
m(10,11,14,15) X X X X 1-1-

Den implikanta urvalsprincipen är densamma som i Quines metod . Enkla implikanter som är kärnor visas i fet stil. I det här exemplet täcker inte kärnorna alla minterms, i vilket fall en ytterligare tabellförenklingsprocedur kan utföras (se Petriks metod ). Vi får följande alternativ:

Anteckningar

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

Länkar