Karnaugh-diagram
Uit Wikipedia, de vrije encyclopedie
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.
[bewerk] Voorbeeld
Neem de volgende functie:
- f(A, B, C, D) = E(6, 8, 9, 10, 11, 12, 13, 14)
Deze functie heeft de volgende waarheidstabel (met 0 voor onwaar en 1 voor waar):
| A | B | C | D | Waarde | A | B | C | D | Waarde | |
|---|---|---|---|---|---|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 | 1 | 0 | 0 | 0 | 1 | |
| 0 | 0 | 0 | 1 | 0 | 1 | 0 | 0 | 1 | 1 | |
| 0 | 0 | 1 | 0 | 0 | 1 | 0 | 1 | 0 | 1 | |
| 0 | 0 | 1 | 1 | 0 | 1 | 0 | 1 | 1 | 1 | |
| 0 | 1 | 0 | 0 | 0 | 1 | 1 | 0 | 0 | 1 | |
| 0 | 1 | 0 | 1 | 0 | 1 | 1 | 0 | 1 | 1 | |
| 0 | 1 | 1 | 0 | 1 | 1 | 1 | 1 | 0 | 1 | |
| 0 | 1 | 1 | 1 | 0 | 1 | 1 | 1 | 1 | 0 |
De invoervariabelen kunnen gecombineerd worden op 16 verschillende manieren, bijgevolg heeft het Karnaugh-diagram 16 posities. De meest geschikte manier om dit te rangschikken is met een raster van 4 op 4:
De binaire getallen in het diagram stellen de uitvoer van de functie voor bij een gegeven combinatie van invoergegevens. We schrijven 0 in de linkerbovenhoek van het diagram omdat f = 0 als A = 0, B = 0, C = 1, D = 0. Volgens dezelfde redenering schrijven we 1 in de rechteronderhoek omdat A = 1, B = 0, C = 0, D = 0 geeft f = 1.
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" exact 2n velden omvatten, waarbij n een geheel getal is ≥ 0 (1, 2, 3, 4...). De omkaderingen moeten ook zo groot mogelijk zijn. De meest optimale kaders worden hierboven getoond in groen, rood en blauw.
Voor elk van deze kaders schrijven we nu de variabelen die dezelfde waarde hebben voor elk van de velden in het kader. Voor het eerste (rode) kader vinden we:
- De variabele A heeft dezelfde waarde (1) in het ganse kader, dus behoort A tot de term van het rode kader.
- Variabele B heeft niet dezelfde waarde (ze verandert van 1 naar 0), dus ze wordt uitgesloten.
- Op dezelfde manier verandert D wel maar C niet.
De eerste term wordt daarom AC.
Voor het groene kader zien we dat A en B dezelfde waarde hebben, C en D veranderen. Maar B is 0 en krijgt dus een negatie voor het aan de term toegevoegd wordt.
De tweede term wordt dus AB'.
Het blauwe kader tenslotte geeft de term BCD' waardoor de volledige expressie gegeven wordt door: AC + AB' + BCD'.
Merk op dat de kaders rond de hoeken kunnen gaan. ABD' is bijvoorbeeld een geldig kader, hoewel het niet getekend kan worden als een gesloten lijn.
De inverse functie kan gevonden worden door de nullen te omcirkelen in plaats van de enen.
