Karnaughdiagram

Från Rilpedia

Texten från svenska Wikipedia

Karnaughdiagram av uttrycket ¬AB¬C¬D ∨ A¬B¬C¬D ∨ A¬B¬CD ∨ A¬BC¬D ∨ A¬BCD ∨ AB¬C¬D ∨ ABC¬D ∨ ABCD = AC ∨ B¬C¬D ∨ A¬B

Ett Karnaughdiagram är ett verktyg eller metod för analys och minimering av booleska uttryck. Diagrammen utnyttjar den mänskliga förmågan att se mönster för att slippa göra många uträkningar.

Metoden uppfanns av Edward W. Veitch 1952 och utvecklades vidare av Maurice Karnaugh 1953 för att förenkla digitalteknikkretsar.

I ett karnaughdiagram förs booleska variabler in, vanligen från en sannings- eller funktionstabell, enligt graykod så att det mellan varje par av angränsande rutor endast finns en variabel som varierar. Sedan fyller man i diagrammet med utvärden och grupperar dessa för att få ett så enkelt logiskt uttryck som möjligt.

Egenskaper

Ett karnaughdiagram kan ha ett godtyckligt antal booleska variabler, men vanligast är fem eller färre. Varje variabel kan ta två värden: startvärdet och sin invers. Därför har ett Karnaughdiagram med n variabler 2ⁿ st rutor. Hur man ordnar dessa rutor beror delvis på hur många variabler karnaughdiagrammet har.

karnaughdiagram för funktionen (¬A+B)(A+¬B) = AB + ¬A¬B

När variablerna är definierade och man vill göra ett karnaughdiagram över (en funktion av) dem, beskriver man rutorna med variablerna och fyller sedan i utvärdena i rutorna i överensstämmelse med positionen i rutnätet.

Varje ruta i ett karnaughdiagram har lika många angränsade rutor som karnaughdiagrammet har variabler.

Mindre Karnaughdiagram

Om karnaughdiagrammet har 1-4 variabler kan man enkelt ordna det i en rektangel om 1x2 (eller 2x1) rutor för 1 variabel, 2x2 (eller 1x4, eller 4x1) rutor för 2 variabler, 4x2 (eller 2x4) rutor för 3 variabler och 4x4 rutor för 4 variabler.

För att man ska kunna gruppera utvärdena i karnaughdiagrammet, får endast en variabel skilja sig åt mellan två intilliggande rutor. För att detta ska gälla måste variablerna arrangeras enligt graykod, både lodrätt och vågrätt. De yttersta kolumnerna, respektive raderna, skiljer sig med bara en variabel och gränsar alltså till varandra över kanterna. Man kan tänka sig att hela diagrammet är en isärklippt torus, eller att man rullar ihop den till en cylinder lodrätt eller vågrätt.

karnaughdiagram med 2 variabler

3 variabler

4 variabler

karnaughdiagram för 5 variabler, visualiserat som två st 4-variablersdiagram över varandra

Större Karnaughdiagram

Om karnaughdiagrammet har fler än 4 variabler, kan man inte konstruera det i ett rektangulärt rutnät där varje ruta har 5 angränsande rutor. Därför brukar man då konstruera det med flera mindre karnaughdiagram som i sig är rutor i ett större, övergripande karnaughdiagram (man kan till exempel illustrera det i 3D som två karnaughdiagram ovanför varandra, se bild).

karnaughdiagram för 5 variabler, den blå rutan angränsar till alla de 5 röda rutorna

Detta innebär till exempel för 5 variabler att man har 2st karnaughdiagram med 4 variabler (4x4), ett där den femte variabeln har sitt startvärde, och ett där den har sin invers. Det betyder att utöver de 4 rutor som en ruta angränsar till i sitt 4x4-diagram, angränsar den även till motsvarande ruta i det angränsande 4x4-diagrammet. Ett annat sätt att konstruera det på vore att göra ett 2-variablers karnaughdiagram över 3-variablers karnaughdiagram, det vill säga som 4 st 4x2-rutors karnaughdiagram.

8 variabler ger ett 4-variablers karnaughdiagram över 4-variablers karnaughdiagram och fler än 8 variabler ger karnaughdiagram över 8-variablers karnaughdiagram. För varje variabel efter var 4:e krävs ytterligare ett överordnat karnaughdiagram. Ett karnaughdiagram med 21 variabler skulle få 6 nivåer, först 5 st 4-variablers karnaughdiagram och sedan ett 1-variabels karnaughdiagram, och sammanlagt 2²¹ st rutor. På detta sätt kan man bygga upp karnaughdiagram av ett godtyckligt antal variabler.

Likhet med Venndiagram

Karnaughdiagram är uppbyggda som ett venndiagram strukturerat i rutor så att man enkelt ska kunna hitta och identifiera grupper av samma utvärden.

karnaughdiagram där rutorna har numrerats som om ABCD vore ett binärtal; svart streck betyder att variabeln är 1 (eller sann) i de raderna/kolumnerna

venndiagram med siffror motsvarande karnaughdiagrammets

Exempel

Exempel 1

Det enklaste sättet att göra ett Karnaughdiagram är att först skriva en sanningstabell. Karnaughdiagrammet för denna tabell innehåller en ruta för varje rad i denna sanningstabell.

Låt oss ta funktionen logisk konjunktion (AND) som exempel. Denna funktion har följande sanningstabell:

I tabellen representerar en nolla värdet falskt och en etta motsv. värdet sant. Eftersom det finns fyra rader i denna tabell så kommer det att finnas fyra rutor i vårt Karnaughdiagram. Vi väljer denna gång att sätta båda variablerna A och B på samma rad.

I den övre raden har vi placerat variablerna A och B i ordningen AB, så de binärtal som syns till höger är skrivna i den ordningen. Snedstrecket före AB har ingen annan betydelse än att vara avskiljare till de variabler som kan finnas i den lodräta kolumnen längst till vänster. Notera att endast en bit ändrar för varje steg vi går åt höger.

I rutan nedanför talet där A = 1 och B = 1, har vi fyllt i en etta, precis som framgår ur sanningstabellen för vår funktion. Så här gör man för hela sanningstabellen och när man är färdig har man fyllt i Karnaughdiagrammet. För klarhets skull skriver man inte ut nollor utan endast ettor.

Exempel 2

Låt oss nu ta ett lite mer omfattande exempel. Låt oss skapa en funktion som har tre variabler, ABC. Funktionen får vara (A ∧ B ) ∨ C. Sanningstabellen blir då följande:

Då vi gör ett Karnaughdiagram av detta placerar vi till exempel variablerna A och B som i föregående exempel på övre raden, men vi placerar C i den lodräta kolumnen till vänster. Sedan placerar vi in resultatet och vi får följande diagram.

Exempel 3: minimering

Med hjälp av Karnaughdiagram kan man även ibland minimera (dvs. förenkla) invecklade booleska uttryck. Detta tas upp i detta exempel.

Minimeringen baserar sig på det faktum att när diagrammet ställts upp korrekt, så skiljer sig närliggande binärtal med endast en bit. Om man hittar två vågrätt eller lodrätt intilliggande rutor i diagrammet, så skiljer sig en variabel i dessa två rutor. Denna blir då irrelevant i sammanhanget och kan förkastas.

I detta exempel tar vi funktionen Y = (¬A ∧ ¬B ∧ C) ∨ (¬A ∧ B ∧ C) ∨ (A ∧ ¬B ∧ ¬C) ∨ (A ∧ ¬B ∧ C). Dess sanningstabell har detta utseende:

Vi gör ett Karnaughdiagram av tabellen och får då följande:

Vi hittar i diagrammet två fall där två intilliggande rutor (vågrätt eller lodrätt) innehåller ettor. Vi börjar med att granska det vågräta fallet. Variabeln A har värdet 0 för båda rutorna, variabeln C har värdet 1 för båda rutorna, och variabel B har värdet 0 i ena och 1 i andra rutan. Därmed, för denna grupp, så har värdet B ingen inverkan på "resultatet". Därmed är variabeln B överflödig i denna grupp och kan förkastas.

I det lodräta fallet är variabel A konstant 1, B konstant 0 och C varierar. Därmed kan C förkastas ur den lodräta gruppen.

Då vi reducerar uttrycket för funktionen ovan tar vi alltså bort B ur de två fall som berörde den vågräta gruppen och C ur de som rörde den lodräta gruppen. Vi har då kvar den minimerade funktionen Z = (¬A ∧ C) ∨ (¬A ∧ C) ∨ (A ∧ ¬B) ∨ (A ∧ ¬B). Då vi ytterligare raderar dubbletterna får vi det enkla uttrycket Z = (¬A ∧ C) ∨ (A ∧ ¬B). Denna funktion har samma sanningstabell som den mer komplicerade funktionen som vi utgick ifrån.