1. Hva et Karnaugh-diagram er
Et Karnaugh-diagram er en sannhetstabell tegnet om som et rutenett. Maurice Karnaugh presenterte det ved Bell Labs i 1953 som en måte å forenkle koblingsnett på med øyet, og det er fremdeles den raskeste måten å minimere en liten boolsk funksjon for hånd: ingen algebra, ingen lover å huske, bare rektangler.
Hver rute i diagrammet rommer én rad fra sannhetstabellen. Det som gjør diagrammet til mer enn en omstokking, er rekkefølgen radene står i: ruter som ligger inntil hverandre skiller seg i nøyaktig én variabel.
Den ene egenskapen gjør hele jobben. Er to naboruter begge sanne, kan variabelen som endrer seg mellom dem ikke være det som gjør uttrykket sant: den faller bort, og ett ledd dekker begge rutene. Å forenkle blir dermed å tegne de største rektanglene du kan.
2. Hvorfor kolonnene ser feilsortert ut
Kolonnene i et Karnaugh-diagram teller ikke 00, 01, 10, 11. De går 00, 01, 11, 10 - reflektert Gray-kode, en rekkefølge der hver verdi skiller seg fra den neste i én bit. Binær telling ville satt 01 ved siden av 10, som skiller seg i to biter, og da ville naboruter ikke fortelle noe.
| A \ BC | 00 | 01 | 11 | 10 |
|---|---|---|---|---|
| 0 | 0 | 1 | 3 | 2 |
| 1 | 4 | 5 | 7 | 6 |
Kantene er naboer de også. Første og siste kolonne skiller seg i én variabel, og det samme gjør øverste og nederste rad, så en gruppe kan løpe ut over den ene kanten og fortsette på den andre - derfor utgjør de fire hjørnene i et diagram med fire variabler én enkelt gruppe. Et Karnaugh-diagram er egentlig tegnet på en torus; det flate arket er en bekvemmelighet.
3. Å gruppere ettallene
For å lese av en minimal sum av produkter dekker du hver rute med et ettall med rektangulære grupper, etter fire regler:
- En gruppe er et rektangel på 1, 2, 4, 8 … ruter - en toerpotens langs hver side.
- En gruppe kan gå rundt kantene av diagrammet, vannrett, loddrett eller begge deler.
- Grupper kan overlappe. En rute som dekkes to ganger koster ingenting; en rute som blir udekket endrer funksjonen.
- Gjør hver gruppe så stor den kan bli, og bruk deretter så få grupper som dekker alle ettallene.
Hver gruppe blir ett ledd. Du leser det av ved å spørre hvilke variabler som holder seg like i hele gruppen: de står i leddet - uendret der de er 1, negert der de er 0 - og hver variabel som endrer seg faller bort. En gruppe på to ruter mister én variabel, en på fire mister to, en på åtte mister tre. Det minimale uttrykket er disjunksjonen av leddene.
4. Et gjennomregnet eksempel
Ta (A ∧ B) ∨ (¬A ∧ C) ∨ (B ∧ C ∧ D). Diagrammet har fire variabler: A og B nedover radene, C og D bortover kolonnene.
| 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 dekker alle ettallene. Den ene er blokken på fire ruter i de to radene der A = 0 og de to kolonnene der C = 1: både B og D endrer seg inne i den, så de faller bort, og leddet er ¬A ∧ C. Den andre er hele raden der A og B begge er 1, tvers over alle fire kolonnene: C og D endrer seg langs den, og igjen står A ∧ B.
Den minimale formen er altså (¬A ∧ C) ∨ (A ∧ B). Det tredje leddet i det opprinnelige uttrykket, B ∧ C ∧ D, er borte: hver rute det dekket var allerede dekket av en av de to gruppene. Slik ser absorpsjon ut når du kan se den.
5. Primimplikanter og nødvendige implikanter
En gruppe som ikke kan gjøres større, kalles en primimplikant. Å liste primimplikantene er den lette halvdelen av oppgaven; å velge hvilke av dem som skal beholdes, er halvdelen som går galt.
Dekkes en rute av bare én primimplikant, er den implikanten nødvendig: ingen minimal form kan utelate den, for ingenting annet dekker den ruten. Ta de nødvendige implikantene først, og dekk så det som er igjen med så få av de gjenværende gruppene som mulig.
Å være grådig - å ta den største gruppen som fremdeles er ledig, gang på gang - er fristende og virker ikke alltid. På et syklisk skjema, der ingen implikant er nødvendig og hver rute dekkes to ganger, kan det grådige valget ende ett ledd lengre enn det beste svaret. Diagrammet på dette nettstedet søker i stedet gjennom alle de gjenværende valgene, noe som med fire variabler ikke koster noe.
6. Å gruppere nullene i stedet
Alt over virker like godt på nullene. Dekk dem med de samme rektanglene, les hver gruppe med negerte literaler - en variabel som er 1 i hele gruppen står negert, en som er 0 står uendret - og bind gruppene sammen med ∧ i stedet for ∨.
Resultatet er et produkt av summer: en konjunksjon av disjunksjoner som er usann i nøyaktig de rutene der uttrykket er usant, og dermed sann alle andre steder. Hvilken av formene som er kortest, avhenger av funksjonen - en formel med få ettall har en kort sum av produkter, en med få nuller et kort produkt av summer - så det lønner seg å lese av begge før du velger.
7. Større diagrammer og don't care-ruter
Fem og seks variabler kan tegnes som to eller fire firevariabeldiagrammer stablet oppå hverandre, der ruter på samme sted i nabolag regnes som naboer. Det virker, men naboskapet som gjorde metoden synlig, er nå noe du må huske i stedet for å se. Utover det gjør Quine-McCluskey-algoritmen den samme jobben i tabellform: den er den mekaniske utgaven av nettopp denne grupperingen, og det er den som kjører bak diagrammene her.
Maskinvaredesign legger til én idé til. Noen inngangskombinasjoner forekommer aldri - et binærkodet desimalsiffer er aldri 1010 - så designeren bryr seg ikke om hva kretsen gjør med dem. Slike ruter merkes med X og kan leses som den verdien som gjør gruppene størst. Diagrammene i denne kalkulatoren bygges ut fra en formel, som gir hver tilordning en verdi, så ingen rute er noen gang et don't care.
8. Prøv selv
Skriv et uttrykk med to til fire variabler i kalkulatoren, så tegnes diagrammet under sannhetstabellen, med hver gruppe ringet inn i sin egen farge og den minimale formen skrevet under. Bytt til produkt av summer for å se nullene gruppert i stedet.