Karnaughkaarten

Karnaughkaarten, ook wel K-­map genoemd, is een diagrammethode voor het vereenvoudigen van Booleaanse functies. Ze is ontwikkeld door Maurice Karnaugh in 1953 en biedt een visuele manier om minimale logische vergelijkingen te vinden die een functionele relatie weergeven. De kaart werd geïnspireerd door eerdere werk van Veitch en wordt veel toegepast in digitaal ontwerp en logic synthesis.

Een Karnaughkaart is een rooster waarin elke cel overeenkomt met een minterm van de variabelen van de functie. De variabelen worden zo gerangschikt dat buurcellen elkaar in precies één variabele onderscheiden ( Gray-code volgorde). Meestal worden kaarten met twee tot vier variabelen gebruikt (2×2, 2×4, of 4×4), terwijl kaarten met meer variabelen complexer zijn. Een cel wordt gemarkeerd als 1 als de functie bij die combinatie van variabelen waar is, en soms kunnen “don’t-care”-toestanden worden ingevuld als 1 om grotere groepen mogelijk te maken.

Het kernprincipe is het vormen van de grootste mogelijke groepen van aangrenzende 1’s die een macht van twee vormen (1, 2, 4, 8, …). Groepen kunnen over randen heen wrap-around zijn. Elke groep levert een Booleaanse productterm op: variabelen die in alle cells van de groep constant zijn worden weergegeven in natuurlijk of complementvorm, variabelen die veranderen worden weggelaten. De vereenvoudigde functie is de logische som (OR) van deze producttermen. Don’t-care-cellen helpen bij het uitbreiden van groepen en kunnen leiden tot kortere expressies.

Beperkingen zijn onder meer de snel toenemende kaartgrootte bij meer variabelen, wat de methode onpraktisch maakt voor veel variabelen. In zulke gevallen worden vaak algebraïsche methoden zoals Quine–McCluskey toegepast. Karnaughkaarten bieden echter een intuïtieve en visuele aanpak voor het minimiseren van logische functies in onderwijs en basisontwerp.