Karnaughdiagrammet

Matematikern Maurice Karnaugh, har konstruerat ett diagram-hjälpmedel för minimering av Boolska funktioner, Karnaugh-diagrammet. ( The Map for Synthesis of Combinational Logic Circuits, AIEE, Nov. 1953 ).
Karnaughdiagrammet utnyttjar det faktum att vi människor är duktiga på att känna igen mönster, och på så sätt med diagrammets hjälp kan bestämma vilka termer i en Boolesk funktion som ska kombineras för att ge det enklaste uttrycket. Karnaughdiagrammet kan enkelt användas för funktioner med upp till fyra variabler, och med lite träning upp till sex variabler. För funktioner med fler än sex variabler får datorprogram ta över, och sådana finns det idag gott om.
( Vi kommer här att begränsa oss till fyra variabler - så att ingen behöver bli "yr i huvudet" ).

Exempel. En funktion av fyra variabler a b c d.

Sanningstabellen ovan innehåller 11 st 1:or och 5 st 0:or. Enligt tidigare vet vi att funktionen kan uttryckas på SP-form med 11 st mintermer eller på PS-form med 5 st maxtermer. Den som använt Booles algebra vet att det därefter följer ett mödosamt arbete för att ta fram enklare uttryck. Mintermerna kan kombineras på många olika sätt som alla resulterar i olika förenklade uttryck - hur vet man om man har funnit det enklaste?

I stället för att förenkla funktionen med Booles algebra ska vi här använda metoden med Karnaughdiagram.

Karnaughdiagrammet är den logiska funktionens sanningstabell uppställd på ett annat sätt. En logisk funktion av fyra variabler har en sanningstabell med 16 rader och dessa avbildas i ett Karnaughdiagram som 16 rutor. ( Ettorna/nollorna i Karnaughdiagrammet kommer således från sanningstabellen ). Karnaughdiagrammets rutor är numrerade efter Graykoden så att två rutor som är "grannar" ligger på "enhetsavstånd". De skiljer sig således bara åt i en variabel.

Två "grannar"

Rutorna "5" och "13" är "grannar" i Karnaughdiagrammet ( fast det är långt mellan dem i sanningstabellen ). De svarar mot två mintermer med fyra variabler, och i figuren visas hur de med Booles algebra, kan reduceras till en term med tre variabler. Det de två rutorna har gemensamt är att b=1, c=0 och d=1, och den reducerade termen uttrycker precis detta. ( Termen är en produkt av b, d och c:s invers ).
Överallt i Karnaughdiagrammet där man hittar två ettor som är "grannar" ( vertikalt eller horisontellt ) kan man reducera de mintermerna till det som är gemensamt för de två rutorna. Detta kallas för en hoptagning.

Fyra "grannar"

Rutorna "1" "3" "5" "7" är en grupp av fyra rutor med ettor som ligger som "grannar" till varandra. Även här går de fyra mintermerna att reducera till en term som uttrycker det som är gemensamt för rutorna, nämligen att a=0 och d=1. Överallt i Karnaughdiagrammet där man hittar sådana grupper av fyra ettor kan man göra sådana förenklingar, hoptagningar.

Åtta "grannar"

Alla grupper av 2, 4, 8, ( ... 2^N dvs. med jämna 2-potenser ) rutor som innehåller ettor kan reduceras till en term, med "det som är gemensamt", en hoptagning.

Karnaugh-toroid

Egentligen bör man avbilda Karnaughdiagrammet på en toroid ( en donut ). Når man en kant, så börjar diagrammet om från den motsatta sidan! Ruta 0 är således "granne" med ruta 2, men även "granne" med ruta 8 som är granne med ruta 10. De fyra ettorna i hörnen har b=0 och d=0 gemensamt och kan därför bilda en hoptagning.

Vid lektionen skickar vi runt en Karnaugh-toroid, därefter bör det vara helt klart vad som menas med detta!

Bästa hoptagningar?

Man söker efter så stora hoptagningar som möjligt. I exemplet finns det en hoptagning med åtta ettor ( rutorna 0,1,3,2,4,5,7,6 ). Hörnen ( 0,2,8,10 ) är en hoptagning av fyra ettor. Två av rutorna ( 0,10 ) har redan tagits med i den första hoptagningen, men inget hindrar att en ruta bir medtagen flera gånger.
Alla ettor måste med i funktionen, antingen i en hoptagning, eller som en minterm. Ettan i ruta 13 kan bilda en hoptagning med ettan i ruta 5, någon större hoptagning finns tyvärr inte för denna etta.

Den resulterande funktionen innebär som synes en mycket stor förenkling jämfört med den ursprunkliga funktionen med de 11 mintermerna.

Hoptagning av 0:or

Karnaughdiagrammet är också användbart för hoptagning av 0:or. Hoptagningarna kan omfatta samma antal rutor som i fallet med hoptagning av 1:or. I detta exempel kan 0:orna tas ihop i par med sina "grannar". Maxtermerna förenklas till det som är gemensamt för rutorna.

Det förenklade uttrycket med produkten av tre summor innebär en mycket stor förenkling av den ursprungliga funktionens fem maxtermer.