Karnaugh-diagram

Uit Wikipedia, de vrije encyclopedie
Ga naar: navigatie, zoeken

Een Karnaugh-diagram of ook wel een Veitch-diagram is een hulpmiddel om expressies in Booleaanse algebra te vereenvoudigen. Het diagram werd uitgevonden in 1950 door Maurice Karnaugh, een telecommunicatie-ingenieur bij Bell Labs.

Dikwijls zijn er uitgebreide berekeningen nodig om een Booleaanse expressie of functie zo eenvoudig mogelijk te schrijven, maar met een Karnaugh-diagram kan dit vaak sneller. Doordat het menselijk brein gemakkelijk patronen kan herkennen, helpt het diagram om snel op te zoeken welke termen gecombineerd kunnen worden om een expressie te vereenvoudigen. Daarenboven kan men met Karnaugh-diagrammen snel herkennen waar eventueel een zogenaamde "race condition" zou kunnen voorkomen, en men kan ze dan ook verwijderen, wat met Booleaanse expressies alleen niet kan.

Een Karnaugh-diagram is geschikt voor vereenvoudigen tot maximaal zes variabelen; meer variabelen maken het zelfs voor het brein moeilijk om nog patronen te herkennen. Voor expressies met meer dan 4 variabelen is het beter het Quine-McCluskey-algoritme te gebruiken. Heden ten dage wordt voor dit doel echter in de regel de veel efficiëntere Espresso heuristische logische minimalisator toegepast.

Karnaugh-diagrammen zijn ook nuttig bij het aanleren van Booleaanse functies en minimalisatie.

Voorbeeld[bewerken]

De functie heeft de volgende waarheidstabel (met 0 voor onwaar en 1 voor waar):

Waarde van Waarde van
0 0 0 0 0 0 8 1 0 0 0 1
1 0 0 0 1 0 9 1 0 0 1 1
2 0 0 1 0 0 10 1 0 1 0 1
3 0 0 1 1 0 11 1 0 1 1 1
4 0 1 0 0 0 12 1 1 0 0 1
5 0 1 0 1 0 13 1 1 0 1 1
6 0 1 1 0 1 14 1 1 1 0 1
7 0 1 1 1 0 15 1 1 1 1 0

De waarheidstabel wordt anders weergegeven door de invoervariabelen en in paren en tegen elkaar uit te zetten. De waarden van deze paren zijn geordend in Gray-code, om ervoor te zorgen dat in twee opeenvolgende waarden er slechts één variabele verandert.

Het zo ontstane Karnaugh-diagram is een 4 bij 4 diagram, met in het veld de functiewaarde

Sample Karnaugh map, style #1.

Als eenmaal de getallen ingevuld zijn, is de volgende stap het vinden van minimale termen voor de uiteindelijke expressie. Deze termen kunnen gevonden worden door de enen in het diagram te omkaderen. Dit moet gebeuren op een dusdanige manier dat de "kaders" rechthoekig zijn en exact velden omvatten, waarbij een natuurlijk getal is groter dan 0. De omkaderingen moeten ook zo groot mogelijk zijn. De optimale kaders worden hierboven getoond in groen, rood en blauw.

Voor elk van deze kaders wordt nagegaan welke variabele in alle velden van het kader dezelfde waarde heeft. Voor het eerste (rode) kader blijkt:

  • De variabele heeft dezelfde waarde (1) in het hele kader, dus behoort tot de term die hoort bij het rode kader.
  • De variabele heeft niet dezelfde waarde (ze verandert van 1 naar 0), dus wordt ze uitgesloten.
  • Op dezelfde manier verandert wel, maar niet. is hier altijd gelijk aan 0.

Omdat wordt de negatie aan de term toegevoegd. De eerste term wordt daarom

In het groene kader is in elk veld en maar veranderen en De tweede term wordt daarom

In het blauwe kader ten slotte is en verandert van waarde, zodat de derde term is.

De volledige expressie wordt dus gegeven door

Men verifieert eenvoudig dat bijvoorbeeld

De inverse functie kan gevonden worden door de nullen te omcirkelen in plaats van de enen.

Zie ook[bewerken]

Externe links[bewerken]