1. Hvad et Karnaugh-kort er
Et Karnaugh-kort er en sandhedstabel tegnet om som et gitter. Maurice Karnaugh præsenterede det på Bell Labs i 1953 som en måde at forenkle koblingskredse på med øjet, og det er stadig den hurtigste måde at minimere en lille boolesk funktion i hånden: ingen algebra, ingen love at huske, kun rektangler.
Hvert felt på kortet rummer én række af sandhedstabellen. Det, der gør kortet til mere end en omrokering, er rækkefølgen, felterne står i: nabofelter adskiller sig i præcis én variabel.
Den ene egenskab gør hele arbejdet. Hvis to nabofelter begge er sande, kan den variabel, der skifter mellem dem, ikke være grunden til at udtrykket er sandt: den falder væk, og ét led dækker begge felter. At forenkle bliver dermed et spørgsmål om at tegne de størst mulige rektangler.
2. Hvorfor kolonnerne ser forkert sorterede ud
Kolonnerne på et Karnaugh-kort tæller ikke 00, 01, 10, 11. De løber 00, 01, 11, 10 - refleksiv Gray-kode, en orden hvor hver værdi adskiller sig fra den næste i én bit. Binær optælling ville sætte 01 ved siden af 10, som adskiller sig i to bit, og så ville nabofelter ikke fortælle noget.
| A \ BC | 00 | 01 | 11 | 10 |
|---|---|---|---|---|
| 0 | 0 | 1 | 3 | 2 |
| 1 | 4 | 5 | 7 | 6 |
Kanterne er også naboer. Den første og den sidste kolonne adskiller sig i én variabel, og det samme gør den øverste og den nederste række, så en gruppe må løbe ud over den ene kant og fortsætte på den anden - derfor udgør de fire hjørner på et kort med fire variable én enkelt gruppe. Et Karnaugh-kort er i virkeligheden tegnet på en torus; det flade ark er en bekvemmelighed.
3. At gruppere ettallerne
For at aflæse en minimal sum af produkter på kortet dækker du hvert felt med et 1-tal med rektangulære grupper efter fire regler:
- En gruppe er et rektangel på 1, 2, 4, 8 … felter - en potens af to på hver led.
- En gruppe må gå om kanten af kortet, vandret, lodret eller begge dele.
- Grupper må overlappe. Et felt, der dækkes to gange, koster ingenting; et felt, der ikke dækkes, ændrer funktionen.
- Gør hver gruppe så stor, den kan blive, og brug så få grupper, som dækker alle ettallerne.
Hver gruppe bliver til ét led. Det aflæses ved at spørge, hvilke variable der er ens i hele gruppen: de står i leddet - uændrede hvor de er 1, negerede hvor de er 0 - og enhver variabel, der skifter, falder væk. En gruppe på to felter mister én variabel, en på fire mister to, en på otte mister tre. Det minimale udtryk er disjunktionen af leddene.
4. Et gennemregnet eksempel
Tag (A ∧ B) ∨ (¬A ∧ C) ∨ (B ∧ C ∧ D). Kortet har fire variable: A og B ned ad rækkerne, C og D hen ad kolonnerne.
| 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 |
To grupper dækker alle ettallerne. Den ene er blokken på fire felter i de to rækker, hvor A = 0, og de to kolonner, hvor C = 1: både B og D skifter inde i den, så de falder væk, og leddet er ¬A ∧ C. Den anden er hele rækken, hvor A og B begge er 1, hen over alle fire kolonner: C og D skifter hen ad den, og tilbage bliver A ∧ B.
Den minimale form er altså (¬A ∧ C) ∨ (A ∧ B). Det tredje led i det oprindelige udtryk, B ∧ C ∧ D, er forsvundet: hvert felt, det dækkede, var allerede dækket af en af de to grupper. Sådan ser absorption ud, når man kan se den.
5. Primimplikanter og væsentlige implikanter
En gruppe, der ikke kan gøres større, kaldes en primimplikant. At liste primimplikanterne er den lette halvdel af opgaven; at vælge hvilke af dem der skal beholdes, er den halvdel, der går galt.
Hvis et felt kun dækkes af én primimplikant, er den implikant væsentlig: ingen minimal form kan undvære den, for intet andet dækker det felt. Tag de væsentlige implikanter først, og dæk så resten med så få af de øvrige grupper som muligt.
At være grådig - igen og igen at tage den største gruppe, der er tilbage - er fristende og virker ikke altid. På et cyklisk skema, hvor ingen implikant er væsentlig, og hvert felt dækkes to gange, kan det grådige valg ende ét led længere end det bedste svar. Kortet på dette site gennemsøger i stedet alle de resterende muligheder, hvilket ved fire variable ikke koster noget.
6. At gruppere nullerne i stedet
Alt ovenstående virker lige så godt på nullerne. Dæk dem med de samme rektangler, aflæs hver gruppe med negerede literaler - en variabel, der er 1 i hele gruppen, står negeret, en der er 0 står uændret - og forbind grupperne med ∧ i stedet for ∨.
Resultatet er et produkt af summer: en konjunktion af disjunktioner, der er falsk i præcis de felter, hvor udtrykket er falsk, og dermed sand alle andre steder. Hvilken af de to former der er kortest, afhænger af funktionen - en formel med få ettaller har en kort sum af produkter, en med få nuller et kort produkt af summer - så det er værd at aflæse begge på kortet, før man vælger.
7. Større kort og don't care-felter
Fem og seks variable kan tegnes som to eller fire kort med fire variable stablet oven på hinanden, hvor felter samme sted i nabolag regnes som naboer. Det virker, men den naboskab, der gjorde metoden synlig, er nu noget, man skal huske frem for at se. Derudover gør Quine-McCluskey-algoritmen det samme arbejde i tabelform: den er den mekaniske udgave af netop denne gruppering, og det er den, der kører bag kortene her.
Hardwaredesign tilføjer én idé mere. Nogle inputkombinationer forekommer aldrig - et binært kodet decimalciffer er aldrig 1010 - så designeren er ligeglad med, hvad kredsen gør ved dem. De felter markeres med et X og må læses som den værdi, der gør grupperne størst. Kortene i denne beregner bygges ud fra en formel, som giver hver tildeling en værdi, så intet felt er her et don't care.
8. Prøv selv
Skriv et udtryk med to til fire variable i beregneren, så tegnes kortet under sandhedstabellen med hver gruppe indrammet i sin egen farve og den minimale form skrevet nedenunder. Skift til produkt af summer for at se nullerne grupperet i stedet.