1. Wat een Karnaugh-diagram is
Een Karnaugh-diagram is een waarheidstabel die opnieuw is getekend als rooster. Maurice Karnaugh presenteerde het in 1953 bij Bell Labs als manier om schakelnetwerken op het oog te vereenvoudigen, en het is nog altijd de snelste manier om een kleine Booleaanse functie met de hand te minimaliseren: geen algebra, geen wetten om te onthouden, alleen rechthoeken.
Elke cel van het diagram bevat één rij van de waarheidstabel. Wat het diagram meer maakt dan een herschikking, is de volgorde waarin die rijen staan: cellen die naast elkaar liggen verschillen in precies één variabele.
Die ene eigenschap doet al het werk. Zijn twee naburige cellen allebei waar, dan kan de variabele die tussen hen verandert niet zijn wat de uitdrukking waar maakt: ze valt weg, en één term dekt beide cellen. Vereenvoudigen wordt zo een kwestie van de grootst mogelijke rechthoeken tekenen.
2. Waarom de kolommen door elkaar lijken te staan
De kolommen van een Karnaugh-diagram tellen niet 00, 01, 10, 11. Ze lopen 00, 01, 11, 10: gereflecteerde Gray-code, een ordening waarin elke waarde in één bit van de volgende verschilt. Binair tellen zou 01 naast 10 zetten, en die verschillen in twee bits: naburige cellen zouden dan niets meer zeggen.
| A \ BC | 00 | 01 | 11 | 10 |
|---|---|---|---|---|
| 0 | 0 | 1 | 3 | 2 |
| 1 | 4 | 5 | 7 | 6 |
Ook de randen zijn buren. De eerste en de laatste kolom verschillen in één variabele, en de bovenste en onderste rij eveneens, dus een groep mag over een rand heen lopen en aan de andere kant verdergaan - daarom vormen de vier hoeken van een diagram met vier variabelen samen één groep. Een Karnaugh-diagram staat eigenlijk op een torus getekend; het platte vel is een gemak.
3. De enen groeperen
Om een minimale som van producten van het diagram af te lezen, dek je elke cel met een 1 af met rechthoekige groepen, volgens vier regels:
- Een groep is een rechthoek van 1, 2, 4, 8 … cellen: een macht van twee langs elke zijde.
- Een groep mag om de randen van het diagram heen lopen, horizontaal, verticaal of allebei.
- Groepen mogen elkaar overlappen. Een cel die twee keer wordt gedekt kost niets; een cel die ongedekt blijft verandert de functie.
- Maak elke groep zo groot als hij kan worden en gebruik daarna zo weinig groepen als alle enen dekken.
Elke groep wordt één term. Je leest hem af door te vragen welke variabelen over de hele groep gelijk blijven: die staan in de term - ongewijzigd waar ze 1 zijn, ontkend waar ze 0 zijn - en elke variabele die verandert valt weg. Een groep van twee cellen verliest één variabele, een van vier verliest er twee, een van acht drie. De minimale uitdrukking is de disjunctie van de termen.
4. Een uitgewerkt voorbeeld
Neem (A ∧ B) ∨ (¬A ∧ C) ∨ (B ∧ C ∧ D). Het diagram heeft vier variabelen: A en B in de rijen, C en D in de kolommen.
| AB \ CD | 00 | 01 | 11 | 10 |
|---|---|---|---|---|
| 00 | 0 | 0 | 1 | 1 |
| 01 | 0 | 0 | 1 | 1 |
| 11 | 1 | 1 | 1 | 1 |
| 10 | 0 | 0 | 0 | 0 |
Twee groepen dekken alle enen. De ene is het blok van vier cellen in de twee rijen waar A = 0 en de twee kolommen waar C = 1: daarbinnen veranderen B en D, dus die vallen weg en de term is ¬A ∧ C. De andere is de hele rij waarin A en B allebei 1 zijn, over alle vier de kolommen: C en D veranderen erover, en A ∧ B blijft over.
De minimale vorm is dus (¬A ∧ C) ∨ (A ∧ B). De derde term van het origineel, B ∧ C ∧ D, is verdwenen: elke cel die hij dekte was al gedekt door een van de twee groepen. Zo ziet absorptie eruit als je haar kunt zien.
5. Priem- en essentiële implicanten
Een groep die niet groter kan worden gemaakt heet een priemimplicant. De priemimplicanten opsommen is de makkelijke helft van het probleem; kiezen welke je houdt is de helft die misgaat.
Wordt een cel door maar één priemimplicant gedekt, dan is die implicant essentieel: geen enkele minimale vorm kan hem weglaten, want niets anders dekt die cel. Neem eerst de essentiële implicanten en dek wat overblijft met zo weinig mogelijk van de overige groepen.
Gulzig zijn - telkens de grootste nog beschikbare groep pakken - is verleidelijk en werkt niet altijd. Op een cyclisch schema, waar geen enkele implicant essentieel is en elke cel dubbel wordt gedekt, kan de gulzige keuze met één term meer eindigen dan het beste antwoord. Het diagram op deze site doorzoekt in plaats daarvan alle overgebleven keuzes, wat bij vier variabelen niets kost.
6. In plaats daarvan de nullen groeperen
Alles hierboven werkt net zo goed op de nullen. Dek ze af met dezelfde rechthoeken, lees elke groep met ontkende literalen - een variabele die over de hele groep 1 is verschijnt ontkend, een die 0 is verschijnt ongewijzigd - en verbind de groepen met ∧ in plaats van ∨.
Het resultaat is een product van sommen: een conjunctie van disjuncties die onwaar is in precies de cellen waarin de uitdrukking onwaar is, en dus overal elders waar. Welke vorm korter is hangt van de functie af - een formule met weinig enen heeft een korte som van producten, een met weinig nullen een kort product van sommen - dus loont het de moeite beide van het diagram af te lezen voordat je kiest.
7. Grotere diagrammen en don't-cares
Vijf en zes variabelen kun je tekenen als twee of vier diagrammen met vier variabelen op elkaar gestapeld, waarbij cellen op dezelfde plek in naburige lagen als aangrenzend gelden. Het werkt, maar de aangrenzing die de methode zichtbaar maakte, moet je nu onthouden in plaats van zien. Daarboven doet het algoritme van Quine-McCluskey hetzelfde werk als tabel: het is de mechanische vorm van precies deze groepering, en het draait achter de diagrammen hier.
Hardwareontwerp voegt nog één idee toe. Sommige invoercombinaties komen nooit voor - een binair gecodeerd decimaal cijfer is nooit 1010 - dus kan het de ontwerper niet schelen wat de schakeling ermee doet. Die cellen krijgen een X en mogen als beide waarden worden gelezen, welke de groepen ook maar groter maakt. De diagrammen in deze rekenmachine komen uit een formule, die elke toekenning een waarde geeft, dus is hier geen enkele cel een don't-care.
8. Probeer het zelf
Typ een uitdrukking van twee tot vier variabelen in de rekenmachine en het diagram verschijnt onder de waarheidstabel, met elke groep in zijn eigen kleur omcirkeld en de minimale vorm eronder uitgeschreven. Zet hem op product van sommen om in plaats daarvan de nullen gegroepeerd te zien.