Karnaugh-diagrammer

1. Hva et Karnaugh-diagram er

Et Karnaugh-diagramKarnaugh-diagramEt rutenett over sannhetstabellen som gjør forenklinger synlige.Les hele oppslaget er en sannhetstabellsannhetstabellÉn rad per verditildeling, med formelens verdi i hver.Les hele oppslaget 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 variabelutsagnsvariabelEn bokstav som p eller A som står for et vilkårlig utsagn.Les hele oppslaget.

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.

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 produkterdisjunktiv normalformEt ELLER av OG-er: en disjunksjon av konjunksjoner av literaler.Les hele oppslaget 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, negertnegasjonSnur en sannhetsverdi: ¬p er sann nettopp når p er usann.Les hele oppslaget 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.

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 primimplikantprimimplikantEn gruppe i diagrammet som ikke kan gjøres større.Les hele oppslaget. Å 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 seks 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 literalerliteralEn variabel eller negasjonen av den, som p eller ¬p.Les hele oppslaget - 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 summerkonjunktiv normalformEt OG av ELLER-er: en konjunksjon av klausuler.Les hele oppslaget: en konjunksjonkonjunksjonSann bare når begge delene er sanne: p ∧ q.Les hele oppslaget av disjunksjonerdisjunksjonSann når minst én del er sann: p ∨ q.Les hele oppslaget 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 seks 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.